This is an archive of the discontinued LLVM Phabricator instance.

Strength reduce intrinsics with overflow into regular arithmetic operations if possible.

Authored by eeckstein on Dec 2 2014, 5:08 AM.



Some intrinsics, like s/uadd.with.overflow and umul.with.overflow, are already strength reduced.
This change adds other arithmetic intrinsics: s/usub.with.overflow, smul.with.overflow.
It completes the work on PR20194.

Beside that, I did also a refactoring: I extracted the creation of the resulting struct in to a separate function CreateOverflowResult().

Diff Detail

Event Timeline

eeckstein updated this revision to Diff 16805.Dec 2 2014, 5:08 AM
eeckstein retitled this revision from to Strength reduce intrinsics with overflow into regular arithmetic operations if possible..
eeckstein updated this object.
eeckstein edited the test plan for this revision. (Show Details)
eeckstein added a reviewer: bkramer.
eeckstein added a subscriber: Unknown Object (MLST).
reames added a subscriber: reames.Dec 2 2014, 5:39 PM

In the future, please split your changes into the smallest chunks you can. In this case, you've got three pieces:

  • The refactoring to draw out the factory function - LGTM
  • The signed and unsigned add cases with existing functions - LGTM
  • The signed multiplication case with a new helper function - Needs a second opinion. I don't spot anything obviously wrong, but I don't trust my own reasoning around overflow. I suspect you could also use this helper function in the normal signed mul case as well.

If you want to split it for submission and only hold the last feel free.


Nit: CreateOverflowResultTuple or CreateOverflowTuple

extremely minor, feel free to ignore if you disagree


Brief comment here would be good. You appear to be using the fact that a N bit number multiplied by a M bit number can yield a maximum of an N+M+1 bit number right?


General comment: Doing refactorings in separate changes from semantic changes makes it much easier and faster to review. Strongly, strongly preferred.


This change is clearly fine.

As a general point, it feels like this code could be factored to share a lot more of the logic from the normal arithmetic cases. However, if you do that, it should be a separate change.


This change is the one I'm not entirely sure of - due to the implementation of the helper function - and would like a second opinion on.

nadav added a subscriber: nadav.Dec 5 2014, 8:40 AM

Everything except for the function WillNotOverflowSignedMul looks great. I also agree with Philip that the refactoring should go in as a separate patch. The first part of WillNotOverflowSignedMul looks correct. The second part (SignBits == BitWidth + 1) is more complex and I prefer that someone else would take a look. I believe that Michael Gottesman is a good candidate for reviewing this part of the code.

eeckstein updated this revision to Diff 17148.Dec 11 2014, 12:08 AM
eeckstein added reviewers: reames, gottesmm.

I did a split of the change:
I committed the refactoring in r224006.

This updated diff is the remaining part: the strength reduction for sub/mul.

gottesmm edited edge metadata.Dec 14 2014, 9:10 PM

I would comment this a little differently. I think it is good to have the Hacker's Delight mention, but IIRC LLVM has some specific rules about this. I would just ask on the list or irc. The actual implementation looks fine to me (it is exactly the same as hacker's delight).


I would put the comment below about Hacker's delight up here and add a quick high level explanation of what you are doing.


Make sure to mention that underestimating the number of sign bits gives you a more conservative answer so the fact that we are underestimating can not cause us to get the wrong answer.


You should add why it is interesting that the result is n+m significant bits. Otherwise the line does not add anything.


There are 2x ambiguous cases. I would say what they actually are. Also you should mention that we are not handling the second case.

I would also specify that you are only handling a part of the first ambiguous case that can be known easily via the information at hand pi.e. that there is a low likelihood that we will have enough information to check the product, but we *can* check the sign = )].


I would remove this if you do what I suggested with the comment above.

eeckstein updated this revision to Diff 17272.Dec 15 2014, 2:55 AM
eeckstein edited edge metadata.


I updated the comments.

I think it is good to have the Hacker's Delight mention, but IIRC LLVM has some specific rules about this.

I changed it to the style of other references in the llvm sources.

gottesmm accepted this revision.Dec 16 2014, 4:21 PM
gottesmm edited edge metadata.


This revision is now accepted and ready to land.Dec 16 2014, 4:21 PM
eeckstein closed this revision.Dec 16 2014, 11:30 PM

committed in r224417