This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold '((%x * %y) u/ %x) != %y' to '@llvm.umul.with.overflow' + overflow bit extraction
ClosedPublic

Authored by lebedev.ri on Jul 23 2019, 6:59 AM.

Details

Summary

((%x * %y) u/ %x) != %y is one of (3?) common ways to check that
some unsigned multiplication (will not) overflow.
Currently, we don't catch it. We could:

$ /repositories/alive2/build-Clang-unknown/alive -root-only ~/llvm-patch1.ll 
Processing /home/lebedevri/llvm-patch1.ll..

----------------------------------------
Name: no overflow
  %o0 = mul i4 %y, %x
  %o1 = udiv i4 %o0, %x
  %r = icmp ne i4 %o1, %y
  ret i1 %r
=>
  %n0 = umul_overflow i4 %x, %y
  %o0 = extractvalue {i4, i1} %n0, 0
  %o1 = udiv %o0, %x
  %r = extractvalue {i4, i1} %n0, 1
  ret %r

Done: 1
Optimization is correct!

----------------------------------------
Name: no overflow
  %o0 = mul i4 %y, %x
  %o1 = udiv i4 %o0, %x
  %r = icmp eq i4 %o1, %y
  ret i1 %r
=>
  %n0 = umul_overflow i4 %x, %y
  %o0 = extractvalue {i4, i1} %n0, 0
  %o1 = udiv %o0, %x
  %n1 = extractvalue {i4, i1} %n0, 1
  %r = xor %n1, -1
  ret i1 %r

Done: 1
Optimization is correct!

Diff Detail

Event Timeline

lebedev.ri created this revision.Jul 23 2019, 6:59 AM
xbolva00 added inline comments.Jul 23 2019, 7:25 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3341

Instruction *Mul = nullptr;?

3347

..remove

3378

Also add multi use check?

bool HasMultiUseMul = Mul && !Mul->hasOneUse();
if (..)

NFC, rebase, improve comments.

lebedev.ri added inline comments.Jul 23 2019, 9:12 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3347

Why i believe this is the conceptually-wrong solution:
Consider this:

void *data;
bool something = false;
if(some_check(&data, &something))
else if(another_check(&data))
else return;

if(something)
  ...

The problem is that while this may seem ok, we did zero-init something initially after all,
we then did pass it to some_check(), and it may have changed it's value.
Now, if some_check() returned false, we do another_check(),
but there we don't do anything with something.
We might intended to keep whatever we got there from some_check(),
or maybe we did not and simply forgot to re-zero-init it.
And in latter case something is essentially undefined, and we have a bug that won't be fun to debug.

Compare with:

void *data;
bool something; // if we do not init it before using MSAN will catch it.
if(some_check(&data, &something))
else if(another_check(&data))
  something = false; // yay
else return;

if(something) // all certainly good here.
  ...

Does this make sense?

3378

If we insert in place of old mul only if mul had extra uses,
then maybe this intrinsic will still be hoisted back into that
other basic block because it's loop-invariant.
Or maybe it we always place insert in place of old mul
it will get sinked into some other only basic block where it's used.

I'm honestly not sure what the best solution here is,
we just don't have enough information to make the final
(the one that won't be altered by later passes) choice here.
Either choice that passes -verify is good.

Consistently placing it in place of the old mul seemed least arbitrary to me.

Maybe others have some other ideas?

lebedev.ri added inline comments.Jul 23 2019, 10:27 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3378

Maybe others have some other ideas?

Err, what i meant to say is, maybe there is some consistent justification that points
to some particular location being the correct one to insert to?

nikic added inline comments.Jul 27 2019, 1:15 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3378

I don't think it really matters either way, but my preference here would be (for the one-use case) to insert everything together, both because that is the default behavior (what we would do if we were matching for one-use in the first place and had no special handling) and because that makes the condition here and below consistent.

lebedev.ri marked 3 inline comments as done.

Insert everything together if no mul/mul was oneuse.

nikic accepted this revision.Jul 28 2019, 2:06 AM

LGTM

This revision is now accepted and ready to land.Jul 28 2019, 2:06 AM

Thank you for the review.

Rebased, NFC.