[DebugInfo] Add support for variadic DBG_INSTR_REFs in LiveDebugValues

[StephenTozer]

Summary

Following support from the previous patches in this stack being added for variadic DBG_INSTR_REFs to exist, this patch modifies LiveDebugValues to handle those instructions. Support already exists for DBG_VALUE_LISTs, which covers most of the work needed to handle these instructions; this patch only modifies the transferDebugInstrRef function to correctly track them.

[jmorse]

Looks good with some tiny comments -- as ever it'll want tests, which should be folded into this patch, could you add those please.

This is also reassuringly small, which is encouraging and suggest it composes well with the other variadic work.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1603–1610

I believe DenseMap does an initial allocation, and the common case for DBG_INSTR_REF is going to be single value -- could I recommend using a SmallDenseMap instead? It'll expand to be larger when needed.

1634–1645

Aliasing the type name (DbgOp DbgOp) is going to confuse someone at some point, just "Op" perhaps?

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

1195

This will want a docu-comment

[StephenTozer]

Addressed non-test review comments.

[StephenTozer]

Add some lit test coverage, fix a bug with memoization of DBG_PHIs and remove an out-of-date comment.

[jmorse]

Looks good, but with what feels like low test coverage: remind me, the plumbing required to track variadic locations in LiveDebugValues already landed, and we have tests to cover those new code paths, yes?

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

595–596

Definitely wants a comment as to the intention behind this, I'm struggling to work it out.

1606

Recommend const DbgOp & to avoid unnecessary copies cropping up

llvm/test/DebugInfo/MIR/InstrRef/variadic-instr-ref.mir

1–3 ↗

