[MachineCSE] Add a threshold to avoid spending too much time in isProfitableToCSE

[pzheng]

Summary

Currently, it can become extremely costly to compute MayIncreasePressure if the
size of CSUses turns out to be very large. In that case, it's no longer cost
effective to keep computing MayIncreasePressure. Therefore, to limit the amount
of time spent in isProfitableToCSE, we simply conservatively assume
MayIncreasePressure if the size of CSUses is too large. This can reduce overall
compile time by 30% for some benchmarks.

llvm/lib/CodeGen/MachineCSE.cpp

 STATISTIC(NumPREs,      "Number of partial redundant expression"
                         " transformed to fully redundant");
 STATISTIC(NumPhysCSEs,
           "Number of physreg referencing common subexpr eliminated");
 STATISTIC(NumCrossBBCSEs,
           "Number of cross-MBB physreg referencing CS eliminated");
 STATISTIC(NumCommutes,  "Number of copies coalesced after commuting");
 
+// Threshold to avoid excessive cost to compute isProfitableToCSE.
+static cl::opt<int>
+    CSUsesThreshold("csuses-threshold", cl::Hidden, cl::init(1024),
+                    cl::desc("Threshold for the size of CSUses"));
+
 namespace {
 
   class MachineCSE : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     AliasAnalysis *AA;
     MachineDominatorTree *DT;
     MachineRegisterInfo *MRI;
bool MachineCSE::isProfitableToCSE(Register CSReg, Register Reg,
   // 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 (Register::isVirtualRegister(CSReg) && Register::isVirtualRegister(Reg)) {
     MayIncreasePressure = false;
     SmallPtrSet<MachineInstr*, 8> CSUses;
+    int NumOfUses = 0;
     for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
       CSUses.insert(&MI);
+      // Too costly to compute if NumOfUses is very large. Conservatively assume
+      // MayIncreasePressure to avoid spending too much time here.
+      if (++NumOfUses > CSUsesThreshold) {
+        MayIncreasePressure = true;
+        break;
+      }
     }
+    if (!MayIncreasePressure)
       for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
         if (!CSUses.count(&MI)) {
           MayIncreasePressure = true;
           break;
         }
       }
   }
   if (!MayIncreasePressure) return true;
 
   // 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 *BB = MI->getParent();