[DebugInfo] Correctly coalesce DBG_VALUEs that mix direct and indirect values

Summary:
This should fix a regression introduced by r313786, which switched from
MachineInstr::isIndirectDebugValue() to checking if operand 1 is an
immediate. I didn't have a test case for it until now.

A single UserValue, which approximates a user variable, may have many
DBG_VALUE instructions that disagree about whether the variable is in
memory or in a virtual register. This will become much more common once
we have llvm.dbg.addr, but you can construct such a test case manually
today with llvm.dbg.value.

Before this change, we would get two UserValues: one for direct and one
for indirect DBG_VALUE instructions describing the same variable. If we
build separate interval maps for direct and indirect locations, we will
end up accidentally coalescing identical DBG_VALUE intervals that need
to remain separate because they are broken up by intervals of the
opposite direct-ness.

Reviewers: aprantl

Subscribers: llvm-commits, hiraditya

Differential Revision: https://reviews.llvm.org/D37932

llvm-svn: 314819
diff --git a/llvm/lib/CodeGen/LiveDebugVariables.cpp b/llvm/lib/CodeGen/LiveDebugVariables.cpp
index d7345b0..7a4694f 100644
--- a/llvm/lib/CodeGen/LiveDebugVariables.cpp
+++ b/llvm/lib/CodeGen/LiveDebugVariables.cpp
@@ -91,8 +91,43 @@
   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
 }
 
+enum : unsigned { UndefLocNo = ~0U };
+
+/// Describes a location by number along with some flags about the original
+/// usage of the location.
+class DbgValueLocation {
+public:
+  DbgValueLocation(unsigned LocNo, bool WasIndirect)
+      : LocNo(LocNo), WasIndirect(WasIndirect) {
+    static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing");
+    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; }
+
+  DbgValueLocation changeLocNo(unsigned NewLocNo) const {
+    return DbgValueLocation(NewLocNo, WasIndirect);
+  }
+
+  bool operator==(const DbgValueLocation &O) const {
+    return LocNo == O.LocNo && WasIndirect == O.WasIndirect;
+  }
+  bool operator!=(const DbgValueLocation &O) const { return !(*this == O); }
+
+private:
+  unsigned LocNo : 31;
+  unsigned WasIndirect : 1;
+};
+
 /// LocMap - Map of where a user value is live, and its location.
