[Outliner] Add tail call support

[paquette]

Summary

Major changes:
This commit adds tail-call support to the outliner. This works by making terminators/returns legal to outline if they are either already tail-calls, or they're the last instruction in a function. By doing this, we get two major benefits:

1. Exposure of new outlining candidates. There could be a repeated substring that was previously too short to outline which is sometimes adjacent to a return. The added return instruction could make it beneficial to outline.

2. Saved instructions. On x86-64, if we can tail call a candidate, we simply outline the terminator/return along with the candidate, saving us a return in tail-called cases. On other targets, this is more significant. For example, if we outline a candidate as a tail-call on ARM64, we can avoid saving/restoring the link register at the call-site, saving two instructions per outlined call.

Minor changes:

• Changes to machine-outliner.ll test to ensure that it won't break if the order of outlined functions changes
• Expanded on the comments on the outlining hooks in TargetInstrInfo.h

[MatzeB]

Wouldn't the things you do for tail calls here apply in the same way to all forms of returning instructions (MachineInstr::isReturn()), I would assume sequences ending in a return are even more common than tail calls.

[MatzeB]

While there are (unrelated?) test changes, I see no test for the new functionality added.

[MatzeB]

Is it possible to avoid the code dealing with ReturnIDs and the new TailCall instruction type, simply by taking the last instruction of an outlined sequence and calling TII::isTailCall() (or MachineInstr::isReturn()) on it to determine whether we outline a sequence ending in one?

lib/CodeGen/MachineOutliner.cpp

519

This can be const.

[paquette]

Removed the extra instruction type for tail calls and fixed up the other couple minor things.

[MatzeB]

The code looks good to me, but this still lacks a test!

include/llvm/Target/TargetInstrInfo.h

1145

This looks unintentional (rebaseing didn't take r296901 into account probably).

lib/CodeGen/MachineOutliner.cpp

924

seems unrelated.

1199–1200

isReturn() and isTailCall() imply isTerminator() so it should be enough to check just that.

1231–1233

same as above.

lib/Target/X86/X86InstrInfo.cpp

10421–10423

I still wonder if things would just work if you change this to:
if (MI.isTerminator() && MI->getParent()->succ_empty()) so you can catch returns or noreturn functions such as exit() or abort() as well.

If I miss something then go ahead with the current change. I just have the feeling that one of the next commits will just start renaming all the IsTailCall to something like ExitsFunction anyway...

10426

isReturn() implies isTerminator().

10450–10460

Things like improving comments can be committed right away without review (people that care can do post-commit review). This has the added benefits that the actual reviews become smaller.

[paquette]

Added a test case, removed the tail call MachineOutlinerInstrType.

This also no longer has anything to do with the stack fixups patch.

[MatzeB]

LGTM with nitpicks addressed.

test/CodeGen/X86/machine-outliner-tailcalls.ll

9

You can probably remove the !tbaa bits

27–30

This can be removed if the tbaa bits are gone.

[echristo]

The boolean parameter threaded through seems a bit unwieldy. Would it be better to either a) add a call that said e.g. TII.numInstrsForCallReturn(), or b) just assume 1?

Also minor coding convention nit, single statement ifs don't need a { } :)

-eric

[echristo]

Hi Jessica,

I noticed that this was committed without addressing my feedback about the boolean parameters, what's up? :)

-eric

[paquette]

In D30670#713287, @echristo wrote:

Hi Jessica,

I noticed that this was committed without addressing my feedback about the boolean parameters, what's up? :)

-eric

Oh whoops. I'm scatterbrained, that's what's up. I'll remove it in the next patch.

Actually, the next patch should end up re-architecting a lot of this so that I can handle some more variations on how functions should be outlined/constructed for the AArch64 outliner. Since we're *kind of* talking about this sort of thing, I'll just brain-dump what I'm thinking in here, just to verify whether or not it'd accomplish what you were getting at.

