[SCEV] Try to prove predicates by splitting them.

[sanjoy]

Summary

This change teaches SCEV that to prove A u< B it is sufficient to
prove each of these facts individually:

• B >= 0
• A s< B
• A >= 0

In practice, SCEV sometimes finds it easier to prove these facts
individually than to prove A u< B as one atomic step.

[sanjoy]

ping!

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

6987

Why do you use isKnownNonNegative(RHS) but not isKnownNonNegative(LHS)?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

6987

isKnownNonNegative is less powerful than isKnownPredicate. isKnownPredicate does a control dependence analysis while isKnownNonNegative just looks at getSignedRange which does not take most control dependence into account (it does take some control dependence into account indirectly, by leveraging the no-wrap flags on SCEV instructions).

The cases we're looking to optimize are of the form %iv ult %length. Here %length is a load instruction with !range metadata that lets us directly prove that %length is positive without control dependence, and %iv is an induction variable which takes some control dependence analysis to prove as being always positive.

I cannot try this out before tomorrow, but I think using isKnownPredicate to prove RHS is positive as well should work (except we'll be burning more compile time). Another possibility is to keep the code as is, and add what I said here as a comment.

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

6987

I'd only recommend doing the more expensive thing if you can construct a test case where it helps, and that test case is in canonical form (i.e. IndVarSimplify would not change it to make the simpler version work). Otherwise, just adding what you have here as a comment should be fine.

[sanjoy]

• rebase + add comment suggested by Hal

[sanjoy]

ping!

[hfinkel]

LGTM.

include/llvm/Analysis/ScalarEvolution.h

private:
 
     /// Mark predicate values currently being processed by isImpliedCond.
     DenseSet<Value*> PendingLoopPredicates;
 
     /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
     /// conditions dominating the backedge of a loop.
     bool WalkingBEDominatingConds;
 
+    /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
+    /// predicate by splitting it into a set of independent predicates.
+    bool ProvingSplitPredicate;
+
     /// Information about the number of loop iterations for which a loop exit's
     /// branch condition evaluates to the not-taken path.  This is a temporary
     /// pair of exact and max expressions that are eventually summarized in
     /// ExitNotTakenInfo and BackedgeTakenInfo.
     struct ExitLimit {
       const SCEV *Exact;
       const SCEV *Max;
 
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 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);
+
     /// Drop memoized information computed for S.
     void forgetMemoizedResults(const SCEV *S);
 
     /// Return an existing SCEV for V if there is one, otherwise return nullptr.
     const SCEV *getExistingSCEV(Value *V);
 
     /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
     /// pointer.

lib/Analysis/ScalarEvolution.cpp

if (isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) &&
         isLoopBackedgeGuardedByCond(L, Pred, LHS, RAR->getPostIncExpr(*this))) {
       if (!LAR) return true;
       RightGuarded = true;
     }
   }
   if (LeftGuarded && RightGuarded)
     return true;
 
+  if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
+    return true;
+
   // Otherwise see what can be done with known constant ranges.
   return isKnownPredicateWithRanges(Pred, LHS, RHS);
 }
 
 bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS,
                                            ICmpInst::Predicate Pred,
                                            bool &Increasing) {
   bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing);
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::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred,
+                                                   const SCEV *LHS,
+                                                   const SCEV *RHS) {
+  if (ProvingSplitPredicate)
+    return false;
+
+  // Allowing arbitrary number of activations of isKnownPredicateViaSplitting on
+  // the stack can result in exponential time complexity.
+  SaveAndRestore<bool> Restore(ProvingSplitPredicate, true);
+
+  // If L >= 0 then I `ult` L <=> I >= 0 && I `slt` L
+  //
+  // To prove L >= 0 we use isKnownNonNegative whereas to prove I >= 0 we use
+  // isKnownPredicate.  isKnownPredicate is more powerful, but also more
+  // expensive; and using isKnownNonNegative(RHS) is sufficient for most of the
+  // interesting cases seen in practice.  We can consider "upgrading" L >= 0 to
+  // use isKnownPredicate later if needed.
+  if (Pred == ICmpInst::ICMP_ULT && isKnownNonNegative(RHS) &&
+      isKnownPredicate(CmpInst::ICMP_SGE, LHS,
+                       getConstant(LHS->getType(), 0)) &&
+      isKnownPredicate(CmpInst::ICMP_SLT, LHS, RHS))
+    return true;
+
+  return false;
+}
+
 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
 /// protected by a conditional between LHS and RHS.  This is used to
 /// to eliminate casts.
 bool
 ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
                                              ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard

 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
 
 ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
                                  AssumptionCache &AC, DominatorTree &DT,
                                  LoopInfo &LI)
     : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI),
       CouldNotCompute(new SCEVCouldNotCompute()),
