Page MenuHomePhabricator

[InstSimplify] Transform X * Y % Y --> 0.
ClosedPublic

Authored by davidtgoldblatt on May 20 2021, 12:11 PM.

Diff Detail

Event Timeline

davidtgoldblatt requested review of this revision.May 20 2021, 12:11 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 20 2021, 12:11 PM

Do you have commit access? If so, please add the test file with baseline CHECK lines as a preliminary patch.

llvm/test/Transforms/InstSimplify/rem.ll
336

We should have the commuted variant of this test too. Even better if you use a vector type for that case, so we have coverage for that possibility too.

378

Similar to above - please add a commuted mul operand test for more coverage.

Add commuted and vector test cases.

davidtgoldblatt marked 2 inline comments as done.May 20 2021, 3:02 PM

I don't have commit access. Happy to split this in two and do two diffs if you'd prefer, though.

I don't have commit access. Happy to split this in two and do two diffs if you'd prefer, though.

No problem. I can commit on your behalf. To confirm - use your gmail address for author info?

Would it make sense to unify this with the related div transforms? If I'm seeing it correctly, we could also pick up this (and unsigned sibling) transform if we can generalize that block:
https://alive2.llvm.org/ce/z/AvaDGJ

define i8 @src(i8 %a, i8 %y) {
  %x = sdiv i8 %a, %y
  %mul = mul i8 %x, %y
  %mod = srem i8 %mul, %y
  ret i8 %mod
}

define i8 @tgt(i8 %x, i8 %y) {
  ret i8 0
}

Interestingly, it looks like we currently miscompile that pattern in instcombine.

No problem. I can commit on your behalf. To confirm - use your gmail address for author info?

Yep, that should be fine, thank you.

Would it make sense to unify this with the related div transforms? If I'm seeing it correctly, we could also pick up this (and unsigned sibling) transform if we can generalize that block:
https://alive2.llvm.org/ce/z/AvaDGJ

I.e. pull out the signedness checks into bool NoOverflow or something, and additionally set NoOverflow to true if the X in X * Y / Y or X * Y % Y is of the form A / Y? I think we still need to check the specific operation (to decide to reduce to X or 0), but I think it does get us some extra cases we can simplify. Happy to do so if you'd prefer, although my initial thought is that it's a little complex for a case I don't know I've seen.

No problem. I can commit on your behalf. To confirm - use your gmail address for author info?

Yep, that should be fine, thank you.

Please update and regenerate the test CHECK lines after: 3c4b79481d45

Would it make sense to unify this with the related div transforms? If I'm seeing it correctly, we could also pick up this (and unsigned sibling) transform if we can generalize that block:
https://alive2.llvm.org/ce/z/AvaDGJ

I.e. pull out the signedness checks into bool NoOverflow or something, and additionally set NoOverflow to true if the X in X * Y / Y or X * Y % Y is of the form A / Y? I think we still need to check the specific operation (to decide to reduce to X or 0), but I think it does get us some extra cases we can simplify. Happy to do so if you'd prefer, although my initial thought is that it's a little complex for a case I don't know I've seen.

That's fine - we can make that a potential follow-up. You could add a TODO comment. The related block in simplifyDiv() is at line 1055. We make the code a bit more complicated by generalizing it in simplifyDivRem(), but then we're less likely to lose a transform.

define i8 @src(i8 %a, i8 %y) {

%x = sdiv i8 %a, %y
%mul = mul i8 %x, %y
%mod = srem i8 %mul, %y
ret i8 %mod

}
Interestingly, it looks like we currently miscompile that pattern in instcombine.

For reference, that miscompile appears to be only with an undef input. We have a mul transform that creates an extra use of the numerator op, so we need to freeze it to make the transform safe.

Merge cases into simplifyDivRem

Went ahead and did the suggested unification, which was an obvious improvement
once I understood things better.

BTW, re-reading I realized I phrased that diff update poorly. I meant to say something more like "now that I understand better, it's obvious to me that you're right", not like "that thing you pointed out was obvious"; hopefully it parsed that way, and sorry if it didn't.

xbolva00 added inline comments.
llvm/lib/Analysis/InstructionSimplify.cpp
925–926

Nit: opcode as 1st arg?

Since we expanded the scope of the transform, we need a few more tests. Feel free to add to or adjust this if you want:
cb3bc9d81d

Also, we should add an Alive2 link for that general pattern to the list in the patch summary/commit message:
https://alive2.llvm.org/ce/z/AvaDGJ

davidtgoldblatt edited the summary of this revision. (Show Details)

Add (a / y) * y % y tests, make Opcode first arg, add Alive2 links to the commit message.

davidtgoldblatt marked an inline comment as done.May 24 2021, 10:16 AM
spatel accepted this revision.May 25 2021, 5:39 AM

LGTM - thanks!
Sorry if it wasn't clear - I already committed the extra tests to the main branch, so you can rebase off of that here. If you get to it first, please update here, otherwise I'll merge before landing.

This revision is now accepted and ready to land.May 25 2021, 5:39 AM
This revision was automatically updated to reflect the committed changes.

Ah, gotcha, thanks. Still learning the LLVM diff workflows.