[LiveDebugValues] Encode a location in VarLoc IDs, NFC [2/3]

[vsk]

Summary

This is part 2 of a 3-part series to address a compile-time explosion
issue in LiveDebugValues.

---

Each VarLoc has a unique ID: this ID is used to look up a VarLoc in the
VarLocMap, and to virtually insert a VarLoc into a VarLocSet. Instead of
inserting the VarLoc /itself/ into the VarLocSet, we insert just the ID,
because this can be represented efficiently with a SparseBitVector.

This change introduces LocIndex, a layer of abstraction on top of VarLoc
IDs. Prior to this change, an ID was just an index into a vector. With
this change, an ID encodes both an index /and/ a register location. The
type-checker ensures that conversions to and from LocIndex are correct.

For the moment the register location is always 0 (undef). We have plenty
of bits left over to encode physregs, stack slots, and other locations
in the future.

Loosely depends on: https://reviews.llvm.org/D74984

[vsk]

Back out changes accidentally introduced in a rebase.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

118

Should we write this as an adaptor/wrapper of SparseBitVector instead?
I'm fine with "no" as an answer.

133

Out of curiosity: This data structure looks like a hand-written implementation of union { uint64_t ; struct {int32_t; int32_t}} are there some UB-related problems with doing just that?

436–447

If it's has methods, it gets a doxygen comment :-)

452

Nit: ///< or the comments must come before the decl.

[probinson]

llvm/lib/CodeGen/LiveDebugValues.cpp

133

(Drive-by comment) There are definitely endian-ness problems with a simple union.

[vsk]

llvm/lib/CodeGen/LiveDebugValues.cpp

118

I'm not sure I follow, sorry. Do you mean, should we be writing for (LocIndex LI : someVarLocSet), where someVarLocSet is a wrapper around a bitvector that allows iteration over LocIndex? I'm inclined to say 'no', as working with the wrapper to set operations and the like might be messier than converting to/from LocIndex.

133

My intention in writing out the left shift explicitly is to make it clear to readers that "Location" lives in the high bits. This isn't clear to me when this is written as a union. There could be weird effects with endianness as Paul points out.

436–447

Ouch, I accidentally squashed the change to add doxygen comments to VarLocMap into D74986. Is it all right if I land the change there? Splitting the commit apart is a pain.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

436–447

Sure. Just FYI, you can use a mixture of git reset HEAD~1 (un-commit changes) and git add -p (selectively add changes to commit) to move lines from one commit to another.

llvm/lib/CodeGen/LiveDebugValues.cpp

static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
 
   return Reg && Reg != SP && Reg != FP;
 }
 
 namespace {
 
 using DefinedRegsSet = SmallSet<Register, 32>;
 
+/// A type-checked pair of {Register Location (or 0), Index}, used to index
+/// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
+/// for insertion into a \ref VarLocSet, and efficiently converted back. The
+/// type-checker helps ensure that the conversions aren't lossy.
+///
+/// Why encode a location /into/ the VarLocMap index? This makes it possible
+/// to find the open VarLocs killed by a register def very quickly. This is a
+/// performance-critical operation for LiveDebugValues.
+struct LocIndex {
+  uint32_t Location; // Physical registers live in the range [1;2^30) (see
+                     // \ref MCRegister), so we have plenty of range left here
+                     // to encode non-register locations.
+  uint32_t Index;
+
+  LocIndex(uint32_t Location, uint32_t Index)
+      : Location(Location), Index(Index) {}
+
+  uint64_t getAsRawInteger() const {
+    return (static_cast<uint64_t>(Location) << 32) | Index;
+  }
+
+  static LocIndex fromRawInteger(uint64_t ID) {
+    return {static_cast<uint32_t>(ID >> 32), static_cast<uint32_t>(ID)};
+  }
+};
+
 class LiveDebugValues : public MachineFunctionPass {
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
 
#endif
 
     /// This operator guarantees that VarLocs are sorted by Variable first.
     bool operator<(const VarLoc &Other) const {
       return std::tie(Var, Kind, Loc.Hash, Expr) <
              std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr);
     }
   };
 
