I've seen that gcc7 supports the CALL_EXPR_MUST_TAIL_CALL flag internally. Unfortunately it is not exposed to the frontend. As of now it seems only possible to use the flag via a plugin (See below). Regarding the plugin I couldn't figure out quickly how to register a pragma which annotates the subsequent call. Therefore I used a variable named __musttail as marker. Is there some documentation on how to create such a pragma properly? test.c: #include <stdio.h> #define MUSTTAIL(f) ({ \ __attribute__ ((unused)) int __musttail; \ return f; \ }) void g() { printf("g called\n"); } void f() { printf("f called\n"); MUSTTAIL(g()); } int main() { f(); return 0; } musttail.cc: #include <gcc-plugin.h> #include <plugin-version.h> #include <tree.h> #include <c-family/c-pragma.h> #include <stdio.h> int plugin_is_GPL_compatible; static tree process_musttail(tree* tp, int* walk_subtrees, void* data ATTRIBUTE_UNUSED) { static bool musttail = false; const char* name = get_name(*tp); if (name) { if (!strcmp(name, "__musttail")) musttail = true; } if (musttail && TREE_CODE(*tp) == CALL_EXPR) { CALL_EXPR_MUST_TAIL_CALL(*tp) = true; musttail = false; } return NULL_TREE; } static void callback(void *gcc_data, void *user_data) { tree fndecl = (tree)gcc_data; gcc_assert(TREE_CODE(fndecl) == FUNCTION_DECL); walk_tree(&DECL_SAVED_TREE(fndecl), process_musttail, NULL, NULL); } int plugin_init(plugin_name_args *plugin_info, plugin_gcc_version *version) { if (!plugin_default_version_check(version, &gcc_version)) return 1; const char *plugin_name = plugin_info->base_name; register_callback(plugin_name, PLUGIN_PRE_GENERICIZE, callback, NULL); return 0; }
See also bug 77734
I created a plugin that lets you annotate a whole function as musttail: https://github.com/pietro/gcc-musttail-plugin/ I think that in order to add an attribute to the return statement like clang has done the parser for the C frontend needs to be modified.
*** Bug 112558 has been marked as a duplicate of this bug. ***
https://gcc.gnu.org/pipermail/gcc/2021-April/235882.html https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html The lack of this feature is motivating CPython to rely on LLVM for its JIT in future releases.
To get guaranteed tail-calls to work you need to adjust the calling convention for the caller as well as the callee. Things are trivial as long as parameters always fit in registers. With parameters on the stack you need, in general, to shift the responsibility for their deallocation from caller to callee, and this results in a non-standard calling convention.
(In reply to David Edelsohn from comment #4) > The lack of this feature is motivating CPython to rely on LLVM for its JIT > in future releases. Which is interesting because GCC JIT supports this already. Just not exposed to C. That was mentioned in the gcc mailing list archive that you pointed to too. e.g. https://gcc.gnu.org/onlinedocs/jit/topics/expressions.html#c.gcc_jit_rvalue_set_bool_require_tail_call
https://github.com/llvm/llvm-project/issues/72555 Hmmm
(In reply to David Edelsohn from comment #4) > The lack of this feature is motivating CPython to rely on LLVM for its JIT > in future releases. Do you have something I can read up on for this part? It's the first I've heard it.
Brandt Bucher: A JIT compiler for CPython https://www.youtube.com/watch?v=HxSHIpEQRjs https://github.com/brandtbucher/cpython/tree/justin
(In reply to David Edelsohn from comment #9) > Brandt Bucher: A JIT compiler for CPython > https://www.youtube.com/watch?v=HxSHIpEQRjs > https://github.com/brandtbucher/cpython/tree/justin But must tail is there for the gcc jit interface already. Maybe it is not exposed to c/c++ attribute but it is there already. So maybe this is just not noticing that point.
GIMPLE supports must_tail, but it is not exposed at the sources level / attributes in GCC. CPython is not adding the LLVM JIT at runtime. The proposal is to utilize LLVM at build time to generate code templates that can be copied into the CPython binary and patched with relocations. CALL_EXPR_MUST_TAIL_CALL and libgccjit are not sufficient for the CPython plan. The plan does not propose connecting CPython to an existing JIT in LLVM (or GCC).
(In reply to David Edelsohn from comment #11) > GIMPLE supports must_tail, but it is not exposed at the sources level / > attributes in GCC. > > CPython is not adding the LLVM JIT at runtime. The proposal is to utilize > LLVM at build time to generate code templates that can be copied into the > CPython binary and patched with relocations. This is now up as https://github.com/python/cpython/pull/113465 and https://github.com/python/cpython/issues/113464. See also PR110899 and https://discourse.llvm.org/t/rfc-exposing-ghccc-calling-convention-as-preserve-none-to-clang/74233 (which is linked from the CPython PR for adding the JIT).
Patches posted by Andi Kleen: https://inbox.sourceware.org/gcc-patches/20240124110800.3154093-2-ak@linux.intel.com/.
Latest patchkit is here, but stalled due to lack of reviewers: https://gcc.gnu.org/pipermail/gcc-patches/2024-June/653319.html
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:a6502accf381358173b19e615fdeb0aa17949c93 commit r15-2122-ga6502accf381358173b19e615fdeb0aa17949c93 Author: Andi Kleen <ak@linux.intel.com> Date: Tue Jan 23 23:42:08 2024 -0800 Improve must tail in RTL backend - Give error messages for all causes of non sibling call generation - When giving error messages clear the musttail flag to avoid ICEs - Error out when tree-tailcall failed to mark a must-tail call sibcall. In this case it doesn't know the true reason and only gives a vague message. gcc/ChangeLog: PR c/83324 * calls.cc (maybe_complain_about_tail_call): Clear must tail flag on error. (expand_call): Give error messages for all musttail failures.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:b738a63e528db410a1c51fc27db37fe22f0cb397 commit r15-2124-gb738a63e528db410a1c51fc27db37fe22f0cb397 Author: Andi Kleen <ak@linux.intel.com> Date: Wed May 15 19:57:22 2024 -0700 Enable musttail tail conversion even when not optimizing Enable the tailcall optimization for non optimizing builds, but in this case only checks calls that have the musttail attribute set. This makes musttail work without optimization. This is done with a new late musttail pass that is only active when not optimizing. The new pass relies on tree-cfg to discover musttails. This avoids a ~0.8% compiler run time penalty at -O0. gcc/ChangeLog: PR c/83324 * function.h (struct function): Add has_musttail. * lto-streamer-in.cc (input_struct_function_base): Stream has_musttail. * lto-streamer-out.cc (output_struct_function_base): Dito. * passes.def (pass_musttail): Add. * tree-cfg.cc (notice_special_calls): Record has_musttail. (clear_special_calls): Clear has_musttail. * tree-pass.h (make_pass_musttail): Add. * tree-tailcall.cc (find_tail_calls): Handle only_musttail argument. (tree_optimize_tail_calls_1): Pass on only_musttail. (execute_tail_calls): Pass only_musttail as false. (class pass_musttail): Add. (make_pass_musttail): Add.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:81824596361cf4919d6dc026155160581c99b860 commit r15-2125-g81824596361cf4919d6dc026155160581c99b860 Author: Andi Kleen <ak@linux.intel.com> Date: Tue May 21 07:01:57 2024 -0700 Give better error messages for musttail When musttail is set, make tree-tailcall give error messages when it cannot handle a call. This avoids vague "other reasons" error messages later at expand time when it sees a musttail function not marked tail call. In various cases this requires delaying the error until the call is discovered. Also print more information on the failure to the dump file. gcc/ChangeLog: PR c/83324 * tree-tailcall.cc (maybe_error_musttail): New function. (suitable_for_tail_opt_p): Report error reason. (suitable_for_tail_call_opt_p): Report error reason. (find_tail_calls): Accept basic blocks with abnormal edges. Delay reporting of errors until the call is discovered. Move top level suitability checks to here. (tree_optimize_tail_calls_1): Remove top level checks.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:d062b0abf45cd54057352fc4b7827a3b1b9a160a commit r15-2126-gd062b0abf45cd54057352fc4b7827a3b1b9a160a Author: Andi Kleen <ak@linux.intel.com> Date: Fri Jun 21 11:19:12 2024 -0700 Mark expand musttail error messages for translation The musttail error messages are reported to the user, so must be translated. gcc/ChangeLog: PR c/83324 * calls.cc (initialize_argument_information): Mark messages for translation. (can_implement_as_sibling_call_p): Dito. (expand_call): Dito.
Middle/back-end parts are in, still need acks for the C/C++ frontend parts
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:5c4c1fe6df0f752764cdfd7404a60bfd2b4f5057 commit r15-2168-g5c4c1fe6df0f752764cdfd7404a60bfd2b4f5057 Author: Andi Kleen <ak@linux.intel.com> Date: Wed May 15 19:38:43 2024 -0700 Add a musttail generic attribute to the c-attribs table The actual handling is directly in the parser since the generic mechanism doesn't support statement attributes, but this gives basic error checking/detection on the attribute. gcc/c-family/ChangeLog: PR c/83324 * c-attribs.cc (handle_musttail_attribute): Add. * c-common.h (handle_musttail_attribute): Add.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:59dd1d7ab21ad9a7ebf641ec9aeea609c003ad2f commit r15-2169-g59dd1d7ab21ad9a7ebf641ec9aeea609c003ad2f Author: Andi Kleen <ak@linux.intel.com> Date: Tue Jan 23 23:44:48 2024 -0800 C++: Support clang compatible [[musttail]] (PR83324) This patch implements a clang compatible [[musttail]] attribute for returns. musttail is useful as an alternative to computed goto for interpreters. With computed goto the interpreter function usually ends up very big which causes problems with register allocation and other per function optimizations not scaling. With musttail the interpreter can be instead written as a sequence of smaller functions that call each other. To avoid unbounded stack growth this requires forcing a sibling call, which this attribute does. It guarantees an error if the call cannot be tail called which allows the programmer to fix it instead of risking a stack overflow. Unlike computed goto it is also type-safe. It turns out that David Malcolm had already implemented middle/backend support for a musttail attribute back in 2016, but it wasn't exposed to any frontend other than a special plugin. This patch adds a [[gnu::musttail]] attribute for C++ that can be added to return statements. The return statement must be a direct call (it does not follow dependencies), which is similar to what clang implements. It then uses the existing must tail infrastructure. For compatibility it also detects clang::musttail Passes bootstrap and full test gcc/c-family/ChangeLog: * c-attribs.cc (set_musttail_on_return): New function. * c-common.h (set_musttail_on_return): Declare new function. gcc/cp/ChangeLog: PR c/83324 * cp-tree.h (AGGR_INIT_EXPR_MUST_TAIL): Add. * parser.cc (cp_parser_statement): Handle musttail. (cp_parser_jump_statement): Dito. * pt.cc (tsubst_expr): Copy CALL_EXPR_MUST_TAIL_CALL. * semantics.cc (simplify_aggr_init_expr): Handle musttail.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:7db47f7b915c5f5d645fa536547e26b92290afe3 commit r15-2170-g7db47f7b915c5f5d645fa536547e26b92290afe3 Author: Andi Kleen <ak@linux.intel.com> Date: Wed Jan 24 07:44:23 2024 -0800 C: Implement musttail attribute for returns Implement a C23 clang compatible musttail attribute similar to the earlier C++ implementation in the C parser. gcc/c/ChangeLog: PR c/83324 * c-parser.cc (struct attr_state): Define with musttail_p. (c_parser_statement_after_labels): Handle [[musttail]]. (c_parser_std_attribute): Dito. (c_parser_handle_musttail): Dito. (c_parser_compound_statement_nostart): Dito. (c_parser_all_labels): Dito. (c_parser_statement): Dito. * c-tree.h (c_finish_return): Add musttail_p flag. * c-typeck.cc (c_finish_return): Handle musttail_p flag.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:56f824cc206ff00d466aaeb11211d8005c4668bc commit r15-2172-g56f824cc206ff00d466aaeb11211d8005c4668bc Author: Andi Kleen <ak@linux.intel.com> Date: Tue Jan 23 23:38:23 2024 -0800 Add documentation for musttail attribute gcc/ChangeLog: PR c/83324 * doc/extend.texi: Document [[musttail]]
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:2bd8177256b6d87f6e75819218cf22c2c0bfc1ac commit r15-2231-g2bd8177256b6d87f6e75819218cf22c2c0bfc1ac Author: Andi Kleen <ak@linux.intel.com> Date: Tue Jan 23 23:44:48 2024 -0800 C++: Support clang compatible [[musttail]] (PR83324) This patch implements a clang compatible [[musttail]] attribute for returns. musttail is useful as an alternative to computed goto for interpreters. With computed goto the interpreter function usually ends up very big which causes problems with register allocation and other per function optimizations not scaling. With musttail the interpreter can be instead written as a sequence of smaller functions that call each other. To avoid unbounded stack growth this requires forcing a sibling call, which this attribute does. It guarantees an error if the call cannot be tail called which allows the programmer to fix it instead of risking a stack overflow. Unlike computed goto it is also type-safe. It turns out that David Malcolm had already implemented middle/backend support for a musttail attribute back in 2016, but it wasn't exposed to any frontend other than a special plugin. This patch adds a [[gnu::musttail]] attribute for C++ that can be added to return statements. The return statement must be a direct call (it does not follow dependencies), which is similar to what clang implements. It then uses the existing must tail infrastructure. For compatibility it also detects clang::musttail Passes bootstrap and full test gcc/c-family/ChangeLog: * c-attribs.cc (set_musttail_on_return): New function. * c-common.h (set_musttail_on_return): Declare new function. gcc/cp/ChangeLog: PR c/83324 * cp-tree.h (AGGR_INIT_EXPR_MUST_TAIL): Add. * parser.cc (cp_parser_statement): Handle musttail. (cp_parser_jump_statement): Dito. * pt.cc (tsubst_expr): Copy CALL_EXPR_MUST_TAIL_CALL. * semantics.cc (simplify_aggr_init_expr): Handle musttail.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:78bbdbd5352df527feccf0a8c2f862f25a2e88b4 commit r15-2232-g78bbdbd5352df527feccf0a8c2f862f25a2e88b4 Author: Andi Kleen <ak@linux.intel.com> Date: Wed Jan 24 07:44:23 2024 -0800 C: Implement musttail attribute for returns Implement a C23 clang compatible musttail attribute similar to the earlier C++ implementation in the C parser. gcc/c/ChangeLog: PR c/83324 * c-parser.cc (struct attr_state): Define with musttail_p. (c_parser_statement_after_labels): Handle [[musttail]]. (c_parser_std_attribute): Dito. (c_parser_handle_musttail): Dito. (c_parser_compound_statement_nostart): Dito. (c_parser_all_labels): Dito. (c_parser_statement): Dito. * c-tree.h (c_finish_return): Add musttail_p flag. * c-typeck.cc (c_finish_return): Handle musttail_p flag.
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>: https://gcc.gnu.org/g:8daae81113eeff37b4ae2e08a9797295fbc8b81e commit r15-2234-g8daae81113eeff37b4ae2e08a9797295fbc8b81e Author: Andi Kleen <ak@linux.intel.com> Date: Tue Jan 23 23:38:23 2024 -0800 Add documentation for musttail attribute gcc/ChangeLog: PR c/83324 * doc/extend.texi: Document [[musttail]]
Implemented in trunk in a mostly LLVM compatible way. There are some remaining open issues (PR116019, PR115979, PR115606, PR115607) , but none should be show stoppers. There are some differences to clang, mainly that gcc handles a few cases that clang doesn't, but clang handles more cases with -O0. The success also depends on the architecture and the languages (C is better than C++ due to PR115606)
I'd like to ask whether this new attribute replaces or otherwise interacts with the existing -foptimize-sibling-calls flag. Thanks. Brad
The semantics of -foptimize-sibling-calls do not change. However if your program depends on sbling calls for correctness it should migrate to the new attribute
Thanks. I asked for some help in testing this new attribute at gcc-help: https://gcc.gnu.org/pipermail/gcc-help/2024-August/143676.html
Are there plans to support the __attribute__((musttail)) notation for C code? It appears that with heine:~/programs/gambit/gambit> clang -v Ubuntu clang version 14.0.0-1ubuntu1.1 one needs to pass something like -std=c2x on the command line to support [[clang::musttail]], while this clang supports __attribute__((musttail)) "out of the box", as it were.
The feature is currently only supported with standard C/C++ attributes ([[clang/gnu::musttail]]), not __attribute__ But given that you have existing code that uses the old syntax and clang supports that too we should probably add that too.
I don't know what the issues are about whether to support __attribute__, whether the notation is obsolete or nonstandard. If gcc doesn't support this notation, it might lead to just one more #ifdef in the user code.
Yeah I think GCC should support the __attribute__ style syntax for this attribute, too
*** Bug 52067 has been marked as a duplicate of this bug. ***