-      WalkingBEDominatingConds(false), ValuesAtScopes(64), LoopDispositions(64),
-      BlockDispositions(64), FirstUnknown(nullptr) {}
+      WalkingBEDominatingConds(false), ProvingSplitPredicate(false),
+      ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64),
+      FirstUnknown(nullptr) {}
 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
     : F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI),
       CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
-      WalkingBEDominatingConds(false),
+      WalkingBEDominatingConds(false), ProvingSplitPredicate(false),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),
       ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
       LoopDispositions(std::move(Arg.LoopDispositions)),
       BlockDispositions(std::move(Arg.BlockDispositions)),
       UnsignedRanges(std::move(Arg.UnsignedRanges)),
       SignedRanges(std::move(Arg.SignedRanges)),
ScalarEvolution::~ScalarEvolution() {
   for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
          BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end();
        I != E; ++I) {
     I->second.clear();
   }
 
   assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
   assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");
+  assert(!ProvingSplitPredicate && "ProvingSplitPredicate garbage!");
 }
 
 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
   return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
 }
 
 static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
                           const Loop *L) {

test/Transforms/IndVarSimplify/eliminate-comparison.ll

 
 bb2:
   ret i1 false
 
 bb3:
   ret i1 true
 }
 
+define void @func_19(i32* %length.ptr) {
+; CHECK-LABEL: @func_19(
+ entry:
+  %length = load i32, i32* %length.ptr, !range !0
+  %length.is.nonzero = icmp ne i32 %length, 0
+  br i1 %length.is.nonzero, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
+  %iv.inc = add i32 %iv, 1
+  %range.check = icmp ult 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, %length
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret void
+}
+
+define void @func_20(i32* %length.ptr) {
+; Like @func_19, but %length is no longer provably positive, so
+; %range.check cannot be proved to be always true.
+
+; CHECK-LABEL: @func_20(
+ entry:
+  %length = load i32, i32* %length.ptr
+  %length.is.nonzero = icmp ne i32 %length, 0
+  br i1 %length.is.nonzero, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
+  %iv.inc = add i32 %iv, 1
+  %range.check = icmp ult i32 %iv, %length
+  br i1 %range.check, label %be, label %leave
+; CHECK:   br i1 %range.check, label %be, label %leave.loopexit
+; CHECK: be:
+
+ 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_21(i32* %length.ptr, i32 %init) {
+; Like @func_19, but it is no longer possible to prove %iv's start
+; value is positive without doing some control flow analysis.
+
+; CHECK-LABEL: @func_21(
+ entry:
+  %length = load i32, i32* %length.ptr, !range !0
+  %length.is.nonzero = icmp ne i32 %length, 0
+  %init.is.positive = icmp sgt i32 %init, 0
+  %entry.cond = and i1 %length.is.nonzero, %init.is.positive
+  br i1 %length.is.nonzero, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
+  %iv.inc = add i32 %iv, 1
+  %range.check = icmp ult 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, %length
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret void
+}
+
 !0 = !{i32 0, i32 2147483647}