[PowerPC] Do not emit record-form rotates when record-form andi/andis suffices

[nemanjai]

Summary

This is a follow-up to the previous patch that eliminated some of the rotates. With this addition, we will also emit the record-form andis.
This patch increases the number of record-form rotates we eliminate by more than 70%.

[nemanjai]

Added the missing check for the record-form "and immediate shifted" as compares they feed are often redundant.

[inouehrs]

lib/Target/PowerPC/PPCInstrInfo.cpp

1911

MBInLoHWord/MEInLoHWord are more descriptive. I first think H means Hi before reading comment.
Also they can be bool, but it is ok if you prefer int for bool.

[nemanjai]

Change variable names as requested as it cleans up the code.

[nemanjai]

lib/Target/PowerPC/PPCInstrInfo.cpp

1911

Thanks, that's a good idea.

[nemanjai]

Ping. I'd like to get this committed. Can someone please review?

[inouehrs]

This patch increases the number of record-form rotates we emit by more than 70%.

Do you mean reducing the record-form rotates by 70%? If so, it is great!

lib/Target/PowerPC/PPCInstrInfo.cpp

1814

This change seems independent from other part of this patch. So this can be a separate patch.
Also it is nice to add an unit test for this part.

[nemanjai]

Remove the orthogonal change that allows us to optimize compares fed by record-form ANDIS.

[nemanjai]

In D44897#1215313, @inouehrs wrote:

This patch increases the number of record-form rotates we emit by more than 70%.

Do you mean reducing the record-form rotates by 70%? If so, it is great!

Oops! Yes this patch definitely causes a reduction in the number of record-form rotates :)
I updated the description (it was meant to say eliminate rather than emit).

[nemanjai]

lib/Target/PowerPC/PPCInstrInfo.cpp

1814

Both great points (this part being orthogonal as well as needing its own test case). Separate patch in https://reviews.llvm.org/D51353

[nemanjai]

@inouehrs I think I've addressed your comments adequately. Do you have any further comments or can you accept this revision?

[inouehrs]

LGTM

lib/Target/PowerPC/PPCInstrInfo.cpp

if (!MI && !Sub)
     return false;
 
   // The single candidate is called MI.
   if (!MI) MI = Sub;
 
   int NewOpC = -1;
   int MIOpC = MI->getOpcode();
   if (MIOpC == PPC::ANDIo || MIOpC == PPC::ANDIo8)
     NewOpC = MIOpC;
   else {
     NewOpC = PPC::getRecordFormOpcode(MIOpC);
     if (NewOpC == -1 && PPC::getNonRecordFormOpcode(MIOpC) != -1)
       NewOpC = MIOpC;
   }
 
   // FIXME: On the non-embedded POWER architectures, only some of the record
   // forms are fast, and we should use only the fast ones.
