[DebugInfo] Use a DenseMap to coalesce MachineOperand locations

[rnk]

Summary

The new code should be linear in the number of DBG_VALUEs, while the old
code was quadratic.

This is also hopefully a more direct expression of the problem, which
is to:

1. Rewrite all virtual register operands to stack slots or physical registers
2. Uniquely number those machine operands, assigning them location numbers
3. Rewrite all uses of the old location numbers in the interval map to use the new location numbers

In r313400, I attempted to track which locations were spilled in a
parallel bitvector indexed by location number. My code was broken
because these location numbers are not stable during rewriting.

[aprantl]

Testcase is the same as in the original commit?

llvm/include/llvm/CodeGen/MachineOperand.h

785

///

[hans]

I'm not familiar with the DBG_VALUE stuff, but this looks good as far as I can tell.

llvm/include/llvm/CodeGen/MachineOperand.h

787

I wonder if this could be made future-proof in case another MO_ enumerator is ever added. Maybe add a MO_LAST = MO_Predicate to the enumeration?

llvm/lib/CodeGen/LiveDebugVariables.cpp

947

nit: the change description said DenseMap :-)
Maybe comment somehow that the bool is just a dummy here and you're just using it as a set?

970

Should this comment on the fact that coalescing can happen here if the new location is identical to something already in NewLocations?

[rnk]

llvm/include/llvm/CodeGen/MachineOperand.h

785

Done, but I think it's private so it won't show up in Doxygen anyway.

787

Good idea, done.

llvm/lib/CodeGen/LiveDebugVariables.cpp

970

The coalescing really happens below when we update the IntervalMap. I'll elaborate there on what it is.

llvm/include/llvm/CodeGen/MachineOperand.h

 //===-- llvm/CodeGen/MachineOperand.h - MachineOperand class ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the declaration of the MachineOperand class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_MACHINEOPERAND_H
 #define LLVM_CODEGEN_MACHINEOPERAND_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/Support/DataTypes.h"
 #include <cassert>
 
 namespace llvm {
 
 class BlockAddress;
 class ConstantFP;
static MachineOperand CreatePredicate(unsigned Pred) {
     return Op;
   }
 
   friend class MachineInstr;
   friend class MachineRegisterInfo;
 private:
   void removeRegFromUses();
 
+  // Artificial kinds for DenseMap usage.
+  enum : unsigned char {
+    MO_Empty = MO_Predicate + 1,
+    MO_Tombstone,
+  };
+
+  friend struct DenseMapInfo<MachineOperand>;
+
   //===--------------------------------------------------------------------===//
   // Methods for handling register use/def lists.
   //===--------------------------------------------------------------------===//
 
   /// isOnRegUseList - Return true if this operand is on a register use/def list
   /// or false if not.  This can only be called for register operands that are
   /// part of a machine instruction.
   bool isOnRegUseList() const {
     assert(isReg() && "Can only add reg operand to use lists");
     return Contents.Reg.Prev != nullptr;
   }
 };
 
+template <> struct DenseMapInfo<MachineOperand> {
+  static MachineOperand getEmptyKey() {
+    return MachineOperand(static_cast<MachineOperand::MachineOperandType>(
+        MachineOperand::MO_Empty));
+  }
+  static MachineOperand getTombstoneKey() {
+    return MachineOperand(static_cast<MachineOperand::MachineOperandType>(
+        MachineOperand::MO_Tombstone));
+  }
+  static unsigned getHashValue(const MachineOperand &MO) {
+    return hash_value(MO);
+  }
+  static bool isEqual(const MachineOperand &LHS, const MachineOperand &RHS) {
+    if (LHS.getType() == MachineOperand::MO_Empty ||
+        LHS.getType() == MachineOperand::MO_Tombstone)
+      return LHS.getType() == RHS.getType();
+    return LHS.isIdenticalTo(RHS);
+  }
+};
+
 inline raw_ostream &operator<<(raw_ostream &OS, const MachineOperand& MO) {
   MO.print(OS, nullptr);
   return OS;
 }
 
   // See friend declaration above. This additional declaration is required in
   // order to compile LLVM with IBM xlC compiler.
   hash_code hash_value(const MachineOperand &MO);
 } // End llvm namespace
 
 #endif

llvm/lib/CodeGen/LiveDebugVariables.cpp

class UserValue {
 
   /// Map of slot indices where this value is live.
   LocMap locInts;
 
