[PowerPC] Exploit paddi instruction on Power 10 for constant materialization

[stefanp]

Summary

Starting with Power 10 the instruction paddi is available to use.
The instruction allows for immediates that are 34 bits.

This patch adds exploitation of the paddi instruction to allow us
to materialize constants.

[steven.zhang]

llvm/test/CodeGen/PowerPC/p10-constants.ll

16–19

I guess you miss to rebase the patch, so we see this irrelative change ?

[NeHuang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1046

why do we name it as FO instead of LO here? can you please explain what FO stands for?

1111

Can we merge the code for the three patterns? Maybe we can do something like:
Var = TZ/30-LZ/TO for different scenarios and use Var below (feel free to change Var to other name):

APInt SignedInt34 = APInt(34, (Imm >> (Var)) & 0x3ffffffff);
APInt Extended = SignedInt34.sext(64);
Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
                                getI64Imm(*Extended.getRawData()));
return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
                              getI32Imm(Var), getI32Imm(LZ));

[stefanp]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1046

The FO is for Following Ones. It is the number of ones that follow the first zeros.
The idea is that you are counting these:

00...0011...1110<bits>
       ^------^

1111

That's a good idea. I'm going to try to merge these into one and see how that looks.
I want to try to keep the comments to explain each scenario.

llvm/test/CodeGen/PowerPC/p10-constants.ll

16–19

You are right. I will rebase this patch.

[stefanp]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1111

I realized now why this isn't going to work. I thought it was going to work when you mentioned it but now I see why they are separate.
The instructions are not identical. When the shift is TZ the instruction is RLDIC and the other two are RLDICL. I don't think it is worth changing how the code is written to merge just two of the patterns (it will make it more confusing when looking at why all the patterns have their own if statement and then two of them are merged) Therefore I'm just going to leave the code as-is.

[stefanp]

Rebased the patch to the top of main.

