From 8ba782a30cbc855cccafc6b8be6fb16bad12fa67 Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Sun, 20 Sep 2015 01:52:18 +0000
Subject: [PATCH] [IndVars] Fix a bug in r248045.

Because -indvars widens induction variables through arithmetic,
`NeverNegative` cannot be a property of the `WidenIV` (a `WidenIV`
manages information for all transitive uses of an IV being widened,
including uses of `-1 * IV`).  Instead it must live on `NarrowIVDefUse`
which manages information for a specific def-use edge in the transitive
use list of an induction variable.

This change also adds a test case that demonstrates the problem with
r248045.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@248107 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/IndVarSimplify.cpp      | 33 +++++++++++--------
 .../IndVarSimplify/widen-loop-comp.ll         | 32 ++++++++++++++++++
 2 files changed, 51 insertions(+), 14 deletions(-)

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index c58c9978b82..72d95794949 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -832,10 +832,19 @@ struct NarrowIVDefUse {
   Instruction *NarrowUse;
   Instruction *WideDef;
 
-  NarrowIVDefUse(): NarrowDef(nullptr), NarrowUse(nullptr), WideDef(nullptr) {}
+  // True if the narrow def is never negative.  Tracking this information lets
+  // us use a sign extension instead of a zero extension or vice versa, when
+  // profitable and legal.
+  bool NeverNegative;
+
+  NarrowIVDefUse()
+      : NarrowDef(nullptr), NarrowUse(nullptr), WideDef(nullptr),
+        NeverNegative(false) {}
 
-  NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD):
-    NarrowDef(ND), NarrowUse(NU), WideDef(WD) {}
+  NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
+                 bool NeverNegative)
+      : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
+        NeverNegative(NeverNegative) {}
 };
 
 /// WidenIV - The goal of this transform is to remove sign and zero extends
@@ -849,11 +858,6 @@ class WidenIV {
   Type *WideType;
   bool IsSigned;
 
-  // True if the narrow induction variable is never negative.  Tracking this
-  // information lets us use a sign extension instead of a zero extension or
-  // vice versa, when profitable and legal.
-  bool NeverNegative;
-
   // Context
   LoopInfo        *LI;
   Loop            *L;
@@ -876,7 +880,6 @@ public:
     OrigPhi(WI.NarrowIV),
     WideType(WI.WidestNativeType),
     IsSigned(WI.IsSigned),
-    NeverNegative(false),
     LI(LInfo),
     L(LI->getLoopFor(OrigPhi->getParent())),
     SE(SEv),
@@ -1103,7 +1106,7 @@ bool WidenIV::WidenLoopCompare(NarrowIVDefUse DU) {
   //      (A) == icmp slt i32 sext(%narrow), sext(%val)
   //          == icmp slt i32 zext(%narrow), sext(%val)
 
-  if (!(NeverNegative || IsSigned == Cmp->isSigned()))
+  if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
     return false;
 
   Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
@@ -1240,6 +1243,10 @@ Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
 /// pushNarrowIVUsers - Add eligible users of NarrowDef to NarrowIVUsers.
 ///
 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
+  const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
+  bool NeverNegative =
+      SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
+                           SE->getConstant(NarrowSCEV->getType(), 0));
   for (User *U : NarrowDef->users()) {
     Instruction *NarrowUser = cast<Instruction>(U);
 
@@ -1247,7 +1254,8 @@ void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
     if (!Widened.insert(NarrowUser).second)
       continue;
 
-    NarrowIVUsers.push_back(NarrowIVDefUse(NarrowDef, NarrowUser, WideDef));
+    NarrowIVUsers.push_back(
+        NarrowIVDefUse(NarrowDef, NarrowUser, WideDef, NeverNegative));
   }
 }
 
@@ -1267,9 +1275,6 @@ PHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) {
   if (!AddRec)
     return nullptr;
 
-  NeverNegative = SE->isKnownPredicate(ICmpInst::ICMP_SGE, AddRec,
-                                       SE->getConstant(AddRec->getType(), 0));
-
   // Widen the induction variable expression.
   const SCEV *WideIVExpr = IsSigned ?
     SE->getSignExtendExpr(AddRec, WideType) :
diff --git a/test/Transforms/IndVarSimplify/widen-loop-comp.ll b/test/Transforms/IndVarSimplify/widen-loop-comp.ll
index 5860bf2a8b3..b87cd055019 100644
--- a/test/Transforms/IndVarSimplify/widen-loop-comp.ll
+++ b/test/Transforms/IndVarSimplify/widen-loop-comp.ll
@@ -321,3 +321,35 @@ for.end:
 leave:
   ret i32 0
 }
+
+declare void @consume.i64(i64)
+declare void @consume.i1(i1)
+
+define i32 @test10(i32 %v) {
+; CHECK-LABEL: @test10(
+ entry:
+; CHECK-NOT: zext
+  br label %loop
+
+ loop:
+; CHECK: loop:
+; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 0, %entry ]
+; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+; CHECK: [[MUL:%[a-z0-9]+]] = mul nsw i64 %indvars.iv, -1
+; CHECK: [[MUL_TRUNC:%[a-z0-9]+]] = trunc i64 [[MUL]] to i32
+; CHECK: [[CMP:%[a-z0-9]+]] = icmp eq i32 [[MUL_TRUNC]], %v
+; CHECK: call void @consume.i1(i1 [[CMP]])
+
+  %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
+  %i.inc = add i32 %i, 1
+  %iv = mul i32 %i, -1
+  %cmp = icmp eq i32 %iv, %v
+  call void @consume.i1(i1 %cmp)
+  %be.cond = icmp slt i32 %i.inc, 11
+  %ext = sext i32 %iv to i64
+  call void @consume.i64(i64 %ext)
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret i32 22
+}
-- 
2.34.1