(On Diff #470530)

Super-nit -- I don't like the file name, ideally there would be some kind of indicator that it's touching LiveDebugValues in some way.

50 ↗

(On Diff #470530)

Sounds like a DbgEntityHistoryCalculator matter rather than one for LiveDebugValues, right?

154 ↗

(On Diff #470530)

Ideally we'd remove these redundant keys (all the false / zero ones) below

[StephenTozer]

Rebased onto latest master; addressed review comments. The section of code that turned variadic expressions into non-variadic expressions so that they could be recovered as entry values has been extracted into a separate function in DebugInfoMetadata, and another instance of that logic in AsmPrinter has been updated to use this function. If you think that change should be rolled into a separate patch then I'm happy to do so!

[StephenTozer]

In D133927#4007888, @jmorse wrote:

Looks good, but with what feels like low test coverage: remind me, the plumbing required to track variadic locations in LiveDebugValues already landed, and we have tests to cover those new code paths, yes?

Yes - after all the input debug value instructions are converted to the internal representation (DbgValue) in the instruction referencing live debug values, variadic DBG_INSTR_REFs follow the same code paths as DBG_VALUE_LISTs, which had test coverage added when they were introduced. Notably those patches added unit tests, and this patch has nothing to add on top of them. If you think test coverage could be expanded though then I should be able to generate some more cases, it might not be a bad idea to cast a wide net in case there are any rare or insidious errors.

llvm/test/DebugInfo/MIR/InstrRef/variadic-instr-ref.mir

50 ↗

(On Diff #470530)

Indeed - there is some clobbering that's handled in LiveDebugValues, and I thought this should be one such case, but after checking over it again it's firmly out of LiveDebugValues' wheelhouse.

[jmorse]

In D133927#4023568, @StephenTozer wrote:

Yes - after all the input debug value instructions are converted to the internal representation (DbgValue) in the instruction referencing live debug values, variadic DBG_INSTR_REFs follow the same code paths as DBG_VALUE_LISTs, which had test coverage added when they were introduced. Notably those patches added unit tests, and this patch has nothing to add on top of them. If you think test coverage could be expanded though then I should be able to generate some more cases, it might not be a bad idea to cast a wide net in case there are any rare or insidious errors.

SGTM

[StephenTozer]

Rebased onto latest main, slightly updated and added unit tests for convertToNonVariadicExpression.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

private:
   Optional<SpillLocationNo> isRestoreInstruction(const MachineInstr &MI,
                                           MachineFunction *MF, unsigned &Reg);
 
   /// Given a spill instruction, extract the spill slot information, ensure it's
   /// tracked, and return the spill number.
   Optional<SpillLocationNo>
   extractSpillBaseRegAndOffset(const MachineInstr &MI);
 
+  /// For an instruction reference given by \p InstNo and \p OpNo in instruction
+  /// \p MI returns the Value pointed to by that instruction reference if any
+  /// exists, otherwise returns None.
+  Optional<ValueIDNum> getValueForInstrRef(unsigned InstNo, unsigned OpNo,
+                                           MachineInstr &MI,
+                                           const ValueTable *MLiveOuts,
+                                           const ValueTable *MLiveIns);
+
   /// Observe a single instruction while stepping through a block.
   void process(MachineInstr &MI, const ValueTable *MLiveOuts,
                const ValueTable *MLiveIns);
 
   /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
   /// \returns true if MI was recognized and processed.
   bool transferDebugValue(const MachineInstr &MI);
 

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

public:
   bool recoverAsEntryValue(const DebugVariable &Var,
                            const DbgValueProperties &Prop,
                            const ValueIDNum &Num) {
     // Is this variable location a candidate to be an entry value. First,
     // should we be trying this at all?
     if (!ShouldEmitDebugEntryValues)
       return false;
 
+    const DIExpression *DIExpr = Prop.DIExpr;
+
     // We don't currently emit entry values for DBG_VALUE_LISTs.
-    if (Prop.IsVariadic)
+    if (Prop.IsVariadic) {
+      if (!DIExpr->isSingleLocationExpression())
         return false;
+      SmallVector<uint64_t> NonVariadicOps(make_range(
+        DIExpr->expr_op_begin().getNext().getBase(), DIExpr->elements_end()));
+      DIExpr = DIExpression::get(DIExpr->getContext(), NonVariadicOps);
+    }
 
     // Is the variable appropriate for entry values (i.e., is a parameter).
-    if (!isEntryValueVariable(Var, Prop.DIExpr))
+    if (!isEntryValueVariable(Var, DIExpr))
       return false;
 
     // Is the value assigned to this variable still the entry value?
     if (!isEntryValueValue(Num))
       return false;
 
     // Emit a variable location using an entry value expression.
     DIExpression *NewExpr =
-        DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue);
+        DIExpression::prepend(DIExpr, DIExpression::EntryValue);
     Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
     MachineOperand MO = MachineOperand::CreateReg(Reg, false);
 
     PendingDbgValues.push_back(
-        emitMOLoc(MO, Var, {NewExpr, Prop.Indirect, Prop.IsVariadic}));
+        emitMOLoc(MO, Var, {NewExpr, Prop.Indirect, false}));
     return true;
   }
 
   /// 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);
bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
 
   // If performing final tracking of transfers, report this variable definition
   // to the TransferTracker too.
   if (TTracker)
     TTracker->redefVar(MI);
   return true;
 }
 
-bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
-                                             const ValueTable *MLiveOuts,
-                                             const ValueTable *MLiveIns) {
-  if (!MI.isDebugRef())
-    return false;
-
-  // Only handle this instruction when we are building the variable value
-  // transfer function.
-  if (!VTracker && !TTracker)
-    return false;
-
-  unsigned InstNo = MI.getDebugOperand(0).getInstrRefInstrIndex();
-  unsigned OpNo = MI.getDebugOperand(0).getInstrRefOpIndex();
-
-  const DILocalVariable *Var = MI.getDebugVariable();
-  const DIExpression *Expr = MI.getDebugExpression();
-  const DILocation *DebugLoc = MI.getDebugLoc();
-  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
-  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
-         "Expected inlined-at fields to agree");
-
-  DebugVariable V(Var, Expr, InlinedAt);
-
-  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
-  if (Scope == nullptr)
-    return true; // Handled by doing nothing. This variable is never in scope.
-
-  const MachineFunction &MF = *MI.getParent()->getParent();
-
+Optional<ValueIDNum> InstrRefBasedLDV::getValueForInstrRef(
+    unsigned InstNo, unsigned OpNo, MachineInstr &MI,
+    const ValueTable *MLiveOuts, const ValueTable *MLiveIns) {
   // Various optimizations may have happened to the value during codegen,
   // recorded in the value substitution table. Apply any substitutions to
   // the instruction / operand number in this DBG_INSTR_REF, and collect
   // any subregister extractions performed during optimization.
+  const MachineFunction &MF = *MI.getParent()->getParent();
 
   // Create dummy substitution with Src set, for lookup.
   auto SoughtSub =
       MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
 
   SmallVector<unsigned, 4> SeenSubregs;
   auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
   while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
if (NewID && !MTracker->isSpill(L)) {
         }
       }
     } else {
       // If we can't handle subregisters, unset the new value.
       NewID = None;
     }
   }
 