I was thinking was that everything that talks with the target should be in terms of the start/end MachineBasicBlock::iterators for each candidate. The target would then decide how/if that candidate should be outlined. This would mean that the outliner wouldn't have to actually know *how* things are outlined at all, which would make it easier to add target-specific features in the future.

For example,

getOutliningBenefit(size_t SequenceSize, size_t Occurrences, bool CanBeTailCall)

would become something like

callOverhead(MachineBasicBlock::iterator StartIt, MachineBasicBlock::iterator EndIt)
functionOverhead(MachineBasicBlock::iterator StartIt, MachineBasicBlock::iterator EndIt)

And then the number of instructions taken up by an outlined sequence could be redefined as

callOverhead(StartIt, EndIt)* NumOccurrences + functionOverhead(StartIt, EndIt) + SequenceSize

I think this is somewhat less cumbersome and nicely divorces target-specific stuff from the main outlining pass. I do worry that it moves a little too much of the pass' functionality into [TargetName]InstrInfo though. What do you think?

[echristo]

I think that sounds awesome :)

I'm also taking a look at your other patch.

[MatzeB]

Looks like this was committed in r297653

include/llvm/Target/TargetInstrInfo.h

public:
   virtual bool DefinesPredicate(MachineInstr &MI,
                                 std::vector<MachineOperand> &Pred) const {
     return false;
   }
 
   /// Return true if the specified instruction can be predicated.
   /// By default, this returns true for every instruction with a
   /// PredicateOperand.
   virtual bool isPredicable(const MachineInstr &MI) const {
     return MI.getDesc().isPredicable();
   }
 
   /// Return true if it's safe to move a machine
   /// instruction that defines the specified register class.
   virtual bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const {
     return true;
   }
public:
   /// to prevent register allocator to insert spills before such instructions.
   virtual bool isBasicBlockPrologue(const MachineInstr &MI) const {
     return false;
   }
 
   /// \brief Return how many instructions would be saved by outlining a
   /// sequence containing \p SequenceSize instructions that appears
   /// \p Occurrences times in a module.
-  virtual unsigned getOutliningBenefit(size_t SequenceSize, size_t Occurrences)
-  const {
+  virtual unsigned getOutliningBenefit(size_t SequenceSize, size_t Occurrences,
+                                       bool CanBeTailCall) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::getOutliningBenefit!");
   }
 
   /// Represents how an instruction should be mapped by the outliner.
   /// \p Legal instructions are those which are safe to outline.
   /// \p Illegal instructions are those which cannot be outlined.
   /// \p Invisible instructions are instructions which can be outlined, but
   /// shouldn't actually impact the outlining result.
   enum MachineOutlinerInstrType {Legal, Illegal, Invisible};
 
-  /// Return true if the instruction is legal to outline.
+  /// Returns how or if \p MI should be outlined.
   virtual MachineOutlinerInstrType getOutliningType(MachineInstr &MI) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::getOutliningType!");
   }
 
   /// Insert a custom epilogue for outlined functions.
   /// This may be empty, in which case no epilogue or return statement will be
   /// emitted.
   virtual void insertOutlinerEpilogue(MachineBasicBlock &MBB,
-                                      MachineFunction &MF) const {
+                                      MachineFunction &MF,
+                                      bool IsTailCall) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinerEpilogue!");
   }
 
   /// Insert a call to an outlined function into the program.
   /// Returns an iterator to the spot where we inserted the call. This must be
   /// implemented by the target.
   virtual MachineBasicBlock::iterator
   insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
-                     MachineBasicBlock::iterator &It, MachineFunction &MF)
-  const {
+                     MachineBasicBlock::iterator &It, MachineFunction &MF,
+                     bool IsTailCall) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinedCall!");
   }
 
   /// Insert a custom prologue for outlined functions.
   /// This may be empty, in which case no prologue will be emitted.
   virtual void insertOutlinerPrologue(MachineBasicBlock &MBB,
-                                      MachineFunction &MF) const {
+                                      MachineFunction &MF,
+                                      bool IsTailCall) const {
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::insertOutlinerPrologue!");
   }
 
   /// Return true if the function can safely be outlined from.
   /// By default, this means that the function has no red zone.
