[PowerPC] Exploit the rlwinm instructions for "and" with constant.

[steven.zhang]

Summary

For now, PowerPC will using several instructions to get the constant and "and" it with the following case:

define i32 @test1(i32 %a) {
  %and = and i32 %a, -2
  ret i32 %and

However, we could exploit it with the rotate mask instructions.

               MB  ME
+----------------------+
|xxxxxxxxxxx00011111000|
+----------------------+
 0         32         64

Notice that, we can only do it if the MB is larger than 32 and MB <= ME as RLWINM will replace the content of [0 - 32) with [32 - 64) even we didn't rotate it.

[shchenz]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4467

Seems if you only consider MB>=32 && MB<=ME case, i think current isRunOfOnes for type i32 should match your requirement? Before call isRunOfOnes() check whether Imm64 can be represented by i32?

4468

for and reg, 0xffffffffffff00ffULL, it should be replaced by one single rlwinm instruction, seems it is not handled here?

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4468

Good point. I will add it together.

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4468

Hmm, after double check, we cannot do it with single rlwinm instructions as it is a wrapping, and the content [0, 31] has been filled with the content of [32, 63]. We need another instructions to clear it. That is the case of 'else' clause.

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4467

We need the isRunOfOnes64 as we will do the special handling for all the cases that is RunOfOne64 with two instructions.

[shchenz]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4468

Sorry, I made a mistake here. and reg, 0xffffffffffff00ffULL I think this case is not a good candidate for one single rlwinm instruction. We get a wrap mask and the result is only related to the low 32 bit of and input. But from the mask 0xffffffffffff00ffULL, the result should be also related to high 32 bit of and input. But I think it is a good candidate for your patch https://reviews.llvm.org/D71831.

llvm/test/CodeGen/PowerPC/opt-cmp-inst-cr0-live.ll

10

The case change seems strange here, the left uses a record form ANDI8, so we can eliminate the CMPLDI with 0 after peephole. But with this change, ANDI8 is converted to RLWINM8, which is not record form. but it surprises me we still can delete the CMPLDI with 0 and replace RLWINM8 back with ANDI8. I think here we should use record form RLWINM8o. But I think it is not this patch's scope.

[steven.zhang]

llvm/test/CodeGen/PowerPC/opt-cmp-inst-cr0-live.ll

10

If it is NOT 16 bit, it is transformed to RLWINM8 record form. And it makes sense to me.

define signext i32 @fn1(i32 %baz) {
  %1 = mul nsw i32 %baz, 208
  %2 = zext i32 %1 to i64
  %3 = shl i64 %2, 47
  %4 = ashr exact i64 %3, 47
  %5 = icmp eq i64 %4, 0
  br i1 %5, label %foo, label %bar
foo:
  ret i32 1

bar:
  ret i32 0
}

	mulli 3, 3, 208
	rlwinm. 3, 3, 0, 15, 27
	beq	0, .LBB0_2

[steven.zhang]

Remove the 16-bit limit as we will have benefit even it is within 16bit, as rlwinm won't define the CR register while ANDIo did.

[shchenz]

LGTM with one nit comment.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4460

imm16 should be handle as well in new patch? comment should update?

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4460

Oops, I will update it when commit this patch.

[steven.zhang]

I realize that most reviewers were on vacation during this patch was reviewed and committed. It is a bit too haste to commit this patch. Please add the comments here if have any concern. Sorry about this.

[amyk]

Just curious about a specific portion of your patch, so I posted a comment.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4460

Might be a silly question, but what exactly does this comment mean and why is a 16-bit immediate significant? And did you mean to say, If it is not a 16-bit imm?

llvm/lib/Target/PowerPC/MCTargetDesc/PPCMCTargetDesc.h

if (isShiftedMask_32(Val)) {
       MB = countLeadingZeros((Val - 1) ^ Val) + 1;
       return true;
     }
   }
   // no run present
   return false;
 }
 
+static inline bool isRunOfOnes64(uint64_t Val, unsigned &MB, unsigned &ME) {
+  if (!Val)
+    return false;
+
+  if (isShiftedMask_64(Val)) {
+    // look for the first non-zero bit
+    MB = countLeadingZeros(Val);
+    // look for the first zero bit after the run of ones
+    ME = countLeadingZeros((Val - 1) ^ Val);
+    return true;
+  } else {
+    Val = ~Val; // invert mask
+    if (isShiftedMask_64(Val)) {
+      // effectively look for the first zero bit
+      ME = countLeadingZeros(Val) - 1;
+      // effectively look for the first one bit after the run of zeros
+      MB = countLeadingZeros((Val - 1) ^ Val) + 1;
+      return true;
+    }
+  }
+  // no run present
+  return false;
+}
+
 } // end namespace llvm
 
 // Generated files will use "namespace PPC". To avoid symbol clash,
 // undefine PPC here. PPC may be predefined on some hosts.
 #undef PPC
 
 // Defines symbolic names for PowerPC registers.  This defines a mapping from
 // register name to register number.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

if (isMask_64(Imm64)) {
       // i.e. the immediate is a sequence of ones from most significant side
       // and all zero for reminder, we should use rldicr.
       MB = 63 - countTrailingOnes(~Imm64);
       SH = 0;
       SDValue Ops[] = { Val, getI32Imm(SH, dl), getI32Imm(MB, dl) };
       CurDAG->SelectNodeTo(N, PPC::RLDICR, MVT::i64, Ops);
       return true;
     }
