[ARM][MachineOutliner] Add NoLRSave mode.

[yroux]

Summary

Outline chunks of code which don't need a save/restore mechanism of the link register.

[yroux]

This was splitted from D76068

[samparker]

Thanks for splitting this out, but how about some more testing..?

• Instructions that read/write SP (in the presence and absence of calls and LR usage).
• The generated return instruction.

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5700

SmallVector?

[yroux]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5700

It will be passed as a parameter to outliner::OutlinedFunction which waits for an std::Vector, maybe a SmallVector can used there instead but I think it should be done in another patch

[yroux]

Updated testcase

[samparker]

Thanks, LGTM.

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5700

Okay, fair enough.

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

 ///
 /// +-------------------------+--------+-----+
 /// |                         | Thumb2 | ARM |
 /// +-------------------------+--------+-----+
 /// | Call overhead in Bytes  |      4 |   4 |
 /// | Frame overhead in Bytes |      0 |   0 |
 /// | Stack fixup required    |     No |  No |
 /// +-------------------------+--------+-----+
+///
+/// \p MachineOutlinerNoLRSave implies that the function should be called using
+/// a BL instruction, but doesn't require LR to be saved and restored. This
+/// happens when LR is known to be dead.
+///
+/// That is,
+///
+/// I1                                OUTLINED_FUNCTION:
+/// I2 --> BL OUTLINED_FUNCTION       I1
+/// I3                                I2
+///                                   I3
+///                                   BX LR
+///
+/// +-------------------------+--------+-----+
+/// |                         | Thumb2 | ARM |
+/// +-------------------------+--------+-----+
+/// | Call overhead in Bytes  |      4 |   4 |
+/// | Frame overhead in Bytes |      4 |   4 |
+/// | Stack fixup required    |     No |  No |
+/// +-------------------------+--------+-----+
 
-enum MachineOutlinerClass { MachineOutlinerTailCall, MachineOutlinerThunk };
+enum MachineOutlinerClass {
+  MachineOutlinerTailCall,
+  MachineOutlinerThunk,
+  MachineOutlinerNoLRSave
+};
 
 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;
 
   OutlinerCosts(const ARMSubtarget &target)
       : CallTailCall(target.isThumb() ? 4 : 4),
         FrameTailCall(target.isThumb() ? 0 : 0),
         CallThunk(target.isThumb() ? 4 : 4),
