CSc 520 — Principles of Programming Languages29 : Control Structures — Inline vs. MacrosChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergMarch 31, 20081 Inline Expansion• The most important and popular inter-procedural optimization is inline expansion, that is replacingthe call of a procedure with the procedure’s body.• Why would you want to perform inlining? There are several reasons:1. There are a number of things that happen when a procedure call is made:(a) evaluate the arguments of the call,(b) push the arguments onto the stack or move them to argument transfer registers,(c) save registers that contain live values and that might be trashed by the called routine,(d) make the jump to the called routine,2 Inline Expansion. . .• 1. continued. . .(e) make the jump to the called routine,(f) set up an activation record,(g) execute the body of the called routine,(h) return back to the callee, possibly returning a result,(i) deallocate the activation record.2. Many of these actions don’t have to be performed if we inline the callee in the caller, and hencemuch of the overhead associated with pr ocedure calls is optimized away.3. More importantly, programs written in modern imperative and OO-languages tend to be so litteredwith procedure/method calls. . . .3 Inline Expansion. . .• 3. . . . This is the result of programming with abstract data types. Hence, there is often very littleopportunity for optimization. However, when inlining is performed on a sequence of procedure1calls, the code from the bodies of several procedures is combined, opening up a larger scope foroptimization.• There are problems, of course. Obviously, in most cases the size of the procedure call code will be lessthan the size of the callee’s body’s code. So, the size of the program will increase as calls are expanded.4 Inline Expansion. . .• A larger executable takes longer to load from secondary storage and may affect the paging behaviorof the machine. More importantly, a routine (or an inner loop of a routine) that fits within theinstruction-cache before expansion, might be too large for the cache after expansion.• Also,larger procedures need more registers (the register pressure is higher) than small ones. If,after expansion, a procedure is so large (or contains such complicated expressions) that the number ofregisters provided by the architecture is not enough, then spill code will have to be inserted when werun out of registers.5 Inline Expansion. . .• Several questions remain. Which procedures should be inlined? Some languages (C++, Ada, Modula-3) allow the user to specify (through a keyword or pragma) the procedures that should be eligible forexpansions. However, this implies that a given procedure should always be expanded, regardless ofthe environment in which it is called. This may not be the best thing to do. For example, we mightconsider inlining a call to P inside a tightly nested inner loop, but choose not to do so in a moduleinitialization code that is only executed once.6 Inline Expansion. . .• Some compilers don’t rely on the user to decide on what should be inlined. Instead they use1. A static heuristic, such as “procedures which are(a) shorter than 10 lines and have fewer than 5 parameters or(b) are leaf routines (i.e. don’t make any calls themselves)are candidates for inlining”.2. A heuristic based on profiling. After running the program through a profiler we know how manytimes each procedure is likely to be called from each call site. Only inline small, frequently calledprocedures.7 Inline Expansion. . .• How do we inline across module boundaries? We need access to the code of the called procedure. I fthe procedure is declared in a separately compiled module, this code is not available. What do we do?Good question. . .• What’s the difference between inlining and macro expansion? Inlining is performed after semanticanalysis, macro expansion before.28 Inline Expansion. . .• At which level do we perform the inlining?intermediate code Most common.source code Some source-to-source translators perform inlining.assembly code Doable (with some compiler cooperation), but unusual.9 Algorithm1. Build the call graph:(a) Create an empty directed graph G.(b) Add a node for each routine and for the main program.(c) If procedure P calls procedure Q then insert a directed edge P → Q.P RSTMainQV10 Algorithm. . .• G is actually a multigraph since a procedure might make multiple calls to the same procedure.• Beware of indirect calls through procedure parameters or variables, as well as method invocations!11 Algorithm. . .2. Pick routines to inline. Possible heuristics:(a) Discard recursive routines (Perform a topological sort of the call graph. Cycles indicate recursion.)or just inline them one or two levels deep.(b) Select routines with indegree=1.(c) Select calls to small routines in inner loops.(d) Rely on user-defined INLINE pragmas.(e) Use profiling information.(f) Consider effects on caching, paging, register pressure, total code size, ...(g) ...12 Algorithm. . .3. FOR each call P (a1, · · · , an) in Q to inline procedure P (f1, · · · , fn), in reverse topological order ofthe call graph DO(a) Replace the call P (a1, · · · , an) with P ’s body.3(b) Replace references to call-by-reference formal fkwith a reference to the corresponding actualparameter ak.(c) For each call-by-value formal parameter fkcreate a new local ck. Insert code to copy the call-by-value actual akinto ck. Replace references to the call-by-value formal fkwith a reference to itscopy ck.(d) For each of P ’s local variables lkcreate a new local vkin Q. Replace references to local variablelkwith a reference to vk.13 Topological OrderExample:main(){ Q(); ... Q(); };P(){ R(); ... S(); };T(){ R();}; R(){S();};S(){ V();}; Q(){}; V(){};Topological Order:7PRSTMainQV132456814 Topological Order. . .• Performing the inlining in reverse topological order saves time. For example, expanding V in S beforeexpanding S in R and P is faster than expanding S in P, then S in R, and then V in P and R.• Note: there is no path main → T. Maybe T could be deleted?15 Inlining Example (Original)TYPE T = ARRAY [1..100] OF CHAR;PROCEDURE P (n : INTEGER; z : T; VAR y :INTEGER);VAR i : INTEGER;BEGINIF n < 100 THENFOR i := 1 TO n DO y := z[i] + y; z[i] := 0; ENDFORENDIFEND P;VAR S : INTEGER; A : T;BEGIN P(10, A, S); END16
View Full Document
Unlocking...