Module rustc_passes::liveness
source · Expand description
A classic liveness analysis based on dataflow over the AST. Computes, for each local variable in a function, whether that variable is live at a given point. Program execution points are identified by their IDs.
Basic idea
The basic model is that each local variable is assigned an index. We represent sets of local variables using a vector indexed by this index. The value in the vector is either 0, indicating the variable is dead, or the ID of an expression that uses the variable.
We conceptually walk over the AST in reverse execution order. If we find a use of a variable, we add it to the set of live variables. If we find an assignment to a variable, we remove it from the set of live variables. When we have to merge two flows, we take the union of those two flows – if the variable is live on both paths, we simply pick one ID. In the event of loops, we continue doing this until a fixed point is reached.
Checking initialization
At the function entry point, all variables must be dead. If this is not the case, we can report an error using the ID found in the set of live variables, which identifies a use of the variable which is not dominated by an assignment.
Checking moves
After each explicit move, the variable must be dead.
Computing last uses
Any use of the variable where the variable is dead afterwards is a last use.
Implementation details
The actual implementation contains two (nested) walks over the AST.
The outer walk has the job of building up the ir_maps instance for the
enclosing function. On the way down the tree, it identifies those AST
nodes and variable IDs that will be needed for the liveness analysis
and assigns them contiguous IDs. The liveness ID for an AST node is
called a live_node
(it’s a newtype’d u32
) and the ID for a variable
is called a variable
(another newtype’d u32
).
On the way back up the tree, as we are about to exit from a function
declaration we allocate a liveness
instance. Now that we know
precisely how many nodes and variables we need, we can allocate all
the various arrays that we will need to precisely the right size. We then
perform the actual propagation on the liveness
instance.
This propagation is encoded in the various propagate_through_*()
methods. It effectively does a reverse walk of the AST; whenever we
reach a loop node, we iterate until a fixed point is reached.
The RWU
struct
At each live node N
, we track three pieces of information for each
variable V
(these are encapsulated in the RWU
struct):
-
reader
: theLiveNode
ID of some node which will read the value thatV
holds on entry toN
. Formally: a nodeM
such that there exists a pathP
fromN
toM
whereP
does not writeV
. If thereader
isNone
, then the current value will never be read (the variable is dead, essentially). -
writer
: theLiveNode
ID of some node which will write the variableV
and which is reachable fromN
. Formally: a nodeM
such that there exists a pathP
fromN
toM
andM
writesV
. If thewriter
isNone
, then there is no writer ofV
that followsN
. -
used
: a boolean value indicating whetherV
is used. We distinguish a read from a use in that a use is some read that is not just used to generate a new value. For example,x += 1
is a read but not a use. This is used to generate better warnings.
Special nodes and variables
We generate various special nodes for various, well, special purposes.
These are described in the Liveness
struct.
Modules
Structs
Enums
- VarKind 🔒