Add 'musttail' marker to call instructions

[rnk]

Summary

This is similar to the 'tail' marker, except that it guarantees that
tail call optimization will occur. It also comes with convervative IR
verification rules that ensure that tail call optimization is possible.

[majnemer]

include/llvm/IR/Instructions.h

1293–1294

Wouldn't it make more sense to have setTailCall take an enum TailCallKind instead of having both setTailCall and setTailCallKind ?

[• tpoechtrager]

For the LangRef, I suggest we remove the text related to when a "tail"
call is guaranteed. With the addition of "musttail" these semantics are
redundant. Instead, "tail" should be advisory only. This would involve
breaking backwards compatibility.

With the new option, should GauranteedTailCallOpt exist? I suggest not.

In code, it would be useful to refer to the old "tail" attribute as "may
tail". This clarifies the semantics in code even if we don't change the
IR name. In particular, I'm referring to CallSite/Instruction here.

In the verifier you need to handle chains of bitcasts. These will
reduce to a single bitcast, but InstCombine may not have run yet. We
don't want each opto pass to need to do this simplification.

Otherwise, LGTM and I support the addition.

Philip

• {F53037, layout=link}

[rnk]

• Make the musttail property of a call immutable
• Add harder LangRef guarantees about arg forwarding and stack growth

[rnk]

I ended up leaving the docs on tail calls in. Removing that support is tricky, because I don't want musttail to change the calling convention of the call. As implemented, -tailcallopt changes the ABI of fastcc, GHC, and HiPE. I checked with GHC and HiPE, and they either never pass args in memory, or always use callee-pop.

But IMO we need to split fastcc into two ccs: one for guaranteed TCO and one for fast codegen. That feels like a big change that I should split out.

[rnk]

• Make musttail mutable again, since the inliner has to tweak it.

[rnk]

• Remove wording about the inliner and variadic arguments, since we don't have Ellipsis support yet

[rnk]

This landed some how over time.

docs/LangRef.rst

 '``call``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = [tail] call [cconv] [ret attrs] <ty> [<fnty>*] <fnptrval>(<function args>) [fn attrs]
+      <result> = [tail | musttail] call [cconv] [ret attrs] <ty> [<fnty>*] <fnptrval>(<function args>) [fn attrs]
 
 Overview:
 """""""""
 
 The '``call``' instruction represents a simple function call.
 
 Arguments:
 """"""""""
 
 This instruction requires several arguments:
 
-#. The optional "tail" marker indicates that the callee function does
-   not access any allocas or varargs in the caller. Note that calls may
-   be marked "tail" even if they do not occur before a
-   :ref:`ret <i_ret>` instruction. If the "tail" marker is present, the
-   function call is eligible for tail call optimization, but `might not
-   in fact be optimized into a jump <CodeGenerator.html#tailcallopt>`_.
-   The code generator may optimize calls marked "tail" with either 1)
-   automatic `sibling call
-   optimization <CodeGenerator.html#sibcallopt>`_ when the caller and
-   callee have matching signatures, or 2) forced tail call optimization
-   when the following extra requirements are met:
+#. The optional ``tail`` and ``musttail`` markers indicate that the optimizers
+   should perform tail call optimization.  The ``tail`` marker is a hint that
+   `can be ignored <CodeGenerator.html#sibcallopt>`_.  The ``musttail`` marker
+   means that the call must be tail call optimized in order for the program to
+   be correct.  The ``musttail`` marker provides these guarantees:
+
+   #. The call will not cause unbounded stack growth if it is part of a
+      recursive cycle in the call graph.
+   #. Arguments with the :ref:`inalloca <attr_inalloca>` attribute are
+      forwarded in place.
+
+   Both markers imply that the callee does not access allocas or varargs from
+   the caller.  Calls marked ``musttail`` must obey the following additional
+   rules:
+
+   - The call must immediately precede a :ref:`ret <i_ret>` instruction,
+     or a pointer bitcast followed by a ret instruction.
+   - The ret instruction must return the (possibly bitcasted) value
+     produced by the call or void.
+   - The caller and callee prototypes must match.  Pointer types of
+     parameters or return types may differ in pointee type, but not
+     in address space.
+   - The calling conventions of the caller and callee must match.
+   - All ABI-impacting function attributes, such as sret, byval, inreg,
+     returned, and inalloca, must match.
+
+   Tail call optimization for calls marked ``tail`` is guaranteed to occur if
+   the following conditions are met:
 
    -  Caller and callee both have the calling convention ``fastcc``.
    -  The call is in tail position (ret immediately follows call and ret
       uses value of call or is void).
    -  Option ``-tailcallopt`` is enabled, or
       ``llvm::GuaranteedTailCallOpt`` is ``true``.
    -  `Platform specific constraints are
       met. <CodeGenerator.html#tailcallopt>`_

