[LICM] Make promotion faster

[nikic]

Summary

As mentioned at the MSSA roundtable, LICM spends a lot of time construction an AST, despite the caps already in place. This patch is a proposal on how to reduce the impact.

The idea here is pretty simple: We're only interested in must-alias mod sets of loop invariant pointers. As such, only populate the AST with loop-invariant loads and stores (anything else is definitely not promotable) and then discard any sets which alias with any of the remaining, definitely non-promotable accesses.

If we promoted something, check whether this has made some other accesses loop invariant and thus possible promotion candidates.

This has a large positive compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=f197cf2126be3b224cadfe8b1cde9c05f638a0ea&to=7f1e24e26d198e1d80d32c87c9fd1f5cf3cc8c5f&stat=instructions We save ~1.8% geomean at O3, and lencod in particular saves 6%, with up to 25% on individual files.

There is no impact on the number of promotions (licm.NumPromoted) in test-suite in the O3 configuration with this change.

[lebedev.ri]

An ignorant word of caution: anything can be made faster by making it do less stuff.

There's no code-size impact on any of the CTMark programs, so code quality impact of the change should be low.

That doesn't really sound like exhaustive-enough test coverage to me.

[nikic]

In D89264#2325990, @lebedev.ri wrote:

An ignorant word of caution: anything can be made faster by making it do less stuff.

There's no code-size impact on any of the CTMark programs, so code quality impact of the change should be low.

That doesn't really sound like exhaustive-enough test coverage to me.

Yes, of course :) I have checked this on the full test-suite now, and there are no codegen differences with this patch. The only differences in statistics are...

basicaa.SearchLimitReached | 146199 | 128184
basicaa.SearchTimes | 50855724 | 23825700
memory-builtins.ObjectVisitorArgument | 331614 | 254610
memory-builtins.ObjectVisitorLoad | 149739 | 81225

...which just tells us that we're doing a lot less AA queries, which is exactly the intention behind this. Of course the lit test failures indicate that regressions here are possible, even if they don't show up in practice.

[lebedev.ri]

In D89264#2326088, @nikic wrote:

In D89264#2325990, @lebedev.ri wrote:

An ignorant word of caution: anything can be made faster by making it do less stuff.

There's no code-size impact on any of the CTMark programs, so code quality impact of the change should be low.

That doesn't really sound like exhaustive-enough test coverage to me.

Yes, of course :) I have checked this on the full test-suite now, and there are no codegen differences with this patch. The only differences in statistics are...

