[SCEV] Make isImpliedCond smarter.

[sanjoy]

Summary

This change teaches isImpliedCond to infer things like "X sgt 0" => "X -
1 sgt -1".

The logic to do the heavy lifting is present in the ConstantRange
class, this change simply gets ScalarEvolution to exploit that when
reasonable.

Depends on D8345

[atrick]

Hi Sanjoy,

This looks ok, but is there any way to canonicalize (add-by-constant <pred> constant) before checking isImpliedCond? That way it would be symmetric and you wouldn't need separate logic to handle it.

[atrick]

Yep. I don't have a better suggestion then.
LGTM.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

private:
     /// isImpliedCondOperandsHelper - Test whether the condition described by
     /// Pred, LHS, and RHS is true whenever the condition described by Pred,
     /// FoundLHS, and FoundRHS is true.
     bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
                                      const SCEV *LHS, const SCEV *RHS,
                                      const SCEV *FoundLHS,
                                      const SCEV *FoundRHS);
 
+    /// isImpliedCondOperandsViaRanges - Test whether the condition described by
+    /// Pred, LHS, and RHS is true whenever the condition described by Pred,
+    /// FoundLHS, and FoundRHS is true.  Utility function used by
+    /// isImpliedCondOperands.
+    bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
+                                        const SCEV *LHS, const SCEV *RHS,
+                                        const SCEV *FoundLHS,
+                                        const SCEV *FoundRHS);
+
     /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
     /// in the header of its containing loop, we know the loop executes a
     /// constant number of times, and the PHI node is just a recurrence
     /// involving constants, fold it.
     Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs,
                                                 const Loop *L);
 
     /// isKnownPredicateWithRanges - Test if the given expression is known to

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

 
 /// isImpliedCondOperands - Test whether the condition described by Pred,
 /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
 /// and FoundRHS is true.
 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS,
                                             const SCEV *FoundLHS,
                                             const SCEV *FoundRHS) {
+  if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS))
+    return true;
+
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      FoundLHS, FoundRHS) ||
          // ~x < ~y --> x > y
          isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      getNotSCEV(FoundRHS),
                                      getNotSCEV(FoundLHS));
 }
 
if (IsKnownPredicateFull(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
         IsKnownPredicateFull(ICmpInst::ICMP_ULE, RHS, FoundRHS))
       return true;
     break;
   }
 
   return false;
 }
 
+/// isImpliedCondOperandsViaRanges - helper function for isImpliedCondOperands.
+/// Tries to get cases like "X `sgt` 0 => X - 1 `sgt` -1".
+bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
+                                                     const SCEV *LHS,
+                                                     const SCEV *RHS,
+                                                     const SCEV *FoundLHS,
+                                                     const SCEV *FoundRHS) {
+  if (!isa<SCEVConstant>(RHS) || !isa<SCEVConstant>(FoundRHS))
+    // The restriction on `FoundRHS` be lifted easily -- it exists only to
+    // reduce the compile time impact of this optimization.
+    return false;
+
+  const SCEVAddExpr *AddLHS = dyn_cast<SCEVAddExpr>(LHS);
+  if (!AddLHS || AddLHS->getOperand(1) != FoundLHS ||
+      !isa<SCEVConstant>(AddLHS->getOperand(0)))
+    return false;
+
+  APInt ConstFoundRHS = cast<SCEVConstant>(FoundRHS)->getValue()->getValue();
+
+  // `FoundLHSRange` is the range we know `FoundLHS` to be in by virtue of the
+  // antecedent "`FoundLHS` `Pred` `FoundRHS`".
+  ConstantRange FoundLHSRange =
+      ConstantRange::makeAllowedICmpRegion(Pred, ConstFoundRHS);
+
+  // Since `LHS` is `FoundLHS` + `AddLHS->getOperand(0)`, we can compute a range
+  // for `LHS`:
+  APInt Addend =
+      cast<SCEVConstant>(AddLHS->getOperand(0))->getValue()->getValue();
+  ConstantRange LHSRange = FoundLHSRange.add(ConstantRange(Addend));
+
+  // We can also compute the range of values for `LHS` that satisfy the
+  // consequent, "`LHS` `Pred` `RHS`":
+  APInt ConstRHS = cast<SCEVConstant>(RHS)->getValue()->getValue();
+  ConstantRange SatisfyingLHSRange =
+      ConstantRange::makeSatisfyingICmpRegion(Pred, ConstRHS);
+
+  // The antecedent implies the consequent if every value of `LHS` that
+  // satisfies the antecedent also satisfies the consequent.
+  return SatisfyingLHSRange.contains(LHSRange);
+}
+
 // Verify if an linear IV with positive stride can overflow when in a
 // less-than comparison, knowing the invariant term of the comparison, the
 // stride and the knowledge of NSW/NUW flags on the recurrence.
 bool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
                                          bool IsSigned, bool NoWrap) {
   if (NoWrap) return false;
 
   unsigned BitWidth = getTypeSizeInBits(RHS->getType());

llvm/trunk/test/Analysis/ScalarEvolution/infer-via-ranges.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+define void @infer_via_ranges(i32 *%arr, i32 %n) {
+; CHECK-LABEL: @infer_via_ranges
+ entry:
+  %first.itr.check = icmp sgt i32 %n, 0
+  %start = sub i32 %n, 1
+  br i1 %first.itr.check, label %loop, label %exit
+
+ loop:
+; CHECK-LABEL: loop:
+  %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ]
+  %idx.dec = sub i32 %idx, 1
+  %abc = icmp sge i32 %idx, 0
+; CHECK: br i1 true, label %in.bounds, label %out.of.bounds
+  br i1 %abc, label %in.bounds, label %out.of.bounds
+
+ in.bounds:
+; CHECK-LABEL: in.bounds:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %next = icmp sgt i32 %idx.dec, -1
+  br i1 %next, label %loop, label %exit
+
+ out.of.bounds:
+  ret void
+
+ exit:
+  ret void
+}