[InstCombine] use loop info when running the pass after loop vectorization

[david-arm]

Summary

This is the follow-up to D144199 and suggestion from D144045.
We make use of loop info explicit via InstCombine pass
parameter rather than semi-arbitrary via caching.

The only InstCombine transform that uses LoopInfo currently is
a GEP fold in visitGEPOfGEP(), so that shows up as a failure in
the dedicated test for the fold as well as several
LoopVectorizer tests that run extra passes.

I don't see any pass manager regression tests that actually
check for pass options, but based on the LoopVectorizer test
expectations, I assumed that we want to use loop analysis on
all of the InstCombine invocations following vectorization.

Co-authored-by: Sanjay Patel <[e-mail]>

[spatel]

Compile-time appears to be almost the same with this patch:
https://llvm-compile-time-tracker.com/compare.php?from=7067aee367d40882cf8324357ab5a09275a590b6&to=acda66ccbf5a30300fa646c33c70d703cb614347&stat=instructions:u
...so I think that means we're doing the same amount of loop analysis as before.

[nikic]

I've commented with my understanding of the current behavior (excluding cases where analyses are "accidentally" preserved). TBH I'm not entirely sure what to do here. I don't think the LoopVectorize tests had any particular intention (just used whatever the behavior was).

For D144045, I guess we only need LoopInfo for the very last InstCombine run after LICM. But for the GEP swapping fold, we need it before LICM. Probably to be robust, that part shouldn't be performed by InstCombine at all and done by LICM itself (i.e. reassociate if it enables LICM).

llvm/lib/Passes/PassBuilderPipelines.cpp

1171

Looks right: LoopVectorize requires LoopInfo and LoopUnroll, SROA will preserve it.

1184

Looks right: EarlyCSE and CVP are CFG-preserving, and we still have LoopInfo from above.

1198

Doesn't look right: SimplifyCFG invalidates LoopInfo.

1220

Doesn't look right: SimplifyCFG invalides LoopInfo and SCCP doesn't require it.

1235

Same here, nothing has requested LoopInfo since.

1258

Looks right, LoopUnroll requested LoopInfo, SROA preserved.

1272

Looks right, AlignmentFromAssumptions requires LoopInfo.

[spatel]

llvm/lib/Passes/PassBuilderPipelines.cpp

1198

I suspect we'll be fine not using LoopInfo on the pre-LICM invocations, so I can change these.

But let me check my understanding: by not right, do you mean we could be regenerating loop info here, or there's a potential miscompile from using invalid LoopInfo? SimplifyCFG should report/invalidate if LoopInfo might have changed? InstCombine is now doing this:

LI = &AM.getResult<LoopAnalysis>(F);

...so that should not get a stale/invalid analysis?

[spatel]

Patch updated:
Changed instcombine pipeline invocations to not use loop info unless it is already available, so this is effectively NFC.

I didn't change the LoopVectorizer test RUN lines from the previous draft; we could instead update the CHECK lines. If we eventually move the GEP transform from InstCombine to LICM as suggested, I think we'd update the vectorizer tests again and see the difference in the CHECK lines.

[spatel]

Ping.

[fhahn]

This should probably have an instcombine test that shows the difference between instcombine<use-loop-info> and plain instcombine?

[spatel]

In D144274#4167715, @fhahn wrote:

This should probably have an instcombine test that shows the difference between instcombine<use-loop-info> and plain instcombine?

Yes, I can add a RUN line for "constant-fold-gep.ll" to show it. The affected test is "gep_plus_addr_sub_self_in_loop". It could be done as a preliminary NFC patch or part of this one.

[spatel]

Patch updated:
Add a RUN line to the instcombine test to show with and without loop info test diff.

[tschuett]

It is odd to me that instcombine has two modes: with and without loopinfo. Wouldn't completely removing loopinfo make instcombine better testable, hermetic, and predictable?

[spatel]

In D144274#4167818, @tschuett wrote:

It is odd to me that instcombine has two modes: with and without loopinfo. Wouldn't completely removing loopinfo make instcombine better testable, hermetic, and predictable?