-  using VarLocMap = UniqueVector<VarLoc>;
+  class VarLocMap {
+    UniqueVector<VarLoc> VarLocs;
+
+  public:
+    LocIndex insert(const VarLoc &VL) {
+      uint32_t Index = VarLocs.insert(VL);
+      return {0, Index};
+    }
+
+    const VarLoc &operator[](LocIndex ID) const { return VarLocs[ID.Index]; }
+  };
+
   using VarLocSet = SparseBitVector<>;
   using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
   struct TransferDebugPair {
     MachineInstr *TransferInst; /// Instruction where this transfer occurs.
-    unsigned LocationID;        /// Location number for the transfer dest.
+    LocIndex LocationID;        /// Location number for the transfer dest.
   };
   using TransferMap = SmallVector<TransferDebugPair, 4>;
 
   // Types for recording sets of variable fragments that overlap. For a given
   // local variable, we record all other fragments of that variable that could
   // overlap it, to reduce search time.
   using FragmentOfVar =
       std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
#endif
   /// two different maps (Vars/EntryValuesBackupVars), so erase/insert
   /// methods act differently depending on whether a VarLoc is primary
   /// location or backup one. In the case the VarLoc is backup location
   /// we will erase/insert from the EntryValuesBackupVars map, otherwise
   /// we perform the operation on the Vars.
   class OpenRangesSet {
     VarLocSet VarLocs;
     // Map the DebugVariable to recent primary location ID.
-    SmallDenseMap<DebugVariable, unsigned, 8> Vars;
+    SmallDenseMap<DebugVariable, LocIndex, 8> Vars;
     // Map the DebugVariable to recent backup location ID.
-    SmallDenseMap<DebugVariable, unsigned, 8> EntryValuesBackupVars;
+    SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars;
     OverlapMap &OverlappingFragments;
 
   public:
     OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {}
 
     const VarLocSet &getVarLocs() const { return VarLocs; }
 
     /// Terminate all open ranges for VL.Var by removing it from the set.
     void erase(const VarLoc &VL);
 
     /// Terminate all open ranges listed in \c KillSet by removing
     /// them from the set.
     void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs);
 
     /// Insert a new range into the set.
-    void insert(unsigned VarLocID, const VarLoc &VL);
+    void insert(LocIndex VarLocID, const VarLoc &VL);
 
     /// Insert a set of ranges.
     void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) {
-      for (unsigned Id : ToLoad) {
-        const VarLoc &VarL = Map[Id];
-        insert(Id, VarL);
+      for (uint64_t ID : ToLoad) {
+        LocIndex Idx = LocIndex::fromRawInteger(ID);
+        const VarLoc &VarL = Map[Idx];
+        insert(Idx, VarL);
       }
     }
 
-    llvm::Optional<unsigned> getEntryValueBackup(DebugVariable Var);
+    llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var);
 
     /// Empty the set.
     void clear() {
       VarLocs.clear();
       Vars.clear();
       EntryValuesBackupVars.clear();
     }
 
#endif
   Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
                                                   MachineFunction *MF,
                                                   unsigned &Reg);
   /// Given a spill instruction, extract the register and offset used to
   /// address the spill location in a target independent way.
   VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
   void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                TransferMap &Transfers, VarLocMap &VarLocIDs,
-                               unsigned OldVarID, TransferKind Kind,
+                               LocIndex OldVarID, TransferKind Kind,
                                unsigned NewReg = 0);
 
   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                           VarLocMap &VarLocIDs);
   void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                   VarLocMap &VarLocIDs, TransferMap &Transfers);
   bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                         VarLocMap &VarLocIDs, const VarLoc &EntryVL);

 /// tracking its backup entry location. Otherwise, if the VarLoc is primary
 /// location, erase the variable from the Vars set.
 void LiveDebugValues::OpenRangesSet::erase(const VarLoc &VL) {
   // Erasure helper.
   auto DoErase = [VL, this](DebugVariable VarToErase) {
     auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
     auto It = EraseFrom->find(VarToErase);
     if (It != EraseFrom->end()) {
-      unsigned ID = It->second;
-      VarLocs.reset(ID);
+      LocIndex ID = It->second;
+      VarLocs.reset(ID.getAsRawInteger());
       EraseFrom->erase(It);
     }
   };
 
   DebugVariable Var = VL.Var;
 
   // Erase the variable/fragment that ends here.
   DoErase(Var);
for (auto Fragment : MapIt->second) {
       DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()});
     }
   }
 }
 
 void LiveDebugValues::OpenRangesSet::erase(const VarLocSet &KillSet,
                                            const VarLocMap &VarLocIDs) {
   VarLocs.intersectWithComplement(KillSet);
-  for (unsigned ID : KillSet) {
-    const VarLoc *VL = &VarLocIDs[ID];
+  for (uint64_t ID : KillSet) {
+    const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)];
     auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
     EraseFrom->erase(VL->Var);
   }
 }
 
