Machine-Independent Optimizations III CS308 Compiler Theory 1
Machine-Independent Optimizations Ⅲ CS308 Compiler Theory 1
Partial-Redundancy Elimination Minimize the number of expression evaluations Consider all possible execution sequences in a flow graph,and look at the number of times an expression such as x +y is evaluated. 。 By moving around the places where x +y is evaluated and keeping the result in a temporary variable when necessary,we often can reduce the number of evaluations of this expression along many of the execution paths. CS308 Compiler Theory 2
Partial-Redundancy Elimination • Minimize the number of expression evaluations • Consider all possible execution sequences in a flow graph, and look at the number of times an expression such as x + y is evaluated. • By moving around the places where x + y is evaluated and keeping the result in a temporary variable when necessary, we often can reduce the number of evaluations of this expression along many of the execution number of evaluations of this expression along many of the execution paths. CS308 Compiler Theory 2
The Sources of Redundancy B B2 a =b+c b=7 B3 B2 a =b+c d=b+c a =b+c e b+c d b+c B B t =btc B3 t =b+c B3 b=7 t b+c t btc a t t =b+c a =t d =t d t (a) (b) (c) Figure 9.30:Examples of(a)global common subexpression,(b)loop-invariant code motion,(c)partial-redundancy elimination. 3
The Sources of Redundancy CS308 Compiler Theory 3
Global Common Subexpressions An expression b+c is redundant at point p,if it is an available expression at that point. The expression b +c has been computed along all paths reaching p,and the variables b and c were not redefined after the last expression was evaluated. CS308 Compiler Theory 4
Global Common Subexpressions • An expression b + c is redundant at point p, if it is an available expressi hi on at t hat po int. • The expression b + c has been computed along all paths reaching p, and th i bl b d t d fi d ft th l t i the var i ables b an d c were no t re d efine d after the las t express ion was evaluated. CS308 Compiler Theory 4
Loop-Invariant Expressions The expression b +c is loop invariant assuming neither the variable b nor c is redefined within the loop. We can optimize the program by replacing all the re-executions in a loop by a single calculation outside the loop CS308 Compiler Theory 5
Loop-Invariant Expressions • The expression b + c is loop invariant assuming neither the variable b nor c i d fi d i hi h l is re d efine d w i thin t he loop. • We can optimize the program by replacing all the re-executions in a loop by a single calculation outside the loop. CS308 Compiler Theory 5