[RDA] Don't explicitly store outgoing reaching defs (NFCI)

[nikic]

Summary

We currently explicitly store the last reaching def at the end of a basic block. However, this information is already available as the last element in the reaching definitions vector -- they only differ in whether the reaching def is relative to the start or the end of the basic block.

This patch removes the separate MBBOutRegsInfos and instead computes the incoming reaching defs on the fly. For that purpose it does cache the number of (non-debug) instructions in each block.

Assuming D77513 as baseline, this drops the memory requirement per basic block per reg unit from 12 to 8 bytes, which makes for an extra 1% saving on sqlite compilation. It's not completely free (with about 0.05% increase in instructions retired), but that seems like a good tradeoff.

[samparker]

lib/CodeGen/ReachingDefAnalysis.cpp

98

Maybe now would be a good time to encapsulate these MBB details in their own class, instead of several separate vectors and a vector of vectors?

[nikic]

lib/CodeGen/ReachingDefAnalysis.cpp

98

I'm planning to submit one more patch (last one, I promise!) that changes the reaching def storage from MBBNumber => RegUnit => Defs to RegUnit => MBBNumber => Defs, because that allows us not to allocate any storage for register units that are unused in a function. Prototype implementation at https://gist.github.com/nikic/45d4c76338637331bd7048348398833d. Haven't put this up yet, because I didn't measure an actual max-rss improvement with it. I suspect that RDA memory usage is now low enough that the peak memory usage moved somewhere else.

In any case, with that patch the reaching defs storage would not be indexed by MBBNumber first anymore, so it would have to be separate from the NumInsts storage.

[samparker]

lib/CodeGen/ReachingDefAnalysis.cpp

98

Okay. Maybe another way to make this code a bit easier to follow would be to make getIncomingReachingDef take the Unit and the predecessor?

include/llvm/CodeGen/ReachingDefAnalysis.h

private:
   unsigned NumRegUnits;
   /// Instruction that defined each register, relative to the beginning of the
   /// current basic block.  When a LiveRegsDefInfo is used to represent a
   /// live-out register, this value is relative to the end of the basic block,
   /// so it will be a negative number.
   using LiveRegsDefInfo = std::vector<int>;
   LiveRegsDefInfo LiveRegs;
 
-  /// Keeps clearance information for all registers. Note that this
-  /// is different from the usual definition notion of liveness. The CPU
-  /// doesn't care whether or not we consider a register killed.
-  using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>;
-  OutRegsInfoMap MBBOutRegsInfos;
-
   /// Current instruction number.
   /// 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;
 
+  /// Number of non-debug instructions in each basic block.
+  std::vector<int> MBBNumInsts;
+
   /// All reaching defs of a given RegUnit for a given MBB.
   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;
 
public:
   bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg) const;
 
   /// Return whether a MachineInstr could be inserted at MI and safely define
   /// the given register without affecting the program, ignoring any effects
   /// on the provided instructions.
   bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg, InstSet &Ignore) const;
 
 private:
+  /// Get reaching def coming from a predecessor.
+  int getIncomingReachingDef(const MBBRegUnitDefs &Defs, int NumInsts) const;
+
   /// Set up LiveRegs by merging predecessor live-out values.
   void enterBasicBlock(MachineBasicBlock *MBB);
 
   /// Update live-out values.
   void leaveBasicBlock(MachineBasicBlock *MBB);
 
   /// Process he given basic block.
   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);

lib/CodeGen/ReachingDefAnalysis.cpp

 static bool isValidRegDef(const MachineOperand &MO) {
   return isValidReg(MO) && MO.isDef();
 }
 
 static bool isValidRegDefOf(const MachineOperand &MO, int PhysReg) {
   return isValidRegDef(MO) && MO.getReg() == PhysReg;
 }
 
