[DebugInstrRef][9/9] Handle DBG_INSTR_REFs use-before-defs in LiveDebugValues

[jmorse]

Summary

The MachineSink pass has a lot of code to handle how variable locations move when an instruction sinks. I wrote in PR44117 how it becomes difficult to determine the correct behaviour in the general case. Dealing with this with instruction-referencing variable locations is simple: we just tolerate DBG_INSTR_REFs referring to values that haven't been computed yet. This patch adds support into InstrRefBasedLDV to record when a variable value appears in the middle of a block, and should have a DBG_VALUE added when it appears (a debug use before def).

While described simply, this relies heavily on the value-propagation algorithm in InstrRefBasedLDV. The implementation doesn't attempt to verify the location of a value unless something non-trivial occurs to merge variable values in vlocJoin. This means that a variable with a value that has no location can retain it across all control flow (including loops). It's only when another debug instruction specifies a different variable value that we have to check, and find there's no location.

This property means that if a machine value is defined in a block dominated by a DBG_INSTR_REF that refers to it, all the successor blocks can automatically find a location for that value (if it's not clobbered). Thus in a sense, InstrRefBasedLDV is already supporting and implementing use-before-defs. This patch allows us to specify a variable location in the block where it's defined.

When loading live-in variable locations, TransferTracker currently discards those where it can't find a location for the variable value. However, we can tell from the machine value number whether the value is defined in this block. If it is, add it to a set of use-before-def records. Then, once the relevant instruction has been processed, emit a DBG_VALUE immediately after it.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1002

A class with all public members is called a struct ;-)

1003

It's either:

/// Comment.
int field;

or int field; ///< Comment. I prefer the first variant.

[jmorse]

Rebase to account for some whitespace differences.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

public:
   /// Map from DebugVariable to it's current location and qualifying meta
   /// information. To be used in conjunction with ActiveMLocs to construct
   /// enough information for the DBG_VALUEs for a particular LocIdx.
   DenseMap<DebugVariable, LocAndProperties> ActiveVLocs;
 
   /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
   SmallVector<MachineInstr *, 4> PendingDbgValues;
 