Tried to merge three of the cases but it looks like that won't work as one of
the cases actually uses a different instrution (I didn't even notice this)
RLDIC vs. RLDICL. I don't want to merge the remaining two as I think this is
more clear.

[stefanp]

Gentle ping.

[amyk]

Just a few minor nit comments.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1084

Minor spelling mistake.

llvm/test/CodeGen/PowerPC/p10-constants.ll

249

I noticed we don't really use the term Trailing Ones, but we use Following Ones. Would it be better if we said Following Ones here?

260

Just double checking but does this test correspond to the (LZ + FO + TO) > 30 case?

If that is the case, should the comment be Leading Zeros + Following Ones + Trailing Zeros?

[amyk]

llvm/test/CodeGen/PowerPC/p10-constants.ll

249

Actually, you can disregard this comment. I made a mistake. We have both Trailing Ones and Following Ones in this patch. Sorry about that!

[stefanp]

Fixed spelling mistake.

[lei]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1050–1052

I see this lambda defined in at least 2 other functions in this file. Maybe it's time to make this an actual function rather then a lambda within the different functions. But that can be a followup NFC patch.

[amyk]

Sorry for the delay and thank you for addressing my previous comments. I think this LGTM.

[stefanp]

Rebased patch to prepare for commit.

[hokein]

hi @stefanp, this patch caused an asan error when running on ninja check-llvm-codegen-powerpc.

llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:1046:48: runtime error: shift exponent 64 is too large for 64-bit type 'uint64_t' (aka 'unsigned long')

[hokein]

In D93300#2621881, @hokein wrote:

hi @stefanp, this patch caused an asan error when running on ninja check-llvm-codegen-powerpc.

llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:1046:48: runtime error: shift exponent 64 is too large for 64-bit type 'uint64_t' (aka 'unsigned long')

ok, looks like @RKSimon fixed them in https://github.com/llvm/llvm-project/commit/f6524b4ada823a9766f7cbdfc16e052971e005f6, Thanks!

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

 
 // Try to select instructions to generate a 64 bit immediate using prefix as
 // well as non prefix instructions. The function will return the SDNode
 // to materialize that constant or it will return nullptr if it does not
 // find one. The variable InstCnt is set to the number of instructions that
 // were selected.
 static SDNode *selectI64ImmDirectPrefix(SelectionDAG *CurDAG, const SDLoc &dl,
                                         uint64_t Imm, unsigned &InstCnt) {
+  unsigned TZ = countTrailingZeros<uint64_t>(Imm);
+  unsigned LZ = countLeadingZeros<uint64_t>(Imm);
+  unsigned TO = countTrailingOnes<uint64_t>(Imm);
+  unsigned FO = countLeadingOnes<uint64_t>(Imm << LZ);
+  unsigned Hi32 = Hi_32(Imm);
+  unsigned Lo32 = Lo_32(Imm);
+
+  auto getI32Imm = [CurDAG, dl](unsigned Imm) {
+    return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
+  };
+
+  auto getI64Imm = [CurDAG, dl](uint64_t Imm) {
+    return CurDAG->getTargetConstant(Imm, dl, MVT::i64);
+  };
+
   // Following patterns use 1 instruction to materialize Imm.
   InstCnt = 1;
 
   // The pli instruction can materialize up to 34 bits directly.
   // It is defined in the TD file and so we just return the constant.
   if (isInt<34>(Imm))
     return cast<ConstantSDNode>(CurDAG->getConstant(Imm, dl, MVT::i64));
 
-  InstCnt = 0;
-  return nullptr;
+  // Require at least two instructions.
+  InstCnt = 2;
+  SDNode *Result = nullptr;
+  // Patterns : {zeros}{ones}{33-bit value}{zeros}
+  //            {zeros}{33-bit value}{zeros}
+  //            {zeros}{ones}{33-bit value}
+  //            {ones}{33-bit value}{zeros}
+  // We can take advantage of PLI's sign-extension semantics to generate leading
+  // ones, and then use RLDIC to mask off the ones on both sides after rotation.
+  if ((LZ + FO + TZ) > 30) {
+    APInt SignedInt34 = APInt(34, (Imm >> TZ) & 0x3ffffffff);
+    APInt Extended = SignedInt34.sext(64);
+    Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
+                                    getI64Imm(*Extended.getRawData()));
+    return CurDAG->getMachineNode(PPC::RLDIC, dl, MVT::i64, SDValue(Result, 0),
+                                  getI32Imm(TZ), getI32Imm(LZ));
+  }
+  // Pattern : {zeros}{33-bit value}{ones}
+  // Shift right the Imm by (30 - LZ) bits to construct a negative 34 bit value,
+  // therefore we can take advantage of PLI's sign-extension semantics, and then
+  // mask them off after rotation.
+  //
+  // +--LZ--||-33-bit-||--TO--+     +-------------|--34-bit--+
+  // |00000001bbbbbbbbb1111111| ->  |00000000000001bbbbbbbbb1|
+  // +------------------------+     +------------------------+
+  // 63                      0      63                      0
+  //
+  // +----sext-----|--34-bit--+     +clear-|-----------------+
+  // |11111111111111bbbbbbbbb1| ->  |00000001bbbbbbbbb1111111|
+  // +------------------------+     +------------------------+
+  // 63                      0      63                      0
+  if ((LZ + TO) > 30) {
+    APInt SignedInt34 = APInt(34, (Imm >> (30 - LZ)) & 0x3ffffffff);
+    APInt Extended = SignedInt34.sext(64);
+    Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
+                                    getI64Imm(*Extended.getRawData()));
+    return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
+                                  getI32Imm(30 - LZ), getI32Imm(LZ));
+  }
+  // Patterns : {zeros}{ones}{33-bit value}{ones}
+  //            {ones}{33-bit value}{ones}
+  // Similar to LI we can take advantage of PLI's sign-extension semantics to
+  // generate leading ones, and then use RLDICL to mask off the ones in left
+  // sides (if required) after rotation.
+  if ((LZ + FO + TO) > 30) {
+    APInt SignedInt34 = APInt(34, (Imm >> TO) & 0x3ffffffff);
+    APInt Extended = SignedInt34.sext(64);
+    Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64,
+                                    getI64Imm(*Extended.getRawData()));
+    return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
+                                  getI32Imm(TO), getI32Imm(LZ));
+  }
+  // Patterns : {******}{31 zeros}{******}
+  //          : {******}{31 ones}{******}
+  // If Imm contains 31 consecutive zeros/ones then the remaining bit count
+  // is 33. Rotate right the Imm to construct a int<33> value, we can use PLI
+  // for the int<33> value and then use RLDICL without a mask to rotate it back.
+  //
+  // +------|--ones--|------+     +---ones--||---33 bit--+
+  // |bbbbbb1111111111aaaaaa| ->  |1111111111aaaaaabbbbbb|
+  // +----------------------+     +----------------------+
+  // 63                    0      63                    0
+  for (unsigned Shift = 0; Shift < 63; ++Shift) {
+    uint64_t RotImm = (Imm >> Shift) | (Imm << (64 - Shift));
+    if (isInt<34>(RotImm)) {
+      Result =
+          CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(RotImm));
+      return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64,
+                                    SDValue(Result, 0), getI32Imm(Shift),
+                                    getI32Imm(0));
+    }
+  }
+
+  // Patterns : High word == Low word
+  // This is basically a splat of a 32 bit immediate.
+  if (Hi32 == Lo32) {
+    Result = CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Hi32));
+    SDValue Ops[] = {SDValue(Result, 0), SDValue(Result, 0), getI32Imm(32),
+                     getI32Imm(0)};
+    return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
+  }
+
+  InstCnt = 3;
+  // Catch-all
+  // This pattern can form any 64 bit immediate in 3 instructions.
+  SDNode *ResultHi =
+      CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Hi32));
+  SDNode *ResultLo =
+      CurDAG->getMachineNode(PPC::PLI8, dl, MVT::i64, getI64Imm(Lo32));
+  SDValue Ops[] = {SDValue(ResultLo, 0), SDValue(ResultHi, 0), getI32Imm(32),
+                   getI32Imm(0)};
+  return CurDAG->getMachineNode(PPC::RLDIMI, dl, MVT::i64, Ops);
 }
 
 static SDNode *selectI64Imm(SelectionDAG *CurDAG, const SDLoc &dl, uint64_t Imm,
                             unsigned *InstCnt = nullptr) {
   unsigned InstCntDirect = 0;
   // No more than 3 instructions is used if we can select the i64 immediate
   // directly.
   SDNode *Result = selectI64ImmDirect(CurDAG, dl, Imm, InstCntDirect);

llvm/test/CodeGen/PowerPC/fast-isel-pcrel.ll

 ; CHECK-NEXT:  # %bb.0: # %entry
 ; CHECK-NEXT:    mflr r0
 ; CHECK-NEXT:    std r0, 16(r1)
 ; CHECK-NEXT:    stdu r1, -112(r1)
 ; CHECK-NEXT:    std r3, 104(r1)
 ; CHECK-NEXT:    paddi r3, 0, .L.str@PCREL, 1
 ; CHECK-NEXT:    bl printf@notoc
 ; CHECK-NEXT:    ld r4, 104(r1)
-; CHECK-NEXT:    lis r3, 8201
-; CHECK-NEXT:    ori r3, r3, 64225
-; CHECK-NEXT:    rldic r3, r3, 33, 1
-; CHECK-NEXT:    oris r3, r3, 36700
-; CHECK-NEXT:    ori r3, r3, 10486
+; CHECK-NEXT:    pli r5, 1075049922
+; CHECK-NEXT:    pli r3, 2405181686
+; CHECK-NEXT:    rldimi r3, r5, 32, 0
 ; CHECK-NEXT:    std r3, 0(r4)
 ; CHECK-NEXT:    addi r1, r1, 112
 ; CHECK-NEXT:    ld r0, 16(r1)
 ; CHECK-NEXT:    mtlr r0
 ; CHECK-NEXT:    blr
 entry:
   %d.addr = alloca double*, align 8
   store double* %d, double** %d.addr, align 8

llvm/test/CodeGen/PowerPC/p10-constants.ll

 ; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu \
 ; RUN:   -mcpu=pwr10 -ppc-asm-full-reg-names -ppc-vsr-nums-as-vr < %s | \
 ; RUN:   FileCheck %s
 ; RUN: llc -verify-machineinstrs -mtriple=powerpc64-unknown-linux-gnu \
 ; RUN:   -mcpu=pwr10 -ppc-asm-full-reg-names -ppc-vsr-nums-as-vr < %s | \
 ; RUN:   FileCheck %s
 ; RUN: llc -verify-machineinstrs -mtriple=powerpc-unknown-linux-gnu \
 ; RUN:   -mcpu=pwr10 -ppc-asm-full-reg-names -ppc-vsr-nums-as-vr < %s | \
 ; RUN:   FileCheck %s --check-prefix=CHECK32
 
 ; These test cases aim to test constant materialization using the pli instruction on Power10.
 
 define  signext i32 @t_16BitsMinRequiring34Bits() {
 ; CHECK-LABEL: t_16BitsMinRequiring34Bits:
 ; CHECK:  pli r3, 32768
 ; CHECK-NEXT: blr
 ; CHECK32-LABEL: t_16BitsMinRequiring34Bits:
 ; CHECK32:  pli r3, 32768
 ; CHECK32-NEXT: blr
 
 entry:
   ret i32 32768
 }
 
 define  signext i32 @t_16Bits() {
 ; CHECK-LABEL: t_16Bits:
 ; CHECK:  pli r3, 62004

 ; CHECK32-NEXT: blr
 
 entry:
   ret i64 8589934592
 }
 
 define  i64 @t_34Bits() {
 ; CHECK-LABEL: t_34Bits:
-; CHECK:  lis r3, 25158
-; CHECK-NEXT: ori r3, r3, 35535
+; CHECK:  pli r3, 1648790223
 ; CHECK-NEXT: rldic r3, r3, 3, 30
 ; CHECK-NEXT: blr
 ; CHECK32-LABEL: t_34Bits:
 ; CHECK32:  li r3, 3
 ; CHECK32-NEXT: pli r4, 305419896
 ; CHECK32-NEXT: blr
 
 entry:
   ret i64 13190321784
 }
 
 define  i64 @t_35Bits() {
 ; CHECK-LABEL: t_35Bits:
-; CHECK:  lis r3, -442
-; CHECK-NEXT: ori r3, r3, 35535
+; CHECK:  pli r3, 4266035919
 ; CHECK-NEXT: rldic r3, r3, 3, 29
 ; CHECK-NEXT: blr
 ; CHECK32-LABEL: t_35Bits:
 ; CHECK32:  li r3, 7
 ; CHECK32-NEXT: pli r4, -231451016
 ; CHECK32-NEXT: blr
 
 entry:
   ret i64 34128287352
 }
 
+; (Value >> Shift) can be expressed in 34 bits
+define  i64 @t_Shift() {
+; CHECK-LABEL: t_Shift:
+; CHECK:         pli r3, 8522759166
+; CHECK-NEXT:    rotldi r3, r3, 48
+; CHECK-NEXT:    blr
+
+entry:
+  ; 0xFBFE00000001FBFE
+  ret i64 18157950747604548606
+}
+
+; Leading Zeros + Following Ones + Trailing Zeros > 30
+define  i64 @t_LZFOTZ() {
+; CHECK-LABEL: t_LZFOTZ:
+; CHECK:         pli r3, -349233
+; CHECK-NEXT:    rldic r3, r3, 4, 12
+; CHECK-NEXT:    blr
+
+entry:
+  ; 0x000FFFFFFFAABCF0
+  ret i64 4503599621782768
+}
+
+; Leading Zeros + Trailing Ones > 30
+define  i64 @t_LZTO() {
+; CHECK-LABEL: t_LZTO:
+; CHECK:         pli r3, -2684406441
+; CHECK-NEXT:    rldicl r3, r3, 11, 19
+; CHECK-NEXT:    blr
+entry:
+  ; 0x00001AFFF9AABFFF
+  ret i64 29686707699711
+}
+
+; Leading Zeros + Trailing Ones + Following Zeros > 30
+define  i64 @t_LZTOFO() {
+; CHECK-LABEL: t_LZTOFO:
+; CHECK:         pli r3, -5720033968
+; CHECK-NEXT:    rldicl r3, r3, 11, 12
+; CHECK-NEXT:    blr
+entry:
+  ; 0x000FF55879AA87FF
+  ret i64 4491884997806079
+}
+
+; Requires full expansion
+define  i64 @t_Full64Bits1() {
+; CHECK-LABEL: t_Full64Bits1:
+; CHECK:         pli r4, 2146500607
+; CHECK-NEXT:    pli r3, 4043305214
+; CHECK-NEXT:    rldimi r3, r4, 32, 0
+; CHECK-NEXT:    blr
+entry:
+  ; 0x7FF0FFFFF0FFF0FE
+  ret i64 9219149911952453886
+}
+
+; Requires full expansion
+define  i64 @t_Ful64Bits2() {
+; CHECK-LABEL: t_Ful64Bits2:
+; CHECK:         pli r4, 4042326015
+; CHECK-NEXT:    pli r3, 4043305214
+; CHECK-NEXT:    rldimi r3, r4, 32, 0
+; CHECK-NEXT:    blr
+entry:
+  ; 0xF0F0FFFFF0FFF0FE
+  ret i64 17361658038238310654
+}
+
+; A splat of 32 bits: 32 Bits Low == 32 Bits High
+define  i64 @t_Splat32Bits() {
+; CHECK-LABEL: t_Splat32Bits:
+; CHECK:         pli r3, 262916796
+; CHECK-NEXT:    rldimi r3, r3, 32, 0
+; CHECK-NEXT:    blr
+entry:
+  ; 0x0FABCABC0FABCABC
+  ret i64 1129219040652020412
+}
+
 ; The load immediates resulting from phi-nodes are needed to test whether
 ; li/lis is preferred to pli by the instruction selector.
 define dso_local void @t_phiNode() {
 ; CHECK-LABEL: t_phiNode:
 ; CHECK:  lis r6, 18
 ; CHECK-NEXT: li r5, 291
 ; CHECK-NEXT: li r4, 0
 ; CHECK-NEXT:   cmpwi r3, 1