I guess i was thinking of even bigger coverage (SPEC?, but i personally don't have it (either?)).

basicaa.SearchLimitReached | 146199 | 128184
basicaa.SearchTimes | 50855724 | 23825700
memory-builtins.ObjectVisitorArgument | 331614 | 254610
memory-builtins.ObjectVisitorLoad | 149739 | 81225

...which just tells us that we're doing a lot less AA queries, which is exactly the intention behind this. Of course the lit test failures indicate that regressions here are possible, even if they don't show up in practice.

IIRC those run-to-run stats changes are there always, and are therefore indicative of nondeterminism.

[asbirlea]

Could you address the loop versioning test failures?

[nikic]

Rebase to pick up fix for the LoopVersioningLICM noalias metadata. Those regressions are no longer present now.

[nikic]

Rebase over NFC to make this patch smaller.

[asbirlea]

I tested this in two configurations we use for compiler releases and I'm seeing quite a few runtime regressions in the 10-20% area and a couple of 40% run time regressions.
It doesn't look worth the compile time gain with such large run time regressions.

[nikic]

Add back support for "promotion of promotion".

[nikic]

In D89264#2328663, @asbirlea wrote:

I tested this in two configurations we use for compiler releases and I'm seeing quite a few runtime regressions in the 10-20% area and a couple of 40% run time regressions.
It doesn't look worth the compile time gain with such large run time regressions.

Thank you for running those tests! Those results are pretty unexpected to me, as this was not supposed to change the behavior in any substantial way. The two possibilities that come to mind are:

• Those regressions were using the "promotion of promotion" behavior. I originally did not bother supporting this because the situation seemed so contrived, and I would expect EarlyCSE/GVN or anything else doing store-load forwarding to handle it. However, it's also really simple to support and doesn't come with additional compile-time cost, so I extended the patch to handle it (thus also removing the one lit test regression).
• The different processing order for accesses ends up mattering in those cases. Due to AATags intersection the AST is order-dependent, and the different order can result in more or less accesses being promoted (and either direction could be either good or bad for performance).

It's hard to guess without a test case to look at, and unfortunately test-suite doesn't have one. Are any of the regressions you observed in publicly available code that I could check?

I don't really want to give up on this change yet, as the compile-time impact is fairly substantial for some types of code (a few >20% wins on individual files).

[asbirlea]

A couple of public benchmarks:
singlesource polybench jacobi 1d imper is seeing a 11.9% run time regression
multisource MallocBench_gs is seeing a 15.8% run time regression
both on haswell, without thinlto.
With thinlto, eigen is seeing a lot of regressions in the 5-20%range and another benchmark has the 40% spike.

I rerun the performance numbers after the promotion of promotion patch update and the results are improved.
In opt, on haswell, there are still a few notable regressions, in the range of 5-10%, with one 32% outlier; singlesource looks resolved; multisource MallocBench_gs is still seeing a 16.3% regression
With thinlto there are still lots of 5-17% regressions in eigen, but the 40% spike is replaced with a range of 5% regression to one significant improvement.

I'll run additional configurations to determine if the gains out-weight the regressions.
On the 2 configurations I tested so far, there are enough regressions that I wouldn't push this. I wouldn't drop it just yet either, it has good potential for compile and run time.

[fhahn]

Marking as changes required, as there are some reported regression with this change.

[nikic]

Rebase with some minor cleanup.

[nikic]

@asbirlea Would you mind giving this patch another try? There have been quite a few changes on the alias analysis side in the meantime. I just ran into another case where LICM promotion takes more than 10% of compile-time and remembered this patch.

[asbirlea]

Ack, testing in progress.

[asbirlea]

Runtime impact looks reasonable now. What's the compile-time impact for the patch now?

Minor comments inline.

llvm/lib/Transforms/Scalar/LICM.cpp

436

Nit: It seems the conditions in IsPotentiallyPromotable would be useful as an early filter to prevent filling up the MaybePromotable only to clean it up shortly after.

2216

Remove the addAllInstructionsInLoopUsingMSSA API as well.

2244

A quick exit check for promotion is whether the AST is saturated.
Probably need to add the API for that inside the AliasSetTracker.

bool isSaturated(){
    return AliasAnyAS != nullptr;
}

if (AST.isSaturated())
    return {}; // Nothing to promote...

[nikic]

Remove addAllInstructionsInLoopUsingMSSA() API.

[nikic]

In D89264#2573058, @asbirlea wrote:

Runtime impact looks reasonable now. What's the compile-time impact for the patch now?

The link in the summary is already an updated run (https://llvm-compile-time-tracker.com/compare.php?from=f197cf2126be3b224cadfe8b1cde9c05f638a0ea&to=7f1e24e26d198e1d80d32c87c9fd1f5cf3cc8c5f&stat=instructions), so this is now ~1.8% geomean improvement at O3, with 5.5% on lencod in particular.

llvm/lib/Transforms/Scalar/LICM.cpp

436

The idea here is that some accesses may not be promotable initially, but may become promotable after others have been promoted. Each iteration removes all potentially promotable accesses from MaybePromotable, leaving the rest for the next iteration (if any promotion happened). For this reason we can't do early filtering here. (See also the comment on the loop below.)

2244

If I'm understanding how this works correctly, won't the "saturated" case be handled automatically? If the AST is saturated, then there will only be a single may-alias set, so the loop below will only iterate once and return afterwards.

[nikic]

ping :)

[asbirlea]

llvm/lib/Transforms/Scalar/LICM.cpp

436

I misread the condition on which accesses are kept in MaybePromotable. This is fine.

2244

Yes, you're right, this is good.

[nikic]

Always use aliasesUnknownInst() API to correctly model atomic accesses. Add previously miscompiled test case.

[asbirlea]

LGTM.

[fhahn]

It looks like this is causing Clang to crash https://bugs.llvm.org/show_bug.cgi?id=50367

llvm/lib/Transforms/Scalar/LICM.cpp

 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
                              AliasSetTracker *AST, MemorySSAUpdater *MSSAU);
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo,
                                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE);
 
