[NFC] Replace a linked list in LiveDebugVariables pass with a DenseMap

[Orlando]

Summary

This patch improves asan self-host build times slightly.

Self-host build times with and without this patch
------------------------------------------------------------------
With this patch applied | Build type           | CPU time (mins)
------------------------------------------------------------------
No                      | RelWithDebInfo, asan | 226
Yes                     | RelWithDebInfo, asan | 218 (-3.5%)

In LiveDebugVariables.cpp:
Prior to this patch, UserValues were grouped into linked list chains. Each
chain was the union of two sets: { A: Matching Source variable } or
{ B: Matching virtual register }. A ptr to the heads (or 'leaders')
of each of these chains were kept in a map with the { Source variable } used
as the key (set A predicate) and another with { Virtual register } as key
(set B predicate).

There was a search through the chains in the function getUserValue looking for
UserValues with matching { Source variable, Complex expression, Inlined-at
location }. Essentially searching for a subset of A through two interleaved
linked lists of set A and B. Importantly, by design, the subset will only
contain one or zero elements here. That is to say a UserValue can be uniquely
identified by the tuple { Source variable, Complex expression, Inlined-at
location } if it exists.

This patch removes the linked list and instead uses a DenseMap to map
the tuple { Source variable, Complex expression, Inlined-at location }
to UserValue ptrs so that the getUserValue search predicate is this map key.
The virtual register map now maps a vreg to a SmallVector<UserVal *> so that
set B is still available for quick searches.

[Orlando]

The numbers are much better than I expected but I haven't been able to prove
myself wrong after a bunch of testing. So, I've put this patch up for the
community's expert eyes.

[aprantl]

This is a really nice performance win and the code looks nicer, too.

llvm/lib/CodeGen/LiveDebugVariables.cpp

152

nit:

/// The debug info variable we are part of.
 const DILocalVariable *Variable;
...

333

FYI. If you don't want to implement all this, you can also inherit from std::pair<std::pair<>>. (With a single pair this is a more obvious win.)

[aprantl]

llvm/lib/CodeGen/LiveDebugVariables.cpp

165

Not your code, but: add a FragmentInfo element?

409

How many elements does this have on average? Is a SmallDenseMap a win?

[dblaikie]

llvm/lib/CodeGen/LiveDebugVariables.cpp

338

Drop the inline keyword here and above - the linkage is implied by the definition being provided inside a class definition.

[Orlando]

Addressed comments and fixed Summary (previously it referred to
LiveDebugValues.cpp instead of LiveDebugVariables.cpp).

@aprantl

Not your code, but: add a FragmentInfo element?

As you point out in D66415 we need to take care to track overlapping fragment
ranges too. This shouldn't be too hard but it makes more sense to me to rebase
D66415 on this and work from there.

How many elements does this have on average? Is a SmallDenseMap a win?

The following numbers are only anecdotal of course. I compiled two example
single file projects with -g -O2 (A: ~100,000 loc, B: ~20,000 loc) and in both
cases roughly 90% of UserVarMap.size() were <= 64.

---

Project A: UserVarMap size
--------------------------------------
Size <= x | Num maps | % of total maps
--------------------------------------
0         | 697      | 50
2         | 770      | 55.2
4         | 797      | 57.2
8         | 858      | 61.5
16        | 969      | 69.5
32        | 1109     | 79.6
64        | 1221     | 87.6
128       | 1311     | 94.0
256       | 1361     | 97.6
512       | 1379     | 98.9
1024      | 1388     | 99.6

--------------------------------------
Project B: UserVarMap size
--------------------------------------
Size <= x | Num maps | % of total maps
--------------------------------------
0         | 296      | 50.3
2         | 306      | 52.0
4         | 333      | 56.6
8         | 364      | 61.9
16        | 397      | 67.5
32        | 477      | 81.1
64        | 530      | 90.1
128       | 572      | 97.3
256       | 582      | 99.0
512       | 587	     | 99.8
1024      | 588      | 100