Yes, an option-free pass would be better in isolation, but we are trying to balance the goals of the pass and its effect on the entire opt pipeline.
Some notes to summarize how we got here and the expected path forward:

1. The GEP transform that currently uses LoopInfo probably doesn't even belong in InstCombine; it should be moved to LICM.
2. The fdiv transform from D144045 is motivating this change. I'm proposing to allow LoopInfo to guide that fold (and likely others that are similar) because the main alternative so far is to add more passes to the pipeline to get the outcome we want. That's not good for compile-time.
3. Another alternative is to defer to codegen - that would either be CodeGenPrepare (because SDAG is limited to a single basic block) or GISel - but we would still be going back and forth on transforms, so it's not great for overall efficiency.
4. See D143631 and D87479 for previous discussion and details.

[david-arm]

From what I can see the patch LGTM! It seems like all review comments have been addressed and this patch then unblocks D144045.

[nikic]

Hm, it looks like this ended up causing non-trivial codegen changes: https://llvm-compile-time-tracker.com/compare.php?from=772aa05452f8ff90a47168e6801cda2acb5a1873&to=43ae4b62b2671cf73e691c0b53324cd39405cd51&stat=size-text So we're not preserving previous behavior in some significant way(s).

[spatel]

In D144274#4186866, @nikic wrote:

Hm, it looks like this ended up causing non-trivial codegen changes: https://llvm-compile-time-tracker.com/compare.php?from=772aa05452f8ff90a47168e6801cda2acb5a1873&to=43ae4b62b2671cf73e691c0b53324cd39405cd51&stat=size-text So we're not preserving previous behavior in some significant way(s).

Thanks - I reverted with 43ae4b62b267.
It's unlikely that I will be able to investigate those diffs in the near term, so hopefully someone else can commandeer/edit this patch and update D144045.

[david-arm]

In D144274#4186897, @spatel wrote:

In D144274#4186866, @nikic wrote:

Hm, it looks like this ended up causing non-trivial codegen changes: https://llvm-compile-time-tracker.com/compare.php?from=772aa05452f8ff90a47168e6801cda2acb5a1873&to=43ae4b62b2671cf73e691c0b53324cd39405cd51&stat=size-text So we're not preserving previous behavior in some significant way(s).

Thanks - I reverted with 43ae4b62b267.
It's unlikely that I will be able to investigate those diffs in the near term, so hopefully someone else can commandeer/edit this patch and update D144045.

Hi @sanjay, thanks for landing the patch anyway!

@nikic, do you still believe this patch is the correct way forward in order to enable D144045? It sounds like your main concern is that we're probably missing some other places where we need to set UseLoopInfo? It would be to make progress on D144045, or indeed any approach that fixes the fdiv sinking issue!

[david-arm]

I think I've found the problem - the patch was missing another case that needs the loop info option.

[david-arm]

I have spoken with @spatel who said he is unlikely to have much time to progress this patch and he's happy for me to commandeer it.

[david-arm]

• Added a missing place where we require the loop info.

[fhahn]

In D144274#4216205, @david-arm wrote:

I think I've found the problem - the patch was missing another case that needs the loop info option.

great, would it be possible to add a phase ordering test that demonstrates the issue and shows that it is fixed with the latest version?

[tschuett]

There is no space for an InstCombineWithLoopInfo to avoid all the phase ordering issues?

[david-arm]

In D144274#4219354, @fhahn wrote:

In D144274#4216205, @david-arm wrote:

I think I've found the problem - the patch was missing another case that needs the loop info option.

great, would it be possible to add a phase ordering test that demonstrates the issue and shows that it is fixed with the latest version?

I can certainly try, although I don't really know what a phase ordering test is. The phases haven't changed I don't think - we're just definitely ensuring we have loop info instead of hoping it was cached. Can you provide any examples of other tests that I can look at?

[david-arm]

In D144274#4219397, @tschuett wrote:

There is no space for an InstCombineWithLoopInfo to avoid all the phase ordering issues?

