[DebugInfo@O2] Fix PR41992: LiveDebugVariables can drop DBG_VALUEs through misinterpreting fragments

[Orlando]

Summary

Bug: https://bugs.llvm.org/show_bug.cgi?id=41992

This patch prevents DBG_VALUE instructions being incorrectly coalesced by
liveDebugVariables.

A 'UserValue' roughly represents a source variable. A UserValue was identified
by looking at the source variable, DIExpression, and the inlined-at location
of the source variable.

This is a problem because this means arbitrary DIExpressions were being used
to classify the UserValues. For example, a DW_OP_deref on the value presented
in the DBG_VALUE doesn't change what source variable we're describing. Instead
we should only be looking at the fragment info in the DIExpression.

This patch identifies UserValues by looking at the source vaiable, the variable
fragment info, and the inlined-at location. UserValue no longer tracks the
DIExpression associated with the set of DBG_VALUES.

DbgValueLocation seemed like a good place to keep track of the DIExpression
used by the DBG_VALUE because:

1. This stops the locations with different DIExpressions being coalesced by the interval map used to track the uses.
2. There is a 1-to-1 mapping of use locations to DIExpressions.
3. Minimal source changes required to implement this fix.

I've added a test which covers the case outlined in the bug.

[aprantl]

The testcase makes perfect sense and that sounds like a good bug to fix!
I do wonder wonder why the patch goes out of its way to save fragment infos when fragments don't appear in the test at all?

[aprantl]

I think you may need at least one more test that involves fragments. Two non-overlapping fragments should be handled like DBG_VALUEs that describe different variables. Two (partially) overlapping fragments should be handled as if they are describing the same variable.

[Orlando]

Thanks for the review!

I do wonder wonder why the patch goes out of its way to save fragment infos when fragments don't appear in the test at all?

The fragment info changes were a natural path since the DIExpression could no longer be used to identify the UserValues, but failing to test any IR with fragments was an oversight for sure.

Two (partially) overlapping fragments should be handled as if they are describing the same variable.

I hadn't considered the 'partially' case, I'll look into this now. I think my current patch will change shape a bit as a result.

[Orlando]

I'm abandoning this because I've created the WIP revision D70121 which handles fragment overlaps.

llvm/lib/CodeGen/LiveDebugVariables.cpp

 
 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID) {
   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
 }
 
 enum : unsigned { UndefLocNo = ~0U };
 
 /// Describes a location by number along with some flags about the original
