[DebugInfo] Unify location selection logic for values in InstrRefBasedImpl

[StephenTozer]

Summary

Currently the instruction referencing live debug values has 3 separate places where we iterate over all known locations to find the best machine location for a set of values at a given point in the program. Each of these places has an implementation of this check, and one of them has slightly different logic to the others (TransferTracker::loadInLocs prefers registers to spill slots). This patch moves the check for the "quality" of a machine location into a separate function, which also avoids repeatedly calling some slightly-expensive functions, giving a slight performance improvement in optimized debug builds [0].

[0] http://llvm-compile-time-tracker.com/compare.php?from=2ec98ffbf12163ee4ff9f4e674eba714bce24ec1&to=e5163ffef719cd55f7c9641988bbb64effd23b75&stat=instructions%3Au

[StephenTozer]

llvm/test/DebugInfo/MIR/X86/live-debug-values-restore.mir

382

Note that this test change is caused by the fact that previously, due to loadInLocs preferring registers to spill slots, both of the expected register DBG_VALUEs would be emitted at the start of the block. Since loadInLocs prefers spill slots as-of this patch, the fragment (0, 32) now starts as a spill slot and gets transferred to a register after the kill near the start of the block. This does not affect the substance of the test, as the important part is checking that the register debug values have the correct fragment information, which they still do.

[jmorse]

Slightly twitchy about there being a zero LocIdx -- I think I tried to suppress there being any default-constructed LocIdxes out there. On the other hand, it comes with a sentinel value attached, so it's no big deal.

LGTM.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1617–1618

Feels like an "isBest" method on the LocationAndQuality class might be the best way of performing the check below?

[StephenTozer]

In D140412#4008377, @jmorse wrote:

Slightly twitchy about there being a zero LocIdx -- I think I tried to suppress there being any default-constructed LocIdxes out there. On the other hand, it comes with a sentinel value attached, so it's no big deal.

In this case the reasoning was that LocIdx is 32 bits that only uses 24 for the location, so the sentinel value can be UINT_MAX; since LocationAndQuality uses just 24 bits for the location, I figured there wasn't any good value that could be assigned to the location bits, while the quality bits already tell us whether the location bits mean anything or not.

[StephenTozer]

Updated for review comments, None -> std::nullopt.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
                   const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
       : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
         CalleeSavedRegs(CalleeSavedRegs) {
     TLI = MF.getSubtarget().getTargetLowering();
     auto &TM = TPC.getTM<TargetMachine>();
     ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
   }
 
