Fix PR26055 - LiveDebugValues is very slow

[aprantl]

Summary

This path modifies the LiveDebugValues pass to use more efficient set datastructures as outlined in https://llvm.org/bugs/show_bug.cgi?id=26055.

This original revision is Daniel's original patch.
I'll follow-up with some bug fixes on top of it soon.

[aprantl]

This fixes the remaining bugs in the original patch and adds some cleanups.

• [Correctness] The VarLoc::operator<() implementation now takes semantic equality between two VarLocs (that have different MI pointers in them) into account.
• [Correctness] Both operator<() implementations now check for equality of the first pointer before comparing the second pointer.
• In join(), I'm using an in-place llvm::set_intersect().
• [Debuggability] printVarLocInMBB() now sorts the output in BB order
• The order of the DEBUG_VALUEs is different when they come from a set, so I needed to update two of our testcases.

Before this patch, a particularly nasty ASANified testcase that I had took

user	9m20.248s

After this patch, the same testcase compiles in

user	3m12.294s

Definitely a big win! I'll look into the Bitvectors next, but I think we can also land this version of the patch meanwhile.

[llvm-commits]

Thanks for taking on this work!

I'm curious:
Does your new patch + correctness fixes take > 2 iterations to converge on
the .ll file?
(If so, something is still wrong :P)

• msg-26860-62.txt162 BDownload

[aprantl]

Good Point, and no, it doesn't converge!
In retrospect it is pretty obvious that VarLoc::getHashValue() still cannot be right. I'll fix that.

[aprantl]

Fixed VarLoc::getHashValue().

On trunk the testcase from the PR converges in 3 iterations and ~5s;
with this patch it converges in 3 iterations and ~4.8s.

[weimingz]

lib/CodeGen/LiveDebugValues.cpp

402

Can we bail out if no coverage after certain iterations?

[• dberlin]

The number of iterations should be loop depth + 3, maximum

[aprantl]

Ok, sorry, that was a bit silly on my end: The example from the PR has two functions, and I "measured" by adding a print after every Worklist.swap(Pending);
After adding a second print upon entering a new function the full printout now reads:

entering function_Z3fooRKN2cv3MatEPhRKNS_8KeyPointE
iteration completed
iteration completed
entering functionasan.module_ctor
iteration completed

So, yes, it does indeed converge after two iterations.

[• dberlin]

Awesome. That's a pretty good sign it's correct :)

[aprantl]

This version replaces the data structures with SparseBitVectors and adds a couple of further optimizations.
Apart from making the algorithm much easier to read, this now brings the ASAN example I've been primarily testing on down to just 8 seconds(!) in a NoAsserts build (while producing an identical object file :-).

Some of the optimizations I added on top are:

• VarLoc now explicitly stores the register location for faster comparisons.
• transferDebugValue no longer checks the inlinedAt field. This makes a huge difference because looking up the inline scope of a MachineInstr is quite slow. This means that we can't propagate more than one inlined copies of the same variable. IMHO this is an acceptable trade-off. Note that this only affects accuracy, not correctness.
• I experimented with many different data structures (std::list, SmallDenseMap, SmallBitVector) for VarLocList, but settled on a SparseBitVector, because it makes the InLocs |= OpenRanges operation very natural. Iterating over the set bits in a SparseBitVector can be expensive, but it doesn't seem to make much of a difference in practice.

I think this is as far as I want to go with optimizations for PR26055.
Once we add support for more differnet kinds of debug (value) locations, it might make sense to revisit this.

[• dberlin]

lib/CodeGen/LiveDebugValues.cpp

232

Errr, this seems like a regression :P
Also, if you want to float this idea, IMHO, you should split up this patch:

First, make it do the same thing with sparsebitvectors
Second, make any functionality/design changes you want on top of that.

255

Are you positive of the invalidation semantics of sparsebitvector iterators?

In particular, what happens if the reset call causes the current element to go away?
I do believe that will cause the iterator to be invalidated.

(Also, this is N^2)

269

Ditto iterator invalidation here.