-using LocMap = IntervalMap<SlotIndex, unsigned, 4>;
+using LocMap = IntervalMap<SlotIndex, DbgValueLocation, 4>;
 
 namespace {
 
@@ -110,7 +145,6 @@
 class UserValue {
   const DILocalVariable *Variable; ///< The debug info variable we are part of.
   const DIExpression *Expression; ///< Any complex address expression.
-  bool IsIndirect;        ///< true if this is a register-indirect+offset value.
   DebugLoc dl;            ///< The debug location for the variable. This is
                           ///< used by dwarf writer to find lexical scope.
   UserValue *leader;      ///< Equivalence class leader.
@@ -128,7 +162,7 @@
 
   /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx,
-                        unsigned LocNo, bool Spilled, LiveIntervals &LIS,
+                        DbgValueLocation Loc, bool Spilled, LiveIntervals &LIS,
                         const TargetInstrInfo &TII);
 
   /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
@@ -138,10 +172,10 @@
 
 public:
   /// UserValue - Create a new UserValue.
-  UserValue(const DILocalVariable *var, const DIExpression *expr, bool i,
-            DebugLoc L, LocMap::Allocator &alloc)
-      : Variable(var), Expression(expr), IsIndirect(i), dl(std::move(L)),
-        leader(this), locInts(alloc) {}
+  UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
+            LocMap::Allocator &alloc)
+      : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
+        locInts(alloc) {}
 
   /// getLeader - Get the leader of this value's equivalence class.
   UserValue *getLeader() {
@@ -156,13 +190,12 @@
 
   /// match - Does this UserValue match the parameters?
   bool match(const DILocalVariable *Var, const DIExpression *Expr,
-             const DILocation *IA, bool indirect) const {
-    return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA &&
-           indirect == IsIndirect;
+             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;
   }
 
-  enum : unsigned { UndefLocNo = ~0U };
-
   /// merge - Merge equivalence classes.
   static UserValue *merge(UserValue *L1, UserValue *L2) {
     L2 = L2->getLeader();
@@ -211,14 +244,15 @@
   void mapVirtRegs(LDVImpl *LDV);
 
   /// addDef - Add a definition point to this value.
-  void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
+  void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect) {
+    DbgValueLocation Loc(getLocationNo(LocMO), IsIndirect);
     // Add a singular (Idx,Idx) -> Loc mapping.
     LocMap::iterator I = locInts.find(Idx);
     if (!I.valid() || I.start() != Idx)
-      I.insert(Idx, Idx.getNextSlot(), getLocationNo(LocMO));
+      I.insert(Idx, Idx.getNextSlot(), Loc);
     else
       // A later DBG_VALUE at the same SlotIndex overrides the old location.
-      I.setValue(getLocationNo(LocMO));
+      I.setValue(Loc);
   }
 
   /// extendDef - Extend the current definition as far as possible down.
@@ -226,12 +260,12 @@
   /// range of VNI.
   /// End points where VNI is no longer live are added to Kills.
   /// @param Idx   Starting point for the definition.
-  /// @param LocNo Location number to propagate.
+  /// @param Loc   Location number to propagate.
   /// @param LR    Restrict liveness to where LR has the value VNI. May be null.
   /// @param VNI   When LR is not null, this is the value to restrict to.
   /// @param Kills Append end points of VNI's live range to Kills.
   /// @param LIS   Live intervals analysis.
-  void extendDef(SlotIndex Idx, unsigned LocNo,
+  void extendDef(SlotIndex Idx, DbgValueLocation Loc,
                  LiveRange *LR, const VNInfo *VNI,
                  SmallVectorImpl<SlotIndex> *Kills,
                  LiveIntervals &LIS);
@@ -241,13 +275,14 @@
   /// 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 Kills   Points where the range of LocNo could be extended.
   /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
-  void addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
-                       const SmallVectorImpl<SlotIndex> &Kills,
-                       SmallVectorImpl<std::pair<SlotIndex, unsigned>> &NewDefs,
-                       MachineRegisterInfo &MRI,
-                       LiveIntervals &LIS);
+  void addDefsFromCopies(
+      LiveInterval *LI, unsigned LocNo, bool WasIndirect,
+      const SmallVectorImpl<SlotIndex> &Kills,
+      SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
+      MachineRegisterInfo &MRI, LiveIntervals &LIS);
 
   /// computeIntervals - Compute the live intervals of all locations after
   /// collecting all their def points.
@@ -302,7 +337,7 @@
 
   /// getUserValue - Find or create a UserValue.
   UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
-                          bool IsIndirect, const DebugLoc &DL);
+                          const DebugLoc &DL);
 
   /// lookupVirtReg - Find the EC leader for VirtReg or null.
   UserValue *lookupVirtReg(unsigned VirtReg);
@@ -400,10 +435,13 @@
   OS << "\"\t";
   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
     OS << " [" << I.start() << ';' << I.stop() << "):";
-    if (I.value() == UndefLocNo)
+    if (I.value().isUndef())
       OS << "undef";
-    else
-      OS << I.value();
+    else {
+      OS << I.value().locNo();
+      if (I.value().wasIndirect())
+        OS << " ind";
+    }
   }
   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
     OS << " Loc" << i << '=';
@@ -427,19 +465,18 @@
 }
 
 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
