[ARM][MachineOutliner] Add LR RegSave mode.

[yroux]

Summary

Outline chunks of code which need to save and restore the link register when a spare register can be used to it.

[samparker]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5653

Is PC already covered by getReservedRegs or do we need to check here too? Also do you mean tGPR? That seems too restrictive for Thumb2. I think it would be better, easier and safer to just use the rGPR for both.

[yroux]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5653

Yes PC is marked as reserved by getReservedRegs, but you're right rGPR is a much better choice

[yroux]

Change register class to rGPR for both modes and updated testcase

[samparker]

I just run some numbers on the test suite and the results are already looking very good with 1.4% geomean reduction for T32, so many thanks! Is this the final patch of the set?

[yroux]

Thanks :)

No there is 3 more patches in the set, one for the default mode (save/restore of lr on the stack), one which will add the support of calls in the outlined regions and the most tricky one which will fixup the stack to handle load/store. In the end we should reach ~3% of size reduction in T32 and ~5% in ARM (this is what I observed on average for various benchs).

So, I'll submit the next 2 patches in the coming days and the last one might take a bit longer to be reabased and validated, but will be out soon.

Thanks for the reviews!

[samparker]

Great stuff, I look forward to the other patches then :)

llvm/lib/Target/ARM/ARMBaseInstrInfo.h

public:
   void buildOutlinedFrame(MachineBasicBlock &MBB, MachineFunction &MF,
                           const outliner::OutlinedFunction &OF) const override;
   MachineBasicBlock::iterator
   insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                      MachineBasicBlock::iterator &It, MachineFunction &MF,
                      const outliner::Candidate &C) const override;
 
 private:
