[RDA] Avoid full reprocessing of blocks in loops (NFCI)

[nikic]

Summary

RDA sometimes needs to visit blocks twice, to take into account reaching defs coming in along loop back edges. Currently it handles repeated visitation the same way as usual, which means that it will scan through all instructions and their reg unit defs again. Not only is this very inefficient, it also means that all reaching defs in loops are going to be inserted twice.

We can do much better than this. The only thing we need to handle is a new reaching def from a predecessor, which either needs to be prepended to the reaching definitions (if there was no reaching def from a predecessor), or needs to replace an existing predecessor reaching def, if it is more recent. Since D77508 we only store the most recent predecessor reaching def, so that's the only one that may need updating.

This also has the nice side-effect that reaching definitions are now automatically sorted and unique, so drop the llvm::sort() call in favor of an assertion.

[samparker]

lib/CodeGen/ReachingDefAnalysis.cpp

157 ↗

(On Diff #255189)

It would be nice to reduce the indentation and just continue on the inverse. And maybe also continue when MBBReachingDefs[MBBNumber][Unit] is empty instead of comparing iterators below?

[nikic]

Reduce indentation with early continue. Make NumInsts the number of non-debug instructions (as processDef is skipped for debug instructions).

[nikic]

lib/CodeGen/ReachingDefAnalysis.cpp

157 ↗

(On Diff #255189)

I've added the early continue for the ReachingDefDefaultVal check. I don't think the same can be done if MBBReachingDefs[MBBNumber][Unit] is empty, because we do need to insert a reaching def (and possibly update the end of block reaching def) in that case.

[samparker]

Okay, thanks for doing this. LGTM.

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

private:
   void enterBasicBlock(MachineBasicBlock *MBB);
 
   /// Update live-out values.
   void leaveBasicBlock(MachineBasicBlock *MBB);
 
   /// Process he given basic block.
   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
+  /// Process block that is part of a loop again.
+  void reprocessBasicBlock(MachineBasicBlock *MBB);
+
   /// Update def-ages for registers defined by MI.
   /// Also break dependencies on partial defs and undef uses.
   void processDefs(MachineInstr *);
 
   /// Utility function for isSafeToMoveForwards/Backwards.
   template<typename Iterator>
   bool isSafeToMove(MachineInstr *From, MachineInstr *To) const;
 

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
         MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
       }
     }
   }
   InstIds[MI] = CurInstr;
   ++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() &&
+           "Should have pre-allocated MBBInfos for all MBBs");
+    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
+    // Incoming may be empty for dead predecessors.
+    if (Incoming.empty())
+      continue;
+
+    for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
+      int Def = Incoming[Unit];
+      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)
                     << (!TraversedMBB.IsDone ? ": incomplete\n"
                                              : ": all preds known\n"));
 
+  if (!TraversedMBB.PrimaryPass) {
+    // Reprocess MBB that is part of a loop.
+    reprocessBasicBlock(MBB);
+    return;
+  }
+
   enterBasicBlock(MBB);
   for (MachineInstr &MI : *MBB) {
     if (!MI.isDebugInstr())
       processDefs(&MI);
   }
   leaveBasicBlock(MBB);
 }
 
void ReachingDefAnalysis::init() {
   LoopTraversal Traversal;
   TraversedMBBOrder = Traversal.traverse(*MF);
 }
 
 void ReachingDefAnalysis::traverse() {
   // Traverse the basic blocks.
   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
     processBasicBlock(TraversedMBB);
-  // Sorting all reaching defs found for a ceartin reg unit in a given BB.
+#ifndef NDEBUG
+  // Make sure reaching defs are sorted and unique.
   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
-    for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
-      llvm::sort(RegUnitDefs);
+    for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
+      int LastDef = ReachingDefDefaultVal;
+      for (int Def : RegUnitDefs) {
+        assert(Def > LastDef && "Defs must be sorted and unique");
+        LastDef = Def;
+      }
+    }
   }
+#endif
 }
 
 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) const {
   assert(InstIds.count(MI) && "Unexpected machine instuction.");
   int InstId = InstIds.lookup(MI);
   int DefRes = ReachingDefDefaultVal;
   unsigned MBBNumber = MI->getParent()->getNumber();
   assert(MBBNumber < MBBReachingDefs.size() &&