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
Partially Redundant Expressions An example of a partially redundant expression is shown in Fig.9.30(c). The expression b+c in block B4 is redundant on the path Bl-B2-B4, but not on the path Bl-B3-B4. We can eliminate the redundancy on the former path by placing a computation of b+c in block B3 All the results of b+c are written into a temporary variable t,and the calculation in block B4 is replaced with t. Partial-redundancy elimination requires the placement of new expression computations. CS308 Compiler Theory 6
Partially Redundant Expressions • An example of a partially redundant expression is shown in Fig. 9.30(c). • The expression b + c in block B4 is redundant on the path Bl - B2 - B4 , but not on the path Bl - B3 - B4 . • We can eliminate the redundancy on the former path by placing a computation of b + c in block B3 . • All th lt f b + itt i t t i bl t d th All the results o f b + c are written i n to a temporary var i able t, an d the calculation in block B4 is replaced with t. • Partial-redundancy elimination requires the placement of new expression computations expression computations. CS308 Compiler Theory 6
Can All Redundancy Be Eliminated? Is it possible to eliminate all redundant computations along every path? -NO B B2 B3 B2 =b+c B3 a =b+c d =b+c t =b+c B6 B5 A critical edge of a flow graph is any edge d =t leading from a node with more than one successor to a node with more than one predecessor. CS308 Compiler Theory 7
Can All Redundancy Be Eliminated? • Is it possible to eliminate all redundant computations along every path? – NO A critical edge of a flow graph is any edge leading from a node with more than one CS308 Compiler Theory 7 successor to a node with more than one predecessor
Can All Redundancy Be Eliminated? a s b+c B2 a -b+c B3 t d b+c 86 B6 B s d■t d=b+c B6 B (a) (b) Figure 9.32:Code duplication to eliminate redundancies CS308 Compiler Theory 8
Can All Redundancy Be Eliminated? CS308 Compiler Theory 8
The Lazy-Code-Motion Problem It is desirable for programs optimized with a partial-redundancy- elimination algorithm to have the following properties: 1.All redundant computations of expressions that can be eliminated without code duplication are eliminated. 2.The optimized program does not perform any computation that is not in the original program execution. 3.Expressions are computed at the latest possible time We refer to the optimization of eliminating partial redundancy with the goal of delaying the computations as much as possible as lazy code motion. CS308 Compiler Theory
The Lazy-Code-Motion Problem • It is desirable for programs optimized with a partial-redundancyeli i i l i h li m inat ion a lgor i t hm to h h ave t he f ll i o ow ing propert ies: 1. All redundant computations of expressions that can be eliminated with t d ithou t co de d li ti li i t d duplication are eli m ina t e d. 2. The optimized program does not perform any computation that is not in the original program execution original program execution. 3. Expressions are computed at the latest possible time. • We refer to the optimization of eliminating partial redundancy with the goal of delaying the computations as much as possible as goal of delaying the computations as much as possible as lazy code lazy code motion. CS308 Compiler Theory 9
The Lazy-Code-Motion Problem ·Full Redundancy An expression e in block B is redundant if along all paths reaching B,e has been evaluated and the operands of e have not been redefined subsequently. Let sbe the set of blocks,each containing expression e,that renders e in B redundant. -The set of edges leaving the blocks in Smust necessarily form a cutset,which if removed,disconnects block B from the entry of the program. Moreover,no operands of e are redefined along the paths that lead from the blocks in S to B. CS308 Compiler Theory 10
The Lazy-Code-Motion Problem • Full Redundancy – An expression e in block B is redundant if along all paths reaching B, e has been evaluated and the operands of e have not been redefined subsequently. – Let S be the set of blocks each containing expression be the set of blocks, each containing expression e, that renders that renders e in B redundant. – The set of edges leaving the blocks in S must necessarily form a cutset, which if removed di bl k d, disconnects bloc k B f h fh rom t he entry o f t he program. – Moreover, no operands of e are redefined along the paths that lead from the blocks in S to B. CS308 Compiler Theory 10