You have have to make a temporary sparsebitmap and subtract it (intersectwithcomplement)

[davide]

lib/CodeGen/LiveDebugValues.cpp

51

Can you please add a message to these assertions? Thanks!

[davide]

First, let me tell you that I'm very excited about this patch. During an LTO build of medium-to-large sized C++ applications, I can clearly see this pass showing up in the profile, so I decided to benchmark it. Unfortunately, I think the patch as is introduces a regression :(

#0 0x00000000005e4398 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/davide/work/build-llvm/bin/lld+0x5e4398) 0x00000000005e1eee llvm::sys::RunSignalHandlers() (/home/davide/work/build-llvm/bin/lld+0x5e1eee)
#2 0x00000000005e2136 SignalHandler(int) (/home/davide/work/build-llvm/bin/lld+0x5e2136)
#3 0x00007f71573309f0 __restore_rt (/lib64/libpthread.so.0+0x109f0)
#4 0x000000000141867c (anonymous namespace)::LiveDebugValues::transferRegisterDef(llvm::MachineInstr&, llvm::SparseBitVector<128u>&, llvm::UniqueVector<(anonymous namespace)::LiveDebugValues::VarLoc> const&) [clone .isra.178] [clone .constprop.275] (/home/davide/work/build-llvm/bin/lld+0x141867c)
#5 0x000000000141a827 (anonymous namespace)::LiveDebugValues::ExtendRanges(llvm::MachineFunction&) [clone .constprop.265] (/home/davide/work/build-llvm/bin/lld+0x141a827)
#6 0x0000000001479b65 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/davide/work/build-llvm/bin/lld+0x1479b65)
#7 0x0000000001c3a0b2 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/davide/work/build-llvm/bin/lld+0x1c3a0b2)
#8 0x0000000001c3a41b llvm::FPPassManager::runOnModule(llvm::Module&) (/home/davide/work/build-llvm/bin/lld+0x1c3a41b)
#9 0x0000000001c39bfe llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/davide/work/build-llvm/bin/lld+0x1c39bfe)
#10 0x00000000014dae09 codegen(llvm::Module*, llvm::raw_pwrite_stream&, std::function<std::unique_ptr<llvm::TargetMachine, std::default_delete<llvm::TargetMachine> > ()>, llvm::TargetMachine::CodeGenFileType) [clone .constprop.50] (/home/davide/work/build-llvm/bin/lld+0x14dae09)
#11 0x00000000014db08a llvm::splitCodeGen(std::unique_ptr<llvm::Module, std::default_delete<llvm::Module> >, llvm::ArrayRef<llvm::raw_pwrite_stream*>, llvm::ArrayRef<llvm::raw_pwrite_stream*>, std::function<std::unique_ptr<llvm::TargetMachine, std::default_delete<llvm::TargetMachine> > ()> const&, llvm::TargetMachine::CodeGenFileType, bool) (/home/davide/work/build-llvm/bin/lld+0x14db08a)
#12 0x00000000005bb240 lld::elf::BitcodeCompiler::runSplitCodegen(std::function<std::unique_ptr<llvm::TargetMachine, std::default_delete<llvm::TargetMachine> > ()> const&) (/home/davide/work/build-llvm/bin/lld+0x5bb240)
#13 0x00000000005bc827 lld::elf::BitcodeCompiler::compile() (/home/davide/work/build-llvm/bin/lld+0x5bc827)
#14 0x000000000057ab45 lld::elf::SymbolTable<llvm::object::ELFType<(llvm::support::endianness)1, true> >::addCombinedLtoObject() (/home/davide/work/build-llvm/bin/lld+0x57ab45)
#15 0x00000000004ecfb8 void lld::elf::LinkerDriver::link<llvm::object::ELFType<(llvm::support::endianness)1, true> >(llvm::opt::InputArgList&) (/home/davide/work/build-llvm/bin/lld+0x4ecfb8)
#16 0x000000000044e7ec lld::elf::LinkerDriver::main(llvm::ArrayRef<char const*>) (/home/davide/work/build-llvm/bin/lld+0x44e7ec)
#17 0x00000000004eefbe lld::elf::link(llvm::ArrayRef<char const*>, llvm::raw_ostream&, bool) (/home/davide/work/build-llvm/bin/lld+0x4eefbe)
#18 0x000000000044dce7 main (/home/davide/work/build-llvm/bin/lld+0x44dce7)
#19 0x00007f71564ce580 __libc_start_main (/lib64/libc.so.6+0x20580)
#20 0x00000000004a03b9 _start (/home/davide/work/build-llvm/bin/lld+0x4a03b9)
Stack dump:
0.      Program arguments:
1.      Running pass 'Function Pass Manager' on module 'ld-temp.o'.
2.      Running pass 'Live DEBUG_VALUE analysis' on function '@_Z10iPPc'

