This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Support rewriting ZExt expressions with loop guard info.
ClosedPublic

Authored by fhahn on Nov 10 2021, 9:27 AM.

Details

Summary

So far, applying loop guard information has been restricted to
SCEVUnknown. In a few cases, like PR40961 and PR52464, this leads to
SCEV failing to determine tight upper bounds for the backedge taken
count.

This patch adjusts SCEVLoopGuardRewriter and applyLoopGuards to support
re-writing ZExt expressions.

This is a first step towards fixing PR40961 and PR52464.

Diff Detail

Event Timeline

fhahn created this revision.Nov 10 2021, 9:27 AM
fhahn requested review of this revision.Nov 10 2021, 9:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 10 2021, 9:27 AM
nikic added inline comments.Nov 10 2021, 9:41 AM
llvm/lib/Analysis/ScalarEvolution.cpp
13722

Can you please add a test where you both have a condition on %x and on zext %x? I think we'll end up losing the information from the direct condition in that case.

Something I also find odd here is the mismatch between the code collecting rewrites and the visitor. We'll collect rewrites on all SCEVs, but then only rewrite unknown and zext.

fhahn updated this revision to Diff 386778.Nov 12 2021, 3:08 AM

Updated the code to also apply information collected to other expressions in the mas. This ensures we include information about sub-expressions when applying larger expressions. I added tests that show cases where we would otherwise miss information ( 5dfe60d171d7) and rebased on top of that.

I also restricted info collection to LHS that are either SCEVUnknown or SCEVZeroExtendExpr for now.

Compile-time wise this shows a very small increase on average: http://llvm-compile-time-tracker.com/compare.php?from=b57c22ade8673d68088f5638a1050e3f3c1f163d&to=5792b893889fbfd459b9ec062dedea6c130b9786&stat=instructions

NewPM-O3: +0.02%
NewPM-ReleaseThinLTO: +0.02%
NewPM-ReleaseLTO-g: +0.04%

fhahn marked an inline comment as done.Nov 12 2021, 3:14 AM
fhahn added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
13722

Can you please add a test where you both have a condition on %x and on zext %x? I think we'll end up losing the information from the direct condition in that case.

Added those tests in 5dfe60d171d7. The original version failed to apply information of sub-expressions to larger expressions, so we failed to determine the tightest bound in one the cases. I updated the patch to re-write the collected expressions with the information we collected, which should resolve that issue.

Something I also find odd here is the mismatch between the code collecting rewrites and the visitor. We'll collect rewrites on all SCEVs, but then only rewrite unknown and zext.

Good point! There are other motivating cases that require re-writing other expressions as well (for PR40961), but for now I also restricted collecting to LHSs that are either SCEVUnknown or SCEVZeroExtendExpr.

This generally looks very reasonable.

Can I request that you split off the change which switches the map from value keyed to SCEV keyed, and land that without separate review? It seems like it should be entirely NFC. Reducing diff and isolating failures is always good.

llvm/lib/Analysis/ScalarEvolution.cpp
13923

This should follow from the empty check just above.

13932

You can fold this into the previous code by simply pushing Expr onto the replacement list last.

Hm, do we need a fixed point in the loop above? It seems like we have the possibility of one replacement enabling another. Is there something non-obvious in the above which handles that?

fhahn updated this revision to Diff 386885.Nov 12 2021, 10:31 AM
fhahn marked an inline comment as done.

This generally looks very reasonable.

Can I request that you split off the change which switches the map from value keyed to SCEV keyed, and land that without separate review? It seems like it should be entirely NFC. Reducing diff and isolating failures is always good.

Thanks, I committed the SCEV->SECV map change in 03cfea68c65f and rebased the patch.

I'll respond to the inline comments in a bit.

reames accepted this revision.Nov 12 2021, 10:34 AM

Thanks for the rebase, much easier to understand.

LGTM w/the previous inline style comment addressed. You can follow up on the fixed point question post-commit if desired.

