From 4fab1d4f07d728d5f2d0831ceaebf4b0dbed79d7 Mon Sep 17 00:00:00 2001
From: Sjoerd Meijer <sjoerd.meijer@arm.com>
Date: Thu, 14 Jul 2016 12:23:48 +0000
Subject: [PATCH] This converts a signed remainder instruction to unsigned
 remainder, which enables the code size optimisation to fold a rem and div
 into a single aeabi_uidivmod call. This was not happening before because sdiv
 was converted but srem not, and instructions with different signedness are
 not combined.

Differential Revision: http://reviews.llvm.org/D22214


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@275403 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/CorrelatedValuePropagation.cpp     | 53 +++++++++++++------
 .../CorrelatedValuePropagation/srem.ll        | 21 ++++++++
 2 files changed, 59 insertions(+), 15 deletions(-)
 create mode 100644 test/Transforms/CorrelatedValuePropagation/srem.ll

diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index c09f3534dcf..c0fed053339 100644
--- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -37,6 +37,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(NumSRems,     "Number of srem converted to urem");
 
 namespace {
   class CorrelatedValuePropagation : public FunctionPass {
@@ -325,31 +326,50 @@ static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
   return true;
 }
 
-/// See if LazyValueInfo's ability to exploit edge conditions or range
-/// information is sufficient to prove the both operands of this SDiv are
-/// positive.  If this is the case, replace the SDiv with a UDiv. Even for local
-/// conditions, this can sometimes prove conditions instcombine can't by
-/// exploiting range information.
-static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
-  if (SDI->getType()->isVectorTy())
-    return false;
-
+// Helper function to rewrite srem and sdiv. As a policy choice, we choose not
+// to waste compile time on anything where the operands are local defs.  While
+// LVI can sometimes reason about such cases, it's not its primary purpose.
+static bool hasLocalDefs(BinaryOperator *SDI) {
   for (Value *O : SDI->operands()) {
-    // As a policy choice, we choose not to waste compile time on anything where
-    // the operands are local defs.  While LVI can sometimes reason about such
-    // cases, it's not its primary purpose.
     auto *I = dyn_cast<Instruction>(O);
     if (I && I->getParent() == SDI->getParent())
-      return false;
+      return true;
   }
+  return false;
+}
 
+static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) {
   Constant *Zero = ConstantInt::get(SDI->getType(), 0);
   for (Value *O : SDI->operands()) {
-    LazyValueInfo::Tristate Result =
-        LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
+    auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
     if (Result != LazyValueInfo::True)
       return false;
   }
+  return true;
+}
+
+static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
+  if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) ||
+      !hasPositiveOperands(SDI, LVI))
+    return false;
+
+  ++NumSRems;
+  auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
+                                        SDI->getName(), SDI);
+  SDI->replaceAllUsesWith(BO);
+  SDI->eraseFromParent();
+  return true;
+}
+
+/// See if LazyValueInfo's ability to exploit edge conditions or range
+/// information is sufficient to prove the both operands of this SDiv are
+/// positive.  If this is the case, replace the SDiv with a UDiv. Even for local
+/// conditions, this can sometimes prove conditions instcombine can't by
+/// exploiting range information.
+static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
+  if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) ||
+      !hasPositiveOperands(SDI, LVI))
+    return false;
 
   ++NumSDivs;
   auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
@@ -410,6 +430,9 @@ static bool runImpl(Function &F, LazyValueInfo *LVI) {
       case Instruction::Invoke:
         BBChanged |= processCallSite(CallSite(II), LVI);
         break;
+      case Instruction::SRem:
+        BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
+        break;
       case Instruction::SDiv:
         BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
         break;
diff --git a/test/Transforms/CorrelatedValuePropagation/srem.ll b/test/Transforms/CorrelatedValuePropagation/srem.ll
new file mode 100644
index 00000000000..7c954856655
--- /dev/null
+++ b/test/Transforms/CorrelatedValuePropagation/srem.ll
@@ -0,0 +1,21 @@
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7m-arm-none-eabi"
+
+define void @h(i32* nocapture %p, i32 %x) local_unnamed_addr #0 {
+entry:
+; CHECK-LABEL: @h(
+; CHECK: urem
+
+  %cmp = icmp sgt i32 %x, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  %rem2 = srem i32 %x, 10
+  store i32 %rem2, i32* %p, align 4
+  br label %if.end
+
+if.end:
+  ret void
+}
-- 
2.49.0