Lecture 6 Program Flow AnalysisWhy Analyze Program Flow?Program Flow AnalysisMotivation: Constant PropagationCode OptimizationsBasic BlocksBasic Block Partitioning AlgorithmExample: Finding LeadersSlide 9Slide 10Slide 11Example: Forming the Basic BlocksControl Flow Graph (CFG)Example: Control Flow Graph FormationExample : Control Flow Graph FormationSlide 16CFGs are MultigraphsIdentifying loopsDominatorsDomination RelationSlide 21An ExampleQuestionExampleDominance IntuitionSlide 26Slide 27Slide 28Slide 29Dominator TreeA Dominator Tree (Example)Finding LoopsDefinitionSlide 34How to Find Loops?Natural LoopsSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48PowerPoint PresentationSlide 50Slide 51RegionsPoints and PathsSlide 54Slide 55Global Dataflow AnalysisDefinition and UseReach and KillDefinition Reachability: ExampleProblem Formulation: Example 2Available Expressions (Sub-expression Elimination)Example: Available ExpressionExample: Redundant ExpressionD-U and U-D Chains (Motivation)UD chainDU chainReaching DefinitionsGlobal Data-Flow AnalysisData-Flow Analysis of Structured ProgramsSlide 70Dataflow Equations for Reaching DefinitionSlide 72Dataflow Analysis: An ExampleSolution?SolutionIterative Algorithm for Reaching DefinitionsSlide 77Slide 78Slide 79Slide 80Algorithm ConvergenceConclusionsReferences and CopyrightLecture 6Lecture 6Program Flow AnalysisProgram Flow AnalysisForrest BrewerRyan KastnerJose AmaralWhy Analyze Program Flow?Why Analyze Program Flow?Determine run-time resource and time requirements–How does program allocate and use memory?–What computation resources are used?–What is the expected run-time?–What are the best and worst-case run-time profiles?•Need for real-time analysis in Embedded SystemsPartition the results using the program structure–Determine the potential for Optimization•Optimize use of resources–Restructure to lower worst-case time bounds•Ease real-time constraintsBasic blockControl Flow Analysis: determine control structure of a program and build Control Flow GraphsData Flow Analysis: determine the flow of data values and build Data Flow GraphsSolution for the Flow Analysis Problem: propagate data flow information along flow graph.ProgramProcedureInterproceduralIntra-proceduralLocalFlow analysisData flow analysisControl flow analysisProgram Flow AnalysisProgram Flow AnalysisMotivation: Constant PropagationMotivation: Constant PropagationS1: A  2 (def of A)S2: B  10 (def of B)Sk: C  A + B Is C a constant?Sk+1: for (I=1;I++;I<C) {...C is really a constant–easy to estimate run-timeHard to tell locallyCode optimization - a program transformation that preserves correctness and improves the performance (e.g., execution time, size, resource contention, other metrics) of the input program. Code optimization may be performed at multiple levels of program representation:1. Source code 2. Intermediate code3. Target machine code Optimized vs. optimal - the term “optimized” is used to indicate a relative performance improvement. “Optimal” is a claim of non-inferiority among target set of programs.Code OptimizationsCode OptimizationsBasic BlocksBasic BlocksOnly the last statement of a basic block can be a branch statement and only the first statement of a basic block can be a target of a branch. (Semantically, control branches and start targets take place only at beginning and end of basic blocks)Def: A basic block is a sequence of consecutive intermediate language statements in which flow of control can only enter at the beginning and leave at the end.(AhoSethiUllman, pp. 529)Basic Block Partitioning AlgorithmBasic Block Partitioning Algorithm(AhoSethiUllman, pp. 529)1. Identify leader statements (i.e. the first statements of basic blocks) by using the following rules:(i) The first statement in the program is a leader(ii) Any statement that is the target of a branch statement is a leader (for most intermediate languages these are statements with an associated label)(iii) Any statement that immediately follows a branch or return statement is a leaderExample: Finding LeadersExample: Finding Leadersbegin prod := 0; i := 1; do begin prod := prod + a[i] * b[i]; i = i+ 1; end while i <= 20endThe following code computes the inner product of two vectors. Source code(1) prod := 0(2) i := 1(3) t1 := 4 * i(4) t2 := a[t1](5) t3 := 4 * i(6) t4 := b[t3](7) t5 := t2 * t4(8) t6 := prod + t5(9) prod := t6(10) t7 := i + 1(11) i := t7(12) if i <= 20 goto (3)Three-address code(AhoSethiUllman, pp. 529)Example: Finding LeadersExample: Finding Leadersbegin prod := 0; i := 1; do begin prod := prod + a[i] * b[i] i = i+ 1; end while i <= 20endThe following code computes the inner product of two vectors. (1) prod := 0(2) i := 1(3) t1 := 4 * i(4) t2 := a[t1](5) t3 := 4 * i(6) t4 := b[t3](7) t5 := t2 * t4(8) t6 := prod + t5(9) prod := t6(10) t7 := i + 1(11) i := t7(12) if i <= 20 goto (3)(13) …Source codeThree-address codeRule (i)Example: Finding LeadersExample: Finding Leadersbegin prod := 0; i := 1; do begin prod := prod + a[i] * b[i] i = i+ 1; end while i <= 20endThe following code computes the inner product of two vectors. (1) prod := 0(2) i := 1(3) t1 := 4 * i(4) t2 := a[t1](5) t3 := 4 * i(6) t4 := b[t3](7) t5 := t2 * t4(8) t6 := prod + t5(9) prod := t6(10) t7 := i + 1(11) i := t7(12) if i <= 20 goto (3)(13) …Source codeThree-address codeRule (i)Rule (ii)Example: Finding LeadersExample: Finding Leadersbegin prod := 0; i := 1; do begin prod := prod + a[i] * b[i] i = i+ 1; end while i <= 20endThe following code computes the inner product of two vectors. (1) prod := 0(2) i := 1(3) t1 := 4 * i(4) t2 := a[t1](5) t3 := 4 * i(6) t4 := b[t3](7) t5 := t2 * t4(8) t6 := prod + t5(9) prod := t6(10) t7 := i + 1(11) i := t7(12) if i <= 20 goto (3)(13) …Source codeThree-address codeRule (i)Rule (ii)Rule (iii)Example: Forming the Basic BlocksExample: Forming the Basic BlocksBasic Blocks: (1) prod := 0(2) i := 1(3) t1 := 4 * i(4) t2 := a[t1](5) t3 := 4 * i(6) t4 := b[t3](7) t5 := t2 * t4(8) t6 := prod + t5(9) prod := t6(10) t7 := i + 1(11) i := t7(12) if i <= 20 goto (3)(13) …B1B2B3(1) prod := 0(2) i := 1(3) t1 := 4 * i(4) t2 := a[t1](5) t3 := 4 *