Advanced Compilers CMPSCI 710 Spring 2003 Interprocedural AnalysisTopicsAliasingAliasing Examples, IAliasing Examples, IIAlias Examples, IIIInterprocedural AnalysisProblems with Interprocedural AnalysisAnalysis SensitivityContext SensitivitySummary InformationTwo Types of InformationPropagation Summaries: ExamplesSide-Effect Summaries: ExamplesComputing SummariesImplementing IPA: The Call GraphCall Graph ExampleSide-Effect SummarizationSide-Effect Summary ExampleAlternatives to IPA: InliningAlternatives to IPA: CloningCloningConclusionUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer ScienceEmery BergerUniversity of Massachusetts, AmherstAdvanced CompilersCMPSCI 710Spring 2003Interprocedural AnalysisUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science2TopicsUp to nowIntraprocedural analysesDataflow analysesDefUse, SSARegister AllocationSchedulingJust for individual proceduresToday: Interprocedural analysisacross/between proceduresWhy?UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science3AliasingFormals and/or globals may be aliasedTwo names point to same locationOnly form of aliasing for Java, FortranAt procedure callGlobals may be modified or usedActual args may be modified or usedUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science4Aliasing Examples, INeed alias analysis to do:Instruction schedulingRegister allocationUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science5Aliasing Examples, IINeed alias analysis to do:Dead code eliminationCode motionUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science6Alias Examples, IIINeed alias analysis to do:Constant propagationTo perform alias analysis, we need…UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science7Interprocedural AnalysisGoalsEnable standard optimizations even with procedure callsReduce call overhead for proceduresEnable optimizations not possible for single proceduresOptimizationsRegister allocationLoop transformationsCSE, etc.UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science8Problems withInterprocedural AnalysisNot without drawbacksWhole-program analysisWhat about libraries?Separate compilation requires recompilation analysis [Burke & Torczon 93]ExpensiveDoesn’t scale well, or worseSome problems intractablee.g., Flow-sensitive killUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science9Analysis SensitivityFlow-insensitiveWhat may happen (on at least one path)Linear-timeFlow-sensitiveConsider control flow (what must happen)Iterative data-flow: possibly exponentialContext-insensitiveCall treated the same regardless of caller“Monovariant” analysisContext-sensitiveReanalyze callee for each caller“Polyvariant” analysisMore sensitivity ) more accuracy, but more expenseUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science10Context SensitivityReanalyze callee as if procedure was inlinedToo expensive in space & timeRecursion?Approximate context sensitivity:Reanalyze callee for k levels of calling contextUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science11Summary InformationAnother approach: summarize each procedureEffect/result of called procedure for callersEffect/input of callers for called procedureStore in database for use by later optimization passPros:+Concise+Fast+Practical: separate compilationCons:-ImpreciseUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science12Two Types of InformationTrack info that flows into procedures“Propagation problems”, e.g.:which formals are constant?which formals are aliased to globals?Track info that flows out of procedures“Side effect problems”, e.g.:which globals defined/used by procedure?which locals defined/used by procedure?Which actual parameters defined by procedure?UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science13Propagation Summaries: ExamplesMAY-ALIASFormals that may be aliased to globalsMUST-ALIASFormals definitely aliased to globalsCONSTANTFormals that are defi n itely constantUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science14Side-Effect Summaries: ExamplesMODVariables poss ibly modified (defined) by procedure callREFVariables poss ibly referenced (used) by procedureKILLVariables that are definit ely killed in procedureUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science15Computing SummariesBottom-up (MOD, REF, KILL)Summarizes effect of callTop-down (MAY-ALIAS)Summarizes information about callerBi-directional (AVAIL, CONSTANT)Info to/from caller & calleeUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science16Implementing IPA: The Call GraphRepresent procedure call relationshipby call graphG = (V,E,start)Each procedure is unique vertexCall site = edge between caller & callee(u,v) = call from u to vCan label with source lineCycles represent recursionUUNIVERSITY OF NIVERSITY OF