[SCEV][IndVarSimplify] Add nsw/nuw falgs to binary ops before visiting IVUsers

[aleksandr.popov]

Summary

Annotate binary operators primarily in the
'SimplifyIndvar::simplifyUsers' to give more context for analyzes and
transformations with users, which are visited before binary operators.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

11118 ↗

(On Diff #495144)

Why not isKnownPredicateAt(SignFlippedPred, LHS, RHS, CtxI)? It may also take assumes in current block into consideration.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

756

How is that related to what the patch claims to do? Should it be a separate patch with separate tests?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

11115 ↗

(On Diff #495144)

Sure this is wrong.

start = SINT_MAX - 1
step = 2
RHS = SINT_MAX

On first iteration, both checks pass.

SINT_MAX - 1 <s SINT_MAX // true
SINT_MAX - 1 <u SINT_MAX // true

On the 2nd iteration unsigned check will fail.
SINT_MAX + 1 <s SINT_MAX true
SINT_MAX + 1 <u SINT_MAX false

Note that what you did is just duplicated the checks above, but dropped the nuw check that was there for reason.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

11115 ↗

(On Diff #495144)

Sorry, nsw check.

[aleksandr.popov]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

756

Now there are 2 places where we are doing BO strengthen: before and inside the loop, so I though it would be better to move this code to a separate method to reduce repeating

[mkazantsev]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

936

Factoring out this check into strengthenBinaryOp can be split off as a NFC patch. Then, make a functional patch that introduces its new use.

[aleksandr.popov]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

936

Thanks, will do that

[aleksandr.popov]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

936

Split: https://reviews.llvm.org/D143562

[mkazantsev]

Update the patch after split-off & update commit message according to what it's doing now?

[mkazantsev]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

894

This solves problem for users of initial IV, but seems that it still exists for users of users. Can we do it for all values?

[aleksandr.popov]

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

894

I'll add test for the case with users of users, thanks

[nikic]

IIRC strengthenBinaryOp() is expensive, it would be great not to call it twice. (It works on double-sized SCEV expressions, so usually 128 bits, and thus takes all the slow paths).

It would be helpful to provide some more context on what the actual problem here is, i.e. in which order are we visiting instructions / performing folds in the example, and what would the right order be. I suspect it's not actually necessary to call it twice, but it's hard to say without understanding the root problem.

[aleksandr.popov]

I'll try to explain the root probrem in the 'unknown.start' test case.

• Currently we process IV's users in this order:

%signed.cmp = icmp slt i32 %iv, %len
%unsigned.cmp = icmp ult i32 %iv, %len
%iv.next = add i32 %iv, 1

When we try to make %unsigned.cmp invariant, IV's SCEV doesn't have nsw/nuw flags:

{%start,+,1}<%loop>

Therefore AddRec's MonotonicType, computed in the ScalarEvolution::getLoopInvariantPredicate, is nullopt and we can't make %unsigned.cmp invariant.

• But if we visit bin op firstly and annotate it with nsw/nuw flags, they will be propagated to IV's SCEV:

{%start,+,1}<nuw><nsw><%loop>

And it allows us to make %unsigned.cmp invariant, since MonotonicType has value

[nikic]

Thanks for the explanation.

In D143409#4125708, @aleksandr.popov wrote:

But if we visit bin op firstly and annotate it with nsw/nuw flags, they will be propagated to IV's SCEV:

I suspect that what actually happens is that as part of the getZeroExtendExpr() call, we infer a nowrap flag on the addrec in https://github.com/llvm/llvm-project/blob/7a49d50f22ad577d91cda7904c8a162c2cecd4a8/llvm/lib/Analysis/ScalarEvolution.cpp#L1688, or one of the later bits in the same method. If this is the case, it would be nice to know which one is responsible here, and in particular whether it is the constant range one.

This is a long-standing issue, that nowrap flags are inferred when creating zext/sext expressions, so that creating those expressions can improve "unrelated" analysis results. I tried to address the constant range nowrap inference in D90338, but haven't pursued this in a while.

[fhahn]

In D143409#4125832, @nikic wrote:

Thanks for the explanation.

In D143409#4125708, @aleksandr.popov wrote:

But if we visit bin op firstly and annotate it with nsw/nuw flags, they will be propagated to IV's SCEV:

I suspect that what actually happens is that as part of the getZeroExtendExpr() call, we infer a nowrap flag on the addrec in https://github.com/llvm/llvm-project/blob/7a49d50f22ad577d91cda7904c8a162c2cecd4a8/llvm/lib/Analysis/ScalarEvolution.cpp#L1688, or one of the later bits in the same method. If this is the case, it would be nice to know which one is responsible here, and in particular whether it is the constant range one.

This is a long-standing issue, that nowrap flags are inferred when creating zext/sext expressions, so that creating those expressions can improve "unrelated" analysis results. I tried to address the constant range nowrap inference in D90338, but haven't pursued this in a while.

That reminded me of a patch I had lying around for a while to strengthen no wrap flags when construction AddRecs: D144050

[aleksandr.popov]

I suspect that what actually happens is that as part of the getZeroExtendExpr() call, we infer a nowrap flag on the addrec in https://github.com/llvm/llvm-project/blob/7a49d50f22ad577d91cda7904c8a162c2cecd4a8/llvm/lib/Analysis/ScalarEvolution.cpp#L1688, or one of the later bits in the same method. If this is the case, it would be nice to know which one is responsible here, and in particular whether it is the constant range one.

We infer a nowrap flag on the addrec from the proveNoUnsignedWrapViaInduction(AR) call: https://github.com/llvm/llvm-project/blob/7a49d50f22ad577d91cda7904c8a162c2cecd4a8/llvm/lib/Analysis/ScalarEvolution.cpp#L1776

This seems to be the reason why patch https://reviews.llvm.org/D144050 from Florian didn't help in the case

[mkazantsev]

I think this sould go, unless we have a better idea how to fix it. After all, it's just one more go of logic that is done in loop anyways. I'll give it couple of days to chill if someone has strong objections.

[nikic]

I still think this is the wrong way to go about it. If it's infeasible to ensure the flags are present in the first place, we should probably expose the methods to explicitly infer the flags on the addrec, without having to go through zext/sext to make this happen as a side effect.

[mkazantsev]

Yeah, the question is, how much does it take and is it possible to do without running into a cyclic dependency...

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp

public:
     bool makeIVComparisonInvariant(ICmpInst *ICmp, Instruction *IVOperand);
     void eliminateIVComparison(ICmpInst *ICmp, Instruction *IVOperand);
     void simplifyIVRemainder(BinaryOperator *Rem, Instruction *IVOperand,
                              bool IsSigned);
     void replaceRemWithNumerator(BinaryOperator *Rem);
     void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);
     void replaceSRemWithURem(BinaryOperator *Rem);
     bool eliminateSDiv(BinaryOperator *SDiv);
+    bool strengthenBinaryOp(BinaryOperator *BO, Instruction *IVOperand);
     bool strengthenOverflowingOperation(BinaryOperator *OBO,
                                         Instruction *IVOperand);
     bool strengthenRightShift(BinaryOperator *BO, Instruction *IVOperand);
   };
 }
 
 /// Find a point in code which dominates all given instructions. We can safely
 /// assume that, whatever fact we can prove at the found point, this fact is
bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,
   SE->forgetValue(UseInst);
   UseInst->replaceAllUsesWith(IVOperand);
   ++NumElimIdentity;
   Changed = true;
   DeadInsts.emplace_back(UseInst);
   return true;
 }
 
+bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,
+                                        Instruction *IVOperand) {
+  return (isa<OverflowingBinaryOperator>(BO) &&
+          strengthenOverflowingOperation(BO, IVOperand)) ||
+         (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));
+}
+
 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
 /// unsigned-overflow.  Returns true if anything changed, false otherwise.
 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
                                                     Instruction *IVOperand) {
   auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
       cast<OverflowingBinaryOperator>(BO));
 
   if (!Flags)
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
   // Use-def pairs if IV users waiting to be processed for CurrIV.
   SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;
 
   // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
   // called multiple times for the same LoopPhi. This is the proper thing to
   // do for loop header phis that use each other.
   pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
 
+  // Annotate binary operators primarily to give more context for analyzes and
+  // transformations with users, which are visited before binary operators. E.g.
+  // for IV comparison invariant making
+  for (auto [UseInst, IVOperand] : SimpleIVUsers)
+    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst))
+      if (strengthenBinaryOp(BO, IVOperand))
+        pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
+
   while (!SimpleIVUsers.empty()) {
     std::pair<Instruction*, Instruction*> UseOper =
       SimpleIVUsers.pop_back_val();
     Instruction *UseInst = UseOper.first;
 
     // If a user of the IndVar is trivially dead, we prefer just to mark it dead
     // rather than try to do some complex analysis or transformation (such as
     // widening) basing on it.
if (!IVOperand)
       continue;
 
     if (eliminateIVUser(UseInst, IVOperand)) {
       pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
       continue;
     }
 
     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {
-      if ((isa<OverflowingBinaryOperator>(BO) &&
-           strengthenOverflowingOperation(BO, IVOperand)) ||
-          (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
+      if (strengthenBinaryOp(BO, IVOperand)) {
         // re-queue uses of the now modified binary operator and fall
         // through to the checks that remain.
         pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
       }
     }
 
     // Try to use integer induction for FPToSI of float induction directly.
     if (replaceFloatIVWithIntegerIV(UseInst)) {

llvm/test/Transforms/IndVarSimplify/cycled_phis.ll

 failed.unsigned:
   call void @fail(i32 2)
   unreachable
 
 done:
   ret i32 %iv
 }
 
-; TODO: The 2nd check can be made invariant.
+; The 2nd check can be made invariant.
 ; slt and ult checks are equivalent. When IV is negative, slt check will pass and ult will
 ; fail. Because IV is incrementing, this will fail on 1st iteration or never.
 define i32 @unknown.start(i32 %start, ptr %len.ptr) {
 ; CHECK-LABEL: @unknown.start(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[PREHEADER:%.*]]
 ; CHECK:       preheader:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
-; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
+; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[START]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:
 ; CHECK-NEXT:    call void @fail(i32 1)
 ; CHECK-NEXT:    unreachable
failed.unsigned:
   call void @fail(i32 2)
   unreachable
 
 done:
   ret i32 %iv
 }
 
 
-; TODO: We should be able to prove that:
+; We should be able to prove that:
 ; - %sibling.iv.next is non-negative;
 ; - therefore, %iv is non-negative;
 ; - therefore, unsigned check can be removed.
 define i32 @start.from.sibling.iv(ptr %len.ptr, ptr %sibling.len.ptr) {
 ; CHECK-LABEL: @start.from.sibling.iv(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]]
 ; CHECK-NEXT:    br label [[SIBLING_LOOP:%.*]]
 ; CHECK:       sibling.loop:
 ; CHECK-NEXT:    [[SIBLING_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIBLING_RC:%.*]] = icmp ult i32 [[SIBLING_IV]], [[SIBLING_LEN]]
 ; CHECK-NEXT:    br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]]
 ; CHECK:       sibling.backedge:
 ; CHECK-NEXT:    [[SIBLING_IV_NEXT]] = add nuw nsw i32 [[SIBLING_IV]], 1
 ; CHECK-NEXT:    [[SIBLING_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[PREHEADER:%.*]]
 ; CHECK:       preheader:
 ; CHECK-NEXT:    [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i32 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_LCSSA]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
+; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
-; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]]
-; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:
 ; CHECK-NEXT:    call void @fail(i32 1)
 ; CHECK-NEXT:    unreachable
 ; CHECK:       failed.unsigned:

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_BACKEDGE]]
 ; CHECK:       outer.loop.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[OUTER_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]]
 ; CHECK:       failed.signed:

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]]
 ; CHECK:       signed.passed:
 ; CHECK-NEXT:    [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]]
 ; CHECK-NEXT:    br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_SELECTION:%.*]]
 ; CHECK:       outer.loop.selection:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    [[SWITCH_COND:%.*]] = call i32 @switch.cond()
 ; CHECK-NEXT:    switch i32 [[SWITCH_COND]], label [[TAKE_SAME:%.*]] [
 ; CHECK-NEXT:    i32 1, label [[TAKE_INCREMENT:%.*]]