include/llvm/IR/CallSite.h

public:
   /// getType - Return the type of the instruction that generated this call site
   ///
   Type *getType() const { return (*this)->getType(); }
 
   /// getCaller - Return the caller function for this call site
   ///
   FunTy *getCaller() const { return (*this)->getParent()->getParent(); }
 
+  /// \brief Tests if this is a tail call.  Only a CallInst can be a tail call.
+  bool isTailCall() const { return isCall() && cast<CallInst>->isTailCall(); }
+
+  /// \brief Tests if this call site must be tail call optimized.  Only a
+  /// CallInst can be tail call optimized.
+  bool isMustTailCall() const {
+    return isCall() && cast<CallInst>(getInstruction())->isMustTailCall();
+  }
+
 #define CALLSITE_DELEGATE_GETTER(METHOD) \
   InstrTy *II = getInstruction();    \
   return isCall()                        \
     ? cast<CallInst>(II)->METHOD         \
     : cast<InvokeInst>(II)->METHOD
 
 #define CALLSITE_DELEGATE_SETTER(METHOD) \
   InstrTy *II = getInstruction();    \

include/llvm/IR/Instructions.h

static Instruction *CreateMalloc(BasicBlock *InsertAtEnd,
                                    Function* MallocF = nullptr,
                                    const Twine &Name = "");
   /// CreateFree - Generate the IR for a call to the builtin free function.
   static Instruction* CreateFree(Value* Source, Instruction *InsertBefore);
   static Instruction* CreateFree(Value* Source, BasicBlock *InsertAtEnd);
 
   ~CallInst();
 
-  bool isTailCall() const { return getSubclassDataFromInstruction() & 1; }
+  // Note that 'musttail' implies 'tail'.
+  enum TailCallKind { TCK_None = 0, TCK_Tail = 1, TCK_MustTail = 2 };
+  TailCallKind getTailCallKind() const {
+    return TailCallKind(getSubclassDataFromInstruction() & 3);
+  }
+  bool isTailCall() const {
+    return (getSubclassDataFromInstruction() & 3) != TCK_None;
+  }
+  bool isMustTailCall() const {
+    return (getSubclassDataFromInstruction() & 3) == TCK_MustTail;
+  }
   void setTailCall(bool isTC = true) {
-    setInstructionSubclassData((getSubclassDataFromInstruction() & ~1) |
-                               unsigned(isTC));
+    setInstructionSubclassData((getSubclassDataFromInstruction() & ~3) |
+                               unsigned(isTC ? TCK_Tail : TCK_None));
+  }
+  void setTailCallKind(TailCallKind TCK) {
+    setInstructionSubclassData((getSubclassDataFromInstruction() & ~3) |
+                               unsigned(TCK));
   }
 
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
 
   /// getNumArgOperands - Return the number of call arguments.
   ///
   unsigned getNumArgOperands() const { return getNumOperands() - 1; }
public:
 
   /// \brief Wrappers for getting the \c Use of a call argument.
   const Use &getArgOperandUse(unsigned i) const { return getOperandUse(i); }
   Use &getArgOperandUse(unsigned i) { return getOperandUse(i); }
 
   /// getCallingConv/setCallingConv - Get or set the calling convention of this
   /// function call.
   CallingConv::ID getCallingConv() const {
-    return static_cast<CallingConv::ID>(getSubclassDataFromInstruction() >> 1);
+    return static_cast<CallingConv::ID>(getSubclassDataFromInstruction() >> 2);
   }
   void setCallingConv(CallingConv::ID CC) {
-    setInstructionSubclassData((getSubclassDataFromInstruction() & 1) |
-                               (static_cast<unsigned>(CC) << 1));
+    setInstructionSubclassData((getSubclassDataFromInstruction() & 3) |
+                               (static_cast<unsigned>(CC) << 2));
   }
 
   /// getAttributes - Return the parameter attributes for this call.
   ///
   const AttributeSet &getAttributes() const { return AttributeList; }
 
   /// setAttributes - Set the parameter attributes for this call.
   ///

lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                    \
   KEYWORD(localdynamic);
   KEYWORD(initialexec);
   KEYWORD(localexec);
   KEYWORD(zeroinitializer);
   KEYWORD(undef);
   KEYWORD(null);
   KEYWORD(to);
   KEYWORD(tail);