I have limited time next week, but I'll try anyway to reduce a test case for you ASAP.

[• dberlin]

My guess is you have a case where the iterator invalidation causes it to
crash :)

[• dberlin]

lib/CodeGen/LiveDebugValues.cpp

255

One way to solve the invalidation problem, other than creating a separate bitvector, would be to not use the auto loop, but instead to always move the iterator forward and erase behind the iterator.

Two, you can solve the O(N^2)-ness a few ways (it's really worse, but let's just deal with the part going over the open ranges):

A simple way -

Form a bitvector out of this:

for (const MachineOperand &MO : MI.operands()) {
   if (MO.isReg() && MO.isDef() && MO.getReg() &&
       TRI->isPhysicalRegister(MO.getReg())) {
     // Remove ranges of all aliased registers.
     for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
         <set bit for *RAI here>

Then take this loop:

for (unsigned ID : OpenRanges)
  if (VarLocIDs[ID].isDescribedByReg() == *RAI)

and do the tests against the bitvector instead (ie test the bit VarLocIDs[ID].isDescribedByReg())
This will only process each range once instead of process each range for every operand :)

This is essentially splitting it into:

1. Figure out which registers the machine instruction affects
2. Test which open ranges they affect

You can do things that are more complicated if this part gets slow.

269

You could also just move the iterator ahead of doing the reset.

[aprantl]

To establish a useful basis for discussion and further optimization, here is an NFC patch (no dropping of inlined copies) that also fixes the iterator invalidation problem noted by Daniel and reported by Davide.

I'm now going to look into Daniel's suggestions about improving the O(n^2) inner loops. Thanks!

[• dberlin]

Note: If the time bound on the version with N^2 inner loops is beyond what
you want to do, happy to review the patch as-is and get it in, and we can
just drop a comment about further improvement

[aprantl]

In D20178#431100, @dberlin wrote:

Note: If the time bound on the version with N^2 inner loops is beyond what
you want to do, happy to review the patch as-is and get it in, and we can
just drop a comment about further improvement

Thanks, I think it would be a good idea to make a cut here and land this revision in trunk as an intermediate step so we can use it as a basis for further improvements!

I'll keep working on it, but doing so takes time, and I keep getting distracted by other things.

As for my progress: I'm done with my first iteration of rewriting transferRegisterDef() and it had almost no effect on my benchmark. This is because in my benchmark none of the variables survive the first basic block, which explains why I couldn't measure any improvements. I'll need to find a better benchmark to profile my bitvectorized transferRegisterDef() implementation.

So where are the remaining 2 minutes spent? With some more profiling I figured that most of the time is spent in transferDebugValue(). In my benchmark OpenRanges has >5000 elements (mostly from inlined C++ one-liners) so linearly iterating over all of them for every DEBUG_VALUE is very expensive. My idea is to exploit the sorted-ness of the map in the UniqueVector to only iterate over only over the elements that share the same DebugVariable.

I'll post a separate review once I've got something presentable.

[mgrang]

lib/CodeGen/LiveDebugValues.cpp

25

Includes should be alphabetically ordered:

#include "llvm/ADT/SparseBitVector.h" should come before #include "llvm/ADT/Statistic.h"

[• dberlin]

LGTM

lib/CodeGen/LiveDebugValues.cpp

54

Nit: indirectly

97

Errr, do you really never use the hash and the registerloc at the same time?

[aprantl]

lib/CodeGen/LiveDebugValues.cpp

97

The hash is meant to be a convenient alternative view of the the two uint32_t as a single uint64_t. Now that I think of it, I wonder whether that is guaranteed on all imaginable architectures.

[• dberlin]

Yeah, i honestly don't know.
It's a need way to avoid constructing a real hash, my next question would
be "is it actually demonstrably slower to compute a hash for real"?

Also, since the stuff is constant anyway, can't you just compute it at init
time anyway?
It's not like you have to compute it repeatedly.

[aprantl]

Thanks! I landed an updated version that includes all open suggestions in r270776.

[aprantl]

This can be closed now.

lib/CodeGen/LiveDebugValues.cpp

 /// inserted.
 ///
 /// This is a separate pass from DbgValueHistoryCalculator to facilitate
 /// testing and improve modularity.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"

 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
 
 namespace {
 
 class LiveDebugValues : public MachineFunctionPass {
 
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
 
   typedef std::pair<const DILocalVariable *, const DILocation *>
       InlinedVariable;
 
   /// A potentially inlined instance of a variable.
   struct DebugVariable {
     const DILocalVariable *Var;
     const DILocation *InlinedAt;
 
     DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
         : Var(_var), InlinedAt(_inlinedAt) {}
 
+    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);
     }
+
+    static unsigned getHashValue(const DebugVariable &DV) {
+      return hash_combine(DV.Var, DV.InlinedAt);
+    }
   };
 
   /// Member variables and functions for Range Extension across basic blocks.
   struct VarLoc {
     DebugVariable Var;
     const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr.
 
     VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
 
     bool operator==(const VarLoc &V) const;
+    bool operator<(const VarLoc &V) const {
+      if (*this == V)
+        return false;
+      if (Var == V.Var)
+        return MI < V.MI;
+      return Var < V.Var;
+    }
+
+    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);
   bool transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges,
                               VarLocInMBB &OutLocs);
   bool transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs);
 
   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