-/// usage of the location.
+/// usage of the location. A DIExpression is used to help classify the
+/// location usage.
 class DbgValueLocation {
 public:
-  DbgValueLocation(unsigned LocNo, bool WasIndirect)
-      : LocNo(LocNo), WasIndirect(WasIndirect) {
-    static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing");
+  DbgValueLocation(unsigned LocNo, bool WasIndirect, const DIExpression &Expr)
+      : LocNo(LocNo), WasIndirect(WasIndirect), Expression(&Expr) {
     assert(locNo() == LocNo && "location truncation");
   }
 
   DbgValueLocation() : LocNo(0), WasIndirect(0) {}
 
   unsigned locNo() const {
     // Fix up the undef location number, which gets truncated.
     return LocNo == INT_MAX ? UndefLocNo : LocNo;
   }
   bool wasIndirect() const { return WasIndirect; }
   bool isUndef() const { return locNo() == UndefLocNo; }
+  const DIExpression *expression() const { return Expression; }
 
   DbgValueLocation changeLocNo(unsigned NewLocNo) const {
-    return DbgValueLocation(NewLocNo, WasIndirect);
+    return DbgValueLocation(NewLocNo, WasIndirect, *Expression);
   }
 
   friend inline bool operator==(const DbgValueLocation &LHS,
                                 const DbgValueLocation &RHS) {
-    return LHS.LocNo == RHS.LocNo && LHS.WasIndirect == RHS.WasIndirect;
+    return LHS.LocNo == RHS.LocNo && LHS.WasIndirect == RHS.WasIndirect &&
+           LHS.Expression == RHS.Expression;
   }
 
   friend inline bool operator!=(const DbgValueLocation &LHS,
                                 const DbgValueLocation &RHS) {
     return !(LHS == RHS);
   }
 
 private:
+  const DIExpression *Expression = nullptr;
   unsigned LocNo : 31;
   unsigned WasIndirect : 1;
 };
 
 /// Map of where a user value is live, and its location.
-using LocMap = IntervalMap<SlotIndex, DbgValueLocation, 4>;
+using LocMap = IntervalMap<SlotIndex, DbgValueLocation>;
 
 /// Map of stack slot offsets for spilled locations.
 /// Non-spilled locations are not added to the map.
 using SpillOffsetMap = DenseMap<unsigned, unsigned>;
 
 namespace {
 
 class LDVImpl;
 
 /// A user value is a part of a debug info user variable.
 ///
 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
 /// holds part of a user variable. The part is identified by a byte offset.
 ///
 /// UserValues are grouped into equivalence classes for easier searching. Two
 /// user values are related if they refer to the same variable, or if they are
 /// held by the same virtual register. The equivalence class is the transitive
 /// closure of that relation.
 class UserValue {
   const DILocalVariable *Variable; ///< The debug info variable we are part of.
-  const DIExpression *Expression; ///< Any complex address expression.
+  /// Fragment of the source variable.
+  const Optional<DIExpression::FragmentInfo> FragInfo;
   DebugLoc dl;            ///< The debug location for the variable. This is
                           ///< used by dwarf writer to find lexical scope.
   UserValue *leader;      ///< Equivalence class leader.
   UserValue *next = nullptr; ///< Next value in equivalence class, or null.
 
   /// Numbered locations referenced by locmap.
   SmallVector<MachineOperand, 4> locations;
 
   /// Map of slot indices where this value is live.
   LocMap locInts;
 
-  /// Insert a DBG_VALUE into MBB at Idx for LocNo.
+  /// Insert a DBG_VALUE into MBB at Idx for Loc.locNo().
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
                         SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled,
                         unsigned SpillOffset, LiveIntervals &LIS,
                         const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI);
 
   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
   /// is live. Returns true if any changes were made.
   bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
                      LiveIntervals &LIS);
 
 public:
   /// Create a new UserValue.
-  UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
+  UserValue(const DILocalVariable *var,
+            Optional<DIExpression::FragmentInfo> frag, DebugLoc L,
             LocMap::Allocator &alloc)
-      : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
+      : Variable(var), FragInfo(frag), dl(std::move(L)), leader(this),
         locInts(alloc) {}
 
   /// Get the leader of this value's equivalence class.
   UserValue *getLeader() {
     UserValue *l = leader;
     while (l != l->leader)
       l = l->leader;
     return leader = l;
   }
 
   /// Return the next UserValue in the equivalence class.
   UserValue *getNext() const { return next; }
 
   /// Does this UserValue match the parameters?
-  bool match(const DILocalVariable *Var, const DIExpression *Expr,
+  bool match(const DILocalVariable *Var,
+             Optional<DIExpression::FragmentInfo> Frag,
              const DILocation *IA) const {
-    // FIXME: The fragment should be part of the equivalence class, but not
-    // other things in the expression like stack values.
-    return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA;
+    return Var == Variable && Frag == FragInfo && dl->getInlinedAt() == IA;
   }
 
   /// Merge equivalence classes.
   static UserValue *merge(UserValue *L1, UserValue *L2) {
     L2 = L2->getLeader();
     if (!L1)
       return L2;
     L1 = L1->getLeader();
unsigned getLocationNo(const MachineOperand &LocMO) {
     }
     return locations.size() - 1;
   }
 
   /// Ensure that all virtual register locations are mapped.
   void mapVirtRegs(LDVImpl *LDV);
 
   /// Add a definition point to this value.
-  void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect) {
-    DbgValueLocation Loc(getLocationNo(LocMO), IsIndirect);
+  void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect,
+              const DIExpression &Expr) {
+    DbgValueLocation Loc(getLocationNo(LocMO), IsIndirect, Expr);
+
     // Add a singular (Idx,Idx) -> Loc mapping.
     LocMap::iterator I = locInts.find(Idx);
     if (!I.valid() || I.start() != Idx)
       I.insert(Idx, Idx.getNextSlot(), Loc);
     else
       // A later DBG_VALUE at the same SlotIndex overrides the old location.
       I.setValue(Loc);
   }
void extendDef(SlotIndex Idx, DbgValueLocation Loc,
                  SmallVectorImpl<SlotIndex> *Kills,
                  LiveIntervals &LIS);
 
   /// The value in LI/LocNo may be copies to other registers. Determine if
   /// any of the copies are available at the kill points, and add defs if
   /// possible.
   ///
   /// \param LI Scan for copies of the value in LI->reg.
-  /// \param LocNo Location number of LI->reg.
-  /// \param WasIndirect Indicates if the original use of LI->reg was indirect
+  /// \param Loc LI->reg location and usage debug info.
   /// \param Kills Points where the range of LocNo could be extended.
   /// \param [in,out] NewDefs Append (Idx, LocNo) of inserted defs here.
   void addDefsFromCopies(
-      LiveInterval *LI, unsigned LocNo, bool WasIndirect,
+      LiveInterval *LI, DbgValueLocation Loc,
       const SmallVectorImpl<SlotIndex> &Kills,
       SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
       MachineRegisterInfo &MRI, LiveIntervals &LIS);
 
   /// Compute the live intervals of all locations after collecting all their
   /// def points.
   void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
                         LiveIntervals &LIS, LexicalScopes &LS);