if (MIOpC != NewOpC) {
     // We need to be careful here: we're replacing one instruction with
     // another, and we need to make sure that we get all of the right
     // implicit uses and defs. On the other hand, the caller may be holding
     // an iterator to this instruction, and so we can't delete it (this is
     // specifically the case if this is the instruction directly after the
     // compare).
 
     // Rotates are expensive instructions. If we're emitting a record-form
-    // rotate that can just be an andi, we should just emit the andi.
-    if ((MIOpC == PPC::RLWINM || MIOpC == PPC::RLWINM8) &&
-        MI->getOperand(2).getImm() == 0) {
+    // rotate that can just be an andi/andis, we should just emit that.
+    if (MIOpC == PPC::RLWINM || MIOpC == PPC::RLWINM8) {
+      unsigned GPRRes = MI->getOperand(0).getReg();
+      int64_t SH = MI->getOperand(2).getImm();
       int64_t MB = MI->getOperand(3).getImm();
       int64_t ME = MI->getOperand(4).getImm();
-      if (MB < ME && MB >= 16) {
-        uint64_t Mask = ((1LLU << (32 - MB)) - 1) & ~((1LLU << (31 - ME)) - 1);
-        NewOpC = MIOpC == PPC::RLWINM ? PPC::ANDIo : PPC::ANDIo8;
+      // We can only do this if both the start and end of the mask are in the
+      // same halfword.
+      int MBInHWord = MB >= 16 ? 1 : 0;
+      int MEInHWord = ME >= 16 ? 1 : 0;
+      uint64_t Mask = ~0LLU;
+
+      if (MB <= ME && MBInHWord == MEInHWord && SH == 0) {
+        Mask = ((1LLU << (32 - MB)) - 1) & ~((1LLU << (31 - ME)) - 1);
+        // The mask value needs to shift right 16 if we're emitting andis.
+        Mask >>= MBInHWord == 0 ? 16 : 0;
+        NewOpC = MIOpC == PPC::RLWINM ?
+          (MBInHWord == 0 ? PPC::ANDISo : PPC::ANDIo) :
+          (MBInHWord == 0 ? PPC::ANDISo8 :PPC::ANDIo8);
+      } else if (MRI->use_empty(GPRRes) && (ME == 31) &&
+                 (ME - MB + 1 == SH) && (MB >= 16)) {
+        // If we are rotating by the exact number of bits as are in the mask
+        // and the mask is in the least significant bits of the register,
+        // that's just an andis. (as long as the GPR result has no uses).
+        Mask = ((1LLU << 32) - 1) & ~((1LLU << (32 - SH)) - 1);
+        Mask >>= 16;
+        NewOpC = MIOpC == PPC::RLWINM ? PPC::ANDISo :PPC::ANDISo8;
+      }
+      // If we've set the mask, we can transform.
+      if (Mask != ~0LLU) {
         MI->RemoveOperand(4);
         MI->RemoveOperand(3);
         MI->getOperand(2).setImm(Mask);
         NumRcRotatesConvertedToRcAnd++;
       }
     } else if (MIOpC == PPC::RLDICL && MI->getOperand(2).getImm() == 0) {
       int64_t MB = MI->getOperand(3).getImm();
       if (MB >= 48) {

test/CodeGen/PowerPC/noPermuteFormasking.ll

for.body.i.i.i.i.i.i.i.prol.loopexit:             ; preds = %entry
   br i1 %6, label %exitBB, label %for.body.i.i.i.i.i.i.i
 
 for.body.i.i.i.i.i.i.i:                           ; preds = %for.body.i.i.i.i.i.i.i.prol.loopexit
   unreachable
 
 exitBB: ; preds = %for.body.i.i.i.i.i.i.i.prol.loopexit
   ret void
 }
+
+define signext i32 @andis_bot(i32 signext %a, i32 signext %b) {
+; CHECK-LABEL: andis_bot:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    andis. 5, 3, 1
+; CHECK-NEXT:    li 5, 1
+; CHECK-NEXT:    isel 4, 4, 5, 2
+; CHECK-NEXT:    mullw 3, 4, 3
+; CHECK-NEXT:    extsw 3, 3
+; CHECK-NEXT:    blr
+entry:
+  %and = and i32 %a, 65536
+  %tobool = icmp eq i32 %and, 0
+  %mul = select i1 %tobool, i32 %b, i32 1
+  %cond = mul nsw i32 %mul, %a
+  ret i32 %cond
+}
+
+; Function Attrs: norecurse nounwind readnone
+define signext i32 @andis_mid(i32 signext %a, i32 signext %b) {
+; CHECK-LABEL: andis_mid:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    andis. 5, 3, 252
+; CHECK-NEXT:    li 5, 1
+; CHECK-NEXT:    isel 4, 4, 5, 2
+; CHECK-NEXT:    mullw 3, 4, 3
+; CHECK-NEXT:    extsw 3, 3
+; CHECK-NEXT:    blr
+entry:
+  %and = and i32 %a, 16515072
+  %tobool = icmp eq i32 %and, 0
+  %mul = select i1 %tobool, i32 %b, i32 1
+  %cond = mul nsw i32 %mul, %a
+  ret i32 %cond
+}
+
+; Function Attrs: norecurse nounwind readnone
+define signext i32 @andis_top(i32 signext %a, i32 signext %b) {
+; CHECK-LABEL: andis_top:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    andis. 5, 3, 64512
+; CHECK-NEXT:    li 5, 1
+; CHECK-NEXT:    isel 4, 4, 5, 2
+; CHECK-NEXT:    mullw 3, 4, 3
+; CHECK-NEXT:    extsw 3, 3
+; CHECK-NEXT:    blr
+entry:
+  %tobool = icmp ugt i32 %a, 67108863
+  %mul = select i1 %tobool, i32 1, i32 %b
+  %cond = mul nsw i32 %mul, %a
+  ret i32 %cond
+}

test/CodeGen/PowerPC/tail-dup-break-cfg.ll

 ; body2
 ; exit
 
 ;CHECK-LABEL: tail_dup_break_cfg:
 ;CHECK: mr [[TAGREG:[0-9]+]], 3
 ;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 1
 ;CHECK-NEXT: bc 12, 1, [[BODY1LABEL:[._0-9A-Za-z]+]]
 ;CHECK-NEXT: # %test2
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: bne 0, [[BODY2LABEL:[._0-9A-Za-z]+]]
 ;CHECK: [[EXITLABEL:[._0-9A-Za-z]+]]: # %exit
 ;CHECK: blr
 ;CHECK-NEXT: [[BODY1LABEL]]
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: beq 0, [[EXITLABEL]]
 ;CHECK-NEXT: [[BODY2LABEL:[._0-9A-Za-z]+]]:
 ;CHECK: b [[EXITLABEL]]
 define void @tail_dup_break_cfg(i32 %tag) {
 entry:
   br label %test1
 test1:
   %tagbit1 = and i32 %tag, 1

 
 ; The branch weights here hint that we shouldn't tail duplicate in this case.
 ;CHECK-LABEL: tail_dup_dont_break_cfg:
 ;CHECK: mr [[TAGREG:[0-9]+]], 3
 ;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 1
 ;CHECK-NEXT: bc 4, 1, [[TEST2LABEL:[._0-9A-Za-z]+]]
 ;CHECK-NEXT: # %body1
 ;CHECK: [[TEST2LABEL]]: # %test2
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: beq 0, [[EXITLABEL:[._0-9A-Za-z]+]]
 ;CHECK-NEXT: # %body2
 ;CHECK: [[EXITLABEL:[._0-9A-Za-z]+]]: # %exit
 ;CHECK: blr
 define void @tail_dup_dont_break_cfg(i32 %tag) {
 entry:
   br label %test1
 test1:

 ; CHECK-LABEL: tail_dup_no_succ
 ; CHECK: # %entry
 ; CHECK: # %v
 ; CHECK: # %ret
 ; CHECK: # %bb
 ; CHECK: # %succ
 ; CHECK: # %c
 ; CHECK: bl c
-; CHECK: rlwinm. {{[0-9]+}}, {{[0-9]+}}, 0, 29, 29
+; CHECK: andi. {{[0-9]+}}, {{[0-9]+}}, 4
 ; CHECK: beq
 ; CHECK: b
 define void @tail_dup_no_succ(i32 %tag) {
 entry:
   %tagbit1 = and i32 %tag, 1
   %tagbit1eq0 = icmp eq i32 %tagbit1, 0
   br i1 %tagbit1eq0, label %v, label %bb, !prof !2 ; %v very much more likely
 bb:

test/CodeGen/PowerPC/tail-dup-layout.ll

 ; and then check that the correct test has been duplicated into the end of
 ; the optional blocks and that the optional blocks are in the correct order.
 ;CHECK-LABEL: straight_test:
 ; test1 may have been merged with entry
 ;CHECK: mr [[TAGREG:[0-9]+]], 3
 ;CHECK: andi. {{[0-9]+}}, [[TAGREG:[0-9]+]], 1
 ;CHECK-NEXT: bc 12, 1, .[[OPT1LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: # %test2
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: bne 0, .[[OPT2LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[TEST3LABEL:[_0-9A-Za-z]+]]: # %test3
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 4
 ;CHECK-NEXT: bne 0, .[[OPT3LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[TEST4LABEL:[_0-9A-Za-z]+]]: # %test4
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 28, 28
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 8
 ;CHECK-NEXT: bne 0, .[[OPT4LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[EXITLABEL:[_0-9A-Za-z]+]]: # %exit
 ;CHECK: blr
 ;CHECK-NEXT: .[[OPT1LABEL]]:
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: beq 0, .[[TEST3LABEL]]
 ;CHECK-NEXT: .[[OPT2LABEL]]:
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 4
 ;CHECK-NEXT: beq 0, .[[TEST4LABEL]]
 ;CHECK-NEXT: .[[OPT3LABEL]]:
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 28, 28
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 8
 ;CHECK-NEXT: beq 0, .[[EXITLABEL]]
 ;CHECK-NEXT: .[[OPT4LABEL]]:
 ;CHECK: b .[[EXITLABEL]]
 
 define void @straight_test(i32 %tag) {
 entry:
   br label %test1
 test1:

 ; and then check that the correct test has been duplicated into the end of
 ; the optional blocks and that the optional blocks are in the correct order.
 ;CHECK-LABEL: straight_test_50:
 ; test1 may have been merged with entry
 ;CHECK: mr [[TAGREG:[0-9]+]], 3
 ;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 1
 ;CHECK-NEXT: bc 12, 1, .[[OPT1LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: # %test2
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: bne 0, .[[OPT2LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[TEST3LABEL:[_0-9A-Za-z]+]]: # %test3
-;CHECK-NEXT: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK-NEXT: andi. {{[0-9]+}}, [[TAGREG]], 4
 ;CHECK-NEXT: bne 0, .[[OPT3LABEL:[_0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[EXITLABEL:[_0-9A-Za-z]+]]: # %exit
 ;CHECK: blr
 ;CHECK-NEXT: .[[OPT1LABEL]]:
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: beq 0, .[[TEST3LABEL]]
 ;CHECK-NEXT: .[[OPT2LABEL]]:
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 4
 ;CHECK-NEXT: beq 0, .[[EXITLABEL]]
 ;CHECK-NEXT: .[[OPT3LABEL]]:
 ;CHECK: b .[[EXITLABEL]]
 
 define void @straight_test_50(i32 %tag) {
 entry:
   br label %test1
 test1:

 ;CHECK: addi
 ;CHECK-O2: .[[CHECKLABEL:[._0-9A-Za-z]+]]: # %for.check
 ;CHECK: lwz [[TAGREG:[0-9]+]], 0([[TAGPTRREG]])
 ;CHECK-O3: .[[CHECKLABEL:[._0-9A-Za-z]+]]: # %for.check
 ;CHECK: # %bb.{{[0-9]+}}: # %test1
 ;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 1
 ;CHECK-NEXT: bc 12, 1, .[[OPT1LABEL:[._0-9A-Za-z]+]]
 ;CHECK-NEXT: # %test2
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: bne 0, .[[OPT2LABEL:[._0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[TEST3LABEL:[._0-9A-Za-z]+]]: # %test3
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 4
 ;CHECK-NEXT: bne 0, .[[OPT3LABEL:[._0-9A-Za-z]+]]
 ;CHECK-NEXT: .[[TEST4LABEL:[._0-9A-Za-z]+]]: # %{{(test4|optional3)}}
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 28, 28
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 8
 ;CHECK-NEXT: beq 0, .[[LATCHLABEL]]
 ;CHECK-NEXT: b .[[OPT4LABEL:[._0-9A-Za-z]+]]
 ;CHECK: [[OPT1LABEL]]
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 30, 30
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 2
 ;CHECK-NEXT: beq 0, .[[TEST3LABEL]]
 ;CHECK-NEXT: .[[OPT2LABEL]]
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 29, 29
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 4
 ;CHECK-NEXT: beq 0, .[[TEST4LABEL]]
 ;CHECK-NEXT: .[[OPT3LABEL]]
-;CHECK: rlwinm. {{[0-9]+}}, [[TAGREG]], 0, 28, 28
+;CHECK: andi. {{[0-9]+}}, [[TAGREG]], 8
 ;CHECK-NEXT: beq 0, .[[LATCHLABEL]]
 ;CHECK: [[OPT4LABEL]]:
 ;CHECK: b .[[LATCHLABEL]]
 define void @loop_test(i32* %tags, i32 %count) {
 entry:
   br label %for.check
 for.check:
   %count.loop = phi i32 [%count, %entry], [%count.sub, %for.latch]

 ; "unavoidable" blocks.
 ; CHECK-LABEL: avoidable_test:
 ; CHECK: # %bb.{{[0-9]+}}: # %entry
 ; CHECK: andi.
 ; CHECK: # %bb.{{[0-9]+}}: # %test2
 ; Make sure then2 falls through from test2
 ; CHECK-NOT: # %{{[-_a-zA-Z0-9]+}}
 ; CHECK: # %bb.{{[0-9]+}}: # %then2
-; CHECK: rlwinm. {{[0-9]+}}, {{[0-9]+}}, 0, 29, 29
+; CHECK: andi. {{[0-9]+}}, {{[0-9]+}}, 4
 ; CHECK: # %else1
 ; CHECK: bl a
 ; CHECK: bl a
 ; Make sure then2 was copied into else1
-; CHECK: rlwinm. {{[0-9]+}}, {{[0-9]+}}, 0, 29, 29
+; CHECK: andi. {{[0-9]+}}, {{[0-9]+}}, 4
 ; CHECK: # %end1
 ; CHECK: bl d
 ; CHECK: # %else2
 ; CHECK: bl c
 ; CHECK: # %end2
 define void @avoidable_test(i32 %tag) {
 entry:
   br label %test1