Hi @tschuett, sorry I don't really understand what you mean. Can you explain what you would like me to do?

[tschuett]

In D144274#4219406, @david-arm wrote:

In D144274#4219397, @tschuett wrote:

There is no space for an InstCombineWithLoopInfo to avoid all the phase ordering issues?

Hi @tschuett, sorry I don't really understand what you mean. Can you explain what you would like me to do?

I don't want you to do anything. I already said above that InstCombine behaves differently depending on whether it has a LoopInfo or not.

[nikic]

I've put up https://reviews.llvm.org/D146813 to move the loop invariant GEP reassociation into LICM, which should allow us to drop the LoopInfo dependency from InstCombine.

[david-arm]

In D144274#4219580, @nikic wrote:

I've put up https://reviews.llvm.org/D146813 to move the loop invariant GEP reassociation into LICM, which should allow us to drop the LoopInfo dependency from InstCombine.

Hi @nikic, ok thanks! But isn't the LoopInfo still needed for D144045, i.e. we use it to determine whether or not we should sink the fdiv?

[david-arm]

• Rebase.

[david-arm]

• Rebase.

[sdesmalen]

At the moment this patch is NFC because after rG2ec1d0f427c7822540352c0c14d057e7bfe4f77b there are no longer any combines that make use of LoopInfo. So this patch probably isn't very useful in isolation (i.e. without D144045)?

llvm/lib/Passes/PassBuilderPipelines.cpp

void PassBuilder::addVectorPasses(OptimizationLevel Level,
   }
 
   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());
+  FPM.addPass(InstCombinePass(InstCombineOptions().setUseLoopInfo(true)));
 
   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.
     ExtraPasses.addPass(EarlyCSEPass());
     ExtraPasses.addPass(CorrelatedValuePropagationPass());
