This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by haicheng on Mar 6 2016, 5:50 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

haicheng updated this revision to Diff 49927.Mar 6 2016, 5:50 PM
haicheng retitled this revision from to [CorrelatedValuePropagation] Convert an SDiv to a UDiv if both operands are known to be nonnegative.
haicheng updated this object.
haicheng set the repository for this revision to rL LLVM.
haicheng added a subscriber: llvm-commits.
mcrosier added inline comments.Mar 7 2016, 6:04 AM
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 added a subscriber: bkramer.Mar 7 2016, 6:17 AM

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

haicheng added a comment.EditedMar 7 2016, 1:39 PM

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 updated this revision to Diff 50047.Mar 8 2016, 8:39 AM
haicheng marked 2 inline comments as done.

Address Chad's comments first.

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.

ValueTracking can't properly support non-local things

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

reames requested changes to this revision.Mar 9 2016, 11:57 AM
reames edited edge metadata.

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
This revision now requires changes to proceed.Mar 9 2016, 11:57 AM

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 added a comment.Mar 9 2016, 2:18 PM

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 updated this revision to Diff 50226.Mar 9 2016, 7:08 PM
haicheng edited edge metadata.
haicheng marked 2 inline comments as done.

Address Philip's comments. Thank you.

haicheng updated this revision to Diff 50227.Mar 9 2016, 7:12 PM
haicheng edited edge metadata.

Clean the format.

reames accepted this revision.Mar 10 2016, 6:08 PM
reames edited edge metadata.

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)

This revision is now accepted and ready to land.Mar 10 2016, 6:08 PM
haicheng updated this revision to Diff 50565.Mar 13 2016, 8:27 PM
haicheng edited edge metadata.
haicheng marked 3 inline comments as done.

Address Philip's comment.

mcrosier closed this revision.Mar 14 2016, 8:54 AM
mcrosier edited edge metadata.

Committed r263406.

jlebar added a subscriber: jlebar.Jun 29 2016, 6:11 PM

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 edited edge metadata.Jun 29 2016, 8:28 PM
sanjoy added a subscriber: sanjoy.

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

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

Thanks, Sanjoy!