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

[rnk]

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.

[rnk]

• rebase

[dblaikie]

llvm/lib/CodeGen/LiveDebugVariables.cpp

119–122 ↗

(On Diff #116048)

Generally, binary op overloads should be non-members (they can be friends though, which can be defined inline) to ensure equal conversions are possible on both sides of the operand.

[aprantl]

llvm/lib/CodeGen/LiveDebugVariables.cpp

110 ↗

(On Diff #116048)

I find this confusing.. we only have 32 bits available for LocNo.. can this every fire?

[aprantl]

llvm/lib/CodeGen/LiveDebugVariables.cpp

110 ↗

(On Diff #116048)

s/32/31/

[rnk]

llvm/lib/CodeGen/LiveDebugVariables.cpp

110 ↗

(On Diff #116048)

It's INT_MAX, not UINT_MAX, i.e. 0x7FFFFFFF, so it's the all-ones value of the 31-bit bitfield. I wasn't sure what the best way to express this was. =/

[rnk]

ping, I want to make sure nobody else has to debug the regression. :)

[danilaml]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

What does that mean/imply? I've come across a case/bug that would be solved by not emitting same DBG_VALUE that differ only in that one has !DIExpression() and the other !DIExpression(DW_OP_LLVM_fragment, 0, <reg_size_in_bits>). Are those supposed to be the equivalent and one can safely emit a singe !DIExpression() instead? What caused this to remain as FIXME in the first place?

[aprantl]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

!DIExpression(DW_OP_LLVM_fragment, 0, <reg_size_in_bits>) could a special case that could just mean that sizeof(variable)-reg_size bits are unused padding, in which case it would have been better to emit a cast/sign-extend operation instead of a fragment, but that is hard to tell without the concrete example. Are there remaining upper bits in your variable that are significant? In any case, it is not generally safe to treat the fragment at offset 0 as equivalent to an empty expression, but there may be ways to void the fragment earlier in the compiler.

[danilaml]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

The variable is the same as reg in size as far as I can see (signed 32-bit integer).

I have something like

DBG_VALUE $r1, $noreg, !"i", !DIExpression()
$r2 = COPY $r1
DBG_VALUE $r2, $noreg, !"i", !DIExpression()
<some unrelated instr>
DBG_VALUE $r2, $noreg, !"i", !DIExpression(DW_OP_LLVM_fragment, 0, 32)
$r1 = ADD $r2, 1
DBG_VALUE $r1, $noreg, !"i", !DIExpression()
...

which is then broken by mi scheduling since LLVM only moves adjacent DBG_VALUES when it reschedules instructions (in this case it moves above copy before ADD leaving now wrong info fro $r2 after <some unrelated instr>).

This would be solved if !DIExpression() was coalesced with the fragment (so that all relevant DBG_VALUEs always follow the instruction in my case). I've noticed this FIXME this might be read as just that, hence asked to elaborate (I understand that preferable solution would be to (also) fix scheduler, but its obviously more involved).

[aprantl]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

Can you figure out which pass creates the fragment? (Probably SROA?)

[danilaml]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

It happens during DAG selection (although I don't see any debug values in its output). Last IR has no fragments ad first MIR has them. It could be the implicit result of some lowering but I don't know anything that might've caused it (possibly byproduct of some pattern match?). Anyway, how does that relate the question of whether empty empty expression on some reg is equivalent to fragment(0, size)? Or are you implying that fragment dbg value is wrong in this case and shouldn't have been generated?

[aprantl]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

Perhaps it's the DAG legalizer creating it?

If a fragment was created for a good reason, then an empty expression which covers the entire variable, is not equivalent to an fragment at offset 0 because there must be upper bits of the variable that are not covered by that fragment expression. But if the expression is redundant, because the fragment does cover the entire variable it perhaps shouldn't have been created, and that's the bug you'll want to fix.

[danilaml]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

Don't see anything suspicious with legalizer. The only thing I see in adjacent instruction is "ISEL: Starting pattern match" morphing add node into add_with_immediate (using patter from tablegen, I gather). Also, I don't quite get what you mean by "because there must be upper bits of the variable that are not covered by that fragment expression", since the variable, the register and the node type (i32) are all 32 bits. Perhaps fragments are added by tablegen pattern match to be conservative? Anyway, is it really a bug? It could be some sort of deficiency, but what is wrong with adding such fragments? Do they change the semantics of the debug info? I.e. do they differ in meaning from empty di expression? If not, then what's wrong with treating them equivalent in the function above? What does the FIXME comment mean by "The fragment should be part of the equivalence class"?

[aprantl]

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

195

What does the FIXME comment mean by "The fragment should be part of the equivalence class"

Two dbg.values describing the same (inlined instance of a) variable, with no fragment expression or overlapping fragment expressions describe the same entity and therefore the second dbg.value truncates the live range of the first and changes the location of that variable (fragment). Two dbg.values with non-overlapping fragment expressions are independent from each other, as if they were describing two different variables.

You were asking whether an empty DIExpression can be treated as the same as a fragment at offset 0, and the answer is no, because the upper bits are missing. If the fragment does cover the entire variable then the code that generated the fragment should be fixed, but you can't safely merge the fragment and the non-fragment here.

llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp

void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 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.
+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 {
 
 class LDVImpl;
 
 /// UserValue - 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.
-  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.
   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;
 
   /// Set of interval start indexes that have been trimmed to the
   /// lexical scope.
   SmallSet<SlotIndex, 2> trimmedDefs;
 
   /// 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
   /// is live. Returns true if any changes were made.
   bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
                      LiveIntervals &LIS);
 
 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() {
     UserValue *l = leader;
     while (l != l->leader)
       l = l->leader;
     return leader = l;
   }
 
   /// getNext - Return the next UserValue in the equivalence class.
   UserValue *getNext() const { return next; }
 
   /// 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();
     if (!L1)
       return L2;
     L1 = L1->getLeader();
     if (L1 == L2)
       return L1;
if (locations.back().isReg())
       locations.back().setIsUse();
     return locations.size() - 1;
   }
 
   /// mapVirtRegs - Ensure that all virtual register locations are mapped.
   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.
   /// Stop when meeting an existing def or when leaving the live
   /// 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);
 
   /// addDefsFromCopies - 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 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,
+      SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
+      MachineRegisterInfo &MRI, LiveIntervals &LIS);
 
   /// computeIntervals - Compute the live intervals of all locations after
   /// collecting all their def points.
   void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
                         LiveIntervals &LIS, LexicalScopes &LS);
 
   /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
   /// live. Returns true if any changes were made.
class LDVImpl {
   VRMap virtRegToEqClass;
 
   /// Map user variable to eq class leader.
   using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
   UVMap userVarMap;
 
   /// 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);
 
   /// handleDebugValue - Add DBG_VALUE instruction to our maps.
   /// @param MI  DBG_VALUE instruction
   /// @param Idx Last valid SLotIndex before instruction.
   /// @return    True if the DBG_VALUE instruction should be deleted.

 void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
   auto *DV = cast<DILocalVariable>(Variable);
   OS << "!\"";
   printExtendedName(OS, DV, dl);
 
   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 << '=';
     locations[i].print(OS, TRI);
   }
   OS << '\n';
 }
 
 void LDVImpl::print(raw_ostream &OS) {
   OS << "********** DEBUG VARIABLES **********\n";
   for (unsigned i = 0, e = userValues.size(); i != e; ++i)
     userValues[i]->print(OS, TRI);
 }
 #endif
 
 void UserValue::mapVirtRegs(LDVImpl *LDV) {
   for (unsigned i = 0, e = locations.size(); i != e; ++i)
     if (locations[i].isReg() &&
         TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
       LDV->mapVirtReg(locations[i].getReg(), this);
 }
 
 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;
 }
 
 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
   UserValue *&Leader = virtRegToEqClass[VirtReg];
bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
   // DBG_VALUE loc, offset, variable
   if (MI.getNumOperands() != 4 ||
       !(MI.getOperand(1).isReg() || MI.getOperand(1).isImm()) ||
       !MI.getOperand(2).isMetadata()) {
     DEBUG(dbgs() << "Can't handle " << MI);
     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;
 }
 
 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
   bool Changed = false;
   for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
        ++MFI) {
     MachineBasicBlock *MBB = &*MFI;
for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
       } while (MBBI != MBBE && MBBI->isDebugValue());
     }
   }
   return Changed;
 }
 
 /// 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;
   MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
   SlotIndex Stop = LIS.getMBBEndIdx(MBB);
   LocMap::iterator I = locInts.find(Start);
 
   // Limit to VNI's live range.
if (Segment->end < Stop) {
       ToEnd = false;
     }
   }
 
   // There could already be a short def at Start.
   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;
   }
 
   // Limited by the next def.
   if (I.valid() && I.start() < Stop) {
     Stop = I.start();
     ToEnd = false;
   }
   // Limited by VNI's live range.
   else if (!ToEnd && Kills)
     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,
+    SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
   if (Kills.empty())
     return;
   // Don't track copies from physregs, there are too many uses.
   if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
     return;
 
   // Collect all the (vreg, valno) pairs that are copies of LI.
   SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
     // or it could be spilled.
     if (!TargetRegisterInfo::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)