-    ExtraPasses.addPass(InstCombinePass());
+    ExtraPasses.addPass(
+        InstCombinePass(InstCombineOptions().setUseLoopInfo(true)));
     LoopPassManager LPM;
     LPM.addPass(LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap,
                          /*AllowSpeculation=*/true));
     LPM.addPass(SimpleLoopUnswitchPass(/* NonTrivial */ Level ==
                                        OptimizationLevel::O3));
     ExtraPasses.addPass(
         RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
     ExtraPasses.addPass(
         createFunctionToLoopPassAdaptor(std::move(LPM), /*UseMemorySSA=*/true,
                                         /*UseBlockFrequencyInfo=*/true));
     ExtraPasses.addPass(
         SimplifyCFGPass(SimplifyCFGOptions().convertSwitchRangeToICmp(true)));
     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
   // convert to more optimized IR using more aggressive simplify CFG options.
   // The extra sinking transform can create larger basic blocks, so do this
   // before SLP vectorization.
   FPM.addPass(SimplifyCFGPass(SimplifyCFGOptions()
                                   .forwardSwitchCondToPhi(true)
                                   .convertSwitchRangeToICmp(true)
                                   .convertSwitchToLookupTable(true)
                                   .needCanonicalLoops(false)
                                   .hoistCommonInsts(true)
                                   .sinkCommonInsts(true)));
 
   if (IsFullLTO) {
     FPM.addPass(SCCPPass());
     FPM.addPass(InstCombinePass());
     FPM.addPass(BDCEPass());
   }
 
   // Optimize parallel scalar instruction chains into SIMD instructions.
   if (PTO.SLPVectorization) {
     FPM.addPass(SLPVectorizerPass());
     if (Level.getSpeedupLevel() > 1 && ExtraVectorizerPasses) {
       FPM.addPass(EarlyCSEPass());
     }
   }
   // Enhance/cleanup vector code.
   FPM.addPass(VectorCombinePass());
 
   if (!IsFullLTO) {
-    FPM.addPass(InstCombinePass());
+    FPM.addPass(InstCombinePass(InstCombineOptions().setUseLoopInfo(true)));
     // Unroll small loops to hide loop backedge latency and saturate any
     // parallel execution resources of an out-of-order processor. We also then
     // need to clean up redundancies and loop invariant code.
     // FIXME: It would be really good to use a loop-integrated instruction
     // combiner for cleanup here so that the unrolling and LICM can be pipelined
     // across the loop nests.
     // We do UnrollAndJam in a separate LPM to ensure it happens before unroll
     if (EnableUnrollAndJam && PTO.LoopUnrolling) {
       FPM.addPass(createFunctionToLoopPassAdaptor(
           LoopUnrollAndJamPass(Level.getSpeedupLevel())));
     }
     FPM.addPass(LoopUnrollPass(LoopUnrollOptions(
         Level.getSpeedupLevel(), /*OnlyWhenForced=*/!PTO.LoopUnrolling,
         PTO.ForgetAllSCEVInLoopUnroll)));
     FPM.addPass(WarnMissedTransformationsPass());
     // Now that we are done with loop unrolling, be it either by LoopVectorizer,
     // or LoopUnroll passes, some variable-offset GEP's into alloca's could have
     // become constant-offset, thus enabling SROA and alloca promotion. Do so.
     // NOTE: we are very late in the pipeline, and we don't have any LICM
     // or SimplifyCFG passes scheduled after us, that would cleanup
     // the CFG mess this may created if allowed to modify CFG, so forbid that.
     FPM.addPass(SROAPass(SROAOptions::PreserveCFG));
-    FPM.addPass(InstCombinePass());
+    FPM.addPass(InstCombinePass(InstCombineOptions().setUseLoopInfo(true)));
     FPM.addPass(
         RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
     FPM.addPass(createFunctionToLoopPassAdaptor(
         LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap,
                  /*AllowSpeculation=*/true),
         /*UseMemorySSA=*/true, /*UseBlockFrequencyInfo=*/true));
   }
 
   // Now that we've vectorized and unrolled loops, we may have more refined
   // alignment information, try to re-derive it here.
   FPM.addPass(AlignmentFromAssumptionsPass());
 
   if (IsFullLTO)
-    FPM.addPass(InstCombinePass());
+    FPM.addPass(InstCombinePass(InstCombineOptions().setUseLoopInfo(true)));
 }
 
 ModulePassManager
 PassBuilder::buildModuleOptimizationPipeline(OptimizationLevel Level,
                                              ThinOrFullLTOPhase LTOPhase) {
   const bool LTOPreLink = isLTOPreLink(LTOPhase);
   ModulePassManager MPM;
 

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 PreservedAnalyses InstCombinePass::run(Function &F,
                                        FunctionAnalysisManager &AM) {
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 
-  // TODO: Only use LoopInfo when the option is set. This requires that the
-  //       callers in the pass pipeline explicitly set the option.
-  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
-  if (!LI && Options.UseLoopInfo)
+  // Only use LoopInfo when the option is set by callers.
+  LoopInfo *LI = nullptr;
+  if (Options.UseLoopInfo)
     LI = &AM.getResult<LoopAnalysis>(F);
 
   auto *AA = &AM.getResult<AAManager>(F);
   auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
   ProfileSummaryInfo *PSI =
       MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
   auto *BFI = (PSI && PSI->hasProfileSummary()) ?
       &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;

llvm/test/Transforms/LoopVectorize/ARM/mve-reductions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -passes=loop-vectorize,instcombine,simplifycfg -simplifycfg-require-and-preserve-domtree=1 -tail-predication=enabled < %s -S -o - | FileCheck %s
+; RUN: opt -passes='loop-vectorize,instcombine<use-loop-info>,simplifycfg' -simplifycfg-require-and-preserve-domtree=1 -tail-predication=enabled < %s -S -o - | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "thumbv8.1m.main-arm-none-eabi"
 
 ; Should not be vectorized
 define i64 @add_i64_i64(ptr nocapture readonly %x, i32 %n) #0 {
 ; CHECK-LABEL: @add_i64_i64(
 ; CHECK-NEXT:  entry:

llvm/test/Transforms/LoopVectorize/X86/x86-interleaved-accesses-masked-group.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -mcpu=skx -S -passes=loop-vectorize,instcombine,simplifycfg -simplifycfg-require-and-preserve-domtree=1 -force-vector-width=8 -force-vector-interleave=1 -enable-interleaved-mem-accesses < %s | FileCheck %s -check-prefix=DISABLED_MASKED_STRIDED
-; RUN: opt -mcpu=skx -S -passes=loop-vectorize,instcombine,simplifycfg -simplifycfg-require-and-preserve-domtree=1 -force-vector-width=8 -force-vector-interleave=1 -enable-interleaved-mem-accesses  -enable-masked-interleaved-mem-accesses < %s | FileCheck %s -check-prefix=ENABLED_MASKED_STRIDED
+; RUN: opt -mcpu=skx -S -passes='loop-vectorize,instcombine<use-loop-info>,simplifycfg' -simplifycfg-require-and-preserve-domtree=1 -force-vector-width=8 -force-vector-interleave=1 -enable-interleaved-mem-accesses < %s | FileCheck %s -check-prefix=DISABLED_MASKED_STRIDED
+; RUN: opt -mcpu=skx -S -passes='loop-vectorize,instcombine<use-loop-info>,simplifycfg' -simplifycfg-require-and-preserve-domtree=1 -force-vector-width=8 -force-vector-interleave=1 -enable-interleaved-mem-accesses  -enable-masked-interleaved-mem-accesses < %s | FileCheck %s -check-prefix=ENABLED_MASKED_STRIDED
 
 target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
 target triple = "i386-unknown-linux-gnu"
 
 ; When masked-interleaved-groups are disabled:
 ; Check that the predicated load is not vectorized as an
 ; interleaved-group but rather as a scalarized accesses.
 ; (For SKX, Gather is not supported by the compiler for chars, therefore

llvm/test/Transforms/LoopVectorize/X86/x86-interleaved-store-accesses-with-gaps.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -mcpu=skx -S -passes='loop-vectorize,instcombine,simplifycfg,loop-mssa(licm)' -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses -prefer-predicate-over-epilogue=predicate-dont-vectorize < %s | FileCheck %s -check-prefix=DISABLED_MASKED_STRIDED
-; RUN: opt -mcpu=skx -S -passes='loop-vectorize,instcombine,simplifycfg,loop-mssa(licm)' -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses  -enable-masked-interleaved-mem-accesses -prefer-predicate-over-epilogue=predicate-dont-vectorize < %s | FileCheck %s -check-prefix=ENABLED_MASKED_STRIDED
+; RUN: opt -mcpu=skx -S -passes='loop-vectorize,instcombine<use-loop-info>,simplifycfg,loop-mssa(licm)' -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses -prefer-predicate-over-epilogue=predicate-dont-vectorize < %s | FileCheck %s -check-prefix=DISABLED_MASKED_STRIDED
+; RUN: opt -mcpu=skx -S -passes='loop-vectorize,instcombine<use-loop-info>,simplifycfg,loop-mssa(licm)' -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses  -enable-masked-interleaved-mem-accesses -prefer-predicate-over-epilogue=predicate-dont-vectorize < %s | FileCheck %s -check-prefix=ENABLED_MASKED_STRIDED
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; (1) Interleave-group with factor 4, storing only 2 members out of the 4.
 ; Check that when we allow masked-memops to support interleave-group with gaps,
 ; the store is vectorized using a wide masked store, with a 1,1,0,0,1,1,0,0,... mask.
 ; Check that when we don't allow masked-memops to support interleave-group with gaps,

llvm/test/Transforms/LoopVectorize/interleaved-accesses.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -passes=loop-vectorize,instcombine -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses=true -runtime-memory-check-threshold=24 < %s | FileCheck %s
+; RUN: opt -S -passes='loop-vectorize,instcombine<use-loop-info>' -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses=true -runtime-memory-check-threshold=24 < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 
 ; Check vectorization on an interleaved load group of factor 2 and an interleaved
 ; store group of factor 2.
 
 ; int AB[1024];
 ; int CD[1024];