class LDVImpl {
   using VRMap = DenseMap<unsigned, UserValue *>;
   VRMap virtRegToEqClass;
 
   /// Map user variable to eq class leader.
   using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
   UVMap userVarMap;
 
   /// Find or create a UserValue.
-  UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
+  UserValue *getUserValue(const DILocalVariable *Var, Optional<DIExpression::FragmentInfo> Frag,
                           const DebugLoc &DL);
 
   /// Find the EC leader for VirtReg or null.
   UserValue *lookupVirtReg(unsigned VirtReg);
 
   /// Add DBG_VALUE instruction to our maps.
   ///
   /// \param MI DBG_VALUE instruction

 void UserValue::mapVirtRegs(LDVImpl *LDV) {
   for (unsigned i = 0, e = locations.size(); i != e; ++i)
     if (locations[i].isReg() &&
         Register::isVirtualRegister(locations[i].getReg()))
       LDV->mapVirtReg(locations[i].getReg(), this);
 }
 
 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
-                                 const DIExpression *Expr, const DebugLoc &DL) {
+                                 Optional<DIExpression::FragmentInfo> Frag, const DebugLoc &DL) {
   UserValue *&Leader = userVarMap[Var];
   if (Leader) {
     UserValue *UV = Leader->getLeader();
     Leader = UV;
     for (; UV; UV = UV->getNext())
-      if (UV->match(Var, Expr, DL->getInlinedAt()))
+      if (UV->match(Var, Frag, DL->getInlinedAt()))
         return UV;
   }
 
-  userValues.push_back(
-      std::make_unique<UserValue>(Var, Expr, DL, allocator));
+  userValues.push_back(std::make_unique<UserValue>(Var, Frag, DL, allocator));
   UserValue *UV = userValues.back().get();
   Leader = UserValue::merge(Leader, UV);
   return UV;
 }
 
 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
   assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs");
   UserValue *&Leader = virtRegToEqClass[VirtReg];
bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
 
   // Get or create the UserValue for (variable,offset) here.
   bool IsIndirect = MI.getOperand(1).isImm();
   if (IsIndirect)
     assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
   const DILocalVariable *Var = MI.getDebugVariable();
   const DIExpression *Expr = MI.getDebugExpression();
   UserValue *UV =
-      getUserValue(Var, Expr, MI.getDebugLoc());
+      getUserValue(Var, Expr->getFragmentInfo(), MI.getDebugLoc());
   if (!Discard)
-    UV->addDef(Idx, MI.getOperand(0), IsIndirect);
+    UV->addDef(Idx, MI.getOperand(0), IsIndirect, *Expr);
   else {
     MachineOperand MO = MachineOperand::CreateReg(0U, false);
     MO.setIsDebug();
-    UV->addDef(Idx, MO, false);
+    UV->addDef(Idx, MO, false, *Expr);
   }
   return true;
 }
 
 bool LDVImpl::handleDebugLabel(MachineInstr &MI, SlotIndex Idx) {
   // DBG_LABEL label
   if (MI.getNumOperands() != 1 || !MI.getOperand(0).isMetadata()) {
     LLVM_DEBUG(dbgs() << "Can't handle " << MI);
void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
   else if (!ToEnd && Kills)
     Kills->push_back(Stop);
 
   if (Start < Stop)
     I.insert(Start, Stop, Loc);
 }
 
 void UserValue::addDefsFromCopies(
-    LiveInterval *LI, unsigned LocNo, bool WasIndirect,
+    LiveInterval *LI, DbgValueLocation Loc,
     const SmallVectorImpl<SlotIndex> &Kills,
     SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
     MachineRegisterInfo &MRI, LiveIntervals &LIS) {
   if (Kills.empty())
     return;
   // Don't track copies from physregs, there are too many uses.
   if (!Register::isVirtualRegister(LI->reg))
     return;
for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
     // or it could be spilled.
     if (!Register::isVirtualRegister(DstReg))
       continue;
 
     // Is LocNo extended to reach this copy? If not, another def may be blocking
     // it, or we are looking at a wrong value of LI.
     SlotIndex Idx = LIS.getInstructionIndex(*MI);
     LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
-    if (!I.valid() || I.value().locNo() != LocNo)
+    if (!I.valid() || I.value().locNo() != Loc.locNo())
       continue;
 
     if (!LIS.hasInterval(DstReg))
       continue;
     LiveInterval *DstLI = &LIS.getInterval(DstReg);
     const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
     assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
     CopyValues.push_back(std::make_pair(DstLI, DstVNI));
for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
       LocMap::iterator I = locInts.find(Idx);
       if (I.valid() && I.start() <= Idx)
         continue;
       LLVM_DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
                         << DstVNI->id << " in " << *DstLI << '\n');
       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
-      DbgValueLocation NewLoc(LocNo, WasIndirect);
+      DbgValueLocation NewLoc = Loc.changeLocNo(LocNo);
       I.insert(Idx, Idx.getNextSlot(), NewLoc);
       NewDefs.push_back(std::make_pair(Idx, NewLoc));
       break;
     }
   }
 }
 
 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
