Fix for bug in indvars / SCEV generating wrong code (PR18223)

[spatel]

Summary

As diagnosed by Justin Bogner in http://llvm.org/bugs/show_bug.cgi?id=18223:
ScalarEvolution::isKnownPredicate() can wrongly reduce a comparison when both the LHS and RHS are SCEVAddRecExprs.

This patch checks that both LHS and RHS are guarded in the case when both are SCEVAddRecExprs.

The test case is against indvars because I could not find a way to directly test SCEV.

[atrick]

I'll let Justin review this first since he also has a potential patch. Then I'll review the outcome of that review.

[atrick]

LGTM

lib/Analysis/ScalarEvolution.cpp

 
   // If LHS or RHS is an addrec, check to see if the condition is true in
   // every iteration of the loop.
-  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
-    if (isLoopEntryGuardedByCond(
-          AR->getLoop(), Pred, AR->getStart(), RHS) &&
-        isLoopBackedgeGuardedByCond(
-          AR->getLoop(), Pred, AR->getPostIncExpr(*this), RHS))
-      return true;
-  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(RHS))
-    if (isLoopEntryGuardedByCond(
-          AR->getLoop(), Pred, LHS, AR->getStart()) &&
-        isLoopBackedgeGuardedByCond(
-          AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*this)))
-      return true;
-
+  // If LHS and RHS are both addrec, both conditions must be true in
+  // every iteration of the loop.
+  const SCEVAddRecExpr *LAR = dyn_cast<SCEVAddRecExpr>(LHS);
+  const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS);
+  bool LeftGuarded = false;
+  bool RightGuarded = false;
+  if (LAR) {
+    const Loop *L = LAR->getLoop();
+    if (isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
+        isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) {
+      if (!RAR) return true;
+      LeftGuarded = true;
+    }
+  }
+  if (RAR) {
+    const Loop *L = RAR->getLoop();
+    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;
+  
   // Otherwise see what can be done with known constant ranges.
   return isKnownPredicateWithRanges(Pred, LHS, RHS);
 }

test/Transforms/IndVarSimplify/pr18223.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+
+; indvars should transform the phi node pair from the for-loop    
+; CHECK-LABEL: @main(
+; CHECK: ret = phi i32 [ 0, %entry ], [ 0, {{.*}} ]
+
+@c = common global i32 0, align 4
+
+define i32 @main() #0 {
+entry:
+  %0 = load i32* @c, align 4
+  %tobool = icmp eq i32 %0, 0
+  br i1 %tobool, label %for.body, label %exit
+
+for.body:
+  %inc2 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %sub = add i32 %inc2, -1
+  %cmp1 = icmp uge i32 %sub, %inc2
+  %conv = zext i1 %cmp1 to i32
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %inc2, 1
+  %cmp = icmp slt i32 %inc, 5
+  br i1 %cmp, label %for.body, label %exit
+
+exit:
+  %ret = phi i32 [ 0, %entry ], [ %conv, %for.inc ]
+  ret i32 %ret
+}