[ARM] Allow TBB formation for Thumb1 in more cases.

[efriedma]

Summary

Requiring the input of the first shift to be killed is more conservative than necessary; we can just insert an explicit copy instead.

Thinking about it a bit more, I'm not sure it's really worth complicating this code to catch a few more cases; it's not uncommon (I found 7 instances in a relatively small codebase), but it's not really common either. That said, I have another patch that breaks a couple regression tests without this fix.

[dmgreen]

Yep, this came up a few times in the tests I ran. Looks like a nice improvement, and I don't think it complicate things too much.

test/CodeGen/Thumb/tbb-live-index.mir

9

Nit: Can you clean up the testcase a little.

[efriedma]

Looking over this again, I'm not doing quite what the comment says I'm doing. Specifically, the insertion point for the MOVS is wrong: it has to be inserted at the point of the shift, not the TBB, because Thumb1OrigIdx could be killed by some other instruction in the block.

lib/Target/ARM/ARMConstantIslandPass.cpp

if (!MI->getOperand(0).isKill()) // FIXME: needed now?
       continue;
 
     unsigned DeadSize = 0;
     bool CanDeleteLEA = false;
     bool BaseRegKill = false;
 
     unsigned IdxReg = ~0U;
     bool IdxRegKill = true;
+    bool Thumb1IdxMov = false;
+    unsigned Thumb1OrigIdx = ~0U;
     if (isThumb2) {
       IdxReg = MI->getOperand(1).getReg();
       IdxRegKill = MI->getOperand(1).isKill();
 
       bool PreservedBaseReg =
         preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
       if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
         continue;
     } else {
       // We're in thumb-1 mode, so we must have something like:
       //   %idx = tLSLri %idx, 2
       //   %base = tLEApcrelJT
       //   %t = tLDRr %base, %idx
       unsigned BaseReg = User.MI->getOperand(0).getReg();
 
       if (User.MI->getIterator() == User.MI->getParent()->begin())
         continue;
       MachineInstr *Shift = User.MI->getPrevNode();
       if (Shift->getOpcode() != ARM::tLSLri ||
-          Shift->getOperand(3).getImm() != 2 ||
-          !Shift->getOperand(2).isKill())
+          Shift->getOperand(3).getImm() != 2)
         continue;
+
+      // The unshifted "idx" may or may not be dead; if it isn't, treat the
+      // shift as if it was transformed from "%idx = tLSLri %idxOrig, 2" to
+      // "%idx = tMOVSr %idxOrig; %idx = tLSLri %idx, 2".
+      //
+      // (tTBB_JT needs to clobber the register because it eventually lowers
+      // to a sequence which includes "add %idx, pc".)
+      if (!Shift->getOperand(2).isKill()) {
+        if (Shift->getOperand(2).isUndef())
+          continue;
+        Thumb1IdxMov = true;
+        Thumb1OrigIdx = Shift->getOperand(2).getReg();
+        IdxReg = Shift->getOperand(0).getReg();
+      } else {
         IdxReg = Shift->getOperand(2).getReg();
+      }
       unsigned ShiftedIdxReg = Shift->getOperand(0).getReg();
 
       // It's important that IdxReg is live until the actual TBB/TBH. Most of
       // the range is checked later, but the LEA might still clobber it and not
       // actually get removed.
       if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
         continue;
 
for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
 
     LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI);
     MachineInstr *CPEMI = User.CPEMI;
     unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
     if (!isThumb2)
       Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
 
     MachineBasicBlock::iterator MI_JT = MI;
+    if (Thumb1IdxMov) {
+      MachineInstr *NewMOVS =
+          BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(ARM::tMOVSr), IdxReg)
+              .addReg(Thumb1OrigIdx);
+      LLVM_DEBUG(dbgs() << "Inserting extra tMOVSr: " << *NewMOVS);
+      DeadSize -= 2;
+    }
     MachineInstr *NewJTMI =
         BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
             .addReg(User.MI->getOperand(0).getReg(),
                     getKillRegState(BaseRegKill))
             .addReg(IdxReg, getKillRegState(IdxRegKill))
             .addJumpTableIndex(JTI, JTOP.getTargetFlags())
             .addImm(CPEMI->getOperand(0).getImm());
     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI);