-                                 const DIExpression *Expr, bool IsIndirect,
-                                 const DebugLoc &DL) {
+                                 const DIExpression *Expr, 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(), IsIndirect))
+      if (UV->match(Var, Expr, DL->getInlinedAt()))
         return UV;
   }
 
   userValues.push_back(
-      llvm::make_unique<UserValue>(Var, Expr, IsIndirect, DL, allocator));
+      llvm::make_unique<UserValue>(Var, Expr, DL, allocator));
   UserValue *UV = userValues.back().get();
   Leader = UserValue::merge(Leader, UV);
   return UV;
@@ -466,15 +503,15 @@
     return false;
   }
 
-  // Get or create the UserValue for (variable,offset).
+  // 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();
-  //here.
-  UserValue *UV = getUserValue(Var, Expr, IsIndirect, MI.getDebugLoc());
-  UV->addDef(Idx, MI.getOperand(0));
+  UserValue *UV =
+      getUserValue(Var, Expr, MI.getDebugLoc());
+  UV->addDef(Idx, MI.getOperand(0), IsIndirect);
   return true;
 }
 
@@ -509,7 +546,7 @@
 
 /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
 /// data-flow analysis to propagate them beyond basic block boundaries.
-void UserValue::extendDef(SlotIndex Idx, unsigned LocNo, LiveRange *LR,
+void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
                           const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills,
                           LiveIntervals &LIS) {
   SlotIndex Start = Idx;
@@ -536,7 +573,7 @@
   if (I.valid() && I.start() <= Start) {
     // Stop when meeting a different location or an already extended interval.
     Start = Start.getNextSlot();
-    if (I.value() != LocNo || I.stop() != Start)
+    if (I.value() != Loc || I.stop() != Start)
       return;
     // This is a one-slot placeholder. Just skip it.
     ++I;
@@ -552,14 +589,14 @@
     Kills->push_back(Stop);
 
   if (Start < Stop)
-    I.insert(Start, Stop, LocNo);
+    I.insert(Start, Stop, Loc);
 }
 
-void
-UserValue::addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
-                       const SmallVectorImpl<SlotIndex> &Kills,
-                       SmallVectorImpl<std::pair<SlotIndex, unsigned>> &NewDefs,
-                       MachineRegisterInfo &MRI, LiveIntervals &LIS) {
+void UserValue::addDefsFromCopies(
+    LiveInterval *LI, unsigned LocNo, bool WasIndirect,
+    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.
@@ -586,7 +623,7 @@
     // 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)
+    if (!I.valid() || I.value().locNo() != LocNo)
       continue;
 
     if (!LIS.hasInterval(DstReg))
@@ -619,8 +656,9 @@
       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
-      I.insert(Idx, Idx.getNextSlot(), LocNo);
-      NewDefs.push_back(std::make_pair(Idx, LocNo));
+      DbgValueLocation NewLoc(LocNo, WasIndirect);
+      I.insert(Idx, Idx.getNextSlot(), NewLoc);
+      NewDefs.push_back(std::make_pair(Idx, NewLoc));
       break;
     }
   }
