This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombiner] Add decomposition patterns for Mul-by-Imm.
ClosedPublic

Authored by Esme on Sep 24 2020, 12:54 AM.

Details

Summary

This patch is derived from D87384.
In this patch we expand the existing decomposition of mul-by-constant to be more general by implementing 2 patterns:

mul x, (2^N + 2^M) --> (add (shl x, N), (shl x, M))
mul x, (2^N - 2^M) --> (sub (shl x, N), (shl x, M))

The conversion will be trigged if the multiplier is a big constant that the target can't use a single multiplication instruction to handle. This is controlled by the hook decomposeMulByConstant.

More over, the conversion benefits from an ILP improvement since the instructions are independent. A case with the sequence like following also gets benefit since a shift instruction is saved.

*res1 = a * 0x8800;
*res2 = a * 0x8080;

Diff Detail

Event Timeline

Esme created this revision.Sep 24 2020, 12:54 AM
Esme requested review of this revision.Sep 24 2020, 12:54 AM
Esme retitled this revision from [PowerPC] Add patterns for Mul-by-Imm in DAGCombiner. to [DAGCombiner][PowerPC] Add decomposition patterns for Mul-by-Imm..Sep 24 2020, 1:38 AM
steven.zhang retitled this revision from [DAGCombiner][PowerPC] Add decomposition patterns for Mul-by-Imm. to [DAGCombiner] Add decomposition patterns for Mul-by-Imm..Sep 24 2020, 1:44 AM
steven.zhang added reviewers: spatel, RKSimon.
RKSimon added inline comments.Sep 29 2020, 3:38 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
3648

MulC.lshrInPlace(TZeros);

llvm/lib/Target/PowerPC/PPCISelLowering.cpp
16067

Maybe better to use ConstNode->getAPIntValue().isSignedIntN() ?

Esme updated this revision to Diff 295721.Oct 1 2020, 8:02 PM

@RKSimon Thanks. Updated.

spatel added inline comments.Oct 2 2020, 7:45 AM
llvm/lib/Target/PowerPC/PPCISelLowering.cpp
16075

Just to confirm: no target besides PPC is going to see any diffs from this patch because they don't check the constant for trailing zeros yet?

(We really should implement the TODO from the DAGCombiner code comment, so every target doesn't have to duplicate this logic.)

Esme added inline comments.Oct 4 2020, 10:21 AM
llvm/lib/Target/PowerPC/PPCISelLowering.cpp
16075

Thanks for your comments. @spatel

  1. Yes, RISCV and X86 implemented the hook decomposeMulByConstant and both of them don't check the constant for trailing zeros, therefore they will never return true for these constants. So yes, this patch has no effect on targets other than PPC.
  2. I will look into the TODO after my vacation (Oct 9). :D
spatel accepted this revision.Oct 5 2020, 6:40 AM

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
3602–3604

Independent of this patch, but if you are looking at making further changes in here...that looks strange/unnecessary. The other transforms around here are using N1IsConst; why is this one different?

This revision is now accepted and ready to land.Oct 5 2020, 6:40 AM
RKSimon added inline comments.Oct 5 2020, 6:53 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
3602–3604

I think because this one has been updated to support non-uniform vectors but most of others haven't, or only match scalars or uniform/splat vectors.

This revision was automatically updated to reflect the committed changes.
MaskRay added a subscriber: MaskRay.Oct 9 2020, 6:31 PM
MaskRay added inline comments.
llvm/lib/Target/PowerPC/PPCISelLowering.cpp
16079

LONG_MAX+1 and LONG_MIN-1 are signed overflows. I fixed it in 2bd4730850cc0f3ab7bd0c51b18c0a220e480dc7

saugustine added inline comments.
llvm/lib/Target/PowerPC/PPCISelLowering.cpp
16079

undefined-behaviour sanitizer reports an error at this line when executing the test at llvm-project/llvm/test/CodeGen/PowerPC/mul-const-i64.ll

PPCISelLowering.cpp:16079:27: runtime error: signed integer overflow: 9223372036854775807 + 1 cannot be represented in type 'long'