+static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L,
+                                function_ref<void(Instruction *)> Fn);
+static SmallVector<SmallSetVector<Value *, 8>, 0>
+collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L,
+                           SmallVectorImpl<Instruction *> &MaybePromotable);
+
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
                  BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI,
                  TargetTransformInfo *TTI, ScalarEvolution *SE, MemorySSA *MSSA,
                  OptimizationRemarkEmitter *ORE);
 
   LoopInvariantCodeMotion(unsigned LicmMssaOptCap,
                           unsigned LicmMssaNoAccForPromotionCap)
       : LicmMssaOptCap(LicmMssaOptCap),
         LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap) {}
 
 private:
   unsigned LicmMssaOptCap;
   unsigned LicmMssaNoAccForPromotionCap;
 
   std::unique_ptr<AliasSetTracker>
   collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AAResults *AA);
-  std::unique_ptr<AliasSetTracker>
-  collectAliasInfoForLoopWithMSSA(Loop *L, AAResults *AA,
-                                  MemorySSAUpdater *MSSAU);
 };
 
 struct LegacyLICMPass : public LoopPass {
   static char ID; // Pass identification, replacement for typeid
   LegacyLICMPass(
       unsigned LicmMssaOptCap = SetLicmMssaOptCap,
       unsigned LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap)
       : LoopPass(ID), LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap) {
if (!HasCatchSwitch) {
         InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
         if (MSSAU)
           MSSAInsertPts.push_back(nullptr);
       }
 
       PredIteratorCache PIC;
 
       bool Promoted = false;
-
-      // Build an AST using MSSA.
-      if (!CurAST.get())
-        CurAST = collectAliasInfoForLoopWithMSSA(L, AA, MSSAU.get());
-
+      if (CurAST.get()) {
         // Loop over all of the alias sets in the tracker object.
         for (AliasSet &AS : *CurAST) {
           // We can promote this alias set if it has a store, if it is a "Must"
           // alias set, if the pointer is loop invariant, and if we are not
           // eliminating any volatile loads or stores.
           if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
               !L->isLoopInvariant(AS.begin()->getValue()))
             continue;
 
           assert(
               !AS.empty() &&
               "Must alias set should have at least one pointer element in it!");
 
           SmallSetVector<Value *, 8> PointerMustAliases;
           for (const auto &ASI : AS)
             PointerMustAliases.insert(ASI.getValue());
 
           Promoted |= promoteLoopAccessesToScalars(
               PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC, LI,
               DT, TLI, L, CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
         }
+      } else {
+        SmallVector<Instruction *, 16> MaybePromotable;
+        foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
+          MaybePromotable.push_back(I);
+        });
+
+        // Promoting one set of accesses may make the pointers for another set
+        // loop invariant, so run this in a loop (with the MaybePromotable set
+        // decreasing in size over time).
+        bool LocalPromoted;
+        do {
+          LocalPromoted = false;
+          for (const SmallSetVector<Value *, 8> &PointerMustAliases :
+               collectPromotionCandidates(MSSA, AA, L, MaybePromotable)) {
+            LocalPromoted |= promoteLoopAccessesToScalars(
+                PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC,
+                LI, DT, TLI, L, /*AST*/nullptr, MSSAU.get(), &SafetyInfo, ORE);
+          }
+          Promoted |= LocalPromoted;
+        } while (LocalPromoted);
+      }
 
       // Once we have promoted values across the loop body we have to
       // recursively reform LCSSA as any nested loop may now have values defined
       // within the loop used in the outer loop.
       // FIXME: This is really heavy handed. It would be a bit better to use an
       // SSAUpdater strategy during promotion that was LCSSA aware and reformed
       // it as it went.
       if (Promoted)
if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
   if (PreheaderLoad->use_empty())
     eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, MSSAU);
 
   return true;
 }
 
