This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.
ClosedPublic

Authored by fhahn on Feb 14 2023, 3:14 PM.

Details

Summary

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improvements by
strengthening flags after creating the AddRec.

I'll also share a follow-up patch that removes the code to strengthen
flags when creating SCEV[Zero,Sign]ExtendExprs. Modifying AddRecs while
creating those can lead to surprising changes.

Compile-time looks neutral:
https://llvm-compile-time-tracker.com/compare.php?from=94676cf8a13c511a9acfc24ed53c98964a87bde3&to=aced434e8b103109104882776824c4136c90030d&stat=instructions:u

Diff Detail

Event Timeline

fhahn created this revision.Feb 14 2023, 3:14 PM
fhahn requested review of this revision.Feb 14 2023, 3:14 PM

Wow. How do we live without that? :)

I remember that in the past attempts of lower inference of some flags led to some cyclic dependencies and infinite loops, so I don't know if it can be the case here. But hopefully testing will reveal that.

llvm/lib/Analysis/ScalarEvolution.cpp
5739

Should we update Flags here to have more optimistic flags for BEInst?

5870

Same here.

fhahn marked 2 inline comments as done.Feb 16 2023, 8:47 AM
fhahn added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
5739

I tried to do that in D144197, but it seems the only change is a single regression; I've not looked into it in detail so far though.

fhahn updated this revision to Diff 498042.Feb 16 2023, 8:47 AM
fhahn marked an inline comment as done.

Rebase, updated last missing tests.

Wow. How do we live without that? :)

I remember that in the past attempts of lower inference of some flags led to some cyclic dependencies and infinite loops, so I don't know if it can be the case here. But hopefully testing will reveal that.

So far I didn't spot any issue in my testing, if there's a cyclic dependency this should be straight-forward to find once this lands.

mkazantsev added inline comments.Feb 16 2023, 10:05 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5739

It's not exactly what I mean, I mean smth like

if (auto *AR = dyn_cast<SCEVAddRecExpr>(PHISCEV)) {
  Flags = Flags | proveNoWrapViaConstantRanges(AR);
 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), Flags);
}
// further on, updated Flags is used, see line 5749.
nikic added a comment.Feb 17 2023, 7:23 AM

I think ideally we'd want this to happen in getOrCreateAddRec(), so we always infer these flags, even if the addrec is not created from IR. But a naive approach to that would probably run into issues because BE count calculation will need the addrec in the first place. So I think this patch is a reasonable starting point for now, and gets most of the test diff out of the way.

Note that there is a failing polly test.

llvm/test/Analysis/ScalarEvolution/range-signedness.ll
1

Broken test

llvm/test/CodeGen/Thumb2/mve-laneinterleaving-reduct.ll
4

Why did these tests get deleted?

fhahn updated this revision to Diff 498599.Feb 18 2023, 10:29 AM
fhahn marked an inline comment as done.

I think ideally we'd want this to happen in getOrCreateAddRec(), so we always infer these flags, even if the addrec is not created from IR. But a naive approach to that would probably run into issues because BE count calculation will need the addrec in the first place. So I think this patch is a reasonable starting point for now, and gets most of the test diff out of the way.

Agreed, doing it in getOrCreateAddRec would a nice follow-up improvement. I'll look into it.

Note that there is a failing polly test.

Updated the failing test and restored the 2 tests pointed out.

fhahn marked an inline comment as done.Feb 18 2023, 10:30 AM
fhahn added inline comments.
llvm/test/Analysis/ScalarEvolution/range-signedness.ll
1

Ah yes, switched to updating it manually.

llvm/test/CodeGen/Thumb2/mve-laneinterleaving-reduct.ll
4

I forgot to re-add the other functions while I was checking the change in @correlate. Brought them back now.

It looks like there are two regressions in tests, any idea what causes them?

llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll
15

Regression

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
20

Regression

llvm/test/Transforms/LoopUnroll/peel-loop-conditions.ll
648

Comment might need an update.

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll
104

Looks like a spurious test regeneration change?

fhahn updated this revision to Diff 500270.Feb 24 2023, 11:59 AM
fhahn marked 3 inline comments as done.

Rebase, remove test comment and unneeded changes.

fhahn marked 2 inline comments as done.Feb 24 2023, 12:04 PM
fhahn added inline comments.
llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll
15

This one seems to be caused by proveNoSignedWrapViaInduction failing to strengthen flags later due to different evaluation order for an AddRec that's computed when building another AddRec after strengthening flags earlier here. This could be fixed by also strengthening using proveNoSignedWrapViaInduction earlier as in D144753

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
20

I still need to investigate this one.

llvm/test/Transforms/LoopUnroll/peel-loop-conditions.ll
648

Remove the comment. %i.05 is in range from [0, 3) for %inc = add i32 %i.05, 1, so inferring nsw should be correct.

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll
104

Yep, undid the changes.

fhahn marked 3 inline comments as done.Mar 6 2023, 8:59 AM

What are the current thoughts on the next steps to move forward with this. As for the 2 regressions, I think the one in llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll won't be easily resolve-able. The other one can be solved by a follow-up (D144753), but it needs a bit more work because currently it triggers an infinite loop in a test case.

llvm/lib/Analysis/ScalarEvolution.cpp
5739

Ah I see, thanks! I put up D145395 as follow-up. Although I am not sure if it is correct for all cases, as the strengthening with ranges may be independent of BEValue overflowing.

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
20

Ok, here's what's going on.

Without this patch, this is strengthened by this code here:
https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ScalarEvolution.cpp#L1651

With the new changes, this code now gets called earlier via the call to proveNoWrapViaConstantRanges, which in turn computes the backedge taken-count, which in turn calls getSCEVAtScope, which in turn creates the SCEV for %idxprom20. Because getSCEVAtScope constructs the SCEV for %idxprom20 while computing the backedge taken count, the backedge taken count will be SCEVCouldNotCompute at L1651, hence the flags don't get strengthened.

I don't know if there's a way to avoid this issue, but it seems a small price to pay in this case.

mkazantsev accepted this revision.Mar 6 2023, 8:48 PM

LG

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
20

Interesting. If we have proved that the range here only contains 3, can we just reduce it to SCEVConstant?

I believe that if a loop has zero BE taken count, all its AddRecs are <nuw><nsw> too.

This revision is now accepted and ready to land.Mar 6 2023, 8:48 PM
mkazantsev added inline comments.Mar 6 2023, 8:50 PM
llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
20

I think we might have a fundamental issue with being unable construct anything but AddRec for an IV, even in such loops.

nikic accepted this revision.Mar 7 2023, 12:09 AM

LGTM

fhahn marked an inline comment as done.Mar 7 2023, 7:45 AM
fhahn added inline comments.
llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
20

It should be possible to simplify AddRecs (and any other SCEV expression) to a constant if the range for it is a single-element range: https://github.com/llvm/llvm-project/commit/ce3286116dc7e00c5c61db6c92e771f531ff38cd

This naive version has quite a bit of fallout in terms of test changes and some regressions (presumably because various places expect AddRecs and would need updating)

It also has a notable compile-time impact https://llvm-compile-time-tracker.com/compare.php?from=fbb73422260c6eae2ddbde299a266557a5bce8de&to=ce3286116dc7e00c5c61db6c92e771f531ff38cd&stat=instructions:u

This revision was landed with ongoing or failed builds.Mar 7 2023, 8:11 AM
This revision was automatically updated to reflect the committed changes.