[PowerPC] Collapse RLDICL/RLDICR into RLDIC when possible

[nemanjai]

Summary

Generally speaking, we lower to an optimal rotate sequence for nodes visible in the SDAG. However, there are instances where the two rotates are not visible at ISEL time - most notably those in a very common sequence when lowering switch statements to jump tables.
A common situation is a switch on a 32-bit integer. This value has to have the upper 32 bits cleared and because jump table offsets are word offsets, the value needs to be shifted left by 2 bits. We currently emit the clear and the left shift as two separate instructions, but this is not needed as we can lower it to a single RLDIC.
This patch just cleans that up.

[nemanjai]

Cleaned up the comments and the MB parameter for RLDIC does not need to include the shift that was originally on the RLDICL.

[stefanp]

The patch does what we want it to do in most cases (including the example that motivated it) but some boundary conditions need to be considered before it is safe in all cases.

lib/Target/PowerPC/PPCMIPeephole.cpp

51

nit:
collapsed

785

The value for NewMB can be negative.
For example:

%1:g8rc = RLDICL %0, 10, 1
%2:g8rc = RLDICR %1, 10, 43

In this case NewMB = -9
I changed the testcase you provided and used the above two lines and I get an assert.

We may still be able to handle the negative case (because this is a rotate) but it may require another if statement and special handling.

793

The value for (63 - NewSH) can also be negative and I think it needs to be a special case.
Each shift has to be less than or equal to 63 but the sum of two shifts can be greater than 63.

test/CodeGen/PowerPC/collapse-rotates.mir

54

Had to delete this line on the machine I was running on to get this test to pass...
The error is:

error: YAML:53:23: unknown key 'machineFunctionInfo'
machineFunctionInfo: {}

I'm not sure what the issue is here but I feel like that line is not universally supported.

[nemanjai]

lib/Target/PowerPC/PPCMIPeephole.cpp

51

Good catch, thanks.

793

These are very good points. I will add a check to bail out if either NewMB or NewSH are larger than 63.

test/CodeGen/PowerPC/collapse-rotates.mir

54

I am not sure what that's about. Perhaps you were on an older revision where that wasn't part of MIR?

[nemanjai]

Added a check for wrapping in the computation of the new shift amount and mask start bit.

[stefanp]

LGTM.
The one very minor comment I have I think can be addressed on commit.

test/CodeGen/PowerPC/collapse-rotates.mir

54

I have tried to reproduce this since but I have not been able to. I would say don't worry about this.
I assume the issue was on my end.

test/CodeGen/PowerPC/jump-tables-collapse-rotate.ll

3

nit:
This is something that I find helps with readability of the test case.
Is it possible to add: -ppc-asm-full-reg-names

lib/Target/PowerPC/PPCMIPeephole.cpp

 STATISTIC(NumOptADDLIs, "Number of optimized ADD instruction fed by LI");
 STATISTIC(NumConvertedToImmediateForm,
           "Number of instructions converted to their immediate form");
 STATISTIC(NumFunctionsEnteredInMIPeephole,
           "Number of functions entered in PPC MI Peepholes");
 STATISTIC(NumFixedPointIterations,
           "Number of fixed-point iterations converting reg-reg instructions "
           "to reg-imm ones");
+STATISTIC(NumRotatesCollapsed,
+          "Number of pairs of rotate left, clear left/right colapsed");
 
 static cl::opt<bool>
 FixedPointRegToImm("ppc-reg-to-imm-fixed-point", cl::Hidden, cl::init(true),
                    cl::desc("Iterate to a fixed point when attempting to "
                             "convert reg-reg instructions to reg-imm"));
 
 static cl::opt<bool>
 ConvertRegReg("ppc-convert-rr-to-ri", cl::Hidden, cl::init(true),
for (MachineInstr &MI : MBB) {
         BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(PPC::COPY),
                 MI.getOperand(0).getReg())
             .add(Op1);
         ToErase = &MI;
         Simplified = true;
         NumOptADDLIs++;
         break;
       }
