Page MenuHomePhabricator

[SCEV] Fix finite loop non-strict predicate simplification (PR60944)
ClosedPublic

Authored by nikic on Tue, Mar 7, 8:20 AM.

Details

Summary

There are a number of issues with the current code for converting ule -> ult (etc) predicates for comparisons controlling finite loops:

  • It sets nowrap flags, which may only hold for that particular comparison, not globally. (PR60944)
  • It doesn't check that the RHS is invariant. (I'm not sure this can cause practical issues independently of the previous point.)
  • It runs before simplifications that may be more profitable. (PR54191)

This patch moves the handling for this into computeExitLimitFromICmp(), because it is somewhat tightly coupled with assumptions in that code, and addresses the aforementioned issues.

Fixes https://github.com/llvm/llvm-project/issues/60944.
Fixes https://github.com/llvm/llvm-project/issues/54191.

Diff Detail

Event Timeline

nikic created this revision.Tue, Mar 7, 8:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Mar 7, 8:20 AM
nikic requested review of this revision.Tue, Mar 7, 8:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Mar 7, 8:20 AM
mkazantsev added inline comments.Wed, Mar 8, 7:58 PM
llvm/lib/Analysis/ScalarEvolution.cpp
9184

Can this overflow?

StephenFan added inline comments.Wed, Mar 8, 9:48 PM
llvm/lib/Analysis/ScalarEvolution.cpp
9184

Yes, it can. Although it can't overflow in loop L, it still may overflow somewhere out of the loop. See test file pr60944.ll below.
In loop2, %iv + 1 can not overflow as a result of mustprogress attribute, but %iv + 1 can still overflow in loop.

mkazantsev added inline comments.Mon, Mar 13, 12:43 AM
llvm/lib/Analysis/ScalarEvolution.cpp
9184

I don't quite get the logic here. Imagine that the loops has two exits, one exit is iv <= MAX_INT (so it is never taken) and another exit is guaranteed to exit in 100 iterations (so the loop is finite). Then you just turn this first exit condition into iv < MIN_INT which is trivially false and immediately exit on the 1st iteration. To me it doesn't matter if the loop is finite or not, you cannot add one here.

nikic added inline comments.Mon, Mar 13, 1:02 AM
llvm/lib/Analysis/ScalarEvolution.cpp
9184

ControllingFiniteLoop is ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L). This means that the lopo is finite *and* only has one exit.

mkazantsev added inline comments.Mon, Mar 13, 8:46 PM
llvm/lib/Analysis/ScalarEvolution.cpp
9184

I don't understand. Here is what ControlsExit is from the comment of computeExitLimitFromCond:

/// \p ControlsExit is true if ExitCond directly controls the exit
/// branch. In this case, we can assume that the loop exits only if the
/// condition is true and can infer that failing to meet the condition prior
/// to integer wraparound results in undefined behavior.

It doesn't mean that there is only one exit. It only means that, no matter what exit is taken, the condition is going to be true. How do you infer ability to add 1 and guarantee the new (non-equivalent) condition under the same circumstances?

mkazantsev accepted this revision.Tue, Mar 14, 2:42 AM

Ok, thanks for clarification. Maybe rename this into IsOnlyExit or ControlsOnlyExit?

This revision is now accepted and ready to land.Tue, Mar 14, 2:42 AM
This revision was landed with ongoing or failed builds.Tue, Mar 14, 2:59 AM
This revision was automatically updated to reflect the committed changes.