Page MenuHomePhabricator
Differential D141875

[InstCombine] Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1), (shl y, C1))
ClosedPublic
Actions

Authored by goldstein.w.n on Jan 16 2023, 3:21 PM.

Details

Reviewers
nikic
majnemer
spatel
Commits
rGc17ccced4b0b: Recommit "Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 +…
rGedd80befeeb9: Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1), (shl y…
Summary

This is just expanding the existing pattern that exists for AND/XOR/OR
and gets a bit more parallelism in from the instruction sequence.

Alive2:
Add - https://alive2.llvm.org/ce/z/dSmPkV
Sub1 - https://alive2.llvm.org/ce/z/6rpi5V
Sub2 - https://alive2.llvm.org/ce/z/UfYeUd

Diff Detail

Unit TestsFailed
View All

TimeTest
60,530 msx64 debian > Clang.CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/non-overloaded::vloxseg.c
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/clang -cc1 -internal-isystem /var/lib/buildkite-agent/builds/llvm-project/build/lib/clang/16/include -nostdsysteminc -triple riscv64 -target-feature +v -target-feature +zfh -target-feature +experimental-zvfh -disable-O0-optnone -emit-llvm /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/non-overloaded/vloxseg.c -o - | /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -S -passes=mem2reg | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefix=CHECK-RV64 /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/non-overloaded/vloxseg.c
60,470 msx64 debian > Clang.CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/non-overloaded::vluxseg.c
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/clang -cc1 -internal-isystem /var/lib/buildkite-agent/builds/llvm-project/build/lib/clang/16/include -nostdsysteminc -triple riscv64 -target-feature +v -target-feature +zfh -target-feature +experimental-zvfh -disable-O0-optnone -emit-llvm /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/non-overloaded/vluxseg.c -o - | /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -S -passes=mem2reg | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefix=CHECK-RV64 /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/non-overloaded/vluxseg.c
60,760 msx64 debian > Clang.CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/overloaded::vloxseg.c
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/clang -cc1 -internal-isystem /var/lib/buildkite-agent/builds/llvm-project/build/lib/clang/16/include -nostdsysteminc -triple riscv64 -target-feature +v -target-feature +zfh -target-feature +experimental-zvfh -disable-O0-optnone -emit-llvm /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/overloaded/vloxseg.c -o - | /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -S -passes=mem2reg | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefix=CHECK-RV64 /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/overloaded/vloxseg.c
60,540 msx64 debian > Clang.CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/overloaded::vluxseg.c
Script: -- : 'RUN: at line 3'; /var/lib/buildkite-agent/builds/llvm-project/build/bin/clang -cc1 -internal-isystem /var/lib/buildkite-agent/builds/llvm-project/build/lib/clang/16/include -nostdsysteminc -triple riscv64 -target-feature +v -target-feature +zfh -target-feature +experimental-zvfh -disable-O0-optnone -emit-llvm /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/overloaded/vluxseg.c -o - | /var/lib/buildkite-agent/builds/llvm-project/build/bin/opt -S -passes=mem2reg | /var/lib/buildkite-agent/builds/llvm-project/build/bin/FileCheck --check-prefix=CHECK-RV64 /var/lib/buildkite-agent/builds/llvm-project/clang/test/CodeGen/RISCV/rvv-intrinsics-autogenerated/policy/overloaded/vluxseg.c

Event Timeline

goldstein.w.n created this revision.Jan 16 2023, 3:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 16 2023, 3:21 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
goldstein.w.n requested review of this revision.Jan 16 2023, 3:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 16 2023, 3:21 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B208115: Diff 489642.Jan 16 2023, 3:22 PM
goldstein.w.n added a parent revision: D141874: [InstCombine] Add tests for reoredering (shift (add (shift x, C0), y), C1); NFC.Jan 16 2023, 3:22 PM
goldstein.w.n added reviewers: nikic, majnemer.
Herald added a subscriber: StephenFan. · View Herald TranscriptJan 16 2023, 3:23 PM
nikic added a reviewer: spatel.Jan 17 2023, 5:31 AM
spatel added a comment.Jan 17 2023, 6:13 AM

Subtract should be handled as well as add?

goldstein.w.n added a comment.Jan 17 2023, 9:24 AM
In D141875#4058818, @spatel wrote:

Subtract should be handled as well as add?

Yes, I'll update:
https://alive2.llvm.org/ce/z/4TVEIg

goldstein.w.n updated this revision to Diff 489876.Jan 17 2023, 10:22 AM

Add support for sub + update commit message

goldstein.w.n retitled this revision from [InstCombine] Reorder (shl (add (shl x, C0), y), C1) -> (add (shl x, C0 + C1), (shl y, C1)) to [InstCombine] Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1), (shl y, C1)).Jan 17 2023, 10:23 AM
goldstein.w.n edited the summary of this revision. (Show Details)
In D141875#4058818, @spatel wrote:

