[LoopVectorize] Preserve CFG analyses if CFG wasn't modified

[mkazantsev]

Summary

One of transforms the loop vectorizer makes is LCSSA formation. In some cases it
is the only transform it makes. We should not drop CFG analyzes if only LCSSA was
formed and no actual CFG changes was made.

We should think of expanding this logic to other passes as well, and maybe make
it a part of PM framework.

[mkazantsev]

I'd view it as a PoC for more general change; it seems that LV is not the only pass that drops analyzes because of transforms that should not lead to it. But until it's framed properly, we can go with a local solution.

[fhahn]

In D78360#1988644, @mkazantsev wrote:

I'd view it as a PoC for more general change; it seems that LV is not the only pass that drops analyzes because of transforms that should not lead to it. But until it's framed properly, we can go with a local solution.

Great to see work being done in that direction, thanks! Do you think it would be possible to add a test case with a loop that cannot be vectorized but it adds an LCSSA PHI and check the pass manager output to ensure it preserves a CFG analysis (besides DT which already is preserved)?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7995

It might simplifies things a bit if we would just let CFGChanged imply Changed.

[mkazantsev]

In D78360#1988737, @fhahn wrote:

In D78360#1988644, @mkazantsev wrote:

I'd view it as a PoC for more general change; it seems that LV is not the only pass that drops analyzes because of transforms that should not lead to it. But until it's framed properly, we can go with a local solution.

Great to see work being done in that direction, thanks! Do you think it would be possible to add a test case with a loop that cannot be vectorized but it adds an LCSSA PHI and check the pass manager output to ensure it preserves a CFG analysis (besides DT which already is preserved)?

I'll try.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7995

What exactly are you suggesting?

[mkazantsev]

Added test.

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7995

you could use Changed || CFGChanged to set Changed in LoopVectorizeResult I think, rather than having Changed |= CFGChanged |= .... in multiple places. Just a nit.

[mkazantsev]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7995

I don't really think it's a good idea, because in this case Changed would need a better name; we cannot just set CFGChanged at some point and not set Changed, the reader may think that this transform *only* changes CFG, which might be not true.

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

struct LoopVectorizeOptions {
   }
 
   LoopVectorizeOptions &setVectorizeOnlyWhenForced(bool Value) {
     VectorizeOnlyWhenForced = Value;
     return *this;
   }
 };
 
+/// Storage for information about made changes.
+struct LoopVectorizeResult {
+  bool MadeAnyChange;
+  bool MadeCFGChange;
+
+  LoopVectorizeResult(bool MadeAnyChange, bool MadeCFGChange)
+      : MadeAnyChange(MadeAnyChange), MadeCFGChange(MadeCFGChange) {}
+};
+
 /// The LoopVectorize Pass.
 struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> {
 private:
   /// 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.
public:
   AssumptionCache *AC;
   std::function<const LoopAccessInfo &(Loop &)> *GetLAA;
   OptimizationRemarkEmitter *ORE;
   ProfileSummaryInfo *PSI;
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Shim for old PM.
-  bool runImpl(Function &F, ScalarEvolution &SE_, LoopInfo &LI_,
-               TargetTransformInfo &TTI_, DominatorTree &DT_,
-               BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_,
-               DemandedBits &DB_, AliasAnalysis &AA_, AssumptionCache &AC_,
-               std::function<const LoopAccessInfo &(Loop &)> &GetLAA_,
-               OptimizationRemarkEmitter &ORE_, ProfileSummaryInfo *PSI_);
+  LoopVectorizeResult
+  runImpl(Function &F, ScalarEvolution &SE_, LoopInfo &LI_,
+          BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_, DemandedBits &DB_,
+          AliasAnalysis &AA_, AssumptionCache &AC_,
 
   bool processLoop(Loop *L);
 };
 
 /// Reports a vectorization failure: print \p DebugMsg for debugging
 /// purposes along with the corresponding optimization remark \p RemarkName.
 /// If \p I is passed, it is an instruction that prevents vectorization.
 /// Otherwise, the loop \p TheLoop is used for the location of the remark.
 void reportVectorizationFailure(const StringRef DebugMsg,
     const StringRef OREMsg, const StringRef ORETag,
     OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I = nullptr);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

bool runOnFunction(Function &F) override {
     auto *DB = &getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
     auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
     auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 
     std::function<const LoopAccessInfo &(Loop &)> GetLAA =
         [&](Loop &L) -> const LoopAccessInfo & { return LAA->getInfo(&L); };
 
     return Impl.runImpl(F, *SE, *LI, *TTI, *DT, *BFI, TLI, *DB, *AA, *AC,
-                        GetLAA, *ORE, PSI);
+                        GetLAA, *ORE, PSI).MadeAnyChange;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequired<ScalarEvolutionWrapperPass>();
if (RemainderLoopID.hasValue()) {
     // Mark the loop as already vectorized to avoid vectorizing again.
     Hints.setAlreadyVectorized();
   }
 
   LLVM_DEBUG(verifyFunction(*L->getHeader()->getParent()));
   return true;
 }
 
