InstrRefBasedImpl.cpp File Reference (original) (raw)

This is a separate implementation of LiveDebugValues, see LiveDebugValues.cpp and [VarLocBasedImpl.cpp](VarLocBasedImpl%5F8cpp.html "LiveDebugValues is an optimistic "available expressions" dataflow algorithm.") for more information.

This pass propagates variable locations between basic blocks, resolving control flow conflicts between them. The problem is SSA construction, where each debug instruction assigns the value that a variable has, and every instruction where the variable is in scope uses that variable. The resulting map of instruction-to-value is then translated into a register (or spill) location for each variable over each instruction.

The primary difference from normal SSA construction is that we cannot create PHI values that contain variable values. CodeGen has already completed, and we can't alter it just to make debug-info complete. Thus: we can identify function positions where we would like a PHI value for a variable, but must search the MachineFunction to see whether such a PHI is available. If no such PHI exists, the variable location must be dropped.

To achieve this, we perform two kinds of analysis. First, we identify every value defined by every instruction (ignoring those that only move another value), then re-compute an SSA-form representation of the MachineFunction, using value propagation to eliminate any un-necessary PHI values. This gives us a map of every value computed in the function, and its location within the register file / stack.

Secondly, for each variable we perform the same analysis, where each debug instruction is considered a def, and every instruction where the variable is in lexical scope as a use. Value propagation is used again to eliminate any un-necessary PHIs. This gives us a map of each variable to the value it should have in a block.

Once both are complete, we have two maps for each block:

Variables to the values they should have,
Values to the register / spill slot they are located in. After which we can marry-up variable values with a location, and emit DBG_VALUE instructions specifying those locations. Variable locations may be dropped in this process due to the desired variable value not being resident in any machine location, or because there is no PHI value in any location that accurately represents the desired value. The building of location lists for each block is left to DbgEntityHistoryCalculator.

This pass is kept efficient because the size of the first SSA problem is proportional to the working-set size of the function, which the compiler tries to keep small. (It's also proportional to the number of blocks). Additionally, we repeatedly perform the second SSA problem analysis with only the variables and blocks in a single lexical scope, exploiting their locality.

Terminology

A machine location is a register or spill slot, a value is something that's defined by an instruction or PHI node, while a variable value is the value assigned to a variable. A variable location is a machine location, that must contain the appropriate variable value. A value that is a PHI node is occasionally called an mphi.

The first SSA problem is the "machine value location" problem, because we're determining which machine locations contain which values. The "locations" are constant: what's unknown is what value they contain.

The second SSA problem (the one for variables) is the "variable value problem", because it's determining what values a variable has, rather than what location those values are placed in.

TODO: Overlapping fragments Entry values Add back DEBUG statements for debugging this Collect statistics

Definition in file InstrRefBasedImpl.cpp.