[SCEV] Support sub in and negative constants willNotOverflow

[mkazantsev]

Summary

This lifts two TODOs from this function, allowing us to prove
no-overflow whether it happens through max int (up) or through
min int (down) for both and and sub.

[mkazantsev]

Internal testing found a bug, investigating.

[mkazantsev]

Ah ok, it is only legal for signed.

[mkazantsev]

Bug fixed, logic expanded.

[dmakogon]

LGTM

[dmakogon]

llvm/lib/Analysis/ScalarEvolution.cpp

2369

You don't need this else after return

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

2369

Indeed.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

2369

I just want to keep it that way because it is so perfectly aligned one under one.

llvm/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
   const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
   const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
   const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
   if (A == B)
     return true;
   // Can we use context to prove the fact we need?
   if (!CtxI)
     return false;
-  // We can prove that add(x, constant) doesn't wrap if isKnownPredicateAt can
-  // guarantee that x <= max_int - constant at the given context.
-  // TODO: Support other operations.
-  if (BinOp != Instruction::Add)
-    return false;
   auto *RHSC = dyn_cast<SCEVConstant>(RHS);
   // TODO: Lift this limitation.
   if (!RHSC)
     return false;
   APInt C = RHSC->getAPInt();
+  // We can prove that add(x, constant) doesn't wrap if isKnownPredicateAt can
+  // guarantee that x <= max_int - constant at the given context.
+  // TODO: Support mul.
+  if (BinOp == Instruction::Sub)
+    C = -C;
+  else if (BinOp != Instruction::Add)
+    return false;
   // TODO: Also lift this limitation.
   if (Signed && C.isNegative())
     return false;
   unsigned NumBits = C.getBitWidth();
   APInt Max =
       Signed ? APInt::getSignedMaxValue(NumBits) : APInt::getMaxValue(NumBits);
   APInt Limit = Max - C;
   ICmpInst::Predicate Pred = Signed ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
   return isKnownPredicateAt(Pred, LHS, getConstant(Limit), CtxI);
 }
 
 std::optional<SCEV::NoWrapFlags>
 ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(
     const OverflowingBinaryOperator *OBO) {
   // It cannot be done any better.
   if (OBO->hasNoUnsignedWrap() && OBO->hasNoSignedWrap())
     return std::nullopt;
 
   SCEV::NoWrapFlags Flags = SCEV::NoWrapFlags::FlagAnyWrap;
 
   if (OBO->hasNoUnsignedWrap())
     Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
   if (OBO->hasNoSignedWrap())

llvm/test/Transforms/IndVarSimplify/infer-poison-flags.ll

 }
 
 define void @sub_cr_nsw_nuw() {
 ; CHECK-LABEL: @sub_cr_nsw_nuw(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[I_NEXT]] = sub nsw i32 [[I]], -1
+; CHECK-NEXT:    [[I_NEXT]] = sub nuw nsw i32 [[I]], -1
 ; CHECK-NEXT:    store i32 [[I]], ptr @A, align 4
 ; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[I_NEXT]], 1000
 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[LOOPEXIT:%.*]]
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop