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

[nikic]

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.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9184

Can this overflow?

[StephenFan]

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]

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]

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]

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?

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

9184

Clarified in https://github.com/llvm/llvm-project/commit/6d70812789c2583333c25ff15c5e2b166d66ce1b. See https://github.com/llvm/llvm-project/blob/6d70812789c2583333c25ff15c5e2b166d66ce1b/llvm/lib/Analysis/ScalarEvolution.cpp#L8826 for how this flag is set.

[mkazantsev]

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