Update musttail verification to check all swiftasync->swiftasync tail calls.

[varungandhi-apple]

Summary

When -enable-swifttailcc-musttail-check is passed (off by default), we will
check that all swiftasync->swiftasync tail calls are marked musttail.

This can be used to catch codegen bugs with a missing musttail.

[davezarzycki]

LGTM but I don't feel ownership over this code.

[varungandhi-apple]

clang-format

[dexonsmith]

llvm/lib/IR/Verifier.cpp

3431

Hmm... I'm not sure it's right for the verifier to behave differently depending on NDEBUG -- note that these Assert calls are not the same as the assert macro from <cassert>. If this was intentional, can you explain why?

[dexonsmith]

This doesn't look like a particularly expensive verifier check (although maybe I've missed something). What's the motivation for hiding it behind EnableSwiftTailCCMustTailCheck? Have you considered using bitcode AutoUpgrade to fix old IR?

llvm/lib/IR/Verifier.cpp

3432–3439

I wonder if the verifier failure message would be more helpful if some of what's being asserted is in the assertion. Maybe, at least the isa_and_nonnull check; maybe also the calling convention checks, but I'm not sure.

[varungandhi-apple]

I used Assert for two reasons: (1) the surrounding code uses Assert, so it seemed like the right thing to use and (2) in case there's a failure, it will display the instruction missing the musttail.

I'm using NDEBUG because we would like this check to not be turned on for release builds.

Happy to change the code to something different/more idiomatic so long as it has the same effect.

[aschwaighofer]

llvm/lib/IR/Verifier.cpp

3431

We want these errors in assert builds -- so we can fix instances where we are missing musttail instructions -- but we don't want them in release builds because they are not necessarily fatal.

An alternative, is to just enable EnableSwiftTailCCMustTailCheck (which is disabled per default) in the frontend if we compile with asserts.

[varungandhi-apple]

This doesn't look like a particularly expensive verifier check (although maybe I've missed something). What's the motivation for hiding it behind EnableSwiftTailCCMustTailCheck?

Having a flag makes it easier to turn off from Swift if we need to turn it off for some reason. Missing the musttail is technically not a fatal error, but it increases the risk of stack overflow if Swift doesn't generate the right IR.

[dexonsmith]

llvm/lib/IR/Verifier.cpp

3431

