LLVM  13.0.0git
InstrRefBasedImpl.cpp File Reference
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/UniqueVector.h"
#include "llvm/CodeGen/LexicalScopes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/TypeSize.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
#include <limits.h>
#include <limits>
#include "LiveDebugValues.h"
Include dependency graph for InstrRefBasedImpl.cpp:

Go to the source code of this file.

## Macros

#define DEBUG_TYPE   "livedebugvalues"

#define NUM_LOC_BITS   24

## Variables

static cl::opt< bool > EmulateOldLDV ("emulate-old-livedebugvalues", cl::Hidden, cl::desc("Act like old LiveDebugValues did"), cl::init(false))

static cl::opt< bool > ObserveAllStackops ("observe-all-stack-ops", cl::Hidden, cl::desc("Allow non-kill spill and restores"), cl::init(false))

## Detailed Description

This is a separate implementation of LiveDebugValues, see LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information.

This pass propagates variable locations between basic blocks, resolving control flow conflicts between them. The problem is much like SSA construction, where each DBG_VALUE 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.

This pass determines which DBG_VALUE dominates which instructions, or if none do, where values must be merged (like PHI nodes). The added complication is that because codegen has already finished, a PHI node may be needed for a variable location to be correct, but no register or spill slot merges the necessary values. In these circumstances, the variable location is dropped.

What makes this analysis non-trivial is loops: we cannot tell in advance whether a variable location is live throughout a loop, or whether its location is clobbered (or redefined by another DBG_VALUE), without exploring all the way through.

To make this simpler we perform two kinds of analysis. First, we identify every value defined by every instruction (ignoring those that only move another value), then compute a map of which values are available for each instruction. This is stronger than a reaching-def analysis, as we create PHI values where other values merge.

Secondly, for each variable, we effectively re-construct SSA using each DBG_VALUE as a def. The DBG_VALUEs read a value-number computed by the first analysis from the location they refer to. We can then compute the dominance frontiers of where a variable has a value, and create PHI nodes where they merge. This isn't precisely SSA-construction though, because the function shape is pre-defined. If a variable location requires a PHI node, but no PHI for the relevant values is present in the function (as computed by the first analysis), the location must be dropped.

Once both are complete, we can pass back over all instructions knowing:

• What value each variable should contain, either defined by an instruction or where control flow merges
• What the location of that value is (if any). Allowing us to create appropriate live-in DBG_VALUEs, and DBG_VALUEs when a value moves location. After this pass runs, all variable locations within a block should be specified by DBG_VALUEs within that block, allowing DbgEntityHistoryCalculator to focus on individual blocks.

This pass is able to go fast because the size of the first reaching-definition analysis 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 reaching-definition analysis with only the variables and blocks in a single lexical scope, exploiting their locality.

Determining where PHIs happen is trickier with this approach, and it comes to a head in the major problem for LiveDebugValues: is a value live-through a loop, or not? Your garden-variety dataflow analysis aims to build a set of facts about a function, however this analysis needs to generate new value numbers at joins.

To do this, consider a lattice of all definition values, from instructions and from PHIs. Each PHI is characterised by the RPO number of the block it occurs in. Each value pair A, B can be ordered by RPO(A) < RPO(B): with non-PHI values at the top, and any PHI value in the last block (by RPO order) at the bottom.

(Awkwardly: lower-down-the lattice means a greater RPO number. Below, "rank" always refers to the former).

At any join, for each register, we consider:

• All incoming values, and
• The PREVIOUS live-in value at this join. If all incoming values agree: that's the live-in value. If they do not, the incoming values are ranked according to the partial order, and the NEXT LOWEST rank after the PREVIOUS live-in value is picked (multiple values of the same rank are ignored as conflicting). If there are no candidate values, or if the rank of the live-in would be lower than the rank of the current blocks PHIs, create a new PHI value.

Intuitively: if it's not immediately obvious what value a join should result in, we iteratively descend from instruction-definitions down through PHI values, getting closer to the current block each time. If the current block is a loop head, this ordering is effectively searching outer levels of loops, to find a value that's live-through the current loop.

If there is no value that's live-through this loop, a PHI is created for this location instead. We can't use a lower-ranked PHI because by definition it doesn't dominate the current block. We can't create a PHI value any earlier, because we risk creating a PHI value at a location where values do not in fact merge, thus misrepresenting the truth, and not making the true live-through value for variable locations.

This algorithm applies to both calculating the availability of values in the first analysis, and the location of variables in the second. However for the second we add an extra dimension of pain: creating a variable location PHI is only valid if, for each incoming edge,

• There is a value for the variable on the incoming edge, and
• All the edges have that value in the same register. Or put another way: we can only create a variable-location PHI if there is a matching machine-location PHI, each input to which is the variables value in the predecessor block.

To accommodate this difference, each point on the lattice is split in two: a "proposed" PHI and "definite" PHI. Any PHI that can immediately have a location determined are "definite" PHIs, and no further work is needed. Otherwise, a location that all non-backedge predecessors agree on is picked and propagated as a "proposed" PHI value. If that PHI value is truly live-through, it'll appear on the loop backedges on the next dataflow iteration, after which the block live-in moves to be a "definite" PHI. If it's not truly live-through, the variable value will be downgraded further as we explore the lattice, or remains "proposed" and is considered invalid once dataflow completes.

### 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 dataflow 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 dataflow 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. Unfortunately, it's not that simple, because producing a PHI value always involves picking a location. This is an imperfection that we just have to accept, at least for now.

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

Definition in file InstrRefBasedImpl.cpp.

## ◆ DEBUG_TYPE

 #define DEBUG_TYPE   "livedebugvalues"

Definition at line 202 of file InstrRefBasedImpl.cpp.

## ◆ NUM_LOC_BITS

 #define NUM_LOC_BITS   24

Definition at line 243 of file InstrRefBasedImpl.cpp.

## ◆ EmulateOldLDV

 cl::opt EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden, cl::desc("Act like old LiveDebugValues did"), cl::init(false))
static

## ◆ ObserveAllStackops

 cl::opt ObserveAllStackops("observe-all-stack-ops", cl::Hidden, cl::desc("Allow non-kill spill and restores"), cl::init(false))
static