-void LiveDebugValues::OpenRangesSet::insert(unsigned VarLocID,
+void LiveDebugValues::OpenRangesSet::insert(LocIndex VarLocID,
                                             const VarLoc &VL) {
   auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
-  VarLocs.set(VarLocID);
+  VarLocs.set(VarLocID.getAsRawInteger());
   InsertInto->insert({VL.Var, VarLocID});
 }
 
 /// Return the Loc ID of an entry value backup location, if it exists for the
 /// variable.
-llvm::Optional<unsigned>
+llvm::Optional<LocIndex>
 LiveDebugValues::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
   auto It = EntryValuesBackupVars.find(Var);
   if (It != EntryValuesBackupVars.end())
     return It->second;
 
   return llvm::None;
 }
 
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
                                        const VarLocInMBB &V,
                                        const VarLocMap &VarLocIDs,
                                        const char *msg,
                                        raw_ostream &Out) const {
   Out << '\n' << msg << '\n';
   for (const MachineBasicBlock &BB : MF) {
     const VarLocSet &L = V.lookup(&BB);
     if (L.empty())
       continue;
     Out << "MBB: " << BB.getNumber() << ":\n";
-    for (unsigned VLL : L) {
-      const VarLoc &VL = VarLocIDs[VLL];
+    for (uint64_t VLL : L) {
+      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)];
       Out << " Var: " << VL.Var.getVariable()->getName();
       Out << " MI: ";
       VL.dump(TRI, Out);
     }
   }
   Out << "\n";
 }
 #endif
if (I != MI.getParent()->rend()) {
     SrcRegOp = DestSrc->Source;
     DestRegOp = DestSrc->Destination;
     if (Reg != DestRegOp->getReg())
       return true;
     TrySalvageEntryValue = true;
   }
 
   if (TrySalvageEntryValue) {
-    for (unsigned ID : OpenRanges.getVarLocs()) {
-      const VarLoc &VL = VarLocIDs[ID];
+    for (uint64_t ID : OpenRanges.getVarLocs()) {
+      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
       if (!VL.isEntryBackupLoc())
         continue;
 
       if (VL.getEntryValueCopyBackupReg() == Reg &&
           VL.MI.getOperand(0).getReg() == SrcRegOp->getReg())
         return false;
     }
   }
if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) {
       LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
                  MI.print(dbgs(), /*IsStandalone*/ false,
                           /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
                           /*AddNewLine*/ true, TII));
       OpenRanges.erase(EntryVL);
     }
   }
 
