[DebugInfo][InstrRef][NFC] Use DenseMaps where we can, use more efficient ValueIDNum repr

[jmorse]

Summary

This is a "misc" patch, making various tweaks to speed InstrRefBasedLDV up. I've been testing it on the compile-time-tracking project website, and it gets back something like 2% of instructions retired. There's still a non-trivial cost of instruction referencing, this patch eases the matter. Things done:

• Adjusting the default sizes of some densemaps / smallvectors, and calling reserve() early when we know how large they should be,
• Allowing LocIdx (the sequential location numbers) to be densemap keys,
• Allowing ValueIDNums to be densemap keys,
• Adjusting the representation of ValueIDNums to sharing a union with a uint64_t.

The latter is the most interesting: ValueIDNum is supposed to be a value type, but clang doesn't condense the comparison functions down to a single value comparison. Maybe I was doing something wrong, but explicitly having the bitfield as part of a union lets us do it manually.

Replacing other containers with dense ones is fairly straight forwards. I have to introduce a intermediate variable during an assignment, because DenseMap[A] = DenseMap[B] isn't always safe if one of those operator[]'s causes the container to reallocate.

Strangest of all: replacing the std::map in TransferTracker::loadInLocs with a DenseMap causes a performance loss, so I haven't done it. I still need to dig into why std::map is faster in this case.

[Orlando]

LGTM - please clang-format.

Strangest of all: replacing the std::map in TransferTracker::loadInLocs with a DenseMap causes a performance loss

Some maybe-useless speculation: Perhaps the current ValueIDNum hash is poor / causing high number of collisions? std::map (as opposed to DenseMap and std::unorderd_map) is ordered. Maybe in this case, the ordered search is quicker than a hash table lookup or something like that?

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

119

backed -> packed?

1043

Curious if you have you tried experimenting with this hash function at all?

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

1043

I tried the standard llvm hash_code, which caused CTMark to be slower. Looking at the assembly, hash_code adds three or four instructions, and that's all. This difference is for the transition of hash_code to nothing, and shows a speedup:

http://llvm-compile-time-tracker.com/compare.php?from=d6553eab88c71e1d797163295750f2d1bc3d86ba&to=cfe24102d48687ccb7fbcc8311488bb3a87010bb&stat=instructions

IMO, the distribution is (seemingly) good enough already.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

 
 public:
 #define NUM_LOC_BITS 24
   LocIdx(unsigned L) : Location(L) {
     assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits");
   }
 
   static LocIdx MakeIllegalLoc() { return LocIdx(); }
+  static LocIdx MakeTombstoneLoc() {
+    LocIdx L = LocIdx();
+    --L.Location;
+    return L;
+  }
 
   bool isIllegal() const { return Location == UINT_MAX; }
 
   uint64_t asU64() const { return Location; }
 
   bool operator==(unsigned L) const { return Location == L; }
 
   bool operator==(const LocIdx &L) const { return Location == L.Location; }

 /// where the value is defined, although there may be no corresponding machine
 /// operand for it (ex: regmasks clobbering values). The instructions are
 /// one-based, and definitions that are PHIs have instruction number zero.
 ///
 /// The obvious limits of a 1M block function or 1M instruction blocks are
 /// problematic; but by that point we should probably have bailed out of
 /// trying to analyse the function.
 class ValueIDNum {
-  uint64_t BlockNo : 20;         /// The block where the def happens.
-  uint64_t InstNo : 20;          /// The Instruction where the def happens.
-                                 /// One based, is distance from start of block.
-  uint64_t LocNo : NUM_LOC_BITS; /// The machine location where the def happens.
+  union {
+    struct {
+      uint64_t BlockNo : 20; /// The block where the def happens.
+      uint64_t InstNo : 20;  /// The Instruction where the def happens.
+      uint64_t LocNo
+          : NUM_LOC_BITS; /// The machine location where the def happens.
+    } s;
+    uint64_t Value;
+  } u;
+
+  static_assert(sizeof(u) == 8, "Badly packed ValueIDNum?");
 
 public:
   // Default-initialize to EmptyValue. This is necessary to make IndexedMaps
   // of values to work.
-  ValueIDNum() : BlockNo(0xFFFFF), InstNo(0xFFFFF), LocNo(0xFFFFFF) {}
-
-  ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
-      : BlockNo(Block), InstNo(Inst), LocNo(Loc) {}
+  ValueIDNum() { u.Value = EmptyValue.asU64(); }
 
-  ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
-      : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) {}
+  ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) {
+    u.s = {Block, Inst, Loc};
+  }
 
