Page MenuHomePhabricator

[Instcombine] Recognize test for overflow in integer multiplication.
ClosedPublic

Authored by sepavloff on Feb 16 2014, 4:19 AM.

Details

Reviewers
bkramer
Summary

If multiplication involves zero-extended arguments and the result is
compared as in the patterns:

%mul32 = trunc i64 %mul64 to i32
%zext = zext i32 %mul32 to i64
%overflow = icmp ne i64 %mul64, %zext

or

%overflow = icmp ugt i64 %mul64 , 0xffffffff

then the multiplication may be replaced by call to umul.with.overflow.
This change fixes PR4917 and PR4918.

Diff Detail

Event Timeline

sepavloff updated this revision to Unknown Object (????).Feb 25 2014, 3:58 AM

Removed unused variables.

ahatanak added inline comments.Mar 6 2014, 10:31 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
2122

If the comparison is ULT, shouldn't it check whether the constant operand is maxVal + 1 instead of maxVal? Otherwise, the result will be incorrect for a code like this:

if (a * b < 0xffffffff)

...
sepavloff added inline comments.Mar 9 2014, 11:30 PM
lib/Transforms/InstCombine/InstCombineCompares.cpp
2122

Yes, you are right. In fact this is one more pattern of test for overflow at multiplication. Thank you!

sepavloff updated this revision to Unknown Object (????).Mar 9 2014, 11:38 PM

Fixed pattern recognition

Pattern recognition if fixed for ult comparison. Also added comparisons against MAX+1 value.
Thanks to Akira Hatanaka!

sepavloff updated this revision to Unknown Object (????).Mar 16 2014, 10:18 AM

Updated patch to align it with recent changes in value iterators.

erikjv added a comment.Apr 1 2014, 7:40 AM

I also did a patch for PR4917, but yours looks more complete. I have some different tests, and I'll see how they compare against this. Will probably do that tomorrow (CEST).

Nitpick: I applied this patch on top of r205314, and I get the following warning:

/Users/erik/dev/clang-llvm/llvm-git/lib/Transforms/InstCombine/InstCombineCompares.cpp:2204:9: warning: ignoring return value of function declared with

warn_unused_result attribute [-Wunused-result]
  Mask.trunc(MulWidth);
  ^~~~~~~~~~ ~~~~~~~~

Yes, good catch. Must be:

Mask = Mask.trunc(MulWidth);

Thanks!

2014-04-01 21:40 GMT+07:00 Erik Verbruggen <erik.verbruggen@me.com>:

I also did a patch for PR4917, but yours looks more complete. I have

some different tests, and I'll see how they compare against this. Will
probably do that tomorrow (CEST).

Nitpick: I applied this patch on top of r205314, and I get the following

warning:

/Users/erik/dev/clang-llvm/llvm-git/lib/Transforms/InstCombine/InstCombineCompares.cpp:2204:9:
warning: ignoring return value of function declared with

warn_unused_result attribute [-Wunused-result]
  Mask.trunc(MulWidth);
  ^~~~~~~~~~ ~~~~~~~~

http://llvm-reviews.chandlerc.com/D2814

erikjv added a comment.Apr 6 2014, 6:32 AM

Could you rename the method to ProcessUMulZExtIdiom? The ProcessUAddIdiom handles a different case, and I have a patch that does the same for UMul.

Otherwise, LGTM, but bkramer has the final say.

As a follow-up, are you interested in doing the same for a signed sub and mul? (Add is already handled.) If not, I can do that.

sepavloff updated this revision to Unknown Object (????).Apr 6 2014, 9:57 PM

Updated patch.

Fixed mask calculation, thanks to Erik Verbruggen.
Renamed processing function.

2014-04-06 20:32 GMT+07:00 Erik Verbruggen <erik.verbruggen@me.com>:

Could you rename the method to ProcessUMulZExtIdiom? The

ProcessUAddIdiom handles a different case, and I have a patch that does the
same for UMul.

Otherwise, LGTM, but bkramer has the final say.

Thank you for review. I updated fix in phabricator. Waiting for bkramer's
word.

As a follow-up, are you interested in doing the same for a signed sub

and mul? (Add is already handled.) If not, I can do that.

Yes, please do that. I took these old problem in hope I wouldn't interfere
with anybody. I am sorry I hindered you.

http://reviews.llvm.org/D2814

Been really busy over the last couple of weeks, sorry for the latency. Here are some preliminary comments.

lib/Transforms/InstCombine/InstCombineCompares.cpp
2074

Not sure why you have this code path in here. An and with a constant on the LHS should've been canonicalized already before instcombine gets here.

You also have to be really careful when modifying instructions like this if you don't want to confuse the rest of instcombine.

2097

You can use dyn_cast<TruncInst> directly

2109

if chains like this can be represented with match() in a much clearer way.

2190–2210

This feels like an awful lot of code for this. Can't you just RAUW the value and have instcombine clean up after you?

3088

zext only works on integers no need for an extra check.

sepavloff updated this revision to Unknown Object (????).Apr 9 2014, 9:40 AM

Patch updated according to reviewer's notes.

sepavloff updated this revision to Unknown Object (????).Apr 9 2014, 9:58 AM

Added missed changes.

Thank you for review!

lib/Transforms/InstCombine/InstCombineCompares.cpp
2074

Removed this code.

2097

Overlooked this opportunity. Fixed.

2109

Changed this piece of code using match().

2190–2210

This code not only RAUW new value, it also adapt the value using ZExt, because new multiplication result is short, but users still wait long value, although high bits are ignored.

Some more review comments. I think you're good to commit when those are fixed.

lib/Transforms/InstCombine/InstCombineCompares.cpp
2071

"const APInt &" would save a copy.

2130

MulWidth can be >= 64. would be better to use APInt arithmetic.

Thank you for review!

2014-04-12 20:29 GMT+07:00 Benjamin Kramer <benny.kra@gmail.com>:

Some more review comments. I think you're good to commit when those are

fixed.

Comment at: lib/Transforms/InstCombine/InstCombineCompares.cpp:2129
@@ +2128,3 @@
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) {
+ APInt MaxVal(CI->getBitWidth(), 1ULL << MulWidth);

+ if (MaxVal.eq(CI->getValue()))

MulWidth can be >= 64. would be better to use APInt arithmetic.

Comment at: lib/Transforms/InstCombine/InstCombineCompares.cpp:2070
@@ +2069,3 @@
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
+ APInt CVal = CI->getValue();

+ if (CVal.getBitWidth() - CVal.countLeadingZeros() > MulWidth)

"const APInt &" would save a copy.

http://reviews.llvm.org/D2814

bkramer accepted this revision.Apr 22 2014, 10:05 AM
bkramer edited edge metadata.
This revision is now accepted and ready to land.Apr 22 2014, 10:05 AM
bkramer closed this revision.Apr 22 2014, 10:05 AM

This was committed in rL206137.