MFC r309124:

Upgrade our copies of clang, llvm, lldb, compiler-rt and libc++ to 3.9.0
release, and add lld 3.9.0.  Also completely revamp the build system for
clang, llvm, lldb and their related tools.

Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
support to build; see UPDATING for more information.

Release notes for llvm, clang and lld are available here:
<http://llvm.org/releases/3.9.0/docs/ReleaseNotes.html>
<http://llvm.org/releases/3.9.0/tools/clang/docs/ReleaseNotes.html>
<http://llvm.org/releases/3.9.0/tools/lld/docs/ReleaseNotes.html>

Thanks to Ed Maste, Bryan Drewery, Andrew Turner, Antoine Brodin and Jan
Beich for their help.

Relnotes:	yes

MFC r309147:

Pull in r282174 from upstream llvm trunk (by Krzysztof Parzyszek):

  [PPC] Set SP after loading data from stack frame, if no red zone is
  present

  Follow-up to r280705: Make sure that the SP is only restored after
  all data is loaded from the stack frame, if there is no red zone.

  This completes the fix for
  https://llvm.org/bugs/show_bug.cgi?id=26519.

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

Reported by:    Mark Millard
PR:             214433

MFC r309149:

Pull in r283060 from upstream llvm trunk (by Hal Finkel):

  [PowerPC] Refactor soft-float support, and enable PPC64 soft float

  This change enables soft-float for PowerPC64, and also makes
  soft-float disable all vector instruction sets for both 32-bit and
  64-bit modes. This latter part is necessary because the PPC backend
  canonicalizes many Altivec vector types to floating-point types, and
  so soft-float breaks scalarization support for many operations. Both
  for embedded targets and for operating-system kernels desiring
  soft-float support, it seems reasonable that disabling hardware
  floating-point also disables vector instructions (embedded targets
  without hardware floating point support are unlikely to have Altivec,
  etc. and operating system kernels desiring not to use floating-point
  registers to lower syscall cost are unlikely to want to use vector
  registers either). If someone needs this to work, we'll need to
  change the fact that we promote many Altivec operations to act on
  v4f32. To make it possible to disable Altivec when soft-float is
  enabled, hardware floating-point support needs to be expressed as a
  positive feature, like the others, and not a negative feature,
  because target features cannot have dependencies on the disabling of
  some other feature. So +soft-float has now become -hard-float.

  Fixes PR26970.

Pull in r283061 from upstream clang trunk (by Hal Finkel):

  [PowerPC] Enable soft-float for PPC64, and +soft-float -> -hard-float

  Enable soft-float support on PPC64, as the backend now supports it.
  Also, the backend now uses -hard-float instead of +soft-float, so set
  the target features accordingly.

  Fixes PR26970.

Reported by:	Mark Millard
PR:		214433

MFC r309212:

Add a few missed clang 3.9.0 files to OptionalObsoleteFiles.

MFC r309262:

Fix packaging for clang, lldb and lld 3.9.0