public:
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::AllVRegsAllocated);
   }
 
   /// Print to ostream with a message.
-  void printVarLocInMBB(const VarLocInMBB &V, const char *msg,
-                        raw_ostream &Out) const;
+  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
+                        const char *msg, raw_ostream &Out) const;
 
   /// Calculate the liveness information for the given machine function.
   bool runOnMachineFunction(MachineFunction &MF) override;
 };
 } // namespace
 
 //===----------------------------------------------------------------------===//
 //            Implementation
static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) {
 
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
 
-void LiveDebugValues::printVarLocInMBB(const VarLocInMBB &V, const char *msg,
+void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
+                                       const VarLocInMBB &V, const char *msg,
                                        raw_ostream &Out) const {
-  Out << "Printing " << msg << ":\n";
-  for (const auto &L : V) {
-    Out << "MBB: " << L.first->getName() << ":\n";
-    for (const auto &VLL : L.second) {
+  for (const MachineBasicBlock &BB : MF) {
+    const auto &L = V.lookup(&BB);
+    Out << "MBB: " << BB.getName() << ":\n";
+    for (const auto &VLL : L) {
       Out << " Var: " << VLL.Var.Var->getName();
       Out << " MI: ";
       (*VLL.MI).dump();
       Out << "\n";
     }
   }
   Out << "\n";
 }
void LiveDebugValues::transferDebugValue(MachineInstr &MI,
   OpenRanges.erase(
       std::remove_if(OpenRanges.begin(), OpenRanges.end(),
                      [&](const VarLoc &V) { return (Var == V.Var); }),
       OpenRanges.end());
 
   // Add Var to OpenRanges from this DBG_VALUE.
   // TODO: Currently handles DBG_VALUE which has only reg as location.
   if (isDescribedByReg(MI)) {
     VarLoc V(Var, &MI);
     OpenRanges.push_back(std::move(V));
   }
 }
 
 /// A definition of a register may mark the end of a range.
 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
                                           VarLocList &OpenRanges) {
   MachineFunction *MF = MI.getParent()->getParent();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
   for (const MachineOperand &MO : MI.operands()) {
     if (MO.isReg() && MO.isDef() && MO.getReg() &&
         TRI->isPhysicalRegister(MO.getReg())) {
       // Remove ranges of all aliased registers.
       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
         OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(),
                                         [&](const VarLoc &V) {
                                           return (*RAI ==
                                                   isDescribedByReg(*V.MI));
                                         }),
                          OpenRanges.end());
     } else if (MO.isRegMask()) {
       // Remove ranges of all clobbered registers. Register masks don't usually
       // 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.
       OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(),
                                       [&](const VarLoc &V) {
                                         unsigned Reg = isDescribedByReg(*V.MI);
                                         return Reg && Reg != SP &&
                                                MO.clobbersPhysReg(Reg);
                                       }),
                        OpenRanges.end());
     }
   }
 }
 
 /// Terminate all open ranges at the end of the current basic block.
 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
                                              VarLocList &OpenRanges,
                                              VarLocInMBB &OutLocs) {
   bool Changed = false;
   const MachineBasicBlock *CurMBB = MI.getParent();
   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
     return false;
 
   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;
 }
 
 /// This routine creates OpenRanges and OutLocs.
 bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
                                VarLocInMBB &OutLocs) {
   bool Changed = false;
   transferDebugValue(MI, OpenRanges);
   transferRegisterDef(MI, OpenRanges);
   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs);
   return Changed;
 }
 
 /// This routine joins the analysis results of all incoming edges in @MBB by
 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
 /// source variable in all the predecessors of @MBB reside in the same location.
 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
                            VarLocInMBB &InLocs) {
   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.
   for (auto p : MBB.predecessors()) {
     auto OL = OutLocs.find(p);
     // Join is null in case of empty OutLocs from any of the pred.
     if (OL == OutLocs.end())
       return false;
 
     // Just copy over the Out locs to incoming locs for the first predecessor.
     if (p == *MBB.pred_begin()) {
       InLocsT = OL->second;
       continue;
     }
-
     // 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_intersect(InLocsT, VLS);
   }
 
   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) {
+    // new range is started for the var from the mbb's beginning by
+    // inserting
+    const MachineInstr *DMI = DiffIt.MI;
+    VarLoc V(DiffIt.Var, MI);
+    ILS.insert(std::move(V));
   }
   return Changed;
 }
 
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>> Worklist;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>> Pending;
   // Initialize every mbb with OutLocs.
   for (auto &MBB : MF)
     for (auto &MI : MBB)
       transfer(MI, OpenRanges, OutLocs);