+    if (!I.valid() || I.value().locNo() != 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;
       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));
-      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;
     }
   }
 }
 
 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;
     }
 
     // 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
     // function).
   }
 
   // Erase all the undefs.
   for (LocMap::iterator I = locInts.begin(); I.valid();)
-    if (I.value() == UndefLocNo)
+    if (I.value().isUndef())
       I.erase();
     else
       ++I;
 
   // The computed intervals may extend beyond the range of the debug
   // location's lexical scope. In this case, splitting of an interval
   // can result in an interval outside of the scope being created,
   // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
void UserValue::computeIntervals(MachineRegisterInfo &MRI,
   for (const InsnRange &Range : Scope->getRanges()) {
     SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
     SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
 
     // At the start of each iteration I has been advanced so that
     // 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.
       I.setStopUnchecked(PrevEnd);
       ++I;
 
       // If the interval also overlaps the start of the "next" (i.e.
       // 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.
     I.advanceTo(RStart);
     if (!I.valid())
       return;
 
     if (I.start() < RStart) {
for (unsigned i = 0; i != NewRegs.size(); ++i) {
     LiveInterval::iterator LIE = LI->end();
     while (LocMapI.valid() && LII != LIE) {
       // At this point, we know that LocMapI.stop() > LII->start.
       LII = LI->advanceTo(LII, LocMapI.start());
       if (LII == LIE)
         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);
           MO.setSubReg(locations[OldLocNo].getSubReg());
           NewLocNo = getLocationNo(MO);
           DidChange = true;
         }
 
         SlotIndex LStart = LocMapI.start();
         SlotIndex LStop  = LocMapI.stop();
+        DbgValueLocation OldLoc = LocMapI.value();
 
         // Trim LocMapI down to the LII overlap.
         if (LStart < LII->start)
           LocMapI.setStartUnchecked(LII->start);
         if (LStop > LII->end)
           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;
         }
       }
 
       // Advance to the next overlap.
       if (LII->end < LocMapI.stop()) {
         if (++LII == LIE)
           break;
         LocMapI.advanceTo(LII->start);
       } else {
         ++LocMapI;
         if (!LocMapI.valid())
           break;
         LII = LI->advanceTo(LII, LocMapI.start());
       }
     }
   }
 
   // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
   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;
     }
   }
 
   DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);});
   return DidChange;
 }
 