I don't have any self-host build time stats for this yet but he default DenseMap
64 element alloc seems almost perfect for these examples. Assuming a
SmallDenseMap allocates space in the object (like SmallVector) and given that
LDVImpl seems to only ever be heap allocated, a SmallDenseMap<..., 64> would
likely give some (small) build time reduction. I'll add more info here
when I can get some self-host build times.

[aprantl]

This is good to land with whatever conclusions we draw from the SmallDenseMap experiment. Thanks!

[Orlando]

After timing some more self-hosts it looks like my original numbers which looked
too good to be true sadly are just that. The self-host asan build time reduction
seems correct (-3.5%) but the non-asan builds are much less impacted then first
thought (about -1%). These numbers are more in line with my original expectation.

After doing some more self-host builds and building a smaller llvm-based project
16 times it seems like the SmallDenseMap makes essentially no difference.

[bjope]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1141

The mapVirtReg call below adds elements to the DenseMap. When a DenseMap grows/shrinks it might be re-allocated. So the pointer to the SmallVector (stored inside the map elements), called UserVals here, may be a dangling pointer after the first call to mapVirtReg and the vector it points to may have been moved.

So the iteration over *UserVals here is not safe, and asan complains about accessing deallocated memory.

A quick workaround that I'm trying downstream is to copy the vector like this:

diff --git a/llvm/lib/CodeGen/LiveDebugVariables.cpp b/llvm/lib/CodeGen/LiveDebugVariables.cpp
index 6032bfe48af..4659ebea254 100644
--- a/llvm/lib/CodeGen/LiveDebugVariables.cpp
+++ b/llvm/lib/CodeGen/LiveDebugVariables.cpp
@@ -1144,10 +1144,16 @@ void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
     return;
 
   // Map all of the new virtual registers.
-  if (auto *UserVals = lookupVirtReg(OldReg))
-    for (auto *UV : *UserVals)
+  if (auto *UserVals = lookupVirtReg(OldReg)) {
+    // Make a copy of the vector. This is needed because VirtRegToUserVals is
+    // updated in the loop below, so the pointer into the VirtRegToUserVals
+    // DenseMap may become invalid in case the map is reallocated.
+    SmallVector<UserValue *, 4> UserValsCopy;
+    UserValsCopy.assign(UserVals->begin(), UserVals->end());
+    for (auto *UV : UserValsCopy)
       for (unsigned i = 0; i != NewRegs.size(); ++i)
         mapVirtReg(NewRegs[i], UV);
+  }
 }

No idea if this impacts the performance negatively (considering that the idea with the refactoring into using a DenseMap seem to be to improve compile speed maybe there are better solutions). But right now we the code is broken so I guess we need to submit a workaround or a revert.

[Orlando]

Hi @bjope thank you for pointing this out and providing a workaround. I'll test out your change and investigate further.

I seem to have lost commit access in the move over to GitHub - thanks @andreadb for reverting this (67720e7bf7df).

[Orlando]

llvm/lib/CodeGen/LiveDebugVariables.cpp

1141

A quick workaround that I'm trying downstream is to copy the vector like this

Replacing the DenseMap LDVImpl::VirtRegToUserVals uses with a std::unordered_map looks like it should also work.

I started work on this patch because @jmorse found that during an asan build LDV consumed ~30% CPU time when building AMDGPUDisassembler.cpp. This worst-case is reduced to <3% for me with my faulty patch and there is no noticeable difference when adding either of these changes. I'll look at the build time impact of these two approaches on self host builds when I get the chance but I'm leaning towards the unordered_map because it makes it harder to run into this again.

Thanks again for the heads up!