-  DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs()));
+  DEBUG(printVarLocInMBB(MF, OutLocs, "OutLocs after initialization", dbgs()));
 
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   unsigned int RPONumber = 0;
   for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
     OrderToBB[RPONumber] = *RI;
     BBToOrder[*RI] = RPONumber;
     Worklist.push(RPONumber);
     ++RPONumber;
   }
 
   // This is a standard "union of predecessor outs" dataflow problem.
   // To solve it, we perform join() and transfer() using the two worklist method
   // until the ranges converge.
   // Ranges have converged when both worklists are empty.
   while (!Worklist.empty() || !Pending.empty()) {
     // We track what is on the pending worklist to avoid inserting the same
     // thing twice.  We could avoid this with a custom priority queue, but this
     // is probably not worth it.
     SmallPtrSet<MachineBasicBlock *, 16> OnPending;
     while (!Worklist.empty()) {
       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
       Worklist.pop();
       MBBJoined = join(*MBB, OutLocs, InLocs);
 
       if (MBBJoined) {
         MBBJoined = false;
         Changed = true;
         for (auto &MI : *MBB)
           OLChanged |= transfer(MI, OpenRanges, OutLocs);
-        DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs()));
-        DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs()));
+        DEBUG(printVarLocInMBB(MF, OutLocs, "OutLocs after propagating", dbgs()));
+        DEBUG(printVarLocInMBB(MF, InLocs, "InLocs after propagating", dbgs()));
 
         if (OLChanged) {
           OLChanged = false;
           for (auto s : MBB->successors())
             if (!OnPending.count(s)) {
               OnPending.insert(s);
               Pending.push(BBToOrder[s]);
             }
         }
       }
     }
     Worklist.swap(Pending);
     // At this point, pending must be empty, since it was just the empty
     // worklist
     assert(Pending.empty() && "Pending should be empty");
   }
 