-  bool isCalleeSaved(LocIdx L) {
+  bool isCalleeSaved(LocIdx L) const {
     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;
     return false;
   };
 
+  // An estimate of the expected lifespan of values at a machine location, with
+  // a greater value corresponding to a longer expected lifespan, i.e. spill
+  // slots generally live longer than callee-saved registers which generally
+  // live longer than non-callee-saved registers. The minimum value of 0
+  // corresponds to an illegal location that cannot have a "lifespan" at all.
+  enum class LocationQuality : unsigned char {
+    Illegal = 0,
+    Register,
+    CalleeSavedRegister,
+    SpillSlot,
+    Best = SpillSlot
+  };
+
+  class LocationAndQuality {
+    unsigned Location : 24;
+    unsigned Quality : 8;
+
+  public:
+    LocationAndQuality() : Location(0), Quality(0) {}
+    LocationAndQuality(LocIdx L, LocationQuality Q)
+        : Location(L.asU64()), Quality(static_cast<unsigned>(Q)) {}
+    LocIdx getLoc() const {
+      if (!Quality)
+        return LocIdx::MakeIllegalLoc();
+      return LocIdx(Location);
+    }
+    LocationQuality getQuality() const { return LocationQuality(Quality); }
+    bool isIllegal() const { return !Quality; }
+    bool isBest() const { return getQuality() == LocationQuality::Best; }
+  };
+
+  // Returns the LocationQuality for the location L iff the quality of L is
+  // is strictly greater than the provided minimum quality.
+  std::optional<LocationQuality>
+  getLocQualityIfBetter(LocIdx L, LocationQuality Min) const {
+    if (L.isIllegal())
+      return std::nullopt;
+    if (Min >= LocationQuality::SpillSlot)
+      return std::nullopt;
+    if (MTracker->isSpill(L))
+      return LocationQuality::SpillSlot;
+    if (Min >= LocationQuality::CalleeSavedRegister)
+      return std::nullopt;
+    if (isCalleeSaved(L))
+      return LocationQuality::CalleeSavedRegister;
+    if (Min >= LocationQuality::Register)
+      return std::nullopt;
+    return LocationQuality::Register;
+  }
+
   /// For a variable \p Var with the live-in value \p Value, attempts to resolve
   /// the DbgValue to a concrete DBG_VALUE, emitting that value and loading the
   /// tracking information to track Var throughout the block.
   /// \p ValueToLoc is a map containing the best known location for every
   ///    ValueIDNum that Value may use.
   /// \p MBB is the basic block that we are loading the live-in value for.
   /// \p DbgOpStore is the map containing the DbgOpID->DbgOp mapping needed to
   ///    determine the values used by Value.
   void loadVarInloc(MachineBasicBlock &MBB, DbgOpIDMap &DbgOpStore,
-                    const DenseMap<ValueIDNum, LocIdx> &ValueToLoc,
+                    const DenseMap<ValueIDNum, LocationAndQuality> &ValueToLoc,
                     DebugVariable Var, DbgValue Value) {
     SmallVector<DbgOp> DbgOps;
     SmallVector<ResolvedDbgOp> ResolvedDbgOps;
     bool IsValueValid = true;
     unsigned LastUseBeforeDef = 0;
 
     // If every value used by the incoming DbgValue is available at block
     // entry, ResolvedDbgOps will contain the machine locations/constants for
for (DbgOpID ID : Value.getDbgOpIDs()) {
         }
         recoverAsEntryValue(Var, Value.Properties, Num);
         IsValueValid = false;
         break;
       }
 
       // Defer modifying ActiveVLocs until after we've confirmed we have a
       // live range.
-      LocIdx M = ValuesPreferredLoc->second;
+      LocIdx M = ValuesPreferredLoc->second.getLoc();
       ResolvedDbgOps.push_back(M);
     }
 
     // If we cannot produce a valid value for the LiveIn value within this
     // block, skip this variable.
     if (!IsValueValid)
       return;
 