+  /// Record of a use-before-def: created when a value that's live-in to the
+  /// current block isn't available in any machine location, but it will be
+  /// defined in this block.
+  class UseBeforeDef {
+  public:
+    ValueIDNum ID;                 /// Value of this variable, def'd in block.
+    DebugVariable Var;             /// Identity of this variable.
+    DbgValueProperties Properties; /// Additional variable properties.
+  };
+
+  /// Map from instruction index (within the block) to the set of UseBeforeDefs
+  /// that become defined at that instruction.
+  DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;
+
+  /// The set of variables that are in UseBeforeDefs and can become a location
+  /// once the relevant value is defined. An element being erased from this
+  /// collection prevents the use-before-def materializing.
+  DenseSet<DebugVariable> UseBeforeDefVariables;
+
   const TargetRegisterInfo &TRI;
   const BitVector &CalleeSavedRegs;
 
   TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
                   MachineFunction &MF, const TargetRegisterInfo &TRI,
                   const BitVector &CalleeSavedRegs)
       : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
         CalleeSavedRegs(CalleeSavedRegs) {}
 
   /// Load object with live-in variable values. \p mlocs contains the live-in
   /// values in each machine location, while \p vlocs the live-in variable
   /// values. This method picks variable locations for the live-in variables,
   /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
   /// object fields to track variable locations as we step through the block.
   /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
   void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs,
                   SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
                   unsigned NumLocs) {
     ActiveMLocs.clear();
     ActiveVLocs.clear();
     VarLocs.clear();
     VarLocs.reserve(NumLocs);
+    UseBeforeDefs.clear();
+    UseBeforeDefVariables.clear();
 
     auto isCalleeSaved = [&](LocIdx L) {
       unsigned Reg = MTracker->LocIdxToLocID[L];
       if (Reg >= MTracker->NumRegs)
         return false;
       for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
         if (CalleeSavedRegs.test(*RAI))
           return true;
void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs,
     for (auto Var : VLocs) {
       if (Var.second.Kind == DbgValue::Const) {
         PendingDbgValues.push_back(
             emitMOLoc(Var.second.MO, Var.first, Var.second.Properties));
         continue;
       }
 
       // If the value has no location, we can't make a variable location.
-      auto ValuesPreferredLoc = ValueToLoc.find(Var.second.ID);
-      if (ValuesPreferredLoc == ValueToLoc.end())
+      const ValueIDNum &Num = Var.second.ID;
+      auto ValuesPreferredLoc = ValueToLoc.find(Num);
+      if (ValuesPreferredLoc == ValueToLoc.end()) {
+        // If it's a def that occurs in this block, register it as a
+        // use-before-def to be resolved as we step through the block.
+        if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
+          addUseBeforeDef(Var.first, Var.second.Properties, Num);
         continue;
+      }
 
       LocIdx M = ValuesPreferredLoc->second;
       auto NewValue = LocAndProperties{M, Var.second.Properties};
       auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
       if (!Result.second)
         Result.first->second = NewValue;
       ActiveMLocs[M].insert(Var.first);
       PendingDbgValues.push_back(
           MTracker->emitLoc(M, Var.first, Var.second.Properties));
     }
     flushDbgValues(MBB.begin(), &MBB);
   }
 
+  /// Record that \p Var has value \p ID, a value that becomes available
+  /// later in the function.
+  void addUseBeforeDef(const DebugVariable &Var,
+                       const DbgValueProperties &Properties, ValueIDNum ID) {
+    UseBeforeDef UBD = {ID, Var, Properties};
+    UseBeforeDefs[ID.getInst()].push_back(UBD);
+    UseBeforeDefVariables.insert(Var);
+  }
+
+  /// After the instruction at index \p Inst and position \p pos has been
+  /// processed, check whether it defines a variable value in a use-before-def.
+  /// If so, and the variable value hasn't changed since the start of the
+  /// block, create a DBG_VALUE.
+  void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
+    auto MIt = UseBeforeDefs.find(Inst);
+    if (MIt == UseBeforeDefs.end())
+      return;
+
+    for (auto &Use : MIt->second) {
+      LocIdx L = Use.ID.getLoc();
+
+      // If something goes very wrong, we might end up labelling a COPY
+      // instruction or similar with an instruction number, where it doesn't
+      // actually define a new value, instead it moves a value. In case this
+      // happens, discard.
+      if (MTracker->LocIdxToIDNum[L] != Use.ID)
+        continue;
+
+      // If a different debug instruction defined the variable value / location
+      // since the start of the block, don't materialize this use-before-def.
+      if (!UseBeforeDefVariables.count(Use.Var))
+        continue;
+
+      PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties));
+    }
+    flushDbgValues(pos, nullptr);
+  }
+
   /// Helper to move created DBG_VALUEs into Transfers collection.
   void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
     if (PendingDbgValues.size() > 0) {
       Transfers.push_back({Pos, MBB, PendingDbgValues});
       PendingDbgValues.clear();
     }
   }
 
   /// Change a variable value after encountering a DBG_VALUE inside a block.
   void redefVar(const MachineInstr &MI) {
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
     DbgValueProperties Properties(MI);
 
     const MachineOperand &MO = MI.getOperand(0);
 
     // Ignore non-register locations, we don't transfer those.
     if (!MO.isReg() || MO.getReg() == 0) {
       auto It = ActiveVLocs.find(Var);
       if (It != ActiveVLocs.end()) {
         ActiveMLocs[It->second.Loc].erase(Var);
         ActiveVLocs.erase(It);
      }
+      // Any use-before-defs no longer apply.
+      UseBeforeDefVariables.erase(Var);
       return;
     }
 
     Register Reg = MO.getReg();
     LocIdx NewLoc = MTracker->getRegMLoc(Reg);
     redefVar(MI, Properties, NewLoc);
   }
 
   /// Handle a change in variable location within a block. Terminate the
   /// variables current location, and record the value it now refers to, so
   /// that we can detect location transfers later on.
   void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
                 Optional<LocIdx> OptNewLoc) {
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
+    // Any use-before-defs no longer apply.
+    UseBeforeDefVariables.erase(Var);
 
     // Erase any previous location,
     auto It = ActiveVLocs.find(Var);
     if (It != ActiveVLocs.end())
       ActiveMLocs[It->second.Loc].erase(Var);
 
     // If there _is_ no new location, all we had to do was erase.
     if (!OptNewLoc)
if (NewID && ID == NewID) {
                isCalleeSaved(CurL))
         FoundLoc = CurL; // Callee saved regs are longer term than normal.
     }
   }
 
   // Tell transfer tracker that the variable value has changed.
   TTracker->redefVar(MI, Properties, FoundLoc);
 
+  // If there was a value with no location; but the value is defined in a
+  // later instruction in this block, this is a block-local use-before-def.
+  if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
+      NewID->getInst() > CurInst)
+    TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID);
+
   // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
   // This DBG_VALUE is potentially a $noreg / undefined location, if
   // FoundLoc is None.
   // (XXX -- could morph the DBG_INSTR_REF in the future).
   MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
   TTracker->PendingDbgValues.push_back(DbgMI);
   TTracker->flushDbgValues(MI.getIterator(), nullptr);
 
