Editing Data-flow analysis (section)

=== Backward analysis ===
The [[live variable analysis]] calculates for each program point the variables that may be 
potentially read afterwards before their next write update. The result is typically used by
[[dead code elimination]] to remove statements that assign to a variable whose value is not used afterwards.

The in-state of a block is the set of variables that are live at the start of it. It initially contains all variables live (contained) in the block, before the transfer function is applied and the actual contained values are computed. The transfer function of a statement is applied by killing the variables that are written within this block (remove them from the set of live variables). The out-state of a block is the set of variables that are live at the end of the block and is computed by the union of the block's successors' in-states.

Initial code:

{{col-begin|width=auto}}
{{col-break}}
 b1: a = 3; 
     b = 5;
     d = 4;
     x = 100;
     if a > b then
 b2:    c = a + b;
        d = 2;
 b3: endif
     c = 4;
     return b * d + c;
{{col-end}}

Backward analysis:

{{col-begin|width=auto}}
{{col-break}}
 // in: {}
 b1: a = 3; 
     b = 5;
     d = 4;
     x = 100; //x is never being used later thus not in the out set {a,b,d}
     if a > b then
 // out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}  
 
 // in: {a,b}
 b2: c = a + b;
     d = 2;
 // out: {b,d}
 
 // in: {b,d}
 b3: endif
     c = 4;
     return b * d + c;
 // out:{}
{{col-end}}

The in-state of b3 only contains ''b'' and ''d'', since ''c'' has been written. The out-state of b1 is the union of the in-states of b2 and b3. The definition of ''c'' in b2 can be removed, since ''c'' is not live immediately after the statement.

Solving the data-flow equations starts with initializing all in-states and out-states to the empty set. The work list is initialized by inserting the exit point (b3) in the work list (typical for backward flow). Its computed in-state differs from the previous one, so its predecessors b1 and b2 are inserted and the process continues. The progress is summarized in the table below.

{| class="wikitable"
|-
! processing
! out-state
! old in-state 
! new in-state
! work list
|-
| b3
| {}
| {}
| {b,d}
| (b1,b2)
|-
| b1
| {b,d}
| {}
| {}
| (b2)
|-
| b2
| {b,d}
| {}
| {a,b}
| (b1)
|-
| b1
| {a,b,d}
| {}
| {}
| ()
|}

Note that b1 was entered in the list before b2, which forced processing b1 twice (b1 was re-entered as predecessor of b2). Inserting b2 before b1 would have allowed earlier completion.

Initializing with the empty set is an optimistic initialization: all variables start out as dead. Note that the out-states cannot shrink from one iteration to the next, although the out-state can be smaller than the in-state. This can be seen from the fact that after the first iteration the out-state can only change by a change of the in-state. Since the in-state starts as the empty set, it can only grow in further iterations.