-        FrameThunk(target.isThumb() ? 0 : 0) {}
+        FrameThunk(target.isThumb() ? 0 : 0),
+        CallNoLRSave(target.isThumb() ? 4 : 4),
+        FrameNoLRSave(target.isThumb() ? 4 : 4) {}
 };
 
 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) {
if (RepeatedSequenceLocs[0].back()->isTerminator()) {
     NumBytesToCreateFrame = Costs.FrameTailCall;
     SetCandidateCallInfo(MachineOutlinerTailCall, Costs.CallTailCall);
   } else if (LastInstrOpcode == ARM::BL || LastInstrOpcode == ARM::BLX ||
              LastInstrOpcode == ARM::tBL || LastInstrOpcode == ARM::tBLXr ||
              LastInstrOpcode == ARM::tBLXi) {
     FrameID = MachineOutlinerThunk;
     NumBytesToCreateFrame = Costs.FrameThunk;
     SetCandidateCallInfo(MachineOutlinerThunk, Costs.CallThunk);
+  } else {
+    // We need to decide how to emit calls + frames. We can always emit the same
+    // frame if we don't need to save to the stack.
+    unsigned NumBytesNoStackCalls = 0;
+    std::vector<outliner::Candidate> CandidatesWithoutStackFixups;
+
+    for (outliner::Candidate &C : RepeatedSequenceLocs) {
+      C.initLRU(TRI);
+
+      // 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);
+      }
+    }
+
+    if (!CandidatesWithoutStackFixups.empty()) {
+      RepeatedSequenceLocs = CandidatesWithoutStackFixups;
     } else
       return outliner::OutlinedFunction();
+  }
 
   return outliner::OutlinedFunction(RepeatedSequenceLocs, SequenceSize,
                                     NumBytesToCreateFrame, FrameID);
 }
 
 bool ARMBaseInstrInfo::isFunctionSafeToOutlineFrom(
     MachineFunction &MF, bool OutlineFromLinkOnceODRs) const {
   const Function &F = MF.getFunction();
if (MI.isCall()) {
 
     return UnknownCallOutlineType;
   }
 
   // Since calls are handled, don't touch LR or PC
   if (MI.modifiesRegister(ARM::LR, TRI) || MI.modifiesRegister(ARM::PC, TRI))
     return outliner::InstrType::Illegal;
 
+  // Does this use the stack?
+  if (MI.modifiesRegister(ARM::SP, TRI) || MI.readsRegister(ARM::SP, TRI)) {
+    // True if there is no chance that any outlined candidate from this range
+    // could require stack fixups. That is, both
+    // * LR is available in the range (No save/restore around call)
+    // * The range doesn't include calls (No save/restore in outlined frame)
+    // are true.
+    // FIXME: This is very restrictive; the flags check the whole block,
+    // not just the bit we will try to outline.
+    bool MightNeedStackFixUp =
+        (Flags & (MachineOutlinerMBBFlags::LRUnavailableSomewhere |
+                  MachineOutlinerMBBFlags::HasCalls));
+
+    if (!MightNeedStackFixUp)
+      return outliner::InstrType::Legal;
+
+    return outliner::InstrType::Illegal;
+  }
+
   // Be conservative with IT blocks.
   if (MI.readsRegister(ARM::ITSTATE, TRI) ||
       MI.modifiesRegister(ARM::ITSTATE, TRI))
     return outliner::InstrType::Illegal;
 
   // Don't outline positions.
   if (MI.isPosition())
     return outliner::InstrType::Illegal;
 
   return outliner::InstrType::Legal;
 }
 
 void ARMBaseInstrInfo::buildOutlinedFrame(
     MachineBasicBlock &MBB, MachineFunction &MF,
     const outliner::OutlinedFunction &OF) const {
+  // Nothing is needed for tail-calls.
+  if (OF.FrameConstructionID == MachineOutlinerTailCall)
+    return;
+
   // For thunk outlining, rewrite the last instruction from a call to a
   // tail-call.
   if (OF.FrameConstructionID == MachineOutlinerThunk) {
     MachineInstr *Call = &*--MBB.instr_end();
     bool isThumb = Subtarget.isThumb();
     unsigned FuncOp = isThumb ? 2 : 0;
     unsigned Opc = Call->getOperand(FuncOp).isReg()
                        ? isThumb ? ARM::tTAILJMPr : ARM::TAILJMPr
                        : isThumb ? Subtarget.isTargetMachO() ? ARM::tTAILJMPd
                                                              : ARM::tTAILJMPdND
                                  : ARM::TAILJMPd;
     MachineInstrBuilder MIB = BuildMI(MBB, MBB.end(), DebugLoc(), get(Opc))
                                   .add(Call->getOperand(FuncOp));
     if (isThumb && !Call->getOperand(FuncOp).isReg())
       MIB.add(predOps(ARMCC::AL));
     Call->eraseFromParent();
+    return;
   }
+
+  // Here we have to insert the return ourselves.  Get the correct opcode from
+  // current feature set.
+  BuildMI(MBB, MBB.end(), DebugLoc(), get(Subtarget.getReturnOpcode()))
+      .add(predOps(ARMCC::AL));
 }
 
 MachineBasicBlock::iterator ARMBaseInstrInfo::insertOutlinedCall(
     Module &M, MachineBasicBlock &MBB, MachineBasicBlock::iterator &It,
     MachineFunction &MF, const outliner::Candidate &C) const {
   MachineInstrBuilder MIB;
   MachineBasicBlock::iterator CallPt;
   unsigned Opc;

llvm/test/CodeGen/ARM/machine-outliner-no-lr-save.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_no_save_ok_arm() #0 { ret void }
+  define void @outline_no_save_ko_arm() #0 { ret void }
+  define void @outline_no_save_ok_thumb() #1 { ret void }
+  define void @outline_no_save_ko_thumb() #1 { ret void }
+
+  declare void @foo()
+
+  attributes #0 = { minsize optsize }
+  attributes #1 = { minsize optsize "target-features"="+armv7-a,+thumb-mode" }
+...
+---
+
+name:           outline_no_save_ok_arm
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: outline_no_save_ok_arm
+  ; CHECK: bb.0:
+  ; CHECK:   BL @OUTLINED_FUNCTION_1
+  ; CHECK: bb.1:
+  ; CHECK:   BL @OUTLINED_FUNCTION_1
+  ; CHECK: bb.2:
+  ; CHECK:   BX_RET 14 /* CC::al */, $noreg
+  bb.0:
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r3 = LDRi12 $sp, 8, 14, $noreg
+  bb.1:
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r2 = MOVi 1, 14, $noreg, $noreg
+    $r3 = LDRi12 $sp, 8, 14, $noreg
+  bb.2:
+    BX_RET 14, $noreg
+...
+---
+
+name:           outline_no_save_ko_arm
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: outline_no_save_ko_arm
+  ; CHECK-NOT: OUTLINED_FUNCTION
+  bb.0:
+    liveins: $lr
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r3 = LDRi12 $sp, 8, 14, $noreg
+    $r2 = MOVr $lr, 14, $noreg, $noreg
+  bb.1:
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r2 = MOVi 2, 14, $noreg, $noreg
+    $r3 = LDRi12 $sp, 8, 14, $noreg
+    $r4 = MOVi 4, 14, $noreg, $noreg
+    BL @foo
+  bb.2:
+    liveins: $lr
+    BX_RET 14, $noreg
+...
+---
+
+name:           outline_no_save_ok_thumb
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: outline_no_save_ok_thumb
+  ; CHECK: bb.0:
+  ; CHECK:   tBL 14 /* CC::al */, $noreg, @OUTLINED_FUNCTION_0
+  ; CHECK: bb.1:
+  ; CHECK:   tBL 14 /* CC::al */, $noreg, @OUTLINED_FUNCTION_0
+  ; CHECK: bb.2:
+  ; CHECK:   tBX_RET 14 /* CC::al */, $noreg
+  bb.0:
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    t2STRi12 $r2, $sp, 0, 14, $noreg
+  bb.1:
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    $r2 = t2MOVi 1, 14, $noreg, $noreg
+    t2STRi12 $r2, $sp, 0, 14, $noreg
+  bb.2:
+    tBX_RET 14, $noreg
+...
+---
+
+name:           outline_no_save_ko_thumb
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: outline_no_save_ko_thumb
+  ; CHECK-NOT: OUTLINED_FUNCTION
+  bb.0:
+    liveins: $lr
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    t2STRi12 $r2, $sp, 0, 14, $noreg
+    $r2 = tMOVr $lr, 14, $noreg
+  bb.1:
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    $r2 = t2MOVi 2, 14, $noreg, $noreg
+    t2STRi12 $r2, $sp, 0, 14, $noreg
+    $r4 = t2MOVi 3, 14, $noreg, $noreg
+    tBL 14, $noreg, @foo
+  bb.2:
+    tBX_RET 14, $noreg
+
+  ; CHECK-LABEL: name: OUTLINED_FUNCTION_0
+  ; CHECK: bb.0:
+  ; CHECK:   $r2 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = t2MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   t2STRi12 $r2, $sp, 0, 14 /* CC::al */, $noreg
+  ; CHECK:   tBX_RET 14 /* CC::al */, $noreg
+
+  ; CHECK-LABEL: name: OUTLINED_FUNCTION_1
+  ; CHECK: bb.0:
+  ; CHECK:   $r2 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r2 = MOVi 1, 14 /* CC::al */, $noreg, $noreg
+  ; CHECK:   $r3 = LDRi12 $sp, 8, 14 /* CC::al */, $noreg
+  ; CHECK:   MOVPCLR 14 /* CC::al */, $noreg