[NFC] Fix performance issue in LiveDebugVariables

[Orlando]

Summary

When compiling AMDGPUDisassembler.cpp in a stage 1 trunk build with
CMAKE_BUILD_TYPE=RelWithDebInfo LLVM_USE_SANITIZER=Address LiveDebugVariables
accounts for 21.5% wall clock time. This fix reduces that to 1.2% by switching
out a linked list lookup with a map lookup.

Note that the linked list is still used to group UserValues by vreg. The vreg
lookups don't cause any problems in this pathological case.

N.B. This is the same idea as D68816, which was reverted, except that it is a less intrusive
fix.

[vsk]

Awesome! Lgtm.

[Orlando]

Thanks @vsk.

llvm/lib/CodeGen/LiveDebugVariables.cpp

 class LDVImpl;
 
 /// 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.
+/// user values are related 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.
   /// The part of the variable we describe.
   const Optional<DIExpression::FragmentInfo> Fragment;
   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.
UserValue *getLeader() {
     while (l != l->leader)
       l = l->leader;
     return leader = l;
   }
 
   /// Return the next UserValue in the equivalence class.
   UserValue *getNext() const { return next; }
 
-  /// Does this UserValue match the parameters?
-  bool matches(const DILocalVariable *Var,
-             Optional<DIExpression::FragmentInfo> OtherFragment,
-             const DILocation *IA) const {
-    // FIXME: Handle partially overlapping fragments.
-    // A DBG_VALUE with a fragment which overlaps a previous DBG_VALUE fragment
-    // for the same variable terminates the interval opened by the first.
-    // getUserValue() uses matches() to filter DBG_VALUEs into interval maps to
-    // represent these intervals.
-    // Given two _partially_ overlapping fragments matches() will always return
-    // false. The DBG_VALUEs will be filtered into separate interval maps and
-    // therefore we do not faithfully represent the original intervals.
-    // See D70121#1849741 for a more detailed explanation and further
-    // discussion.
-    return Var == Variable && OtherFragment == Fragment &&
-           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;
class LDVImpl {
 
   /// 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 *>;
+  /// Map to find existing UserValue instances.
+  using UVMap = DenseMap<DebugVariable, UserValue *>;
   UVMap userVarMap;
 
   /// Find or create a UserValue.
   UserValue *getUserValue(const DILocalVariable *Var,
                           Optional<DIExpression::FragmentInfo> Fragment,
                           const DebugLoc &DL);
 
   /// Find the EC leader for VirtReg or null.
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,
                                  Optional<DIExpression::FragmentInfo> Fragment,
                                  const DebugLoc &DL) {
-  UserValue *&Leader = userVarMap[Var];
-  if (Leader) {
-    UserValue *UV = Leader->getLeader();
-    Leader = UV;
-    for (; UV; UV = UV->getNext())
-      if (UV->matches(Var, Fragment, DL->getInlinedAt()))
-        return UV;
-  }
-
+  // FIXME: Handle partially overlapping fragments. See
+  // https://reviews.llvm.org/D70121#1849741.
+  DebugVariable ID(Var, Fragment, DL->getInlinedAt());
+  UserValue *&UV = userVarMap[ID];
+  if (!UV) {
     userValues.push_back(
         std::make_unique<UserValue>(Var, Fragment, DL, allocator));
-  UserValue *UV = userValues.back().get();
-  Leader = UserValue::merge(Leader, UV);
+    UV = userValues.back().get();
+  }
   return UV;
 }
 
 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
   assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs");
   UserValue *&Leader = virtRegToEqClass[VirtReg];
   Leader = UserValue::merge(Leader, EC);
 }