[ARM][MachineOutliner] Add calls default handling.

[yroux]

Summary

Handles calls inside outlined regions, by saving and restoring the link register.

[samparker]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5846

I've forgotten what FrameDefault represents, but is this right considering that NumBytesToCreateFrame is also initialised to this?

[yroux]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5846

Ah right, the logic here is that NumBytesToCreateFrame is initialised to the costs in byte of adding a "bx lr" to the outlined code (2 or 4 bytes if we are in T2 or ARM) then if we are in a taillcall or thunk case it is set to 0 since the nothing is added to the code, and here we check if there is a call in the outlined chunk, which means that we need to insert a save and restore of the link register, thus we need to increase NumBytesToCreateFrame by the cost of a CallDefault and not FrameDefault, and it is the same in the test below. I'll update the patch.

[yroux]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5846

well, since CallDefault cost contains the cost of the branch it will not be accurate, I'll add a proper cost for save/restore lr

[samparker]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5694

So this is the cost of the store and load, but don't we also need to consider the frame setup too?

[yroux]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5694

The variable NumBytesToCreateFrame is initialized to the default cost of the frame setup and then incremented by the cost of the load/store if needed

[samparker]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5694

So I'm sorry if I'm just being a bit blind (and/or horribly confused!) But I see:

unsigned NumBytesToCreateFrame = Costs.FrameDefault;
NumBytesToCreateFrame += Costs.SaveRestoreLROnStack;

Does this really translate the the cost of inserting:

• a call to the outlined function.
• a sub to adjust the stack pointer in the outlined function.
• the stack store of LR.
• the bx lr from the outlined function.
• the stack restore of LR.

Am I missing some logic that calls SetCandidateCallInfo?

[yroux]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5694

Ok, let's look at the Default case for ARM mode:

• The cost of the call to the outlined function is handled by the setCallInfo method of a candidate, in which Cost.CallDefault is passed.
• Then for the frame:
  • I used a STR_PRE_IMM which decrement SP and store LR in 4 bytes
  • then LR and stack are restored LDR_POST_IMM which is alsor 4 bytes (so the cost of save and restore is 8)
  • and we have the BX LR, is cost is handled by FrameDefault (4 bytes)

[samparker]

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

5694

Ah, indexed load/store! Sorry for missing that in the tests, thanks for clearing that up.

[samparker]

Thanks, LGTM

llvm/lib/Target/ARM/ARMBaseInstrInfo.cpp

struct OutlinerCosts {
   const int CallThunk;
   const int FrameThunk;
   const int CallNoLRSave;
   const int FrameNoLRSave;
   const int CallRegSave;
   const int FrameRegSave;
   const int CallDefault;
   const int FrameDefault;
+  const int SaveRestoreLROnStack;
 
   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),
         CallRegSave(target.isThumb() ? 8 : 12),
         FrameRegSave(target.isThumb() ? 2 : 4),
         CallDefault(target.isThumb() ? 8 : 12),
-        FrameDefault(target.isThumb() ? 2 : 4) {}
+        FrameDefault(target.isThumb() ? 2 : 4),
+        SaveRestoreLROnStack(target.isThumb() ? 8 : 8) {}
 };
 
 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());
for (outliner::Candidate &C : RepeatedSequenceLocs) {
 
       // Is SP used in the sequence at all? If not, we don't have to modify
       // the stack, so we are guaranteed to get the same frame.
       else if (C.UsedInSequence.available(ARM::SP)) {
         NumBytesNoStackCalls += Costs.CallDefault;
         C.setCallInfo(MachineOutlinerDefault, Costs.CallDefault);
         SetCandidateCallInfo(MachineOutlinerDefault, Costs.CallDefault);
         CandidatesWithoutStackFixups.push_back(C);
-      }
-    else
+      } else
         return outliner::OutlinedFunction();
     }
