[RISCV] Optimize (add (shl x, c0), c1)

[benshi001]

Summary

Transform (add (shl x, c0), c1) ->
          (add (shl (add x, c1>>c0), c0), c1-(c1>>c0<<c0)),
if c1>>c0 and c1-(c1>>c0<<c0) are simm12, while c1 is not.

Or transform (add (shl x, c0), c1) ->
             (shl (add x, c1>>c0), c0),
if c1-(c1>>c0<<c0) is zero, and c1>>c0 is simm12 while c1 is not.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

6474 ↗

(On Diff #377088)

I think you can drop this if, getNode will see the constant is 0 and not produce an ADD node.

6482 ↗

(On Diff #377088)

This comment is already above transformAddImmShlImm, we don't need to repeat it.

6491 ↗

(On Diff #377088)

Just drop this comment. It's already above transformAddImmMulImm.

[benshi001]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

6454 ↗

(On Diff #379574)

This comment also repeated before the definition of transformAddShlImm, and should also be dropped.

[craig.topper]

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

6468 ↗

(On Diff #379586)

I think you need to abort if C0 is greater than VT.getSizeInBits() - 1.

[benshi001]

ping ... Any concerns about this patch ?

[asb]

I'm getting a warning when building this (with clang 12.0.1):

/home/asb/llvm-project/llvm/lib/Target/RISCV/RISCVISelLowering.cpp:6490:20: warning: comparison of integers of different signs: 'int64_t' (aka 'long') and 'unsigned long' [-Wsign-compare]
  if (C0 < 1 || C0 > VT.getSizeInBits() - 1 || isInt<12>(C1) ||

[benshi001]

In D111117#3103171, @asb wrote:

I'm getting a warning when building this (with clang 12.0.1):

/home/asb/llvm-project/llvm/lib/Target/RISCV/RISCVISelLowering.cpp:6490:20: warning: comparison of integers of different signs: 'int64_t' (aka 'long') and 'unsigned long' [-Wsign-compare]
  if (C0 < 1 || C0 > VT.getSizeInBits() - 1 || isInt<12>(C1) ||

I have fixed in the newest patch.

[asb]

I'm seeing some code size regressions on this patch - specifically, cases where a reg-reg add is replaced with an addi -256 (which isn't compressible). e.g. 20050121-1.c from the GCC torture suite (-O1, rv32imafdc).

[benshi001]

In D111117#3111631, @asb wrote:

I'm seeing some code size regressions on this patch - specifically, cases where a reg-reg add is replaced with an addi -256 (which isn't compressible). e.g. 20050121-1.c from the GCC torture suite (-O1, rv32imafdc).

Thanks for your patient and careful test, I will made a new patch for SHL related optimization after a careful check.

llvm/test/CodeGen/RISCV/shlimm-addimm.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+;; Test that (add (shl x, c1), c2) can be transformed to
+;; (add (shl (add x, c2/c1), c1), c2%c1) or (shl (add x, c2/c1), c1)
+;; if profitable.
+
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
+; RUN:   | FileCheck -check-prefix=RV32I %s
+; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s \
+; RUN:   | FileCheck -check-prefix=RV64I %s
+
+define i32 @shl5_add1184_a(i32 %x) {
+; RV32I-LABEL: shl5_add1184_a:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    addi a0, a0, 1184
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add1184_a:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    addiw a0, a0, 1184
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 1184
+  ret i32 %tmp1
+}
+
+define signext i32 @shl5_add1184_b(i32 signext %x) {
+; RV32I-LABEL: shl5_add1184_b:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    addi a0, a0, 1184
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add1184_b:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    addiw a0, a0, 1184
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 1184
+  ret i32 %tmp1
+}
+
+define i64 @shl5_add1184_c(i64 %x) {
+; RV32I-LABEL: shl5_add1184_c:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    srli a2, a0, 27
+; RV32I-NEXT:    slli a1, a1, 5
+; RV32I-NEXT:    or a1, a1, a2
+; RV32I-NEXT:    slli a2, a0, 5
+; RV32I-NEXT:    addi a0, a2, 1184
+; RV32I-NEXT:    sltu a2, a0, a2
+; RV32I-NEXT:    add a1, a1, a2
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add1184_c:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    addi a0, a0, 1184
+; RV64I-NEXT:    ret
+  %tmp0 = shl i64 %x, 5
+  %tmp1 = add i64 %tmp0, 1184
+  ret i64 %tmp1
+}
+
+define i32 @shl5_add101024_a(i32 %x) {
+; RV32I-LABEL: shl5_add101024_a:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 25
+; RV32I-NEXT:    addi a1, a1, -1376
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add101024_a:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 25
+; RV64I-NEXT:    addiw a1, a1, -1376
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 101024
+  ret i32 %tmp1
+}
+
+define signext i32 @shl5_add101024_b(i32 signext %x) {
+; RV32I-LABEL: shl5_add101024_b:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 25
+; RV32I-NEXT:    addi a1, a1, -1376
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add101024_b:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 25
+; RV64I-NEXT:    addiw a1, a1, -1376
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 101024
+  ret i32 %tmp1
+}
+
+define i64 @shl5_add101024_c(i64 %x) {
+; RV32I-LABEL: shl5_add101024_c:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    srli a2, a0, 27
+; RV32I-NEXT:    slli a1, a1, 5
+; RV32I-NEXT:    or a1, a1, a2
+; RV32I-NEXT:    slli a2, a0, 5
+; RV32I-NEXT:    lui a0, 25
+; RV32I-NEXT:    addi a0, a0, -1376
+; RV32I-NEXT:    add a0, a2, a0
+; RV32I-NEXT:    sltu a2, a0, a2
+; RV32I-NEXT:    add a1, a1, a2
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add101024_c:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    lui a1, 25
+; RV64I-NEXT:    addiw a1, a1, -1376
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i64 %x, 5
+  %tmp1 = add i64 %tmp0, 101024
+  ret i64 %tmp1
+}
+
+define i32 @shl5_add47968_a(i32 %x) {
+; RV32I-LABEL: shl5_add47968_a:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 12
+; RV32I-NEXT:    addi a1, a1, -1184
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add47968_a:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 12
+; RV64I-NEXT:    addiw a1, a1, -1184
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 47968
+  ret i32 %tmp1
+}
+
+define signext i32 @shl5_add47968_b(i32 signext %x) {
+; RV32I-LABEL: shl5_add47968_b:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 12
+; RV32I-NEXT:    addi a1, a1, -1184
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add47968_b:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 12
+; RV64I-NEXT:    addiw a1, a1, -1184
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 47968
+  ret i32 %tmp1
+}
+
+define i64 @shl5_add47968_c(i64 %x) {
+; RV32I-LABEL: shl5_add47968_c:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    srli a2, a0, 27
+; RV32I-NEXT:    slli a1, a1, 5
+; RV32I-NEXT:    or a1, a1, a2
+; RV32I-NEXT:    slli a2, a0, 5
+; RV32I-NEXT:    lui a0, 12
+; RV32I-NEXT:    addi a0, a0, -1184
+; RV32I-NEXT:    add a0, a2, a0
+; RV32I-NEXT:    sltu a2, a0, a2
+; RV32I-NEXT:    add a1, a1, a2
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add47968_c:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    lui a1, 12
+; RV64I-NEXT:    addiw a1, a1, -1184
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i64 %x, 5
+  %tmp1 = add i64 %tmp0, 47968
+  ret i64 %tmp1
+}
+
+define i32 @shl5_add47969_a(i32 %x) {
+; RV32I-LABEL: shl5_add47969_a:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 12
+; RV32I-NEXT:    addi a1, a1, -1183
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add47969_a:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 12
+; RV64I-NEXT:    addiw a1, a1, -1183
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 47969
+  ret i32 %tmp1
+}
+
+define signext i32 @shl5_add47969_b(i32 signext %x) {
+; RV32I-LABEL: shl5_add47969_b:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 12
+; RV32I-NEXT:    addi a1, a1, -1183
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add47969_b:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 12
+; RV64I-NEXT:    addiw a1, a1, -1183
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, 47969
+  ret i32 %tmp1
+}
+
+define i64 @shl5_add47969_c(i64 %x) {
+; RV32I-LABEL: shl5_add47969_c:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    srli a2, a0, 27
+; RV32I-NEXT:    slli a1, a1, 5
+; RV32I-NEXT:    or a1, a1, a2
+; RV32I-NEXT:    slli a2, a0, 5
+; RV32I-NEXT:    lui a0, 12
+; RV32I-NEXT:    addi a0, a0, -1183
+; RV32I-NEXT:    add a0, a2, a0
+; RV32I-NEXT:    sltu a2, a0, a2
+; RV32I-NEXT:    add a1, a1, a2
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_add47969_c:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    lui a1, 12
+; RV64I-NEXT:    addiw a1, a1, -1183
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i64 %x, 5
+  %tmp1 = add i64 %tmp0, 47969
+  ret i64 %tmp1
+}
+
+define i32 @shl5_sub47968_a(i32 %x) {
+; RV32I-LABEL: shl5_sub47968_a:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 1048564
+; RV32I-NEXT:    addi a1, a1, 1184
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_sub47968_a:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 1048564
+; RV64I-NEXT:    addiw a1, a1, 1184
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, -47968
+  ret i32 %tmp1
+}
+
+define signext i32 @shl5_sub47968_b(i32 signext %x) {
+; RV32I-LABEL: shl5_sub47968_b:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 1048564
+; RV32I-NEXT:    addi a1, a1, 1184
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_sub47968_b:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 1048564
+; RV64I-NEXT:    addiw a1, a1, 1184
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, -47968
+  ret i32 %tmp1
+}
+
+define i64 @shl5_sub47968_c(i64 %x) {
+; RV32I-LABEL: shl5_sub47968_c:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    srli a2, a0, 27
+; RV32I-NEXT:    slli a1, a1, 5
+; RV32I-NEXT:    or a1, a1, a2
+; RV32I-NEXT:    slli a2, a0, 5
+; RV32I-NEXT:    lui a0, 1048564
+; RV32I-NEXT:    addi a0, a0, 1184
+; RV32I-NEXT:    add a0, a2, a0
+; RV32I-NEXT:    sltu a2, a0, a2
+; RV32I-NEXT:    add a1, a1, a2
+; RV32I-NEXT:    addi a1, a1, -1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_sub47968_c:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    lui a1, 1048564
+; RV64I-NEXT:    addiw a1, a1, 1184
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i64 %x, 5
+  %tmp1 = add i64 %tmp0, -47968
+  ret i64 %tmp1
+}
+
+define i32 @shl5_sub47969_a(i32 %x) {
+; RV32I-LABEL: shl5_sub47969_a:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 1048564
+; RV32I-NEXT:    addi a1, a1, 1183
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_sub47969_a:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 1048564
+; RV64I-NEXT:    addiw a1, a1, 1183
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, -47969
+  ret i32 %tmp1
+}
+
+define signext i32 @shl5_sub47969_b(i32 signext %x) {
+; RV32I-LABEL: shl5_sub47969_b:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    slli a0, a0, 5
+; RV32I-NEXT:    lui a1, 1048564
+; RV32I-NEXT:    addi a1, a1, 1183
+; RV32I-NEXT:    add a0, a0, a1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_sub47969_b:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slliw a0, a0, 5
+; RV64I-NEXT:    lui a1, 1048564
+; RV64I-NEXT:    addiw a1, a1, 1183
+; RV64I-NEXT:    addw a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i32 %x, 5
+  %tmp1 = add i32 %tmp0, -47969
+  ret i32 %tmp1
+}
+
+define i64 @shl5_sub47969_c(i64 %x) {
+; RV32I-LABEL: shl5_sub47969_c:
+; RV32I:       # %bb.0:
+; RV32I-NEXT:    srli a2, a0, 27
+; RV32I-NEXT:    slli a1, a1, 5
+; RV32I-NEXT:    or a1, a1, a2
+; RV32I-NEXT:    slli a2, a0, 5
+; RV32I-NEXT:    lui a0, 1048564
+; RV32I-NEXT:    addi a0, a0, 1183
+; RV32I-NEXT:    add a0, a2, a0
+; RV32I-NEXT:    sltu a2, a0, a2
+; RV32I-NEXT:    add a1, a1, a2
+; RV32I-NEXT:    addi a1, a1, -1
+; RV32I-NEXT:    ret
+;
+; RV64I-LABEL: shl5_sub47969_c:
+; RV64I:       # %bb.0:
+; RV64I-NEXT:    slli a0, a0, 5
+; RV64I-NEXT:    lui a1, 1048564
+; RV64I-NEXT:    addiw a1, a1, 1183
+; RV64I-NEXT:    add a0, a0, a1
+; RV64I-NEXT:    ret
+  %tmp0 = shl i64 %x, 5
+  %tmp1 = add i64 %tmp0, -47969
+  ret i64 %tmp1
+}