Convert a signed remainder instruction to unsigned remainder

[SjoerdMeijer]

Summary

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.

[jmolloy]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

343–344

You can simplify this by using "auto"

352

All of these checks can be combined into one if with ||.

[SjoerdMeijer]

Addressed James' comments

[mehdi_amini]

test/Transforms/CorrelatedValuePropagation/srem.ll

26

Do you need all these basic blocks and instructions? (i.e: is this test minimal?)

[SjoerdMeijer]

Simplified the regression test. The transformation triggers when value range can determine that the operands are >= 0. This is accomplished with and if-statement instead of a while loop, which simplifies the test.

[jmolloy]

LGTM now!

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 
 STATISTIC(NumPhis,      "Number of phis propagated");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 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 {
   public:
     static char ID;
     CorrelatedValuePropagation(): FunctionPass(ID) {
      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     }
static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
   AttributeSet AS = CS.getAttributes();
   LLVMContext &Ctx = CS.getInstruction()->getContext();
   AS = AS.addAttribute(Ctx, Indices, Attribute::get(Ctx, Attribute::NonNull));
   CS.setAttributes(AS);
 
   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;
+  }
 
+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),
                                         SDI->getName(), SDI);
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
   SDI->eraseFromParent();
 
for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
       case Instruction::Load:
       case Instruction::Store:
         BBChanged |= processMemAccess(II, LVI);
         break;
       case Instruction::Call:
       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;
       }
     }
 
     Instruction *Term = BB.getTerminator();
     switch (Term->getOpcode()) {

test/Transforms/CorrelatedValuePropagation/srem.ll

+; 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:
+  br label %while.cond
+; CHECK-LABEL: @h(
+; CHECK: urem
+
+while.cond:
+  %p.addr.0 = phi i32* [ %p, %entry ], [ %incdec.ptr, %while.body ]
+  %x.addr.0 = phi i32 [ %x, %entry ], [ %div4, %while.body ]
+  %cmp = icmp sgt i32 %x.addr.0, 0
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:
+  %rem3 = srem i32 %x.addr.0, 10
+  %incdec.ptr = getelementptr inbounds i32, i32* %p.addr.0, i32 1
+  store i32 %rem3, i32* %p.addr.0, align 4
+  %div4 = udiv i32 %x.addr.0, 10
+  br label %while.cond
+
+while.end:
+  ret void
+}
+
+
+
+attributes #0 = { minsize norecurse nounwind optsize }