vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085

1 files changed, 111 insertions, 115 deletions

diff --git a/llvm/lib/CodeGen/LiveDebugVariables.cpp b/llvm/lib/CodeGen/LiveDebugVariables.cpp
index 2dd462fc72b3..2cc547a6b741 100644
--- a/llvm/lib/CodeGen/LiveDebugVariables.cpp
+++ b/llvm/lib/CodeGen/LiveDebugVariables.cpp
@@ -49,6 +49,7 @@
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/InitializePasses.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
@@ -142,51 +143,22 @@ 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;
@@ -207,15 +179,49 @@ class UserValue {
                      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)), locInts(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; }
+
+  /// 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;
+  }
 
-  UserValueIdentity getId() {
-    return UserValueIdentity(Variable, Expression, dl->getInlinedAt());
+  /// 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;
   }
 
   /// Return the location number that matches Loc.
@@ -250,6 +256,25 @@ public:
     return locations.size() - 1;
   }
 
+  /// Remove (recycle) a location number. If \p LocNo still is used by the
+  /// locInts nothing is done.
+  void removeLocationIfUnused(unsigned LocNo) {
+    // Bail out if LocNo still is used.
+    for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
+      DbgValueLocation Loc = I.value();
+      if (Loc.locNo() == LocNo)
+        return;
+    }
+    // Remove the entry in the locations vector, and adjust all references to
+    // location numbers above the removed entry.
+    locations.erase(locations.begin() + LocNo);
+    for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
+      DbgValueLocation Loc = I.value();
+      if (!Loc.isUndef() && Loc.locNo() > LocNo)
+        I.setValueUnchecked(Loc.changeLocNo(Loc.locNo() - 1));
+    }
+  }
+
   /// Ensure that all virtual register locations are mapped.
   void mapVirtRegs(LDVImpl *LDV);
 
@@ -327,29 +352,7 @@ public:
 
   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.
@@ -401,20 +404,20 @@ class LDVImpl {
   /// All allocated UserLabel instances.
   SmallVector<std::unique_ptr<UserLabel>, 2> userLabels;
 
-  /// Map virtual register to UserValues which use it.
-  using VRMap = DenseMap<unsigned, SmallVector<UserValue *, 4>>;
-  VRMap VirtRegToUserVals;
+  /// Map virtual register to eq class leader.
+  using VRMap = DenseMap<unsigned, UserValue *>;
+  VRMap virtRegToEqClass;
 
-  /// Map unique UserValue identity to UserValue.
-  using UVMap = DenseMap<UserValueIdentity, UserValue *>;
-  UVMap UserVarMap;
+  /// Map user variable to eq class leader.
+  using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
+  UVMap userVarMap;
 
   /// Find or create a UserValue.
   UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
                           const DebugLoc &DL);
 
-  /// Find the UserValues for VirtReg or null.
-  SmallVectorImpl<UserValue *> *lookupVirtReg(unsigned VirtReg);
+  /// Find the EC leader for VirtReg or null.
+  UserValue *lookupVirtReg(unsigned VirtReg);
 
   /// Add DBG_VALUE instruction to our maps.
   ///
@@ -454,8 +457,8 @@ public:
     MF = nullptr;
     userValues.clear();
     userLabels.clear();
-    VirtRegToUserVals.clear();
-    UserVarMap.clear();
+    virtRegToEqClass.clear();
+    userVarMap.clear();
     // Make sure we call emitDebugValues if the machine function was modified.
     assert((!ModifiedMF || EmitDone) &&
            "Dbg values are not emitted in LDV");
@@ -463,8 +466,8 @@ public:
     ModifiedMF = false;
   }
 
-  /// Map virtual register to a UserValue.
-  void mapVirtReg(unsigned VirtReg, UserValue *UV);
+  /// Map virtual register to an equivalence class.
+  void mapVirtReg(unsigned VirtReg, UserValue *EC);
 
   /// Replace all references to OldReg with NewRegs.
   void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