-  uint64_t getBlock() const { return BlockNo; }
-  uint64_t getInst() const { return InstNo; }
-  uint64_t getLoc() const { return LocNo; }
-  bool isPHI() const { return InstNo == 0; }
-
-  uint64_t asU64() const {
-    uint64_t TmpBlock = BlockNo;
-    uint64_t TmpInst = InstNo;
-    return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS | LocNo;
+  ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) {
+    u.s = {Block, Inst, Loc.asU64()};
   }
 
+  uint64_t getBlock() const { return u.s.BlockNo; }
+  uint64_t getInst() const { return u.s.InstNo; }
+  uint64_t getLoc() const { return u.s.LocNo; }
+  bool isPHI() const { return u.s.InstNo == 0; }
+
+  uint64_t asU64() const { return u.Value; }
+
   static ValueIDNum fromU64(uint64_t v) {
-    uint64_t L = (v & 0x3FFF);
-    return {v >> 44ull, ((v >> NUM_LOC_BITS) & 0xFFFFF), L};
+    ValueIDNum Val;
+    Val.u.Value = v;
+    return Val;
   }
 
   bool operator<(const ValueIDNum &Other) const {
     return asU64() < Other.asU64();
   }
 
   bool operator==(const ValueIDNum &Other) const {
-    return std::tie(BlockNo, InstNo, LocNo) ==
-           std::tie(Other.BlockNo, Other.InstNo, Other.LocNo);
+    return u.Value == Other.u.Value;
   }
 
   bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); }
 
   std::string asString(const std::string &mlocname) const {
     return Twine("Value{bb: ")
-        .concat(Twine(BlockNo).concat(
-            Twine(", inst: ")
-                .concat((InstNo ? Twine(InstNo) : Twine("live-in"))
-                            .concat(Twine(", loc: ").concat(Twine(mlocname)))
+        .concat(Twine(u.s.BlockNo)
+                    .concat(Twine(", inst: ")
+                                .concat((u.s.InstNo ? Twine(u.s.InstNo)
+                                                    : Twine("live-in"))
+                                            .concat(Twine(", loc: ").concat(
+                                                Twine(mlocname)))
                                             .concat(Twine("}")))))
         .str();
   }
 
   static ValueIDNum EmptyValue;
+  static ValueIDNum TombstoneValue;
 };
 
 /// Thin wrapper around an integer -- designed to give more type safety to
 /// spill location numbers.
 class SpillLocationNo {
 public:
   explicit SpillLocationNo(unsigned SpillNo) : SpillNo(SpillNo) {}
   unsigned SpillNo;
public:
 
   // Helper while building OverlapMap, a map of all fragments seen for a given
   // DILocalVariable.
   using VarToFragments =
       DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
 
   /// Machine location/value transfer function, a mapping of which locations
   /// are assigned which new values.
-  using MLocTransferMap = std::map<LocIdx, ValueIDNum>;
+  using MLocTransferMap = SmallDenseMap<LocIdx, ValueIDNum>;
 
   /// Live in/out structure for the variable values: a per-block map of
   /// variables to their values.
   using LiveIdxT = DenseMap<const MachineBasicBlock *, DbgValue *>;
 
   using VarAndLoc = std::pair<DebugVariable, DbgValue>;
 
   /// Type for a live-in value: the predecessor block, and its value.
return MemOperand->isStore() &&
            && !MemOperand->getPseudoValue()->isAliased(MFI);
   }
 
   Optional<LocIdx> findLocationForMemOperand(const MachineInstr &MI);
 };
 
 } // namespace LiveDebugValues
 
+namespace llvm {
+using namespace LiveDebugValues;
+
+template <> struct DenseMapInfo<LocIdx> {
+  static inline LocIdx getEmptyKey() { return LocIdx::MakeIllegalLoc(); }
+  static inline LocIdx getTombstoneKey() { return LocIdx::MakeTombstoneLoc(); }
+
+  static unsigned getHashValue(const LocIdx &Loc) { return Loc.asU64(); }
+
+  static bool isEqual(const LocIdx &A, const LocIdx &B) { return A == B; }
+};
+
+template <> struct DenseMapInfo<ValueIDNum> {
+  static inline ValueIDNum getEmptyKey() { return ValueIDNum::EmptyValue; }
+  static inline ValueIDNum getTombstoneKey() {
+    return ValueIDNum::TombstoneValue;
+  }
+
+  static unsigned getHashValue(const ValueIDNum &Val) { return Val.asU64(); }
+
+  static bool isEqual(const ValueIDNum &A, const ValueIDNum &B) {
+    return A == B;
+  }
+};
+
+} // end namespace llvm
+
 #endif /* LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H */

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