+  KEYWORD(musttail);
   KEYWORD(target);
   KEYWORD(triple);
   KEYWORD(unwind);
   KEYWORD(deplibs);             // FIXME: Remove in 4.0.
   KEYWORD(datalayout);
   KEYWORD(volatile);
   KEYWORD(atomic);
   KEYWORD(unordered);

lib/AsmParser/LLParser.h

struct ArgInfo {
       ArgInfo(LocTy L, Type *ty, AttributeSet Attr, const std::string &N)
         : Loc(L), Ty(ty), Attrs(Attr), Name(N) {}
     };
     bool ParseArgumentList(SmallVectorImpl<ArgInfo> &ArgList, bool &isVarArg);
     bool ParseFunctionHeader(Function *&Fn, bool isDefine);
     bool ParseFunctionBody(Function &Fn);
     bool ParseBasicBlock(PerFunctionState &PFS);
 
+    enum TailCallType { TCT_None, TCT_Tail, TCT_MustTail };
+
     // Instruction Parsing.  Each instruction parsing routine can return with a
     // normal result, an error result, or return having eaten an extra comma.
     enum InstResult { InstNormal = 0, InstError = 1, InstExtraComma = 2 };
     int ParseInstruction(Instruction *&Inst, BasicBlock *BB,
                          PerFunctionState &PFS);
     bool ParseCmpPredicate(unsigned &Pred, unsigned Opc);
 
     bool ParseRet(Instruction *&Inst, BasicBlock *BB, PerFunctionState &PFS);
private:
     bool ParseCast(Instruction *&I, PerFunctionState &PFS, unsigned Opc);
     bool ParseSelect(Instruction *&I, PerFunctionState &PFS);
     bool ParseVA_Arg(Instruction *&I, PerFunctionState &PFS);
     bool ParseExtractElement(Instruction *&I, PerFunctionState &PFS);
     bool ParseInsertElement(Instruction *&I, PerFunctionState &PFS);
     bool ParseShuffleVector(Instruction *&I, PerFunctionState &PFS);
     int ParsePHI(Instruction *&I, PerFunctionState &PFS);
     bool ParseLandingPad(Instruction *&I, PerFunctionState &PFS);
-    bool ParseCall(Instruction *&I, PerFunctionState &PFS, bool isTail);
+    bool ParseCall(Instruction *&I, PerFunctionState &PFS,
+                   CallInst::TailCallKind IsTail);
     int ParseAlloc(Instruction *&I, PerFunctionState &PFS);
     int ParseLoad(Instruction *&I, PerFunctionState &PFS);
     int ParseStore(Instruction *&I, PerFunctionState &PFS);
     int ParseCmpXchg(Instruction *&I, PerFunctionState &PFS);
     int ParseAtomicRMW(Instruction *&I, PerFunctionState &PFS);
     int ParseFence(Instruction *&I, PerFunctionState &PFS);
     int ParseGetElementPtr(Instruction *&I, PerFunctionState &PFS);
     int ParseExtractValue(Instruction *&I, PerFunctionState &PFS);

lib/AsmParser/LLParser.cpp

int LLParser::ParseInstruction(Instruction *&Inst, BasicBlock *BB,
   // Other.
   case lltok::kw_select:         return ParseSelect(Inst, PFS);
   case lltok::kw_va_arg:         return ParseVA_Arg(Inst, PFS);
   case lltok::kw_extractelement: return ParseExtractElement(Inst, PFS);
   case lltok::kw_insertelement:  return ParseInsertElement(Inst, PFS);
   case lltok::kw_shufflevector:  return ParseShuffleVector(Inst, PFS);
   case lltok::kw_phi:            return ParsePHI(Inst, PFS);
   case lltok::kw_landingpad:     return ParseLandingPad(Inst, PFS);
-  case lltok::kw_call:           return ParseCall(Inst, PFS, false);
-  case lltok::kw_tail:           return ParseCall(Inst, PFS, true);
+  // Call.
+  case lltok::kw_call:     return ParseCall(Inst, PFS, CallInst::TCK_None);
+  case lltok::kw_tail:     return ParseCall(Inst, PFS, CallInst::TCK_Tail);
+  case lltok::kw_musttail: return ParseCall(Inst, PFS, CallInst::TCK_MustTail);
   // Memory.
   case lltok::kw_alloca:         return ParseAlloc(Inst, PFS);
   case lltok::kw_load:           return ParseLoad(Inst, PFS);
   case lltok::kw_store:          return ParseStore(Inst, PFS);
   case lltok::kw_cmpxchg:        return ParseCmpXchg(Inst, PFS);
   case lltok::kw_atomicrmw:      return ParseAtomicRMW(Inst, PFS);
   case lltok::kw_fence:          return ParseFence(Inst, PFS);
   case lltok::kw_getelementptr: return ParseGetElementPtr(Inst, PFS);
while (Lex.getKind() == lltok::kw_catch || Lex.getKind() == lltok::kw_filter){
     LP->addClause(V);
   }
 
   Inst = LP;
   return false;
 }
 
 /// ParseCall
