[PowerPC] Exploit rldimi for ori with large immediates

[qiucf]

Summary

This patch exploits rldimi instruction for patterns like or %a, 0b000011110000, which saves number of instructions in some cases, compared with li-ori-sldi-or.

[nemanjai]

This is a good idea, thanks for working on it. Just needs a slight tweak.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4607

s/sequent/consecutive
(in other places as well)

4611

There are probably some more conditions under which you don't want to do this. What comes to mind is checking for a single use of the input to the OR (since rldimi is destructive) and that the output is not used in a SETCC to compare against zero.

Here's a test case:

long test(long a, long b) {
  return ((a | 4294967296L) > 0) ? a : b;
}

Prior to this patch, the codegen is:

li 5, 1
sldi 5, 5, 32
or. 5, 3, 5
isel 3, 3, 4, 1

With this patch, the codegen is:

li 5, -1
mr 6, 3
rldimi. 6, 5, 32, 31
isel 3, 3, 4, 1

At first glance, the new codegen looks no worse. However it is worse for two reasons:

1. Increased register pressure to move the value due to rldimi being destructive
2. Record-form rotate instead of record-form or is worse because the former is a two-way cracked instruction.

[qiucf]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4611

Thanks for pointing this out. I'm not sure about: after checking the input has only one use, is it still profitable to use or. instead of rldimi. for comparison against zero? Like:

long test(long a, long b, long c) {
  return ((a | 4294967296L) > 0) ? c : b;
}

# Original result
li 6, 1
sldi 6, 6, 32
or. 3, 3, 6
isel 3, 5, 4, 1
blr

# After patch
li 6, -1
rldimi. 3, 6, 32, 31
isel 3, 5, 4, 1
blr

[qiucf]

Check uses of first operand

[nemanjai]

LGTM. Please add a test case where the input value has multiple uses for a test of where we don't do this even when the constant is conducive to doing it. I don't think such an addition requires another review.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4611

Well, we could check something like N->use_begin()->getOpcode() == ISD::SETCC, but I don't think it is necessary. The cracked rldimi. is no worse than the increased path length of the or. sequence.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

 private:
     bool trySETCC(SDNode *N);
     bool tryAsSingleRLDICL(SDNode *N);
     bool tryAsSingleRLDICR(SDNode *N);
     bool tryAsSingleRLWINM(SDNode *N);
     bool tryAsSingleRLWINM8(SDNode *N);
     bool tryAsSingleRLWIMI(SDNode *N);
     bool tryAsPairOfRLDICL(SDNode *N);
+    bool tryAsSingleRLDIMI(SDNode *N);
 
     void PeepholePPC64();
     void PeepholePPC64ZExt();
     void PeepholeCROps();
 
     SDValue combineToCMPB(SDNode *N);
     void foldBoolExts(SDValue &Res, SDNode *&N);
 
bool PPCDAGToDAGISel::tryAsSingleRLDICR(SDNode *N) {
   unsigned MB = 63 - countTrailingOnes(~Imm64);
   unsigned SH = 0;
   SDLoc dl(N);
   SDValue Ops[] = {N->getOperand(0), getI32Imm(SH, dl), getI32Imm(MB, dl)};
   CurDAG->SelectNodeTo(N, PPC::RLDICR, MVT::i64, Ops);
   return true;
 }
 
