[CorrelatedValuePropagation] Convert an SDiv to a UDiv if both operands are known to be nonnegative

[haicheng]

Summary

The motivating example is this

for (j = n; j > 1; j = i) {
   i = j / 2;
}

The signed division is safely to be changed to an unsigned division (j is known to be larger than 1 from the loop guard) and later turned into a shift. LLVM currently cannot figure it out and translates the division into at least 3 instructions.

[mcrosier]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

342

No need to include the function name in the comments. I believe doxygen will take care of this for you.

348

Is this check to make sure we don't try to optimize vectors? If so, it might be more clear to use isVectorTy(), rather than !isIntegerTy().

[bkramer]

Why can't this be handled by SimplifyDemandedBits instead of CVP?

[haicheng]

In D17921#368916, @bkramer wrote:

Why can't this be handled by SimplifyDemandedBits instead of CVP?

If I understand it correctly, SimplifyDemandedBits relies on ValueTracking::computeKnownBits() to find KnownZero and KnownOne. @reames had some experimental code, dom-condition, in ValueTracking that was able to find out non-local information such as j>1 in the example for computeKnownBits(). However, the experimental code is removed in r262646. Moreover, I think approaches similar to dom-condition might be too much for my simple case. Maybe, @reames could provide my insights.

Besides, is there any downside of doing it in CVP?

[haicheng]

Address Chad's comments first.

[bkramer]

In D17921#369252, @haicheng wrote:

Besides, is there any downside of doing it in CVP?

Not many, it's just a new transformation in CVP that's already mostly handled by SimplifyDemandedBits. If ValueTracking can't properly support non-local things CVP is probably the better place.

[haicheng]

In D17921#369802, @bkramer wrote:

ValueTracking can't properly support non-local things

I think that is what I learnt from @reames's experiment.

[reames]

Code wise, looks close to good to go, but I'm missing something design wise. Why is it a good idea to canonicalize sdiv to udiv in general? I can see why when the second operand is a special constant, but why in general?

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

362

Pull the constant int out of the loop.

test/Transforms/CorrelatedValuePropagation/sdiv.ll

16

Please add a couple of extra tests:

• a negative test to show it doesn't trigger when negative
• a simpler case without a loop to show that it works with an early exit guard

[haicheng]

In D17921#371030, @reames wrote:

Why is it a good idea to canonicalize sdiv to udiv in general? I can see why when the second operand is a special constant, but why in general?

Thank you for reviewing the patch. I do this in general just because InstCombiner::visitSDiv() changes sdiv->udiv when both operands are nonnegative (the last case in visitSDiv()).

I agree that the most profitable case is that the second operand is a PowerOfTwo and I have no problem only taking care of this special case.

[reames]

In D17921#371213, @haicheng wrote:

In D17921#371030, @reames wrote:

Why is it a good idea to canonicalize sdiv to udiv in general? I can see why when the second operand is a special constant, but why in general?

Thank you for reviewing the patch. I do this in general just because InstCombiner::visitSDiv() changes sdiv->udiv when both operands are nonnegative (the last case in visitSDiv()).

I agree that the most profitable case is that the second operand is a PowerOfTwo and I have no problem only taking care of this special case.

I hadn't realized we already canonicalized one to the other. Given that parts not new, I'm happy to take this patch essentially as is with the previously expressed comments addressed.

[haicheng]

Address Philip's comments. Thank you.

[haicheng]

Clean the format.

[reames]

LGTM w/a couple of really minor comments addressed.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

38

minor: propagated is the wrong word. Possibly: "converted to udiv"

344

minor: the code is proving the inputs positive, not non-negative.

test/Transforms/CorrelatedValuePropagation/sdiv.ll

36

Please use a check line rather than a CHECK-NOT line here. The check-not is too fragile in the face of minor changes. (e.g. naming)

[haicheng]

Address Philip's comment.

[mcrosier]

