[PowerPC] Handle the constant with many trailing ones.

[Esme]

Summary

We have handled the constants with many trailing zeros like i64 5228199936 ( 0b100110111101000000000000000000000) , which can be materialized by 2 instructions:

	li 3, 2493
	sldi 3, 3, 21

Inspired by this, we considered another case where the constant has many trailing ones. We can take advantage of li/lis's sign-extension to generate leading ones, and then mask extra bits off after rotation.
For example, without such ISEL pattern we need 4 instructions to materialize i64 10460594175 (0b1001101111011111111111111111111111)

	li 3, 2
	sldi 3, 3, 32
	oris 3, 3, 28543
	ori 3, 3, 65535

Now we only need 2 instructions after this patch:

	li 3, -31522
	rldicl 3, 3, 23, 30

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

906

selectI64ImmInstrCount need to be updated to return 2 for your pattern.

[Esme]

The patch D92089 can cover this.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

for (unsigned r = 1; r < 63; ++r) {
 
     RCount = selectI64ImmInstrCountDirect(RImmWithOnes) + 1;
     Count = std::min(Count, RCount);
   }
 
   return Count;
 }
 
 // Select a 64-bit constant. For cost-modeling purposes, selectI64ImmInstrCount
 // (above) needs to be kept in sync with this function.
 static SDNode *selectI64ImmDirect(SelectionDAG *CurDAG, const SDLoc &dl,
                                   int64_t Imm) {
   // Assume no remaining bits.
   unsigned Remainder = 0;
   // Assume no shift required.
   unsigned Shift = 0;
+  // Count trailing zeros.
+  unsigned TrailingZeros = 0;
+  // Count trailing ones.
+  unsigned TrailingOnes = 0;
+  // Count leading zeros as RLDICL's mask.
+  unsigned ClearMask = 0;
 
   // If it can't be represented as a 32 bit value.
   if (!isInt<32>(Imm)) {
-    Shift = countTrailingZeros<uint64_t>(Imm);
-    int64_t ImmSh = static_cast<uint64_t>(Imm) >> Shift;
-
-    // If the shifted value fits 32 bits.
-    if (isInt<32>(ImmSh)) {
-      // Go with the shifted value.
+    TrailingZeros = countTrailingZeros<uint64_t>(Imm);
+    TrailingOnes = countTrailingOnes<uint64_t>(Imm);
+    int64_t ImmSh = TrailingZeros ? static_cast<uint64_t>(Imm) >> TrailingZeros
+                                  : static_cast<uint64_t>(Imm) >> TrailingOnes;
+
+    // If the immediate has many trailing zeros, we can take advantage of
+    // li/lis's sign-extension to generate leading zeros, and then shift it.
+    // Which requires the sign bit to be 0 during li/lis.
+
+    // If the immediate has many trailing ones, we can take advantage of
+    // li/lis's sign-extension to generate leading ones, and then mask extra
+    // bits off after rotation. Which requires the sign bit to be 1 during
+    // li/lis.
+
+    if (TrailingZeros && isInt<32>(ImmSh)) {
+      // If the immediate has many trailing zeros and the shifted value fits
+      // int32, go with the shifted value.
+      Shift = TrailingZeros;
+      Imm = ImmSh;
+    } else if (TrailingOnes && isUInt<32>(ImmSh)) {
+      // If the immediate has many trailing ones and the shifted value fits
+      // uint32, go with the shifted value.
+      ClearMask = countLeadingZeros<uint64_t>(Imm);
       Imm = ImmSh;
     } else {
       // Still stuck with a 64 bit value.
       Remainder = Imm;
       Shift = 32;
       Imm >>= 32;
     }
   }
 
   // Intermediate operand.
   SDNode *Result;
 
   // Handle first 32 bits.
   unsigned Lo = Imm & 0xFFFF;
   unsigned Hi = (Imm >> 16) & 0xFFFF;
 
   auto getI32Imm = [CurDAG, dl](unsigned Imm) {
       return CurDAG->getTargetConstant(Imm, dl, MVT::i32);
   };
 
+  // If the immediate has many trailing ones.
+  if (ClearMask) {
+    if (isUInt<16>(Imm)) {
+      // Set the sign bit to 1.
+      Imm |= 0x8000;
+      Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, getI32Imm(Imm));
+    } else if (Lo) {
+      // Handle the Hi bits and set the sign bit to 1.
+      Hi |= 0x8000;
+      Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64, getI32Imm(Hi));
+      // And the Lo bits.
+      Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
+                                      SDValue(Result, 0), getI32Imm(Lo));
+    } else {
+      // Just the Hi bits.
+      Hi |= 0x8000;
+      Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64, getI32Imm(Hi));
+    }
+    return CurDAG->getMachineNode(PPC::RLDICL, dl, MVT::i64, SDValue(Result, 0),
+                                  getI32Imm(TrailingOnes),
+                                  getI32Imm(ClearMask));
+  }
+
   // Simple value.
   if (isInt<16>(Imm)) {
     uint64_t SextImm = SignExtend64(Lo, 16);
     SDValue SDImm = CurDAG->getTargetConstant(SextImm, dl, MVT::i64);
     // Just the Lo bits.
     Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, SDImm);
   } else if (Lo) {
     // Handle the Hi bits.

llvm/test/CodeGen/PowerPC/combine_ext_trunc.ll

; CHECK-NEXT:    blr
     %c = or i32 %b, %y
     ret i32 %c
 }
 
 ; fold (and (select Cond, 0, -1), X) to (select Cond, 0, X)
 define i32 @pattern3(i1 %cond, i32 %x) {
 ; CHECK-LABEL: pattern3:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    li 5, 0
+; CHECK-NEXT:    li 5, -32768
 ; CHECK-NEXT:    andi. 3, 3, 1
-; CHECK-NEXT:    oris 3, 5, 65535
-; CHECK-NEXT:    ori 3, 3, 65535
+; CHECK-NEXT:    rldicl 3, 5, 32, 32
 ; CHECK-NEXT:    iselgt 3, 0, 3
 ; CHECK-NEXT:    and 3, 3, 4
 ; CHECK-NEXT:    blr
   %sel = select i1 %cond, i32 0, i32 -1
   %res = and i32 %sel, %x
   ret i32 %res
 }
 
 ; fold (or X, (select Cond, -1, 0)) to (select Cond, -1, X)
 define i32 @pattern4(i1 %cond, i32 %x) {
 ; CHECK-LABEL: pattern4:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    li 5, 0
+; CHECK-NEXT:    li 5, -32768
 ; CHECK-NEXT:    andi. 3, 3, 1
-; CHECK-NEXT:    oris 3, 5, 65535
-; CHECK-NEXT:    ori 3, 3, 65535
+; CHECK-NEXT:    rldicl 3, 5, 32, 32
+; CHECK-NEXT:    li 5, 0
 ; CHECK-NEXT:    iselgt 3, 3, 5
 ; CHECK-NEXT:    or 3, 4, 3
 ; CHECK-NEXT:    blr
   %sel = select i1 %cond, i32 -1, i32 0
   %res = or i32 %x, %sel
   ret i32 %res
 }

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

 ; CHECK: blr
 }
 
 define i64 @uint32_2() #0 {
 entry:
   ret i64 4294967295
 
 ; CHECK-LABEL: @uint32_2