+      case PPC::RLDICR: {
+        // We miss the opportunity to emit an RLDIC when lowering jump tables
+        // since ISEL sees only a single basic block. When selecting, the clear
+        // and shift left will be in different blocks.
+        unsigned SrcReg = MI.getOperand(1).getReg();
+        if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
+          break;
+
+        MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
+        if (SrcMI->getOpcode() != PPC::RLDICL)
+          break;
+        MachineOperand MOpSHSrc = SrcMI->getOperand(2);
+        MachineOperand MOpMBSrc = SrcMI->getOperand(3);
+        MachineOperand MOpSHMI = MI.getOperand(2);
+        MachineOperand MOpMEMI = MI.getOperand(3);
+        if (!(MOpSHSrc.isImm() && MOpMBSrc.isImm() &&
+              MOpSHMI.isImm() && MOpMEMI.isImm()))
+          break;
+        uint64_t SHSrc = MOpSHSrc.getImm();
+        uint64_t MBSrc = MOpMBSrc.getImm();
+        uint64_t SHMI = MOpSHMI.getImm();
+        uint64_t MEMI = MOpMEMI.getImm();
+
+        // We have a rotate left and clear left feeding a rotate left and clear
+        // right. The bits that remain after shifting by (SHSrc + SHMI) span
+        // from MBSrc to MEMI. The bits that remain with RLDIC span from
+        // MBSrc to (63 - (SHSrc + SHMI)). So we need to make sure that
+        // (63 - (SHSrc + SHMI)) == MEMI.
+        if ((63 - (SHSrc + SHMI)) != MEMI)
+          break;
+
+        LLVM_DEBUG(dbgs() << "Converting pair: ");
+        LLVM_DEBUG(SrcMI->dump());
+        LLVM_DEBUG(MI.dump());
+
+        MI.setDesc(TII->get(PPC::RLDIC));
+        MI.getOperand(1).setReg(SrcMI->getOperand(1).getReg());
+        MI.getOperand(2).setImm(SHSrc + SHMI);
+        MI.getOperand(3).setImm(MBSrc - (SHSrc + SHMI));
+
+        LLVM_DEBUG(dbgs() << "To: ");
+        LLVM_DEBUG(MI.dump());
+        NumRotatesCollapsed++;
+        break;
+      }
       }
     }
 
     // If the last instruction was marked for elimination,
     // remove it now.
     if (ToErase) {
       ToErase->eraseFromParent();
       ToErase = nullptr;

test/CodeGen/PowerPC/collapse-rotates.mir

+# RUN: llc -mtriple=powerpc64le--linux-gnu -start-before ppc-mi-peepholes %s -o - -verify-machineinstrs | FileCheck %s
+
+--- |
+  ; ModuleID = 'b.ll'
+  source_filename = "b.ll"
+  target datalayout = "e-m:e-i64:64-n32:64"
+  
+  define dso_local i64 @test(i64 %l) {
+  entry:
+    %shl = shl i64 %l, 3
+    ret i64 %shl
+  }
+
+...
+---
+name:            test
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:       
+  - { id: 0, class: g8rc, preferred-register: '' }
+  - { id: 1, class: g8rc, preferred-register: '' }
+  - { id: 2, class: g8rc, preferred-register: '' }
+liveins:         
+  - { reg: '$x3', virtual-reg: '%0' }
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 4294967295
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:           []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    liveins: $x3
+  
+    %0:g8rc = COPY $x3
+    %1:g8rc = RLDICL %0, 2, 32
+    %2:g8rc = RLDICR %1, 3, 58
+    $x3 = COPY %2
+    BLR8 implicit $lr8, implicit $rm, implicit $x3
+
+...
+# CHECK: rldic 3, 3, 5, 27

test/CodeGen/PowerPC/jump-tables-collapse-rotate.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -o - %s | FileCheck %s
+
+; Function Attrs: nounwind
+define dso_local zeroext i32 @test(i32 signext %l) {
+; CHECK-LABEL: test:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    mflr 0
+; CHECK-NEXT:    std 0, 16(1)
+; CHECK-NEXT:    stdu 1, -32(1)
+; CHECK-NEXT:    .cfi_def_cfa_offset 32
+; CHECK-NEXT:    .cfi_offset lr, 16
+; CHECK-NEXT:    addi 3, 3, -1
+; CHECK-NEXT:    cmplwi 3, 5
+; CHECK-NEXT:    bgt 0, .LBB0_3
+; CHECK-NEXT:  # %bb.1: # %entry
+; CHECK-NEXT:    addis 4, 2, .LC0@toc@ha
+; CHECK-NEXT:    rldic 3, 3, 2, 30
+; CHECK-NEXT:    ld 4, .LC0@toc@l(4)
+; CHECK-NEXT:    lwax 3, 3, 4
+; CHECK-NEXT:    add 3, 3, 4
+; CHECK-NEXT:    mtctr 3
+; CHECK-NEXT:    bctr
+; CHECK-NEXT:  .LBB0_2: # %sw.bb
+; CHECK-NEXT:    li 3, 2
+; CHECK-NEXT:    bl test1
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    b .LBB0_10
+; CHECK-NEXT:  .LBB0_3: # %sw.default
+; CHECK-NEXT:    li 3, 1
+; CHECK-NEXT:    bl test1
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    bl test3
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    b .LBB0_10
+; CHECK-NEXT:  .LBB0_4: # %sw.bb3
+; CHECK-NEXT:    li 3, 3
+; CHECK-NEXT:    b .LBB0_9
+; CHECK-NEXT:  .LBB0_5: # %sw.bb5
+; CHECK-NEXT:    li 3, 4
+; CHECK-NEXT:    bl test2
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    bl test3
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    b .LBB0_10
+; CHECK-NEXT:  .LBB0_6: # %sw.bb8
+; CHECK-NEXT:    li 3, 5
+; CHECK-NEXT:    bl test4
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    b .LBB0_10
+; CHECK-NEXT:  .LBB0_7: # %sw.bb10
+; CHECK-NEXT:    li 3, 66
+; CHECK-NEXT:    bl test4
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    bl test1
+; CHECK-NEXT:    nop
+; CHECK-NEXT:    b .LBB0_10
+; CHECK-NEXT:  .LBB0_8: # %sw.bb13
+; CHECK-NEXT:    li 3, 66
+; CHECK-NEXT:  .LBB0_9: # %return
+; CHECK-NEXT:    bl test2
+; CHECK-NEXT:    nop
+; CHECK-NEXT:  .LBB0_10: # %return
+; CHECK-NEXT:    clrldi 3, 3, 32
+; CHECK-NEXT:    addi 1, 1, 32
+; CHECK-NEXT:    ld 0, 16(1)
+; CHECK-NEXT:    mtlr 0
+; CHECK-NEXT:    blr
+entry:
+  switch i32 %l, label %sw.default [
+    i32 1, label %sw.bb
+    i32 2, label %sw.bb3
+    i32 3, label %sw.bb5
+    i32 4, label %sw.bb8
+    i32 5, label %sw.bb10
+    i32 6, label %sw.bb13
+  ]
+
+sw.default:                                       ; preds = %entry
+  %call = tail call signext i32 @test1(i32 signext 1)
+  %call1 = tail call signext i32 @test3(i32 signext %call)
+  br label %return
+
+sw.bb:                                            ; preds = %entry
+  %call2 = tail call signext i32 @test1(i32 signext 2)
+  br label %return
+
+sw.bb3:                                           ; preds = %entry
+  %call4 = tail call signext i32 @test2(i32 signext 3)
+  br label %return
+
+sw.bb5:                                           ; preds = %entry
+  %call6 = tail call signext i32 @test2(i32 signext 4)
+  %call7 = tail call signext i32 @test3(i32 signext %call6)
+  br label %return
+
+sw.bb8:                                           ; preds = %entry
+  %call9 = tail call signext i32 @test4(i32 signext 5)
+  br label %return
+
+sw.bb10:                                          ; preds = %entry
+  %call11 = tail call signext i32 @test4(i32 signext 66)
+  %call12 = tail call signext i32 @test1(i32 signext %call11)
+  br label %return
+
+sw.bb13:                                          ; preds = %entry
+  %call14 = tail call signext i32 @test2(i32 signext 66)
+  br label %return
+
+return:                                           ; preds = %sw.bb13, %sw.bb10, %sw.bb8, %sw.bb5, %sw.bb3, %sw.bb, %sw.default
+  %retval.0 = phi i32 [ %call1, %sw.default ], [ %call14, %sw.bb13 ], [ %call12, %sw.bb10 ], [ %call9, %sw.bb8 ], [ %call7, %sw.bb5 ], [ %call4, %sw.bb3 ], [ %call2, %sw.bb ]
+  ret i32 %retval.0
+}
+
+declare signext i32 @test3(i32 signext)
+
+declare signext i32 @test1(i32 signext)
+
+declare signext i32 @test2(i32 signext)
+
+declare signext i32 @test4(i32 signext)