+static void foreachMemoryAccess(MemorySSA *MSSA, Loop *L,
+                                function_ref<void(Instruction *)> Fn) {
+  for (const BasicBlock *BB : L->blocks())
+    if (const auto *Accesses = MSSA->getBlockAccesses(BB))
+      for (const auto &Access : *Accesses)
+        if (const auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
+          Fn(MUD->getMemoryInst());
+}
+
+static SmallVector<SmallSetVector<Value *, 8>, 0>
+collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L,
+                           SmallVectorImpl<Instruction *> &MaybePromotable) {
+  AliasSetTracker AST(*AA);
+
+  auto IsPotentiallyPromotable = [L](const Instruction *I) {
+    if (const auto *SI = dyn_cast<StoreInst>(I))
+      return L->isLoopInvariant(SI->getPointerOperand());
+    if (const auto *LI = dyn_cast<LoadInst>(I))
+      return L->isLoopInvariant(LI->getPointerOperand());
+    return false;
+  };
+
+  // Populate AST with potentially promotable accesses and remove them from
+  // MaybePromotable, so they will not be checked again on the next iteration.
+  SmallPtrSet<Value *, 16> AttemptingPromotion;
+  MaybePromotable.erase(llvm::remove_if(MaybePromotable, [&](Instruction *I) {
+    if (IsPotentiallyPromotable(I)) {
+      AttemptingPromotion.insert(I);
+      AST.add(I);
+      return true;
+    }
+    return false;
+  }), MaybePromotable.end());
+
+  // We're only interested in must-alias sets that contain a mod.
+  SmallVector<const AliasSet *, 8> Sets;
+  for (AliasSet &AS : AST)
+    if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias())
+      Sets.push_back(&AS);
+
+  if (Sets.empty())
+    return {}; // Nothing to promote...
+
+  // Discard any sets for which there is an aliasing non-promotable access.
+  foreachMemoryAccess(MSSA, L, [&](Instruction *I) {
+    if (AttemptingPromotion.contains(I))
+      return;
+
+    if (Optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I)) {
+      Sets.erase(llvm::remove_if(Sets, [&](const AliasSet *AS) {
+        return AS->aliasesPointer(Loc->Ptr, Loc->Size, Loc->AATags, *AA)
+               != NoAlias;
+      }), Sets.end());
+    } else {
+      Sets.erase(llvm::remove_if(Sets, [&](const AliasSet *AS) {
+        return AS->aliasesUnknownInst(I, *AA);
+      }), Sets.end());
+    }
+  });
+
+  SmallVector<SmallSetVector<Value *, 8>, 0> Result;
+  for (const AliasSet *Set : Sets) {
+    SmallSetVector<Value *, 8> PointerMustAliases;
+    for (const auto &ASI : *Set)
+      PointerMustAliases.insert(ASI.getValue());
+    Result.push_back(std::move(PointerMustAliases));
+  }
+
+  return Result;
+}
+
 /// Returns an owning pointer to an alias set which incorporates aliasing info
 /// from L and all subloops of L.
 std::unique_ptr<AliasSetTracker>
 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
                                                  AAResults *AA) {
   auto CurAST = std::make_unique<AliasSetTracker>(*AA);
 
   // Add everything from all the sub loops.
   for (Loop *InnerL : L->getSubLoops())
     for (BasicBlock *BB : InnerL->blocks())
       CurAST->add(*BB);
 
   // And merge in this loop (without anything from inner loops).
   for (BasicBlock *BB : L->blocks())
     if (LI->getLoopFor(BB) == L)
       CurAST->add(*BB);
 
   return CurAST;
 }
 
-std::unique_ptr<AliasSetTracker>
-LoopInvariantCodeMotion::collectAliasInfoForLoopWithMSSA(
-    Loop *L, AAResults *AA, MemorySSAUpdater *MSSAU) {
-  auto *MSSA = MSSAU->getMemorySSA();
-  auto CurAST = std::make_unique<AliasSetTracker>(*AA, MSSA, L);
-  CurAST->addAllInstructionsInLoopUsingMSSA();
-  return CurAST;
-}
-
 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
                                      AAResults *AA) {
   // First check to see if any of the basic blocks in CurLoop invalidate *V.
   bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
 
   if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
     return isInvalidatedAccordingToAST;