Teach ScalarEvolution to exploit SMin expressions.

[sanjoy]

Summary

This change teaches isImpliedCondOperands the following two facts:

• A ICMP_SGE smin(..., A, ...)
• smin(..., A, ...) ICMP_SLE A

[sanjoy]

This isn't sufficiently general to handle all the cases I want to handle. Please don't review ATM, I'll put up a new diff shortly.

lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      FoundLHS, FoundRHS) ||
          // ~x < ~y --> x > y
          isImpliedCondOperandsHelper(Pred, LHS, RHS,
                                      getNotSCEV(FoundRHS),
                                      getNotSCEV(FoundLHS));
 }
 
+// If Expr computes ~A assign `A' to NotOf and return true, else
+// return false.
+static bool MatchNotExpr(const SCEV *Expr, const SCEV *&NotOf) {
+  const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
+  if (!Add || Add->getNumOperands() != 2) return false;
+
+  const SCEVConstant *AddLHS = dyn_cast<SCEVConstant>(Add->getOperand(0));
+  if (!(AddLHS && AddLHS->getValue()->getValue().isAllOnesValue()))
+    return false;
+
+  const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
+  if (!AddRHS || AddRHS->getNumOperands() != 2) return false;
+
+  const SCEVConstant *MulLHS = dyn_cast<SCEVConstant>(AddRHS->getOperand(0));
+  if (!(MulLHS && MulLHS->getValue()->getValue().isAllOnesValue()))
+    return false;
+
+  NotOf = AddRHS->getOperand(1);
+  return true;
+}
+
+// Is Expr an SMin of Candidate and some other values?
+static bool IsSMinConsistingOf(const SCEV *MinExpr, const SCEV *Candidate) {
+  const SCEV *MaybeSMaxExpr = nullptr;
+  if (!MatchNotExpr(MinExpr, MaybeSMaxExpr))
+    return false;
+
+  const SCEVSMaxExpr *SMaxExpr = dyn_cast<SCEVSMaxExpr>(MaybeSMaxExpr);
+  if (!SMaxExpr) return false;
+
+  for (unsigned i = 0, e = SMaxExpr->getNumOperands(); i != e; i++) {
+    const SCEV *NotOf = nullptr;
+    if (MatchNotExpr(SMaxExpr->getOperand(i), NotOf) && NotOf == Candidate)
+      return true;
+  }
+
+  return false;
+}
+
+// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a SMin
+// expression?
+static bool IsKnownPredicateViaSMinExpr(ICmpInst::Predicate Pred,
+                                        const SCEV *LHS, const SCEV *RHS) {
+  if (Pred == ICmpInst::ICMP_SLE) {
+    // min(A, ...) <= A
+    return IsSMinConsistingOf(LHS, RHS);
+  } else if (Pred == ICmpInst::ICMP_SGE) {
+    // A >= min(A, ...)
+    return IsSMinConsistingOf(RHS, LHS);
+  }
+
+  // This sort of reasoning can be easily extended to general work on
+  // {u|s}{min|max} expression.
+  return false;
+}
+
 /// 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
 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) ||
+        IsKnownPredicateViaSMinExpr(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;
     break;
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_SLE:
-    if (isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
-        isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, RHS, FoundRHS))
+    if (IsKnownPredicateFull(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
+        IsKnownPredicateFull(ICmpInst::ICMP_SGE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_SGE:
-    if (isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
-        isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, RHS, FoundRHS))
+    if (IsKnownPredicateFull(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
+        IsKnownPredicateFull(ICmpInst::ICMP_SLE, RHS, FoundRHS))
       return true;
     break;
   case ICmpInst::ICMP_ULT:
   case ICmpInst::ICMP_ULE:
     if (isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, LHS, FoundLHS) &&
         isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, RHS, FoundRHS))
       return true;
     break;

test/Transforms/IndVarSimplify/backedge-on-min-max.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+define void @foo.1(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @foo.1
+ entry:
+  %min.cmp = icmp slt i32 %a_len, %n
+  %min = select i1 %min.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp slt i32 0, %min
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp slt i32 %idx, %a_len
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp slt i32 %idx.inc, %min
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @foo.2(i32* %a, i32 %a_len, i32 %n) {
+; CHECK-LABEL: @foo.2
+ entry:
+  %min.cmp = icmp slt i32 %a_len, %n
+  %min = select i1 %min.cmp, i32 %a_len, i32 %n
+  %entry.cond = icmp slt i32 0, %min
+  br i1 %entry.cond, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ]
+  %idx.inc = add i32 %idx, 1
+  %in.bounds = icmp sgt i32 %a_len, %idx
+  br i1 %in.bounds, label %ok, label %latch
+; CHECK: br i1 true, label %ok, label %latch
+
+ ok:
+  %addr = getelementptr i32* %a, i32 %idx
+  store i32 %idx, i32* %addr
+  br label %latch
+
+ latch:
+  %be.cond = icmp slt i32 %idx.inc, %min
+  br i1 %be.cond, label %loop, label %exit
+
+ exit:
+  ret void
+}