[PHIElimination] Compile time optimization for huge functions.

[jonpa]

Summary

This is a compile-time optimization for PHIElimination (splitting of critical edges), which was reported at https://bugs.llvm.org/show_bug.cgi?id=44249. As discussed there, the way to remedy the slowdowns with huge functions seems to be to pre-compute the live-in registers for each MBB in an efficient way in PHIElimination.cpp and then pass that information along to LiveVariabless::addNewBlock().

The reported test case there achieves a significant improved compile time with this patch:

TRUNK:

time clang -O3 -march=z10 crash0.i -c -ftime-report |& grep "Eliminate PHI" 
36.5362 ( 46.1%)   0.0137 (  3.2%)  36.5499 ( 45.8%)  36.5584 ( 45.8%)  Eliminate PHI nodes for register allocation 
real    1m20.967s
user    1m19.779s
sys     0m0.623s 

time clang -O3 -target x86_64 crash0.i -c -ftime-report |& grep "Eliminate PHI"
0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0028 (  0.1%)  Eliminate PHI nodes for register allocation
real    0m3.851s
user    0m3.604s
sys     0m0.101s 
 
PATCHED: 
 
time clang -O3 -march=z10 crash0.i -c -ftime-report |& grep "Eliminate PHI"
0.0399 (  0.1%)   0.0001 (  0.0%)   0.0400 (  0.1%)   0.0391 (  0.1%)  Eliminate PHI nodes for register allocation
real    0m43.473s
user    0m42.967s
sys     0m0.497s 
  
time clang -O3 -target x86_64 crash0.i -c -ftime-report |& grep "Eliminate PHI"
0.0000 (  0.0%)   0.0000 (  0.0%)   0.0000 (  0.0%)   0.0010 (  0.0%)  Eliminate PHI nodes for register allocation
real    0m3.645s  
user    0m3.559s 
sys     0m0.090s

There is still a big slowdown for SystemZ, but the PHIElimination slowdown is gone. I would guess that this is an improvement on any given target where the number of virtual registers and basic blocks are great enough, but I have not tried this.

• Is it OK to trust that MBB numbers don't change, or would it be best to use a map from MachineBasicBlock* to its SparseBitVector?

• I choose to store the index of the virtual register instead of the register number, since that intuitively seems wiser (starting at 0), but curious if that's an improvement (but it's just one extra line of code...)

• SparseBitVector was proven faster than BitVector...

[bjope]

llvm/lib/CodeGen/PHIElimination.cpp

166

I think it is a little bit ugly to do this after setting leaveSSA above.
My suggestion is to postpone the leaveSSA toggling until after populating the LiveInSets (considering that this code relies on still having ssa form).

177

This might needs an explanatory code comment.

If there is more than one kill, then it isn't killed in DefMBB => add to liveinset. (Ok!)

Else, if there is one kill and it isn't DefMBB => add to liveinset. (Ok!)

What I think is missing here is a guard to avoid the Kills.front() deref when there are no kills (may happen when a phi is the last use).

[jonpa]

Thanks for review!

Patch updated - see inline comments.

llvm/lib/CodeGen/PHIElimination.cpp

166

OK - moved it down.

177

Added comment.

What I think is missing here is a guard to avoid the Kills.front() deref when there are no kills (may happen when a phi is the last use).

Ah, right!

[jonpa]

Ping!

This patch is very convincing to me since I saw just last week dozens and dozens of huge csmith programs suffering from significant slow-downs where PHI elimination was a big part of it. PHI Elim can take more than a minute without this patch, while with this patch all of those test cases do not spend much time in PHIElim anymore.

I have only tried this on SystemZ, but it really should be target independent. Who could try this on some other architecture as well (I could provide huge csmith programs if needed)?

[bjope]

LGTM

[qcolombet]

LGTM with a nit. Use a reference instead of a pointer (or check the pointer and fallback to the old addNewBlock when the pointer is nullptr)

llvm/lib/CodeGen/LiveVariables.cpp

820

Shouldn't you check that LiveInSets is not nullptr?
Otherwise, use a reference in the API.

[jonpa]

llvm/lib/CodeGen/LiveVariables.cpp

820

Changed the LiveInSets argument to LiveVariables::addNewBlock() to be a reference instead.

llvm/include/llvm/CodeGen/LiveVariables.h

