1CS553 Lecture Interprocedural Analysis and Optimization 2Interprocedural Analysis Last time– Interprocedural analysis Today– Interprocedural alias analysis– Interprocedural optimizationCS553 Lecture Interprocedural Analysis and Optimization 3Jump Functions and Return Jump Functions for ICP int a,b,c,d; void foo(e){ a = b + c; d = e + 2; } foo(3); Partial Transfer Functions for Interprocedural Alias Analysis– funcOutput = PTF(funcInput)– use memoization– PTF lazily computed for each input pattern that occursImproving the Efficiency of the Iterative Algorithm2CS553 Lecture Interprocedural Analysis and Optimization 4Partial Transfer Function [Wilson et. al. 95] Example [http://www.cs.princeton.edu/~jqwu/Memory/survey.html]main() { int *a,*b,c,d; a = &c; b = &d;S0 foo(&a, &b); for (i = 0; i<2; i++) {S1 bar(&a,&a);S2 bar(&b,&b);S3 bar(&a,&b);S4 bar(&b,&a); }}void bar(int **i, int **j) { foo(i,j); }void foo(int **x, int **y){ int *temp = *x; *x = *y; *y = temp;}CS553 Lecture Interprocedural Analysis and Optimization 5Characterizing Interprocedural Analysis Definiteness– May (possible) versus must (definite) Flow sensitivity– Sensitive (consider control flow)– Requires iterative data-flow analysis or similar technique– More accurate than flow-insensitive– Insensitive (ignore control flow)– Can compute in linear time– May information only Context sensitivity– Sensitive (polyvariant analysis)– Re-analyze callee for each caller– Variations based on how much of the call path is maintained– Insensitive (monovariant analysis)– Perform one analysis independent of callers3CS553 Lecture Interprocedural Analysis and Optimization 6Emami 1994 Overview– Compute L and R locations to implement flow-sensitive data-flow analysis– Uses invocation graph for full context-sensitivity– Can be exponential in program size– Handles function pointers Characterization of Emami– Whole program– Flow-sensitive– Context-sensitive– May and must analysis– Alias representation: points-to– Heap modeling: one heap variable– Aggregate modeling: fields and first array elementCS553 Lecture Interprocedural Analysis and Optimization 7Choi 1993 Overview– Iterates over call graph with callsite labeled edges– Iterates over Sparse Evaluation Graph for each procedure Characterization of Choi– Whole program– Flow-sensitive– Context-sensitive (one-level)– May analysis– Alias representation: compact pairs (similar to points-to)– Heap modeling: k names for each malloc stmt– Aggregate modeling: fields?4CS553 Lecture Interprocedural Analysis and Optimization 8Burke 1995 Overview– Iterates over call graph with callsite labeled edges– Iterates over Sparse Evaluation Graph for each procedure– Use kill information before propagating on call graph– Handles function pointers Characterization of Burke– Whole program– Flow-insensitive (kill info is propagated along call edges)– Context-sensitive– May analysis– Alias representation: compact pairs (similar to points-to)– Heap modeling: k names for each malloc stmt?– Aggregate modeling: fields?CS553 Lecture Interprocedural Analysis and Optimization 9Alias/Pointer Analysis Summary5CS553 Lecture Interprocedural Analysis and Optimization 10Interprocedural Analysis vs. Interprocedural Optimization Interprocedural analysis– Gather information across multiple procedures(typically across the entire program)– Can use this information to improve intraprocedural analyses andoptimization (e.g., CSE) Interprocedural optimizations– Optimizations that involve multiple procedurese.g., Inlining, procedure cloning, interprocedural register allocation– Optimizations that use interprocedural analysisCS553 Lecture Interprocedural Analysis and Optimization 11Alternative to Interprocedural Analysis: Inlining Idea– Replace call with procedure body Pros– Reduces call overhead– Exposes calling context to procedure body– Exposes side effects of procedure to caller– Simple! Cons– Code bloat (decrease efficacy of caches, branch predictor, etc)– Can’t always statically determine callee (e.g., in OO languages)– Library source is usually unavailable– Can’t always inline (recursion)6CS553 Lecture Interprocedural Analysis and Optimization 12Inlining Policies The hard question– How do we decide which calls to inline? Many possible heuristics– Only inline small functions– Let the programmer decide using an inline directive– Use a code expansion budget [Ayers, et al ’97]– Use profiling or instrumentation to identify hot paths—inline along thehot paths [Chang, et al ’92]– JIT compilers do this– Use inlining trials for object oriented languages [Dean & Chambers ’94]– Keep a database of functions, their parameter types, and the benefit ofinlining– Keeps track of indirect benefit of inlining– Effective in an incrementally compiled languageOblivious to callsiteCS553 Lecture Interprocedural Analysis and Optimization 13Inlining versus Interprocedural Analysis How effective is inlining?– Richardson & Ganapathi [1989] compared it to interprocedural analysis– Context– Pascal on RISC processors– Used interprocedural USE, MOD, ALIASES information Results– Interprecedural analysis resulted in small benefit (<2%)– Simple link-time inlining provided more benefit (10%)7CS553 Lecture Interprocedural Analysis and Optimization 14Alternative to Interprocedural Analysis: Cloning Procedure Cloning/Specialization– Create a customized version of procedure for particular call sites– Compromise between inlining and interprocedural optimization Pros– Less code bloat than inlining– Recursion is not an issue (as compared to inlining)– Better caller/callee optimization potential (versus interproceduralanalysis) Cons– Still some code bloat (versus interprocedural analysis)– May have to do interprocedural analysis anyway– e.g. Interprocedural constant propagation can guide cloningCS553 Lecture Interprocedural Analysis and Optimization 15Procedure Cloning Abstract implementation– Given a set of call sites to procedure pe.g., {c1,c2,c3,c4,c5,c6}– Partition them into equivalence classes of “similar” call sitese.g., {{c1,c4},{c2,c3},{c6}}– Meaning of “similar” depends on the intended benefite.g., For constant propagation, partition according to constant valuedactual parameters Important question– How do we partition the call