for (auto &Pair : NewLocations) {
     }
   }
 
   // Update the interval map, but only coalesce left, since intervals to the
   // right use the old location numbers. This should merge two contiguous
   // 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());
   }
 }
 
 /// findInsertLocation - Find an iterator for inserting a DBG_VALUE
 /// instruction.
 static MachineBasicBlock::iterator
 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
   }
 
   // Don't insert anything after the first terminator, though.
   return MI->isTerminator() ? MBB->getFirstTerminator() :
                               std::next(MachineBasicBlock::iterator(MI));
 }
 
 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)
              ->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.
-  bool NewIndirect = IsIndirect || Spilled;
   const DIExpression *Expr = Expression;
-  if (Spilled && IsIndirect)
+  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);
   MIB.addMetadata(Variable).addMetadata(Expr);
 }
 
 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
                                 const TargetInstrInfo &TII,
                                 const BitVector &SpilledLocations) {
   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
 
   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
     // first instruction in the range).
     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) {
       // Move to the next block.
       Start = MBBEnd;
       if (++MBB == MFEnd)
         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)
       break;
 
     ++I;
   }
 }

llvm/trunk/test/DebugInfo/X86/dbg-addr-dse.ll

 ; ASM: movl    $2, [[OFF_X]](%rsp)
 ; ASM: callq   escape
 ; ASM: retq
 
 ; DWARF:      DW_TAG_formal_parameter
 ; DWARF-NEXT:   DW_AT_location        (0x00000000
 ; DWARF-NEXT:      {{[^:]*}}: DW_OP_breg7 RSP+{{[0-9]+}}
 ; DWARF-NEXT:      {{[^:]*}}: DW_OP_consts +1, DW_OP_stack_value
-; FIXME: Needs a fix to LiveDebugVariables
-; DWARFX-NEXT:      {{[^:]*}}: DW_OP_breg7 RSP+{{[0-9]+}})
+; DWARF-NEXT:      {{[^:]*}}: DW_OP_breg7 RSP+{{[0-9]+}})
 ; DWARF-NEXT:   DW_AT_name    ("x")
 
 attributes #0 = { nounwind uwtable }
 attributes #2 = { nounwind readnone speculatable }
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!3, !4, !5, !6}
 !llvm.ident = !{!7}

llvm/trunk/test/DebugInfo/X86/live-debug-vars-dse.mir

