This is an archive of the discontinued LLVM Phabricator instance.

[ScalarEvolution] Apply loop guards against min/max for its arguments
ClosedPublic

Authored by dmakogon on Mar 3 2023, 4:28 AM.

Details

Summary

This replaces several rewriting rules in ScalarEvolution::applyLoopGuards that are applied to min/max expressions with the equivalent ones but applied to its arguments.
So currently given we have a loop guard min(a, b) >= c, the min expression gets rewritten as max(c, min(a, b)).
With such approach, we're unable to apply the rewrite if min operands are zext for example (min(zext(a), zext(b))), however it's equivalent to the expression zext(min(a, b)) for which we can apply the rewrite.
We can rewrite the min operands instead with these expressions:

  • a --> max(c, a) and
  • b --> max(c, b)

and this would allow us to apply the loop guard in this and similar cases: min(zext(a), zext(b)) would get rewritten as min(zext(max(c, a)), zext(max(c, b))) instead of just being skipped.

The table of replaced rules (omitting predicates signedness for simplicity):

Old ruleNew rules
min(a, b) >= c --> max(c, min(a, b))a --> max(a, c) and b --> max(b, c)
min(a, b) > c --> max(c + 1, min(a, b))a --> max(a, c + 1) and b --> max(b, c + 1)
max(a, b) <= c --> min(c, max(a, b))a --> min(a, c) and b --> min(b, c)
max(a, b) < c --> min(c - 1, max(a, b))a --> min(a, c - 1) and b --> min(b, c - 1)

Diff Detail

Event Timeline

dmakogon created this revision.Mar 3 2023, 4:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2023, 4:28 AM
dmakogon requested review of this revision.Mar 3 2023, 4:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2023, 4:28 AM
dmakogon updated this revision to Diff 502100.EditedMar 3 2023, 4:42 AM

There is one regression I didn't notice initially (trip-count-minmax.ll). Posted fix for review - https://reviews.llvm.org/D145231

dmakogon edited the summary of this revision. (Show Details)Mar 3 2023, 11:59 AM
dmakogon edited the summary of this revision. (Show Details)Mar 3 2023, 12:24 PM
dmakogon updated this revision to Diff 502225.Mar 3 2023, 12:39 PM

Cleanup, got rid of copy-paste code

mkazantsev requested changes to this revision.Mar 5 2023, 8:41 PM
mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
15064

This is not correct (c + 1 may overflow). Why didn't you just keep it as

//  'min(a, b) >  c'   ->   '(a > c) && (b > c)';

?

15066

Same

15089

Bug when RHS = SINT_MIN.

15108

Why do you think that eq/ne cannot come here?

This revision now requires changes to proceed.Mar 5 2023, 8:41 PM
This comment was removed by mkazantsev.
mkazantsev added a comment.EditedMar 5 2023, 8:50 PM

Okay, seems that same bug is in underlying code. I suggest to fix it first. It seems to be turning predicates that are trivially true into things that may be false .

llvm/lib/Analysis/ScalarEvolution.cpp
15108

Question withdrawn, I see.

mkazantsev added inline comments.Mar 5 2023, 9:16 PM
llvm/lib/Analysis/ScalarEvolution.cpp
15061–15068

This comment is out of place. You are not constructing c + 1 or c - 1 here, it is done in the caller code. Here enough to say that

min(a, b) > c     ->   (a > c) && (b > c); // same for >=
max(a, b) < c     ->   (a < c) && (b < c); // same for <=
mkazantsev added inline comments.Mar 5 2023, 9:19 PM
llvm/lib/Analysis/ScalarEvolution.cpp
15081–15082

I propose refactoring like:

case CmpInst::ICMP_UGT:
  RHS = RHS - 1;
  LLVM_FALLTHROUGH;
case CmpInst::ICMP_UGE:
  RewrittenRHS = getUMaxExpr(RewrittenLHS, RHS);
mkazantsev added a comment.EditedMar 5 2023, 9:20 PM

Generally, you are just replicating the bug and not introducing a new one. I don't insist that fix is blocking this one, you can make them in any order you like more. Please address restructuring comments. Also fix the bug with max/min having another number of operands than 2.

mkazantsev added inline comments.Mar 5 2023, 9:22 PM
llvm/lib/Analysis/ScalarEvolution.cpp
15080–15083

There can be more (or less?) than 2 operands.

mkazantsev added inline comments.Mar 5 2023, 9:27 PM
llvm/lib/Analysis/ScalarEvolution.cpp
15110–15111

What if the operands are also min/max? Maybe use a DFS traversal instead to collect all leaves?

mkazantsev added inline comments.Mar 5 2023, 9:28 PM
llvm/lib/Analysis/ScalarEvolution.cpp
15110–15111

I mean, non-recursive traversal using stack.

mkazantsev added inline comments.Mar 5 2023, 9:31 PM
llvm/lib/Analysis/ScalarEvolution.cpp
15091

You should set RewrittenRHS if it happens.

15093

Can we just always call AddMinMaxRewrites and, if it's not min or max, just to the trivial thing?

mkazantsev added a comment.EditedMar 5 2023, 9:40 PM

So far plans look follwing:

  1. Refactor switch cases into fallthroughs;
  2. Then, make an NFC that calls a function. Instead of
RewrittenRHS = getUMaxExpr(RewrittenLHS, RHS);

smth like

RewrittenRHS = AddRewrites(RewrittenLHS, RHS);

The handling of predicate can be moved inside this function. You don't need to have 2 predicate switches for calling, you just need one. Maybe 2nd (small) switch is only for checks and adding + - 1.

  1. Into this function, add handling of min/max (non-recursive stack-based traversal). The returned value should be the rewrite of original RewrittenLHS no matter if it's a min or not.

As a side thing - add checks that, whenever you compute RHS + - 1, it is not a MAX/MIN int respectively. In this case we should not rewrite anything.

dmakogon updated this revision to Diff 502950.EditedMar 7 2023, 1:11 AM

Thanks for the suggestions, Max.

  1. Now the switch uses fallthroughs.
  2. The expressions are now processed in a worklist, for min/max we enqueue their operands (this also means we support any number of operands).
  3. Suggest to fix +/- 1 bug in a follow-up. The bug was there before, this patch doesn't expose it anyway.

And also there was no use in adding a new function, the traversal is done in the same function as before.

dmakogon marked 10 inline comments as done.Mar 7 2023, 1:14 AM
dmakogon marked an inline comment as done.

Underlying code seems buggy to me. I'd prefer it fixed in follow-ups.

Your change mostly LG, if possible, do variable renaming as a separate patch.

Please wait couple of days in case if someone else has concerns before landing this.

llvm/lib/Analysis/ScalarEvolution.cpp
15074–15082

I know it's not your checks, but this can be changed further.

  • Why pointers are checked only for ult? ugt will also make us computations with it, and why not check it for signed?
    • Does this whole thing even make any sense for pointers?
  • Why we do umax(..., UMIN + 1) correction for unsigned but not smax(..., SMIN + 1) for signed? Why don't we do the same correction for umin(RHS, UMAX - 1) when we are about to add one? Looks like an attempt to hide some bugs.
15104

Can variable renaming be done separately?

mkazantsev accepted this revision.Mar 7 2023, 2:00 AM
This revision is now accepted and ready to land.Mar 7 2023, 2:00 AM
This revision was landed with ongoing or failed builds.Mar 13 2023, 10:06 AM
This revision was automatically updated to reflect the committed changes.