-  virtual bool isFunctionSafeToOutlineFrom(MachineFunction &F) const {
+  virtual bool isFunctionSafeToOutlineFrom(MachineFunction &MF) const {
     llvm_unreachable("Target didn't implement "
                      "TargetInstrInfo::isFunctionSafeToOutlineFrom!");
   }
 
 private:
   unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode;
   unsigned CatchRetOpcode;
   unsigned ReturnOpcode;

lib/CodeGen/MachineOutliner.cpp

if (!CurrNode.isLeaf()) {
       MaxBenefit = Benefit;
       BestStartIdx = CurrNode.SuffixIdx;
       BestLen = StringLen;
     }
   }
 
 public:
 
+  unsigned operator[](const size_t i) const {
+    return Str[i];
+  }
+
   /// \brief Return a substring of the tree with maximum benefit if such a
   /// substring exists.
   ///
   /// Clears the input vector and fills it with a maximum substring or empty.
   ///
   /// \param[in,out] Best The most beneficial substring in the tree. Empty
   /// if it does not exist.
   /// \param BenefitFn The function the query should return a maximum string
struct OutlinedFunction {
 
   /// \brief The sequence of integers corresponding to the instructions in this
   /// function.
   std::vector<unsigned> Sequence;
 
   /// The number of instructions this function would save.
   unsigned Benefit = 0;
 
+  bool IsTailCall = false;
+
   OutlinedFunction(size_t Name, size_t OccurrenceCount,
                    const std::vector<unsigned> &Sequence,
-                   unsigned Benefit)
+                   unsigned Benefit, bool IsTailCall)
       : Name(Name), OccurrenceCount(OccurrenceCount), Sequence(Sequence),