+# RUN: llc -start-after=machine-scheduler %s -o - | FileCheck %s
+
+# C source:
+# void escape(int *);
+# extern int global;
+# void f(int x) {
+#   escape(&x);
+#   x = 1;
+#   global = x;
+#   x = 2;
+#   escape(&x);
+# }
+
+# CHECK-LABEL: f: # @f
+# CHECK: movl    %ecx, [[OFF_X:[0-9]+]](%rsp)
+# CHECK: #DEBUG_VALUE: f:x <- [DW_OP_plus_uconst [[OFF_X]]] [%RSP+0]
+# CHECK: leaq [[OFF_X]](%rsp), %rsi
+# CHECK: callq   escape
+# CHECK: #DEBUG_VALUE: f:x <- 1
+# CHECK: movl    $1, global(%rip)
+# CHECK: #DEBUG_VALUE: f:x <- [DW_OP_plus_uconst [[OFF_X]]] [%RSP+0]
+# CHECK: movl    $2, [[OFF_X]](%rsp)
+# CHECK: callq   escape
+# CHECK: retq
+
+
+--- |
+  ; ModuleID = '<stdin>'
+  source_filename = "dse.c"
+  target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-pc-windows-msvc19.0.24215"
+  
+  @global = external global i32, align 4
+  
+  ; Function Attrs: nounwind readnone speculatable
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+  
+  declare void @escape(i32*)
+  
+  ; Function Attrs: nounwind uwtable
+  define void @f(i32 %x) #1 !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()), !dbg !14
+    call void @escape(i32* %x.addr), !dbg !15
+    call void @llvm.dbg.value(metadata i32 1, metadata !13, metadata !DIExpression()), !dbg !16
+    store i32 1, i32* @global, align 4, !dbg !17
+    call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression()), !dbg !18
+    store i32 2, i32* %x.addr, align 4, !dbg !18
+    call void @escape(i32* %x.addr), !dbg !19
+    ret void, !dbg !20
+  }
+  
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #2
+  
+  attributes #0 = { nounwind readnone speculatable }
+  attributes #1 = { nounwind uwtable }
+  attributes #2 = { nounwind }
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5, !6}
+  !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: "C:\5Csrc\5Cllvm-project\5Cbuild")
+  !2 = !{}
+  !3 = !{i32 2, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 2}
+  !6 = !{i32 7, !"PIC Level", i32 2}
+  !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, variables: !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)
+  !14 = !DILocation(line: 3, column: 12, scope: !8)
+  !15 = !DILocation(line: 4, column: 3, scope: !8)
+  !16 = !DILocation(line: 5, column: 5, scope: !8)
+  !17 = !DILocation(line: 6, column: 10, scope: !8)
+  !18 = !DILocation(line: 7, column: 5, scope: !8)
+  !19 = !DILocation(line: 8, column: 3, scope: !8)
+  !20 = !DILocation(line: 9, column: 1, scope: !8)
+
+...
+---
+name:            f
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: gr32, preferred-register: '' }
+  - { id: 1, class: gr64, preferred-register: '' }
+liveins:         
+  - { reg: '%ecx', virtual-reg: '%0' }
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    8
+  adjustsStack:    false
+  hasCalls:        true
+  stackProtector:  ''
+  maxCallFrameSize: 4294967295
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      
+stack:           
+  - { id: 0, name: x.addr, type: default, offset: 0, size: 4, alignment: 4, 
+      stack-id: 0, callee-saved-register: '', di-variable: '', di-expression: '', 
+      di-location: '' }
+constants:       
+body:             |
+  bb.0.entry:
+    liveins: %ecx
+  
+    %0 = COPY %ecx
+    MOV32mr %stack.0.x.addr, 1, _, 0, _, %0 :: (store 4 into %ir.x.addr)
+    DBG_VALUE %stack.0.x.addr, 0, !13, !DIExpression(), debug-location !14
+    ADJCALLSTACKDOWN64 32, 0, 0, implicit-def dead %rsp, implicit-def dead %eflags, implicit %rsp, debug-location !15
+    %1 = LEA64r %stack.0.x.addr, 1, _, 0, _
+    %rcx = COPY %1, debug-location !15
+    CALL64pcrel32 @escape, csr_win64, implicit %rsp, implicit %rcx, implicit-def %rsp, debug-location !15
+    ADJCALLSTACKUP64 32, 0, implicit-def dead %rsp, implicit-def dead %eflags, implicit %rsp, debug-location !15
+    DBG_VALUE 1, debug-use _, !13, !DIExpression(), debug-location !16
+    MOV32mi %rip, 1, _, @global, _, 1, debug-location !17 :: (store 4 into @global)
+    DBG_VALUE %stack.0.x.addr, 0, !13, !DIExpression(), debug-location !18
+    MOV32mi %stack.0.x.addr, 1, _, 0, _, 2, debug-location !18 :: (store 4 into %ir.x.addr)
+    ADJCALLSTACKDOWN64 32, 0, 0, implicit-def dead %rsp, implicit-def dead %eflags, implicit %rsp, debug-location !19
+    %rcx = COPY %1, debug-location !19
+    CALL64pcrel32 @escape, csr_win64, implicit %rsp, implicit %rcx, implicit-def %rsp, debug-location !19
+    ADJCALLSTACKUP64 32, 0, implicit-def dead %rsp, implicit-def dead %eflags, implicit %rsp, debug-location !19
+    RET 0, debug-location !20
+
+...