[ScalarEvolution] Extend SCEV implication analysis with division

[mkazantsev]

Summary

This patch introduces the following rules related to division to SCEV:

1. FoundLHS > FoundRHS > 0 ---> FoundLHS / 2 > 0 >= RHS.
2. FoundLHS >= FoundRHS > 0 ---> FoundLHS / 2 >= 0 >= RHS.
3. FoundLHS >= FoundRHS, 0 < Denum <= FoundRHS ---> LHS = FoundLHS / Denum >= 1 >= RHS.

These rules related to signed division and are not currently covered by existing analysis.

[mkazantsev]

Need to add tests.

[mkazantsev]

Needs massive rework.

include/llvm/Analysis/ScalarEvolution.h

private:
   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
   /// true.
   bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
                              const SCEV *RHS, const SCEV *FoundLHS,
                              const SCEV *FoundRHS);
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
+  /// true. Here LHS is an operation that includes FoundLHS as one of its
+  /// arguments.
+  bool isImpliedViaOperations(ICmpInst::Predicate Pred,
+                              const SCEV *LHS, const SCEV *RHS,
+                              const SCEV *FoundLHS,
+                              const SCEV *FoundRHS);
+
+  /// 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);
 
   /// 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.  Tries to get

lib/Analysis/ScalarEvolution.cpp

return
       // A <= max(A, ...)
       IsMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS);
   }
 
   llvm_unreachable("covered switch fell through?!");
 }
 
 bool
+ScalarEvolution::isImpliedViaOperations(ICmpInst::Predicate Pred,
+                                        const SCEV *LHS, const SCEV *RHS,
+                                        const SCEV *FoundLHS,
+                                        const SCEV *FoundRHS) {
+  auto GetOpFromExt = [&](const SCEV *S) {
+    if (auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
+      return Ext->getOperand();
+    return S;
+  };
+
+  auto ExtendType = [&](const SCEV *S, Type *T) {
+    if (S->getType() == T)
+      return S;
+    return getSignExtendExpr(S, T);
+  };
+
+  auto MaxType = [&](const SCEV *S1, const SCEV *S2) {
+    return S1->getType()->getIntegerBitWidth() >
+             S2->getType()->getIntegerBitWidth() ?
+               S1->getType() : S2->getType();
+  };
+
+  // Acquire values from extensions.
+  LHS = GetOpFromExt(LHS);
+  FoundLHS = GetOpFromExt(FoundLHS);
+
+  if (auto *Operation = dyn_cast<SCEVUnknown>(LHS)) {
+    Value *Op1, *Op2;
+    // FIXME: Once we have SDiv implemented, we can get rid of this matching.
+    using namespace llvm::PatternMatch;
+    if (match(Operation->getValue(),
+                      m_SDiv(m_Value(Op1), m_Value(Op2)))) {
+      // Rules for division.
+      const SCEV *Num = getSCEV(Op1);
+      const SCEV *Denum = getSCEV(Op2);
+
+      auto *Ty1 = MaxType(Num, FoundLHS);
+      auto *NumExt = ExtendType(Num, Ty1);
+      auto *FoundLHSExt = ExtendType(FoundLHS, Ty1);
+      // Require that LHS = FoundLHS / Denum.
+      if (!HasSameValue(NumExt, FoundLHSExt))
+        return false;
+
+      // Try to prove the following rules:
+      //   FoundLHS > FoundRHS > 0 => FoundLHS / 2 > 0 >= RHS.
+      //   FoundLHS >= FoundRHS > 0 => FoundLHS / 2 >= 0 >= RHS.
+      if ((Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) &&
+          isKnownPositive(FoundRHS) &&
+          isKnownPredicate(ICmpInst::ICMP_SLE, RHS,
+                           getConstant(RHS->getType(), 0u, true)) &&
+          HasSameValue(Denum, getConstant(Denum->getType(), 2u, true)))
+        return true;
+
+      // Try to prove the following rule:
+      //   FoundLHS >= FoundRHS, 0 < Denum <= FoundRHS =>
+      //     LHS = FoundLHS / Denum >= 1 >= RHS.
+      auto *Ty2 = MaxType(Denum, FoundRHS);
+      auto *DenumExt = ExtendType(Denum, Ty2);
+      auto *FoundRHSExt = ExtendType(FoundRHS, Ty2);
+      if (Pred == ICmpInst::ICMP_SGE && isKnownPositive(Denum) &&
+          isKnownPredicate(ICmpInst::ICMP_SLE, RHS,
+                           getConstant(RHS->getType(), 1u, true)) &&
+          isKnownPredicate(ICmpInst::ICMP_SLE, DenumExt, FoundRHSExt))
+        return true;
+    }
+  }
+
+  return false;
+}
+
+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 isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
            IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
   case ICmpInst::ICMP_UGT:
   case ICmpInst::ICMP_UGE:
     if (IsKnownPredicateFull(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
         IsKnownPredicateFull(ICmpInst::ICMP_ULE, RHS, FoundRHS))
       return true;
     break;
   }
 
+  if (isImpliedViaOperations(Pred, LHS, RHS, FoundLHS, FoundRHS))
+    return true;
+
   return false;
 }
 
 bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
                                                      const SCEV *LHS,
                                                      const SCEV *RHS,
                                                      const SCEV *FoundLHS,
                                                      const SCEV *FoundRHS) {