-bool LoopVectorizePass::runImpl(
+LoopVectorizeResult LoopVectorizePass::runImpl(
     Function &F, ScalarEvolution &SE_, LoopInfo &LI_, TargetTransformInfo &TTI_,
     DominatorTree &DT_, BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_,
     DemandedBits &DB_, AliasAnalysis &AA_, AssumptionCache &AC_,
     std::function<const LoopAccessInfo &(Loop &)> &GetLAA_,
     OptimizationRemarkEmitter &ORE_, ProfileSummaryInfo *PSI_) {
   SE = &SE_;
   LI = &LI_;
   TTI = &TTI_;
LoopVectorizeResult LoopVectorizePass::runImpl(
   // 1. the target claims to have no vector registers, and
   // 2. interleaving won't help ILP.
   //
   // The second condition is necessary because, even if the target has no
   // vector registers, loop vectorization may still enable scalar
   // interleaving.
   if (!TTI->getNumberOfRegisters(TTI->getRegisterClassForType(true)) &&
       TTI->getMaxInterleaveFactor(1) < 2)
-    return false;
+    return LoopVectorizeResult(false, false);
 
-  bool Changed = false;
+  bool Changed = false, CFGChanged = false;
 
   // The vectorizer requires loops to be in simplified form.
   // Since simplification may add new inner loops, it has to run before the
   // legality and profitability checks. This means running the loop vectorizer
   // will simplify all loops, regardless of whether anything end up being
   // vectorized.
   for (auto &L : *LI)
-    Changed |=
+    Changed |= CFGChanged |=
         simplifyLoop(L, DT, LI, SE, AC, nullptr, false /* PreserveLCSSA */);
 
   // Build up a worklist of inner-loops to vectorize. This is necessary as
   // the act of vectorizing or partially unrolling a loop creates new loops
   // and can invalidate iterators across the loops.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *L : *LI)
     collectSupportedLoops(*L, LI, ORE, Worklist);
 
   LoopsAnalyzed += Worklist.size();
 
   // Now walk the identified inner loops.
   while (!Worklist.empty()) {
     Loop *L = Worklist.pop_back_val();
 
     // For the inner loops we actually process, form LCSSA to simplify the
     // transform.
     Changed |= formLCSSARecursively(*L, *DT, LI, SE);
 
-    Changed |= processLoop(L);
+    Changed |= CFGChanged |= processLoop(L);
   }
 
   // Process each loop nest in the function.
-  return Changed;
+  return LoopVectorizeResult(Changed, CFGChanged);
 }
 
 PreservedAnalyses LoopVectorizePass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
     auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
     auto &LI = AM.getResult<LoopAnalysis>(F);
     auto &TTI = AM.getResult<TargetIRAnalysis>(F);
     auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
std::function<const LoopAccessInfo &(Loop &)> GetLAA =
         [&](Loop &L) -> const LoopAccessInfo & {
       LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
       return LAM.getResult<LoopAccessAnalysis>(L, AR);
     };
     const ModuleAnalysisManager &MAM =
         AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
     ProfileSummaryInfo *PSI =
         MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
-    bool Changed =
+    LoopVectorizeResult Result =
         runImpl(F, SE, LI, TTI, DT, BFI, &TLI, DB, AA, AC, GetLAA, ORE, PSI);
-    if (!Changed)
+    if (!Result.MadeAnyChange)
       return PreservedAnalyses::all();
     PreservedAnalyses PA;
 
     // 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>();
     }
     PA.preserve<BasicAA>();
     PA.preserve<GlobalsAA>();
+    if (!Result.MadeCFGChange)
+      PA.preserveSet<CFGAnalyses>();
     return PA;
 }

llvm/test/Transforms/LoopVectorize/novect-lcssa-cfg-invalidation.ll

 ; RUN: opt -S -passes="loop-vectorize,jump-threading" -debug-pass-manager < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Checks what analyses are invalidated after Loop Vectorization when no actual
 ; vectorization happens, and the only change LV makes is LCSSA formation.
 
 define i32 @novect(i32* %p) {
 
 ; CHECK:           Running pass: LoopVectorizePass on novect
 ; CHECK:           Invalidating all non-preserved analyses for: novect
 ; CHECK:           Clearing all analysis results for: <possibly invalidated loop>
 ; CHECK:           Invalidating analysis: ScalarEvolutionAnalysis on novect
-; CHECK:           Invalidating analysis: BranchProbabilityAnalysis on novect
-; CHECK:           Invalidating analysis: BlockFrequencyAnalysis on novect
+; CHECK-NOT:       Invalidating analysis: BranchProbabilityAnalysis on novect
+; CHECK-NOT:       Invalidating analysis: BlockFrequencyAnalysis on novect
 ; CHECK:           Invalidating analysis: DemandedBitsAnalysis on novect
 ; CHECK:           Invalidating analysis: MemorySSAAnalysis on novect
 ; CHECK:           Running pass: JumpThreadingPass on novect
 
 ; CHECK:           entry:
 ; CHECK:             br label %middle
 ; CHECK:           middle:
 ; CHECK:             %iv = phi i32 [ 0, %entry ], [ %iv.next, %middle ]