[MachineCSE] Improve MachineCSE profitability heuristics for better compile time.

[huihuiz]

Summary

This patch introduces ProfitableSet to cache the results of profitability checks.
If a common subexpression machine instruction (CSMI) has been identified as
profitable before, then this CSMI tend to be profitable later on, unless a machine
instruction (MI) is not profitable for common subexpression elimination.

This fixes pr37277
Compile time went down from 32s to 13s.

[huihuiz]

Not a good solution

lib/CodeGen/MachineCSE.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addPreservedID(MachineLoopInfoID);
       AU.addRequired<MachineDominatorTree>();
       AU.addPreserved<MachineDominatorTree>();
     }
 
     void releaseMemory() override {
       ScopeMap.clear();
       Exps.clear();
+      ProfitableSet.clear();
     }
 
   private:
     using AllocatorTy = RecyclingAllocator<BumpPtrAllocator,
                             ScopedHashTableVal<MachineInstr *, unsigned>>;
     using ScopedHTType =
         ScopedHashTable<MachineInstr *, unsigned, MachineInstrExpressionTrait,
                         AllocatorTy>;
     using ScopeType = ScopedHTType::ScopeTy;
 
     unsigned LookAheadLimit = 0;
     DenseMap<MachineBasicBlock *, ScopeType *> ScopeMap;
     ScopedHTType VNT;
     SmallVector<MachineInstr *, 64> Exps;
     unsigned CurrVN = 0;
+    SmallSet<MachineInstr *, 32> ProfitableSet;
 
     bool PerformTrivialCopyPropagation(MachineInstr *MI,
                                        MachineBasicBlock *MBB);
     bool isPhysDefTriviallyDead(unsigned Reg,
                                 MachineBasicBlock::const_iterator I,
                                 MachineBasicBlock::const_iterator E) const;
     bool hasLivePhysRegDefUses(const MachineInstr *MI,
                                const MachineBasicBlock *MBB,
                                SmallSet<unsigned,8> &PhysRefs,
                                SmallVectorImpl<unsigned> &PhysDefs,
                                bool &PhysUseDef) const;
     bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
                           SmallSet<unsigned,8> &PhysRefs,
                           SmallVectorImpl<unsigned> &PhysDefs,
                           bool &NonLocal) const;
     bool isCSECandidate(MachineInstr *MI);
     bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
                            MachineInstr *CSMI, MachineInstr *MI);
+    bool isMIProfitableToCSE(unsigned Reg, MachineInstr *CSMI, MachineInstr *MI);
     void EnterScope(MachineBasicBlock *MBB);
     void ExitScope(MachineBasicBlock *MBB);
     bool ProcessBlock(MachineBasicBlock *MBB);
     void ExitScopeIfDone(MachineDomTreeNode *Node,
                          DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren);
     bool PerformCSE(MachineDomTreeNode *Node);
   };
 
bool MachineCSE::isCSECandidate(MachineInstr *MI) {
   // Ignore stack guard loads, otherwise the register that holds CSEed value may
   // be spilled and get loaded back with corrupted data.
   if (MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
     return false;
 
   return true;
 }
 
-/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
-/// common expression that defines Reg.
-bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
-                                   MachineInstr *CSMI, MachineInstr *MI) {
-  // FIXME: Heuristics that works around the lack the live range splitting.
-
-  // If CSReg is used at all uses of Reg, CSE should not increase register
-  // pressure of CSReg.
-  bool MayIncreasePressure = true;
-  if (TargetRegisterInfo::isVirtualRegister(CSReg) &&
-      TargetRegisterInfo::isVirtualRegister(Reg)) {
-    MayIncreasePressure = false;
-    SmallPtrSet<MachineInstr*, 8> CSUses;
-    for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
-      CSUses.insert(&MI);
-    }
-    for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
-      if (!CSUses.count(&MI)) {
-        MayIncreasePressure = true;
-        break;
-      }
-    }
-  }
-  if (!MayIncreasePressure) return true;
-
+/// isMIProfitableToCSE - Check if MI is profitable for CSE.
+bool MachineCSE::isMIProfitableToCSE(unsigned Reg, MachineInstr *CSMI, MachineInstr *MI) {
   // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
   // an immediate predecessor. We don't want to increase register pressure and
   // end up causing other computation to be spilled.
   if (TII->isAsCheapAsAMove(*MI)) {
     MachineBasicBlock *CSBB = CSMI->getParent();
     MachineBasicBlock *BB = MI->getParent();
     if (CSBB != BB && !CSBB->isSuccessor(BB))
       return false;
for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
       if (!MI.isCopyLike()) {
         HasNonCopyUse = true;
         break;
       }
     }
     if (!HasNonCopyUse)
       return false;
   }
+  return true;
+}
+
+/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
+/// common expression that defines Reg.
+bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
+                                   MachineInstr *CSMI, MachineInstr *MI) {
+  // FIXME: Heuristics that works around the lack the live range splitting.
+
+  // If CSReg is used at all uses of Reg, CSE should not increase register
+  // pressure of CSReg.
+  bool MayIncreasePressure = true;
+  if (TargetRegisterInfo::isVirtualRegister(CSReg) &&
+      TargetRegisterInfo::isVirtualRegister(Reg)) {
+    MayIncreasePressure = false;
+    SmallPtrSet<MachineInstr*, 8> CSUses;
+    for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
+      CSUses.insert(&MI);
+    }
+    for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
+      if (!CSUses.count(&MI)) {
+        MayIncreasePressure = true;
+        break;
+      }
+    }
+  }
+  if (!MayIncreasePressure) return true;
 
   // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
   // it unless the defined value is already used in the BB of the new use.
   bool HasPHI = false;
   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(CSReg)) {
     HasPHI |= UseMI.isPHI();
     if (UseMI.getParent() == MI->getParent())
       return true;
for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
         --NumDefs;
         continue;
       }
 
       assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
              TargetRegisterInfo::isVirtualRegister(NewReg) &&
              "Do not CSE physical register defs!");
 
+      if (!isMIProfitableToCSE(OldReg, CSMI, MI)) {
+        LLVM_DEBUG(dbgs() << "*** MI Not profitable, avoid CSE!\n");
+        DoCSE = false;
+        break;
+      }
+
+      if (!ProfitableSet.count(CSMI)) {
         if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
           LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
           DoCSE = false;
           break;
         }
+        ProfitableSet.insert(CSMI);
+      }
 
       // Don't perform CSE if the result of the new instruction cannot exist
       // within the constraints (register class, bank, or low-level type) of
       // the old instruction.
       if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
         LLVM_DEBUG(
             dbgs() << "*** Not the same register constraints, avoid CSE!\n");
         DoCSE = false;