This is an archive of the discontinued LLVM Phabricator instance.

[LLVM][PASSES][InstCombine] Fix (a + a + ...) / a cases
ClosedPublic

Authored by AntonBikineev on Jan 13 2018, 8:45 PM.

Details

Summary

This quickly fixes 35709 . Please note that this is my first patch to the llvm passes infrastructure, so take it easy - I'm pretty sure I've done something dumb in this 3-liner :)

Diff Detail

Repository
rL LLVM

Event Timeline

AntonBikineev created this revision.Jan 13 2018, 8:45 PM
AntonBikineev added a reviewer: llvm-commits.
  1. Please upload patches with full context (-U999999)
  2. This needs testing coverage https://bugs.llvm.org/show_bug.cgi?id=35709#c1 notes that "(x+x+x)/x" is already handled, so maybe search for it and look how it is tested? And given that this is a generalization of that, perhaps that one is no longer needed?

Hey Roman,
Thanks for the comments.

  1. Please upload patches with full context (-U999999)

Done.

  1. This needs testing coverage https://bugs.llvm.org/show_bug.cgi?id=35709#c1 notes that "(x+x+x)/x" is already handled, so maybe search for it and look how it is tested? And given that this is a generalization of that, perhaps that one is no longer needed?

The "(x+x+x)/x" case is handled because "(x+x+x)" gets turned into "mul %x, 3" and then another simplification "(x * y) / x -> y" takes place. Things like "x+x" (with power-of-2 number of terms) in turn, get simplified into "shl %x, constant". So it's not a generalization, but a particular case.

Hey Roman,
Thanks for the comments.

  1. Please upload patches with full context (-U999999)

Done.

  1. This needs testing coverage https://bugs.llvm.org/show_bug.cgi?id=35709#c1 notes that "(x+x+x)/x" is already handled, so maybe search for it and look how it is tested? And given that this is a generalization of that, perhaps that one is no longer needed?

The "(x+x+x)/x" case is handled because "(x+x+x)" gets turned into "mul %x, 3" and then another simplification "(x * y) / x -> y" takes place. Things like "x+x" (with power-of-2 number of terms) in turn, get simplified into "shl %x, constant". So it's not a generalization, but a particular case.

Ah, makes sense. https://godbolt.org/g/qyDUQv
Now, not that i know what i'm talking about, but Alive does not like those testcases as-is:
https://rise4fun.com/Alive/bvYn
But if we look at the IR in godbolt, we can note that it's "shl nsw i32", and then it likes it:
https://rise4fun.com/Alive/23e
So i wonder if that "no signed wrap" needs to be matched too.

Roman,

As the description shows, it's absolutely right. Thanks for pointing this out.

Thank you for working on this!
Looks sane to me, but someone who actually knows this should review.

test/Transforms/InstSimplify/reassociate.ll
166 ↗(On Diff #129826)

Does this need negative tests, with missing nsw?

lebedev.ri set the repository for this revision to rL LLVM.
majnemer added inline comments.Jan 17 2018, 3:00 PM
lib/Analysis/InstructionSimplify.cpp
997–998 ↗(On Diff #129826)

Instead of using m_Value(X) and X == Op1, just use m_Specific(Op1)

@lebedev.ri
My pleasure. Thanks for reviewing this!
@majnemer
Done.

spatel added inline comments.Jan 18 2018, 11:10 AM
test/Transforms/InstSimplify/reassociate.ll
161 ↗(On Diff #130338)

The 'y' param is unused here and the other tests. Please remove.
Make one of the positive tests use a vector type, so we know case that works correctly too.

spatel added a comment.EditedJan 18 2018, 11:37 AM

This patch raises a question that I don't know the answer to. We're missing the more general fold (shift amount is not constant) in instcombine:

Name: shl_div
%a = shl nsw i8 %x, %y
%r = sdiv i8 %a, %x
  =>
%r = shl i8 1, %y

https://rise4fun.com/Alive/7l

You can't do that here in instsimplify because we don't create new instructions here.

Is it better to just add that to instcombine and forego adding the special-case with constant shift amount to instsimplify?

Is it better to just add that to instcombine and forego adding the special-case with constant shift amount to instsimplify?

Yes, I think so. Thanks for indicating this.

This looks right, but see inline comments for some small improvements. Do you have commit access?

Note: we're missing the related 'rem' transforms for these patterns...but I think they would go back in instsimplify:
https://rise4fun.com/Alive/wqHz

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1009 ↗(On Diff #130529)

No need to initialize this; we don't touch 'Y' if the matches fail.
Feel free to fix the similar line above here as a clean-up commit.

1010 ↗(On Diff #130529)

Probably best not to speculatively create this constant. I think you can move this into the 'Create' lines below without violating the 80-column limit. :)

test/Transforms/InstCombine/div-shift.ll
117–119 ↗(On Diff #130529)

I always suggest using the script at utils/update_test_checks.py to auto-generate the check lines. The regex that it would use here are more resilient to underlying cosmetic changes in instcombine (someone might want to give the values special names, and then this test would fail to match).

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

AntonBikineev added a comment.EditedJan 19 2018, 2:16 PM

This looks right, but see inline comments for some small improvements. Do you have commit access?

No, unfortunately.

No need to initialize this; we don't touch 'Y' if the matches fail.

In this particular case it's correct - we eliminate the extra store, but on the other hand IMHO it promotes a good code style by not accidentally reading uninitialized data.

Probably best not to speculatively create this constant. I think you can move this into the 'Create' lines below without violating the 80-column limit. :)

But then we would either need to duplicate this line in both statements or use an extra check... I don't know if it's better :)

This looks right, but see inline comments for some small improvements. Do you have commit access?

No, unfortunately.

No problem; I can commit on your behalf when the patch is complete. I can check in the tests first if you agree with my explanation on that.

No need to initialize this; we don't touch 'Y' if the matches fail.

In this particular case it's correct - we eliminate the extra store, but on the other hand IMHO it promotes a good code style by not accidentally reading uninitialized data.

I think the argument goes the other way - we want to see a compiler warning if we accidentally read the variable uninitialized, so we purposely leave it uninitialized to allow that possibility.

Probably best not to speculatively create this constant. I think you can move this into the 'Create' lines below without violating the 80-column limit. :)

But then we would either need to duplicate this line in both statements or use an extra check... I don't know if it's better :)

It's correct that you'll duplicate the line, but I think that's better than potentially executing code that won't be used.

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

I've checked all the test on my machine. The only one that failed was CodeGen/Generic/dwarf-md5.ll:

error: expected string not found in input
; OBJ-5: Dir MD5 Checksum File Name

but it doesn't seem to relate to the change.

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

check all of the tests in

check<..>in == commit

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

check all of the tests in

check<..>in == commit

Right - sorry, my writing was lousy there. Let me commit the tests now to demonstrate what I was hoping for. :)

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

check all of the tests in

check<..>in == commit

Right - sorry, my writing was lousy there. Let me commit the tests now to demonstrate what I was hoping for. :)

Sure, go ahead :)

Tests committed at:
https://reviews.llvm.org/rL323043

If you rebase the patch now, we'll just see the diffs / improvements from the new fold.

spatel accepted this revision.Jan 21 2018, 7:21 AM

LGTM.

This revision is now accepted and ready to land.Jan 21 2018, 7:21 AM
This revision was automatically updated to reflect the committed changes.