   /// Set of interval start indexes that have been trimmed to the
   /// lexical scope.
   SmallSet<SlotIndex, 2> trimmedDefs;
 
-  /// coalesceLocation - After LocNo was changed, check if it has become
-  /// identical to another location, and coalesce them. This may cause LocNo or
-  /// a later location to be erased, but no earlier location will be erased.
-  void coalesceLocation(unsigned LocNo);
-
   /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
                         LiveIntervals &LIS, const TargetInstrInfo &TII);
 
   /// splitLocation - 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);

 
 void LDVImpl::print(raw_ostream &OS) {
   OS << "********** DEBUG VARIABLES **********\n";
   for (unsigned i = 0, e = userValues.size(); i != e; ++i)
     userValues[i]->print(OS, TRI);
 }
 #endif
 
-void UserValue::coalesceLocation(unsigned LocNo) {
-  unsigned KeepLoc = 0;
-  for (unsigned e = locations.size(); KeepLoc != e; ++KeepLoc) {
-    if (KeepLoc == LocNo)
-      continue;
-    if (locations[KeepLoc].isIdenticalTo(locations[LocNo]))
-      break;
-  }
-  // No matches.
-  if (KeepLoc == locations.size())
-    return;
-
-  // Keep the smaller location, erase the larger one.
-  unsigned EraseLoc = LocNo;
-  if (KeepLoc > EraseLoc)
-    std::swap(KeepLoc, EraseLoc);
-  locations.erase(locations.begin() + EraseLoc);
-
-  // Rewrite values.
-  for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
-    unsigned v = I.value();
-    if (v == EraseLoc)
-      I.setValue(KeepLoc);      // Coalesce when possible.
-    else if (v > EraseLoc)
-      I.setValueUnchecked(v-1); // Avoid coalescing with untransformed values.
-  }
-}
-
 void UserValue::mapVirtRegs(LDVImpl *LDV) {
   for (unsigned i = 0, e = locations.size(); i != e; ++i)
     if (locations[i].isReg() &&
         TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
       LDV->mapVirtReg(locations[i].getReg(), this);
 }
 
 UserValue *LDVImpl::getUserValue(const MDNode *Var, const MDNode *Expr,

 }
 
 void LiveDebugVariables::
 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
 }
 
-void
-UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) {
-  // Iterate over locations in reverse makes it easier to handle coalescing.
-  for (unsigned i = locations.size(); i ; --i) {
-    unsigned LocNo = i-1;
-    MachineOperand &Loc = locations[LocNo];
+void UserValue::rewriteLocations(VirtRegMap &VRM,
+                                 const TargetRegisterInfo &TRI) {
+  // Build a set of new locations with new numbers so we can coalesce our
+  // IntervalMap if two vreg intervals collapse to the same physical location.
+  MapVector<MachineOperand, bool> NewLocations;
+  SmallVector<unsigned, 4> LocNoMap(locations.size());
+  for (unsigned I = 0, E = locations.size(); I != E; ++I) {
+    MachineOperand Loc = locations[I];
     // Only virtual registers are rewritten.
-    if (!Loc.isReg() || !Loc.getReg() ||
-        !TargetRegisterInfo::isVirtualRegister(Loc.getReg()))
-      continue;
+    if (Loc.isReg() && Loc.getReg() &&
+        TargetRegisterInfo::isVirtualRegister(Loc.getReg())) {
       unsigned VirtReg = Loc.getReg();
       if (VRM.isAssignedReg(VirtReg) &&
           TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
         // This can create a %noreg operand in rare cases when the sub-register
         // index is no longer available. That means the user value is in a
         // non-existent sub-register, and %noreg is exactly what we want.
         Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
       } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
         // FIXME: Translate SubIdx to a stackslot offset.
         Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
       } else {
         Loc.setReg(0);
         Loc.setSubReg(0);
       }
-    coalesceLocation(LocNo);
+    }
+
+    // Insert the new location and record its number.
+    auto InsertResult = NewLocations.insert({Loc, false});
+    LocNoMap[I] = std::distance(NewLocations.begin(), InsertResult.first);
+  }
+
+  // Rewrite the locations.
+  locations.clear();
+  for (const auto &Pair : NewLocations)
+    locations.push_back(Pair.first);
+
+  // Update the interval map, but only coalesce left, since intervals to the
+  // right use the old location numbers.
+  for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
+    unsigned NewLocNo = LocNoMap[I.value()];
+    I.setValueUnchecked(NewLocNo);
+    I.setStart(I.start());
   }
 }
 
 /// findInsertLocation - Find an iterator for inserting a DBG_VALUE
 /// instruction.
 static MachineBasicBlock::iterator
 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
                    LiveIntervals &LIS) {