-  // We, we have a value number or None. Tell the variable value tracker about
-  // it. The rest of this LiveDebugValues implementation acts exactly the same
-  // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
-  // aren't immediately available).
-  DbgValueProperties Properties(Expr, false, true);
+  return NewID;
+}
+
+bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
+                                             const ValueTable *MLiveOuts,
+                                             const ValueTable *MLiveIns) {
+  if (!MI.isDebugRef())
+    return false;
+
+  // Only handle this instruction when we are building the variable value
+  // transfer function.
+  if (!VTracker && !TTracker)
+    return false;
+
+  const DILocalVariable *Var = MI.getDebugVariable();
+  const DIExpression *Expr = MI.getDebugExpression();
+  const DILocation *DebugLoc = MI.getDebugLoc();
+  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
+  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
+         "Expected inlined-at fields to agree");
+
+  DebugVariable V(Var, Expr, InlinedAt);
+
+  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
+  if (Scope == nullptr)
+    return true; // Handled by doing nothing. This variable is never in scope.
+
   SmallVector<DbgOpID> DbgOpIDs;
-  if (NewID)
+  for (const MachineOperand &MO : MI.debug_operands()) {
+    if (!MO.isDbgInstrRef()) {
+      // TODO: A DBG_INSTR_REF could contain a frame index, which would be a
+      // register at this point.
+      assert(!MO.isReg() && "DBG_INSTR_REF should not contain registers");
+      DbgOpID ConstOpID = DbgOpStore.insert(DbgOp(MO));
+      DbgOpIDs.push_back(ConstOpID);
+      continue;
+    }
+
+    unsigned InstNo = MO.getInstrRefInstrIndex();
+    unsigned OpNo = MO.getInstrRefOpIndex();
+
+    // Default machine value number is <None> -- if no instruction defines
+    // the corresponding value, it must have been optimized out.
+    Optional<ValueIDNum> NewID =
+        getValueForInstrRef(InstNo, OpNo, MI, MLiveOuts, MLiveIns);
+    // We have a value number or None. If the latter, then kill the entire debug
+    // value.
+    if (NewID) {
       DbgOpIDs.push_back(DbgOpStore.insert(*NewID));
+    } else {
+      DbgOpIDs.clear();
+      break;
+    }
+  }
+
+  // We have a DbgOpID for every value or for none. Tell the variable value
+  // tracker about it. The rest of this LiveDebugValues implementation acts
+  // exactly the same for DBG_INSTR_REFs as DBG_VALUEs (just, the former can
+  // refer to values that aren't immediately available).
+  DbgValueProperties Properties(Expr, false, true);
   if (VTracker)
     VTracker->defVar(MI, Properties, DbgOpIDs);
 
   // If we're on the final pass through the function, decompose this INSTR_REF
   // into a plain DBG_VALUE.
   if (!TTracker)
     return true;
 