public:
   /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All
   /// variables that are live out of DomBB and live into SuccBB will be marked
   /// as passing live through BB. This method assumes that the machine code is
   /// still in SSA form.
   void addNewBlock(MachineBasicBlock *BB,
                    MachineBasicBlock *DomBB,
                    MachineBasicBlock *SuccBB);
 
+  void addNewBlock(MachineBasicBlock *BB,
+                   MachineBasicBlock *DomBB,
+                   MachineBasicBlock *SuccBB,
+                   std::vector<SparseBitVector<>> &LiveInSets);
+
   /// isPHIJoin - Return true if Reg is a phi join register.
   bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); }
 
   /// setPHIJoin - Mark Reg as a phi join register.
   void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); }
 };
 
 } // End llvm namespace
 
 #endif

llvm/include/llvm/CodeGen/MachineBasicBlock.h

 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/ADT/simple_ilist.h"
+#include "llvm/ADT/SparseBitVector.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBundleIterator.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/MC/LaneBitmask.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/Printable.h"
 #include <cassert>
bool isEHScopeReturnBlock() const {
     return !empty() && back().isEHScopeReturn();
   }
 
   /// Split the critical edge from this block to the given successor block, and
   /// return the newly created block, or null if splitting is not possible.
   ///
   /// This function updates LiveVariables, MachineDominatorTree, and
   /// MachineLoopInfo, as applicable.
-  MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P);
+  MachineBasicBlock *
+  SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P,
+                    std::vector<SparseBitVector<>> *LiveInSets = nullptr);
 
   /// Check if the edge between this block and the given successor \p
   /// Succ, can be split. If this returns true a subsequent call to
   /// SplitCriticalEdge is guaranteed to return a valid basic block if
   /// no changes occurred in the meantime.
   bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const;
 
   void pop_front() { Insts.pop_front(); }

llvm/lib/CodeGen/LiveVariables.cpp

for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 
     // If the register is either killed in or live through SuccBB it's also live
     // through BB.
     VarInfo &VI = getVarInfo(Reg);
     if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber()))
       VI.AliveBlocks.set(NumNew);
   }
 }
+
+/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
+/// variables that are live out of DomBB will be marked as passing live through
+/// BB. LiveInSets[BB] is *not* updated (because it is not needed during
+/// PHIElimination).
+void LiveVariables::addNewBlock(MachineBasicBlock *BB,
+                                MachineBasicBlock *DomBB,
+                                MachineBasicBlock *SuccBB,
+                                std::vector<SparseBitVector<>> &LiveInSets) {
+  const unsigned NumNew = BB->getNumber();
+
+  SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()];
+  for (auto R = BV.begin(), E = BV.end(); R != E; R++) {
+    unsigned VirtReg = Register::index2VirtReg(*R);
+    LiveVariables::VarInfo &VI = getVarInfo(VirtReg);
+    VI.AliveBlocks.set(NumNew);
+  }
+  // All registers used by PHI nodes in SuccBB must be live through BB.
+  for (MachineBasicBlock::iterator BBI = SuccBB->begin(),
+         BBE = SuccBB->end();
+       BBI != BBE && BBI->isPHI(); ++BBI) {
+    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
+      if (BBI->getOperand(i + 1).getMBB() == BB)
+        getVarInfo(BBI->getOperand(i).getReg())
+          .AliveBlocks.set(NumNew);
+  }
+}

llvm/lib/CodeGen/MachineBasicBlock.cpp

MachineBasicBlock *MachineBasicBlock::getFallThrough() {
   // through.
   return (FBB == nullptr) ? &*Fallthrough : nullptr;
 }
 
 bool MachineBasicBlock::canFallThrough() {
   return getFallThrough() != nullptr;
 }
 
-MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ,
-                                                        Pass &P) {
+MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(
+    MachineBasicBlock *Succ, Pass &P,
+    std::vector<SparseBitVector<>> *LiveInSets) {
   if (!canSplitCriticalEdge(Succ))
     return nullptr;
 
   MachineFunction *MF = getParent();
   DebugLoc DL;  // FIXME: this is nowhere
 
   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
   MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
while (!KilledRegs.empty()) {
           continue;
         if (Register::isVirtualRegister(Reg))
           LV->getVarInfo(Reg).Kills.push_back(&*I);
         LLVM_DEBUG(dbgs() << "Restored terminator kill: " << *I);
         break;
       }
     }
     // Update relevant live-through information.
+    if (LiveInSets != nullptr)
+      LV->addNewBlock(NMBB, this, Succ, *LiveInSets);
+    else
       LV->addNewBlock(NMBB, this, Succ);
   }
 
   if (LIS) {
     // After splitting the edge and updating SlotIndexes, live intervals may be
     // in one of two situations, depending on whether this block was the last in
     // the function. If the original block was the last in the function, all
     // live intervals will end prior to the beginning of the new split block. If
     // the original block was not at the end of the function, all live intervals

llvm/lib/CodeGen/PHIElimination.cpp

private:
     /// here. In particular, we want to map the number of uses of a virtual
     /// register which is used in a PHI node. We map that to the BB the
     /// vreg is coming from. This is used later to determine when the vreg
     /// is killed in the BB.
     void analyzePHINodes(const MachineFunction& MF);
 
     /// Split critical edges where necessary for good coalescer performance.
     bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
-                       MachineLoopInfo *MLI);
+                       MachineLoopInfo *MLI,
+                       std::vector<SparseBitVector<>> *LiveInSets);
 
     // These functions are temporary abstractions around LiveVariables and
     // LiveIntervals, so they can go away when LiveVariables does.
     bool isLiveIn(unsigned Reg, const MachineBasicBlock *MBB);
     bool isLiveOutPastPHIs(unsigned Reg, const MachineBasicBlock *MBB);
 
     using BBVRegPair = std::pair<unsigned, unsigned>;
     using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;

 
 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
   MRI = &MF.getRegInfo();
   LV = getAnalysisIfAvailable<LiveVariables>();
   LIS = getAnalysisIfAvailable<LiveIntervals>();
 
   bool Changed = false;
 
-  // This pass takes the function out of SSA form.
-  MRI->leaveSSA();
-
   // Split critical edges to help the coalescer.
   if (!DisableEdgeSplitting && (LV || LIS)) {
+    // A set of live-in regs for each MBB which is used to update LV
+    // efficiently also with large functions.
+    std::vector<SparseBitVector<>> LiveInSets;
+    if (LV) {
+      LiveInSets.resize(MF.size());
+      for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
+        // Set the bit for this register for each MBB where it is
+        // live-through or live-in (killed).
+        unsigned VirtReg = Register::index2VirtReg(Index);
+        MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
+        if (!DefMI)
+          continue;
+        LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
+        SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
+        SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
+        while (AliveBlockItr != EndItr) {
+          unsigned BlockNum = *(AliveBlockItr++);
+          LiveInSets[BlockNum].set(Index);
+        }
+        // The register is live into an MBB in which it is killed but not
+        // defined. See comment for VarInfo in LiveVariables.h.
+        MachineBasicBlock *DefMBB = DefMI->getParent();
+        if (VI.Kills.size() > 1 ||
+            (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
+          for (auto *MI : VI.Kills)
+            LiveInSets[MI->getParent()->getNumber()].set(Index);
+      }
+    }
+
     MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     for (auto &MBB : MF)
-      Changed |= SplitPHIEdges(MF, MBB, MLI);
+      Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr));
   }
 
+  // This pass takes the function out of SSA form.
+  MRI->leaveSSA();
+
   // Populate VRegPHIUseCount
   analyzePHINodes(MF);
 
   // Eliminate PHI instructions by inserting copies into predecessor blocks.
   for (auto &MBB : MF)
     Changed |= EliminatePHINodes(MF, MBB);
 
   // Remove dead IMPLICIT_DEF instructions.
for (const auto &BBI : MBB) {
       for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
         ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
                                      BBI.getOperand(i).getReg())];
     }
 }
 
 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
                                    MachineBasicBlock &MBB,
-                                   MachineLoopInfo *MLI) {
+                                   MachineLoopInfo *MLI,
+                                   std::vector<SparseBitVector<>> *LiveInSets) {
   if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
     return false;   // Quick exit for basic blocks without PHIs.
 
   const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
   bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
 
   bool Changed = false;
   for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
         // This edge could be entering a loop, exiting a loop, or it could be
         // both: Jumping directly form one loop to the header of a sibling
         // loop.
         // Split unless this edge is entering CurLoop from an outer loop.
         ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
       }
       if (!ShouldSplit && !SplitAllCriticalEdges)
         continue;
-      if (!PreMBB->SplitCriticalEdge(&MBB, *this)) {
+      if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
         LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
         continue;
       }
       Changed = true;
       ++NumCriticalEdgesSplit;
     }
   }
   return Changed;