test/CodeGen/Thumb/tbb-live-index.mir

+# RUN: llc -run-pass arm-cp-islands %s -o - | FileCheck %s
+
+# Make sure we form a TBB in this case.
+# CHECK: $r0 = tMOVSr $r5, implicit-def $cpsr
+# CHECK: tTBB_JT $pc, killed $r0, %jump-table.0, 0
+
+--- |
+  ; ModuleID = '<stdin>'
+  source_filename = "-"
+  target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+  target triple = "thumbv6m-unknown-unknown-eabi"
+  
+  ; Function Attrs: nounwind
+  define dso_local void @f(i32 %n, i32 %x, void (i32)* nocapture %f) local_unnamed_addr #0 {
+  entry:
+    %cmp13 = icmp sgt i32 %n, 0
+    br i1 %cmp13, label %for.body.preheader, label %for.cond.cleanup
+  
+  for.body.preheader:                               ; preds = %entry
+    br label %for.body
+  
+  for.cond.cleanup:                                 ; preds = %for.inc, %entry
+    ret void
+  
+  for.body:                                         ; preds = %for.body.preheader, %for.inc
+    %lsr.iv = phi i32 [ %n, %for.body.preheader ], [ %lsr.iv.next, %for.inc ]
+    switch i32 %x, label %for.inc [
+      i32 0, label %sw.bb
+      i32 1, label %sw.bb1
+      i32 2, label %sw.bb2
+      i32 3, label %sw.bb3
+      i32 4, label %sw.bb4
+      i32 5, label %sw.bb5
+    ]
+  
+  sw.bb:                                            ; preds = %for.body
+    tail call void %f(i32 1) #1
+    br label %sw.bb1
+  
+  sw.bb1:                                           ; preds = %sw.bb, %for.body
+    tail call void %f(i32 1) #1
+    br label %sw.bb2
+  
+  sw.bb2:                                           ; preds = %sw.bb1, %for.body
+    tail call void %f(i32 2) #1
+    br label %sw.bb3
+  
+  sw.bb3:                                           ; preds = %sw.bb2, %for.body
+    tail call void %f(i32 3) #1
+    br label %sw.bb4
+  
+  sw.bb4:                                           ; preds = %sw.bb3, %for.body
+    tail call void %f(i32 5) #1
+    br label %sw.bb5
+  
+  sw.bb5:                                           ; preds = %sw.bb4, %for.body
+    tail call void %f(i32 8) #1
+    br label %for.inc
+  
+  for.inc:                                          ; preds = %sw.bb5, %for.body
+    %lsr.iv.next = add i32 %lsr.iv, -1
+    %exitcond = icmp eq i32 %lsr.iv.next, 0
+    br i1 %exitcond, label %for.cond.cleanup, label %for.body
+  }
+  
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #1
+  
+  attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m0" "target-features"="+armv6-m,+strict-align,+thumb-mode" "unsafe-fp-math"="false" "use-soft-float"="false" }
+  attributes #1 = { nounwind }
+  
+  !llvm.module.flags = !{!0, !1}
+  !llvm.ident = !{!2}
+  
+  !0 = !{i32 1, !"wchar_size", i32 4}
+  !1 = !{i32 1, !"min_enum_size", i32 4}
+  !2 = !{!"clang version 8.0.0 (https://git.llvm.org/git/clang.git/ 2abe10f0902311fdb2896d3c6223787f51049fac) (llvm/ 07ee4139395c993f231e6ee76211468ff3e8bde8)"}
+
+...
+---
+name:            f
+alignment:       1
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+registers:       
+liveins:         
+  - { reg: '$r0', virtual-reg: '' }
+  - { reg: '$r1', virtual-reg: '' }
+  - { reg: '$r2', virtual-reg: '' }
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       16
+  offsetAdjustment: 0
+  maxAlignment:    4
+  adjustsStack:    true
+  hasCalls:        true
+  stackProtector:  ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      
+stack:           
+  - { id: 0, name: '', type: spill-slot, offset: -4, size: 4, alignment: 4, 
+      stack-id: 0, callee-saved-register: '$lr', callee-saved-restored: false, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, name: '', type: spill-slot, offset: -8, size: 4, alignment: 4, 
+      stack-id: 0, callee-saved-register: '$r6', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 2, name: '', type: spill-slot, offset: -12, size: 4, alignment: 4, 
+      stack-id: 0, callee-saved-register: '$r5', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 3, name: '', type: spill-slot, offset: -16, size: 4, alignment: 4, 
+      stack-id: 0, callee-saved-register: '$r4', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+constants:       
+jumpTable:       
+  kind:            inline
+  entries:         
+    - id:              0
+      blocks:          [ '%bb.4', '%bb.5', '%bb.6', '%bb.7', '%bb.8', '%bb.9' ]
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x50000000), %bb.11(0x30000000)
+    liveins: $r0, $r1, $r2, $r4, $r5, $r6, $lr
+  
+    frame-setup tPUSH 14, $noreg, killed $r4, killed $r5, killed $r6, killed $lr, implicit-def $sp, implicit $sp
+    frame-setup CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup CFI_INSTRUCTION offset $lr, -4
+    frame-setup CFI_INSTRUCTION offset $r6, -8
+    frame-setup CFI_INSTRUCTION offset $r5, -12
+    frame-setup CFI_INSTRUCTION offset $r4, -16
+    tCMPi8 $r0, 1, 14, $noreg, implicit-def $cpsr
+    tBcc %bb.11, 11, killed $cpsr
+  
+  bb.1:
+    successors: %bb.2(0x80000000)
+    liveins: $r0, $r1, $r2
+  
+    $r4 = tMOVr $r2, 14, $noreg
+    $r5 = tMOVr $r1, 14, $noreg
+    $r6 = tMOVr $r0, 14, $noreg
+  
+  bb.2.for.body:
+    successors: %bb.10(0x12492492), %bb.3(0x6db6db6e)
+    liveins: $r4, $r5, $r6
+  
+    tCMPi8 renamable $r5, 5, 14, $noreg, implicit-def $cpsr
+    tBcc %bb.10, 8, killed $cpsr
+  
+  bb.3.for.body:
+    successors: %bb.4(0x15555555), %bb.5(0x15555555), %bb.6(0x15555555), %bb.7(0x15555555), %bb.8(0x15555555), %bb.9(0x15555555)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tLSLri renamable $r5, 2, 14, $noreg
+    renamable $r1 = tLEApcrelJT %jump-table.0, 14, $noreg
+    renamable $r0 = tLDRr killed renamable $r1, killed renamable $r0, 14, $noreg :: (load 4 from jump-table)
+    tBR_JTr killed renamable $r0, %jump-table.0
+  
+  bb.4.sw.bb:
+    successors: %bb.5(0x80000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tMOVi8 1, 14, $noreg
+    tBLXr 14, $noreg, renamable $r4, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit-def $sp
+  
+  bb.5.sw.bb1:
+    successors: %bb.6(0x80000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tMOVi8 1, 14, $noreg
+    tBLXr 14, $noreg, renamable $r4, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit-def $sp
+  
+  bb.6.sw.bb2:
+    successors: %bb.7(0x80000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tMOVi8 2, 14, $noreg
+    tBLXr 14, $noreg, renamable $r4, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit-def $sp
+  
+  bb.7.sw.bb3:
+    successors: %bb.8(0x80000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tMOVi8 3, 14, $noreg
+    tBLXr 14, $noreg, renamable $r4, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit-def $sp
+  
+  bb.8.sw.bb4:
+    successors: %bb.9(0x80000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tMOVi8 5, 14, $noreg
+    tBLXr 14, $noreg, renamable $r4, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit-def $sp
+  
+  bb.9.sw.bb5:
+    successors: %bb.10(0x80000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r0, dead $cpsr = tMOVi8 8, 14, $noreg
+    tBLXr 14, $noreg, renamable $r4, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit-def $sp
+  
+  bb.10.for.inc:
+    successors: %bb.11(0x04000000), %bb.2(0x7c000000)
+    liveins: $r4, $r5, $r6
+  
+    renamable $r6, $cpsr = tSUBi3 killed renamable $r6, 1, 14, $noreg
+    tBcc %bb.2, 1, killed $cpsr
+  
+  bb.11.for.cond.cleanup:
+    tPOP_RET 14, $noreg, def $r4, def $r5, def $r6, def $pc, implicit-def $sp, implicit $sp
+
+...