Spring 2009 Lecture 9: Introduction to Program Analysis and Optimization
by user
Comments
Transcript
Spring 2009 Lecture 9: Introduction to Program Analysis and Optimization
Spring 2009 Lecture 9: Introduction to Program Analysis and Optimization Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Program g Analysis y • Compile-time reasoning about run-time behavior of program – Can discover things that are always true: • “x “ is i always l 1 in i the th statement t t t y = x + z”” • “the pointer p always points into array a” • “the statement return 5 can never execute” – Can infer things that are likely to be true: • “the reference r usually refers to an object of class C” • “the the statement a = b + c appears to execute more frequently than the statement x = y + z” – Distinction between data and control-flow properties Saman Amarasinghe 3 6.035 ©MIT Fall 1998 Transformations • Use analysis results to transform program • Overall goal: improve some aspect of program • Traditional goals: –R Reduce d number b off executed d instructions i i – Reduce overall code size • Other goals emerge as space becomes more complex – Reduce number of cycles • Use vector or DSP instructions • Improve instruction or data cache hit rate – Reduce power consumption – Reduce memory usage Saman Amarasinghe 4 6.035 ©MIT Fall 1998 Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Control Flow Graph p • Nodes Represent p Computation p – Each Node is a Basic Block a Block o is a Sequence qu of o Instructions u o with – Basic • No Branches Out Of Middle of Basic Block • No Branches Into Middle of Basic Block • Basic Blocks should be maximal – Execution of basic block starts with first instruction – Includes all instructions in basic block • Edges Represent Control Flow Saman Amarasinghe 6 6.035 ©MIT Fall 1998 Control Flow Graph p into add(n, k) { s = 0; a = 4; i = 0; if (k == 0) b = 1; 1 else b = 2; while (i < n) { s = s + a*b;; i = i + 1; } return s; }Saman Amarasinghe s = 0; a = 4; i = 0; k == 0 b = 2; b = 1; i<n s = s + a*b; *b i = i + 1; 7 return s; 6.035 ©MIT Fall 1998 Basic Block Construction • Start with instruction control-flow graph g p • Visit all edges in graph • Merge adjacent nodes if – Only one edge from first node – Only one edge into second node s = 0; s = 0; a = 4; a = 4; Saman Amarasinghe 8 6.035 ©MIT Fall 1998 s = 0; s = 0; a = 4; a = 4; i = 0; k == 0 b = 2; b = 1; i<n s = s + a*b; return s; i = i + 1; Saman Amarasinghe 9 6.035 ©MIT Fall 2006 s = 0; s = 0; a = 4; i = 0; a = 4; i = 0; k == 0 b = 2; b = 1; i<n s = s + a*b; return s; i = i + 1; Saman Amarasinghe 10 6.035 ©MIT Fall 2006 s = 0; s = 0; a = 4; i = 0; k == 0 a = 4; i = 0; k == 0 b = 2; b = 1; i<n s = s + a*b; return s; i = i + 1; Saman Amarasinghe 11 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n s = s + a*b; return s; i = i + 1; Saman Amarasinghe 12 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; return s; i = i + 1; Saman Amarasinghe 13 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; s = s + a*b; return s; i = i + 1; Saman Amarasinghe 14 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; s = s + a*b; i = i + 1; return s; i = i + 1; Saman Amarasinghe 15 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; s = s + a*b; i = i + 1; return s; i = i + 1; Saman Amarasinghe 16 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; s = s + a*b; i = i + 1; return s; return s; i = i + 1; Saman Amarasinghe 17 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; b = 1; s = s + a*b; i = i + 1; return s; return s; i = i + 1; Saman Amarasinghe 18 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; b = 1; s = s + a*b; i = i + 1; return s; return s; i = i + 1; Saman Amarasinghe 19 6.035 ©MIT Fall 2006 s = 0; a = 4; i = 0; k == 0 s = 0; a = 4; i = 0; k == 0 b = 2; b = 2; b = 1; i<n i<n s = s + a*b; b = 1; s = s + a*b; i = i + 1; return s; return s; i = i + 1; Saman Amarasinghe 20 6.035 ©MIT Fall 2006 Program Points, Split and Join Points Points • One program point before and after each statement in program • Split point has multiple successors – conditional branch statements only split points • Merge point has multiple predecessors • Each basic block – Either starts with a merge point or its predecessor ends with a split point – Either ends with a split point or its successor starts t t with ith a merge point i t Saman Amarasinghe 21 6.035 ©MIT Fall 1998 Basic Block Optimizations p • Common SubSubExpression Elimination – a=(x+y)+z; ( y) b=x+y; y – t=x+y; a=t+z; b=t; • Constant Propagation P opagation – x=5; b=x+y; – x=5;; b=5+y; y; – a=x+y; b=a; c=b+z; – a=x+y; b=a; c=a+z; • Dead Code Elimination – a=x+y; b=a; b=a+z; – a=x+y; b=a+z • Strength Reduction • Algebraic Identities – t=i*4; t i*4 – t=i<<2; – a=x*1; – a=x; Saman Amarasinghe • Copy Propagation 22 6.035 ©MIT Fall 1998 Basic Block Analysis y Approach pp • Assume normalized basic block - all statements are of the form – var = var op var (where op is a binary operator) – var = op var (where op is a unary operator) – var = var • Simulate a symbolic execution of basic block – Reason about values of variables (or other aspects of computation) – Derive property of interest Saman Amarasinghe 23 6.035 ©MIT Fall 1998 Two Kinds of Variables • Temporaries p Introduced Byy Compiler p – Transfer values only within basic block odu d as a part pa of o instruction u o flattening a g – Introduced – Introduced by optimizations/transformations – Typically assigned to only once • Program Variables – Declared in original program – May be assigned to multiple times – May M transfer t f values l between b t basic b i blocks bl k Saman Amarasinghe 24 6.035 ©MIT Fall 1998 Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Value Numbering • Reason about values of variables and expressions in the program – Simulate execution of basic block – Assign virtual value to each variable and expression • Discovered property: which variables and expressions have the same value • Stand dard duse: – Common subexpression elimination – Typically combined with transformation that • Saves computed values in temporaries • Replaces expressions with temporaries when value off expressiion previiouslly computted d Saman Amarasinghe 26 6.035 ©MIT Fall 1998 New Basic Block Original Basic Block a = x+y t1 = a b = a+z t2 = b b = b+y t3 = b c = t2 a = x+y b=a a+zz b = b+y c = a+z Var to Val x v1 y v2 a v3 z v4 4 b v5 v6 c v5 Saman Amarasinghe Exp to Val v1+v2 v3 v3+v4 v5 v5+v2 v6 27 Exp to Tmp v1+v2 t1 v3+v4 t2 v5+v2 t6 6.035 ©MIT Fall 1998 Value Numbering g Summaryy • Forward symbolic execution of basic block • Each new value assigned to temporary – a=x+y; becomes a=x+y; t=a; – Temporary preserves value for use later in program even if original variable rewritten • a=x+y; a=a+z; b=x+y becomes • a=x+y; t=a; a=a+z; b=t; • Maps –V Var to t Vall – specifi ifies symb bolilic vallue for each hvar iable bl – Exp to Val – specifies value of each evaluated expression – Exp to Tmp – specifies tmp that holds value of each evaluated expression Saman Amarasinghe 28 6.035 ©MIT Fall 1998 Map p Usage g • Var to Val – Used to compute symbolic value of y and z when processing statement off fform x = y + z • Exp p to Tmp p – Used to determine which tmp to use if value(y) + value(z) previously computed when processing statement of form x = y + z • Exp to Val – Used d to update d Var to Vall when h • processing statement of the form x = y + z, and • value(y) + value(z) previously computed Saman Amarasinghe 29 6.035 ©MIT Fall 1998 Interesting g Properties p • Finds common subexpressions even if they use diff different t variables i bl in i expressions i – y=a+b; x=b; z=a+x becomes – y=a+b; y a+b; t=y; t y; x=b; x b; z=t z t – Why? Because computes with symbolic values • Finds common subexpressions even if variable that originally held the value was overwritten a+b; yy=1; 1; zz=a+b a+b becomes – yy=a+b; – y=a+b; t=y; y=1; z=t y Because saves values awayy in – Why? temporaries Saman Amarasinghe 30 6.035 ©MIT Fall 1998 One More Interesting g Property p y • Flattening and CSE combine to capture partial and arbitrarily complex common subexpressions w=(a+b)+c; – After flattening: t1=a+b; t1 a+b; w w=t1+c; t1+c; x=b; y=(a+x)+c; z=a+b; x=b; b; t2=a+x; t2 a+x; yy=t2+c; t2+c; zz=a+b; a+b; – CSE algorithm notices that • t1 1+c and dt 2+c compute same vallue • In the statement z = a+b, a+b has already been computed so generated code can reuse the result t1=a+b; w=t1+c; t3=w; x=b; t2=t1; y=t3; Saman Amarasinghe 31 6.035 z=t1; ©MIT Fall 1998 Problems I • Algorithm has a temporary for each new value – a=x+y; t1=a; • Introduces – lots of temporaries – lots of copy statements to temporaries • In many cases, temporaries and copy statements are unnecessary • So S we eliminate li i t them th with ith copy propagation ti and d dead code elimination Saman Amarasinghe 32 6.035 ©MIT Fall 1998 Problems II • Expressions have to be identical – a=x+y+z; b=y+z+x; c=x*2+y+2*z–(x+z) • We use canonicalization • We use algebraic simplification Saman Amarasinghe 33 6.035 ©MIT Fall 1998 Copy py Propagation p g • Once again, simulate execution of program • If can, use original variable instead of temporary – a=x+y; b=x+y; – After CSE becomes a=x+y; t=a; b=t; – After CP becomes a=x+y; t=a; b=a; – After Aft DCE b becomes a=x+y; b=a; b • Key idea: –d determine t i when h original i i l variable i bl is i NOT overwritten itt between its assignment statement and the use of the computed value – If not overwritten, use original variable Saman Amarasinghe 34 6.035 ©MIT Fall 1998 Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Copy py Propagation p g Maps p • Maintain two maps p – tmp to var: tells which variable to use instead of a given temporary variable – var to set: inverse of tmp to var. tells which temps are mapped to a given variable by tmp to var Saman Amarasinghe 36 6.035 ©MIT Fall 1998 Copy py Propagation p g Example p • Original • After CSE and Copy Propagation a = x+y x+y b = a+z c = x+y a=b a = x+y t1 = a b = a+z t2 = b c=a a=b a • After CSE a = x+y t1 = a b = a+z t2 = b c = t1 t1 a = b Saman Amarasinghe 37 6.035 ©MIT Fall 2006 Copy py Propagation p g Example p Basic Block Aft CSE After Basic Block After CSE and d Copy C Prop a = x+y t1 = a a = x+y t1 = a t1 tmp to var var to set t1 a a {t1} Saman Amarasinghe 38 6.035 ©MIT Fall 2006 Copy py Propagation p g Example p Basic Block Af After CSE Basic Block After CSE and d Copy C Prop a = x+y t1 = a b = a+z t2 = b a = x+y t1 = a t1 b = a+z t2 = b tmp to var var to set t1 a t2 b Saman Amarasinghe a {t1} b {t2} t2} 39 6.035 ©MIT Fall 2006 Copy py Propagation p g Example p Basic Block Aft CSE After Basic Block After CSE and d Copy C Prop a = x+y t1 = a b = a+z t2 = b c = t1 a = x+y t1 = a t1 b = a+z t2 = b tmp to var var to set t1 a t2 b Saman Amarasinghe a {t1} b {t2} t2} 40 6.035 ©MIT Fall 2006 Copy py Propagation p g Example p Basic Block Aft CSE After Basic Block After CSE and d Copy C Prop a = x+y t1 = a b = a+z t2 = b c = t1 a = x+y t1 = a t1 b = a+z t2 = b c=a tmp to var var to set t1 a t2 b Saman Amarasinghe a {t1} b {t2} t2} 41 6.035 ©MIT Fall 2006 Copy py Propagation p g Example p Basic Block Aft CSE After Basic Block After CSE and d Copy C Prop a = x+y t1 = a b = a+z t2 = b c = t1 a=b a = x+y t1 = a t1 b = a+z t2 = b c=a a=b tmp to var var to set t1 a t2 b Saman Amarasinghe a {t1} b {t2} t2} 42 6.035 ©MIT Fall 2006 Copy py Propagation p g Example p Basic Block Aft CSE After Basic Block After CSE and d Copy C Prop a = x+y t1 = a b = a+z t2 = b c = t1 a=b a = x+y t1 = a t1 b = a+z t2 = b c=a a=b tmp to var var to set t1 t1 t2 b Saman Amarasinghe a {} b {t2} t2} 43 6.035 ©MIT Fall 2006 Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Dead Code Elimination • Copy py propagation p p g keeps p all temps p around • May be temps that are never read • Dead Code Elimination removes them Basic Block After CSE and CP Basic Block After CSE CP and DCE CSE, a = x+y t1 = a b = a+z t2 = b c=a a=b Saman Amarasinghe a = x+y b = a+z c=a a=b 45 6.035 ©MIT Fall 1998 Dead Code Elimination • Basic Idea – Process Code In Reverse Execution Order a a a set of o variables a ab that a are a needed d d – Maintain later in computation g to a temporary p y – If encounter an assignment that is not needed, remove assignment Saman Amarasinghe 46 6.035 ©MIT Fall 1998 Basic Block After CSE and Copy Prop a = x+y t1 = a b = a+z t2 = b c=a a=b Needed Set { } {b} Saman Amarasinghe 47 6.035 ©MIT Fall 2006 Basic Block After CSE and Copy Prop a = x+y t1 = a b = a+z t2 = b c=a a=b Needed Set {{a,, b}} Saman Amarasinghe 48 6.035 ©MIT Fall 2006 Basic Block After CSE and Copy Prop a = x+y t1 = a b = a+z t2 = b c=a a=b Needed Set {{a,, b}} Saman Amarasinghe 49 6.035 ©MIT Fall 2006 Basic Block After CSE and Copy Prop a = x+y t1 = a b = a+z c=a a=b Needed Set {{a,, b}} Saman Amarasinghe 50 6.035 ©MIT Fall 2006 Basic Block After CSE and Copy Prop a = x+y t1 = a b = a+z c=a a=b Needed Set {{a,, b,, z}} Saman Amarasinghe 51 6.035 ©MIT Fall 2006 Basic Block After CSE and Copy Prop a = x+y t1 = a b = a+z c=a a=b Needed Set {{a,, b,, z}} Saman Amarasinghe 52 6.035 ©MIT Fall 2006 Basic Block After CSE and Copy Prop a = x+y b = a+z c=a a=b Needed Set {{a,, b,, z}} Saman Amarasinghe 53 6.035 ©MIT Fall 2006 Basic Block After , CSE Copy Propagation, and Dead Code Elimination a = x+y b = a+z c=a a=b Needed Set {{a,, b,, z}} Saman Amarasinghe 54 6.035 ©MIT Fall 2006 Basic Block After , CSE Copy Propagation, and Dead Code Elimination a = x+y b = a+z c=a a = b Needed Set {{a,, b,, z}} Saman Amarasinghe 55 6.035 ©MIT Fall 2006 Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Algebraic g Simplification p • Apply pp y our knowledge g from alg gebra,, number theory etc. to simplify expressions Saman Amarasinghe 57 6.035 ©MIT Fall 1998 Algebraic g Simplification p • Apply pp y our knowledge g from algebra, g , number theory etc. to simplify expressions • Example –a+0 –a*1 –a/1 –a*0 –0-a – a + (-b) – -(-a) ( a) Saman Amarasinghe a a a 0 -a a-b a 58 6.035 ©MIT Fall 1998 Algebraic g Simplification p • Apply pp y our knowledge g from alg gebra,, number theory etc. to simplify expressions • Example Example –a –a –a –a Saman Amarasinghe true false true false 59 a false true a 6.035 ©MIT Fall 1998 Algebraic g Simplification p • Apply pp y our knowledge g from alg gebra,, number theory etc. to simplify expressions • Example Example –a^2 –a*2 –a*8 Saman Amarasinghe a*a a+a a << 3 60 6.035 ©MIT Fall 1998 Opportunities for Algebraic Simplification Simplification • In the code – Programmers are lazy to simplify expressions – Programs are more readable with full expressions • After compiler expansion – Example: Array read A[8][12] will get expanded to – *(Abase + 4*(12 + 8*256)) which can be simplified • After other optimizations Saman Amarasinghe 61 6.035 ©MIT Fall 1998 Usefulness of Algebraic g Simplification p •R Reduces d the th number b off instructions i t ti • Uses less expensive instructions • Enable other optimizations Saman Amarasinghe 62 6.035 ©MIT Fall 1998 Implementation p • Not a data-flow optimization! p • Find candidates that matches the simplification rules and simplify the expression trees • Candidates may not be obvious Saman Amarasinghe 63 6.035 ©MIT Fall 1998 Implementation p • Not a data-flow optimization! p • Find candidates that matches the simplification rules and simplify the expression trees • Candidates may not be obvious – Example a+b-a + - a b Saman Amarasinghe 64 a 6.035 ©MIT Fall 1998 Use knowledge g about operators p • Commutative operators – a op b = b op a – • Associative operators – ((a op p b)) op p c = b op p (a op p c)) Saman Amarasinghe 65 6.035 ©MIT Fall 1998 Canonical Format • Put expression p trees into a canonical format – Sum of multiplicands p – Variables/terms in a canonical order – Example (a+3)*(a+8)*4 4*a*a+44*a+96 – Section 12.3.1 of whale book talks about this Saman Amarasinghe 66 6.035 ©MIT Fall 1998 Effects on the Numerical Stabilityy • Some alg gebraic simp plifications mayy produce p incorrect results Saman Amarasinghe 67 6.035 ©MIT Fall 1998 Effects on the Numerical Stabilityy • Some alg gebraic simp plifications mayy produce p incorrect results • Example – (a / b)*0 + c Saman Amarasinghe 68 6.035 ©MIT Fall 1998 Effects on the Numerical Stabilityy • Some alg gebraic simp plifications mayy produce p incorrect results • Example – (a / b)*0 + c – we can simplify this to c Saman Amarasinghe 69 6.035 ©MIT Fall 1998 Effects on the Numerical Stabilityy • Some alg gebraic simp plifications mayy produce p incorrect results • Example – (a / b)*0 + c – we can simplify this to c – But what about when b = 0 should be a exception, but we we’llll get a result! Saman Amarasinghe 70 6.035 ©MIT Fall 1998 Outline • Introduction • Basic Blocks • Common Subexpression Elimination • Copy C Propagation P ti • Dead ead Code Elimination at o • Algebraic Simplification • Summary Interesting g Properties p • Analysis and Transformation Algorithms S b li ll Simulate Symbolically Si l t Execution E ti off Program P – CSE and Copy Propagation go forward – Dead Code Elimination goes backwards • Transformations stacked – Group of basic transformations work together – Often, one transformation creates inefficient code that is cleaned up by following transformations – Transformations can be useful even if original code may not benefit from transformation Saman Amarasinghe 72 6.035 ©MIT Fall 1998 Other Basic Block Transformations • Constant Propagation p g • Strength Reduction – a<<2 = a a*4; 4; a+a+a = 3 3*a; a; • Do these in unified transformation framework not in earlier or later phases framework, Saman Amarasinghe 73 6.035 ©MIT Fall 1998 Summaryy • Basic block analyses and transformations • Symb bolilicalllly siimullate t executi tion offprogram – Forward (CSE, copy prop, constant prop) – Backward (Dead code elimination) • Stacked groups of analyses and transformations that work together – CSE introduces excess temp poraries and copy pystatements – Copy propagation often eliminates need to keep temporary variables around – Dead code elimination removes useless code • Similar in spirit to many analyses and transformations that operate across basic blocks Saman Amarasinghe 74 6.035 ©MIT Fall 1998 MIT OpenCourseWare http://ocw.mit.edu 6.035 Computer Language Engineering Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.