-  unsigned ID;
   if (isDbgValueDescribedByReg(MI) || MI.getOperand(0).isImm() ||
       MI.getOperand(0).isFPImm() || MI.getOperand(0).isCImm()) {
     // Use normal VarLoc constructor for registers and immediates.
     VarLoc VL(MI, LS);
     // End all previous ranges of VL.Var.
     OpenRanges.erase(VL);
 
-    ID = VarLocIDs.insert(VL);
+    LocIndex ID = VarLocIDs.insert(VL);
     // Add the VarLoc to OpenRanges from this DBG_VALUE.
     OpenRanges.insert(ID, VL);
   } else if (MI.hasOneMemOperand()) {
     llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?");
   } else {
     // This must be an undefined location. We should leave OpenRanges closed.
     assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 &&
            "Unexpected non-undef DBG_VALUE encountered");
   }
 }
 
 /// Turn the entry value backup locations into primary locations.
 void LiveDebugValues::emitEntryValues(MachineInstr &MI,
                                       OpenRangesSet &OpenRanges,
                                       VarLocMap &VarLocIDs,
                                       TransferMap &Transfers,
                                       SparseBitVector<> &KillSet) {
-  for (unsigned ID : KillSet) {
-    if (!VarLocIDs[ID].Var.getVariable()->isParameter())
+  for (uint64_t ID : KillSet) {
+    LocIndex Idx = LocIndex::fromRawInteger(ID);
+    const VarLoc &VL = VarLocIDs[Idx];
+    if (!VL.Var.getVariable()->isParameter())
       continue;
 
-    auto DebugVar = VarLocIDs[ID].Var;
-    auto EntryValBackupID = OpenRanges.getEntryValueBackup(DebugVar);
+    auto DebugVar = VL.Var;
+    Optional<LocIndex> EntryValBackupID =
+        OpenRanges.getEntryValueBackup(DebugVar);
 
     // If the parameter has the entry value backup, it means we should
     // be able to use its entry value.
     if (!EntryValBackupID)
       continue;
 
     const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID];
     VarLoc EntryLoc =
         VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo);
-    unsigned EntryValueID = VarLocIDs.insert(EntryLoc);
+    LocIndex EntryValueID = VarLocIDs.insert(EntryLoc);
     Transfers.push_back({&MI, EntryValueID});
     OpenRanges.insert(EntryValueID, EntryLoc);
   }
 }
 
 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
 /// new VarLoc. If \p NewReg is different than default zero value then the
 /// new location will be register location created by the copy like instruction,
 /// otherwise it is variable's location on the stack.
 void LiveDebugValues::insertTransferDebugPair(
     MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
-    VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind,
+    VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
     unsigned NewReg) {
   const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
 
   auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
-    unsigned LocId = VarLocIDs.insert(VL);
+    LocIndex LocId = VarLocIDs.insert(VL);
 
     // Close this variable's previous location range.
     OpenRanges.erase(VL);
 
     // Record the new location as an open range, and a postponed transfer
     // inserting a DBG_VALUE for this location.
     OpenRanges.insert(LocId, VL);
     TransferDebugPair MIP = {&MI, LocId};
if (MO.isReg() && MO.isDef() && MO.getReg() &&
       // DEBUG_VALUE across the call is still a better user experience. Note:
       // the actual removal is done after we finish visiting MachineOperands,
       // for performance reasons.
       DeadRegMasks.push_back(MO.getRegMask());
     }
   }
   // For performance reasons, it's critical to iterate over the open var locs
   // at most once.
-  for (unsigned ID : OpenRanges.getVarLocs()) {
-    unsigned Reg = VarLocIDs[ID].isDescribedByReg();
+  for (uint64_t ID : OpenRanges.getVarLocs()) {
+    LocIndex Idx = LocIndex::fromRawInteger(ID);
+    unsigned Reg = VarLocIDs[Idx].isDescribedByReg();
     if (!Reg)
       continue;
 
     if (DeadRegs.count(Reg)) {
       KillSet.set(ID);
       continue;
     }
 
void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
   LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
 
   // First, if there are any DBG_VALUEs pointing at a spill slot that is
   // written to, then close the variable location. The value in memory
   // will have changed.
   VarLocSet KillSet;
   if (isSpillInstruction(MI, MF)) {
     Loc = extractSpillBaseRegAndOffset(MI);
-    for (unsigned ID : OpenRanges.getVarLocs()) {
-      const VarLoc &VL = VarLocIDs[ID];
+    for (uint64_t ID : OpenRanges.getVarLocs()) {
+      LocIndex Idx = LocIndex::fromRawInteger(ID);
+      const VarLoc &VL = VarLocIDs[Idx];
       if (VL.Kind == VarLoc::SpillLocKind && VL.Loc.SpillLocation == *Loc) {
         // This location is overwritten by the current instruction -- terminate
         // the open range, and insert an explicit DBG_VALUE $noreg.
         //
         // Doing this at a later stage would require re-interpreting all
         // DBG_VALUes and DIExpressions to identify whether they point at
         // memory, and then analysing all memory writes to see if they
         // overwrite that memory, which is expensive.
         //
         // At this stage, we already know which DBG_VALUEs are for spills and
         // where they are located; it's best to fix handle overwrites now.
         KillSet.set(ID);
         VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0);
-        unsigned UndefLocID = VarLocIDs.insert(UndefVL);
+        LocIndex UndefLocID = VarLocIDs.insert(UndefVL);
         Transfers.push_back({&MI, UndefLocID});
       }
     }
     OpenRanges.erase(KillSet, VarLocIDs);
   }
 
   // Try to recognise spill and restore instructions that may create a new
   // variable location.
   if (isLocationSpill(MI, MF, Reg)) {
     TKind = TransferKind::TransferSpill;
     LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
                       << "\n");
   } else {
     if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
       return;
     TKind = TransferKind::TransferRestore;
     LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
                       << "\n");
   }
   // Check if the register or spill location is the location of a debug value.
