Content deleted Content added
→References: others have this cat, too |
improve typesetting of constants and variables |
||
(33 intermediate revisions by 26 users not shown) | |||
Line 1:
In [[
== Example ==
Consider the following program:
The set of live variables
Note that the assignment to <code>a</code> may be eliminated as <code>a</code> is not used later, but there is insufficient information to justify removing all of line 3 as <code>f</code> may have [[Side effect (computer science)|side effects]] (printing <code>b * c</code>, perhaps).
▲ L1: b := 3;
▲ L2: c := 5;
== Expression in terms of dataflow equations ==
▲ L3: a := f(b + c);
Liveness analysis is a "backwards may" analysis. The analysis is done in a [[Data-flow_analysis#Backward_Analysis|backwards]] order, and the dataflow [[confluence operator]] is [[set union]]. In other words, if applying liveness analysis to a function with a particular number of logical branches within it, the analysis is performed starting from the end of the function working towards the beginning (hence "backwards"), and a variable is considered live if any of the branches moving forward within the function might potentially (hence "may") need the variable's current value. This is in contrast to a "backwards must" analysis which would instead enforce this condition on all branches moving forward.
▲The set of live variables at line L3 is {<code>b</code>, <code>c</code>} because both are used in the addition, and thereby the call to <code>f</code> and assignment to <code>a</code>. But the set of live variables at line L1 is
The dataflow equations used for a given basic block
:<math>
{\mbox{GEN}}[s] </math>: The set of variables that are used in s before any assignment in the same basic block.
:<math>
{\mbox{KILL}}[s] </math>: The set of variables that are assigned a value in s (in many books that discuss compiler design, KILL (s) is also defined as the set of variables assigned a value in s ''before any use'', but this
:<math>
{\mbox{LIVE}}_{\mathrm{in}}[s] = {\mbox{GEN}}[s] \cup ({\mbox{LIVE}}_{\mathrm{out}}[s] - {\mbox{KILL}}[s])
</math>
:<math>
{\mbox{LIVE}}_{\mathrm{out}}[\mathit{final}] = {\emptyset}
</math>
:<math>
{\mbox{LIVE}}_{\mathrm{out}}[s] = \bigcup_{p \in \mathrm{succ}[
</math>
Line 44:
The in-state of a block is the set of variables that are live at the start of the block. Its out-state is the set of variables that are live at the end of it. The out-state is the union of the in-states of the block's successors. The transfer function of a statement is applied by making the variables that are written dead, then making the variables that are read live.
== Second example ==
{|
|
// in: {}; predecessor blocks: none
b1: a = 3;
b = 5;
Line 54 ⟶ 55:
// out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}
// in: {a,b}; predecessor blocks: b1
b2: c = a + b;
d = 2;
// out: {b,d}
// in: {b,d}; predecessor blocks: b1 and b2
b3: endif
c = 4;
Line 106 ⟶ 107:
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.
==References==
{{reflist|30em}}
{{cite book|last1=Aho|first1=Alfred|last2=Lam|first2=Monica|last3=Sethi|first3=Ravi|last4=Ullman|first4=Jeffrey|year=2007|edition=2|title=Compilers: Principles, Techniques, and Tools|page=608}}
{{Compiler optimizations}}
[[Category:Compiler optimizations]]
[[Category:Data-flow analysis]]
[[Category:Static program analysis]]
|