This revision is now accepted and ready to land.Nov 12 2021, 10:34 AM

Thanks for the rebase, much easier to understand.

LGTM w/the previous inline style comment addressed. You can follow up on the fixed point question post-commit if desired.

Thanks! I still need to construct a couple of test cases for the follow-up. But I thought a bit more and I think I need maintain a vector with expressions to rewrite separately, to avoid depending on the iteration order of the dense map, which may not be consistent. I'm planning to incorporate that in the commit version, independent of following up on the fixed-point iteration.

fhahn updated this revision to Diff 387301.Nov 15 2021, 9:41 AM

rebased.

@nikic it looks like there's a crash on the llvm-compile-time-tracker with the latest version (applying rewrites), but I was unable to reproduce this locally with various combinations of flags. What compiler/flags is used by the tracker to build the compiler used?

The log to the failure is http://llvm-compile-time-tracker.com/show_error.php?commit=d628e5e177b9a9dd4f279ce7c301fd312be0cfa7 in case you have any ideas.

nikic added a comment.Nov 15 2021, 9:56 AM

rebased.

@nikic it looks like there's a crash on the llvm-compile-time-tracker with the latest version (applying rewrites), but I was unable to reproduce this locally with various combinations of flags. What compiler/flags is used by the tracker to build the compiler used?

The log to the failure is http://llvm-compile-time-tracker.com/show_error.php?commit=d628e5e177b9a9dd4f279ce7c301fd312be0cfa7 in case you have any ideas.

Here's the (unreduced) IR, crashes for me under opt -O1: https://gist.github.com/nikic/bd117601aedea5f03b5750571d07624e

I just ran the /root/llvm-compile-time-tracker/llvm-project-build/bin/clang -DNDEBUG -fno-experimental-new-pass-manager -O3 -fomit-frame-pointer -flto -DNDEBUG -g -w -Werror=date-time -MD -MT tools/CMakeFiles/fpcmp-target.dir/fpcmp.c.o -MF tools/CMakeFiles/fpcmp-target.dir/fpcmp.c.o.d -o tools/CMakeFiles/fpcmp-target.dir/fpcmp.c.o -c /root/llvm-compile-time-tracker/llvm-test-suite/tools/fpcmp.c command after adjusting to local paths, but sometimes these things depend on external deps like the used libc.

rebased.

@nikic it looks like there's a crash on the llvm-compile-time-tracker with the latest version (applying rewrites), but I was unable to reproduce this locally with various combinations of flags. What compiler/flags is used by the tracker to build the compiler used?

The log to the failure is http://llvm-compile-time-tracker.com/show_error.php?commit=d628e5e177b9a9dd4f279ce7c301fd312be0cfa7 in case you have any ideas.

Here's the (unreduced) IR, crashes for me under opt -O1: https://gist.github.com/nikic/bd117601aedea5f03b5750571d07624e

I just ran the /root/llvm-compile-time-tracker/llvm-project-build/bin/clang -DNDEBUG -fno-experimental-new-pass-manager -O3 -fomit-frame-pointer -flto -DNDEBUG -g -w -Werror=date-time -MD -MT tools/CMakeFiles/fpcmp-target.dir/fpcmp.c.o -MF tools/CMakeFiles/fpcmp-target.dir/fpcmp.c.o.d -o tools/CMakeFiles/fpcmp-target.dir/fpcmp.c.o -c /root/llvm-compile-time-tracker/llvm-test-suite/tools/fpcmp.c command after adjusting to local paths, but sometimes these things depend on external deps like the used libc.

Thanks! I think I figured out the issue: RewriteMap[Expr] = Rewriter.visit(RewriteTo); may add an entry to RewriteMap before evaluating RewriteTo depending on the compiler used.

This revision was landed with ongoing or failed builds.Nov 16 2021, 3:16 AM
This revision was automatically updated to reflect the committed changes.