if (Register::isVirtualRegister(LocMO.getReg())) {
       // if the original location for example is %vreg0:sub_hi, and we find a
       // full register copy in addDefsFromCopies (at the moment it only handles
       // full register copies), then we must add the sub1 sub-register index to
       // the new location. However, that is only possible if the new virtual
       // register is of the same regclass (or if there is an equivalent
       // sub-register in that regclass). For now, simply skip handling copies if
       // a sub-register is involved.
       if (LI && !LocMO.getSubReg())
-        addDefsFromCopies(LI, Loc.locNo(), Loc.wasIndirect(), Kills, Defs, MRI,
-                          LIS);
+        addDefsFromCopies(LI, Loc, Kills, Defs, MRI, LIS);
       continue;
     }
 
     // For physregs, we only mark the start slot idx. DwarfDebug will see it
     // as if the DBG_VALUE is valid up until the end of the basic block, or
     // the next def of the physical register. So we do not need to extend the
     // range. It might actually happen that the DBG_VALUE is the last use of
     // the physical register (e.g. if this is an unused input argument to a
void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
   assert(cast<DILocalVariable>(Variable)
              ->isValidLocationForIntrinsic(getDebugLoc()) &&
          "Expected inlined-at fields to agree");
 
   // If the location was spilled, the new DBG_VALUE will be indirect. If the
   // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
   // that the original virtual register was a pointer. Also, add the stack slot
   // offset for the spilled register to the expression.
-  const DIExpression *Expr = Expression;
+  const DIExpression *Expr = Loc.expression();
   uint8_t DIExprFlags = DIExpression::ApplyOffset;
   bool IsIndirect = Loc.wasIndirect();
   if (Spilled) {
     if (IsIndirect)
       DIExprFlags |= DIExpression::DerefAfter;
     Expr =
         DIExpression::prepend(Expr, DIExprFlags, SpillOffset);
     IsIndirect = true;

llvm/test/DebugInfo/pr41992.ll

+; Test that two identical DBG_VALUEs are not coalesced when another used to describe
+; the same source variable with a different DIExpression is found between them.
+
+; RUN: llc %s -stop-after=virtregrewriter -o - | FileCheck %s
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref)
+; CHECK: DBG_VALUE 1, $noreg, ![[DBG_VAR]], !DIExpression()
+; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_deref)
+
+declare void @llvm.dbg.addr(metadata, metadata, metadata)
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+declare void @escape(i32*)
+
+@global = external global i32, align 4
+
+define void @f(i32 %x) !dbg !8 {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_deref)), !dbg !18
+  call void @escape(i32* %x.addr), !dbg !18
+  call void @llvm.dbg.value(metadata i32 1, metadata !13, metadata !DIExpression()), !dbg !18
+  store i32 1, i32* @global, align 4, !dbg !18
+  call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_deref)), !dbg !18
+  store i32 2, i32* %x.addr, align 4, !dbg !18
+  call void @escape(i32* %x.addr), !dbg !18
+  ret void, !dbg !18
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "dse.c", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!7 = !{!"clang version 6.0.0 "}
+!8 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 3, type: !9, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12)
+!9 = !DISubroutineType(types: !10)
+!10 = !{null, !11}
+!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!12 = !{!13}
+!13 = !DILocalVariable(name: "x", arg: 1, scope: !8, file: !1, line: 3, type: !11)
+!18 = !DILocation(line: 3, column: 12, scope: !8)