Add support for function attribute "notail"

[ahatanak]

Summary

This patch adds support for a new function attribute "notail". The attribute is used to disable tail call optimization on calls to functions marked with the attribute.

This is different from the attribute proposed in D12547, which disables tail call optimizations on call sites within the marked function.

http://reviews.llvm.org/D12547

[ahatanak]

The llvm-side patch is here: http://reviews.llvm.org/D12923

[dexonsmith]

I wonder if 'notailcall' be better, since it contains a verb (like 'noinline'). I don't have a strong opinion; just putting the alternative out there.

[ahatanak]

I've made some changes following the discussion I had and the feedback I got on the llvm-side patch.

This is the link to the discussion thread:
http://thread.gmane.org/gmane.comp.compilers.llvm.cvs/271105/

The difference between the previous patch and this patch lies in the way indirect calls (at the source level) are handled. The approach taken in the previous patch attached the notail attribute to the declaration or definition of functions in the IR, which enabled blocking tail call optimization on an indirect call site if the compiler could statically determine it was calling a function marked notail. In this patch, clang marks a call instruction in the IR as notail only if it is a direct call to a function marked "notail". It does nothing to prevent tail call on indirect call sites.

I think there are a couple of things that have to be discussed:

1. Name of the attribute: Should it be "notail" or "notailcall"? Perhaps it should be named something like "nodirecttail" to indicate it is used to block direct calls, but not indirect calls?

2. Can we guarantee or promise that the attribute will *always* block direct calls (but do nothing for indirect calls)? Or should we say this attribute only prevents tail call (even for direct calls) on a best effort basis in case it turns out there are cases where it isn't possible to keep that promise?

[aaron.ballman]

In D12922#265452, @ahatanak wrote:

I think there are a couple of things that have to be discussed:

1. Name of the attribute: Should it be "notail" or "notailcall"? Perhaps it should be named something like "nodirecttail" to indicate it is used to block direct calls, but not indirect calls?

The attribute prevents tail calls from the call site, not for the function itself. "notail", at least to me, implies that the function definition itself will not have TCO; it does not imply that callers will be affected. Perhaps "not_tail_called" or "disable_tail_calls"? It's a hard concept to get across in a small identifier.

Also, I would like to see a test that shows always_inline, notail also gets diagnosed as mutually exclusive, and a test that the right thing happens with a C++ spelling on a member function.

~Aaron

include/clang/Basic/AttrDocs.td

1619

It would be good to clarify what you mean by direct calls, as not all of the readers are going to understand that easily. Perhaps a simple code example showing a call to the function, and a call to the same function through a function pointer, with comments showing which one has TCO.

You should also call out that it is mutually exclusive with always_inline.

lib/Sema/SemaDeclAttr.cpp

1705

Missing the same check in the always_inline attribute handler.

[ahatanak]

Address some of the review comments:

• Added a c++ test which tests the c++ spelling of the attribute on member functions and shows which virtual functions calls get marked as "notail" in the IR.
• Added a check that was missing in always_inline attribute handler.
• Fixed test/Sema/attr-notail.c to test always_inline and notail are mutually exclusive, regardless of the order in which they are added to the function.

[ahatanak]

include/clang/Basic/AttrDocs.td

1619

Perhaps direct call isn't the right term to use for this attribute. I'm still trying to figure out the best way to handle c++ virtual functions: this attribute is not very useful for someone who is looking for a way to reliably prevent tail-call to a virtual function.

[ahatanak]

Address review comments:

1. Renamed the attribute to "not_tail_called".

I chose "not_tail_called" over "notailcall" or "notail" to better distinguish it from the attribute that is proposed in http://reviews.llvm.org/D12547 (which is tentatively named "disable_tail_calls").

2. Made changes to error-out if a virtual function or an objective-c method is marked "not_tail_called".

I made this change because this attribute isn't useful when the compiler cannot resolve the function call statically at compile time and it isn't important for the use case I have.

3. Added code examples to AttrDocs.td.

[aaron.ballman]

lib/Sema/SemaDecl.cpp

5374 ↗