loadInlocs(MachineBasicBlock &MBB, ValueTable &MLocs, DbgOpIDMap &DbgOpStore,
     ActiveMLocs.clear();
     ActiveVLocs.clear();
     VarLocs.clear();
     VarLocs.reserve(NumLocs);
     UseBeforeDefs.clear();
     UseBeforeDefVariables.clear();
 
     // Map of the preferred location for each value.
-    DenseMap<ValueIDNum, LocIdx> ValueToLoc;
+    DenseMap<ValueIDNum, LocationAndQuality> ValueToLoc;
 
     // Initialized the preferred-location map with illegal locations, to be
     // filled in later.
     for (const auto &VLoc : VLocs)
       if (VLoc.second.Kind == DbgValue::Def)
         for (DbgOpID OpID : VLoc.second.getDbgOpIDs())
           if (!OpID.ID.IsConst)
-            ValueToLoc.insert(
-                {DbgOpStore.find(OpID).ID, LocIdx::MakeIllegalLoc()});
+            ValueToLoc.insert({DbgOpStore.find(OpID).ID, LocationAndQuality()});
 
     ActiveMLocs.reserve(VLocs.size());
     ActiveVLocs.reserve(VLocs.size());
 
     // Produce a map of value numbers to the current machine locs they live
     // in. When emulating VarLocBasedImpl, there should only be one
     // location; when not, we get to pick.
     for (auto Location : MTracker->locations()) {
       LocIdx Idx = Location.Idx;
       ValueIDNum &VNum = MLocs[Idx.asU64()];
       if (VNum == ValueIDNum::EmptyValue)
         continue;
       VarLocs.push_back(VNum);
 
       // Is there a variable that wants a location for this value? If not, skip.
       auto VIt = ValueToLoc.find(VNum);
       if (VIt == ValueToLoc.end())
         continue;
 
-      LocIdx CurLoc = VIt->second;
-      // In order of preference, pick:
-      //  * Callee saved registers,
-      //  * Other registers,
-      //  * Spill slots.
-      if (CurLoc.isIllegal() || MTracker->isSpill(CurLoc) ||
-          (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.asU64()))) {
-        // Insert, or overwrite if insertion failed.
-        VIt->second = Idx;
-      }
+      auto &Previous = VIt->second;
+      // If this is the first location with that value, pick it. Otherwise,
+      // consider whether it's a "longer term" location.
+      std::optional<LocationQuality> ReplacementQuality =
+          getLocQualityIfBetter(Idx, Previous.getQuality());
+      if (ReplacementQuality)
+        Previous = LocationAndQuality(Idx, *ReplacementQuality);
     }
 
     // Now map variables to their picked LocIdxes.
     for (const auto &Var : VLocs) {
       loadVarInloc(MBB, DbgOpStore, ValueToLoc, Var.first, Var.second);
     }
     flushDbgValues(MBB.begin(), &MBB);
   }
public:
   /// block, create a DBG_VALUE.
   void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
     auto MIt = UseBeforeDefs.find(Inst);
     if (MIt == UseBeforeDefs.end())
       return;
 
     // Map of values to the locations that store them for every value used by
     // the variables that may have become available.
-    SmallDenseMap<ValueIDNum, LocIdx> ValueToLoc;
+    SmallDenseMap<ValueIDNum, LocationAndQuality> ValueToLoc;
 
     // Populate ValueToLoc with illegal default mappings for every value used by
     // any UseBeforeDef variables for this instruction.
     for (auto &Use : MIt->second) {
       if (!UseBeforeDefVariables.count(Use.Var))
         continue;
 
       for (DbgOp &Op : Use.Values) {
         assert(!Op.isUndef() && "UseBeforeDef erroneously created for a "
                                 "DbgValue with undef values.");
         if (Op.IsConst)
           continue;
 
-        ValueToLoc.insert(std::make_pair(Op.ID, LocIdx::MakeIllegalLoc()));
+        ValueToLoc.insert({Op.ID, LocationAndQuality()});
       }
     }
 
     // Exit early if we have no DbgValues to produce.
     if (ValueToLoc.empty())
       return;
 
     // Determine the best location for each desired value.
     for (auto Location : MTracker->locations()) {
       LocIdx Idx = Location.Idx;
       ValueIDNum &LocValueID = Location.Value;
 
       // Is there a variable that wants a location for this value? If not, skip.
       auto VIt = ValueToLoc.find(LocValueID);
       if (VIt == ValueToLoc.end())
         continue;
 
-      LocIdx CurLoc = VIt->second;
-      // In order of preference, pick:
-      //  * Callee saved registers,
-      //  * Other registers,
-      //  * Spill slots.
-      if (CurLoc.isIllegal() || MTracker->isSpill(CurLoc) ||
-          (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.asU64()))) {
-        // Insert, or overwrite if insertion failed.
-        VIt->second = Idx;
-      }
+      auto &Previous = VIt->second;
+      // If this is the first location with that value, pick it. Otherwise,
+      // consider whether it's a "longer term" location.
+      std::optional<LocationQuality> ReplacementQuality =
+          getLocQualityIfBetter(Idx, Previous.getQuality());
+      if (ReplacementQuality)
+        Previous = LocationAndQuality(Idx, *ReplacementQuality);
     }
 
     // Using the map of values to locations, produce a final set of values for
     // this variable.
     for (auto &Use : MIt->second) {
       if (!UseBeforeDefVariables.count(Use.Var))
         continue;
 
       SmallVector<ResolvedDbgOp> DbgOps;
 
       for (DbgOp &Op : Use.Values) {
         if (Op.IsConst) {
           DbgOps.push_back(Op.MO);
           continue;
         }
-        LocIdx NewLoc = ValueToLoc.find(Op.ID)->second;
+        LocIdx NewLoc = ValueToLoc.find(Op.ID)->second.getLoc();
         if (NewLoc.isIllegal())
           break;
         DbgOps.push_back(NewLoc);
       }
 
       // If at least one value used by this debug value is no longer available,
       // i.e. one of the values was killed before we finished defining all of
       // the values used by this variable, discard.
bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
 
   // If we're on the final pass through the function, decompose this INSTR_REF
   // into a plain DBG_VALUE.
   if (!TTracker)
     return true;
 
   // Pick a location for the machine value number, if such a location exists.
   // (This information could be stored in TransferTracker to make it faster).
-  std::optional<LocIdx> FoundLoc;
+  TransferTracker::LocationAndQuality FoundLoc;
   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;
+      std::optional<TransferTracker::LocationQuality> ReplacementQuality =
+          TTracker->getLocQualityIfBetter(CurL, FoundLoc.getQuality());
+      if (ReplacementQuality) {
+        FoundLoc =
+            TransferTracker::LocationAndQuality(CurL, *ReplacementQuality);
+        if (FoundLoc.isBest())
+          break;
       }
-
-      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.
     }
   }
 
   SmallVector<ResolvedDbgOp> NewLocs;