@@ -503,7 +506,7 @@ static void printExtendedName(raw_ostream &OS, const DINode *Node,
                               const DILocation *DL) {
   const LLVMContext &Ctx = Node->getContext();
   StringRef Res;
-  unsigned Line;
+  unsigned Line = 0;
   if (const auto *V = dyn_cast<const DILocalVariable>(Node)) {
     Res = V->getName();
     Line = V->getLine();
@@ -572,27 +575,31 @@ void UserValue::mapVirtRegs(LDVImpl *LDV) {
 
 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
                                  const DIExpression *Expr, const DebugLoc &DL) {
-  auto Ident = UserValueIdentity(Var, Expr, DL->getInlinedAt());
-  UserValue *&UVEntry = UserVarMap[Ident];
-
-  if (UVEntry)
-    return UVEntry;
+  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));
-  return UVEntry = userValues.back().get();
+  userValues.push_back(
+      std::make_unique<UserValue>(Var, Expr, DL, allocator));
+  UserValue *UV = userValues.back().get();
+  Leader = UserValue::merge(Leader, UV);
+  return UV;
 }
 
-void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *UV) {
+void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
   assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs");
-  assert(UserVarMap.find(UV->getId()) != UserVarMap.end() &&
-         "UserValue should exist in UserVarMap");
-  VirtRegToUserVals[VirtReg].push_back(UV);
+  UserValue *&Leader = virtRegToEqClass[VirtReg];
+  Leader = UserValue::merge(Leader, EC);
 }
 
-SmallVectorImpl<UserValue *> *LDVImpl::lookupVirtReg(unsigned VirtReg) {
-  VRMap::iterator Itr = VirtRegToUserVals.find(VirtReg);
-  if (Itr != VirtRegToUserVals.end())
-    return &Itr->getSecond();
+UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
+  if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
+    return UV->getLeader();
   return nullptr;
 }
 
@@ -1086,23 +1093,14 @@ UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
     }
   }
 
-  // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
-  locations.erase(locations.begin() + OldLocNo);
-  LocMapI.goToBegin();
-  while (LocMapI.valid()) {
-    DbgValueLocation v = LocMapI.value();
-    if (v.locNo() == OldLocNo) {
-      LLVM_DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
-                        << LocMapI.stop() << ")\n");
-      LocMapI.erase();
-    } else {
-      // Undef values always have location number UndefLocNo, so don't change
-      // locNo in that case. See getLocationNo().
-      if (!v.isUndef() && v.locNo() > OldLocNo)
-        LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
-      ++LocMapI;
-    }
-  }
+  // Finally, remove OldLocNo unless it is still used by some interval in the
+  // locInts map. One case when OldLocNo still is in use is when the register
+  // has been spilled. In such situations the spilled register is kept as a
+  // location until rewriteLocations is called (VirtRegMap is mapping the old
+  // register to the spill slot). So for a while we can have locations that map
+  // to virtual registers that have been removed from both the MachineFunction
+  // and from LiveIntervals.
+  removeLocationIfUnused(OldLocNo);
 
   LLVM_DEBUG({
     dbgs() << "Split result: \t";
@@ -1129,18 +1127,16 @@ UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
 
 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
   bool DidChange = false;
-  if (auto *UserVals = lookupVirtReg(OldReg))
-    for (auto *UV : *UserVals)
-      DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
+  for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
+    DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
 
   if (!DidChange)
     return;
 
   // Map all of the new virtual registers.
-  if (auto *UserVals = lookupVirtReg(OldReg))
-    for (auto *UV : *UserVals)
-      for (unsigned i = 0; i != NewRegs.size(); ++i)
-        mapVirtReg(NewRegs[i], UV);
+  UserValue *UV = lookupVirtReg(OldReg);
+  for (unsigned i = 0; i != NewRegs.size(); ++i)
+    mapVirtReg(NewRegs[i], UV);
 }
 
 void LiveDebugVariables::