+  // Fetch the concrete DbgOps now, as we will need them later.
+  SmallVector<DbgOp> DbgOps;
+  for (DbgOpID OpID : DbgOpIDs) {
+    DbgOps.push_back(DbgOpStore.find(OpID));
+  }
+
   // Pick a location for the machine value number, if such a location exists.
   // (This information could be stored in TransferTracker to make it faster).
-  Optional<LocIdx> FoundLoc;
+  SmallDenseMap<ValueIDNum, LocIdx> FoundLocs;
+  // Initialized the preferred-location map with illegal locations, to be
+  // filled in later.
+  for (DbgOp Op : DbgOps) {
+    if (!Op.IsConst)
+      FoundLocs.insert({Op.ID, LocIdx::MakeIllegalLoc()});
+  }
+
   for (auto Location : MTracker->locations()) {
     LocIdx CurL = Location.Idx;
     ValueIDNum ID = MTracker->readMLoc(CurL);
-    if (NewID && ID == NewID) {
-      // If this is the first location with that value, pick it. Otherwise,
-      // consider whether it's a "longer term" location.
-      if (!FoundLoc) {
-        FoundLoc = CurL;
-        continue;
-      }
+    if (!FoundLocs.count(ID))
+      continue;
+    auto FoundLocIt = FoundLocs.find(ID);
+    if (FoundLocIt->second.isIllegal()) {
+      FoundLocIt->second = CurL;
 
-      if (MTracker->isSpill(CurL))
-        FoundLoc = CurL; // Spills are a longer term location.
-      else if (!MTracker->isSpill(*FoundLoc) &&
-               !MTracker->isSpill(CurL) &&
-               !isCalleeSaved(*FoundLoc) &&
-               isCalleeSaved(CurL))
-        FoundLoc = CurL; // Callee saved regs are longer term than normal.
-    }
+      FoundLocIt->second = CurL; // Spills are a longer term location.
+    else if (!MTracker->isSpill(FoundLocIt->second) &&
+             !MTracker->isSpill(CurL) && !isCalleeSaved(FoundLocIt->second) &&
+      FoundLocIt->second =
+          CurL; // Callee saved regs are longer term than normal.
   }
 
   SmallVector<ResolvedDbgOp> NewLocs;
-  if (FoundLoc)
-    NewLocs.push_back(*FoundLoc);
+  for (DbgOp DbgOp : DbgOps) {
+    if (DbgOp.IsConst) {
+      NewLocs.push_back(DbgOp.MO);
+      continue;
+    }
+    LocIdx FoundLoc = FoundLocs.find(DbgOp.ID)->second;
+    if (FoundLoc.isIllegal()) {
+      NewLocs.clear();
+      break;
+    }
+    NewLocs.push_back(FoundLoc);
+  }
   // Tell transfer tracker that the variable value has changed.
   TTracker->redefVar(MI, Properties, NewLocs);
 
-  // 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) {
-    SmallVector<DbgOp> UseBeforeDefLocs;
-    UseBeforeDefLocs.push_back(*NewID);
+  // If there were values with no location, but all such values are defined in
+  // later instructions in this block, this is a block-local use-before-def.
+  if (!DbgOps.empty() && NewLocs.empty()) {
+    bool IsValidUseBeforeDef = true;
+    uint64_t LastUseBeforeDef = 0;
+    for (auto ValueLoc : FoundLocs) {
+      ValueIDNum NewID = ValueLoc.first;
+      LocIdx FoundLoc = ValueLoc.second;
+      if (!FoundLoc.isIllegal())
+        continue;
+      // If we have an value with no location that is not defined in this block,
+      // then it has no location in this block, leaving this value undefined.
+      if (NewID.getBlock() != CurBB || NewID.getInst() <= CurInst) {
+        IsValidUseBeforeDef = false;
+        break;
+      }
+      LastUseBeforeDef = std::max(LastUseBeforeDef, NewID.getInst());
+    }
+    if (IsValidUseBeforeDef) {
       TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false, true},
-                              UseBeforeDefLocs, NewID->getInst());
+                                DbgOps, LastUseBeforeDef);
+    }
   }
 
   // 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(NewLocs, V, Properties);