-  if (FoundLoc)
-    NewLocs.push_back(*FoundLoc);
+  if (!FoundLoc.isIllegal())
+    NewLocs.push_back(FoundLoc.getLoc());
   // 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 &&
+  if (FoundLoc.isIllegal() && NewID && NewID->getBlock() == CurBB &&
       NewID->getInst() > CurInst) {
     SmallVector<DbgOp> UseBeforeDefLocs;
     UseBeforeDefLocs.push_back(*NewID);
     TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false, false},
                               UseBeforeDefLocs, NewID->getInst());
   }
 
   // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
   // This DBG_VALUE is potentially a $noreg / undefined location, if
-  // FoundLoc is None.
+  // FoundLoc is illegal.
   // (XXX -- could morph the DBG_INSTR_REF in the future).
   MachineInstr *DbgMI = MTracker->emitLoc(NewLocs, V, Properties);
 
   TTracker->PendingDbgValues.push_back(DbgMI);
   TTracker->flushDbgValues(MI.getIterator(), nullptr);
   return true;
 }
 

llvm/test/DebugInfo/MIR/X86/live-debug-values-restore.mir

 # This second function has been appended as a regression test against a
 # crash, caused by expressions being created from spill restores that did
 # not preserve fragment information. Test that no empty expressions are
 # created at all, and the last block describes both variable fragments.
 
 # CHECK-LABEL: name: g
 # CHECK-NOT: !DIExpression()
 # CHECK-LABEL: bb.2.if.end:
+# CHECK:       DBG_VALUE $rbx, $noreg, ![[QVAR]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 # CHECK:       DBG_VALUE $rdi, $noreg, ![[QVAR]], !DIExpression(DW_OP_LLVM_fragment, 0, 32)
-# CHECK-NEXT:  DBG_VALUE $rbx, $noreg, ![[QVAR]], !DIExpression(DW_OP_LLVM_fragment, 32, 32)
 
 name:            g
 alignment:       16
 tracksRegLiveness: true
 liveins:         
   - { reg: '$rdi', virtual-reg: '' }
 frameInfo:       
   stackSize:       48