-        Benefit(Benefit)
+        Benefit(Benefit), IsTailCall(IsTailCall)
         {}
 };
 
 /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings.
 struct InstructionMapper {
 
   /// \brief The next available integer to assign to a \p MachineInstr that
   /// cannot be outlined.
struct InstructionMapper {
   /// queried for candidates.
   ///
   /// \param MBB The \p MachineBasicBlock to be translated into integers.
   /// \param TRI \p TargetRegisterInfo for the module.
   /// \param TII \p TargetInstrInfo for the module.
   void convertToUnsignedVec(MachineBasicBlock &MBB,
                             const TargetRegisterInfo &TRI,
                             const TargetInstrInfo &TII) {
     for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
          It++) {
 
       // Keep track of where this instruction is in the module.
       switch(TII.getOutliningType(*It)) {
         case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
           mapToIllegalUnsigned(It);
           break;
 
struct MachineOutliner : public ModulePass {
   /// \param[out] FunctionList Filled with functions corresponding to each type
   /// of \p Candidate.
   /// \param ST The suffix tree for the module.
   /// \param TII TargetInstrInfo for the module.
   ///
   /// \returns The length of the longest candidate found. 0 if there are none.
   unsigned buildCandidateList(std::vector<Candidate> &CandidateList,
                               std::vector<OutlinedFunction> &FunctionList,
-                              SuffixTree &ST, const TargetInstrInfo &TII);
+                              SuffixTree &ST,
+                              InstructionMapper &Mapper,
+                              const TargetInstrInfo &TII);
 
   /// \brief Remove any overlapping candidates that weren't handled by the
   /// suffix tree's pruning method.
   ///
   /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
   /// If a short candidate is chosen for outlining, then a longer candidate
   /// which has that short candidate as a suffix is chosen, the tree's pruning
   /// method will not find it. Thus, we need to prune before outlining as well.
for (auto Sit = It + 1; Sit != Et; Sit++) {
             dbgs() << "--- C1 :[" << C1.StartIdx << ", " << C1End << "]\n";
             dbgs() << "--- C2 :[" << C2.StartIdx << ", " << C2End << "]\n";
             );
 
       // Update the function's occurrence count and benefit to reflec that C2
       // is being removed.
       F2.OccurrenceCount--;
       F2.Benefit = TII.getOutliningBenefit(F2.Sequence.size(),
-                                           F2.OccurrenceCount
+                                           F2.OccurrenceCount,
+                                           F2.IsTailCall
                                            );
 
       // Mark C2 as not in the list.
       C2.InCandidateList = false;
 
       DEBUG (
             dbgs() << "- Removed C2. \n";
             dbgs() << "--- Num fns left for C2: " << F2.OccurrenceCount << "\n";
             dbgs() << "--- C2's benefit: " << F2.Benefit << "\n";
             );
     }
   }
 }
 
 unsigned
 MachineOutliner::buildCandidateList(std::vector<Candidate> &CandidateList,
                                     std::vector<OutlinedFunction> &FunctionList,
                                     SuffixTree &ST,
+                                    InstructionMapper &Mapper,
                                     const TargetInstrInfo &TII) {
 
   std::vector<unsigned> CandidateSequence; // Current outlining candidate.
   unsigned MaxCandidateLen = 0; // Length of the longest candidate.
 
   // Function for maximizing query in the suffix tree.
   // This allows us to define more fine-grained types of things to outline in
   // the target without putting target-specific info in the suffix tree.
-  auto BenefitFn = [&TII](const SuffixTreeNode &Curr, size_t StringLen) {
+  auto BenefitFn = [&TII, &ST, &Mapper](const SuffixTreeNode &Curr,
+                                        size_t StringLen) {
 
     // Any leaf whose parent is the root only has one occurrence.
     if (Curr.Parent->isRoot())
       return 0u;
 
     // Anything with length < 2 will never be beneficial on any target.
     if (StringLen < 2)
       return 0u;
 
     size_t Occurrences = Curr.Parent->OccurrenceCount;
 
     // Anything with fewer than 2 occurrences will never be beneficial on any
     // target.
     if (Occurrences < 2)
       return 0u;
 
-    return TII.getOutliningBenefit(StringLen, Occurrences);
+    // Check if the last instruction in the sequence is a return.
+    MachineInstr *LastInstr =
+    Mapper.IntegerInstructionMap[ST[Curr.SuffixIdx + StringLen - 1]];
+    assert(LastInstr && "Last instruction in sequence was unmapped!");
+
+    // The only way a terminator could be mapped as legal is if it was safe to
+    // tail call.
+    bool IsTailCall = LastInstr->isTerminator();
+
+    return TII.getOutliningBenefit(StringLen, Occurrences, IsTailCall);
   };
 
   // Repeatedly query the suffix tree for the substring that maximizes
   // BenefitFn. Find the occurrences of that string, prune the tree, and store
   // each occurrence as a candidate.
   for (ST.bestRepeatedSubstring(CandidateSequence, BenefitFn);
        CandidateSequence.size() > 1;
        ST.bestRepeatedSubstring(CandidateSequence, BenefitFn)) {
 
     std::vector<size_t> Occurrences;
 
     bool GotNonOverlappingCandidate =
         ST.findOccurrencesAndPrune(CandidateSequence, Occurrences);
 
     // Is the candidate we found known to overlap with something we already
     // outlined?
     if (!GotNonOverlappingCandidate)
       continue;
 
     // Is this candidate the longest so far?
     if (CandidateSequence.size() > MaxCandidateLen)
       MaxCandidateLen = CandidateSequence.size();
 
+    MachineInstr *LastInstr =
+    Mapper.IntegerInstructionMap[CandidateSequence.back()];
+    assert(LastInstr && "Last instruction in sequence was unmapped!");
+
+    // The only way a terminator could be mapped as legal is if it was safe to
+    // tail call.
+    bool IsTailCall = LastInstr->isTerminator();
+
     // Keep track of the benefit of outlining this candidate in its
     // OutlinedFunction.
     unsigned FnBenefit = TII.getOutliningBenefit(CandidateSequence.size(),
-                                                 Occurrences.size()
+                                                 Occurrences.size(),
+                                                 IsTailCall
                                                  );
 
     assert(FnBenefit > 0 && "Function cannot be unbeneficial!");
 
     // Save an OutlinedFunction for this candidate.
     FunctionList.emplace_back(
         FunctionList.size(), // Number of this function.
         Occurrences.size(),  // Number of occurrences.
         CandidateSequence,   // Sequence to outline.
-        FnBenefit            // Instructions saved by outlining this function.
+        FnBenefit,           // Instructions saved by outlining this function.
+        IsTailCall           // Flag set if this function is to be tail called.
         );
 
     // Save each of the occurrences of the candidate so we can outline them.
     for (size_t &Occ : Occurrences)
       CandidateList.emplace_back(
           Occ,                      // Starting idx in that MBB.
           CandidateSequence.size(), // Candidate length.
           FunctionList.size() - 1   // Idx of the corresponding function.
MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
   MachineFunction &MF = MMI.getMachineFunction(*F);
   MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   const TargetInstrInfo &TII = *STI.getInstrInfo();
 
   // Insert the new function into the module.
   MF.insert(MF.begin(), &MBB);
 
-  TII.insertOutlinerPrologue(MBB, MF);
+  TII.insertOutlinerPrologue(MBB, MF, OF.IsTailCall);
 
   // Copy over the instructions for the function using the integer mappings in
   // its sequence.
   for (unsigned Str : OF.Sequence) {
     MachineInstr *NewMI =
         MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
     NewMI->dropMemRefs();
 
     // Don't keep debug information for outlined instructions.
     // FIXME: This means outlined functions are currently undebuggable.
     NewMI->setDebugLoc(DebugLoc());
     MBB.insert(MBB.end(), NewMI);
   }
 
-  TII.insertOutlinerEpilogue(MBB, MF);
+  TII.insertOutlinerEpilogue(MBB, MF, OF.IsTailCall);
 
   return &MF;
 }
 
 bool MachineOutliner::outline(Module &M,
                               const ArrayRef<Candidate> &CandidateList,
                               std::vector<OutlinedFunction> &FunctionList,
                               InstructionMapper &Mapper) {
for (const Candidate &C : CandidateList) {
     if (!OF.MF)
       OF.MF = createOutlinedFunction(M, OF, Mapper);
 
     MachineFunction *MF = OF.MF;
     const TargetSubtargetInfo &STI = MF->getSubtarget();
     const TargetInstrInfo &TII = *STI.getInstrInfo();
 
     // Insert a call to the new function and erase the old sequence.
-    TII.insertOutlinedCall(M, *MBB, StartIt, *MF);
+    TII.insertOutlinedCall(M, *MBB, StartIt, *MF, OF.IsTailCall);
     StartIt = Mapper.InstrList[C.StartIdx];
     MBB->erase(StartIt, EndIt);
 
     OutlinedSomething = true;
 
     // Statistics.
     NumOutlined++;
   }
bool MachineOutliner::runOnModule(Module &M) {
   }
 
   // Construct a suffix tree, use it to find candidates, and then outline them.
   SuffixTree ST(Mapper.UnsignedVec);
   std::vector<Candidate> CandidateList;
   std::vector<OutlinedFunction> FunctionList;
 
   unsigned MaxCandidateLen =
-      buildCandidateList(CandidateList, FunctionList, ST, *TII);
+      buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
 
   pruneOverlaps(CandidateList, FunctionList, MaxCandidateLen, *TII);
   return outline(M, CandidateList, FunctionList, Mapper);
 }

lib/Target/X86/X86InstrInfo.h

public:
   decomposeMachineOperandsTargetFlags(unsigned TF) const override;
 
   ArrayRef<std::pair<unsigned, const char *>>
   getSerializableDirectMachineOperandTargetFlags() const override;
 
   bool isTailCall(const MachineInstr &Inst) const override;
 
   unsigned getOutliningBenefit(size_t SequenceSize,
-                               size_t Occurrences) const override;
+                               size_t Occurrences,
+                               bool CanBeTailCall) const override;
 
   bool isFunctionSafeToOutlineFrom(MachineFunction &MF) const override;
 
   llvm::X86GenInstrInfo::MachineOutlinerInstrType
   getOutliningType(MachineInstr &MI) const override;
 
   void insertOutlinerEpilogue(MachineBasicBlock &MBB,
-                              MachineFunction &MF) const override;
+                              MachineFunction &MF,
+                              bool IsTailCall) const override;
 
   void insertOutlinerPrologue(MachineBasicBlock &MBB,
-                              MachineFunction &MF) const override;
+                              MachineFunction &MF,
+                              bool isTailCall) const override;
 
   MachineBasicBlock::iterator
   insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                      MachineBasicBlock::iterator &It,
-                     MachineFunction &MF) const override;
-
+                     MachineFunction &MF,
+                     bool IsTailCall) const override;
 protected:
   /// Commutes the operands in the given instruction by changing the operands
   /// order and/or changing the instruction's opcode and/or the immediate value
   /// operand.
   ///
   /// The arguments 'CommuteOpIdx1' and 'CommuteOpIdx2' specify the operands
   /// to be commuted.
   ///

