[EarlyCSE & MSSA] Cap the clobbering calls in EarlyCSE.

[asbirlea]

Summary

Unlimitted number of calls to getClobberingAccess can lead to high
compile times in pathological cases.
Limitting getClobberingAccess to a fairly high number. Can be adjusted
based on users/need.
Note: this is the only user of MemorySSA currently enabled by default.
The same handling exists in LICM (disabled atm). As MemorySSA gains more
users, this logic of capping will need to move inside MemorySSA.

[srhines]

Very cool, thank you for coming up with a great way to improve this case.

[george.burgess.iv]

Thanks for doing this! Just two nits for you :)

lib/Transforms/Scalar/EarlyCSE.cpp

672 ↗

(On Diff #186899)

Please add a TODO with notes about moving this to MSSA and maybe the link to the motivating patch (https://reviews.llvm.org/D56720)

1206 ↗

(On Diff #186899)

Should we be resetting ClobberCounter here, as well?

[asbirlea]

lib/Transforms/Scalar/EarlyCSE.cpp

1206 ↗

(On Diff #186899)

AFAICT run() is only invoked once for an EarlyCSE instance and it's not recursive.

I'm also missing the purpose of CurrentGeneration = LiveOutGeneration; and
the above

// Save the current generation.
unsigned LiveOutGeneration = CurrentGeneration;

Could you please clarify?

[george.burgess.iv]

lib/Transforms/Scalar/EarlyCSE.cpp

1206 ↗

(On Diff #186899)

AFAICT run() is only invoked once for an EarlyCSE instance and it's not recursive.

That's what I thought, too, but I saw this, so I assumed I was missing something.

Looks like that was added circa 2012; I assume this pass has changed quite a lot since then. I'm hoping davide (or one of the subscribers) may have context on EarlyCSE's usage patterns?

If no one is sure, I vote that we replace it with an early assert(!CurrentGeneration && "Create a new EarlyCSE instance to run it again") (which can optionally be removed if no one complains within a reasonable amount of time).

[asbirlea]

Address comment (add TODO).

[asbirlea]

lib/Transforms/Scalar/EarlyCSE.cpp

1206 ↗

(On Diff #186899)

I agree with cleaning up existing code, but I will argue against doing it in this patch. Happy to send a follow up one adding the assert.

[george.burgess.iv]

Thanks again!

lib/Transforms/Scalar/EarlyCSE.cpp

1206 ↗

(On Diff #186899)

IMO, if we're not asserting that this 'cleanup' code is useless as a part of this patch, we should be cleaning up the MSSA counter until those assertions do land.

Not a strong enough nit for me to block this patch on, since I agree that it's probably a nop in any case. Your call. :)

[asbirlea]

lib/Transforms/Scalar/EarlyCSE.cpp

1206 ↗

(On Diff #186899)

Tested with the assert, all seems fine (i.e. those assignments are nops).
I'll go ahead and send this out to unblock the folks hitting the pathological compile times.
Thanks a lot for the review!
(I'll send the clean-up patch shortly as well)

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

 STATISTIC(NumCSECVP,   "Number of compare instructions CVP'd");
 STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
 STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
 STATISTIC(NumDSE,      "Number of trivial dead stores removed");
 
 DEBUG_COUNTER(CSECounter, "early-cse",
               "Controls which instructions are removed");
 
+static cl::opt<unsigned> EarlyCSEMssaOptCap(
+    "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,
+    cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange "
+             "for faster compile. Caps the MemorySSA clobbering calls."));
+
 //===----------------------------------------------------------------------===//
 // SimpleValue
 //===----------------------------------------------------------------------===//
 
 namespace {
 
 /// Struct representing the available values in the scoped hash table.
 struct SimpleValue {
EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,
            const TargetTransformInfo &TTI, DominatorTree &DT,
            AssumptionCache &AC, MemorySSA *MSSA)
       : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),
         MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
 
   bool run();
 
 private:
+  unsigned ClobberCounter = 0;
   // Almost a POD, but needs to call the constructors for the scoped hash
   // tables so that a new scope gets pushed on. These are RAII so that the
   // scope gets popped when the NodeScope is destroyed.
   class NodeScope {
   public:
     NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
               InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls)
       : Scope(AvailableValues), LoadScope(AvailableLoads),
bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
   auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
   if (!LaterMA)
     return true;
 
   // Since we know LaterDef dominates LaterInst and EarlierInst dominates
   // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
   // EarlierInst and LaterInst and neither can any other write that potentially
   // clobbers LaterInst.
-  MemoryAccess *LaterDef =
-      MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
+  MemoryAccess *LaterDef;
+  if (ClobberCounter < EarlyCSEMssaOptCap) {
+    LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
+    ClobberCounter++;
+  } else
+    LaterDef = LaterMA->getDefiningAccess();
+
   return MSSA->dominates(LaterDef, EarlierMA);
 }
 
 bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
   // A location loaded from with an invariant_load is assumed to *never* change
   // within the visible scope of the compilation.
   if (auto *LI = dyn_cast<LoadInst>(I))
     if (LI->getMetadata(LLVMContext::MD_invariant_load))