This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fix buggy `(mul X, Y)` -> `(shl X, Log2(Y))` transform PR62175
ClosedPublic

Authored by goldstein.w.n on Apr 18 2023, 12:34 AM.

Details

Summary

Bug was because we recognized patterns like (shl 4, Z) as a power of
2 we could take Log2 of (2 + Z), but doing (shl X, (2 + Z)) can
cause a poison shift.

https://alive2.llvm.org/ce/z/yuJm_k

The fix is to verify that Log2(Y) will be a non-poisonous shift
amount. We can do this with:

`nsw` flag:
    - https://alive2.llvm.org/ce/z/yyyJBr
    - https://alive2.llvm.org/ce/z/YgubD_
`nuw` flag:
    - https://alive2.llvm.org/ce/z/-4mpyV
    - https://alive2.llvm.org/ce/z/a6ik6r
Prove `Y != 0`:
    - https://alive2.llvm.org/ce/z/ced4su
    - https://alive2.llvm.org/ce/z/X-JJHb

Diff Detail

Event Timeline

goldstein.w.n created this revision.Apr 18 2023, 12:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 18 2023, 12:34 AM
goldstein.w.n requested review of this revision.Apr 18 2023, 12:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 18 2023, 12:34 AM
nikic added inline comments.Apr 18 2023, 12:58 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
189

Replace RequireNoOverflow with an AssumeNonZero flag. This is what justifies it for division.

1227

Don't we always infer nuw for shl of one?

goldstein.w.n marked 2 inline comments as done.

RequireNoOverflow -> AssumeNonZero + just use nuw for 1 << shl

nikic added inline comments.Apr 18 2023, 12:22 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1220–1226

Would be a bit cleaner imho.

1252

This isn't right: The result being non-zero doesn't imply the arguments being non-zero here, see https://alive2.llvm.org/ce/z/AtZmi_. For the sake of simplicity, just always pass AssumeNonZero=false here.

goldstein.w.n marked an inline comment as done.

Fix bug in umin/umax case

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1252

This isn't right: The result being non-zero doesn't imply the arguments being non-zero here, see https://alive2.llvm.org/ce/z/AtZmi_. For the sake of simplicity, just always pass AssumeNonZero=false here.

Good catch. Thats been buggy since llvm15: https://godbolt.org/z/ehen9hz6G
We probably need to backport?

Should I do the following so backporting is easier?

  1. Revert D146347
  2. Add AssumeNonZero with false in this umin/umax case
  3. Repost D146347 with AssumeNonZero changes?
goldstein.w.n added inline comments.Apr 18 2023, 1:10 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1252

This isn't right: The result being non-zero doesn't imply the arguments being non-zero here, see https://alive2.llvm.org/ce/z/AtZmi_. For the sake of simplicity, just always pass AssumeNonZero=false here.

Good catch. Thats been buggy since llvm15: https://godbolt.org/z/ehen9hz6G
We probably need to backport?

Should I do the following so backporting is easier?

  1. Revert D146347
  2. Add AssumeNonZero with false in this umin/umax case
  3. Repost D146347 with AssumeNonZero changes?

The rationale being then the patch for Step 2 can just be backported w.o any conflicts.

nikic accepted this revision.Apr 18 2023, 1:17 PM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1252

No strong opinion either way. The conflict resolution here looks pretty trivial.

This revision is now accepted and ready to land.Apr 18 2023, 1:17 PM
goldstein.w.n added inline comments.Apr 18 2023, 1:30 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1252

No strong opinion either way. The conflict resolution here looks pretty trivial.

Okay, I'll push as is.

This revision was landed with ongoing or failed builds.Apr 18 2023, 3:18 PM
This revision was automatically updated to reflect the committed changes.
goldstein.w.n added inline comments.Apr 18 2023, 3:27 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1252

This isn't right: The result being non-zero doesn't imply the arguments being non-zero here, see https://alive2.llvm.org/ce/z/AtZmi_. For the sake of simplicity, just always pass AssumeNonZero=false here.

Created issue: https://github.com/llvm/llvm-project/issues/62221