lib/Target/X86/X86InstrInfo.cpp

namespace {
   };
 }
 
 char LDTLSCleanup::ID = 0;
 FunctionPass*
 llvm::createCleanupLocalDynamicTLSPass() { return new LDTLSCleanup(); }
 
 unsigned X86InstrInfo::getOutliningBenefit(size_t SequenceSize,
-                                           size_t Occurrences) const {
+                                           size_t Occurrences,
+                                           bool CanBeTailCall) const {
   unsigned NotOutlinedSize = SequenceSize * Occurrences;
+  unsigned OutlinedSize;
 
-  // Sequence appears once in outlined function (Sequence.size())
-  // One return instruction (+1)
-  // One call per occurrence (Occurrences)
-  unsigned OutlinedSize = (SequenceSize + 1) + Occurrences;
+  // Is it a tail call?
+  if (CanBeTailCall) {
+    // If yes, we don't have to include a return instruction-- it's already in
+    // our sequence. So we have one occurrence of the sequence + #Occurrences
+    // calls.
+    OutlinedSize = SequenceSize + Occurrences;
+  } else {
+    // If not, add one for the return instruction.
+    OutlinedSize = (SequenceSize + 1) + Occurrences;
+  }
 
   // Return the number of instructions saved by outlining this sequence.
   return NotOutlinedSize > OutlinedSize ? NotOutlinedSize - OutlinedSize : 0;
 }
 
 bool X86InstrInfo::isFunctionSafeToOutlineFrom(MachineFunction &MF) const {
   return MF.getFunction()->hasFnAttribute(Attribute::NoRedZone);
 }
 
 X86GenInstrInfo::MachineOutlinerInstrType
 X86InstrInfo::getOutliningType(MachineInstr &MI) const {
 
-  // Don't outline returns or basic block terminators.
-  if (MI.isReturn() || MI.isTerminator())
+  // Don't allow debug values to impact outlining type.
+  if (MI.isDebugValue() || MI.isIndirectDebugValue())
+    return MachineOutlinerInstrType::Invisible;
+
+  // Is this a tail call? If yes, we can outline as a tail call.
+  if (isTailCall(MI))
+    return MachineOutlinerInstrType::Legal;
+
+  // Is this the terminator of a basic block?
+  if (MI.isTerminator() || MI.isReturn()) {
+
+    // Does its parent have any successors in its MachineFunction?
+    if (MI.getParent()->succ_empty())
+        return MachineOutlinerInstrType::Legal;
+
+    // It does, so we can't tail call it.
     return MachineOutlinerInstrType::Illegal;
+  }
 
   // Don't outline anything that modifies or reads from the stack pointer.
   //
   // FIXME: There are instructions which are being manually built without
   // explicit uses/defs so we also have to check the MCInstrDesc. We should be
   // able to remove the extra checks once those are fixed up. For example,
   // sometimes we might get something like %RAX<def> = POP64r 1. This won't be
   // caught by modifiesRegister or readsRegister even though the instruction
   // really ought to be formed so that modifiesRegister/readsRegister would
   // catch it.
   if (MI.modifiesRegister(X86::RSP, &RI) || MI.readsRegister(X86::RSP, &RI) ||
       MI.getDesc().hasImplicitUseOfPhysReg(X86::RSP) ||
-      MI.getDesc().hasImplicitDefOfPhysReg(X86::RSP))
+      MI.getDesc().hasImplicitDefOfPhysReg(X86::RSP)) 
     return MachineOutlinerInstrType::Illegal;
 