-///   ::= 'tail'? 'call' OptionalCallingConv OptionalAttrs Type Value
+///   ::= 'call' OptionalCallingConv OptionalAttrs Type Value
+///       ParameterList OptionalAttrs
+///   ::= 'tail' 'call' OptionalCallingConv OptionalAttrs Type Value
+///       ParameterList OptionalAttrs
+///   ::= 'musttail' 'call' OptionalCallingConv OptionalAttrs Type Value
 ///       ParameterList OptionalAttrs
 bool LLParser::ParseCall(Instruction *&Inst, PerFunctionState &PFS,
-                         bool isTail) {
+                         CallInst::TailCallKind TCK) {
   AttrBuilder RetAttrs, FnAttrs;
   std::vector<unsigned> FwdRefAttrGrps;
   LocTy BuiltinLoc;
   CallingConv::ID CC;
   Type *RetType = nullptr;
   LocTy RetTypeLoc;
   ValID CalleeID;
   SmallVector<ParamInfo, 16> ArgList;
   LocTy CallLoc = Lex.getLoc();
 
-  if ((isTail && ParseToken(lltok::kw_call, "expected 'tail call'")) ||
+  if ((TCK != CallInst::TCK_None &&
+       ParseToken(lltok::kw_call, "expected 'tail call'")) ||
       ParseOptionalCallingConv(CC) ||
       ParseOptionalReturnAttrs(RetAttrs) ||
       ParseType(RetType, RetTypeLoc, true /*void allowed*/) ||
       ParseValID(CalleeID) ||
       ParseParameterList(ArgList, PFS) ||
       ParseFnAttributeValuePairs(FnAttrs, FwdRefAttrGrps, false,
                                  BuiltinLoc))
     return true;
if (FnAttrs.hasAttributes())
     Attrs.push_back(AttributeSet::get(RetType->getContext(),
                                       AttributeSet::FunctionIndex,
                                       FnAttrs));
 
   // Finish off the Attribute and check them
   AttributeSet PAL = AttributeSet::get(Context, Attrs);
 
   CallInst *CI = CallInst::Create(Callee, Args);
-  CI->setTailCall(isTail);
+  CI->setTailCallKind(TCK);
   CI->setCallingConv(CC);
   CI->setAttributes(PAL);
   ForwardRefAttrGroups[CI] = FwdRefAttrGrps;
   Inst = CI;
   return false;
 }
 
 //===----------------------------------------------------------------------===//

lib/AsmParser/LLToken.h

enum Kind {
     kw_externally_initialized,
     kw_extern_weak,
     kw_external, kw_thread_local,
     kw_localdynamic, kw_initialexec, kw_localexec,
     kw_zeroinitializer,
     kw_undef, kw_null,
     kw_to,
     kw_tail,
+    kw_musttail,
     kw_target,
     kw_triple,
     kw_unwind,
     kw_deplibs,                 // FIXME: Remove in 4.0
     kw_datalayout,
     kw_volatile,
     kw_atomic,
     kw_unordered, kw_monotonic, kw_acquire, kw_release, kw_acq_rel, kw_seq_cst,

lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::FUNC_CODE_INST_CALL: {
             return Error(InvalidRecord);
           Args.push_back(Op);
         }
       }
 
       I = CallInst::Create(Callee, Args);
       InstructionList.push_back(I);
       cast<CallInst>(I)->setCallingConv(
-        static_cast<CallingConv::ID>(CCInfo>>1));
-      cast<CallInst>(I)->setTailCall(CCInfo & 1);
+          static_cast<CallingConv::ID>((~(1U << 14) & CCInfo) >> 1));
+      CallInst::TailCallKind TCK = CallInst::TCK_None;
+      if (CCInfo & 1)
+        TCK = CallInst::TCK_Tail;
+      if (CCInfo & (1 << 14))
+        TCK = CallInst::TCK_MustTail;
+      cast<CallInst>(I)->setTailCallKind(TCK);
       cast<CallInst>(I)->setAttributes(PAL);
       break;
     }
     case bitc::FUNC_CODE_INST_VAARG: { // VAARG: [valistty, valist, instty]
       if (Record.size() < 3)
         return Error(InvalidRecord);
       Type *OpTy = getTypeByID(Record[0]);
       Value *Op = getValue(Record, 1, NextValueNo, OpTy);

lib/Bitcode/Writer/BitcodeWriter.cpp

static void WriteInstruction(const Instruction &I, unsigned InstID,
   case Instruction::Call: {
     const CallInst &CI = cast<CallInst>(I);
     PointerType *PTy = cast<PointerType>(CI.getCalledValue()->getType());
     FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
 
     Code = bitc::FUNC_CODE_INST_CALL;
 
     Vals.push_back(VE.getAttributeID(CI.getAttributes()));
-    Vals.push_back((CI.getCallingConv() << 1) | unsigned(CI.isTailCall()));
+    Vals.push_back((CI.getCallingConv() << 1) | unsigned(CI.isTailCall()) |
+                   unsigned(CI.isMustTailCall()) << 14);
     PushValueAndType(CI.getCalledValue(), InstID, Vals, VE);  // Callee
 
     // Emit value #'s for the fixed parameters.
     for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
       // Check for labels (can happen with asm labels).
       if (FTy->getParamType(i)->isLabelTy())
         Vals.push_back(VE.getValueID(CI.getArgOperand(i)));
       else

lib/IR/AsmWriter.cpp

if (I.hasName()) {
     // Print out the def slot taken.
     int SlotNum = Machine.getLocalSlot(&I);
     if (SlotNum == -1)
       Out << "<badref> = ";
     else
       Out << '%' << SlotNum << " = ";
   }
 
-  if (isa<CallInst>(I) && cast<CallInst>(I).isTailCall())
+  if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
+    if (CI->isMustTailCall())
+      Out << "musttail ";
+    else if (CI->isTailCall())
       Out << "tail ";
+  }
 
   // Print out the opcode...
   Out << I.getOpcodeName();
 
   // If this is an atomic load or store, print out the atomic marker.
   if ((isa<LoadInst>(I)  && cast<LoadInst>(I).isAtomic()) ||
       (isa<StoreInst>(I) && cast<StoreInst>(I).isAtomic()))
     Out << " atomic";

lib/IR/Verifier.cpp

private:
   void visitAtomicRMWInst(AtomicRMWInst &RMWI);
   void visitFenceInst(FenceInst &FI);
   void visitAllocaInst(AllocaInst &AI);
   void visitExtractValueInst(ExtractValueInst &EVI);
   void visitInsertValueInst(InsertValueInst &IVI);
   void visitLandingPadInst(LandingPadInst &LPI);
 
   void VerifyCallSite(CallSite CS);
+  void verifyMustTailCall(CallInst &CI);
   bool PerformTypeCheck(Intrinsic::ID ID, Function *F, Type *Ty, int VT,
                         unsigned ArgNo, std::string &Suffix);
   bool VerifyIntrinsicType(Type *Ty, ArrayRef<Intrinsic::IITDescriptor> &Infos,
                            SmallVectorImpl<Type *> &ArgTys);
   bool VerifyIntrinsicIsVarArg(bool isVarArg,
                                ArrayRef<Intrinsic::IITDescriptor> &Infos);
   bool VerifyAttributeCount(AttributeSet Attrs, unsigned Params);
   void VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx, bool isFunction,
for (FunctionType::param_iterator PI = FTy->param_begin(),
            PE = FTy->param_end(); PI != PE; ++PI)
       Assert1(!(*PI)->isMetadataTy(),
               "Function has metadata parameter but isn't an intrinsic", I);
   }
 
   visitInstruction(*I);
 }
 