+bool PPCDAGToDAGISel::tryAsSingleRLDIMI(SDNode *N) {
+  assert(N->getOpcode() == ISD::OR && "ISD::OR SDNode expected");
+  uint64_t Imm64;
+  unsigned MB, ME;
+  SDValue N0 = N->getOperand(0);
+
+  // We won't get fewer instructions if the imm is 32-bit integer.
+  // rldimi requires the imm to have consecutive ones with both sides zero.
+  // Also, make sure the first Op has only one use, otherwise this may increase
+  // register pressure since rldimi is destructive.
+  if (!isInt64Immediate(N->getOperand(1).getNode(), Imm64) ||
+      isUInt<32>(Imm64) || !isRunOfOnes64(Imm64, MB, ME) || !N0.hasOneUse())
+    return false;
+
+  unsigned SH = 63 - ME;
+  SDLoc Dl(N);
+  // Use select64Imm for making LI instr instead of directly putting Imm64
+  SDValue Ops[] = {
+      N->getOperand(0),
+      SDValue(selectI64Imm(CurDAG, getI64Imm(-1, Dl).getNode()), 0),
+      getI32Imm(SH, Dl), getI32Imm(MB, Dl)};
+  CurDAG->SelectNodeTo(N, PPC::RLDIMI, MVT::i64, Ops);
+  return true;
+}
+
 // Select - Convert the specified operand from a target-independent to a
 // target-specific node if it hasn't already been changed.
 void PPCDAGToDAGISel::Select(SDNode *N) {
   SDLoc dl(N);
   if (N->isMachineOpcode()) {
     N->setNodeId(-1);
     return;   // Already selected.
   }
if (N->getOperand(0)->getOpcode() == ISD::FrameIndex &&
       // If this is equivalent to an add, then we can fold it with the
       // FrameIndex calculation.
       if ((LHSKnown.Zero.getZExtValue()|~(uint64_t)Imm) == ~0ULL) {
         selectFrameIndex(N, N->getOperand(0).getNode(), (int)Imm);
         return;
       }
     }
 
+    // If this is 'or' against an imm with consecutive ones and both sides zero,
+    // try to emit rldimi
+    if (tryAsSingleRLDIMI(N))
+      return;
+
     // OR with a 32-bit immediate can be handled by ori + oris
     // without creating an immediate in a GPR.
     uint64_t Imm64 = 0;
     bool IsPPC64 = PPCSubTarget->isPPC64();
     if (IsPPC64 && isInt64Immediate(N->getOperand(1), Imm64) &&
         (Imm64 & ~0xFFFFFFFFuLL) == 0) {
       // If ImmHi (ImmHi) is zero, only one ori (oris) is generated later.
       uint64_t ImmHi = Imm64 >> 16;

llvm/test/CodeGen/PowerPC/ori_imm32.ll

 entry:
   %or = or i64 %a, 4294967295
   ret i64 %or
 }
 
 define i64 @ori_test_b(i64 %a) {
 ; CHECK-LABEL: ori_test_b:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    li 4, 1
-; CHECK-NEXT:    sldi 4, 4, 32
-; CHECK-NEXT:    or 3, 3, 4
+; CHECK-NEXT:    li 4, -1
+; CHECK-NEXT:    rldimi 3, 4, 32, 31
 ; CHECK-NEXT:    blr
 entry:
   %or = or i64 %a, 4294967296
   ret i64 %or
 }
 
 define i64 @ori_test_c(i64 %a) {
 ; CHECK-LABEL: ori_test_c:

llvm/test/CodeGen/PowerPC/ori_imm64.ll

 entry:
   %or = or i64 %a, 18446744073709551615 ; 0xffffffffffffffff
   ret i64 %or
 }
 
 define i64 @ori_test_2(i64 %a) {
 ; CHECK-LABEL: ori_test_2:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    lis 4, 15
-; CHECK-NEXT:    ori 4, 4, 65535
-; CHECK-NEXT:    sldi 4, 4, 29
-; CHECK-NEXT:    or 3, 3, 4
+; CHECK-NEXT:    li 4, -1
+; CHECK-NEXT:    rldimi 3, 4, 29, 15
 ; CHECK-NEXT:    blr
 entry:
   %or = or i64 %a, 562949416550400 ; 0x1ffffe0000000
   ret i64 %or
 }
 
 define i64 @ori_test_3(i64 %a) {
 ; CHECK-LABEL: ori_test_3:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    lis 4, -32768
-; CHECK-NEXT:    rldicr 4, 4, 36, 63
-; CHECK-NEXT:    or 3, 3, 4
+; CHECK-NEXT:    li 4, -1
+; CHECK-NEXT:    rldimi 3, 4, 3, 28
 ; CHECK-NEXT:    blr
 entry:
   %or = or i64 %a, 68719476728 ; 0xffffffff8
   ret i64 %or
 }
 
 define i64 @ori_test_4(i64 %a) {
 ; CHECK-LABEL: ori_test_4:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    li 4, 4112
 ; CHECK-NEXT:    sldi 4, 4, 32
 ; CHECK-NEXT:    oris 4, 4, 4112
 ; CHECK-NEXT:    ori 4, 4, 65535
 ; CHECK-NEXT:    or 3, 3, 4
 ; CHECK-NEXT:    blr
 entry:
   %or = or i64 %a, 17661175070719 ; 0x10101010ffff
   ret i64 %or
 }
+
+; Don't exploit rldimi if operand has multiple uses
+define i64 @test_test_5(i64 %a, i64 %b) {
+; CHECK-LABEL: test_test_5:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    li 5, 1
+; CHECK-NEXT:    sldi 5, 5, 32
+; CHECK-NEXT:    or 5, 3, 5
+; CHECK-NEXT:    add 4, 5, 4
+; CHECK-NEXT:    sub 3, 3, 4
+; CHECK-NEXT:    blr
+entry:
+  %or = or i64 %a, 4294967296
+  %add = add i64 %or, %b
+  %div = sub i64 %a, %add
+  ret i64 %div
+}