+  // Outlined calls change the instruction pointer, so don't read from it.
   if (MI.readsRegister(X86::RIP, &RI) ||
       MI.getDesc().hasImplicitUseOfPhysReg(X86::RIP) ||
       MI.getDesc().hasImplicitDefOfPhysReg(X86::RIP))
     return MachineOutlinerInstrType::Illegal;
 
+  // Positions can't safely be outlined.
   if (MI.isPosition())
     return MachineOutlinerInstrType::Illegal;
 
+  // Make sure none of the operands of this instruction do anything tricky.
   for (const MachineOperand &MOP : MI.operands())
     if (MOP.isCPI() || MOP.isJTI() || MOP.isCFIIndex() || MOP.isFI() ||
         MOP.isTargetIndex())
       return MachineOutlinerInstrType::Illegal;
 
-  // Don't allow debug values to impact outlining type.
-  if (MI.isDebugValue() || MI.isIndirectDebugValue())
-    return MachineOutlinerInstrType::Invisible;
-
   return MachineOutlinerInstrType::Legal;
 }
 
 void X86InstrInfo::insertOutlinerEpilogue(MachineBasicBlock &MBB,
-                                          MachineFunction &MF) const {
+                                          MachineFunction &MF,
+                                          bool IsTailCall) const {
+
+  // If we're a tail call, we already have a return, so don't do anything.
+  if (IsTailCall)
+    return;
 
+  // We're a normal call, so our sequence doesn't have a return instruction.
+  // Add it in.
   MachineInstr *retq = BuildMI(MF, DebugLoc(), get(X86::RETQ));
   MBB.insert(MBB.end(), retq);
 }
 
 void X86InstrInfo::insertOutlinerPrologue(MachineBasicBlock &MBB,
-                                          MachineFunction &MF) const {
+                                          MachineFunction &MF,
+                                          bool IsTailCall) const {
   return;
 }
 
 MachineBasicBlock::iterator
 X86InstrInfo::insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
                                  MachineBasicBlock::iterator &It,