Committed r263406.

[jlebar]

This patch regresses our ability to unroll

void dummy(int);
void foo() {
#pragma unroll
  for (int i = 32; i > 0; i /= 2) { dummy(i); }
}

It's unclear to me whether this is a deficiency in scalar evolution or a bad canonicalization, although the comments above suggest maybe the latter?

[sanjoy]

This is a deficiency in SCEV, should be fixed in
http://reviews.llvm.org/rL274199

[mcrosier]

In D17921#470975, @sanjoy wrote:

This is a deficiency in SCEV, should be fixed in
http://reviews.llvm.org/rL274199

Thanks, Sanjoy!

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 #define DEBUG_TYPE "correlated-value-propagation"
 
 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");
 
 namespace {
   class CorrelatedValuePropagation : public FunctionPass {
     LazyValueInfo *LVI;
 
     bool processSelect(SelectInst *SI);
     bool processPHI(PHINode *P);
     bool processMemAccess(Instruction *I);
     bool processCmp(CmpInst *C);
     bool processSwitch(SwitchInst *SI);
     bool processCallSite(CallSite CS);
+    bool processSDiv(BinaryOperator *SDI);
 
     /// Return a constant value for V usable at At and everything it
     /// dominates.  If no such Constant can be found, return nullptr.
     Constant *getConstantAt(Value *V, Instruction *At);
 
   public:
     static char ID;
     CorrelatedValuePropagation(): FunctionPass(ID) {
bool CorrelatedValuePropagation::processCallSite(CallSite CS) {
   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
+/// nonnegative.  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.
+bool CorrelatedValuePropagation::processSDiv(BinaryOperator *SDI) {
+  if (SDI->getType()->isVectorTy())
+    return false;
+
+  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;
+  }
+
+  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
+  for (Value *O : SDI->operands()) {
+    LazyValueInfo::Tristate Result =
+        LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
+    if (Result != LazyValueInfo::True)
+      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();
+
+  return true;
+}
+
 Constant *CorrelatedValuePropagation::getConstantAt(Value *V, Instruction *At) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
 
   // TODO: The following really should be sunk inside LVI's core algorithm, or
   // at least the outer shims around such.
   auto *C = dyn_cast<CmpInst>(V);
   if (!C) return nullptr;
for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
       case Instruction::Load:
       case Instruction::Store:
         BBChanged |= processMemAccess(II);
         break;
       case Instruction::Call:
       case Instruction::Invoke:
         BBChanged |= processCallSite(CallSite(II));
         break;
+      case Instruction::SDiv:
+        BBChanged |= processSDiv(cast<BinaryOperator>(II));
+        break;
       }
     }
 
     Instruction *Term = FI->getTerminator();
     switch (Term->getOpcode()) {
     case Instruction::Switch:
       BBChanged |= processSwitch(cast<SwitchInst>(Term));
       break;

test/Transforms/CorrelatedValuePropagation/sdiv.ll

+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test0(
+define void @test0(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %j.0 = phi i32 [ %n, %entry ], [ %div, %for.body ]
+  %cmp = icmp sgt i32 %j.0, 1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+; CHECK: %div1 = udiv i32 %j.0, 2 
+  %div = sdiv i32 %j.0, 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+; CHECK-LABEL: @test1(
+define void @test1(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %j.0 = phi i32 [ %n, %entry ], [ %div, %for.body ]
+  %cmp = icmp sgt i32 %j.0, -2
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+; CHECK: %div = sdiv i32 %j.0, 2 
+  %div = sdiv i32 %j.0, 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+; CHECK-LABEL: @test2(
+define void @test2(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 1
+  br i1 %cmp, label %bb, label %exit
+
+bb:                                         
+; CHECK: %div1 = udiv i32 %n, 2 
+  %div = sdiv i32 %n, 2
+  br label %exit
+
+exit:                                         
+  ret void
+}