-; CHECK: li [[REG1:[0-9]+]], 0
-; CHECK: oris [[REG2:[0-9]+]], [[REG1]], 65535
-; CHECK: ori 3, [[REG2]], 65535
+; CHECK: li [[REG1:[0-9]+]], -32768
+; CHECK: rldicl 3, [[REG1]], 32, 32
 ; CHECK: blr
 }
 
 define i32 @uint32_2_i32() #0 {
 entry:
   ret i32 -1
 
 ; CHECK-LABEL: @uint32_2_i32
-; CHECK: li [[REG1:[0-9]+]], 0
-; CHECK: oris [[REG2:[0-9]+]], [[REG1]], 65535
-; CHECK: ori 3, [[REG2]], 65535
+; CHECK: li [[REG1:[0-9]+]], -32768
+; CHECK: rldicl 3, [[REG1]], 32, 32
 ; CHECK: blr
 }
 
 define i64 @uint32_3() #0 {
 entry:
   ret i64 2147483648
 
 ; CHECK-LABEL: @uint32_3

 ; CHECK: blr
 }
 
 define i64 @cn_ones_1() #0 {
 entry:
   ret i64 10460594175
 
 ; CHECK-LABEL: @cn_ones_1
-; CHECK: li [[REG1:[0-9]+]], 2
-; CHECK: sldi [[REG2:[0-9]+]], [[REG1]], 32
-; CHECK: oris [[REG3:[0-9]+]], [[REG2]], 28543
-; CHECK: ori 3, [[REG3]], 65535
+; CHECK: li [[REG1:[0-9]+]], -31522
+; CHECK: rldicl 3, [[REG1]], 23, 30
 ; CHECK: blr
 }
 
 define i64 @cn_ones_2() #0 {
 entry:
   ret i64 10459119615
 
 ; CHECK-LABEL: @cn_ones_2
-; CHECK: li [[REG1:[0-9]+]], 2
-; CHECK: sldi [[REG2:[0-9]+]], [[REG1]], 32
-; CHECK: oris [[REG3:[0-9]+]], [[REG2]], 28521
-; CHECK: ori 3, [[REG3]], 32767
+; CHECK: lis [[REG1:[0-9]+]], -32764
+; CHECK: ori [[REG2:[0-9]+]], [[REG1]], 57042
+; CHECK: rldicl 3, [[REG2]], 15, 30
+; CHECK: blr
+}
+
+define i64 @cn_ones_3() #0 {
+entry:
+  ret i64 47244673023
+
+; CHECK-LABEL: @cn_ones_3
+; CHECK: lis [[REG1:[0-9]+]], -32746
+; CHECK: rldicl 3, [[REG1]], 15, 28
 ; CHECK: blr
 }
 
 attributes #0 = { nounwind readnone }

llvm/test/CodeGen/PowerPC/negctr.ll

 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 1, %entry ]
   %indvars.iv.next = add i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, 0
   br i1 %exitcond, label %for.end, label %for.body
 
 ; CHECK: @main
-; CHECK: li [[REG:[0-9]+]], 0
-; CHECK: oris [[REG2:[0-9]+]], [[REG]], 65535
-; CHECK: ori [[REG3:[0-9]+]], [[REG2]], 65535
-; CHECK: mtctr [[REG3]]
+; CHECK: li [[REG:[0-9]+]], -32768
+; CHECK: rldicl [[REG2:[0-9]+]], [[REG]], 32, 32
+; CHECK: mtctr [[REG2]]
 ; CHECK: bdnz
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 define void @main1() #0 {
 entry:

llvm/test/CodeGen/PowerPC/ori_imm64.ll

 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:    lis 4, -28656
+; CHECK-NEXT:    ori 4, 4, 4112
+; CHECK-NEXT:    rldicl 4, 4, 16, 19
 ; 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