-                                 MachineFunction &MF) const {
+                                 MachineFunction &MF,
+                                 bool IsTailCall) const {
+  // Is it a tail call?
+  if (IsTailCall) {
+    // Yes, just insert a JMP.
+    It = MBB.insert(It,
+                  BuildMI(MF, DebugLoc(), get(X86::JMP_1))
+                      .addGlobalAddress(M.getNamedValue(MF.getName())));
+  } else {
+    // No, insert a call.
     It = MBB.insert(It,
                   BuildMI(MF, DebugLoc(), get(X86::CALL64pcrel32))
                       .addGlobalAddress(M.getNamedValue(MF.getName())));
+  }
+
   return It;
 }

test/CodeGen/X86/machine-outliner-tailcalls.ll

+; RUN: llc -enable-machine-outliner -mtriple=x86_64-apple-darwin < %s | FileCheck %s
+
+@x = common local_unnamed_addr global i32 0, align 4
+
+define i32 @foo0(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: _foo0:
+; CHECK: jmp l_OUTLINED_FUNCTION_0
+; CHECK-NEXT: .cfi_endproc
+  store i32 0, i32* @x, align 4, !tbaa !2
+  %2 = tail call i32 @ext(i32 1) #2
+  ret i32 undef
+}
+
+declare i32 @ext(i32) local_unnamed_addr #1
+
+define i32 @foo1(i32) local_unnamed_addr #0 {
+; CHECK-LABEL: _foo1:
+; CHECK: jmp l_OUTLINED_FUNCTION_0
+; CHECK-NEXT: .cfi_endproc
+  store i32 0, i32* @x, align 4, !tbaa !2
+  %2 = tail call i32 @ext(i32 1) #2
+  ret i32 undef
+}
+
+attributes #0 = { noredzone nounwind ssp uwtable "no-frame-pointer-elim"="false" }
+
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+
+; CHECK-LABEL: l_OUTLINED_FUNCTION_0:
+; CHECK: movl  $0, (%rax)
+; CHECK-NEXT: movl  $1, %edi
+; CHECK-NEXT: jmp _ext 
 No newline at end of file

