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)