Index: lib/CodeGen/LiveDebugValues.cpp
===================================================================
--- lib/CodeGen/LiveDebugValues.cpp
+++ lib/CodeGen/LiveDebugValues.cpp
@@ -61,25 +61,21 @@
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
 
+  /// Based on std::pair so it can be used as an index into a DenseMap.
   typedef std::pair<const DILocalVariable *, const DILocation *>
-      InlinedVariable;
-
+      DebugVariableBase;
   /// A potentially inlined instance of a variable.
-  struct DebugVariable {
-    const DILocalVariable *Var;
-    const DILocation *InlinedAt;
+  struct DebugVariable : public DebugVariableBase {
+    DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
+        : DebugVariableBase(Var, InlinedAt) {}
 
-    DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
-        : Var(_var), InlinedAt(_inlinedAt) {}
+    const DILocalVariable *getVar() const { return this->first; };
+    const DILocation *getInlinedAt() const { return this->second; };
 
     bool operator<(const DebugVariable &DV) const {
-      if (Var == DV.Var)
-        return InlinedAt < DV.InlinedAt;
-      return Var < DV.Var;
-    }
-
-    bool operator==(const DebugVariable &DV) const {
-      return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
+      if (getVar() == DV.getVar())
+        return getInlinedAt() < DV.getInlinedAt();
+      return getVar() < DV.getVar();
     }
   };
 
@@ -136,6 +132,7 @@
       return Var == Other.Var && Loc.Hash == Other.Loc.Hash;
     }
 
+    /// This operator guarantees that VarLocs are sorted by Variable first.
     bool operator<(const VarLoc &Other) const {
       if (Var == Other.Var)
         return Loc.Hash < Other.Loc.Hash;
@@ -144,10 +141,22 @@
   };
 
   typedef UniqueVector<VarLoc> VarLocMap;
-  typedef SparseBitVector<> VarLocList;
   typedef SparseBitVector<> VarLocSet;
   typedef SmallDenseMap<const MachineBasicBlock *, VarLocSet> VarLocInMBB;
 
+  /// This holds the working set of open ranges. For fast access, this
+  /// is done both as a set of VarLocIDs, and a map of DebugVariable
+  /// to recent VarLocID. Note that a DBG_VALUE ends all previous open
+  /// ranges for the same variable.
+  struct VarLocList {
+    VarLocSet VarLocs;
+    SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
+    void clear() {
+      VarLocs.clear();
+      Vars.clear();
+    }
+  };
+
   void transferDebugValue(const MachineInstr &MI, VarLocList &OpenRanges,
                           VarLocMap &VarLocIDs);
   void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges,
@@ -221,7 +230,7 @@
     Out << "MBB: " << BB.getName() << ":\n";
     for (unsigned VLL : L) {
       const VarLoc &VL = VarLocIDs[VLL];
-      Out << " Var: " << VL.Var.Var->getName();
+      Out << " Var: " << VL.Var.getVar()->getName();
       Out << " MI: ";
       VL.dump();
       Out << "\n";
@@ -244,18 +253,22 @@
          "Expected inlined-at fields to agree");
 
   // End all previous ranges of Var.
-  SparseBitVector<> KillSet;
-  for (unsigned ID : OpenRanges) {
-    auto &ORVar = VarLocIDs[ID].Var;
-    if (ORVar.Var == Var && ORVar.InlinedAt == InlinedAt)
-      KillSet.set(ID);
+  VarLocSet KillSet;
+  DebugVariable V(Var, InlinedAt);
+  auto OR = OpenRanges.Vars.find(V);
+  if (OR != OpenRanges.Vars.end()) {
+    unsigned ID = OR->second;
+    OpenRanges.Vars.erase(OR);
+    OpenRanges.VarLocs.reset(ID);
   }
-  OpenRanges.intersectWithComplement(KillSet);
-
   // Add the VarLoc to OpenRanges from this DBG_VALUE.
   // TODO: Currently handles DBG_VALUE which has only reg as location.
-  if (isDescribedByReg(MI))
-    OpenRanges.set(VarLocIDs.insert(MI));
+  if (isDescribedByReg(MI)) {
+    VarLoc VL(MI);
+    unsigned ID = VarLocIDs.insert(VL);
+    OpenRanges.VarLocs.set(ID);
+    OpenRanges.Vars.insert({VL.Var, ID});
+  }
 }
 
 /// A definition of a register may mark the end of a range.
@@ -271,7 +284,7 @@
         TRI->isPhysicalRegister(MO.getReg())) {
       // Remove ranges of all aliased registers.
       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
-        for (unsigned ID : OpenRanges)
+        for (unsigned ID : OpenRanges.VarLocs)
           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
             KillSet.set(ID);
     } else if (MO.isRegMask()) {
@@ -279,14 +292,16 @@
       // list SP as preserved.  While the debug info may be off for an
       // instruction or two around callee-cleanup calls, transferring the
       // DEBUG_VALUE across the call is still a better user experience.
-      for (unsigned ID : OpenRanges) {
+      for (unsigned ID : OpenRanges.VarLocs) {
         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
           KillSet.set(ID);
       }
     }
   }
-  OpenRanges.intersectWithComplement(KillSet);
+  OpenRanges.VarLocs.intersectWithComplement(KillSet);
+  for (unsigned ID : KillSet)
+    OpenRanges.Vars.erase(VarLocIDs[ID].Var);
 }
 
 /// Terminate all open ranges at the end of the current basic block.
@@ -299,15 +314,15 @@
   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
     return false;
 
-  if (OpenRanges.empty())
+  if (OpenRanges.VarLocs.empty())
     return false;
 
-  DEBUG(for (unsigned ID : OpenRanges) {
+  DEBUG(for (unsigned ID : OpenRanges.VarLocs) {
           // Copy OpenRanges to OutLocs, if not already present.
           dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
         });
   VarLocSet &VLS = OutLocs[CurMBB];
-  Changed = VLS |= OpenRanges;
+  Changed = VLS |= OpenRanges.VarLocs;
   OpenRanges.clear();
   return Changed;
 }