+static bool isTypeCongruent(Type *L, Type *R) {
+  if (L == R)
+    return true;
+  PointerType *PL = dyn_cast<PointerType>(L);
+  PointerType *PR = dyn_cast<PointerType>(R);
+  if (!PL || !PR)
+    return false;
+  return PL->getAddressSpace() == PR->getAddressSpace();
+}
+
+void Verifier::verifyMustTailCall(CallInst &CI) {
+  // - The caller and callee prototypes must match.  Pointer types of
+  //   parameters or return types may differ in pointee type, but not
+  //   address space.
+  Function *F = CI.getParent()->getParent();
+  auto GetFnTy = [](Value *V) {
+    return cast<FunctionType>(
+        cast<PointerType>(V->getType())->getElementType());
+  };
+  FunctionType *CallerTy = GetFnTy(F);
+  FunctionType *CalleeTy = GetFnTy(CI.getCalledValue());
+  Assert1(CallerTy->getNumParams() == CalleeTy->getNumParams(),
+          "cannot guarantee tail call due to mismatched parameter counts", &CI);
+  Assert1(CallerTy->isVarArg() == CalleeTy->isVarArg(),
+          "cannot guarantee tail call due to mismatched varargs", &CI);
+  Assert1(isTypeCongruent(CallerTy->getReturnType(), CalleeTy->getReturnType()),
+          "cannot guarantee tail call due to mismatched return types", &CI);
+  for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
+    Assert1(
+        isTypeCongruent(CallerTy->getParamType(I), CalleeTy->getParamType(I)),
+        "cannot guarantee tail call due to mismatched parameter types", &CI);
+  }
+
+  // - The calling conventions of the caller and callee must match.
+  Assert1(F->getCallingConv() == CI.getCallingConv(),
+          "cannot guarantee tail call due to mismatched calling conv", &CI);
+
+  // - All ABI-impacting function attributes, such as sret, byval, inreg,
+  //   returned, and inalloca, must match.
+  static const Attribute::AttrKind ABIAttrs[] = {
+      Attribute::Alignment, Attribute::StructRet, Attribute::ByVal,
+      Attribute::InAlloca,  Attribute::InReg,     Attribute::Returned};
+  AttributeSet CallerAttrs = F->getAttributes();
+  AttributeSet CalleeAttrs = CI.getAttributes();
+  for (int I = 0, E = CallerTy->getNumParams(); I != E; ++I) {
+    AttrBuilder CallerABIAttrs;
+    AttrBuilder CalleeABIAttrs;
+    for (auto AK : ABIAttrs) {
+      if (CallerAttrs.hasAttribute(I + 1, AK))
+        CallerABIAttrs.addAttribute(AK);
+      if (CalleeAttrs.hasAttribute(I + 1, AK))
+        CalleeABIAttrs.addAttribute(AK);
+    }
+    Assert1(CallerABIAttrs == CalleeABIAttrs, "cannot guarantee tail call due "
+            "to mismatched ABI impacting function attributes", &CI);
+  }
+
+  // - The call must immediately precede a :ref:`ret <i_ret>` instruction,
+  //   or a pointer bitcast followed by a ret instruction.
+  // - The ret instruction must return the (possibly bitcasted) value
+  //   produced by the call or void.
+  Value *RetVal = &CI;
+  Instruction *Next = CI.getNextNode();
+
+  // Handle the optional bitcast.
+  if (BitCastInst *BI = dyn_cast_or_null<BitCastInst>(Next)) {
+    Assert1(BI->getOperand(0) == RetVal,
+            "bitcast following musttail call must use the call", BI);
+    RetVal = BI;
+    Next = BI->getNextNode();
+  }
+
+  // Check the return.
+  ReturnInst *Ret = dyn_cast_or_null<ReturnInst>(Next);
+  Assert1(Ret, "musttail call must be precede a ret with an optional bitcast",
+          &CI);
+  Assert1(!Ret->getReturnValue() || Ret->getReturnValue() == RetVal,
+          "ret must return the result from a preceding musttail call", Ret);
+}
+
 void Verifier::visitCallInst(CallInst &CI) {
   VerifyCallSite(&CI);
 
+  if (CI.isMustTailCall())
+    verifyMustTailCall(CI);
+
   if (Function *F = CI.getCalledFunction())
     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
       visitIntrinsicFunctionCall(ID, CI);
 }
 
 void Verifier::visitInvokeInst(InvokeInst &II) {
   VerifyCallSite(&II);
 

lib/Target/AArch64/AArch64ISelLowering.cpp

AArch64TargetLowering::LowerCall(CallLoweringInfo &CLI,
   bool IsStructRet = !Outs.empty() && Outs[0].Flags.isSRet();
   bool IsSibCall = false;
 
   if (IsTailCall) {
     IsTailCall = IsEligibleForTailCallOptimization(Callee, CallConv,
                     IsVarArg, IsStructRet, MF.getFunction()->hasStructRetAttr(),
                                                    Outs, OutVals, Ins, DAG);
 
+    if (!IsTailCall && CLI.CS && CLI.CS->isMustTailCall())
+      report_fatal_error("failed to perform tail call elimination on a call "
+                         "site marked musttail");
+
     // A sibling call is one where we're under the usual C ABI and not planning
     // to change that but can still do a tail call:
     if (!TailCallOpt && IsTailCall)
       IsSibCall = true;
   }
 
   SmallVector<CCValAssign, 16> ArgLocs;
   CCState CCInfo(CallConv, IsVarArg, DAG.getMachineFunction(),

lib/Target/ARM/ARMISelLowering.cpp

ARMTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
   if (!Subtarget->supportsTailCall() || MF.getTarget().Options.DisableTailCalls)
     isTailCall = false;
 
   if (isTailCall) {
     // Check if it's really possible to do a tail call.
     isTailCall = IsEligibleForTailCallOptimization(Callee, CallConv,
                     isVarArg, isStructRet, MF.getFunction()->hasStructRetAttr(),
                                                    Outs, OutVals, Ins, DAG);
+    if (!isTailCall && CLI.CS && CLI.CS->isMustTailCall())
+      report_fatal_error("failed to perform tail call elimination on a call "
+                         "site marked musttail");
     // We don't support GuaranteedTailCallOpt for ARM, only automatically
     // detected sibcalls.
     if (isTailCall) {
       ++NumTailCalls;
       isSibCall = true;
     }
   }
 

lib/Target/ARM64/ARM64ISelLowering.cpp

SDValue ARM64TargetLowering::LowerCall(CallLoweringInfo &CLI,
   if (!EnableARM64TailCalls)
     IsTailCall = false;
 
   if (IsTailCall) {
     // Check if it's really possible to do a tail call.
     IsTailCall = isEligibleForTailCallOptimization(
         Callee, CallConv, IsVarArg, IsStructRet,
         MF.getFunction()->hasStructRetAttr(), Outs, OutVals, Ins, DAG);
+    if (!IsTailCall && CLI.CS && CLI.CS->isMustTailCall())
+      report_fatal_error("failed to perform tail call elimination on a call "
+                         "site marked musttail");
     // We don't support GuaranteedTailCallOpt, only automatically
     // detected sibcalls.
     // FIXME: Re-evaluate. Is this true? Should it be true?
     if (IsTailCall)
       ++NumTailCalls;
   }
 
   // Analyze operands of the call, assigning locations to each operand.

lib/Target/Mips/MipsISelLowering.cpp

MipsTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
   unsigned NextStackOffset = CCInfo.getNextStackOffset();
 
   // Check if it's really possible to do a tail call.
   if (IsTailCall)
     IsTailCall =
       isEligibleForTailCallOptimization(MipsCCInfo, NextStackOffset,
                                         *MF.getInfo<MipsFunctionInfo>());
 
+  if (!IsTailCall && CLI.CS && CLI.CS->isMustTailCall())
+    report_fatal_error("failed to perform tail call elimination on a call "
+                       "site marked musttail");
+
   if (IsTailCall)
     ++NumTailCalls;
 
   // Chain is the output chain of the last Load/Store or CopyToReg node.
   // ByValChain is the output chain of the last Memcpy node created for copying
   // byval arguments to the stack.
   unsigned StackAlignment = TFL->getStackAlignment();
   NextStackOffset = RoundUpToAlignment(NextStackOffset, StackAlignment);

lib/Target/PowerPC/PPCISelLowering.cpp

PPCTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
   bool &isTailCall                      = CLI.IsTailCall;
   CallingConv::ID CallConv              = CLI.CallConv;
   bool isVarArg                         = CLI.IsVarArg;
 
   if (isTailCall)
     isTailCall = IsEligibleForTailCallOptimization(Callee, CallConv, isVarArg,
                                                    Ins, DAG);
 
+  if (!isTailCall && CLI.CS && CLI.CS->isMustTailCall())
+    report_fatal_error("failed to perform tail call elimination on a call "
+                       "site marked musttail");
+
   if (PPCSubTarget.isSVR4ABI()) {
     if (PPCSubTarget.isPPC64())
       return LowerCall_64SVR4(Chain, Callee, CallConv, isVarArg,
                               isTailCall, Outs, OutVals, Ins,
                               dl, DAG, InVals);
     else
       return LowerCall_32SVR4(Chain, Callee, CallConv, isVarArg,
                               isTailCall, Outs, OutVals, Ins,

lib/Target/X86/X86ISelLowering.cpp

X86TargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
 
   if (isTailCall) {
     // Check if it's really possible to do a tail call.
     isTailCall = IsEligibleForTailCallOptimization(Callee, CallConv,
                     isVarArg, SR != NotStructReturn,
                     MF.getFunction()->hasStructRetAttr(), CLI.RetTy,
                     Outs, OutVals, Ins, DAG);
 
+    if (!isTailCall && CLI.CS && CLI.CS->isMustTailCall())
+      report_fatal_error("failed to perform tail call elimination on a call "
+                         "site marked musttail");
+
     // Sibcalls are automatically detected tailcalls which do not require
     // ABI changes.
     if (!MF.getTarget().Options.GuaranteedTailCallOpt && isTailCall)
       IsSibcall = true;
 
     if (isTailCall)
       ++NumTailCalls;
   }

test/Bitcode/tailcall.ll

+; RUN: llvm-as < %s | llvm-dis | FileCheck %s
+
+; Check that musttail and tail roundtrip.
+
+declare cc8191 void @t1_callee()
+define cc8191 void @t1() {
+; CHECK: tail call cc8191 void @t1_callee()
+  tail call cc8191 void @t1_callee()
+  ret void
+}
+
+declare cc8191 void @t2_callee()
+define cc8191 void @t2() {
+; CHECK: musttail call cc8191 void @t2_callee()
+  musttail call cc8191 void @t2_callee()
+  ret void
+}

test/CodeGen/X86/musttail.ll

+; RUN: llc -march=x86 < %s | FileCheck %s
+
+; FIXME: Eliminate this tail call at -O0, since musttail is a correctness
+; requirement.
+; RUN: not llc -march=x86 -O0 < %s
+
+declare void @t1_callee(i8*)
+define void @t1(i32* %a) {
+; CHECK-LABEL: t1:
+; CHECK: jmp {{_?}}t1_callee
+  %b = bitcast i32* %a to i8*
+  musttail call void @t1_callee(i8* %b)
+  ret void
+}
+
+declare i8* @t2_callee()
+define i32* @t2() {
+; CHECK-LABEL: t2:
+; CHECK: jmp {{_?}}t2_callee
+  %v = musttail call i8* @t2_callee()
+  %w = bitcast i8* %v to i32*
+  ret i32* %w
+}

test/Verifier/musttail-invalid.ll

+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+; Each musttail call should fail to validate.
+
+declare x86_stdcallcc void @cc_mismatch_callee()
+define void @cc_mismatch() {
+; CHECK: mismatched calling conv
+  musttail call x86_stdcallcc void @cc_mismatch_callee()
+  ret void
+}
+
+declare void @more_parms_callee(i32)
+define void @more_parms() {
+; CHECK: mismatched parameter counts
+  musttail call void @more_parms_callee(i32 0)
+  ret void
+}
+
+declare void @mismatched_intty_callee(i8)
+define void @mismatched_intty(i32) {
+; CHECK: mismatched parameter types
+  musttail call void @mismatched_intty_callee(i8 0)
+  ret void
+}
+
+declare void @mismatched_vararg_callee(i8*, ...)
+define void @mismatched_vararg(i8*) {
+; CHECK: mismatched varargs
+  musttail call void (i8*, ...)* @mismatched_vararg_callee(i8* null)
+  ret void
+}
+
+; We would make this an implicit sret parameter, which would disturb the
+; tail call.
+declare { i32, i32, i32 } @mismatched_retty_callee(i32)
+define void @mismatched_retty(i32) {
+; CHECK: mismatched return types
+  musttail call { i32, i32, i32 } @mismatched_retty_callee(i32 0)
+  ret void
+}
+
+declare void @mismatched_byval_callee({ i32 }*)
+define void @mismatched_byval({ i32 }* byval %a) {
+; CHECK: mismatched ABI impacting function attributes
+  musttail call void @mismatched_byval_callee({ i32 }* %a)
+  ret void
+}
+
+declare void @mismatched_inreg_callee(i32 inreg)
+define void @mismatched_inreg(i32 %a) {
+; CHECK: mismatched ABI impacting function attributes
+  musttail call void @mismatched_inreg_callee(i32 inreg %a)
+  ret void
+}
+
+declare void @mismatched_sret_callee(i32* sret)
+define void @mismatched_sret(i32* %a) {
+; CHECK: mismatched ABI impacting function attributes
+  musttail call void @mismatched_sret_callee(i32* sret %a)
+  ret void
+}
+
+declare i32 @not_tail_pos_callee()
+define i32 @not_tail_pos() {
+; CHECK: musttail call must be precede a ret with an optional bitcast
+  %v = musttail call i32 @not_tail_pos_callee()
+  %w = add i32 %v, 1
+  ret i32 %w
+}

test/Verifier/musttail-valid.ll

+; RUN: llvm-as %s -o /dev/null
+
+; Should assemble without error.
+
+declare void @similar_param_ptrty_callee(i8*)
+define void @similar_param_ptrty(i32*) {
+  musttail call void @similar_param_ptrty_callee(i8* null)
+  ret void
+}
+
+declare i8* @similar_ret_ptrty_callee()
+define i32* @similar_ret_ptrty() {
+  %v = musttail call i8* @similar_ret_ptrty_callee()
+  %w = bitcast i8* %v to i32*
+  ret i32* %w
+}