+  /// Returns an unused general-purpose register which can be used for
+  /// constructing an outlined call if one exists. Returns 0 otherwise.
+  unsigned findRegisterToSaveLRTo(const outliner::Candidate &C) const;
+
   unsigned getInstBundleLength(const MachineInstr &MI) const;
 
   int getVLDMDefCycle(const InstrItineraryData *ItinData,
                       const MCInstrDesc &DefMCID,
                       unsigned DefClass,
                       unsigned DefIdx, unsigned DefAlign) const;
   int getLDMDefCycle(const InstrItineraryData *ItinData,
                      const MCInstrDesc &DefMCID,

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

 ///
 /// +-------------------------+--------+-----+
 /// |                         | Thumb2 | ARM |
 /// +-------------------------+--------+-----+
 /// | Call overhead in Bytes  |      4 |   4 |
 /// | Frame overhead in Bytes |      4 |   4 |
 /// | Stack fixup required    |     No |  No |
 /// +-------------------------+--------+-----+
+///
+/// \p MachineOutlinerRegSave implies that the function should be called with a
+/// save and restore of LR to an available register. This allows us to avoid
+/// stack fixups. Note that this outlining variant is compatible with the
+/// NoLRSave case.
+///
+/// That is,
+///
+/// I1     Save LR                    OUTLINED_FUNCTION:
+/// I2 --> BL OUTLINED_FUNCTION       I1
+/// I3     Restore LR                 I2
+///                                   I3
+///                                   BX LR
+///
+/// +-------------------------+--------+-----+
+/// |                         | Thumb2 | ARM |
+/// +-------------------------+--------+-----+
+/// | Call overhead in Bytes  |      8 |  12 |
+/// | Frame overhead in Bytes |      2 |   4 |
+/// | Stack fixup required    |     No |  No |
+/// +-------------------------+--------+-----+
 
 enum MachineOutlinerClass {
   MachineOutlinerTailCall,
   MachineOutlinerThunk,
-  MachineOutlinerNoLRSave
+  MachineOutlinerNoLRSave,
+  MachineOutlinerRegSave
 };
 
 enum MachineOutlinerMBBFlags {
   LRUnavailableSomewhere = 0x2,
   HasCalls = 0x4,
   UnsafeRegsDead = 0x8
 };
 
 struct OutlinerCosts {
   const int CallTailCall;
   const int FrameTailCall;
   const int CallThunk;
   const int FrameThunk;
   const int CallNoLRSave;
   const int FrameNoLRSave;
+  const int CallRegSave;
+  const int FrameRegSave;
 
   OutlinerCosts(const ARMSubtarget &target)
       : CallTailCall(target.isThumb() ? 4 : 4),
         FrameTailCall(target.isThumb() ? 0 : 0),
         CallThunk(target.isThumb() ? 4 : 4),
         FrameThunk(target.isThumb() ? 0 : 0),
         CallNoLRSave(target.isThumb() ? 4 : 4),
-        FrameNoLRSave(target.isThumb() ? 4 : 4) {}
+        FrameNoLRSave(target.isThumb() ? 4 : 4),
+        CallRegSave(target.isThumb() ? 8 : 12),
+        FrameRegSave(target.isThumb() ? 2 : 4) {}
 };
 
+unsigned
+ARMBaseInstrInfo::findRegisterToSaveLRTo(const outliner::Candidate &C) const {
+  assert(C.LRUWasSet && "LRU wasn't set?");
+  MachineFunction *MF = C.getMF();
+  const ARMBaseRegisterInfo *ARI = static_cast<const ARMBaseRegisterInfo *>(
+      MF->getSubtarget().getRegisterInfo());
+
+  BitVector regsReserved = ARI->getReservedRegs(*MF);
+  // Check if there is an available register across the sequence that we can
+  // use.
+  for (unsigned Reg : ARM::rGPRRegClass) {
+    if (!(Reg < regsReserved.size() && regsReserved.test(Reg)) &&
+        Reg != ARM::LR &&  // LR is not reserved, but don't use it.
+        Reg != ARM::R12 && // R12 is not guaranteed to be preserved.
+        C.LRU.available(Reg) && C.UsedInSequence.available(Reg))
+      return Reg;
+  }
+
+  // No suitable register. Return 0.
+  return 0u;
+}
+
 outliner::OutlinedFunction ARMBaseInstrInfo::getOutliningCandidateInfo(
     std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
   outliner::Candidate &FirstCand = RepeatedSequenceLocs[0];
   unsigned SequenceSize =
       std::accumulate(FirstCand.front(), std::next(FirstCand.back()), 0,
                       [this](unsigned Sum, const MachineInstr &MI) {
                         return Sum + getInstSizeInBytes(MI);
                       });
for (outliner::Candidate &C : RepeatedSequenceLocs) {
 
       // Is LR available? If so, we don't need a save.
       if (C.LRU.available(ARM::LR)) {
         FrameID = MachineOutlinerNoLRSave;
         NumBytesNoStackCalls += Costs.CallNoLRSave;
         C.setCallInfo(MachineOutlinerNoLRSave, Costs.CallNoLRSave);
         CandidatesWithoutStackFixups.push_back(C);
       }
+
+      // Is an unused register available? If so, we won't modify the stack, so
+      // we can outline with the same frame type as those that don't save LR.
+      else if (findRegisterToSaveLRTo(C)) {
+        FrameID = MachineOutlinerRegSave;
+        NumBytesNoStackCalls += Costs.CallRegSave;
+        C.setCallInfo(MachineOutlinerRegSave, Costs.CallRegSave);
+        CandidatesWithoutStackFixups.push_back(C);
+      }
     }
 
     if (!CandidatesWithoutStackFixups.empty()) {
       RepeatedSequenceLocs = CandidatesWithoutStackFixups;
     } else
       return outliner::OutlinedFunction();
   }
 
MachineBasicBlock::iterator ARMBaseInstrInfo::insertOutlinedCall(
 
   // Create the call instruction.
   Opc = isThumb ? ARM::tBL : ARM::BL;
   MachineInstrBuilder CallMIB = BuildMI(MF, DebugLoc(), get(Opc));
   if (isThumb)
     CallMIB.add(predOps(ARMCC::AL));
   CallMIB.addGlobalAddress(M.getNamedValue(MF.getName()));
 
+  // Can we save to a register?
+  if (C.CallConstructionID == MachineOutlinerRegSave) {
+    unsigned Reg = findRegisterToSaveLRTo(C);
+    assert(Reg != 0 && "No callee-saved register available?");
+
+    // Save and restore LR from that register.
+    if (!MBB.isLiveIn(ARM::LR))
+      MBB.addLiveIn(ARM::LR);
+    copyPhysReg(MBB, It, DebugLoc(), Reg, ARM::LR, true);
+    CallPt = MBB.insert(It, CallMIB);
+    copyPhysReg(MBB, It, DebugLoc(), ARM::LR, Reg, true);
+    It--;
+    return CallPt;
+  }
   // Insert the call.
   It = MBB.insert(It, CallMIB);
   return It;
 }

llvm/test/CodeGen/ARM/machine-outliner-lr-regsave.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=arm-- -run-pass=machine-outliner -verify-machineinstrs \
+# RUN: %s -o - | FileCheck %s
+
+--- |
+  define void @outline_save_reg_arm() #0 { ret void }
+  define void @outline_save_reg_thumb() #1 { ret void }
+  declare void @z()
+
+  attributes #0 = { minsize optsize }
+  attributes #1 = { minsize optsize "target-features"="+armv7-a,+thumb-mode" }
+...
+---
+
+name:           outline_save_reg_arm
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: outline_save_reg_arm
+  ; CHECK: bb.0:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r6 = MOVr killed $lr, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   BL @OUTLINED_FUNCTION_1
+  ; CHECK:   $lr = MOVr killed $r6, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK: bb.1:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r6 = MOVr killed $lr, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   BL @OUTLINED_FUNCTION_1
+  ; CHECK:   $lr = MOVr killed $r6, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK: bb.2:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r0 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r1 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r3 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r4 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r5 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK: bb.3:
+  ; CHECK:   liveins: $lr, $r0, $r6, $r7, $r8, $r9, $r10, $r11
+  ; CHECK:   $r6 = MOVr killed $lr, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   BL @OUTLINED_FUNCTION_1
+  ; CHECK:   $lr = MOVr killed $r6, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK: bb.4:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r2 = MOVr $lr, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   BX_RET 14 /* CC::al */, $noreg
+  bb.0:
+    liveins: $lr
+    $r0 = MOVi 1, 14, $noreg, $noreg
+    $r1 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r3 = MOVi 1, 14, $noreg, $noreg
+    $r4 = MOVi 1, 14, $noreg, $noreg
+    $r5 = MOVi 1, 14, $noreg, $noreg
+  bb.1:
+    liveins: $lr
+    $r0 = MOVi 1, 14, $noreg, $noreg
+    $r1 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r3 = MOVi 1, 14, $noreg, $noreg
+    $r4 = MOVi 1, 14, $noreg, $noreg
+    $r5 = MOVi 1, 14, $noreg, $noreg
+  bb.2:
+    liveins: $lr
+    $r0 = MOVi 1, 14, $noreg, $noreg
+    $r1 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r3 = MOVi 1, 14, $noreg, $noreg
+    $r4 = MOVi 1, 14, $noreg, $noreg
+    $r5 = MOVi 1, 14, $noreg, $noreg
+  bb.3:
+    liveins: $lr, $r0, $r6, $r7, $r8, $r9, $r10, $r11
+    $r0 = MOVi 1, 14, $noreg, $noreg
+    $r1 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r3 = MOVi 1, 14, $noreg, $noreg
+    $r4 = MOVi 1, 14, $noreg, $noreg
+    $r5 = MOVi 1, 14, $noreg, $noreg
+  bb.4:
+    liveins: $lr
+    $r2 = MOVr $lr, 14, $noreg, $noreg
+    BX_RET 14, $noreg
+...
+---
+
+name:           outline_save_reg_thumb
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: outline_save_reg_thumb
+  ; CHECK: bb.0:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r6 = tMOVr killed $lr, 14 /* CC::al */, $noreg
+  ; CHECK:   tBL 14 /* CC::al */, $noreg, @OUTLINED_FUNCTION_0
+  ; CHECK:   $lr = tMOVr killed $r6, 14 /* CC::al */, $noreg
+  ; CHECK: bb.1:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r6 = tMOVr killed $lr, 14 /* CC::al */, $noreg
+  ; CHECK:   tBL 14 /* CC::al */, $noreg, @OUTLINED_FUNCTION_0
+  ; CHECK:   $lr = tMOVr killed $r6, 14 /* CC::al */, $noreg
+  ; CHECK: bb.2:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r0 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r1 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r3 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r4 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r5 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK: bb.3:
+  ; CHECK:   liveins: $lr, $r0, $r6, $r7
+  ; CHECK:   $r6 = tMOVr killed $lr, 14 /* CC::al */, $noreg
+  ; CHECK:   tBL 14 /* CC::al */, $noreg, @OUTLINED_FUNCTION_0
+  ; CHECK:   $lr = tMOVr killed $r6, 14 /* CC::al */, $noreg
+  ; CHECK: bb.4:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r2 = tMOVr $lr, 14 /* CC::al */, $noreg
+  ; CHECK:   tBX_RET 14 /* CC::al */, $noreg
+  bb.0:
+    liveins: $lr
+    $r0 = t2MOVi 1, 14, $noreg, $noreg
+    $r1 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r3 = t2MOVi 1, 14, $noreg, $noreg
+    $r4 = t2MOVi 1, 14, $noreg, $noreg
+    $r5 = t2MOVi 1, 14, $noreg, $noreg
+  bb.1:
+    liveins: $lr
+    $r0 = t2MOVi 1, 14, $noreg, $noreg
+    $r1 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r3 = t2MOVi 1, 14, $noreg, $noreg
+    $r4 = t2MOVi 1, 14, $noreg, $noreg
+    $r5 = t2MOVi 1, 14, $noreg, $noreg
+  bb.2:
+    liveins: $lr
+    $r0 = t2MOVi 1, 14, $noreg, $noreg
+    $r1 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r3 = t2MOVi 1, 14, $noreg, $noreg
+    $r4 = t2MOVi 1, 14, $noreg, $noreg
+    $r5 = t2MOVi 1, 14, $noreg, $noreg
+  bb.3:
+    liveins: $lr, $r0, $r6, $r7, $r8, $r9, $r10, $r11
+    $r0 = t2MOVi 1, 14, $noreg, $noreg
+    $r1 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r3 = t2MOVi 1, 14, $noreg, $noreg
+    $r4 = t2MOVi 1, 14, $noreg, $noreg
+    $r5 = t2MOVi 1, 14, $noreg, $noreg
+  bb.4:
+    liveins: $lr
+    $r2 = tMOVr $lr, 14, $noreg
+    tBX_RET 14, $noreg
+
+  ; CHECK-LABEL: name: OUTLINED_FUNCTION_0
+  ; CHECK: bb.0:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r0 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r1 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r3 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r4 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r5 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   tBX_RET 14 /* CC::al */, $noreg
+
+  ; CHECK-LABEL: name: OUTLINED_FUNCTION_1
+  ; CHECK: bb.0:
+  ; CHECK:   liveins: $lr
+  ; CHECK:   $r0 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r1 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r3 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r4 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r5 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   MOVPCLR 14 /* CC::al */, $noreg
+