-  for (unsigned ID : OpenRanges.getVarLocs()) {
-    if (TKind == TransferKind::TransferSpill &&
-        VarLocIDs[ID].isDescribedByReg() == Reg) {
+  for (uint64_t ID : OpenRanges.getVarLocs()) {
+    LocIndex Idx = LocIndex::fromRawInteger(ID);
+    const VarLoc &VL = VarLocIDs[Idx];
+    if (TKind == TransferKind::TransferSpill && VL.isDescribedByReg() == Reg) {
       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
-                        << VarLocIDs[ID].Var.getVariable()->getName() << ")\n");
+                        << VL.Var.getVariable()->getName() << ")\n");
     } else if (TKind == TransferKind::TransferRestore &&
-               VarLocIDs[ID].Kind == VarLoc::SpillLocKind &&
-               VarLocIDs[ID].Loc.SpillLocation == *Loc) {
+               VL.Kind == VarLoc::SpillLocKind &&
+               VL.Loc.SpillLocation == *Loc) {
       LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
-                        << VarLocIDs[ID].Var.getVariable()->getName() << ")\n");
+                        << VL.Var.getVariable()->getName() << ")\n");
     } else
       continue;
-    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind,
+    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind,
                             Reg);
     return;
   }
 }
 
 /// If \p MI is a register copy instruction, that copies a previously tracked
 /// value from one register to another register that is callee saved, we
 /// create new DBG_VALUE instruction  described with copy destination register.
void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
   // saved, is going to stay unclobbered longer, even if it is killed.
   if (!isCalleeSavedReg(DestReg))
     return;
 
   // Remember an entry value movement. If we encounter a new debug value of
   // a parameter describing only a moving of the value around, rather then
   // modifying it, we are still able to use the entry value if needed.
   if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) {
-    for (unsigned ID : OpenRanges.getVarLocs()) {
-      if (VarLocIDs[ID].getEntryValueBackupReg() == SrcReg) {
+    for (uint64_t ID : OpenRanges.getVarLocs()) {
+      LocIndex Idx = LocIndex::fromRawInteger(ID);
+      const VarLoc &VL = VarLocIDs[Idx];
+      if (VL.getEntryValueBackupReg() == SrcReg) {
         LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump(););
-        VarLoc EntryValLocCopyBackup = VarLoc::CreateEntryCopyBackupLoc(
-            VarLocIDs[ID].MI, LS, VarLocIDs[ID].Expr, DestReg);
+        VarLoc EntryValLocCopyBackup =
+            VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg);
 
         // Stop tracking the original entry value.
-        OpenRanges.erase(VarLocIDs[ID]);
+        OpenRanges.erase(VL);
 
         // Start tracking the entry value copy.
-        unsigned EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup);
+        LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup);
         OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup);
         break;
       }
     }
   }
 
   if (!SrcRegOp->isKill())
     return;
 