+
+    // Does every candidate's MBB contain a call?  If so, then we might have a
+    // call in the range.
+    if (FlagsSetInAll & MachineOutlinerMBBFlags::HasCalls) {
+      // check if the range contains a call.  These require a save + restore of
+      // the link register.
+      if (std::any_of(FirstCand.front(), FirstCand.back(),
+                      [](const MachineInstr &MI) { return MI.isCall(); }))
+        NumBytesToCreateFrame += Costs.SaveRestoreLROnStack;
+
+      // Handle the last instruction separately.  If it is tail call, then the
+      // last instruction is a call, we don't want to save + restore in this
+      // case.  However, it could be possible that the last instruction is a
+      // call without it being valid to tail call this sequence.  We should
+      // consider this as well.
+      else if (FrameID != MachineOutlinerThunk &&
+               FrameID != MachineOutlinerTailCall && FirstCand.back()->isCall())
+        NumBytesToCreateFrame += Costs.SaveRestoreLROnStack;
+    }
     RepeatedSequenceLocs = CandidatesWithoutStackFixups;
   }
 
   return outliner::OutlinedFunction(RepeatedSequenceLocs, SequenceSize,
                                     NumBytesToCreateFrame, FrameID);
 }
 
 bool ARMBaseInstrInfo::isFunctionSafeToOutlineFrom(
if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() ||
       return outliner::InstrType::Illegal;
   }
 
   // Don't outline if link register or program counter value are used.
   if (MI.readsRegister(ARM::LR, TRI) || MI.readsRegister(ARM::PC, TRI))
     return outliner::InstrType::Illegal;
 
   if (MI.isCall()) {
+    // Get the function associated with the call.  Look at each operand and find
+    // the one that represents the calle and get its name.
+    const Function *Callee = nullptr;
+    for (const MachineOperand &MOP : MI.operands()) {
+      if (MOP.isGlobal()) {
+        Callee = dyn_cast<Function>(MOP.getGlobal());
+        break;
+      }
+    }
+
+    // Dont't outline calls to "mcount" like functions, in particular Linux
+    // kernel function tracing relies on it.
+    if (Callee &&
+        (Callee->getName() == "\01__gnu_mcount_nc" ||
+         Callee->getName() == "\01mcount" || Callee->getName() == "__mcount"))
+      return outliner::InstrType::Illegal;
+
     // If we don't know anything about the callee, assume it depends on the
     // stack layout of the caller. In that case, it's only legal to outline
     // as a tail-call. Explicitly list the call instructions we know about so
     // we don't get unexpected results with call pseudo-instructions.
     auto UnknownCallOutlineType = outliner::InstrType::Illegal;
     if (Opc == ARM::BL || Opc == ARM::tBL || Opc == ARM::BLX ||
         Opc == ARM::tBLXr || Opc == ARM::tBLXi)
       UnknownCallOutlineType = outliner::InstrType::LegalTerminator;
 
+    if (!Callee)
+      return UnknownCallOutlineType;
+
+    // We have a function we have information about.  Check if it's something we
+    // can safely outline.
+    MachineFunction *MF = MI.getParent()->getParent();
+    MachineFunction *CalleeMF = MF->getMMI().getMachineFunction(*Callee);
+
+    // We don't know what's going on with the callee at all.  Don't touch it.
+    if (!CalleeMF)
+      return UnknownCallOutlineType;
+
+    // Check if we know anything about the callee saves on the function. If we
+    // don't, then don't touch it, since that implies that we haven't computed
+    // anything about its stack frame yet.
+    MachineFrameInfo &MFI = CalleeMF->getFrameInfo();
+    if (!MFI.isCalleeSavedInfoValid() || MFI.getStackSize() > 0 ||
+        MFI.getNumObjects() > 0)
       return UnknownCallOutlineType;
+
+    // At this point, we can say that CalleeMF ought to not pass anything on the
+    // stack. Therefore, we can outline it.
+    return outliner::InstrType::Legal;
   }
 
   // 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)) {
void ARMBaseInstrInfo::restoreLRFromStack(
   if (!Subtarget.isThumb())
     MIB.addReg(0);
   MIB.addImm(Subtarget.getStackAlignment().value()).add(predOps(ARMCC::AL));
 }
 
 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;
   }
 
