From 25fa0d406c5d953c4361baaf8290de40ce82513e Mon Sep 17 00:00:00 2001
From: Hal Finkel <hfinkel@anl.gov>
Date: Wed, 19 Aug 2015 01:51:51 +0000
Subject: [PATCH] Make ScalarEvolution::isKnownPredicate a little smarter

Here we make ScalarEvolution::isKnownPredicate, indirectly, a little smarter.
Given some relational comparison operator OP, and two AddRec SCEVs, {I,+,S} OP
{J,+,T}, we can reduce this to the comparison I OP J when S == T, both AddRecs
are for the same loop, and both are known not to wrap.

As it turns out, because of the way that backedge-guard expressions can be
leveraged when computing known predicates, this allows indvars to simplify the
if-statement comparison in this loop:

  void foo (int *a, int *b, int n) {
    for (int i = 0; i < n; ++i) {
      if (i > n)
        a[i] = b[i] + 1;
    }
  }

which, somewhat surprisingly, we were not previously optimizing away.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245400 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/ScalarEvolution.cpp          | 39 ++++++++++++++++++-
 test/Transforms/IndVarSimplify/bec-cmp.ll | 47 +++++++++++++++++++++++
 2 files changed, 85 insertions(+), 1 deletion(-)
 create mode 100644 test/Transforms/IndVarSimplify/bec-cmp.ll

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 7cf08bd7156..363731a0b6c 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -7326,6 +7326,42 @@ static bool IsMinConsistingOf(ScalarEvolution &SE,
   return IsMaxConsistingOf<MaxExprType>(MaybeMaxExpr, SE.getNotSCEV(Candidate));
 }
 
+static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE,
+                                           ICmpInst::Predicate Pred,
+                                           const SCEV *LHS, const SCEV *RHS) {
+
+  // If both sides are affine addrecs for the same loop, with equal
+  // steps, and we know the recurrences don't wrap, then we only
+  // need to check the predicate on the starting values.
+
+  if (!ICmpInst::isRelational(Pred))
+    return false;
+
+  const SCEVAddRecExpr *LAR = dyn_cast<SCEVAddRecExpr>(LHS);
+  if (!LAR)
+    return false;
+  const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS);
+  if (!RAR)
+    return false;
+  if (LAR->getLoop() != RAR->getLoop())
+    return false;
+  if (!LAR->isAffine() || !RAR->isAffine())
+    return false;
+
+  if (LAR->getStepRecurrence(SE) != RAR->getStepRecurrence(SE))
+    return false;
+
+  auto CheckWrap = [Pred](const SCEVAddRecExpr *AR) -> bool {
+    if (ICmpInst::isSigned(Pred))
+      return AR->getNoWrapFlags(SCEV::FlagNSW);
+    return AR->getNoWrapFlags(SCEV::FlagNUW);
+  };
+
+  if (!CheckWrap(LAR) || !CheckWrap(RAR))
+    return false;
+
+  return SE.isKnownPredicate(Pred, LAR->getStart(), RAR->getStart());
+}
 
 /// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a Min or Max
 /// expression?
@@ -7371,7 +7407,8 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
   auto IsKnownPredicateFull =
       [this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
     return isKnownPredicateWithRanges(Pred, LHS, RHS) ||
-        IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS);
+        IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
+        IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS);
   };
 
   switch (Pred) {
diff --git a/test/Transforms/IndVarSimplify/bec-cmp.ll b/test/Transforms/IndVarSimplify/bec-cmp.ll
new file mode 100644
index 00000000000..06a7d5ebe4d
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/bec-cmp.ll
@@ -0,0 +1,47 @@
+; RUN: opt -S -indvars < %s | FileCheck %s
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-unknown-linux-gnu"
+
+; Function Attrs: nounwind
+define void @foo(i32* nocapture %a, i32* nocapture readonly %b, i32 signext %n) #0 {
+entry:
+
+; CHECK-LABEL: @foo
+
+  %cmp.10 = icmp sgt i32 %n, 0
+  br i1 %cmp.10, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.cond.for.cond.cleanup_crit_edge:              ; preds = %for.inc
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.for.cond.cleanup_crit_edge, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc
+  %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp sgt i32 %i.011, %n
+  br i1 %cmp1, label %if.then, label %for.inc
+
+; CHECK-NOT: br i1 %cmp1, label %if.then, label %for.inc
+; CHECK: br i1 false, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %idxprom = sext i32 %i.011 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %b, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, 1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %inc = add nsw i32 %i.011, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge
+}
+
+attributes #0 = { nounwind }
+
-- 
2.34.1