[SCEV] Teach SCEV some axioms about non-wrapping arithmetic

[sanjoy]

Summary

• A s< (A + C)<nsw> if C > 0
• A s<= (A + C)<nsw> if C >= 0
• (A + C)<nsw> s< A if C < 0
• (A + C)<nsw> s<= A if C <= 0

Right now C needs to be a constant, but we can later generalize it to
be a non-constant if needed.

[reames]

include/llvm/Analysis/ScalarEvolution.h

579

The naming of this seems really odd. Possibly: ViaIntegerFacts?

"certian kinds of overflow" is confusing in the comment.

lib/Analysis/ScalarEvolution.cpp

7177

A comment explaining what this matches would help.

7199

Notation wise: X s<= (X +<nsw> C) if C >= 0 would be far more clear.

[sanjoy]

include/llvm/Analysis/ScalarEvolution.h

579

ViaIntegerFacts seems just as vague as (if not more) ViaNoOverflow to me. :) There are many integer facts that we can use without proving no overflow (e.g. transitivity of <), but this function focuses on using integer facts that are not valid if the the operation in LHS / RHS overflow. I can work this into the comment if you think that'll help. I can also drop the "certain kinds" bit form the comment and just say "ruling out integer overflow".

lib/Analysis/ScalarEvolution.cpp

7177

Will do.

7199

(A + B)<nsw> is the standard notation used when printing SCEV expressions, so I'd rather keep it that way for consistency.

[sanjoy]

• address review

[reames]

lib/Analysis/ScalarEvolution.cpp

7203

Er, this doesn't seem to match either the name or signature of the lambda above?

[sanjoy]

• I accidentally fat fingered the diff upload last time, uploading the correct diff

[reames]

LGTM w/minor comment.

test/Transforms/IndVarSimplify/eliminate-comparison.ll

480

A short comment about *what* this is testing for would make it far easier to understand.

[rtrieu]

r251050 may be causing a miscompile. See:
https://llvm.org/bugs/show_bug.cgi?id=25421

include/llvm/Analysis/ScalarEvolution.h

Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
                                                 const Loop *L);
 
     /// Test if the given expression is known to satisfy the condition described
     /// by Pred and the known constant ranges of LHS and RHS.
     ///
     bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS);
 
+    /// Try to prove the condition described by "LHS Pred RHS" by ruling out
+    /// integer overflow.
+    ///
+    /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
+    /// positive.
+    bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred,
+                                       const SCEV *LHS, const SCEV *RHS);
+
     /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
     /// prove them individually.
     bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
                                       const SCEV *RHS);
 
     /// Try to match the Expr as "(L + R)<Flags>".
     bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
                         SCEV::NoWrapFlags &Flags);

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
   case ICmpInst::ICMP_EQ:
     // The check at the top of the function catches the case where
     // the values are known to be equal.
     break;
   }
   return false;
 }
 
+bool ScalarEvolution::isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred,
+                                                    const SCEV *LHS,
+                                                    const SCEV *RHS) {
+
+  // Match Result to (X + Y)<ExpectedFlags> where Y is a constant integer.
+  // Return Y via OutY.
+  auto MatchBinaryAddToConst =
+      [this](const SCEV *Result, const SCEV *X, APInt &OutY,
+             SCEV::NoWrapFlags ExpectedFlags) {
+    const SCEV *NonConstOp, *ConstOp;
+    SCEV::NoWrapFlags FlagsPresent;
+
+    if (!splitBinaryAdd(Result, ConstOp, NonConstOp, FlagsPresent) ||
+        !isa<SCEVConstant>(ConstOp) || NonConstOp != X)
+      return false;
+
+    OutY = cast<SCEVConstant>(ConstOp)->getValue()->getValue();
+    return (FlagsPresent & ExpectedFlags) != 0;
+  };
+
+  APInt C;
+
+  switch (Pred) {
+  default:
+    break;
+
+  case ICmpInst::ICMP_SGE:
+    std::swap(LHS, RHS);
+  case ICmpInst::ICMP_SLE:
+    // X s<= (X + C)<nsw> if C >= 0
+    if (MatchBinaryAdd(RHS, LHS, C, SCEV::FlagNSW) && C.isNonNegative())
+      return true;
+
+    // (X + C)<nsw> s<= X if C <= 0
+    if (MatchBinaryAdd(LHS, RHS, C, SCEV::FlagNSW) && !C.isStrictlyPositive())
+      return true;
+
+  case ICmpInst::ICMP_SGT:
+    std::swap(LHS, RHS);
+  case ICmpInst::ICMP_SLT:
+    // X s< (X + C)<nsw> if C > 0
+    if (MatchBinaryAdd(RHS, LHS, C, SCEV::FlagNSW) && C.isStrictlyPositive())
+      return true;
+
+    // (X + C)<nsw> s< X if C < 0
+    if (MatchBinaryAdd(LHS, RHS, C, SCEV::FlagNSW) && C.isNegative())
+      return true;
+  }
+
+  return false;
+}
+
 bool ScalarEvolution::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred,
                                                    const SCEV *LHS,
                                                    const SCEV *RHS) {
   if (Pred != ICmpInst::ICMP_ULT || ProvingSplitPredicate)
     return false;
 
   // Allowing arbitrary number of activations of isKnownPredicateViaSplitting on
   // the stack can result in exponential time complexity.

 bool
 ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS,
                                              const SCEV *FoundLHS,
                                              const SCEV *FoundRHS) {
   auto IsKnownPredicateFull =
       [this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
     return isKnownPredicateWithRanges(Pred, LHS, RHS) ||
            IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
-        IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS);
+           IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS) ||
+           isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
   };
 
   switch (Pred) {
   default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
   case ICmpInst::ICMP_EQ:
   case ICmpInst::ICMP_NE:
     if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS))
       return true;

test/Transforms/IndVarSimplify/eliminate-comparison.ll

be:
   call void @side_effect()
   %be.cond = icmp slt i32 %iv.inc, %length
   br i1 %be.cond, label %loop, label %leave
 
  leave:
   ret void
 }
 
+define void @func_22(i32* %length.ptr) {
+; CHECK-LABEL: @func_22(
+ entry:
+  %length = load i32, i32* %length.ptr, !range !0
+  %lim = sub i32 %length, 1
+  %entry.cond = icmp sgt i32 %length, 1
+  br i1 %entry.cond, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
+  %iv.inc = add i32 %iv, 1
+  %range.check = icmp slt i32 %iv, %length
+  br i1 %range.check, label %be, label %leave
+; CHECK:   br i1 true, label %be, label %leave.loopexit
+; CHECK: be:
+
+ be:
+  call void @side_effect()
+  %be.cond = icmp slt i32 %iv.inc, %lim
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret void
+}
+
+define void @func_23(i32* %length.ptr) {
+; CHECK-LABEL: @func_23(
+ entry:
+  %length = load i32, i32* %length.ptr, !range !0
+  %lim = sub i32 %length, 1
+  %entry.cond = icmp sgt i32 %length, 1
+  br i1 %entry.cond, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
+  %iv.inc = add i32 %iv, 1
+  %range.check = icmp sle i32 %iv, %length
+  br i1 %range.check, label %be, label %leave
+; CHECK:   br i1 true, label %be, label %leave.loopexit
+; CHECK: be:
+
+ be:
+  call void @side_effect()
+  %be.cond = icmp sle i32 %iv.inc, %lim
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret void
+}
+
+
 !0 = !{i32 0, i32 2147483647}