[Passes] Only run extra vector passes if loops have been vectorized.

[fhahn]

Summary

This patch uses a similar trick as in D113947 to only run the extra
passes after vectorization on functions where loops have been
vectorized.

The reason for running the 'extra vector passes' is
simplification/unswitching of the runtime checks created by LV, there
should be no need to run them if nothing got vectorized

To do that, a new dummy analysis ShouldRunExtraVectorPasses has been
added. If loops have been vectorized for a function, LV will cache the
analysis. At the moment it uses MadeCFGChanges as proxy for loop
vectorized, which isn't perfect (it could be too aggressive, e.g.
because no runtime checks have been added), but should be good enough
for now.

The extra passes are then managed by a new FunctionPassManager that
collects 2 sets of passes: one to run unconditionally and one to run
only if ShouldRunExtraVectorPasses has been cached.

The reason it manages 2 sets of passes is that there are some
unconditional passes between LV and the 'extra' passes. Having the pass
manager manage both allows us to query the cache before the
unconditional passes might invalidate it.

Without this patch, -extra-vectorizer-passes has the following
compile-time impact:

NewPM-O3: +4.86%
NewPM-ReleaseThinLTO: +3.56%
NewPM-ReleaseLTO-g: +7.17%

http://llvm-compile-time-tracker.com/compare.php?from=ead3979a92fc33add4710c4510d6906260dcb4ad&to=c292da649e2c6e88a31e702fdc474727d09c72bc&stat=instructions

With this patch, that gets reduced to

NewPM-O3: +1.43%
NewPM-ReleaseThinLTO: +1.00%
NewPM-ReleaseLTO-g: +1.58%

http://llvm-compile-time-tracker.com/compare.php?from=ead3979a92fc33add4710c4510d6906260dcb4ad&to=e67d86b57810011cf285eb9aa1944781be6096f0&stat=instructions

It is probably still too high to enable by default, but much better.

[aeubanks]

llvm/include/llvm/Transforms/Vectorize/LoopVectorize.h

98

can ExtraVectorPassManager only contain ConditionalPasses and we have a separate FPM for the normal passes? separation of concerns, seems like this is doing two things that could be separated

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

10753

add a TODO for more precise vectorization tracking?

llvm/test/Other/opt-pipeline-vector-passes.ll

3

this should check that we actually don't run the extra passes when there's no vectorization, e.g.
O2-NOT: Running pass: ...

[fhahn]

llvm/include/llvm/Transforms/Vectorize/LoopVectorize.h

98

The reason why ExtraVectorPassManager contains both the conditional and unconditional passes is that this way we can check whether ShouldRunExtraVectorPasses is available *before* the unconditional passes run.

If we would run the unconditional passes outside of ExtraVectorPassManager, then any change they make would invalidate ShouldRunExtraVectorPasses IIUC. Unless we teach all those passes to preserve it. Or perhaps there's a different alternative?

llvm/test/Other/opt-pipeline-vector-passes.ll

3

Yes, the original test doesn't really check for that. I'll push a commit to improve the test in that regard separately and will also include the vector loop.

[fhahn]

rebased on top of test changes, added TODO

[lebedev.ri]

It would be good to mimic what the module equivalence check does
(when no changes were reported, the module should not have been changed),
and e.g. when in EXPENSIVE_CHECKS mode, if we weren't going to run those
extra vectorization passes because we predicted they wouldn't do anything,
to still run them, and check that they actually didn't do anything.

[fhahn]

In D115052#3170517, @lebedev.ri wrote:

It would be good to mimic what the module equivalence check does
(when no changes were reported, the module should not have been changed),
and e.g. when in EXPENSIVE_CHECKS mode, if we weren't going to run those
extra vectorization passes because we predicted they wouldn't do anything,
to still run them, and check that they actually didn't do anything.

Unfortunately I don't think this will be feasible. The extra passes may simplify things in functions where nothing gets vectorized, *but* I think this is only a side-effect of the current implementation. The comment for the extra passes states that they are specifically intended to simplify runtime checks generated by the vectorizer.

[xbolva00]

It is probably still too high to enable by default, but much better.

It depends, for -O3, this may not be an issue. Maybe worth to look at "mafft"? (+4.17%)

[aeubanks]

this is a little different from D113947 in that we're using an analysis to keep track of something that must happen if a pass did something, whereas D113947 uses an analysis to keep track of if we *don't* have to do something
the only other thing I can think of that's somewhat similar is the devirtualization wrapper where we keep track of the number of direct/indirect calls, and also using value handles to keep track of if any devirtualization happened, and rerun passes if it did

I guess there isn't a great alternative to something like this unless we have some sort of marker within the IR itself, which doesn't really make any sense
so something along these lines seems fine to me

llvm/include/llvm/Transforms/Vectorize/LoopVectorize.h

98

you could override the invalidate() method of Result to be stateless, e.g. following

bool GlobalsAAResult::invalidate(Module &, const PreservedAnalyses &PA,
                                 ModuleAnalysisManager::Invalidator &) {
  // Check whether the analysis has been explicitly invalidated. Otherwise, it's
  // stateless and remains preserved.
  auto PAC = PA.getChecker<GlobalsAA>();
  return !PAC.preservedWhenStateless();
}

this makes it so it's only invalidated if it's specifically abandoned

this should make it so this only needs to wrap the ConditionaPasses and not be its own FunctionPassManager

[fhahn]

Updated to only invalidate the marker analysis when explicitly invalidated as suggested.

I also run a set of benchmarks including SPEC2006/Geekbench on AArch64 (extra vector passes enabled) with and without this patch and there were no notable performance differences.

In D115052#3176907, @xbolva00 wrote:

It is probably still too high to enable by default, but much better.

It depends, for -O3, this may not be an issue. Maybe worth to look at "mafft"? (+4.17%)

Possibly, but I rather not get into this discussion at least until the major compile-time issue this patch addresses has been fixed. I suspect there is potential to tune the 'extra' vector pass sequence a bit more, but unfortunately I won't be able to drive towards enabling by default in the near future.

In D115052#3181453, @aeubanks wrote:

this is a little different from D113947 in that we're using an analysis to keep track of something that must happen if a pass did something, whereas D113947 uses an analysis to keep track of if we *don't* have to do something
the only other thing I can think of that's somewhat similar is the devirtualization wrapper where we keep track of the number of direct/indirect calls, and also using value handles to keep track of if any devirtualization happened, and rerun passes if it did

I guess there isn't a great alternative to something like this unless we have some sort of marker within the IR itself, which doesn't really make any sense
so something along these lines seems fine to me

Yeah, at the moment I don't think there's a general alternative to optionally running passes and using a marker analysis seems like a very convenient way to use the new pass manager to do that.

A related issue was discussed a while ago on llvm-dev ('Execute intrinsic lowering passes on demand' thread) [1] . It might be possible to use a similar approach to conditionally execute various intrinsic lowering passes.

[1] https://lists.llvm.org/pipermail/llvm-dev/2020-March/140531.html

[fhahn]

Also update doc-comment for ExtraVectorPassManager after recent change.

[fhahn]

llvm/include/llvm/Transforms/Vectorize/LoopVectorize.h

98

Done, thanks!

thank you for the post! It helps me tremendously!
krunker

llvm/include/llvm/Transforms/Vectorize/LoopVectorize.h

 class ProfileSummaryInfo;
 class ScalarEvolution;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 
 extern cl::opt<bool> EnableLoopInterleaving;
 extern cl::opt<bool> EnableLoopVectorization;
 
