Interprocedural Analysis & Optimization COMP 512 Rice University Houston, Texas Spring 2009 Copyright 2009, Keith D. Cooper & Linda Torczon, all rights reserved. Students enrolled in Comp 512 at Rice University have explicit permission to make copies of these materials for their personal use. Second Lecture 1!COMP 512, Spring 2009!COMP 512, Spring 2009! 2!Motivation Why consider analysis & optimization of whole programs? 1. To produce better code around call sites >! Avoid saves & restores >! Understand cross-call data flow 2. To produce tailored copies of procedures >! Often, full generality is unneeded >! Constant-valued parameters & globals, aliases 3. To provide sharper global analysis >! Improve on conservative assumptions >! Particularly true for global variables 4. To present the optimizer with more context >! Languages (& programs) with short procedures >! Assumes that context improves code quality Perception is that calls are expensive (& disruptive)COMP 512, Spring 2009! 3!Interprocedural Analysis & Optimization Whole program compilation •! Old ideas •! Trendy subject Component technologies •! Interprocedural analysis >! Control-flow analysis (derive a call graph) >! Data-flow analysis >! Estimating execution frequencies •! Interprocedural optimization >! Inline substitution & procedure cloning >! Activation record merging, cross-jumping, … •! Recompilation analysis {Automatic detection of parallelism Link-time analysis & optimization COMP 512, Spring 2009! 4!Fact versus Folklore Folklore: Create a single large graph & optimize it all •! Get all the benefits of analyzing the whole program •! See all the opportunities •! This should show the upper bound on improvement Fact: The details get in the way •! Single procedure methods get overwhelmed with details >! Imagine a data-flow analysis with all the names >! Two choices–summarization or slow compilation >! And most of the detail is local •! Not clear that this approach leads to better code •! It does lead (inexorably ) to slower compilation Fortran H limited analysis to 996 names, with 2 bits for the rest See, for example, “Interprocedural optimization: Experimental Results,” S. Richardson & M. Ganapathi, Software--Practice and Experience, 19, 149-169, 1989.COMP 512, Spring 2009! 5!Fact versus Folklore Folklore: Overhead of calls is significant •! For small procedures, linkage can dominate useful work •! Should eliminate calls whenever possible (avoid the cost ) •! Lead scientific programmers to non-modular style Fact: Calls have costs, but they also have benefits •! Actual costs are a function of procedure size and call frequency •! Calls provide a much needed separation of concerns >! Imagine nesting all those register lifetimes >! Imagine using a spill-everywhere allocator! >! Few allocators have the courage to spill everything •! Eliminating calls can slow the code down COMP 512, Spring 2009! 6!Fact versus Folklore Folklore: Modular codes need interprocedural optimization •! Higher ratio of calls to real work •! Less straight-line code for optimizer Fact: Opportunities are limited •! Smaller procedures have smaller name spaces >! Fewer interactions to improve >! Fewer common overheads, like address expressions •! Procedure call optimization is more important >! Calls take a larger fraction of the time >! Inline calls to eliminate linkages & create context !! The classic strategy for OO languages >! Avoid copying & de-referencing parametersCOMP 512, Spring 2009! 7!What are the problems? Scoping effects limit opportunities for improvement •! Intraprocedural methods assume a common name space >! Redundancy elimination must “see” definitions >! Constant propagation must “know” values •! Entry & calls tap into an unknown environment •! Formal!actual mapping is onto, not one-to-one At source level, only formals & globals interact across procedures! •! Modularity limits use of globals •! Call-by-value forces values through memory •! Modular programs may be inherently less efficient! Fortran may be the best case scenario ! COMP 512, Spring 2009! 8!What are the problems? Different calls to p have different properties •! Frequency of the call •! Environment that p inherits >! Mapping from parameters to value (& locations) >! Constant values & known values >! Size of task •! Surrounding execution context >! Is call in a parallel loop? >! Which registers are unused? •! Procedure-valued parameters (OOP) May want to optimize distinct calls differently >! Consider simple issue, such as caller-saves vs. callee-saves p n m 1,000 10 p must function correctly in both contextsCOMP 512, Spring 2009! 9!What are the problems? Profitability In real life, its hard to pick the right strategy •! Combination of program, compiler, input data •! No single strategy fits all cases 0.500.600.700.800.901.001.101.201.30vo rt ex shal64 efie304 wanal1 wave euler cedeta linpackdP r o g r a m% Imp rovement3081MIPSSequentConvexStardentInlining eliminated •! > 89% dynamic calls •! > 75% static calls Unpredictable results Cooper, Hall, & Torczon, S–P&E, June, 1991 Many commercial groups have secret (bad) anecdotes about inlining! * COMP 512, Spring 2009! 10!What are the problems? Compilers are engineered objects •! Implementations contain unwritten assumptions >! Code shape >! Finite data structures •! Call sites provide some great big hints >! Limit the global impact of local effects >! Break lifetimes & reset analysis •! Smaller procedures map more easily onto small resources >! 32 (or 32 + 32) registers >! Less control-flow " better knowledge Separation of concerns •! Global optimization work well with plentiful resources •! In larger scopes, resources are taxed & separation breaks downCOMP 512, Spring 2009! 11!What are the problems? What happens at a procedure call? •! Use worst case assumptions about side effects •! Leads to imprecise intraprocedural information •! Leads to explosion in intraprocedural def-use chains procedure joe(i,j,k) l # 2 * k if (j = 100) then m # 10 * j else m # i call ralph(l,m,k) o # m * 2 q # 2 call ralph(o,q,k) write q, m, o, l procedure main call joe( 10, 100, 1000) procedure ralph(a,b,c) b # a * c / 2000 What value is printed for q? Did ralph() change it? Since j = 100 this always executes the then clause and always m has the value 1000 With perfect knowledge, the compiler could replace