[RISCV] Materializing constants with 'rori'

[BaoshanPang]

fix format issue

[BaoshanPang]

It is not clear for me how my code failed the "pre-merge checks", can someone help to point out what's the problem? Thanks.

[craig.topper]

llvm/test/CodeGen/RISCV/imm_zbb.ll

2

Please add a test for the MC layer for the "li" alias as well since it shares the same materialization code.

8

Drop the Function Attrs comment.

9

drop dso_local, local_unnamed_addr, and #0

[craig.topper]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

146

Use unsigned instead of int

149

Can we do this for LeadingOnes == 32 too? For example 0xffffffff77ffffff. That can't use LUI+ADDIW.

154

Can this use Lo_32 and Hi_32 from MathExtras.h? Or is the signed right shift important?

[jrtc27]

Shouldn't this test just go in imm.ll?

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

148

This would be clearer written in binary (with ... for the long sequence of 1's) and x's for the interesting bits

149

Doesn't this work whenever LeadingOnes + TrailingOnes > (64 - 12) and TrailingOnes > 0 (which is currently implied by your conditions, somewhat non-obviously)? I don't see why you need LeadingOnes < 32, other than to avoid the case when the input is all 1's or all 0's and you end up trying to shift by 64, i.e. also TrailingOnes < 64.

150

Need to cast Val to uint64_t when left-shifting too otherwise it's UB; left-shifting on signed types is only defined if the LHS is non-negative and LHS * 2^RHS computed as a natural number is representable in the integral type used, i.e. you're only shifting out 0s at the top and there's at least one left over.

152

Just return true

154

With early return you can avoid the nesting

155

This is UB in a lot of cases, left shifts on signed values are perilous

157–158

Again this seems overly strict, you just need LowerLeadingOnes + UpperTrailingOnes > (64 - 12) and 0 < UpperTrailingOnes < 32?

162

Ditto

165

Just return false

[BaoshanPang]

fix issues found in review

[BaoshanPang]

@craig.topper

Thanks for helping on review.
Please help to check if there is still any issue with new version.

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

157–158

Yes, I agree we should only use "LowerLeadingOnes + UpperTrailingOnes > (64 - 12)".

For 0 < UpperTrailingOnes < 32, it seems we don't need it, as:
if UpperTrailingOnes is 0 then it is impossible to meet: LowerLeadingOnes + UpperTrailingOnes > (64 - 12)
and if UpperTrailingOnes is 32 then the 'Val' should be handled by case 1.

[jrtc27]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

149

As I said you need to take care when the input is all 1s, i.e. check say TrailingOnes < 64, otherwise you have UB due to shifting a uint64_t by 64

157–158

I don't like relying on that, it's fragile, and not obvious because nowhere does it say that's a condition. It should at least be an assertion.

Except, once you correctly handle all-ones input for the first case, i.e. don't let it match as that would cause UB in the shifts, you will end up falling through to here, and you do need to explicitly check UpperTrailingOnes < 32, otherwise this will be broken too.

[jrtc27]

In D116574#3220354, @jrtc27 wrote:

Shouldn't this test just go in imm.ll?

This is unaddressed

[BaoshanPang]

fix left issues found in review

[BaoshanPang]

@jrtc27

Thanks for helping review on this.
Please help to check if there is still any issue.

[jrtc27]

llvm/test/CodeGen/RISCV/imm.ll

11 ↗

(On Diff #397620)

You've clearly not regenerated this file, just hacked it up by hand; use the script. Also probably better to put Zbb between Zba and Zbs?

[BaoshanPang]

use update_llc_test_checks.py to generate the test case

[BaoshanPang]

llvm/test/CodeGen/RISCV/imm.ll

11 ↗

(On Diff #397620)

I wasn't sure how to use the script.

[BaoshanPang]

@jrtc27
Please help to check again. Thanks.

[craig.topper]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

341

You could return Rotate from the function instead of a bool and use 0 to mean no rotate.

And instead of having NegImm12 as an output parameter, you could use the returned Rotate amount to rotate Val left in this if block before using it in the ADDI. That way you wouldn't have two different places in extractRotateInfo rotating Val left to commute NegImm12.

llvm/test/CodeGen/RISCV/imm.ll

2330 ↗

(On Diff #397640)

Insert blank between test functions

2366 ↗

(On Diff #397640)

Add blank line

[craig.topper]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

341

Err... that should have said "compute" not "commute"

[BaoshanPang]

fix more issues

[BaoshanPang]

@craig.topper

Please help to check the code again. Thanks.

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

341

Great idea. The code is much simpler now.

[jrtc27]

llvm/test/CodeGen/RISCV/imm.ll

11 ↗

(On Diff #397620)

Did you regenerate the CHECK lines before reordering the RUN lines? Because the order doesn't match, and I suspect a subsequent regenerate will result in all the CHECK lines moving, making it hard to see actual future diffs.

[BaoshanPang]

update test case

[BaoshanPang]

llvm/test/CodeGen/RISCV/imm.ll

11 ↗

(On Diff #397620)

Ok, I regenerated the file, now the order looks correct.

[craig.topper]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

149

You can drop the curly braces

156

Drop curly braces

339

Use unsigned since the function returns unsigned

341

Add an assert that verifies isInt<12>(NegImm12).

[BaoshanPang]

revise

[BaoshanPang]

I don't understand why my change would result such error:

Script:
--
: 'RUN: at line 1';   /var/lib/buildkite-agent/builds/llvm-project/build/bin/llvm-go go=/usr/bin/go test llvm.org/llvm/bindings/go/llvm
--
Exit Code: 1

Command Output (stderr):
--
no required module provides package llvm.org/llvm/bindings/go/llvm: go.mod file not found in current directory or any parent directory; see 'go help modules'

I also tried to run this test locallly on my ubuntu host but got such result:

./bin/llvm-lit /workspace/risc-v/bpang/T_E_S_T/llvm-project/llvm/test/Bindings/Go/go.test                       
-- Testing: 1 tests, 1 workers --                                                                                                                                                      
UNSUPPORTED: LLVM :: Bindings/Go/go.test (1 of 1)                                                                                                                                      
                                                                                                                                                                                       
Testing Time: 0.07s                                                                                                                                                                    
  Unsupported: 1

[jrtc27]

The Go binding tests are known to be flaky, you can ignore that, it's totally unrelated

[BaoshanPang]

The Go binding tests are known to be flaky, you can ignore that, it's totally unrelated

Then what else should I do to move forward for this review?

[craig.topper]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

341

Use int64_t here so that no bits are dropped. That will make the assert isInt<12> assert more accurate too.

[BaoshanPang]

update

[craig.topper]

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

342

Not here. On the declaration of NegImm12. Right now you have uint64_t->int->int64_t. I'm suggesting uint64_t->int64_t.

[BaoshanPang]

update

[craig.topper]

LGTM

[BaoshanPang]

In D116574#3228416, @craig.topper wrote:

LGTM

@craig.topper
Thanks for the reivew.
I forget to mention that I don't have push permission yet, Can you help to push my code in? Thanks.

[craig.topper]

In D116574#3228425, @BaoshanPang wrote:

In D116574#3228416, @craig.topper wrote:

LGTM

@craig.topper
Thanks for the reivew.
I forget to mention that I don't have push permission yet, Can you help to push my code in? Thanks.

Yes, please provide your name and email as you would like it to appear in the git log

[BaoshanPang]

Yes, please provide your name and email as you would like it to appear in the git log

Baoshan Pang
[e-mail]

Thanks.

llvm/lib/Target/RISCV/MCTargetDesc/RISCVMatInt.cpp

static void generateInstSeqImpl(int64_t Val,
   if (Unsigned)
     Res.push_back(RISCVMatInt::Inst(RISCV::SLLIUW, ShiftAmount));
   else
     Res.push_back(RISCVMatInt::Inst(RISCV::SLLI, ShiftAmount));
   if (Lo12)
     Res.push_back(RISCVMatInt::Inst(RISCV::ADDI, Lo12));
 }
 
+static bool extractRotateInfo(int64_t Val, int &NegImm12, int &Rotate) {
+  // for case: 0b111..1..xxxxxx1..1..
+  unsigned LeadingOnes = countLeadingOnes((uint64_t)Val);
+  unsigned TrailingOnes = countTrailingOnes((uint64_t)Val);
+  if (TrailingOnes > 0 && (LeadingOnes + TrailingOnes) > (64 - 12)) {
+    NegImm12 = ((uint64_t)Val >> TrailingOnes) |
+               ((uint64_t)Val << (64 - TrailingOnes));
+    Rotate = 64 - TrailingOnes;
+    return true;
+  }
+  // for case: 0bxxx1..1..1...xxx
+  unsigned UpperTrailingOnes = countTrailingOnes(Hi_32(Val));
+  unsigned LowerLeadingOnes = countLeadingOnes(Lo_32(Val));
+  if ((UpperTrailingOnes + LowerLeadingOnes) > (64 - 12)) {
+    NegImm12 = ((uint64_t)Val << (32 - UpperTrailingOnes)) |
+               (((uint64_t)Val >> (32 + UpperTrailingOnes)));
+    Rotate = 32 - UpperTrailingOnes;
+    return true;
+  }
+  return false;
+}
+
 namespace llvm {
 namespace RISCVMatInt {
 InstSeq generateInstSeq(int64_t Val, const FeatureBitset &ActiveFeatures) {
   RISCVMatInt::InstSeq Res;
   generateInstSeqImpl(Val, ActiveFeatures, Res);
 
   // If the constant is positive we might be able to generate a shifted constant
   // with no leading zeros and use a final SRLI to restore them.
if (Div > 0) {
       generateInstSeqImpl(Hi52 / Div, ActiveFeatures, TmpSeq);
       TmpSeq.push_back(RISCVMatInt::Inst(Opc, 0));
       TmpSeq.push_back(RISCVMatInt::Inst(RISCV::ADDI, Lo12));
       if (TmpSeq.size() < Res.size())
         Res = TmpSeq;
     }
   }
 
+  // Perform optimization with rori in the Zbb extension.
+  if (Res.size() > 2 && ActiveFeatures[RISCV::FeatureStdExtZbb]) {
+    int NegImm12;
+    int Rotate;
+    if (extractRotateInfo(Val, NegImm12, Rotate)) {
+      RISCVMatInt::InstSeq TmpSeq;
+      TmpSeq.push_back(RISCVMatInt::Inst(RISCV::ADDI, NegImm12));
+      TmpSeq.push_back(RISCVMatInt::Inst(RISCV::RORI, Rotate));
+      Res = TmpSeq;
+    }
+  }
   return Res;
 }
 
 int getIntMatCost(const APInt &Val, unsigned Size,
                   const FeatureBitset &ActiveFeatures, bool CompressionCost) {
   bool IsRV64 = ActiveFeatures[RISCV::Feature64Bit];
   bool HasRVC = CompressionCost && ActiveFeatures[RISCV::FeatureStdExtC];
   int PlatRegSize = IsRV64 ? 64 : 32;

llvm/test/CodeGen/RISCV/imm_zbb.ll

+; RUN: llc -mtriple=riscv64 -mattr=+experimental-zbb \
+; RUN:   -verify-machineinstrs < %s | FileCheck %s -check-prefix=RV64IZBB
+
+
+; Materializing constants with zbb
+
+define i64 @li_rori_1() {
+; RV64IZBB-LABEL: li_rori_1:
+; RV64IZBB:       # %bb.0:
+; RV64IZBB-NEXT:    li a0, -18
+; RV64IZBB-NEXT:    rori    a0, a0, 21
+; RV64IZBB-NEXT:    ret
+  ret i64 -149533581377537
+}
+define i64 @li_rori_2() {
+; RV64IZBB-LABEL: li_rori_2:
+; RV64IZBB:       # %bb.0:
+; RV64IZBB-NEXT:    li a0, -86
+; RV64IZBB-NEXT:    rori    a0, a0, 4
+; RV64IZBB-NEXT:    ret
+  ret i64 -5764607523034234886
+}
+define i64 @li_rori_3() {
+; RV64IZBB-LABEL: li_rori_3:
+; RV64IZBB:       # %bb.0:
+; RV64IZBB-NEXT:    li a0, -18
+; RV64IZBB-NEXT:    rori    a0, a0, 37
+; RV64IZBB-NEXT:    ret
+  ret i64 -2281701377
+}

llvm/test/MC/RISCV/rv64zbb-valid.s

 # With Bitmanip base extension:
 # RUN: llvm-mc %s -triple=riscv64 -mattr=+experimental-zbb -riscv-no-aliases -show-encoding \
 # RUN:     | FileCheck -check-prefixes=CHECK-ASM,CHECK-ASM-AND-OBJ %s
 # RUN: llvm-mc -filetype=obj -triple=riscv64 -mattr=+experimental-zbb < %s \
 # RUN:     | llvm-objdump --mattr=+experimental-zbb -M no-aliases -d -r - \
 # RUN:     | FileCheck --check-prefix=CHECK-ASM-AND-OBJ %s
 
 # CHECK-ASM-AND-OBJ: clzw t0, t1
 # CHECK-ASM: encoding: [0x9b,0x12,0x03,0x60]
 clzw t0, t1
 # CHECK-ASM-AND-OBJ: ctzw t0, t1
 # CHECK-ASM: encoding: [0x9b,0x12,0x13,0x60]
 ctzw t0, t1
 # CHECK-ASM-AND-OBJ: cpopw t0, t1
 # CHECK-ASM: encoding: [0x9b,0x12,0x23,0x60]
 cpopw t0, t1
+
+# CHECK-ASM-AND-OBJ: addi t0, zero, -18
+# CHECK-ASM-AND-OBJ: rori t0, t0, 21
+li t0, -149533581377537
+# CHECK-ASM-AND-OBJ: addi t0, zero, -86
+# CHECK-ASM-AND-OBJ: rori t0, t0, 4
+li t0, -5764607523034234886
+# CHECK-ASM-AND-OBJ: addi t0, zero, -18
+# CHECK-ASM-AND-OBJ: rori t0, t0, 37
+li t0, -2281701377