This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] Provide eliminateIVComparison with context
ClosedPublic

Authored by mkazantsev on Mar 16 2021, 4:38 AM.

Details

Summary

We can prove more predicates when we have a context when eliminating ICmp.
As first (and very obvious) approximation we can use the ICmp instruction itself,
though in the future we are going to use a common dominator of all its users.
Need some refactoring before that.

Diff Detail

Unit TestsFailed

Event Timeline

mkazantsev created this revision.Mar 16 2021, 4:38 AM
mkazantsev requested review of this revision.Mar 16 2021, 4:38 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 16 2021, 4:38 AM
lebedev.ri added inline comments.Mar 16 2021, 4:44 AM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
265
267

It's usually called CtxI

llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll
822

Please precommit, it's a bit noisy.

mkazantsev planned changes to this revision.Mar 16 2021, 4:54 AM
mkazantsev added inline comments.
llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll
119

Looks like it's a bug needs to be fixed before we can go with it.

mkazantsev added inline comments.Mar 16 2021, 5:00 AM
llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll
119

Funny thing that both false and true are correct here.
false is obviously correct because inc is strictly positive and i.0 is non-positive, and this is what is proved without context.
However true is also correct because this is guarded by

br i1 %cmp8243, label %for.body84, label %return

which is an impossible condition. In fact, this code is unreachable so anything is OK.

mkazantsev added inline comments.Mar 16 2021, 5:08 AM
llvm/test/Transforms/IndVarSimplify/scev-expander-preserve-lcssa.ll
119

btw this is a lead for further compile time opt that we are missing. Blocks guarded by false conditions can have any predicate proved automatically, to save some time.

That's sad. I think this is happening because, when false is trivially provable without context, we still spend a lot of time proving true via context. I'll try to find a way around it...

For the compile time concern, one idea you could consider exploring would be to have a version of isKnownPredicateAt which returns an Optional<bool>. Such a routine could use the cheap proof techniques first (in both directions), and then resort to the more expensive ones. In this particular case, it would also simplify the caller code. Looking at a couple other callers, we seem to be missing some optimizations by not asking both.

If we pushed that down all the way to the loop guard processing, that could be a substantial compile time win. (As we'd walk the CFG once, not twice, in the case where we can't prove anything.)

For the compile time concern, one idea you could consider exploring would be to have a version of isKnownPredicateAt which returns an Optional<bool>. Such a routine could use the cheap proof techniques first (in both directions), and then resort to the more expensive ones. In this particular case, it would also simplify the caller code. Looking at a couple other callers, we seem to be missing some optimizations by not asking both.

If we pushed that down all the way to the loop guard processing, that could be a substantial compile time win. (As we'd walk the CFG once, not twice, in the case where we can't prove anything.)

This is a really good way to imrpove this, thank you for bringing this up. I'll consider this.

Rebased on top of new API for predicate evaluation. Now the order of checks should be from cheap to expensive. Hope this is more CT-friendly.

lebedev.ri accepted this revision.Mar 18 2021, 1:02 PM

Looks good to me.

Rebased on top of new API for predicate evaluation. Now the order of checks should be from cheap to expensive. Hope this is more CT-friendly.

It didn't really help, still within the same ballpark +/- noise i would say:
https://llvm-compile-time-tracker.com/compare.php?from=9575c48b8959dae3c3e39e0227435ae6ebd71443&to=c0e80b44e3c80fa9f344b14cbb8435c15f75f94e&stat=instructions
vs
https://llvm-compile-time-tracker.com/compare.php?from=fb04227c7cc3c5ebb3ece90f8ec5c629920eb3af&to=71476f7052b97e7ba9f91624c7fa3d3cbd418aa6&stat=instructions

As discussed in previous SCEV changes, that is probably not a blocker here, although it is not great.

This revision is now accepted and ready to land.Mar 18 2021, 1:02 PM

Well, we clearly can produce better code here. Let's hope it's worth it. I'll spend some time trying to understand how we can make SCEV cheaper.

This revision was landed with ongoing or failed builds.Mar 18 2021, 10:28 PM
This revision was automatically updated to reflect the committed changes.

I wrote
https://bugs.llvm.org/show_bug.cgi?id=52327
about a crash starting to happen with this patch.