llvm/lib/CodeGen/LiveDebugVariables.cpp

 /// Map of stack slot offsets for spilled locations.
 /// Non-spilled locations are not added to the map.
 using SpillOffsetMap = DenseMap<unsigned, unsigned>;
 
 namespace {
 
 class LDVImpl;
 
+/// A UserValue is uniquely identified by the source variable it refers to
+/// (Variable), the expression describing how to get the value (Expression) and
+/// the specific usage (InlinedAt). InlinedAt differentiates both between
+/// inline and non-inline functions, and multiple inlined instances in the same
+/// scope. FIXME: The only part of the Expression which matters for UserValue
+/// identification is the fragment part.
+class UserValueIdentity {
+private:
+  /// The debug info variable we are part of.
+  const DILocalVariable *Variable;
+  /// Any complex address expression.
+  const DIExpression *Expression;
+  /// Function usage identification.
+  const DILocation *InlinedAt;
+
+public:
+  UserValueIdentity(const DILocalVariable *Var, const DIExpression *Expr,
+                    const DILocation *IA)
+      : Variable(Var), Expression(Expr), InlinedAt(IA) {}
+
+  bool match(const DILocalVariable *Var, const DIExpression *Expr,
+             const DILocation *IA) const {
+    // FIXME: The fragment should be part of the identity, but not
+    // other things in the expression like stack values.
+    return Var == Variable && Expr == Expression && IA == InlinedAt;
+  }
+
+  bool match(const UserValueIdentity &Other) const {
+    return match(Other.Variable, Other.Expression, Other.InlinedAt);
+  }
+
+  unsigned hash_value() const {
+    return hash_combine(Variable, Expression, InlinedAt);
+  }
+};
+
 /// A user value is a part of a debug info user variable.
 ///
 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
 /// holds part of a user variable. The part is identified by a byte offset.
-///
-/// UserValues are grouped into equivalence classes for easier searching. Two
-/// user values are related if they refer to the same variable, or if they are
-/// held by the same virtual register. The equivalence class is the transitive
-/// closure of that relation.
 class UserValue {
   const DILocalVariable *Variable; ///< The debug info variable we are part of.
   const DIExpression *Expression; ///< Any complex address expression.
   DebugLoc dl;            ///< The debug location for the variable. This is
                           ///< used by dwarf writer to find lexical scope.
-  UserValue *leader;      ///< Equivalence class leader.
-  UserValue *next = nullptr; ///< Next value in equivalence class, or null.
 
   /// Numbered locations referenced by locmap.
   SmallVector<MachineOperand, 4> locations;
 
   /// Map of slot indices where this value is live.
   LocMap locInts;
 
   /// Insert a DBG_VALUE into MBB at Idx for LocNo.
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
                         SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled,
                         unsigned SpillOffset, LiveIntervals &LIS,
                         const TargetInstrInfo &TII,
                         const TargetRegisterInfo &TRI);
 
   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
   /// is live. Returns true if any changes were made.
   bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
                      LiveIntervals &LIS);
 
 public:
+  UserValue(const UserValue &) = delete;
+
   /// Create a new UserValue.
   UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
             LocMap::Allocator &alloc)
-      : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
-        locInts(alloc) {}
-
-  /// Get the leader of this value's equivalence class.
-  UserValue *getLeader() {
-    UserValue *l = leader;
-    while (l != l->leader)
-      l = l->leader;
-    return leader = l;
-  }
-
-  /// Return the next UserValue in the equivalence class.
-  UserValue *getNext() const { return next; }
+      : Variable(var), Expression(expr), dl(std::move(L)), locInts(alloc) {}
 
