Page MenuHomePhabricator

[InstCombine] transform multiplication overflow check written as a > (UINT_MAX /u b) to umul.with.overflow
AbandonedPublic

Authored by regehr on May 17 2016, 6:16 AM.

Details

Summary

there aren't a lot of good ways to express a portable overflow check for a multiply in conformant C. here's one way that people do it:

a > (UINT_MAX /u b)

this patch teaches instcombine to turn this back into a umul.with.overflow

Diff Detail

Event Timeline

regehr updated this revision to Diff 57469.May 17 2016, 6:16 AM
regehr retitled this revision from to [InstCombine] transform multiplication overflow check written as a > (UINT_MAX /u b) to umul.with.overflow.
regehr updated this object.
regehr added reviewers: spatel, majnemer.
majnemer edited edge metadata.May 17 2016, 10:59 AM

@sanjoy, you dealt with this sort of canonicalization before. What are your thoughts? Would we want this is InstCombine or CGP? umul_with_overflow may be more canonical because it can be speculated...

lib/Transforms/InstCombine/InstCombineCompares.cpp
3253–3255

This might not be a canonical transform if the division has multiple users.

sanjoy edited edge metadata.May 17 2016, 11:42 AM

The conclusions / guidelines decided from the earlier work were

  1. The optimizer should not introduce these intrinsics early in the pipeline, since there are passes that don't understand them yet.
  2. CGP should do a best-effort replacement of arithmetic with overflow intrinsics (i.e. this change should live in CGP).
  3. If the programmer really would have liked the codegen to use overflow bits in the CPU flags, then she need to use __builtin_umull_overflow etc. directly.

@regehr is there some specific reason it helps to canonicalize like this?

Hi guys, I don't know the best place for this-- just wanted to implement it since Rich Felker, author of Musl libc, was complaining that the transformation is missing. If this isn't the right place I'm happy to close this out.

regehr abandoned this revision.May 17 2016, 12:11 PM

Please upload with the full context