I think that alternative (skip the NDEBUG, only set EnableSwiftTailCCMustTailCheck when there's a desire to enable it) seems a bit cleaner to me -- fewer moving parts. Also, I just noticed there's no test for this verifier check; I think we usually use llvm/test/Verifier (and there won't be a need for REQUIRES: asserts if you don't use NDEBUG).

Is the goal to eventually have it on always in the fullness of time? I think we usually use the verifier for IR invariants, but it sounds like maybe that's not what this is.

[varungandhi-apple]

llvm/lib/IR/Verifier.cpp

3432–3439

So it would be like

Assert(!(CI.getCallingConv() == CallingConv::SwiftTail || 
         CI.getCaller()->getCallingConv() == CallingConv::SwiftTail ||
          isa_and_nonnull<ReturnInst>(CI.getNextNode()),

That's okay with me. The reason I wrote it this way is that since the conditions are kinda' long, I found the textual description to be more concise and direct.

[varungandhi-apple]

llvm/lib/IR/Verifier.cpp

3431

Also, I just noticed there's no test for this verifier check; I think we usually use llvm/test/Verifier

I hadn't realized this; I'll add a test.

Is the goal to eventually have it on always in the fullness of time?

Ideally yes. There shouldn't be a good reason for us to miss musttail on tail calls like this one.

[dexonsmith]

In D103275#2785642, @varungandhi-apple wrote:

I used Assert for two reasons: (1) the surrounding code uses Assert, so it seemed like the right thing to use and (2) in case there's a failure, it will display the instruction missing the musttail.

Absolutely, no debate here!

I'm using NDEBUG because we would like this check to not be turned on for release builds.

As @aschwaighofer pointed out, release builds can just avoid setting the enable flag.

In D103275#2785656, @varungandhi-apple wrote:

This doesn't look like a particularly expensive verifier check (although maybe I've missed something). What's the motivation for hiding it behind EnableSwiftTailCCMustTailCheck?

Having a flag makes it easier to turn off from Swift if we need to turn it off for some reason. Missing the musttail is technically not a fatal error, but it increases the risk of stack overflow if Swift doesn't generate the right IR.

I guess I'm wondering what the trajectory is - if the goal is for this to eventually be an IR invariant for the calling convention, I think a verifier check makes sense; once the codegen bugs are sorted out, and the bitcode upgrade is done, the flag can be switched to on-by-default and eventually removed. But if this will never be an invariant of the IR, I'm not sure the LLVM IR verifier is really the right place for the check.

[dexonsmith]

llvm/lib/IR/Verifier.cpp

3432–3439

Yeah, that seems fine to me, or even just Assert(!isa_and_nonnull<ReturnInst>(...)).

[dexonsmith]

In D103275#2785679, @dexonsmith wrote:

I guess I'm wondering what the trajectory is - if the goal is for this to eventually be an IR invariant for the calling convention, I think a verifier check makes sense; once the codegen bugs are sorted out, and the bitcode upgrade is done, the flag can be switched to on-by-default and eventually removed. But if this will never be an invariant of the IR, I'm not sure the LLVM IR verifier is really the right place for the check.

Ah, I see you've already answered that:

Is the goal to eventually have it on always in the fullness of time?

Ideally yes. There shouldn't be a good reason for us to miss musttail on tail calls like this one.

In that case, should this patch also document the intended invariant (maybe with a caveat that it's not enforced yet?) at the swifttailcc entry in LangRef? (https://llvm.org/docs/LangRef.html#calling-conventions)

@rjmccall , I'd be curious about your thoughts.

(Just to explain the other option on my mind -- if this isn't an IR invariant for the calling convention, just a linting check for IR with bad style, maybe there should be a separate pass for linting, and we keep the verifier focused on whether IR is valid.)

[aschwaighofer]

The whole point behind the swiftasynccc convention (swifttailcc in llvm; whose clang support we still have to upstream I think) is to use only constant stack space for an unbounded number of calls in tail call position. So this is an invariant in my opinion. If a frontend wants to opt out of that invariant in can annotate the call with nottail. The c frontend marks calls in tail position immediately followed by a return as musttail. The swift frontend uses musttail wherever appropriate.

[varungandhi-apple]

1. Added test case.
2. Updated LangRef to note mandatory musttail.
3. Added FIXME to code to remove the flag at a point in the future.
4. Fixed a typo "swiftail" -> "swifttail" in the error message.

[varungandhi-apple]

Removed stray tee command used for debugging.

[rjmccall]

I would be uncomfortable with an invariant that all calls from swifttailcc to swifttailcc must be musttail because we might well want to make non-tail calls in some circumstances. However, I think it would be fine to annotate all such calls as either musttail or a hypothetical notail — at least, I think we could achieve that coming out of the frontend, and we ought to be able to maintain it in IR transformations. To do that, you'd need to actually add a notail, though.

[aschwaighofer]

llvm/docs/LangRef.rst

11360

I think we should clarify that this only applies to calls immediately followed by return.

[aschwaighofer]

@rjmccall The invariant is not (edit: s/is/should not be imo/g) all swiftailcc calls need to be annotate but only calls in tail position - call followed by return.

[aschwaighofer]

notail is not hypothetical it already exists.

[aschwaighofer]

I guess that the 'in tail position' restriction cannot really be used by frontends because it has to predict that otherStuff() cannot be optimized away. So it would not buy us much other than a loss of clarity ...

 if (cond) {
   swifttailcc();
   otherStuff();
   ret;
}

[varungandhi-apple]

1. Flip polarity of enable->disable.
2. Turn on checking by default (instead of being off by default).
3. Remove NDEBUG-dependence.
4. Add more explicit wording around mandatory musttail.
5. Update test case to check both ways and remove "REQUIRES: asserts".

[dexonsmith]

In D103275#2787268, @aschwaighofer wrote:

I guess that the 'in tail position' restriction cannot really be used by frontends because it has to predict that otherStuff() cannot be optimized away. So it would not buy us much other than a loss of clarity ...

Yeah, I think that's right. The check for ReturnInst seems quite fragile. Replacing it with a restriction that frontends need to explicitly say notail or musttail seems much easier to reason about.

To that end, a bunch of more specific feedback inline.

llvm/docs/LangRef.rst

447–450

I think this is a good place to document that all calls to swifttailcc from swifttailcc must be marked with either notail or musttail.

11323–11329

I'm not sure you need this change. The text is already clear that musttail means the tail call is mandatory for this particular call.

11360

Given John's feedback about using notail and musttail, I think the return restriction should be dropped, and this content moved to the section on swifttailcc.

llvm/lib/IR/Verifier.cpp

3424–3425

Maybe a better name would be -disable-swifttailcc-check or -disable-verify-swifttailcc? Since it's not just about musttail anymore.

3507

I suggest reverting this change (and the one to verifyMustTailCall()), since the new invariant isn't just about musttail. Instead, you can just add the new check directly in visitCallInst(), or add/call a new function called something like verifyCallingConv().

Incorporating John's feedback about using notail instead of ret, I think the check would be something like:

if (!Disable... &&
    CI.getCallingConv() == CallingConv::SwiftTail &&
    CI.getCaller()->getCallingConv() == CallingConv::SwiftTail)
  Assert(CI.isMustTailCall() || CI.isNoTailCall(), ...);

llvm/test/Verifier/musttail-missing.ll

5–9

This is a great start. It should also check that the verifier doesn't fire when the IR is valid.

Taking into account John's feedback, I think the matrix should be:

• musttail vs. notail vs. tail vs. none of the above (former two are valid, latter two are invalid)
• one of callee and caller is swifttailcc, and the other is not (one example for each direction where the IR would be invalid if both were swiftailcc)

Assuming we're dropping the rule about other instructions before ret we probably don't need that in the matrix.

[efriedma]

If a swifttailcc function calls another swifttailcc in a non-tail position, the proposed rule is that it has to be marked notail? Not sure I understand the justification here. Is there some reason we need to forbid sibcall optimization of swifttailcc functions?

This might just be one of those unfortunate cases where we need to accept suspicious IR to avoid imposing awkward restrictions on optimizations. If you're just trying to audit IR for suspicious constructs, we do have a separate "lint" pass.

[aschwaighofer]

@efriedma It is critical for Swift that ‘swifttailcc’ function calls in tail position be executed in constant stack space. Guaranteed tail call opt was the reason why we added this convention.

We want to guarantee that such calls coming out of the front end be and stay optimizable hence we want to enforce that a call in tail cal position is annotated with musttail coming out of the frontends and that this property is maintained throughout optimization.

llvm/docs/LangRef.rst

"``tailcc``" - Tail callable calling convention
     whenever possible. `Tail calls can only be optimized when this, the fastcc,
     the GHC or the HiPE convention is used. <CodeGenerator.html#id80>`_ This
     calling convention does not support varargs and requires the prototype of
     all callees to exactly match the prototype of the function definition.
 "``swiftcc``" - This calling convention is used for Swift language.
     - On X86-64 RCX and R8 are available for additional integer returns, and
       XMM2 and XMM3 are available for additional FP/vector returns.
     - On iOS platforms, we use AAPCS-VFP calling convention.
 "``swifttailcc``"
     This calling convention is like ``swiftcc`` in most respects, but also the
     callee pops the argument area of the stack so that mandatory tail calls are 
     possible as in ``tailcc``.
 "``cfguard_checkcc``" - Windows Control Flow Guard (Check mechanism)
     This calling convention is used for the Control Flow Guard check function,
     calls to which can be inserted before indirect calls to check that the call
     target is a valid function address. The check function has no return value,
     but it will trigger an OS-level error if the address is not a valid target.
     The set of registers preserved by the check function, and the register
     containing the target address are architecture-specific.
 

 
 The '``call``' instruction represents a simple function call.
 
 Arguments:
 """"""""""
 
 This instruction requires several arguments:
 
-#. 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 optional ``tail`` and ``musttail`` markers (with one exception for
+   mandatory ``musttail`` when using ``swifttailcc``, see below) 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>` or
       :ref:`preallocated <attr_preallocated>` attribute are forwarded in place.
    #. If the musttail call appears in a function with the ``"thunk"`` attribute
       and the caller and callee both have varargs, than any unprototyped
       arguments in register or memory are forwarded to the callee. Similarly,
- 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.
    - The callee must be varargs iff the caller is varargs. Bitcasting a
      non-varargs function to the appropriate varargs type is legal so
      long as the non-varargs prefixes obey the other rules.
+   - ``musttail`` is mandatory for calls where both the caller and
+     the callee use the ``swifttailcc`` convention, and the call is
+     immediately followed by ``ret``.
 
    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`` or ``tailcc``.
    -  The call is in tail position (ret immediately follows call and ret
       uses value of call or is void).
    -  Option ``-tailcallopt`` is enabled,

llvm/lib/IR/Verifier.cpp

static AttrBuilder getParameterABIAttributes(int I, AttributeList Attrs) {
   // `align` is ABI-affecting only in combination with `byval` or `byref`.
   if (Attrs.hasParamAttribute(I, Attribute::Alignment) &&
       (Attrs.hasParamAttribute(I, Attribute::ByVal) ||
        Attrs.hasParamAttribute(I, Attribute::ByRef)))
     Copy.addAlignmentAttr(Attrs.getParamAlignment(I));
   return Copy;
 }
 
+// FIXME: This flag should eventually be removed and the check should be on by
+// default.
+static cl::opt<bool> DisableSwiftTailCCMustTailCheck(
+    "disable-swifttailcc-musttail-check", cl::init(false),
+    cl::desc("Check that tail calls from swifttailcc functions to"
+             " swifttailcc functions are marked musttail."));
+
 void Verifier::verifyMustTailCall(CallInst &CI) {
+  if (!CI.isMustTailCall()) {
+    if (!DisableSwiftTailCCMustTailCheck &&
+        CI.getCallingConv() == CallingConv::SwiftTail &&
+        CI.getCaller()->getCallingConv() == CallingConv::SwiftTail &&
+        isa_and_nonnull<ReturnInst>(CI.getNextNode())) {
+      Assert(false,
+             "tail call from swifttail->swifttail should be marked musttail",
+             &CI);
+    }
+    return;
+  }
+
   Assert(!CI.isInlineAsm(), "cannot use musttail call with inline asm", &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();
   FunctionType *CallerTy = F->getFunctionType();
   FunctionType *CalleeTy = CI.getFunctionType();
void Verifier::verifyMustTailCall(CallInst &CI) {
   Assert(Ret, "musttail call must precede a ret with an optional bitcast",
          &CI);
   Assert(!Ret->getReturnValue() || Ret->getReturnValue() == RetVal,
          "musttail call result must be returned", Ret);
 }
 
 void Verifier::visitCallInst(CallInst &CI) {
   visitCallBase(CI);
-
-  if (CI.isMustTailCall())
-    verifyMustTailCall(CI);
 }
 
 void Verifier::visitInvokeInst(InvokeInst &II) {
   visitCallBase(II);
 
   // Verify that the first non-PHI instruction of the unwind destination is an
   // exception handling instruction.
   Assert(

llvm/test/Verifier/musttail-missing.ll

+; RUN: llvm-as %s -disable-swifttailcc-musttail-check -o /dev/null
+; RUN: not llvm-as %s -o /dev/null 2>&1 | FileCheck %s
+
+declare swifttailcc void @swift_callee()
+define swifttailcc void @swift_caller() {
+; CHECK: tail call from swifttail->swifttail should be marked musttail
+  call swifttailcc void @swift_callee()
+  ret void
+}