From 7e18f7d8ed019d32bdc75d00c50f4cc74a90ba27 Mon Sep 17 00:00:00 2001
From: Chad Rosier <mcrosier@codeaurora.org>
Date: Wed, 12 Oct 2016 13:41:38 +0000
Subject: [PATCH] [CVP] Convert an AShr to a LShr if 1st operand is known to be
 nonnegative.

An arithmetic shift can be safely changed to a logical shift if the first
operand is known positive. This allows ComputeKnownBits (and similar analysis)
to determine the sign bit of the shifted value in some cases. In turn, this
allows InstCombine to canonicalize a signed comparison (a > 0) into an equality
check (a != 0).

PR30577

Differential Revision: https://reviews.llvm.org/D25119

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@284013 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/CorrelatedValuePropagation.cpp     | 23 ++++++++
 .../CorrelatedValuePropagation/ashr.ll        | 56 +++++++++++++++++++
 2 files changed, 79 insertions(+)
 create mode 100644 test/Transforms/CorrelatedValuePropagation/ashr.ll

diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index 535ff1a6a68..fac8c156cb5 100644
--- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -38,6 +38,7 @@ STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
+STATISTIC(NumAShrs,     "Number of ashr converted to lshr");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
 
 static cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(false));
@@ -384,6 +385,25 @@ static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
   return true;
 }
 
+static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
+  if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI))
+    return false;
+
+  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
+  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
+      LazyValueInfo::True)
+    return false;
+
+  ++NumAShrs;
+  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
+                                        SDI->getName(), SDI);
+  BO->setIsExact(SDI->isExact());
+  SDI->replaceAllUsesWith(BO);
+  SDI->eraseFromParent();
+
+  return true;
+}
+
 static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
   typedef OverflowingBinaryOperator OBO;
 
@@ -495,6 +515,9 @@ static bool runImpl(Function &F, LazyValueInfo *LVI) {
       case Instruction::SDiv:
         BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
         break;
+      case Instruction::AShr:
+        BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
+        break;
       case Instruction::Add:
         BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
         break;
diff --git a/test/Transforms/CorrelatedValuePropagation/ashr.ll b/test/Transforms/CorrelatedValuePropagation/ashr.ll
new file mode 100644
index 00000000000..5e6bd1102b7
--- /dev/null
+++ b/test/Transforms/CorrelatedValuePropagation/ashr.ll
@@ -0,0 +1,56 @@
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test1
+define void @test1(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %a = phi i32 [ %n, %entry ], [ %shr, %for.body ]
+  %cmp = icmp sgt i32 %a, 1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+; CHECK: lshr i32 %a, 5
+  %shr = ashr i32 %a, 5
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+;; Negative test to show transform doesn't happen unless n > 0.
+; CHECK-LABEL: @test2
+define void @test2(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %a = phi i32 [ %n, %entry ], [ %shr, %for.body ]
+  %cmp = icmp sgt i32 %a, -2
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+; CHECK: ashr i32 %a, 2
+  %shr = ashr i32 %a, 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+;; Non looping test case.
+; CHECK-LABEL: @test3
+define void @test3(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: lshr exact i32 %n, 4
+  %shr = ashr exact i32 %n, 4
+  br label %exit
+
+exit:
+  ret void
+}
-- 
2.50.0