+
+    // It is not 16-bit imm that means we need two instructions at least if
+    // using "and" instruction. Try to exploit it with rotate mask instructions.
+    if (isRunOfOnes64(Imm64, MB, ME)) {
+      if (MB >= 32 && MB <= ME) {
+        //                MB  ME
+        // +----------------------+
+        // |xxxxxxxxxxx00011111000|
+        // +----------------------+
+        //  0         32         64
+        // We can only do it if the MB is larger than 32 and MB <= ME
+        // as RLWINM will replace the content of [0 - 32) with [32 - 64) even
+        // we didn't rotate it.
+        SDValue Ops[] = { Val, getI64Imm(0, dl), getI64Imm(MB - 32, dl),
+                          getI64Imm(ME - 32, dl) };
+        CurDAG->SelectNodeTo(N, PPC::RLWINM8, MVT::i64, Ops);
+        return true;
+      }
+      // TODO - handle it with rldicl + rldicl
+    }
   }
 
   return false;
 }
 
 // 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) {

llvm/test/CodeGen/PowerPC/and-mask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=powerpc64le-unknown-linux-gnu < %s | FileCheck %s
 
 ; mask 0xFFFFFFFE
 define i32 @test1(i32 %a) {
 ; CHECK-LABEL: test1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    lis 4, 32767
-; CHECK-NEXT:    ori 4, 4, 65535
-; CHECK-NEXT:    sldi 4, 4, 1
-; CHECK-NEXT:    and 3, 3, 4
+; CHECK-NEXT:    rlwinm 3, 3, 0, 0, 30
 ; CHECK-NEXT:    blr
   %and = and i32 %a, -2
   ret i32 %and
 }
 
 ; mask 0xFFFFFFFFFFFFFFF9
 define i64 @test2(i64 %a) {
 ; CHECK-LABEL: test2:

llvm/test/CodeGen/PowerPC/opt-cmp-inst-cr0-live.ll

 ; RUN: llc -verify-machineinstrs -print-before=peephole-opt -print-after=peephole-opt -mtriple=powerpc64-unknown-linux-gnu -o /dev/null 2>&1 < %s | FileCheck %s
 ; RUN: llc -verify-machineinstrs -print-before=peephole-opt -print-after=peephole-opt -mtriple=powerpc64le-unknown-linux-gnu -o /dev/null 2>&1 < %s | FileCheck %s
 
 ; CHECK-LABEL: fn1
 define signext i32 @fn1(i32 %baz) {
   %1 = mul nsw i32 %baz, 208
   %2 = zext i32 %1 to i64
   %3 = shl i64 %2, 48
   %4 = ashr exact i64 %3, 48
-; CHECK: ANDI8o killed {{[^,]+}}, 65520, implicit-def dead $cr0
+; CHECK: RLWINM8 killed {{[^,]+}}, 0, 16, 27
 ; CHECK: CMPLDI
 ; CHECK: BCC
 
 ; CHECK: ANDI8o {{[^,]+}}, 65520, implicit-def $cr0
-; CHECK: COPY $cr0
+; CHECK: COPY killed $cr0
 ; CHECK: BCC
   %5 = icmp eq i64 %4, 0
   br i1 %5, label %foo, label %bar
 
 foo:
   ret i32 1
 
 bar:

llvm/test/CodeGen/PowerPC/popcnt-zext.ll

; SLOW-NEXT:    blr
   ret i64 %z
 }
 
 define i64 @popa_i16_i64(i16 %x) {
 ; FAST-LABEL: popa_i16_i64:
 ; FAST:       # %bb.0:
 ; FAST-NEXT:    clrldi 3, 3, 48
 ; FAST-NEXT:    popcntd 3, 3
-; FAST-NEXT:    andi. 3, 3, 16
+; FAST-NEXT:    rlwinm 3, 3, 0, 27, 27
 ; FAST-NEXT:    blr
 ;
 ; SLOW-LABEL: popa_i16_i64:
 ; SLOW:       # %bb.0:
 ; SLOW-NEXT:    clrlwi 5, 3, 16
 ; SLOW-NEXT:    rlwinm 3, 3, 31, 0, 31
 ; SLOW-NEXT:    andi. 3, 3, 21845
 ; SLOW-NEXT:    lis 4, 13107

 ; SLOW-NEXT:    srwi 4, 3, 4
 ; SLOW-NEXT:    add 3, 3, 4
 ; SLOW-NEXT:    lis 4, 257
 ; SLOW-NEXT:    ori 5, 5, 3855
 ; SLOW-NEXT:    and 3, 3, 5
 ; SLOW-NEXT:    ori 4, 4, 257
 ; SLOW-NEXT:    mullw 3, 3, 4
 ; SLOW-NEXT:    srwi 3, 3, 24
-; SLOW-NEXT:    andi. 3, 3, 16
+; SLOW-NEXT:    rlwinm 3, 3, 0, 27, 27
 ; SLOW-NEXT:    blr
   %pop = call i16 @llvm.ctpop.i16(i16 %x)
   %z = zext i16 %pop to i64 ; SimplifyDemandedBits may turn zext (or sext) into aext
   %a = and i64 %z, 16
   ret i64 %a
 }
 
 declare i8 @llvm.ctpop.i8(i8) nounwind readnone
 declare i16 @llvm.ctpop.i16(i16) nounwind readnone
 declare i32 @llvm.ctpop.i32(i32) nounwind readnone
 declare i64 @llvm.ctpop.i64(i64) nounwind readnone