test/CodeGen/X86/machine-outliner.ll

define i32 @check_boundaries() #0 {
   %4 = alloca i32, align 4
   %5 = alloca i32, align 4
   store i32 0, i32* %1, align 4
   store i32 0, i32* %2, align 4
   %6 = load i32, i32* %2, align 4
   %7 = icmp ne i32 %6, 0
   br i1 %7, label %9, label %8
 
-  ; CHECK: callq l_OUTLINED_FUNCTION_1
+  ; CHECK: callq [[OFUNC1:l_OUTLINED_FUNCTION_[0-9]+]]
   ; CHECK: cmpl  $0, -{{[0-9]+}}(%rbp)
   store i32 1, i32* %2, align 4
   store i32 2, i32* %3, align 4
   store i32 3, i32* %4, align 4
   store i32 4, i32* %5, align 4
   br label %10
 
   store i32 1, i32* %4, align 4
   br label %10
 
   %11 = load i32, i32* %2, align 4
   %12 = icmp ne i32 %11, 0
   br i1 %12, label %14, label %13
 
-  ; CHECK: callq l_OUTLINED_FUNCTION_1
+  ; CHECK: callq [[OFUNC1]]
   store i32 1, i32* %2, align 4
   store i32 2, i32* %3, align 4
   store i32 3, i32* %4, align 4
   store i32 4, i32* %5, align 4
   br label %15
 
   store i32 1, i32* %4, align 4
   br label %15
define i32 @main() #0 {
   %1 = alloca i32, align 4
   %2 = alloca i32, align 4
   %3 = alloca i32, align 4
   %4 = alloca i32, align 4
   %5 = alloca i32, align 4
 
   store i32 0, i32* %1, align 4
   store i32 0, i32* @x, align 4
-  ; CHECK: callq l_OUTLINED_FUNCTION_0
+  ; CHECK: callq [[OFUNC2:l_OUTLINED_FUNCTION_[0-9]+]]
   store i32 1, i32* %2, align 4
   store i32 2, i32* %3, align 4
   store i32 3, i32* %4, align 4
   store i32 4, i32* %5, align 4
   store i32 1, i32* @x, align 4
-  ; CHECK: callq l_OUTLINED_FUNCTION_0
+  ; CHECK: callq [[OFUNC2]]
   store i32 1, i32* %2, align 4
   store i32 2, i32* %3, align 4
   store i32 3, i32* %4, align 4
   store i32 4, i32* %5, align 4
   ret i32 0
 }
 
 attributes #0 = { noredzone nounwind ssp uwtable "no-frame-pointer-elim"="true" }
 
-; CHECK-LABEL: l_OUTLINED_FUNCTION_0:
+; CHECK-LABEL: l_OUTLINED_FUNCTION_1:
 ; CHECK:      movl  $1, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: movl  $2, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: movl  $3, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: movl  $4, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: retq
 
-; CHECK-LABEL: l_OUTLINED_FUNCTION_1:
+; CHECK-LABEL: l_OUTLINED_FUNCTION_0:
 ; CHECK:      movl  $1, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: movl  $2, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: movl  $3, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: movl  $4, -{{[0-9]+}}(%rbp)
 ; CHECK-NEXT: retq