+  // Is there a call in the outlined range?
+  auto IsNonTailCall = [](MachineInstr &MI) {
+    return MI.isCall() && !MI.isReturn();
+  };
+  if (std::any_of(MBB.instr_begin(), MBB.instr_end(), IsNonTailCall)) {
+    MachineBasicBlock::iterator It = MBB.begin();
+    MachineBasicBlock::iterator Et = MBB.end();
+
+    if (OF.FrameConstructionID == MachineOutlinerTailCall ||
+        OF.FrameConstructionID == MachineOutlinerThunk)
+      Et = std::prev(MBB.end());
+
+    // We have to save and restore LR, we need to add it to the liveins if it
+    // is not already part of the set.  This is suffient since outlined
+    // functions only have one block.
+    if (!MBB.isLiveIn(ARM::LR))
+      MBB.addLiveIn(ARM::LR);
+
+    // Insert a save before the outlined region
+    saveLROnStack(MBB, It);
+
+    unsigned StackAlignment = Subtarget.getStackAlignment().value();
+    const TargetSubtargetInfo &STI = MF.getSubtarget();
+    const MCRegisterInfo *MRI = STI.getRegisterInfo();
+    unsigned DwarfReg = MRI->getDwarfRegNum(ARM::LR, true);
+    // Add a CFI saying the stack was moved down.
+    int64_t StackPosEntry = MF.addFrameInst(
+        MCCFIInstruction::cfiDefCfaOffset(nullptr, StackAlignment));
+    BuildMI(MBB, It, DebugLoc(), get(ARM::CFI_INSTRUCTION))
+        .addCFIIndex(StackPosEntry)
+        .setMIFlags(MachineInstr::FrameSetup);
+
+    // Add a CFI saying that the LR that we want to find is now higher than
+    // before.
+    int64_t LRPosEntry = MF.addFrameInst(
+        MCCFIInstruction::createOffset(nullptr, DwarfReg, StackAlignment));
+    BuildMI(MBB, It, DebugLoc(), get(ARM::CFI_INSTRUCTION))
+        .addCFIIndex(LRPosEntry)
+        .setMIFlags(MachineInstr::FrameSetup);
+
+    // Insert a restore before the terminator for the function.  Restore LR.
+    restoreLRFromStack(MBB, Et);
+  }
+
+  // If this is a tail call outlined function, then there's already a return.
+  if (OF.FrameConstructionID == MachineOutlinerTailCall ||
+      OF.FrameConstructionID == MachineOutlinerThunk)
+    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,

llvm/test/CodeGen/ARM/machine-outliner-default.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_default_arm() #0 { ret void }
   define void @outline_default_thumb() #1 { ret void }
-  define void @outline_default_KO_call_arm() #0 { ret void }
-  define void @outline_default_KO_call_thumb() #1 { ret void }
   define void @outline_default_KO_stack_arm() #0 { ret void }
   define void @outline_default_KO_stack_thumb() #0 { ret void }
   declare void @bar()
 
   attributes #0 = { minsize optsize }
   attributes #1 = { minsize optsize "target-features"="+armv7-a,+thumb-mode" }
 ...
 ---
bb.2:
     $r3 = t2MOVi 1, 14, $noreg, $noreg
   bb.3:
     liveins: $lr, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
     $r2 = tMOVr $lr, 14, $noreg
     tBX_RET 14, $noreg
 ...
 ---
 