public:
 
   /// Collection of transfers (DBG_VALUEs) to be inserted.
   SmallVector<Transfer, 32> Transfers;
 
   /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
   /// between TransferTrackers view of variable locations and MLocTrackers. For
   /// example, MLocTracker observes all clobbers, but TransferTracker lazily
   /// does not.
-  std::vector<ValueIDNum> VarLocs;
+  SmallVector<ValueIDNum, 32> VarLocs;
 
   /// Map from LocIdxes to which DebugVariables are based that location.
   /// Mantained while stepping through the block. Not accurate if
   /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
-  std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;
+  DenseMap<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;
 
   /// Map from DebugVariable to it's current location and qualifying meta
   /// information. To be used in conjunction with ActiveMLocs to construct
   /// enough information for the DBG_VALUEs for a particular LocIdx.
   DenseMap<DebugVariable, LocAndProperties> ActiveVLocs;
 
   /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
   SmallVector<MachineInstr *, 4> PendingDbgValues;
auto isCalleeSaved = [&](LocIdx L) {
       for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
         if (CalleeSavedRegs.test(*RAI))
           return true;
       return false;
     };
 
     // Map of the preferred location for each value.
     std::map<ValueIDNum, LocIdx> ValueToLoc;
+    ActiveMLocs.reserve(VLocs.size());
+    ActiveVLocs.reserve(VLocs.size());
 
     // Produce a map of value numbers to the current machine locs they live
     // in. When emulating VarLocBasedImpl, there should only be one
     // location; when not, we get to pick.
     for (auto Location : MTracker->locations()) {
       LocIdx Idx = Location.Idx;
       ValueIDNum &VNum = MLocs[Idx.asU64()];
       VarLocs.push_back(VNum);
void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
 
     // We lazily track what locations have which values; if we've found a new
     // location for the clobbered value, remember it.
     if (NewLoc)
       VarLocs[NewLoc->asU64()] = OldValue;
 
     flushDbgValues(Pos, nullptr);
 
+    // Re-find ActiveMLocIt, iterator could have been invalidated.
+    ActiveMLocIt = ActiveMLocs.find(MLoc);
     ActiveMLocIt->second.clear();
   }
 
   /// Transfer variables based on \p Src to be based on \p Dst. This handles
   /// both register copies as well as spills and restores. Creates DBG_VALUEs
   /// describing the movement.
   void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
     // Does Src still contain the value num we expect? If not, it's been
     // clobbered in the meantime, and our variable locations are stale.
     if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src))
       return;
 
     // assert(ActiveMLocs[Dst].size() == 0);
     //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
-    ActiveMLocs[Dst] = ActiveMLocs[Src];
+
+    // Move set of active variables from one location to another.
+    auto MovingVars = ActiveMLocs[Src];
+    ActiveMLocs[Dst] = MovingVars;
     VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
 
     // For each variable based on Src; create a location at Dst.
-    for (auto &Var : ActiveMLocs[Src]) {
+    for (auto &Var : MovingVars) {
       auto ActiveVLocIt = ActiveVLocs.find(Var);
       assert(ActiveVLocIt != ActiveVLocs.end());
       ActiveVLocIt->second.Loc = Dst;
 
       MachineInstr *MI =
           MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
       PendingDbgValues.push_back(MI);
     }
public:
   }
 };
 
 //===----------------------------------------------------------------------===//
 //            Implementation
 //===----------------------------------------------------------------------===//
 
 ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};
+ValueIDNum ValueIDNum::TombstoneValue = {UINT_MAX, UINT_MAX, UINT_MAX - 1};
 
 #ifndef NDEBUG
 void DbgValue::dump(const MLocTracker *MTrack) const {
   if (Kind == Const) {
     MO->dump();
   } else if (Kind == NoVal) {
     dbgs() << "NoVal(" << BlockNo << ")";
   } else if (Kind == VPHI) {

llvm/unittests/CodeGen/InstrRefLDVTest.cpp

TEST_F(InstrRefLDVTest, MLocSingleBlock) {
 
   // Set up live-in and live-out tables for this function: two locations (we
   // add one later) in a single block.
   ValueIDNum InLocs[2], OutLocs[2];
   ValueIDNum *InLocsPtr[1] = {&InLocs[0]};
   ValueIDNum *OutLocsPtr[1] = {&OutLocs[0]};
 
   // Transfer function: nothing.
-  SmallVector<MLocTransferMap, 1> TransferFunc = {{}};
+  SmallVector<MLocTransferMap, 1> TransferFunc;
+  TransferFunc.resize(1);
 
   // Try and build value maps...
   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
 
   // The result should be that RSP is marked as a live-in-PHI -- this represents
   // an argument. And as there's no transfer function, the block live-out should
   // be the same.
   EXPECT_EQ(InLocs[0], ValueIDNum(0, 0, RspLoc));