Content deleted Content added
m Remove unnecessary |display-author= parameters from CS1 templates; using AWB |
No edit summary |
||
Line 3:
Stated simply: a variable is '''live''' if it holds a value that may be needed in the future.
<!-- Is this paragraph relevant? -->▼
It is a "backwards may" analysis. The analysis is done in a backwards order, and the dataflow [[confluence operator]] is [[set union]].▼
Recently {{As of|2006|lc=on}}, various program analyses such as live variable analysis have been solved using [[Datalog]]. The Datalog specifications for such analyses are generally an order of magnitude shorter than their imperative counterparts (e.g. [[iterative analysis]]), and are at least as efficient.<ref>{{cite book | author=Whaley | title=Using Datalog with Binary Decision Diagrams for Program Analysis | year=2004 | url=http://people.csail.mit.edu/mcarbin/papers/aplas05.pdf}}</ref>▼
== Example ==
{| class="floatright"
|<code>
Line 15 ⟶ 17:
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
only {<code>b</code>} since variable <code>c</code> is updated in L2. The value of variable <code>a</code> is never used. Note that <code>f</code> may be stateful, so the never-live assignment to <code>a</code> can be eliminated, but there is insufficient information to rule on the entirety of <code>L3</code>.
== Expression in terms of dataflow equations ==
▲
The dataflow equations used for a given basic block ''s'' and exiting block ''f'' in live variable analysis are the following:
Line 22 ⟶ 28:
:<math>
{\mbox{KILL}}[s] </math>: The set of variables that are assigned a value in s (in many books{{Clarify}}, KILL (s) is also defined as the set of variables assigned a value in s ''before any use'', but this doesn't change the solution of the dataflow equation):
Line 44 ⟶ 50:
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 ==
{|
|
Line 106 ⟶ 114:
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.
▲<!-- Is this paragraph relevant? -->
▲Recently {{As of|2006|lc=on}}, various program analyses such as live variable analysis have been solved using [[Datalog]]. The Datalog specifications for such analyses are generally an order of magnitude shorter than their imperative counterparts (e.g. [[iterative analysis]]), and are at least as efficient.<ref>{{cite book | author=Whaley | title=Using Datalog with Binary Decision Diagrams for Program Analysis | year=2004 | url=http://people.csail.mit.edu/mcarbin/papers/aplas05.pdf}}</ref>
==References==
| |||