From 952c2741599ed492cedd37da895d7e81bc175ab9 Mon Sep 17 00:00:00 2001
From: Nikita Popov <nikita.ppv@gmail.com>
Date: Sun, 5 Apr 2020 17:59:57 +0200
Subject: [PATCH] [RDA] Use TinyPtrVector to store reaching defs (NFCI)

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 def 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.

Differential Revision: https://reviews.llvm.org/D77513
---
 llvm/include/llvm/CodeGen/ReachingDefAnalysis.h | 34 ++++++++++++++++++++++++-
 1 file changed, 33 insertions(+), 1 deletion(-)

diff --git a/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h b/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h
index 608f0df..8def1a6 100644
--- a/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h
+++ b/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h
@@ -23,6 +23,7 @@
 
 #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"
@@ -32,6 +33,37 @@ 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:
@@ -61,7 +93,7 @@ private:
   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
-- 
2.7.4