[RDA] Use TinyPtrVector to store reaching defs (NFCI)

[nikic]

Summary

RDA currently uses SmallVector<int, 1> to store reaching definitions. A SmallVector<int, 1> is 24 bytes large, and X86 currently has 164 register units, which means we need 3936 bytes per block. If you have a large function with 1000 blocks, that's already 4MB.

A large fraction of these reg units will not have any reaching defs (say, those corresponding to zmm registers), and many will have just one. A TinyPtrVector serves this use-case much better, as it only needs 8 bytes per register if it has 0 or 1 reaching defs.

As the name implies, TinyPtrVector is designed to work with pointers, so we need to add some boilerplate to treat our reaching defs integers as pointers, using an appropriate encoding. We need to keep the low bit free for tagging, and make sure at least one bit is set to distinguish the null pointer.

[nikic]

Together with the dependent patches, this saves on average 1% max-rss, with 4.5% for sqlite (the tramp3d-v4 regression is not real, ThinLTO has unstable memory usage for that benchmark). We also get on average 0.6% less instructions retired. The memory savings are mainly due to this patch, the compile-time improvements mainly due to the dependent patches.

[samparker]

Every day is a school day for me, many thanks.

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
 #define LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/CodeGen/LoopTraversal.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/InitializePasses.h"
 
 namespace llvm {
 
 class MachineBasicBlock;
 class MachineInstr;
 
+/// Thin wrapper around "int" used to store reaching definitions,
+/// using an encoding that makes it compatible with TinyPtrVector.
+/// The 0th LSB is forced zero (and will be used for pointer union tagging),
+/// The 1st LSB is forced one (to make sure the value is non-zero).
+class ReachingDef {
+  uintptr_t Encoded;
+  friend struct PointerLikeTypeTraits<ReachingDef>;
+  explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {}
+
+public:
+  ReachingDef(int Instr) : Encoded((Instr << 2) | 2) {}
+  operator int() const { return ((int) Encoded) >> 2; }
+};
+
+template<>
+struct PointerLikeTypeTraits<ReachingDef> {
+  static constexpr int NumLowBitsAvailable = 1;
+
+  static inline void *getAsVoidPointer(const ReachingDef &RD) {
+    return reinterpret_cast<void *>(RD.Encoded);
+  }
+
+  static inline ReachingDef getFromVoidPointer(void *P) {
+    return ReachingDef(reinterpret_cast<uintptr_t>(P));
+  }
+
+  static inline ReachingDef getFromVoidPointer(const void *P) {
+    return ReachingDef(reinterpret_cast<uintptr_t>(P));
+  }
+};
+
 /// This class provides the reaching def analysis.
 class ReachingDefAnalysis : public MachineFunctionPass {
 private:
   MachineFunction *MF;
   const TargetRegisterInfo *TRI;
   LoopTraversal::TraversalOrder TraversedMBBOrder;
   unsigned NumRegUnits;
   /// Instruction that defined each register, relative to the beginning of the
private:
   /// The first instruction in each basic block is 0.
   int CurInstr;
 
   /// Maps instructions to their instruction Ids, relative to the beginning of
   /// their basic blocks.
   DenseMap<MachineInstr *, int> InstIds;
 
   /// All reaching defs of a given RegUnit for a given MBB.
-  using MBBRegUnitDefs = SmallVector<int, 1>;
+  using MBBRegUnitDefs = TinyPtrVector<ReachingDef>;
   /// All reaching defs of all reg units for a given MBB
   using MBBDefsInfo = std::vector<MBBRegUnitDefs>;
   /// All reaching defs of all reg units for a all MBBs
   using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>;
   MBBReachingDefsInfo MBBReachingDefs;
 
   /// Default values are 'nothing happened a long time ago'.
   const int ReachingDefDefaultVal = -(1 << 20);