@@ -629,36 +667,37 @@
 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
                                  const TargetRegisterInfo &TRI,
                                  LiveIntervals &LIS, LexicalScopes &LS) {
-  SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs;
+  SmallVector<std::pair<SlotIndex, DbgValueLocation>, 16> Defs;
 
   // Collect all defs to be extended (Skipping undefs).
   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
-    if (I.value() != UndefLocNo)
+    if (!I.value().isUndef())
       Defs.push_back(std::make_pair(I.start(), I.value()));
 
   // Extend all defs, and possibly add new ones along the way.
   for (unsigned i = 0; i != Defs.size(); ++i) {
     SlotIndex Idx = Defs[i].first;
-    unsigned LocNo = Defs[i].second;
-    const MachineOperand &Loc = locations[LocNo];
+    DbgValueLocation Loc = Defs[i].second;
+    const MachineOperand &LocMO = locations[Loc.locNo()];
 
-    if (!Loc.isReg()) {
-      extendDef(Idx, LocNo, nullptr, nullptr, nullptr, LIS);
+    if (!LocMO.isReg()) {
+      extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS);
       continue;
     }
 
     // Register locations are constrained to where the register value is live.
-    if (TargetRegisterInfo::isVirtualRegister(Loc.getReg())) {
+    if (TargetRegisterInfo::isVirtualRegister(LocMO.getReg())) {
       LiveInterval *LI = nullptr;
       const VNInfo *VNI = nullptr;
-      if (LIS.hasInterval(Loc.getReg())) {
-        LI = &LIS.getInterval(Loc.getReg());
+      if (LIS.hasInterval(LocMO.getReg())) {
+        LI = &LIS.getInterval(LocMO.getReg());
         VNI = LI->getVNInfoAt(Idx);
       }
       SmallVector<SlotIndex, 16> Kills;
-      extendDef(Idx, LocNo, LI, VNI, &Kills, LIS);
+      extendDef(Idx, Loc, LI, VNI, &Kills, LIS);
       if (LI)
-        addDefsFromCopies(LI, LocNo, Kills, Defs, MRI, LIS);
+        addDefsFromCopies(LI, Loc.locNo(), Loc.wasIndirect(), Kills, Defs, MRI,
+                          LIS);
       continue;
     }
 
@@ -672,7 +711,7 @@
 
   // Erase all the undefs.
   for (LocMap::iterator I = locInts.begin(); I.valid();)
-    if (I.value() == UndefLocNo)
+    if (I.value().isUndef())
       I.erase();
     else
       ++I;
@@ -702,7 +741,7 @@
     // I.stop() >= PrevEnd. Check for overlap.
     if (PrevEnd && I.start() < PrevEnd) {
       SlotIndex IStop = I.stop();
-      unsigned LocNo = I.value();
+      DbgValueLocation Loc = I.value();
 
       // Stop overlaps previous end - trim the end of the interval to
       // the scope range.
@@ -713,7 +752,7 @@
       // current) range create a new interval for the remainder (which
       // may be further trimmed).
       if (RStart < IStop)
-        I.insert(RStart, IStop, LocNo);
+        I.insert(RStart, IStop, Loc);
     }
 
     // Advance I so that I.stop() >= RStart, and check for overlap.
@@ -840,7 +879,7 @@
         break;
 
       // Now LII->end > LocMapI.start(). Do we have an overlap?
-      if (LocMapI.value() == OldLocNo && LII->start < LocMapI.stop()) {
+      if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) {
         // Overlapping correct location. Allocate NewLocNo now.
         if (NewLocNo == UndefLocNo) {
           MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
@@ -851,6 +890,7 @@
 
         SlotIndex LStart = LocMapI.start();
         SlotIndex LStop  = LocMapI.stop();
+        DbgValueLocation OldLoc = LocMapI.value();
 
         // Trim LocMapI down to the LII overlap.
         if (LStart < LII->start)
@@ -859,17 +899,17 @@
           LocMapI.setStopUnchecked(LII->end);
 
         // Change the value in the overlap. This may trigger coalescing.
-        LocMapI.setValue(NewLocNo);
+        LocMapI.setValue(OldLoc.changeLocNo(NewLocNo));
 
         // Re-insert any removed OldLocNo ranges.
         if (LStart < LocMapI.start()) {
-          LocMapI.insert(LStart, LocMapI.start(), OldLocNo);
+          LocMapI.insert(LStart, LocMapI.start(), OldLoc);
           ++LocMapI;
           assert(LocMapI.valid() && "Unexpected coalescing");
         }
         if (LStop > LocMapI.stop()) {
           ++LocMapI;
-          LocMapI.insert(LII->end, LStop, OldLocNo);
+          LocMapI.insert(LII->end, LStop, OldLoc);
           --LocMapI;
         }
       }
@@ -892,14 +932,14 @@
   locations.erase(locations.begin() + OldLocNo);
   LocMapI.goToBegin();
   while (LocMapI.valid()) {
-    unsigned v = LocMapI.value();
-    if (v == OldLocNo) {
+    DbgValueLocation v = LocMapI.value();
+    if (v.locNo() == OldLocNo) {
       DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
                    << LocMapI.stop() << ")\n");
       LocMapI.erase();
     } else {
-      if (v > OldLocNo)
-        LocMapI.setValueUnchecked(v-1);
+      if (v.locNo() > OldLocNo)
+        LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
       ++LocMapI;
     }
   }
@@ -1003,8 +1043,9 @@
   // DBG_VALUE intervals with different vregs that were allocated to the same
   // physical register.
   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
-    unsigned NewLocNo = LocNoMap[I.value()];
-    I.setValueUnchecked(NewLocNo);
+    DbgValueLocation Loc = I.value();
+    unsigned NewLocNo = LocNoMap[Loc.locNo()];
+    I.setValueUnchecked(Loc.changeLocNo(NewLocNo));
     I.setStart(I.start());
   }
 }
@@ -1034,11 +1075,11 @@
 }
 
 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx,
-                                 unsigned LocNo, bool Spilled,
+                                 DbgValueLocation Loc, bool Spilled,
                                  LiveIntervals &LIS,
                                  const TargetInstrInfo &TII) {
   MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
-  MachineOperand &Loc = locations[LocNo];
+  MachineOperand &MO = locations[Loc.locNo()];
   ++NumInsertedDebugValues;
 
   assert(cast<DILocalVariable>(Variable)
@@ -1048,18 +1089,20 @@
   // 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.
-  bool NewIndirect = IsIndirect || Spilled;
   const DIExpression *Expr = Expression;
-  if (Spilled && IsIndirect)
-    Expr = DIExpression::prepend(Expr, DIExpression::WithDeref);
+  bool IsIndirect = Loc.wasIndirect();
+  if (Spilled) {
+    if (IsIndirect)
+      Expr = DIExpression::prepend(Expr, DIExpression::WithDeref);
+    IsIndirect = true;
+  }
 
-  assert((!Spilled || Loc.isFI()) &&
-         "a spilled location must be a frame index");
+  assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index");
 
   MachineInstrBuilder MIB =
       BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE))
-          .add(Loc);
-  if (NewIndirect)
+          .add(MO);
+  if (IsIndirect)
     MIB.addImm(0U);
   else
     MIB.addReg(0U, RegState::Debug);
@@ -1074,8 +1117,8 @@
   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
     SlotIndex Start = I.start();
     SlotIndex Stop = I.stop();
-    unsigned LocNo = I.value();
-    bool Spilled = LocNo != UndefLocNo ? SpilledLocations.test(LocNo) : false;
+    DbgValueLocation Loc = I.value();
+    bool Spilled = !Loc.isUndef() ? SpilledLocations.test(Loc.locNo()) : false;
 
     // If the interval start was trimmed to the lexical scope insert the
     // DBG_VALUE at the previous index (otherwise it appears after the
@@ -1083,12 +1126,12 @@
     if (trimmedDefs.count(Start))
       Start = Start.getPrevIndex();
 
-    DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo);
+    DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
 
     DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
-    insertDebugValue(&*MBB, Start, LocNo, Spilled, LIS, TII);
+    insertDebugValue(&*MBB, Start, Loc, Spilled, LIS, TII);
     // This interval may span multiple basic blocks.
     // Insert a DBG_VALUE into each one.
     while(Stop > MBBEnd) {
@@ -1098,7 +1141,7 @@
         break;
       MBBEnd = LIS.getMBBEndIdx(&*MBB);
       DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
-      insertDebugValue(&*MBB, Start, LocNo, Spilled, LIS, TII);
+      insertDebugValue(&*MBB, Start, Loc, Spilled, LIS, TII);
     }
     DEBUG(dbgs() << '\n');
     if (MBB == MFEnd)