-name:           outline_default_KO_call_arm
-tracksRegLiveness: true
-body:             |
-  ; CHECK-LABEL: name: outline_default_KO_call_arm
-  ; CHECK: bb.0:
-  ; CHECK:   liveins: $lr
-  ; CHECK:   BL @bar, implicit-def dead $lr, implicit $sp
-  ; CHECK:   $r0 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r1 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r2 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r3 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r4 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK: bb.1:
-  ; CHECK:   liveins: $lr, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-  ; CHECK:   BL @bar, implicit-def dead $lr, implicit $sp
-  ; CHECK:   $r0 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r1 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r2 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r3 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r4 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK: bb.2:
-  ; CHECK:   liveins: $lr, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-  ; CHECK:   BL @bar, implicit-def dead $lr, implicit $sp
-  ; CHECK:   $r0 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r1 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r2 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r3 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r4 = MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK: bb.3:
-  ; CHECK:   liveins: $lr, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-  ; CHECK:   $r2 = MOVr $lr, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   BX_RET 14 /* CC::al */, $noreg
-  bb.0:
-    liveins: $lr
-    BL @bar, implicit-def dead $lr, implicit $sp
-    $r0 = MOVi 2, 14, $noreg, $noreg
-    $r1 = MOVi 2, 14, $noreg, $noreg
-    $r2 = MOVi 2, 14, $noreg, $noreg
-    $r3 = MOVi 2, 14, $noreg, $noreg
-    $r4 = MOVi 2, 14, $noreg, $noreg
-  bb.1:
-    liveins: $lr, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-    BL @bar, implicit-def dead $lr, implicit $sp
-    $r0 = MOVi 2, 14, $noreg, $noreg
-    $r1 = MOVi 2, 14, $noreg, $noreg
-    $r2 = MOVi 2, 14, $noreg, $noreg
-    $r3 = MOVi 2, 14, $noreg, $noreg
-    $r4 = MOVi 2, 14, $noreg, $noreg
-  bb.2:
-    liveins: $lr, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-    BL @bar, implicit-def dead $lr, implicit $sp
-    $r0 = MOVi 2, 14, $noreg, $noreg
-    $r1 = MOVi 2, 14, $noreg, $noreg
-    $r2 = MOVi 2, 14, $noreg, $noreg
-    $r3 = MOVi 2, 14, $noreg, $noreg
-    $r4 = MOVi 2, 14, $noreg, $noreg
-  bb.3:
-    liveins: $lr, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-    $r2 = MOVr $lr, 14, $noreg, $noreg
-    BX_RET 14, $noreg
-...
----
-
-name:           outline_default_KO_call_thumb
-tracksRegLiveness: true
-body:             |
-  ; CHECK-LABEL: name: outline_default_KO_call_thumb
-  ; CHECK: bb.0:
-  ; CHECK:   liveins: $lr
-  ; CHECK:   tBL 14 /* CC::al */, $noreg, @bar, implicit-def dead $lr, implicit $sp
-  ; CHECK:   $r0 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r1 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r2 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK: bb.1:
-  ; CHECK:   liveins: $lr, $r3, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-  ; CHECK:   tBL 14 /* CC::al */, $noreg, @bar, implicit-def dead $lr, implicit $sp
-  ; CHECK:   $r0 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r1 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r2 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK: bb.2:
-  ; CHECK:   liveins: $lr, $r3, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-  ; CHECK:   tBL 14 /* CC::al */, $noreg, @bar, implicit-def dead $lr, implicit $sp
-  ; CHECK:   $r0 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r1 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   $r2 = t2MOVi 2, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK: bb.3:
-  ; CHECK:   liveins: $lr, $r3, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-  ; CHECK:   $r2 = tMOVr $lr, 14 /* CC::al */, $noreg
-  ; CHECK:   tBX_RET 14 /* CC::al */, $noreg
-  bb.0:
-    liveins: $lr
-    tBL 14, $noreg, @bar, implicit-def dead $lr, implicit $sp
-    $r0 = t2MOVi 2, 14, $noreg, $noreg
-    $r1 = t2MOVi 2, 14, $noreg, $noreg
-    $r2 = t2MOVi 2, 14, $noreg, $noreg
-  bb.1:
-    liveins: $lr, $r3, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-    tBL 14, $noreg, @bar, implicit-def dead $lr, implicit $sp
-    $r0 = t2MOVi 2, 14, $noreg, $noreg
-    $r1 = t2MOVi 2, 14, $noreg, $noreg
-    $r2 = t2MOVi 2, 14, $noreg, $noreg
-  bb.2:
-    liveins: $lr, $r3, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-    tBL 14, $noreg, @bar, implicit-def dead $lr, implicit $sp
-    $r0 = t2MOVi 2, 14, $noreg, $noreg
-    $r1 = t2MOVi 2, 14, $noreg, $noreg
-    $r2 = t2MOVi 2, 14, $noreg, $noreg
-  bb.3:
-    liveins: $lr, $r3, $r4, $r5, $r6, $r7, $r8, $r9, $r10, $r11
-    $r2 = tMOVr $lr, 14, $noreg
-    tBX_RET 14, $noreg
-...
----
-
 name:           outline_default_KO_stack_arm
 tracksRegLiveness: true
 body:             |
   ; CHECK-LABEL: name: outline_default_KO_stack_arm
   ; CHECK: bb.0:
   ; CHECK:   liveins: $lr
   ; CHECK:   $r0 = LDRi12 $sp, 0, 14 /* CC::al */, $noreg
   ; CHECK:   $r1 = MOVi 3, 14 /* CC::al */, $noreg, $noreg