During the upgrade of clang/llvm etc to 3.9.0 in r309124, the PACKAGE
directive in the usr.bin/clang/*.mk files got dropped accidentally.

Restore it, with a few minor changes and additions:
* Correct license in clang.ucl to NCSA
* Add PACKAGE=clang for clang and most of the "ll" tools
* Put lldb in its own package
* Put lld in its own package

Reviewed by:	gjb, jmallett
Differential Revision: https://reviews.freebsd.org/D8666

MFC r309656:

During the bootstrap phase, when building the minimal llvm library on
PowerPC, add lib/Support/Atomic.cpp.  This is needed because upstream
llvm revision r271821 disabled the use of std::call_once, which causes
some fallback functions from Atomic.cpp to be used instead.

Reported by:	Mark Millard
PR:		214902

MFC r309835:

Tentatively apply https://reviews.llvm.org/D18730 to work around gcc PR
70528 (bogus error: constructor required before non-static data member).
This should fix buildworld with the external gcc package.

Reported by:	https://jenkins.freebsd.org/job/FreeBSD_HEAD_amd64_gcc/

MFC r310194:

Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
3.9.1 release.

Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
support to build; see UPDATING for more information.

Release notes for llvm, clang and lld will be available here:
<http://releases.llvm.org/3.9.1/docs/ReleaseNotes.html>
<http://releases.llvm.org/3.9.1/tools/clang/docs/ReleaseNotes.html>
<http://releases.llvm.org/3.9.1/tools/lld/docs/ReleaseNotes.html>

Relnotes:	yes

1 files changed, 260 insertions, 160 deletions

diff --git a/contrib/llvm/lib/CodeGen/LiveDebugValues.cpp b/contrib/llvm/lib/CodeGen/LiveDebugValues.cpp
index b9937e5..4ff88d5 100644
--- a/contrib/llvm/lib/CodeGen/LiveDebugValues.cpp
+++ b/contrib/llvm/lib/CodeGen/LiveDebugValues.cpp
@@ -18,22 +18,24 @@
 ///
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SparseBitVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/UniqueVector.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/Passes.h"
-#include "llvm/Support/CommandLine.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"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
-#include <queue>
 #include <list>
+#include <queue>
 
 using namespace llvm;
 
@@ -43,48 +45,163 @@ STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
 
 namespace {
 
+// \brief If @MI is a DBG_VALUE with debug value described by a defined
+// register, returns the number of this register. In the other case, returns 0.
+static unsigned isDbgValueDescribedByReg(const MachineInstr &MI) {
+  assert(MI.isDebugValue() && "expected a DBG_VALUE");
+  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
+  // If location of variable is described using a register (directly
+  // or indirectly), this register is always a first operand.
+  return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
+}
+
 class LiveDebugValues : public MachineFunctionPass {
 
 private:
   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 {
-      return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
+    bool operator<(const DebugVariable &DV) const {
+      if (getVar() == DV.getVar())
+        return getInlinedAt() < DV.getInlinedAt();
+      return getVar() < DV.getVar();
     }
   };
 
-  /// Member variables and functions for Range Extension across basic blocks.
+  /// A pair of debug variable and value location.
   struct VarLoc {
-    DebugVariable Var;
-    const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr.
+    const DebugVariable Var;
+    const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
+
+    enum { InvalidKind = 0, RegisterKind } Kind;
+
+    /// The value location. Stored separately to avoid repeatedly
+    /// extracting it from MI.
+    union {
+      struct {
+        uint32_t RegNo;
+        uint32_t Offset;
+      } RegisterLoc;
+      uint64_t Hash;
+    } Loc;
+
+    VarLoc(const MachineInstr &MI)
+        : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), MI(MI),
+          Kind(InvalidKind) {
+      static_assert((sizeof(Loc) == sizeof(uint64_t)),
+                    "hash does not cover all members of Loc");
+      assert(MI.isDebugValue() && "not a DBG_VALUE");
+      assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
+      if (int RegNo = isDbgValueDescribedByReg(MI)) {
+        Kind = RegisterKind;
+        Loc.RegisterLoc.RegNo = RegNo;
+        uint64_t Offset =
+            MI.isIndirectDebugValue() ? MI.getOperand(1).getImm() : 0;
+        // We don't support offsets larger than 4GiB here. They are
+        // slated to be replaced with DIExpressions anyway.
+        if (Offset >= (1ULL << 32))
+          Kind = InvalidKind;
+        else
+          Loc.RegisterLoc.Offset = Offset;
+      }
+    }
+
+    /// If this variable is described by a register, return it,
+    /// otherwise return 0.
+    unsigned isDescribedByReg() const {
+      if (Kind == RegisterKind)
+        return Loc.RegisterLoc.RegNo;
+      return 0;
+    }
 
-    VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {}
+    void dump() const { MI.dump(); }
 
-    bool operator==(const VarLoc &V) const;
+    bool operator==(const VarLoc &Other) const {
+      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;
+      return Var < Other.Var;
+    }
   };
 
-  typedef std::list<VarLoc> VarLocList;
-  typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB;
+  typedef UniqueVector<VarLoc> VarLocMap;
+  typedef SparseBitVector<> VarLocSet;
+  typedef SmallDenseMap<const MachineBasicBlock *, VarLocSet> VarLocInMBB;
+
+  /// This holds the working set of currently 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.
+  class OpenRangesSet {
+    VarLocSet VarLocs;
+    SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
+
+  public:
+    const VarLocSet &getVarLocs() const { return VarLocs; }
+
+    /// Terminate all open ranges for Var by removing it from the set.
+    void erase(DebugVariable Var) {
+      auto It = Vars.find(Var);
+      if (It != Vars.end()) {
+        unsigned ID = It->second;
+        VarLocs.reset(ID);
+        Vars.erase(It);
+      }
+    }
+
+    /// Terminate all open ranges listed in \c KillSet by removing
+    /// them from the set.
+    void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
+      VarLocs.intersectWithComplement(KillSet);
+      for (unsigned ID : KillSet)
+        Vars.erase(VarLocIDs[ID].Var);
+    }
+
+    /// Insert a new range into the set.
+    void insert(unsigned VarLocID, DebugVariableBase Var) {
+      VarLocs.set(VarLocID);
+      Vars.insert({Var, VarLocID});
+    }
+
+    /// Empty the set.
+    void clear() {
+      VarLocs.clear();
+      Vars.clear();
+    }
+
+    /// Return whether the set is empty or not.
+    bool empty() const {
+      assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
+      return VarLocs.empty();
+    }
+  };
 
-  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);
+  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
+                          VarLocMap &VarLocIDs);
+  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                           const VarLocMap &VarLocIDs);
+  bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                              VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
+  bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs);
 
-  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs);
+  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
+            const VarLocMap &VarLocIDs);
 
   bool ExtendRanges(MachineFunction &MF);
 
@@ -98,8 +215,14 @@ public:
   /// information we preserve.
   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,
+  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
+                        const VarLocMap &VarLocIDs, const char *msg,
                         raw_ostream &Out) const;
 
   /// Calculate the liveness information for the given machine function.
@@ -124,109 +247,95 @@ LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) {
 /// Tell the pass manager which passes we depend on and what information we
 /// preserve.
 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
-// \brief If @MI is a DBG_VALUE with debug value described by a defined
-// register, returns the number of this register. In the other case, returns 0.
-static unsigned isDescribedByReg(const MachineInstr &MI) {
-  assert(MI.isDebugValue());
-  assert(MI.getNumOperands() == 4);
-  // If location of variable is described using a register (directly or
-  // indirecltly), this register is always a first operand.
-  return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0;
-}
-
-// \brief This function takes two DBG_VALUE instructions and returns true
-// if their offsets are equal; otherwise returns false.
-static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) {
-  assert(MI1.isDebugValue());
-  assert(MI1.getNumOperands() == 4);
-
-  assert(MI2.isDebugValue());
-  assert(MI2.getNumOperands() == 4);
-
-  if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue())
-    return true;
-
-  // Check if both MIs are indirect and they are equal.
-  if (MI1.isIndirectDebugValue() && MI2.isIndirectDebugValue())
-    return MI1.getOperand(1).getImm() == MI2.getOperand(1).getImm();
-
-  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 VarLocMap &VarLocIDs,
+                                       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) {
-      Out << " Var: " << VLL.Var.Var->getName();
+  for (const MachineBasicBlock &BB : MF) {
+    const auto &L = V.lookup(&BB);
+    Out << "MBB: " << BB.getName() << ":\n";
+    for (unsigned VLL : L) {
+      const VarLoc &VL = VarLocIDs[VLL];
+      Out << " Var: " << VL.Var.getVar()->getName();
       Out << " MI: ";
-      (*VLL.MI).dump();
+      VL.dump();
       Out << "\n";
     }
   }
   Out << "\n";
 }
 
-bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const {
-  return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) &&
-         (areOffsetsEqual(*MI, *V.MI));
-}
-
 /// End all previous ranges related to @MI and start a new range from @MI
 /// if it is a DBG_VALUE instr.
-void LiveDebugValues::transferDebugValue(MachineInstr &MI,
-                                         VarLocList &OpenRanges) {
+void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
+                                         OpenRangesSet &OpenRanges,
+                                         VarLocMap &VarLocIDs) {
   if (!MI.isDebugValue())
     return;
-  const DILocalVariable *RawVar = MI.getDebugVariable();
-  assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
+  const DILocalVariable *Var = MI.getDebugVariable();
+  const DILocation *DebugLoc = MI.getDebugLoc();
+  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
+  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
          "Expected inlined-at fields to agree");
-  DebugVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt());
 
   // End all previous ranges of Var.
-  OpenRanges.erase(
-      std::remove_if(OpenRanges.begin(), OpenRanges.end(),
-                     [&](const VarLoc &V) { return (Var == V.Var); }),
-      OpenRanges.end());
+  DebugVariable V(Var, InlinedAt);
+  OpenRanges.erase(V);
 
-  // Add Var to OpenRanges from this DBG_VALUE.
+  // Add the VarLoc 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));
+  if (isDbgValueDescribedByReg(MI)) {
+    VarLoc VL(MI);
+    unsigned ID = VarLocIDs.insert(VL);
+    OpenRanges.insert(ID, VL.Var);
   }
 }
 
 /// A definition of a register may mark the end of a range.
 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
-                                          VarLocList &OpenRanges) {
+                                          OpenRangesSet &OpenRanges,
+                                          const VarLocMap &VarLocIDs) {
+  MachineFunction *MF = MI.getParent()->getParent();
+  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
+  unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
+  SparseBitVector<> KillSet;
   for (const MachineOperand &MO : MI.operands()) {
-    if (!(MO.isReg() && MO.isDef() && MO.getReg() &&
-          TRI->isPhysicalRegister(MO.getReg())))
-      continue;
-    // 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());
+    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)
+        for (unsigned ID : OpenRanges.getVarLocs())
+          if (VarLocIDs[ID].isDescribedByReg() == *RAI)
+            KillSet.set(ID);
+    } 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.
+      for (unsigned ID : OpenRanges.getVarLocs()) {
+        unsigned Reg = VarLocIDs[ID].isDescribedByReg();
+        if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
+          KillSet.set(ID);
+      }
+    }
   }
+  OpenRanges.erase(KillSet, VarLocIDs);
 }
 
 /// Terminate all open ranges at the end of the current basic block.
 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
-                                             VarLocList &OpenRanges,
-                                             VarLocInMBB &OutLocs) {
+                                             OpenRangesSet &OpenRanges,
+                                             VarLocInMBB &OutLocs,
+                                             const VarLocMap &VarLocIDs) {
   bool Changed = false;
   const MachineBasicBlock *CurMBB = MI.getParent();
   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
@@ -235,29 +344,23 @@ bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
   if (OpenRanges.empty())
     return false;
 
-  VarLocList &VLL = 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;
-    }
-  }
+  DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) {
+          // Copy OpenRanges to OutLocs, if not already present.
+          dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
+        });
+  VarLocSet &VLS = OutLocs[CurMBB];
+  Changed = VLS |= OpenRanges.getVarLocs();
   OpenRanges.clear();
   return Changed;
 }
 
 /// This routine creates OpenRanges and OutLocs.
-bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
-                               VarLocInMBB &OutLocs) {
+bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                               VarLocInMBB &OutLocs, VarLocMap &VarLocIDs) {
   bool Changed = false;
-  transferDebugValue(MI, OpenRanges);
-  transferRegisterDef(MI, OpenRanges);
-  Changed = transferTerminatorInst(MI, OpenRanges, OutLocs);
+  transferDebugValue(MI, OpenRanges, VarLocIDs);
+  transferRegisterDef(MI, OpenRanges, VarLocIDs);
+  Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
   return Changed;
 }
 
@@ -265,14 +368,14 @@ bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
 /// 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) {
+                           VarLocInMBB &InLocs, const VarLocMap &VarLocIDs) {
   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 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.
@@ -284,44 +387,34 @@ bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs,
       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());
+    InLocsT &= OL->second;
   }
 
   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 = InLocsT;
+  Diff.intersectWithComplement(ILS);
+  for (auto ID : 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 VarLoc &DiffIt = VarLocIDs[ID];
+    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(););
+    ILS.set(ID);
+    ++NumInserted;
+    Changed = true;
   }
   return Changed;
 }
@@ -336,21 +429,27 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   bool OLChanged = false;
   bool MBBJoined = false;
 
-  VarLocList OpenRanges; // Ranges that are open until end of bb.
+  VarLocMap VarLocIDs;   // Map VarLoc<>unique ID for use in bitvectors.
+  OpenRangesSet OpenRanges; // Ranges that are open until end of bb.
   VarLocInMBB OutLocs;   // Ranges that exist beyond bb.
   VarLocInMBB InLocs;    // Ranges that are incoming after joining.
 
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
-                      std::greater<unsigned int>> Worklist;
+                      std::greater<unsigned int>>
+      Worklist;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
-                      std::greater<unsigned int>> Pending;
+                      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()));
+      transfer(MI, OpenRanges, OutLocs, VarLocIDs);
+
+  DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization",
+                         dbgs()));
 
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   unsigned int RPONumber = 0;
@@ -360,7 +459,6 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     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.
@@ -373,21 +471,23 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     while (!Worklist.empty()) {
       MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
       Worklist.pop();
-      MBBJoined = join(*MBB, OutLocs, InLocs);
+      MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs);
 
       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()));
+          OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs);
+
+        DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
+                               "OutLocs after propagating", dbgs()));
+        DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
+                               "InLocs after propagating", dbgs()));
 
         if (OLChanged) {
           OLChanged = false;
           for (auto s : MBB->successors())
-            if (!OnPending.count(s)) {
-              OnPending.insert(s);
+            if (OnPending.insert(s).second) {
               Pending.push(BBToOrder[s]);
             }
         }
@@ -399,8 +499,8 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
     assert(Pending.empty() && "Pending should be empty");
   }
 
-  DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs()));
-  DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs()));
+  DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
+  DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
   return Changed;
 }