+int ReachingDefAnalysis::getIncomingReachingDef(const MBBRegUnitDefs &Defs,
+                                                int NumInsts) const {
+  if (Defs.empty())
+    return ReachingDefDefaultVal;
+
+  int Def = Defs.back();
+  if (Def != ReachingDefDefaultVal)
+    // Adjust def to be relative to the end of the basic block.
+    Def -= NumInsts;
+
+  return Def;
+}
+
 void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) {
   unsigned MBBNumber = MBB->getNumber();
   assert(MBBNumber < MBBReachingDefs.size() &&
          "Unexpected basic block number.");
   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
 
   // Reset instruction counter in each basic block.
   CurInstr = 0;
for (const auto &LI : MBB->liveins()) {
       }
     }
     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
     return;
   }
 
   // Try to coalesce live-out registers from predecessors.
   for (MachineBasicBlock *pred : MBB->predecessors()) {
-    assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
+    assert(unsigned(pred->getNumber()) < MBBReachingDefs.size() &&
            "Should have pre-allocated MBBInfos for all MBBs");
-    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
-    // Incoming is null if this is a backedge from a BB
-    // we haven't processed yet
-    if (Incoming.empty())
+    const MBBDefsInfo &Defs = MBBReachingDefs[pred->getNumber()];
+    // Defs is null if this is a backedge from a BB we haven't processed yet.
+    if (Defs.empty())
       continue;
 
     // Find the most recent reaching definition from a predecessor.
-    for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
-      LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
+    int NumInsts = MBBNumInsts[pred->getNumber()];
+    for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
+      int Def = getIncomingReachingDef(Defs[Unit], NumInsts);
+      if (Def == ReachingDefDefaultVal)
+        continue;
+
+      LiveRegs[Unit] = std::max(LiveRegs[Unit], Def);
+    }
   }
 
   // Insert the most recent reaching definition we found.
   for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
     if (LiveRegs[Unit] != ReachingDefDefaultVal)
       MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
 }
 
 void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) {
-  assert(!LiveRegs.empty() && "Must enter basic block first.");
   unsigned MBBNumber = MBB->getNumber();
-  assert(MBBNumber < MBBOutRegsInfos.size() &&
-         "Unexpected basic block number.");
-  // Save register clearances at end of MBB - used by enterBasicBlock().
-  MBBOutRegsInfos[MBBNumber] = LiveRegs;
+  assert(MBBNumber < MBBNumInsts.size() && "Unexpected basic block number.");
 
-  // While processing the basic block, we kept `Def` relative to the start
-  // of the basic block for convenience. However, future use of this information
-  // only cares about the clearance from the end of the block, so adjust
-  // everything to be relative to the end of the basic block.
-  for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
-    if (OutLiveReg != ReachingDefDefaultVal)
-      OutLiveReg -= CurInstr;
+  MBBNumInsts[MBBNumber] = CurInstr;
   LiveRegs.clear();
 }
 
 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
   assert(!MI->isDebugInstr() && "Won't process debug instructions");
 
   unsigned MBBNumber = MI->getParent()->getNumber();
   assert(MBBNumber < MBBReachingDefs.size() &&
void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
   ++CurInstr;
 }
 
 void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
   unsigned MBBNumber = MBB->getNumber();
   assert(MBBNumber < MBBReachingDefs.size() &&
          "Unexpected basic block number.");
 
-  // Count number of non-debug instructions for end of block adjustment.
-  int NumInsts = 0;
-  for (const MachineInstr &MI : *MBB)
-    if (!MI.isDebugInstr())
-      NumInsts++;
-
   // When reprocessing a block, the only thing we need to do is check whether
   // there is now a more recent incoming reaching definition from a predecessor.
   for (MachineBasicBlock *pred : MBB->predecessors()) {
-    assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
+    assert(unsigned(pred->getNumber()) < MBBReachingDefs.size() &&
            "Should have pre-allocated MBBInfos for all MBBs");
-    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
-    // Incoming may be empty for dead predecessors.
-    if (Incoming.empty())
+    const MBBDefsInfo &Defs = MBBReachingDefs[pred->getNumber()];
+    // Defs may be empty for dead predecessors.
+    if (Defs.empty())
       continue;
 
+    int NumInsts = MBBNumInsts[pred->getNumber()];
     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
-      int Def = Incoming[Unit];
+      int Def = getIncomingReachingDef(Defs[Unit], NumInsts);
       if (Def == ReachingDefDefaultVal)
         continue;
 
       auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
       if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
         if (*Start >= Def)
           continue;
 
         // Update existing reaching def from predecessor to a more recent one.
         *Start = Def;
       } else {
         // Insert new reaching def from predecessor.
         MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
       }
-
-      // Update reaching def at end of of BB. Keep in mind that these are
-      // adjusted relative to the end of the basic block.
-      if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
-        MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
     }
   }
 }
 
 void ReachingDefAnalysis::processBasicBlock(
     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
   MachineBasicBlock *MBB = TraversedMBB.MBB;
   LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
   init();
   traverse();
   return false;
 }
 
 void ReachingDefAnalysis::releaseMemory() {
   // Clear the internal vectors.
-  MBBOutRegsInfos.clear();
+  MBBNumInsts.clear();
   MBBReachingDefs.clear();
   InstIds.clear();
   LiveRegs.clear();
 }
 
 void ReachingDefAnalysis::reset() {
   releaseMemory();
   init();
   traverse();
 }
 
 void ReachingDefAnalysis::init() {
   NumRegUnits = TRI->getNumRegUnits();
   MBBReachingDefs.resize(MF->getNumBlockIDs());
-  // Initialize the MBBOutRegsInfos
-  MBBOutRegsInfos.resize(MF->getNumBlockIDs());
+  MBBNumInsts.resize(MF->getNumBlockIDs());
   LoopTraversal Traversal;
   TraversedMBBOrder = Traversal.traverse(*MF);
 }
 
 void ReachingDefAnalysis::traverse() {
   // Traverse the basic blocks.
   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
     processBasicBlock(TraversedMBB);