-  DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
-  DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
+  DEBUG(printVarLocInMBB(MF, OutLocs, "Final OutLocs", dbgs()));
+  DEBUG(printVarLocInMBB(MF, InLocs, "Final InLocs", dbgs()));
   return Changed;
 }
 
 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
 
   bool Changed = false;
 
   Changed |= ExtendRanges(MF);
 
   return Changed;
 }

test/DebugInfo/COFF/register-variables.ll

 ; ASM:         callq   getint
 ; ASM: [[after_getint:\.Ltmp.*]]:
 ; ASM:         #DEBUG_VALUE: a <- %EAX
 ; ASM:         #DEBUG_VALUE: inlineinc:a <- %EAX
 ; ASM:         #DEBUG_VALUE: c <- %EAX
 ; ASM:         testl   %esi, %esi
 ; ASM:         je      .LBB0_2
 ; ASM: # BB#1:                                 # %if.then
-; ASM:         #DEBUG_VALUE: c <- %EAX
-; ASM:         #DEBUG_VALUE: inlineinc:a <- %EAX
-; ASM:         #DEBUG_VALUE: a <- %EAX
-; ASM:         #DEBUG_VALUE: f:p <- %ESI
+; ASM-DAG:     #DEBUG_VALUE: c <- %EAX
+; ASM-DAG:     #DEBUG_VALUE: inlineinc:a <- %EAX
+; ASM-DAG:     #DEBUG_VALUE: a <- %EAX
+; ASM-DAG:     #DEBUG_VALUE: f:p <- %ESI
 ; ASM:         incl    %eax
 ; ASM: [[after_inc_eax:\.Ltmp.*]]:
 ; ASM:         #DEBUG_VALUE: inlineinc:b <- %EAX
 ; ASM:         #DEBUG_VALUE: b <- %EAX
 ; ASM:         incl    x(%rip)
 ; ASM: [[after_if:\.Ltmp.*]]:
 ; ASM: .LBB0_2:                                # %if.else
 ; ASM:         #DEBUG_VALUE: f:p <- %ESI

test/DebugInfo/MIR/X86/live-debug-values-3preds.mir

 #  return a;
 # }
 # with clang -g -O1 -c -emit-llvm LiveDebugValues-3preds.c -S -o live-debug-values-3preds.ll
 # then llc -stop-after stackmap-liveness live-debug-values-3preds.ll -o /dev/null > live-debug-values-3preds.mir
 
 # DBG_VALUE for variables "x", "y" and "z" are extended into BB#9 from its
 # predecessors BB#0, BB#2 and BB#8.
 # CHECK:      bb.9.for.end:
-# CHECK:      DBG_VALUE debug-use %edx, debug-use _, !13, !16, debug-location !20
-# CHECK-NEXT: DBG_VALUE debug-use %esi, debug-use _, !12, !16, debug-location !18
-# CHECK-NEXT: DBG_VALUE debug-use %edi, debug-use _, !11, !16, debug-location !17
-
+# CHECK-DAG:  DBG_VALUE debug-use %edi, debug-use _, !11, !16, debug-location !17
+# CHECK-DAG:  DBG_VALUE debug-use %edx, debug-use _, !13, !16, debug-location !20
+# CHECK-DAG:  DBG_VALUE debug-use %esi, debug-use _, !12, !16, debug-location !18
+# CHECK:      RET
 
 --- |
   ; ModuleID = 'live-debug-values-3preds.ll'
   target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-unknown-linux-gnu"
   
   ; Function Attrs: norecurse nounwind readnone uwtable
   define i32 @add(i32 %x, i32 %y, i32 %z, i32 %a) #0 !dbg !4 {