Data Flow Analysis Applications II

Definition:

  • Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so, v is live at p; otherwise, v is dead at p.

One application:

  • Information of live variables can be used for register allocations.

Understanding Live Variables Analysis

graph TD;
	1[v = 3]
	2[B. ?]
	3[p1. ... = v]
	4[p2. ... ...]
	1-->2
	2-->3
	2-->4

Considering Back Analysis:

  1. May analysis

$$ OUT[B] = \cup \space IN[p] $$

  1. OUT[B] = {v}, how we can get IN[B]

  • Tip: determine whether the variable v in some register R is live, or should we delete the value 3 of v in R, at the point of IN[B]?

    • Yes: IN[B] = {v}
    • No: IN[B] = {}
    1. ​ B.? : k=n –> IN[B]={v}
    2. ​ B.? : k=v –> IN[B]={v}
    3. ​ B.? : v=2 –> IN[B]={}
    4. ​ B.? : v=v+1 –> IN[B]={v}

  • Thus $$ IN[B] = use_B \cup (OUT[B]-def_B) $$ Method:

    • IN[exit] = empty set
    • for each basic block B\exit
      • IN[B] = empty set
    • while changes to any IN occur
      • for each basic block B\exit
        • update OUT[B] and IN[B]
      • End for
    • End while

May analysis: initialize to empty ; Must analysis: initialize to full