2015-04-14 Lazy Code Motion (Ch. 9.5) sources of redundancy (Fig. 9.30) - common subexpressions - loop-invariant expressions ("code hoisting") - partially-redundant expressions some redundancy can only be eliminated via flow graph modification - Fig. 9.31 and Fig. 9.32 lazy code motion (LCM): eliminate partial redunancy and delay computation as long as possible key idea: eliminate partial redundancy by creating extra copies so that the expression is fully redundant tradeoff: calculate early and reduce more redundancy calculate late and minimize register lifetimes cutset - edges that (if removed) would disconnect a block from the entry point anticipated expressions: calculated along all paths from the given point using values available at that point - limits how early an expression can be inserted available expressions: anticipated along all paths reaching the given point postponable expression: early placement is encountered along every path to the given point and there is no use of the expression after the last placement used expressions: expression is on RHS on some path after the given point before it is re-assigned LCM 1) use anticipation to determine where expressions can be placed - calculate anticipated expressions via backward data flow analysis - "are expressions used on all paths after each point?" 2) find earliest cutset subject to constraints - calculate available expressions via forward data flow analysis - find program points where expressions are anticipated but not available - "are expressions anticipated on all paths before each point?" - example: Ex. 9.31 and Fig. 9.35 3) push cutsets as far forward as possible - calculate postponable expressions via forward data flow analysis - find program points where expressions can no longer be postponed - "are expressions NOT USED on all paths before each point?" - example of importance: Ex. 9.33 and Fig. 9.36 4) remove assignments to temporary variables that are only used once - calculate used expressions via backward data flow analysis - "are temporary assignments used on any path after each point?" - (similar to liveness analysis for variables) details in Fig. 9.34 and Alg. 9.36 REVIEW OF VALUE-NUMBER METHOD (Ch. 6.1.2)