This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by david-arm on Feb 17 2023, 9:01 AM.

Details

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 <spatel@rotateright.com>

Diff Detail

Event Timeline

spatel created this revision.Feb 17 2023, 9:01 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 17 2023, 9:01 AM
spatel requested review of this revision.Feb 17 2023, 9:01 AM

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.

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
1116

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

1129

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

1143

Doesn't look right: SimplifyCFG invalidates LoopInfo.

1165

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

1180

Same here, nothing has requested LoopInfo since.

1203

Looks right, LoopUnroll requested LoopInfo, SROA preserved.

1217

Looks right, AlignmentFromAssumptions requires LoopInfo.

spatel added inline comments.Feb 20 2023, 6:41 AM
llvm/lib/Passes/PassBuilderPipelines.cpp
1143

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 updated this revision to Diff 499825.Feb 23 2023, 6:41 AM
spatel marked 7 inline comments as done.

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.

fhahn added a subscriber: fhahn.Mar 3 2023, 10:57 AM

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

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 updated this revision to Diff 502203.Mar 3 2023, 11:35 AM

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

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?

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 accepted this revision.Mar 6 2023, 5:56 AM
david-arm added a subscriber: 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.

This revision is now accepted and ready to land.Mar 6 2023, 5:56 AM
nikic added a comment.Mar 11 2023, 1:10 PM

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

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.

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 reopened this revision.Mar 23 2023, 4:57 AM

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

This revision is now accepted and ready to land.Mar 23 2023, 4:57 AM
david-arm commandeered this revision.Mar 23 2023, 4:58 AM
david-arm edited reviewers, added: spatel; removed: 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.

This revision now requires review to proceed.Mar 23 2023, 4:58 AM
david-arm updated this revision to Diff 507719.Mar 23 2023, 6:23 AM
david-arm edited the summary of this revision. (Show Details)
  • Added a missing place where we require the loop info.
david-arm edited the summary of this revision. (Show Details)Mar 23 2023, 6:27 AM
fhahn added a comment.Mar 24 2023, 6:35 AM

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?

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

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?

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?

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 added a comment.Mar 24 2023, 7:54 AM

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.

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?

khchen added a subscriber: khchen.Apr 12 2023, 11:43 PM

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

david-arm abandoned this revision.Jul 10 2023, 2:37 AM