Subtract should be handled as well as add?

Done.

goldstein.w.n edited the summary of this revision. (Show Details)Jan 17 2023, 10:25 AM
Harbormaster completed remote builds in B208287: Diff 489876.Jan 17 2023, 11:35 AM
goldstein.w.n added a comment.Jan 26 2023, 5:36 PM

ping.

spatel added inline comments.Jan 27 2023, 11:12 AM
llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
325

or add -> or add/sub

328

typo (it was already there but disguised) - "a a"

329

This function name is too specific now since we are not limited to logic ops. Not sure if there's a compact description for the set of possibilities. If not, just go with foldShiftOfShiftedBinOp().

359–362

This was strangely matched, so I reduced it:
c2ab7e2abd834d4ef7b0f277

It shouldn't change anything functionally here, but you may need to update/rebase to patch cleanly.

367

"Reorder" doesn't seem like the right description. I'd use the more literal "FirstShiftIsOp1" or something like that.

spatel mentioned this in D141874: [InstCombine] Add tests for reoredering (shift (add (shift x, C0), y), C1); NFC.Jan 27 2023, 11:20 AM
goldstein.w.n updated this revision to Diff 492863.Jan 27 2023, 11:36 AM
goldstein.w.n marked 5 inline comments as done.

Rebase, change func name, change reorder name, fix comments

spatel accepted this revision.Jan 27 2023, 11:47 AM

LGTM

This revision is now accepted and ready to land.Jan 27 2023, 11:47 AM
Harbormaster completed remote builds in B210446: Diff 492863.Jan 27 2023, 1:42 PM
Closed by commit rGedd80befeeb9: Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1), (shl y… (authored by goldstein.w.n). · Explain WhyJan 27 2023, 3:50 PM
This revision was automatically updated to reflect the committed changes.
goldstein.w.n added a commit: rGedd80befeeb9: Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1), (shl y….
goldstein.w.n added a reverting change: rG423bcf89f13f: Revert "Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 + C1)….Jan 27 2023, 4:45 PM
goldstein.w.n added a comment.Jan 27 2023, 4:48 PM

Either this or D140850 cause the failure: https://lab.llvm.org/buildbot/#/builders/183/builds/10447

Going to revert while I look into it.

goldstein.w.n mentioned this in D140850: [InstCombine] Add optimizations for icmp eq/ne (mul(X, Y), 0).Jan 27 2023, 5:20 PM
spatel added a comment.Jan 27 2023, 5:21 PM
In D141875#4087595, @goldstein.w.n wrote:

Either this or D140850 cause the failure: https://lab.llvm.org/buildbot/#/builders/183/builds/10447

Going to revert while I look into it.

If that was the only builder that failed, I'd try again. It passed on the next try (before you reverted!):
https://lab.llvm.org/buildbot/#/builders/183
Sometimes buildbots just fail inexplicably. :)

goldstein.w.n added a comment.EditedJan 27 2023, 5:30 PM
In D141875#4087655, @spatel wrote:
In D141875#4087595, @goldstein.w.n wrote:

Either this or D140850 cause the failure: https://lab.llvm.org/buildbot/#/builders/183/builds/10447

Going to revert while I look into it.

If that was the only builder that failed, I'd try again. It passed on the next try (before you reverted!):
https://lab.llvm.org/buildbot/#/builders/183
Sometimes buildbots just fail inexplicably. :)

Yeah, also unable to reproduce locally. Coming to conclusion its unrelated, cest la vie.
For recommit should I just apply re-apply the patches and prefix with "Recommit"/explain it was a false positive?

Also thanks for taking a look :)

spatel added a comment.Jan 27 2023, 6:16 PM
In D141875#4087663, @goldstein.w.n wrote:

Yeah, also unable to reproduce locally. Coming to conclusion its unrelated, cest la vie.
For recommit should I just apply re-apply the patches and prefix with "Recommit"/explain it was a false positive?

That should be fine - I usually just append a "(2nd try)" on the patch title, add a short explanation statement, then the original commit message.

goldstein.w.n added a commit: rGc17ccced4b0b: Recommit "Reorder (shl (add/sub (shl x, C0), y), C1) -> (add/sub (shl x, C0 +….Jan 27 2023, 6:39 PM

Revision Contents
Changeset List

PathSize
llvm/
lib/
Transforms/
InstCombine/
43 lines
test/
Transforms/
InstCombine/
42 lines

Diff 489876

View Options

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Loading...
View Options

llvm/test/Transforms/InstCombine/shift-logic.ll

Loading...