Live-variable analysis: Difference between revisions

Revision as of 02:32, 3 May 2023

Latest revision as of 10:21, 9 June 2025

(One intermediate revision by one other user not shown)

Line 16:

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 dataflow equations used for a given basic block ''<math>s''</math> and exiting block ''f''<math>\mathit{final}</math> in live variable analysis are the following:

:<math>

Line 22:

:<math>

{\mbox{KILL}}[s] </math>: The set of variables that are assigned a value in s (in many books{{Clarify|date=May 2015}}that discuss compiler design, KILL (s) is also defined as the set of variables assigned a value in s ''before any use'', but this does not change the solution of the dataflow equation):

:<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}[s]} {\mbox{LIVE}}_{\mathrm{in}}[p]

</math>