for (MachineBasicBlock &MBB : MF) {
     MTracker->loadFromArray(MInLocs[bbnum], bbnum);
     TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
                          NumLocs);
 
     CurBB = bbnum;
     CurInst = 1;
     for (auto &MI : MBB) {
       process(MI);
+      TTracker->checkInstForNewValues(CurInst, MI.getIterator());
       ++CurInst;
     }
   }
 
   // We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer
   // in DWARF in different orders. Use the order that they appear when walking
   // through each block / each instruction, stored in AllVarsNumbering.
   auto OrderDbgValues = [&](const MachineInstr *A,

llvm/test/DebugInfo/MIR/InstrRef/livedebugvalues_instrref_tolocs.mir

bb.1:
     JMP_1 %bb.2
 
     ; CHECK-LABEL: bb.2:
   bb.2:
     ; Just like any other variable location, live-ins should be created for
     ; any successor blocks.
     ; CHECK: DBG_VALUE $rbx, $noreg
 
+    DBG_INSTR_REF 5, 0, !16, !DIExpression(), debug-location !17
+    ; This is a debug use-before-def: the value appears a few instructions
+    ; later. Any earlier value should be terminated here, _and_ we should
+    ; emit a DBG_VALUE when the value becomes available.
+    ; CHECK: DBG_VALUE $noreg, $noreg
+
+    $rax = MOV64ri 1, debug-location !17
+    $rax = MOV64ri 1, debug-location !17
+    $rcx = MOV64ri 1, debug-instr-number 5, debug-location !17
+    ; CHECK: DBG_VALUE $rcx, $noreg
+    $rax = MOV64ri 1, debug-location !17
+
+    DBG_INSTR_REF 6, 0, !16, !DIExpression(), debug-location !17
+    ; Another debug use-before-def, but across block boundaries.
+    ; CHECK: DBG_VALUE $noreg, $noreg
+    JMP_1 %bb.3
+
+    ; CHECK-LABEL: bb.3:
+  bb.3:
+    $rax = MOV64ri 1, debug-location !17
+    $rdx = MOV64ri 1, debug-instr-number 6, debug-location !17
+    ; CHECK: DBG_VALUE $rdx, $noreg
+
+    ; Terminate variable location for next few blocks,
+    DBG_VALUE $noreg, $noreg, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $noreg, $noreg
+    JMP_1 %bb.4
+
+  bb.4:
+    ; The next three blocks form a debug use-before-def modelling a scenario
+    ; where an instruction is sunk (debug inst in bb5, value in bb6). However,
+    ; because a different path joins bb.6, we should _not_ add any DBG_VALUE.
+    ; A different variable value may enter the block via the other path.
+    $rdx = MOV64ri 1, implicit-def $eflags, debug-location !17
+    JCC_1 %bb.6, 4, implicit $eflags, debug-location !17
+  bb.5:
+    DBG_INSTR_REF 7, 0, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $noreg, $noreg
+    JMP_1 %bb.6, debug-location !17
+  bb.6:
+    $rsi = MOV64ri 1, debug-instr-number 7, debug-location !17
+    JMP_1 %bb.7, debug-location !17
+
+  ; A use-before-def shouldn't pass another definition of the variable location
+  ; or value.
+  bb.7:
+    DBG_INSTR_REF 8, 0, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $noreg, $noreg
+    DBG_VALUE $rax, $noreg, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $rax, $noreg,
+    $rdi = MOV64ri 1, debug-instr-number 8, debug-location !17
+
+  ; Loops: use-before-defs should be live-through loops, assuming that nothing
+  ; in that loop modifies the variable location.
+  bb.8:
+    DBG_INSTR_REF 9, 0, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $noreg, $noreg
+    JCC_1 %bb.8, 4, implicit $eflags
+  bb.9:
+    $rax = MOV64ri 11, debug-instr-number 9, debug-location !17
+    ; CHECK: DBG_VALUE $rax, $noreg,
+
+  ; Likewise, use-before-defs where anything changes the variable location
+  ; or value in the loop, should be discarded.
+  bb.10:
+    ; live-in,
+    ; CHECK: DBG_VALUE $rax, $noreg,
+    DBG_INSTR_REF 10, 0, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $noreg, $noreg
+
+  bb.11:
+    $rbx = MOV64ri 1, debug-location !17
+
+  bb.12:
+    DBG_INSTR_REF 9, 0, !16, !DIExpression(), debug-location !17
+    ; This still has a value in $rax,
+    ; CHECK: DBG_VALUE $rax, $noreg
+    JCC_1 %bb.11, 4, implicit $eflags
+
+  bb.13:
+    ; Live in,
+    ; CHECK: DBG_VALUE $rax, $noreg
+    $rbx = MOV64ri 11, debug-instr-number 10, debug-location !17
+    ; This is instruction 10 referred to in bb.10. However, as the variable
+    ; location/value has been modified in the meantime, no DBG_VALUE should be
+    ; generated here.
     RETQ $eax, debug-location !17
 ...