[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

461

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.

2245

Remove the addAllInstructionsInLoopUsingMSSA API as well.

2273

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

461

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.)

2273

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

461

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

2273

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/include/llvm/Analysis/AliasSetTracker.h

 
 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
 #define LLVM_ANALYSIS_ALIASSETTRACKER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
+#include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <vector>
 
 namespace llvm {
 
 class AAResults;
 class AliasSetTracker;
 class BasicBlock;
 class LoadInst;
 class Loop;
-class MemorySSA;
 class AnyMemSetInst;
 class AnyMemTransferInst;
 class raw_ostream;
 class StoreInst;
 class VAArgInst;
 class Value;
 
 enum AliasResult : uint8_t;
public:
 
     ASTCallbackVH &operator=(Value *V);
   };
   /// Traits to tell DenseMap that tell us how to compare and hash the value
   /// handle.
   struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
 
   AAResults &AA;
-  MemorySSA *MSSA = nullptr;
   Loop *L = nullptr;
   ilist<AliasSet> AliasSets;
 
   using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
                                   ASTCallbackVHDenseMapInfo>;
 
   // Map from pointers to their node
   PointerMapType PointerMap;
 
 public:
   /// Create an empty collection of AliasSets, and use the specified alias
   /// analysis object to disambiguate load and store addresses.
   explicit AliasSetTracker(AAResults &AA) : AA(AA) {}
-  explicit AliasSetTracker(AAResults &AA, MemorySSA *MSSA, Loop *L)
-      : AA(AA), MSSA(MSSA), L(L) {}
   ~AliasSetTracker() { clear(); }
 
   /// These methods are used to add different types of instructions to the alias
   /// sets. Adding a new instruction can result in one of three actions
   /// happening:
   ///
   ///   1. If the instruction doesn't alias any other sets, create a new set.
   ///   2. If the instruction aliases exactly one set, add it to the set
   ///   3. If the instruction aliases multiple sets, merge the sets, and add
   ///      the instruction to the result.
   ///
   /// These methods return true if inserting the instruction resulted in the
   /// addition of a new alias set (i.e., the pointer did not alias anything).
   ///
   void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
   void add(LoadInst *LI);
   void add(StoreInst *SI);
   void add(VAArgInst *VAAI);
   void add(AnyMemSetInst *MSI);
   void add(AnyMemTransferInst *MTI);
   void add(Instruction *I);       // Dispatch to one of the other add methods...
   void add(BasicBlock &BB);       // Add all instructions in basic block
   void add(const AliasSetTracker &AST); // Add alias relations from another AST
   void addUnknown(Instruction *I);
-  void addAllInstructionsInLoopUsingMSSA();
 
   void clear();
 
   /// Return the alias sets that are active.
   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
 
   /// Return the alias set which contains the specified memory location.  If
   /// the memory location aliases two or more existing alias sets, will have

llvm/lib/Analysis/AliasSetTracker.cpp

 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the AliasSetTracker and AliasSet classes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
for (const AliasSet &AS : AST) {
     // Loop over all of the pointers in this alias set.
     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
       addPointer(
           MemoryLocation(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo()),
           (AliasSet::AccessLattice)AS.Access);
   }
 }
 
-void AliasSetTracker::addAllInstructionsInLoopUsingMSSA() {
-  assert(MSSA && L && "MSSA and L must be available");
-  for (const BasicBlock *BB : L->blocks())
-    if (auto *Accesses = MSSA->getBlockAccesses(BB))
-      for (auto &Access : *Accesses)
-        if (auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
-          add(MUD->getMemoryInst());
-}
-
 // deleteValue method - This method is used to remove a pointer value from the
 // AliasSetTracker entirely.  It should be used when an instruction is deleted
 // from the program to update the AST.  If you don't use this, you would have
 // dangling pointers to deleted instructions.
 //
 void AliasSetTracker::deleteValue(Value *PtrVal) {
   // First, look up the PointerRec for this pointer.
   PointerMapType::iterator I = PointerMap.find_as(PtrVal);

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;
+  llvm::erase_if(MaybePromotable, [&](Instruction *I) {
+    if (IsPotentiallyPromotable(I)) {
+      AttemptingPromotion.insert(I);
+      AST.add(I);
+      return true;
+    }
+    return false;
+  });
+
+  // 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)) {
+      llvm::erase_if(Sets, [&](const AliasSet *AS) {
+        return AS->aliasesPointer(Loc->Ptr, Loc->Size, Loc->AATags, *AA)
+               != NoAlias;
+      });
+    } else {
+      llvm::erase_if(Sets, [&](const AliasSet *AS) {
+        return AS->aliasesUnknownInst(I, *AA);
+      });
+    }
+  });
+
+  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;