+/// A marker to determine if extra passes after loop vectorization should be
+/// run.
+struct ShouldRunExtraVectorPasses
+    : public AnalysisInfoMixin<ShouldRunExtraVectorPasses> {
+  static AnalysisKey Key;
+  struct Result {
+    bool invalidate(Function &F, const PreservedAnalyses &PA,
+                    FunctionAnalysisManager::Invalidator &) {
+      // Check whether the analysis has been explicitly invalidated. Otherwise,
+      // it remains preserved.
+      auto PAC = PA.getChecker<ShouldRunExtraVectorPasses>();
+      return !PAC.preservedWhenStateless();
+    }
+  };
+
+  Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); }
+};
+
+/// A pass manager to run a set of extra function simplification passes after
+/// vectorization, if requested. LoopVectorize caches the
+/// ShouldRunExtraVectorPasses analysis to request extra simplifications, if
+/// they could be beneficial.
+struct ExtraVectorPassManager : public FunctionPassManager {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
+    auto PA = PreservedAnalyses::all();
+    if (AM.getCachedResult<ShouldRunExtraVectorPasses>(F))
+      PA.intersect(FunctionPassManager::run(F, AM));
+    PA.abandon<ShouldRunExtraVectorPasses>();
+    return PA;
+  }
+};
+
 struct LoopVectorizeOptions {
   /// If false, consider all loops for interleaving.
   /// If true, only loops that explicitly request interleaving are considered.
   bool InterleaveOnlyWhenForced;
 
   /// If false, consider all loops for vectorization.
   /// If true, only loops that explicitly request vectorization are considered.
   bool VectorizeOnlyWhenForced;

llvm/lib/Passes/PassBuilderPipelines.cpp

if (!IsFullLTO) {
     // Eliminate loads by forwarding stores from the previous iteration to loads
     // of the current iteration.
     FPM.addPass(LoopLoadEliminationPass());
   }
   // Cleanup after the loop optimization passes.
   FPM.addPass(InstCombinePass());
 
   if (Level.getSpeedupLevel() > 1 && ExtraVectorizerPasses) {
+    ExtraVectorPassManager ExtraPasses;
     // At higher optimization levels, try to clean up any runtime overlap and
     // alignment checks inserted by the vectorizer. We want to track correlated
     // runtime checks for two inner loops in the same outer loop, fold any
     // common computations, hoist loop-invariant aspects out of any outer loop,
     // and unswitch the runtime checks if possible. Once hoisted, we may have
     // dead (or speculatable) control flows or more combining opportunities.
-    FPM.addPass(EarlyCSEPass());
-    FPM.addPass(CorrelatedValuePropagationPass());
-    FPM.addPass(InstCombinePass());
+    ExtraPasses.addPass(EarlyCSEPass());
+    ExtraPasses.addPass(CorrelatedValuePropagationPass());
+    ExtraPasses.addPass(InstCombinePass());
     LoopPassManager LPM;
     LPM.addPass(LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap));
     LPM.addPass(SimpleLoopUnswitchPass(/* NonTrivial */ Level ==
                                        OptimizationLevel::O3));
-    FPM.addPass(
+    ExtraPasses.addPass(
         RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
-    FPM.addPass(
+    ExtraPasses.addPass(
         createFunctionToLoopPassAdaptor(std::move(LPM), /*UseMemorySSA=*/true,
                                         /*UseBlockFrequencyInfo=*/true));
-    FPM.addPass(SimplifyCFGPass());
-    FPM.addPass(InstCombinePass());
+    ExtraPasses.addPass(SimplifyCFGPass());
+    ExtraPasses.addPass(InstCombinePass());
+    FPM.addPass(std::move(ExtraPasses));
   }
 
   // Now that we've formed fast to execute loop structures, we do further
   // optimizations. These are run afterward as they might block doing complex
   // analyses and transforms such as what are needed for loop vectorization.
 
   // Cleanup after loop vectorization, etc. Simplification passes like CVP and
   // GVN, loop transforms, and others have already run, so it's now better to

llvm/lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis())
 FUNCTION_ANALYSIS("phi-values", PhiValuesAnalysis())
 FUNCTION_ANALYSIS("regions", RegionInfoAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("opt-remark-emit", OptimizationRemarkEmitterAnalysis())
 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("should-not-run-function-passes", ShouldNotRunFunctionPassesAnalysis())
+FUNCTION_ANALYSIS("should-run-extra-vector-passes", ShouldRunExtraVectorPasses())
 FUNCTION_ANALYSIS("stack-safety-local", StackSafetyAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 FUNCTION_ANALYSIS("verify", VerifierAnalysis())
 FUNCTION_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
 FUNCTION_ANALYSIS("divergence", DivergenceAnalysis())
 

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

static Optional<unsigned> getSmallBestKnownTC(ScalarEvolution &SE, Loop *L) {
   return None;
 }
 
 // Forward declare GeneratedRTChecks.
 class GeneratedRTChecks;
 
 namespace llvm {
 
+AnalysisKey ShouldRunExtraVectorPasses::Key;
+
 /// InnerLoopVectorizer vectorizes loops which contain only one basic
 /// block to a specified vectorization factor (VF).
 /// This class performs the widening of scalars into vectors, or multiple
 /// scalars. This class also implements the following features:
 /// * It inserts an epilogue loop for handling loops that don't have iteration
 ///   counts that are known to be a multiple of the vectorization factor.
 /// * It handles the code generation for reduction variables.
 /// * Scalarization (implementation using scalars) of un-vectorizable
PreservedAnalyses LoopVectorizePass::run(Function &F,
     // We currently do not preserve loopinfo/dominator analyses with outer loop
     // vectorization. Until this is addressed, mark these analyses as preserved
     // only for non-VPlan-native path.
     // TODO: Preserve Loop and Dominator analyses for VPlan-native path.
     if (!EnableVPlanNativePath) {
       PA.preserve<LoopAnalysis>();
       PA.preserve<DominatorTreeAnalysis>();
     }
-    if (!Result.MadeCFGChange)
+
+    if (Result.MadeCFGChange) {
+      // Making CFG changes likely means a loop got vectorized. Indicate that
+      // extra simplification passes should be run.
+      // TODO: MadeCFGChanges is not a prefect proxy. Extra passes should only
+      // be run if runtime checks have been added.
+      AM.getResult<ShouldRunExtraVectorPasses>(F);
+      PA.preserve<ShouldRunExtraVectorPasses>();
+    } else {
       PA.preserveSet<CFGAnalyses>();
+    }
     return PA;
 }
 
 void LoopVectorizePass::printPipeline(
     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
   static_cast<PassInfoMixin<LoopVectorizePass> *>(this)->printPipeline(
       OS, MapClassName2PassName);
 
   OS << "<";
   OS << (InterleaveOnlyWhenForced ? "" : "no-") << "interleave-forced-only;";
   OS << (VectorizeOnlyWhenForced ? "" : "no-") << "vectorize-forced-only;";
   OS << ">";
 }

llvm/test/Other/opt-pipeline-vector-passes.ll

 ; RUN: opt -disable-verify -debug-pass-manager -passes='default<O1>' -force-vector-width=4 -S %s 2>&1 | FileCheck %s --check-prefixes=O1
 ; RUN: opt -disable-verify -debug-pass-manager -passes='default<O2>' -force-vector-width=4 -S %s 2>&1 | FileCheck %s --check-prefixes=O2
 ; RUN: opt -disable-verify -debug-pass-manager -passes='default<O2>' -force-vector-width=4 -extra-vectorizer-passes -S %s 2>&1 | FileCheck %s --check-prefixes=O2_EXTRA
 
+; When the loop doesn't get vectorized, no extra vector passes should run.
+; RUN: opt -disable-verify -debug-pass-manager -passes='default<O2>' -force-vector-width=0 -extra-vectorizer-passes -S %s 2>&1 | FileCheck %s --check-prefixes=O2
+
 ; REQUIRES: asserts
 
 ; The loop vectorizer still runs at both -O1/-O2 even with the
 ; debug flag, but it only works on loops explicitly annotated
 ; with pragmas.
 
 ; SLP does not run at -O1. Loop vectorization runs, but it only
 ; works on loops explicitly annotated with pragmas.