[SCEV][IndVars][WIP] Check outer loop invariant when cononicalize comparision

[StephenFan]

Summary

Before this patch, In SimplifyICmpOperands, the comparision would be cononicalized and the NUW
flag would be added if the loop is finite. The reason is as the comments
says, "since the loop is finite, the bound cannot include the corresponding
boundary (otherwise it would loop forever)." But the NUW flag that be added
also assumes the SCEV that this flag attaches is also NUW in outer loops.
It makes some transformations like IndVars eliminating comparisions
that shouldn' t been eliminated.

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

I am new to ScalarEvolution. So I am not sure if it is a right fix.

[nikic]

It would be easier to say with a reduced test case, but this is very likely not the right fix. SCEV nowrap flags must hold unconditionally (i.e., on any well-defined execution, nowrap flags must hold at any point where the SCEV expression is defined). In this context, we only know that the expression does not wrap at that particular use. We should not be setting the flag in this case.

Though I think we should just revert D118090 entirely. It also has a number of regressions reported on the review, and together with this issue, I think it's best to revert.

llvm/test/Transforms/IndVarSimplify/pr60944.ll

1

Please reduce the test case.

[wsmoses]

If it’s possible to not revert that would be preferable as @jdoefert @vchuravy I and others have many applications that would have significant slow down if reverted.

[efriedma]

From my analysis of the testcase, we called "getAddExpr(SCEV::FlagNUW)" while analyzing the first loop, and that broke the analysis of the second loop. The actual simplification isn't relevant.

[StephenFan]

In D144861#4160179, @efriedma wrote:

From my analysis of the testcase, we called "getAddExpr(SCEV::FlagNUW)" while analyzing the first loop, and that broke the analysis of the second loop. The actual simplification isn't relevant.

Sorry, I don't know what you mean by "The actual simplification isn't relevant". Would you mind explaining a little more?

[nikic]

In D144861#4155833, @wsmoses wrote:

If it’s possible to not revert that would be preferable as @jdoefert @vchuravy I and others have many applications that would have significant slow down if reverted.

The change also caused significant slowdowns for multiple other people, which were never addressed (e.g. https://github.com/llvm/llvm-project/issues/54191). Combined with this issue, that's enough for a revert for me.

In D144861#4160432, @StephenFan wrote:

In D144861#4160179, @efriedma wrote:

From my analysis of the testcase, we called "getAddExpr(SCEV::FlagNUW)" while analyzing the first loop, and that broke the analysis of the second loop. The actual simplification isn't relevant.

Sorry, I don't know what you mean by "The actual simplification isn't relevant". Would you mind explaining a little more?

The getAddExpr() with NUW flag sets this flag globally, for all uses of this add. The icmp simplification itself doesn't make a difference, just the side effect that the (not globally correct) nuw flag is set.

If we don't want to revert the patch, the right fix would be to not set the NUW flag in the ControllingFiniteLoop case.

[StephenFan]

In D144861#4160432, @StephenFan wrote:

! In D144861#4160179, @efriedma wrote:
From my analysis of the testcase, we called "getAddExpr(SCEV::FlagNUW)" while analyzing the first loop, and that broke the analysis of the second loop. The actual simplification isn't relevant.

Sorry, I don't know what you mean by "The actual simplification isn't relevant". Would you mind explaining a little more?

The getAddExpr() with NUW flag sets this flag globally, for all uses of this add. The icmp simplification itself doesn't make a difference, just the side effect that the (not globally correct) nuw flag is set.

Thanks for your explanation!

[nikic]

I've posted https://reviews.llvm.org/D145510 as an alternative patch, which hopefully resolves all the issues with the current implementation.

[StephenFan]

In D144861#4175471, @nikic wrote:

I've posted https://reviews.llvm.org/D145510 as an alternative patch, which hopefully resolves all the issues with the current implementation.

Thanks!

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
   /// iff any changes were made. If the operands are provably equal or
   /// unequal, LHS and RHS are set to the same value and Pred is set to either
   /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
   /// controls the exit of a loop known to have a finite number of iterations.
   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
                             const SCEV *&RHS, unsigned Depth = 0,
-                            bool ControllingFiniteLoop = false);
+                            bool ControllingFiniteLoop = false,
+                            const Loop *L = nullptr);
 
   /// Return the "disposition" of the given SCEV with respect to the given
   /// loop.
   LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
 
   /// Return true if the value of the given SCEV is unchanging in the
   /// specified loop.
   bool isLoopInvariant(const SCEV *S, const Loop *L);

llvm/lib/Analysis/ScalarEvolution.cpp

if (isLoopInvariant(LHS, L) && !isLoopInvariant(RHS, L)) {
     // If there is a loop-invariant, force it into the RHS.
     std::swap(LHS, RHS);
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
 
   bool ControllingFiniteLoop =
       ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L);
   // Simplify the operands before analyzing them.
