[SCEV] Apply conditions involving constants first in applyLoopGuards.

[fhahn]

Summary

In some cases the order conditions are applied in can pessimize results.
In general, applying conditions with constant operands should lead to
better results. I think ideally we would apply conditions with operands
that are not involved in any other condition first, but processing
conditions with constants should be a good start.

Alternatively we could re-write all collected expressions after
collecting them. But that's likely more expensive.

Depends on D126460.

Fixes #55645.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

14565

I don't understand this comparison function. If A is constant and B is not, this returns that A is smaller than B. If B is constant and A is not then ... this also returns that A is smaller than B?

[fhahn]

Thanks for taking a look! Unfortunately this only worked by accident and I missed that there aren't any tests with the conditions in reverse order.

I think the real issue here is that we need to apply the conditions that constraint the value range first and the rewriting as multiple last.

[fhahn]

Update sort order to apply conditions that constraint ranges using max/min (predicates != EQ & != NE).

This ensures we rewrite conditons involving URem checks last, which can lead to better results.

[alonkom]

llvm/lib/Analysis/ScalarEvolution.cpp

14554

Even with this sorting won't we lose information about the min/max values of the value?
For example if we know (tc > 0) and (tc % 8 == 0) and we process (tc % 8 == 0) last, AFAIU the SCEV expression will be overridden to (tc / 8) * 8 and we'll lose the fact that the trip count is also positive.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

14563

There may be range comparisons using eq/ne as well, with != 0 probably being the only important one. Possibly we should not be collecting Terms but already classified conditions (i.e. either known factor or known range limit)?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

14560

Use isRelational

[mkazantsev]

Marking as "request changes" just to reduce my list. Feel free to update when the comments are addressed!

llvm/test/Analysis/ScalarEvolution/trip-multiple-guard-info.ll

107

Precommit test?