-  /// Does this UserValue match the parameters?
-  bool match(const DILocalVariable *Var, const DIExpression *Expr,
-             const DILocation *IA) const {
-    // FIXME: The fragment should be part of the equivalence class, but not
-    // other things in the expression like stack values.
-    return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA;
-  }
-
-  /// Merge equivalence classes.
-  static UserValue *merge(UserValue *L1, UserValue *L2) {
-    L2 = L2->getLeader();
-    if (!L1)
-      return L2;
-    L1 = L1->getLeader();
-    if (L1 == L2)
-      return L1;
-    // Splice L2 before L1's members.
-    UserValue *End = L2;
-    while (End->next) {
-      End->leader = L1;
-      End = End->next;
-    }
-    End->leader = L1;
-    End->next = L1->next;
-    L1->next = L2;
-    return L1;
+  UserValueIdentity getId() {
+    return UserValueIdentity(Variable, Expression, dl->getInlinedAt());
   }
 
   /// Return the location number that matches Loc.
   ///
   /// For undef values we always return location number UndefLocNo without
   /// inserting anything in locations. Since locations is a vector and the
   /// location number is the position in the vector and UndefLocNo is ~0,
   /// we would need a very big vector to put the value at the right position.
void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
                        const TargetRegisterInfo &TRI,
                        const SpillOffsetMap &SpillOffsets);
 
   /// Return DebugLoc of this UserValue.
   DebugLoc getDebugLoc() { return dl;}
 
   void print(raw_ostream &, const TargetRegisterInfo *);
 };
+} // namespace
+
+namespace llvm {
+template <> struct DenseMapInfo<UserValueIdentity> {
+  static UserValueIdentity getEmptyKey() {
+    auto Key = DenseMapInfo<DILocalVariable *>::getEmptyKey();
+    return UserValueIdentity(Key, nullptr, nullptr);
+  }
+  static UserValueIdentity getTombstoneKey() {
+    auto Key = DenseMapInfo<DILocalVariable *>::getTombstoneKey();
+    return UserValueIdentity(Key, nullptr, nullptr);
+  }
+  static unsigned getHashValue(const UserValueIdentity &Val) {
+    return Val.hash_value();
+  }
+  static bool isEqual(const UserValueIdentity &LHS,
+                      const UserValueIdentity &RHS) {
+    return LHS.match(RHS);
+  }
+};
+} // namespace llvm
 