-  for (unsigned ID : OpenRanges.getVarLocs()) {
-    if (VarLocIDs[ID].isDescribedByReg() == SrcReg) {
-      insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID,
+  for (uint64_t ID : OpenRanges.getVarLocs()) {
+    LocIndex Idx = LocIndex::fromRawInteger(ID);
+    if (VarLocIDs[Idx].isDescribedByReg() == SrcReg) {
+      insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx,
                               TransferKind::TransferCopy, DestReg);
       return;
     }
   }
 }
 
 /// Terminate all open ranges at the end of the current basic block.
 bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
                                          OpenRangesSet &OpenRanges,
                                          VarLocInMBB &OutLocs,
                                          const VarLocMap &VarLocIDs) {
   bool Changed = false;
 
-  LLVM_DEBUG(for (unsigned ID
+  LLVM_DEBUG(for (uint64_t ID
                   : OpenRanges.getVarLocs()) {
     // Copy OpenRanges to OutLocs, if not already present.
     dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
-    VarLocIDs[ID].dump(TRI);
+    VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI);
   });
   VarLocSet &VLS = OutLocs[CurMBB];
   Changed = VLS != OpenRanges.getVarLocs();
   // New OutLocs set may be different due to spill, restore or register
   // copy instruction processing.
   if (Changed)
     VLS = OpenRanges.getVarLocs();
   OpenRanges.clear();
for (auto p : MBB.predecessors()) {
     // predecessor, and for all other predecessors join the Out locs.
     if (!NumVisited)
       InLocsT = OL->second;
     else
       InLocsT &= OL->second;
 
     LLVM_DEBUG({
       if (!InLocsT.empty()) {
-        for (auto ID : InLocsT)
+        for (uint64_t ID : InLocsT)
           dbgs() << "  gathered candidate incoming var: "
-                 << VarLocIDs[ID].Var.getVariable()->getName() << "\n";
+                 << VarLocIDs[LocIndex::fromRawInteger(ID)]
+                        .Var.getVariable()
+                        ->getName()
+                 << "\n";
       }
     });
 
     NumVisited++;
   }
 
   // Filter out DBG_VALUES that are out of scope.
   VarLocSet KillSet;
   bool IsArtificial = ArtificialBlocks.count(&MBB);
   if (!IsArtificial) {
-    for (auto ID : InLocsT) {
-      if (!VarLocIDs[ID].dominates(MBB)) {
+    for (uint64_t ID : InLocsT) {
+      LocIndex Idx = LocIndex::fromRawInteger(ID);
+      if (!VarLocIDs[Idx].dominates(MBB)) {
         KillSet.set(ID);
         LLVM_DEBUG({
-          auto Name = VarLocIDs[ID].Var.getVariable()->getName();
+          auto Name = VarLocIDs[Idx].Var.getVariable()->getName();
           dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
         });
       }
     }
   }
   InLocsT.intersectWithComplement(KillSet);
 
   // As we are processing blocks in reverse post-order we
   // should have processed at least one predecessor, unless it
   // is the entry block which has no predecessor.
   assert((NumVisited || MBB.pred_empty()) &&
          "Should have processed at least one predecessor");
 
   VarLocSet &ILS = InLocs[&MBB];
   VarLocSet &Pending = PendingInLocs[&MBB];
 
   // New locations will have DBG_VALUE insts inserted at the start of the
   // block, after location propagation has finished. Record the insertions
   // that we need to perform in the Pending set.
   VarLocSet Diff = InLocsT;
   Diff.intersectWithComplement(ILS);
-  for (auto ID : Diff) {
-    Pending.set(ID);
-    ILS.set(ID);
-    ++NumInserted;
-    Changed = true;
-  }
+  Pending |= Diff;
+  ILS |= Diff;
+  unsigned JustInserted = Diff.count();
+  NumInserted += JustInserted;
+  Changed = JustInserted > 0;
 
   // We may have lost locations by learning about a predecessor that either
   // loses or moves a variable. Find any locations in ILS that are not in the
   // new in-locations, and delete those.
   VarLocSet Removed = ILS;
   Removed.intersectWithComplement(InLocsT);
-  for (auto ID : Removed) {
-    Pending.reset(ID);
-    ILS.reset(ID);
-    ++NumRemoved;
-    Changed = true;
-  }
+  Pending.intersectWithComplement(Removed);
+  ILS.intersectWithComplement(Removed);
+  unsigned JustRemoved = Removed.count();
+  NumRemoved += JustRemoved;
+  Changed |= JustRemoved > 0;
 
   return Changed;
 }
 
 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
   for (auto &Iter : PendingInLocs) {
     // Map is keyed on a constant pointer, unwrap it so we can insert insts.
     auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
     VarLocSet &Pending = Iter.second;
 
-    for (unsigned ID : Pending) {
+    for (uint64_t ID : Pending) {
       // The ID location is live-in to MBB -- work out what kind of machine
       // location it is and create a DBG_VALUE.
-      const VarLoc &DiffIt = VarLocIDs[ID];
+      const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)];
       if (DiffIt.isEntryBackupLoc())
         continue;
       MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent());
       MBB.insert(MBB.instr_begin(), MI);
 
       (void)MI;
       LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
     }
void LiveDebugValues::recordEntryValue(const MachineInstr &MI,
 
   LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump(););
 
   // Create the entry value and use it as a backup location until it is
   // valid. It is valid until a parameter is not changed.
   DIExpression *NewExpr =
       DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue);
   VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr);
-  unsigned EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
+  LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
   OpenRanges.insert(EntryValLocID, EntryValLocAsBackup);
 }
 
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");