(On Diff #37816)

Is there a reason this is here instead of SemaDeclAttr.cpp? It seems like the decl passed in with the attribute attached to it should already be known to be virtual or not?

test/Sema/attr-notail.c

9

Missing a test case for the attribute being specified on something other than a function, and one for being passed arguments.

test/SemaCXX/attr-notail.cpp

5 ↗

(On Diff #37816)

Missing the "s" on virtual functions.

[ahatanak]

lib/Sema/SemaDecl.cpp

5374 ↗

(On Diff #37816)

I initially did the check in SemaDeclAttr.cpp but found out that methods declared override are not known to be virtual (isVirtual returns false) when ProcessDeclAttributes is called:

class Base {

// This method is fine.
virtual int foo1();

};

class Derived1 : public Base {

// isVirtual() is false for the declaration of this method.
int foo1() override;

};

This is because ProcessDeclAttributes is called before CheckFunctionDeclaration (in line 7952, which calls Sema::AddOverriddenMethods) is called in Sema::ActOnFunctionDeclarator. Unless there is another way to check if a method is virtual, I don't think we can move the check to SemaDeclAttr.cpp?

[ahatanak]

Fixed test cases:

• Added a test case for the attribute being specified on a variable.
• Added a missing 's' to "virtual function" in the check strings.

[ahatanak]

test/Sema/attr-notail.c

10

I didn't understand what kind of test case is required for not_tail_called on passed arguments. Could you give me an example?

[aaron.ballman]

test/Sema/attr-notail.c

10

Sorry, I may have been unclear. I meant the attribute being passed arguments itself. e.g.,

int f() __attribute__((not_tail_called("this should diagnose")));

[ahatanak]

Added test case that produces an error diagnostic if an argument is passed for not_tail_called.

[aaron.ballman]

lib/Sema/SemaDecl.cpp

5374 ↗

(On Diff #39003)

I am not home yet, and so I don't have the source code to try this out, but I have a sneaking suspicion there's a way to tell whether a function is an override. IIRC, it's something like overridden_methods() on a CXXMethodDecl.

I will do some poking when I am back in front of the source. Otherwise, I would guess you can look at some of the diagnostics in DiagnosticSemaKinds.td for the override keyword itself, because I bet we warn when you specify override on something that isn't a virtual function override, and that should have a code example.

[ahatanak]

lib/Sema/SemaDecl.cpp

5374 ↗

(On Diff #39003)

It's possible to tell a method is a virtual function if either an overridden method is added to its declaration (which will cause isVirtual() to return true) or an OverrideAttr attribute is added. Currently, processDeclAttributes is called before these methods or attributes are added, and that is why I think it isn't possible to tell if the method is virtual when the attributes are being checked.

[aaron.ballman]

LGTM!

lib/Sema/SemaDecl.cpp

5374 ↗

(On Diff #39003)

Ugh, that is really unfortunate, but I think you're right. At some point, we may have to find a way to handle this, but I don't think that should hold up your patch.

[ahatanak]

Thanks, I'll see how the review for the llvm-side patch goes and commit both patches after it is approved.

include/clang/Basic/Attr.td

 }
 
 def NoInstrumentFunction : InheritableAttr {
   let Spellings = [GCC<"no_instrument_function">];
   let Subjects = SubjectList<[Function]>;
   let Documentation = [Undocumented];
 }
 
+def NoTail : InheritableAttr {
+  let Spellings = [GNU<"notail">, CXX11<"clang", "notail">];
+  let Subjects = SubjectList<[Function, ObjCMethod]>;
+  let Documentation = [NoTailDocs];
+}
+
 def NoThrow : InheritableAttr {
   let Spellings = [GCC<"nothrow">, Declspec<"nothrow">];
   let Documentation = [Undocumented];
 }
 
 def NvWeak : IgnoredAttr {
   let Spellings = [GNU<"nv_weak">];
   let LangOpts = [CUDA];

include/clang/Basic/AttrDocs.td

 def NoAliasDocs : Documentation {
   let Category = DocCatFunction;
   let Content = [{
 The ``noalias`` attribute indicates that the only memory accesses inside
 function are loads and stores from objects pointed to by its pointer-typed
 arguments, with arbitrary offsets.
   }];
 }
+
+def NoTailDocs : Documentation {
+  let Category = DocCatFunction;
+  let Content = [{
+Tail call optimization is not performed on direct calls to a function marked ``notail``.
+  }];
+}

lib/CodeGen/CGCall.cpp

#endif
   // after any return-value munging.
   if (CallArgs.hasWritebacks())
     emitWritebacks(*this, CallArgs);
 
   // The stack cleanup for inalloca arguments has to run out of the normal
   // lexical order, so deactivate it and run it manually here.
   CallArgs.freeArgumentMemory(*this);
 
+  if (llvm::CallInst *Call = dyn_cast<llvm::CallInst>(CI))
+    if (TargetDecl && TargetDecl->hasAttr<NoTailAttr>())
+      Call->setTailCallKind(llvm::CallInst::TCK_NoTail);
+
   RValue Ret = [&] {
     switch (RetAI.getKind()) {
     case ABIArgInfo::InAlloca:
     case ABIArgInfo::Indirect: {
       RValue ret = convertTempToRValue(SRetPtr, RetTy, SourceLocation());
       if (UnusedReturnSize)
         EmitLifetimeEnd(llvm::ConstantInt::get(Int64Ty, UnusedReturnSize),
                         SRetPtr.getPointer());

lib/Sema/SemaDeclAttr.cpp

if (isa<ParmVarDecl>(D)) {
     }
   }
 
   D->addAttr(::new (S.Context) CarriesDependencyAttr(
                                    Attr.getRange(), S.Context,
                                    Attr.getAttributeSpellingListIndex()));
 }
 
+static void handleNoTailAttr(Sema &S, Decl *D, const AttributeList &Attr) {
+  if (checkAttrMutualExclusion<AlwaysInlineAttr>(S, D, Attr))
+    return;
+
+  D->addAttr(::new (S.Context) NoTailAttr(
+      Attr.getRange(), S.Context, Attr.getAttributeSpellingListIndex()));
+}
+
 static void handleUsedAttr(Sema &S, Decl *D, const AttributeList &Attr) {
   if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
     if (VD->hasLocalStorage()) {
       S.Diag(Attr.getLoc(), diag::warn_attribute_ignored) << Attr.getName();
       return;
     }
   } else if (!isFunctionOrMethod(D)) {
     S.Diag(Attr.getLoc(), diag::warn_attribute_wrong_decl_type)
if (D->hasAttr<OptimizeNoneAttr>())
     return nullptr;
 
   return ::new (Context) OptimizeNoneAttr(Range, Context,
                                           AttrSpellingListIndex);
 }
 
 static void handleAlwaysInlineAttr(Sema &S, Decl *D,
                                    const AttributeList &Attr) {
+  if (checkAttrMutualExclusion<NoTailAttr>(S, D, Attr))
+    return;
+
   if (AlwaysInlineAttr *Inline = S.mergeAlwaysInlineAttr(
           D, Attr.getRange(), Attr.getName(),
           Attr.getAttributeSpellingListIndex()))
     D->addAttr(Inline);
 }
 
 static void handleMinSizeAttr(Sema &S, Decl *D, const AttributeList &Attr) {
   if (MinSizeAttr *MinSize = S.mergeMinSizeAttr(
case AttributeList::AT_ObjCRequiresPropertyDefs:
     handleSimpleAttribute<ObjCRequiresPropertyDefsAttr>(S, D, Attr);
     break;
   case AttributeList::AT_Unused:
     handleSimpleAttribute<UnusedAttr>(S, D, Attr);
     break;
   case AttributeList::AT_ReturnsTwice:
     handleSimpleAttribute<ReturnsTwiceAttr>(S, D, Attr);
     break;
+  case AttributeList::AT_NoTail:
+    handleNoTailAttr(S, D, Attr);
+    break;
   case AttributeList::AT_Used:
     handleUsedAttr(S, D, Attr);
     break;
   case AttributeList::AT_Visibility:
     handleVisibilityAttr(S, D, Attr, false);
     break;
   case AttributeList::AT_TypeVisibility:
     handleVisibilityAttr(S, D, Attr, true);

test/CodeGen/attr-no-tail.c

+// RUN: %clang_cc1 -triple x86_64-apple-macosx10.7.0 %s -emit-llvm -o - | FileCheck %s
+
+// CHECK: %{{[a-z0-9]+}} = notail call i32 @callee0(i32 %
+// CHECK: %{{[a-z0-9]+}} = notail call i32 @callee1(i32 %
+
+// Check that indirect calls do not have the notail marker.
+// CHECK: store i32 (i32)* @callee1, i32 (i32)** [[ALLOCA1:%[A-Za-z0-9]+]], align 8
+// CHECK: [[INDIRFUNC:%[0-9]+]] = load i32 (i32)*, i32 (i32)** [[ALLOCA1]], align 8
+// CHECK: %{{[a-z0-9]+}} = call i32 [[INDIRFUNC]](i32 %6)
+
+// CHECK: %{{[a-z0-9]+}} = call i32 @callee2(i32 %
+
+int callee0(int a) __attribute__((notail)) {
+  return a + 1;
+}
+
+int callee1(int) __attribute__((notail));
+
+int callee2(int);
+
+typedef int (*FuncTy)(int);
+
+int foo0(int a) {
+  if (a > 1)
+    return callee0(a);
+  if (a == 1)
+    return callee1(a);
+  if (a < 0) {
+    FuncTy F = callee1;
+    return (*F)(a);
+  }
+  return callee2(a);
+}

test/CodeGenCXX/attr-notail.cpp

+// RUN: %clang_cc1 -triple=x86_64-apple-darwin -std=c++11 %s -emit-llvm -o - | FileCheck %s
+
+class Base {
+public:
+  [[clang::notail]] virtual int foo1() {
+    return 0;
+  }
+  virtual ~Base() {}
+};
+
+class Derived1 : public Base {
+public:
+  int foo1() override {
+    return 1;
+  }
+};
+
+class Derived2 : public Derived1 {
+public:
+  [[clang::notail]] int foo1() override {
+    return 2;
+  }
+};
+
+// CHECK-LABEL: define i32 @_Z4foo1iP4BaseP8Derived1
+// CHECK: [[BASEFUNC:%[a-z0-9]+]] = load i32 (%class.Base*)*, i32 (%class.Base*)** {{%[a-z0-9]+}}
+// CHECK: {{%[a-z0-9]+}} = notail call i32 [[BASEFUNC]](%class.Base* {{%[a-z0-9]+}})
+// CHECK: [[DERIVEDFUNC1_1:%[a-z0-9]+]] = load i32 (%class.Derived1*)*, i32 (%class.Derived1*)** {{%[a-z0-9]+}}
+// CHECK: {{%[a-z0-9]+}} = call i32 [[DERIVEDFUNC1_1]](%class.Derived1* {{%[a-z0-9]+}})
+// CHECK: [[DERIVEDFUNC1_2:%[a-z0-9]+]] = load i32 (%class.Derived1*)*, i32 (%class.Derived1*)** {{%[a-z0-9]+}}
+// CHECK: {{%[a-z0-9]+}} = call i32 [[DERIVEDFUNC1_2]](%class.Derived1* {{%[a-z0-9]+}})
+// CHECK: [[DERIVEDFUNC2:%[a-z0-9]+]] = load i32 (%class.Derived2*)*, i32 (%class.Derived2*)** {{%[a-z0-9]+}}
+// CHECK: {{%[a-z0-9]+}} = notail call i32 [[DERIVEDFUNC2]](%class.Derived2* {{%[a-z0-9]+}})
+
+int foo1(int a, Base *b, Derived1 *d) {
+  if (a > 1)
+    return b->foo1(); // Tail-call is prevented.
+  if (a < 0)
+    return d->foo1(); // Tail-call is not prevented.
+  if (a == 0) {
+    Derived1 *i = new Derived2(); // Tail-call is not prevented.
+    return i->foo1();
+  }
+  Derived2 *i = new Derived2(); // Tail-call is prevented.
+  return i->foo1();
+}

test/Sema/attr-notail.c

+// RUN: %clang_cc1 -fsyntax-only -verify %s
+
+int callee0() __attribute__((notail,always_inline)); // expected-error{{'notail' and 'always_inline' attributes are not compatible}}
+int callee1() __attribute__((always_inline,notail)); // expected-error{{'always_inline' and 'notail' attributes are not compatible}}
+
+int foo(int a) {
+  return a ? callee0() : callee1();
+}