|
Inline expansion or inlining for short is a compiler optimization which "expands" a function call site into the actual implementation of the function which is called, rather than each call transferring control to a common piece of code. This reduces overhead associated with the function call, which is especially important for small and frequently called functions, and it helps call-site-specific compiler optimizations, especially constant propagation. The main drawback is that the expansion usually results in a larger binary code, which can actually hurt performance if it damages locality of reference or exceeds resource constraints. Compiler optimization techniques are optimization techniques that have been programmed into a compiler. ...
In computer science, a subroutine (function, procedure, or subprogram) is a sequence of code which performs a specific task, as part of a larger program, and is grouped as one or more statement blocks; such code is sometimes collected into software libraries. ...
In computer science constant propagation (cprop) is an optimization performed by compilers. ...
In computer science, locality of reference, sometimes also called the principle of locality, is a concept which deals with the process of accessing a single resource multiple times. ...
In the context of functional programming languages, inline expansion is often referred to as beta reduction, a term used in the lambda calculus, the formal language underlying these languages. Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
Implementation Once the compiler has decided to inline a particular function, it is usually a simple matter to do so. Depending on whether one wants cross-language inline functions, the inlining can be done with either a high-level intermediate representation, like abstract syntax trees, or a low-level intermediate representation. In either case, one simply computes the arguments, stores them in variables corresponding to the function's arguments, and then inserts the body of the function at the call site. A diagram of the operation of a typical multi-language compiler. ...
In computing, an intermediate representation is a data structure that is constructed from input data to a program, and from which part or all of the output data of the program is constructed in turn. ...
Lloyd smells. ...
A parameter is a measurement or value on which something else depends. ...
Function inlining can also be performed at link-time, which enables inlining of functions whose source is not available such as library functions (see link-time optimization) and at run time, which enables using dynamic profiling information to make better decisions about which functions to inline, as in the Java Hotspot compiler. In computer science, runtime describes the operation of a computer program, the duration of its execution, from beginning to termination (compare compile time). ...
HotSpot is the primary Java Virtual Machine for desktops and servers produced by Sun Microsystems. ...
Here's a simple example of inline expansion performed "by hand" at the source level in the C programming language: The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ...
int pred(int x) { if (x == 0) return 0; else return x - 1; } Before inlining: int f(int y) { return pred(y) + pred(0) + pred(y+1); } After inlining: int f(int y) { int temp = 0; if (y == 0) temp += 0; else temp += y - 1; if (0 == 0) temp += 0; else temp += 0 - 1; if (y+1 == 0) temp += 0; else temp += (y + 1) - 1; return temp; } Note that this is only an example; in an actual C application, it would be preferable to use an inlining language feature such as parameterized macros or inline functions to tell the compiler to perform this transformation. In computer science, a parameterized macro is a type of macro that is able to insert given objects into its expansion. ...
In computer science, an inline function is a programming language construct used to suggest to a compiler that a particular function be subjected to in-line expansion; that is, it suggests that the compiler insert the complete body of the function in every context where that function is used. ...
Since the compiler can tell before inlining that the results of this function are going to be added, and a value plus zero is the same, it can even forego adding the code for the true part of 'pred' when inlining. E.g.
After inlining and optimization:
int f(int y) { int temp = 0; if (y != 0) temp += y - 1; if (0 != 0) temp += 0 - 1; if (y+1 != 0) temp += (y + 1) - 1; return temp; } Where != means 'not equal to'. It may then notice that the second part will never evaluate to true and be executed, and remove it too:
After inlining and further optimization:
int f(int y) { int temp = 0; if (y != 0) temp += y - 1; if (y+1 != 0) temp += (y + 1) - 1; return temp; } The compiler will also generally recognise that in the second conditional statement (y+1)-1 = y, and substitute it with adding just y in that case.
Benefits Inline expansion itself is an optimization, since it eliminates call overhead, but it is much more important as an enabling transformation. That is, once the body of the function is expanded in the context of its call site, often with arguments that may be fixed constants, the code is opened to a variety of new optimizations that were not possible before. For example, a branch using an argument may turn out to be always true or always false in this one case, allowing dead code elimination, loop-invariant statements may be moved outside a loop, or a variable may become a candidate for induction variable elimination. In mathematics and the mathematical sciences, a constant is a fixed, but possibly unspecified, value. ...
Dead code elimination is a technique used in computer science to reduce program size by removing code which can never be executed. ...
Loop-invariant code in an imperative programming language consists of statements which could be moved to before the loop (if the loop always terminates), or after the loop, without affecting the semantics of the program. ...
In our C example, we see that optimization opportunities abound. We can reduce it in the following steps:
- The
temp += 0 statements do nothing. We can remove them. - The condition
0 == 0 is always true, so we can use just the true branch (which does nothing). - The condition
y+1 == 0 is equivalent to y == -1. - The expression
(y + 1) - 1 reduces to simply y (assuming wraparound overflow semantics) - The expressions
y and y+1 cannot both equal zero. This leaves three cases we can explicitly consider. Our new function looks like: int f(int y) { if (y == 0) return y; /* or return 0 */ else if (y == -1) return y - 1; /* or return -2 */ else return y + y - 1; }
Problems Replacing a call site with an expanded function body can present several problems that may make this "optimization" actually hurt performance: This article needs to be cleaned up to conform to a higher standard of quality. ...
- In applications where code size is more important than speed, such as many embedded systems, inlining is usually disadvantageous except for very small functions.
- The increase in code size may cause a small, critical section of code to no longer fit in the cache, causing cache misses and slowdown.
- The added variables from the inlined procedure may consume additional registers, and in an area where register pressure is already high this may force spilling, which causes additional RAM accesses.
- A language specification may allow a program to make additional assumptions about arguments to procedures which it can no longer make after the procedure is inlined.
- If code size is increased too much, resource constraints such as RAM size may be exceeded, leading to programs that either cannot be run or that cause thrashing.
Typically, a compiler is aware of these issues and strives to choose which functions to inline in such a way that performance is only enhanced in most cases. An embedded system is a special-purpose computer system, which is completely encapsulated by the device it controls. ...
Diagram of a CPU memory cache A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. ...
In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to commonly used values—typically, the values being in the midst of a calculation at a given point in time. ...
This page is a candidate to be moved to Wiktionary. ...
Selection methods and language support Many compilers aggressively inline functions wherever it is beneficial to do so. Although this can lead to larger executables, this has nevertheless become more and more desirable as growth of memory capacities have outpaced growth of CPU speed. This automatic type of inlining is a critical optimization in functional languages and object-oriented programming languages, which rely on it to give enough context to their typically small functions to make classical optimization effective. Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...
An object-oriented programming language (also called an OO language) is one that allows or encourages, to some degree, object-oriented programming methods. ...
In imperative programming languages, the approach to inline functions is quite different, since functions are typically much larger. Usually only obvious or key functions are inlined, using language features like inline functions, or in their absence, simple source-level constructs such as parameterized macros. In either case, the programmer chooses which functions to inline manually, although the compiler may in some cases not be able or willing to inline a function marked for inlining. In computer science, imperative programming, as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. ...
In computer science, an inline function is a programming language construct used to suggest to a compiler that a particular function be subjected to in-line expansion; that is, it suggests that the compiler insert the complete body of the function in every context where that function is used. ...
In computer science, a parameterized macro is a type of macro that is able to insert given objects into its expansion. ...
See also Figure of the linking process, where object files and static libraries are assembled into a new library or executable. ...
A macro in computer science is an abstraction, whereby a certain textual pattern is replaced according to a defined set of rules. ...
In computing, partial evaluation is a technique for program optimization by specialization. ...
External links - "Eliminating Virtual Function Calls in C++ Programs" by Gerald Aigner and Urs Hölzle
- "Reducing Indirect Function Call Overhead In C++ Programs" by Brad Calder and Dirk Grumwald
- ALTO - A Link-Time Optimizer for the DEC Alpha
- Article "Advanced techniques" by John R. Levine
- Article "Inlining Semantics for Subroutines which are Recursive" by Henry G. Baker
- Article "Whole Program Optimization with Visual C++ .NET" by Brandon Bray
|
Feeds |
Contact