-  (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0,
-                             (EnableFiniteLoopControl ? ControllingFiniteLoop
-                                                     : false));
+  (void)SimplifyICmpOperands(
+      Pred, LHS, RHS, /*Depth=*/0,
+      (EnableFiniteLoopControl ? ControllingFiniteLoop : false), L);
 
   // If we have a comparison of a chrec against a constant, try to use value
   // ranges to answer this query.
   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
     if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
       if (AddRec->getLoop() == L) {
         // Form the constant range.
         ConstantRange CompRange =
static bool HasSameValue(const SCEV *A, const SCEV *B) {
 
   // Otherwise assume they may have a different value.
   return false;
 }
 
 bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
                                            const SCEV *&LHS, const SCEV *&RHS,
                                            unsigned Depth,
-                                           bool ControllingFiniteLoop) {
+                                           bool ControllingFiniteLoop,
+                                           const Loop *L) {
   bool Changed = false;
   // Simplifies ICMP to trivial true or false by turning it into '0 == 0' or
   // '0 != 0'.
   auto TrivialCase = [&](bool TriviallyTrue) {
     LHS = RHS = getConstant(ConstantInt::getFalse(getContext()));
     Pred = TriviallyTrue ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
     return true;
   };
bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
   // Check for obvious equality.
   if (HasSameValue(LHS, RHS)) {
     if (ICmpInst::isTrueWhenEqual(Pred))
       return TrivialCase(true);
     if (ICmpInst::isFalseWhenEqual(Pred))
       return TrivialCase(false);
   }
 
+  bool IsRHSOuterLoopInvariant = false;
+  if (L) {
+    const Loop *Parent = L->getOutermostLoop();
+    IsRHSOuterLoopInvariant = Parent != L ? isLoopInvariant(RHS, Parent) : true;
+  }
+
   // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by
   // adding or subtracting 1 from one of the operands. This can be done for
   // one of two reasons:
   // 1) The range of the RHS does not include the (signed/unsigned) boundaries
   // 2) The loop is finite, with this comparison controlling the exit. Since the
   // loop is finite, the bound cannot include the corresponding boundary
   // (otherwise it would loop forever).
   switch (Pred) {
case ICmpInst::ICMP_SGE:
     } else if (!getSignedRangeMax(LHS).isMaxSignedValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SGT;
       Changed = true;
     }
     break;
   case ICmpInst::ICMP_ULE:
-    if (ControllingFiniteLoop || !getUnsignedRangeMax(RHS).isMaxValue()) {
+    if ((ControllingFiniteLoop && IsRHSOuterLoopInvariant) ||
+        !getUnsignedRangeMax(RHS).isMaxValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
                        SCEV::FlagNUW);
       Pred = ICmpInst::ICMP_ULT;
       Changed = true;
     } else if (!getUnsignedRangeMin(LHS).isMinValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS);
       Pred = ICmpInst::ICMP_ULT;
       Changed = true;

llvm/test/Transforms/IndVarSimplify/pr60944.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='indvars' -S %s | FileCheck %s
 @b = dso_local global i16 0, align 4
 @c = dso_local local_unnamed_addr global ptr @b, align 8
 @d = dso_local local_unnamed_addr global i32 -1, align 4
 @a = dso_local local_unnamed_addr global i16 0, align 4
 
 ; Function Attrs: nofree norecurse nosync nounwind memory(readwrite, argmem: write, inaccessiblemem: none) uwtable
 define dso_local i32 @main() local_unnamed_addr #0 {

 ; CHECK-NEXT:    [[CONV_I:%.*]] = sext i16 [[TMP3]] to i32
 ; CHECK-NEXT:    [[CMP2_NOT_I:%.*]] = icmp ult i32 [[DIV11_I]], [[CONV_I]]
 ; CHECK-NEXT:    br i1 [[CMP2_NOT_I]], label [[WHILE_END_I_LOOPEXIT:%.*]], label [[WHILE_BODY4_I:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       while.end.i:
 ; CHECK-NEXT:    [[TMP4]] = phi i16 [ [[TMP1]], [[WHILE_BODY_I]] ], [ [[DOTLCSSA:%.*]], [[WHILE_END_I_LOOPEXIT]] ]
 ; CHECK-NEXT:    [[TMP5:%.*]] = load i16, ptr @a, align 4
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = sext i16 [[TMP5]] to i32
 ; CHECK-NEXT:    [[DIV_I]] = sdiv i32 [[CONV5_I]], [[DIV11_I]]
-; CHECK-NEXT:    br i1 false, label [[E_EXIT:%.*]], label [[WHILE_BODY_I]]
+; CHECK-NEXT:    [[CMP6_NOT_I:%.*]] = icmp eq i32 [[DIV11_I]], -1
+; CHECK-NEXT:    br i1 [[CMP6_NOT_I]], label [[E_EXIT:%.*]], label [[WHILE_BODY_I]]
 ; CHECK:       while.body4.i.preheader:
 ; CHECK-NEXT:    br label [[WHILE_BODY4_I]]
 ; CHECK:       while.end.i.loopexit:
 ; CHECK-NEXT:    [[DOTLCSSA]] = phi i16 [ [[TMP3]], [[WHILE_BODY4_I]] ]
 ; CHECK-NEXT:    br label [[WHILE_END_I]]
 ; CHECK:       e.exit:
 ; CHECK-NEXT:    [[DIV_I_LCSSA:%.*]] = phi i32 [ [[DIV_I]], [[WHILE_END_I]] ]
 ; CHECK-NEXT:    store i32 [[DIV_I_LCSSA]], ptr @d, align 4