+namespace {
 /// A user label is a part of a debug info user label.
 class UserLabel {
   const DILabel *Label; ///< The debug info label we are part of.
   DebugLoc dl;          ///< The debug location for the label. This is
                         ///< used by dwarf writer to find lexical scope.
   SlotIndex loc;        ///< Slot used by the debug label.
 
   /// Insert a DBG_LABEL into MBB at Idx.
class LDVImpl {
   bool ModifiedMF = false;
 
   /// All allocated UserValue instances.
   SmallVector<std::unique_ptr<UserValue>, 8> userValues;
 
   /// All allocated UserLabel instances.
   SmallVector<std::unique_ptr<UserLabel>, 2> userLabels;
 
-  /// Map virtual register to eq class leader.
-  using VRMap = DenseMap<unsigned, UserValue *>;
-  VRMap virtRegToEqClass;
-
-  /// Map user variable to eq class leader.
-  using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
-  UVMap userVarMap;
+  /// Map virtual register to UserValues which use it.
+  using VRMap = DenseMap<unsigned, SmallVector<UserValue *, 4>>;
+  VRMap VirtRegToUserVals;
+
+  /// Map unique UserValue identity to UserValue.
+  using UVMap = DenseMap<UserValueIdentity, UserValue *>;
+  UVMap UserVarMap;
 
   /// Find or create a UserValue.
   UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
                           const DebugLoc &DL);
 
-  /// Find the EC leader for VirtReg or null.
-  UserValue *lookupVirtReg(unsigned VirtReg);
+  /// Find the UserValues for VirtReg or null.
+  SmallVectorImpl<UserValue *> *lookupVirtReg(unsigned VirtReg);
 
   /// Add DBG_VALUE instruction to our maps.
   ///
   /// \param MI DBG_VALUE instruction
   /// \param Idx Last valid SLotIndex before instruction.
   ///
   /// \returns True if the DBG_VALUE instruction should be deleted.
   bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
public:
 
   bool runOnMachineFunction(MachineFunction &mf);
 
   /// Release all memory.
   void clear() {
     MF = nullptr;
     userValues.clear();
     userLabels.clear();
-    virtRegToEqClass.clear();
-    userVarMap.clear();
+    VirtRegToUserVals.clear();
+    UserVarMap.clear();
     // Make sure we call emitDebugValues if the machine function was modified.
     assert((!ModifiedMF || EmitDone) &&
            "Dbg values are not emitted in LDV");
     EmitDone = false;
     ModifiedMF = false;
   }
 
-  /// Map virtual register to an equivalence class.
-  void mapVirtReg(unsigned VirtReg, UserValue *EC);
+  /// Map virtual register to a UserValue.
+  void mapVirtReg(unsigned VirtReg, UserValue *UV);
 
   /// Replace all references to OldReg with NewRegs.
   void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
 
   /// Recreate DBG_VALUE instruction from data structures.
   void emitDebugValues(VirtRegMap *VRM);
 
   void print(raw_ostream&);
void UserValue::mapVirtRegs(LDVImpl *LDV) {
   for (unsigned i = 0, e = locations.size(); i != e; ++i)
     if (locations[i].isReg() &&
         Register::isVirtualRegister(locations[i].getReg()))
       LDV->mapVirtReg(locations[i].getReg(), this);
 }
 
 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
                                  const DIExpression *Expr, const DebugLoc &DL) {
-  UserValue *&Leader = userVarMap[Var];
-  if (Leader) {
-    UserValue *UV = Leader->getLeader();
-    Leader = UV;
-    for (; UV; UV = UV->getNext())
-      if (UV->match(Var, Expr, DL->getInlinedAt()))
-        return UV;
-  }
-
-  userValues.push_back(
-      std::make_unique<UserValue>(Var, Expr, DL, allocator));
-  UserValue *UV = userValues.back().get();
-  Leader = UserValue::merge(Leader, UV);
-  return UV;
+  auto Ident = UserValueIdentity(Var, Expr, DL->getInlinedAt());
+  UserValue *&UVEntry = UserVarMap[Ident];
+
+  if (UVEntry)
+    return UVEntry;
+
+  userValues.push_back(std::make_unique<UserValue>(Var, Expr, DL, allocator));
+  return UVEntry = userValues.back().get();
 }
 
-void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
+void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *UV) {
   assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs");
-  UserValue *&Leader = virtRegToEqClass[VirtReg];
-  Leader = UserValue::merge(Leader, EC);
+  assert(UserVarMap.find(UV->getId()) != UserVarMap.end() &&
+         "UserValue should exist in UserVarMap");
+  VirtRegToUserVals[VirtReg].push_back(UV);
 }
 
-UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
-  if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
-    return UV->getLeader();
+SmallVectorImpl<UserValue *> *LDVImpl::lookupVirtReg(unsigned VirtReg) {
+  VRMap::iterator Itr = VirtRegToUserVals.find(VirtReg);
+  if (Itr != VirtRegToUserVals.end())
+    return &Itr->getSecond();
   return nullptr;
 }
 
 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
   // DBG_VALUE loc, offset, variable
   if (MI.getNumOperands() != 4 ||
       !(MI.getOperand(1).isReg() || MI.getOperand(1).isImm()) ||
       !MI.getOperand(2).isMetadata()) {
if (!Loc->isReg() || Loc->getReg() != OldReg)
       continue;
     DidChange |= splitLocation(LocNo, NewRegs, LIS);
   }
   return DidChange;
 }
 
 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
   bool DidChange = false;
-  for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
+  if (auto *UserVals = lookupVirtReg(OldReg))
+    for (auto *UV : *UserVals)
       DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
 
   if (!DidChange)
     return;
 
   // Map all of the new virtual registers.
-  UserValue *UV = lookupVirtReg(OldReg);
+  if (auto *UserVals = lookupVirtReg(OldReg))
+    for (auto *UV : *UserVals)
       for (unsigned i = 0; i != NewRegs.size(); ++i)
         mapVirtReg(NewRegs[i], UV);
 }
 
 void LiveDebugVariables::
 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
 }