Index: lib/CodeGen/LiveDebugValues.cpp
===================================================================
--- lib/CodeGen/LiveDebugValues.cpp
+++ lib/CodeGen/LiveDebugValues.cpp
@@ -60,9 +60,18 @@
     DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
         : Var(_var), InlinedAt(_inlinedAt) {}
 
+    bool operator<(const DebugVariable &DV) const {
+      if (Var < DV.Var)
+        return true;
+      return InlinedAt < DV.InlinedAt;
+    }
+
     bool operator==(const DebugVariable &DV) const {
       return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
     }
+    static unsigned getHashValue(const DebugVariable &DV) {
+      return hash_combine(DV.Var, DV.InlinedAt);
+    }
   };
 
   /// Member variables and functions for Range Extension across basic blocks.
@@ -73,10 +82,20 @@
     VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
 
     bool operator==(const VarLoc &V) const;
+    bool operator<(const VarLoc &V) const {
+      if (Var < V.Var)
+        return true;
+      return MI < V.MI;
+    }
+
+    static unsigned getHashValue(const VarLoc &V) {
+      return hash_combine(V.Var.getHashValue(V.Var), V.MI);
+    }
   };
 
   typedef std::list<VarLoc> VarLocList;
-  typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
+  typedef std::set<VarLoc> VarLocSet;
+  typedef SmallDenseMap<const MachineBasicBlock *, VarLocSet> VarLocInMBB;
 
   void transferDebugValue(MachineInstr &MI, VarLocList &OpenRanges);
   void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges);
@@ -235,17 +254,14 @@
   if (OpenRanges.empty())
     return false;
 
-  VarLocList &VLL = OutLocs[CurMBB];
+  VarLocSet &VLS = OutLocs[CurMBB];
 
   for (auto OR : OpenRanges) {
     // Copy OpenRanges to OutLocs, if not already present.
     assert(OR.MI->isDebugValue());
     DEBUG(dbgs() << "Add to OutLocs: "; OR.MI->dump(););
-    if (std::find_if(VLL.begin(), VLL.end(),
-                     [&](const VarLoc &V) { return (OR == V); }) == VLL.end()) {
-      VLL.push_back(std::move(OR));
-      Changed = true;
-    }
+    auto result = VLS.insert(std::move(OR));
+    Changed |= result.second;
   }
   OpenRanges.clear();
   return Changed;
@@ -269,7 +285,7 @@
   DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n");
   bool Changed = false;
 
-  VarLocList InLocsT; // Temporary incoming locations.
+  VarLocSet InLocsT; // Temporary incoming locations.
 
   // For all predecessors of this MBB, find the set of VarLocs that can be
   // joined.
@@ -286,42 +302,37 @@
     }
 
     // Join with this predecessor.
-    VarLocList &VLL = OL->second;
-    InLocsT.erase(
-        std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) {
-          return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) {
-                    return (ILT == V);
-                  }) == VLL.end());
-        }), InLocsT.end());
+    VarLocSet &VLS = OL->second;
+    set_intersection(VLS.begin(), VLS.end(), InLocsT.begin(), InLocsT.end(),
+                     inserter(InLocsT, InLocsT.end()));
   }
 
   if (InLocsT.empty())
     return false;
 
-  VarLocList &ILL = InLocs[&MBB];
+  VarLocSet &ILS = InLocs[&MBB];
 
   // Insert DBG_VALUE instructions, if not already inserted.
-  for (auto ILT : InLocsT) {
-    if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) {
-          return (ILT == I);
-        }) == ILL.end()) {
-      // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
-      // new range is started for the var from the mbb's beginning by inserting
-      // a new DBG_VALUE. transfer() will end this range however appropriate.
-      const MachineInstr *DMI = ILT.MI;
-      MachineInstr *MI =
-          BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
-                  DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0,
-                  DMI->getDebugVariable(), DMI->getDebugExpression());
-      if (DMI->isIndirectDebugValue())
-        MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
-      DEBUG(dbgs() << "Inserted: "; MI->dump(););
-      ++NumInserted;
-      Changed = true;
-
-      VarLoc V(ILT.Var, MI);
-      ILL.push_back(std::move(V));
-    }
+  VarLocSet Diff;
+  std::set_difference(InLocsT.begin(), InLocsT.end(), ILS.begin(), ILS.end(),
+                      inserter(Diff, Diff.end()));
+  for (auto DiffIt : Diff) {
+    // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a
+    // new range is started for the var from the mbb's beginning by inserting
+    // a new DBG_VALUE. transfer() will end this range however appropriate.
+    const MachineInstr *DMI = DiffIt.MI;
+    MachineInstr *MI =
+        BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(),
+                DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0,
+                DMI->getDebugVariable(), DMI->getDebugExpression());
+    if (DMI->isIndirectDebugValue())
+      MI->getOperand(1).setImm(DMI->getOperand(1).getImm());
+    DEBUG(dbgs() << "Inserted: "; MI->dump(););
+    ++NumInserted;
+    Changed = true;
+
+    VarLoc V(DiffIt.Var, MI);
+    ILS.insert(std::move(V));
   }
   return Changed;
 }