From 11ef606f1d33a8c368b1d071631eba28ae50a94c Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Thu, 3 Mar 2016 18:31:23 +0000
Subject: [PATCH] [SCEV] Be less eager about demoting zexts to sexts

After r262438 we can have provably positive NSW SCEV expressions whose
zero extensions cannot be simplified (since r262438 makes SCEV better at
computing constant ranges).  This means demoting sexts of positive add
recurrences eagerly can result in an unsimplified zero extension where
we could have had a simplified sign extension.  This change fixes the
issue by teaching SCEV to demote sext of a positive SCEV expression to a
zext only if the sext could not be simplified.

llvm-svn: 262638
---
 llvm/lib/Analysis/ScalarEvolution.cpp              |  9 +++++----
 llvm/test/Analysis/ScalarEvolution/sext-to-zext.ll | 23 ++++++++++++++++++++++
 2 files changed, 28 insertions(+), 4 deletions(-)
 create mode 100644 llvm/test/Analysis/ScalarEvolution/sext-to-zext.ll

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 1cb39f6..0365862 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -1612,10 +1612,6 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 
-  // If the input value is provably positive, build a zext instead.
-  if (isKnownNonNegative(Op))
-    return getZeroExtendExpr(Op, Ty);
-
   // sext(trunc(x)) --> sext(x) or x or trunc(x)
   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) {
     // It's possible the bits taken off by the truncate were all sign bits. If
@@ -1781,6 +1777,11 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
       }
     }
 
+  // If the input value is provably positive and we could not simplify
+  // away the sext build a zext instead.
+  if (isKnownNonNegative(Op))
+    return getZeroExtendExpr(Op, Ty);
+
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
diff --git a/llvm/test/Analysis/ScalarEvolution/sext-to-zext.ll b/llvm/test/Analysis/ScalarEvolution/sext-to-zext.ll
new file mode 100644
index 0000000..ca9c6de
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/sext-to-zext.ll
@@ -0,0 +1,23 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define void @f(i1 %c) {
+; CHECK-LABEL: Classifying expressions for: @f
+entry:
+  %start = select i1 %c, i32 100, i32 0
+  %step =  select i1 %c, i32 -1,  i32 1
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.dec, %loop ]
+  %iv.tc = phi i32 [ 0, %entry ], [ %iv.tc.inc, %loop ]
+  %iv.tc.inc = add i32 %iv.tc, 1
+  %iv.dec = add nsw i32 %iv, %step
+  %iv.sext = sext i32 %iv to i64
+; CHECK:  %iv.sext = sext i32 %iv to i64
+; CHECK-NEXT:  -->  {(sext i32 %start to i64),+,(sext i32 %step to i64)}<nsw><%loop>
+  %be = icmp ne i32 %iv.tc.inc, 100
+  br i1 %be, label %loop, label %leave
+
+leave:
+  ret void
+}
-- 
2.7.4