* [PATCH 0/3] Support for mandatory tail calls
@ 2016-01-01 0:00 David Malcolm
2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm
` (3 more replies)
0 siblings, 4 replies; 22+ messages in thread
From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw)
To: gcc-patches, jit; +Cc: David Malcolm
There have been requests [1] for libgccjit to better support
functional programming by supporting the contination-passing style,
in which every function "returns" by calling a "continuation"
function pointer.
These calls must be guaranteed to be implemented as a jump,
otherwise the program could consume an arbitrary amount of stack
space as it executed.
This patch kit implements this.
Patch 1 is a preliminary tweak to calls.c
Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL,
which makes calls.c try harder to implement a flagged call as a
tail-call/sibling call, and makes it issue an error if
the optimization is impossible. It doesn't implement any
frontend support for setting the flag (instead using a plugin
to test it). We had some discussion on the jit list about possibly
introducing a new builtin for this, but the patch punts on this
issue.
Patch 3 implements the libgccjit.h API support to allow client
code to set the flag.
[1] https://gcc.gnu.org/ml/jit/2016-q2/msg00010.html
David Malcolm (3):
Introduce can_implement_as_sibling_call_p
Implement CALL_EXPR_MUST_TAIL_CALL
jit: implement gcc_jit_rvalue_set_bool_require_tail_call
gcc/calls.c | 211 +++++++++++++++++----
gcc/cfgexpand.c | 1 +
gcc/gimple-pretty-print.c | 2 +
gcc/gimple.c | 1 +
gcc/gimple.h | 20 ++
gcc/jit/docs/topics/compatibility.rst | 7 +
gcc/jit/docs/topics/expressions.rst | 24 +++
gcc/jit/jit-common.h | 1 +
gcc/jit/jit-playback.c | 23 ++-
gcc/jit/jit-playback.h | 9 +-
gcc/jit/jit-recording.c | 60 ++++--
gcc/jit/jit-recording.h | 46 +++--
gcc/jit/libgccjit.c | 20 ++
gcc/jit/libgccjit.h | 13 ++
gcc/jit/libgccjit.map | 5 +
gcc/print-tree.c | 2 +-
gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c | 22 +++
gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c | 58 ++++++
.../gcc.dg/plugin/must_tail_call_plugin.c | 76 ++++++++
gcc/testsuite/gcc.dg/plugin/plugin.exp | 3 +
gcc/testsuite/jit.dg/all-non-failing-tests.h | 10 +
.../jit.dg/test-error-impossible-must-tail-call.c | 93 +++++++++
.../jit.dg/test-factorial-must-tail-call.c | 109 +++++++++++
gcc/tree-core.h | 3 +
gcc/tree.h | 5 +
25 files changed, 744 insertions(+), 80 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c
create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c
create mode 100644 gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c
create mode 100644 gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c
create mode 100644 gcc/testsuite/jit.dg/test-factorial-must-tail-call.c
--
1.8.5.3
^ permalink raw reply [flat|nested] 22+ messages in thread* [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL 2016-01-01 0:00 [PATCH 0/3] Support for mandatory tail calls David Malcolm @ 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` Jeff Law ` (2 more replies) 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p David Malcolm ` (2 subsequent siblings) 3 siblings, 3 replies; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: gcc-patches, jit; +Cc: David Malcolm This patch implements support for marking CALL_EXPRs as being mandatory for tail-call-optimization. expand_call tries harder to perform the optimization on such CALL_EXPRs, and issues an error if it fails. Currently this flag isn't accessible from any frontend, so the patch uses a plugin for testing the functionality. Successfully bootstrapped®rtested on x86_64-pc-linux-gnu; adds 8 PASS results to gcc.sum. OK for trunk? gcc/ChangeLog: * calls.c (maybe_complain_about_tail_call): New function. (initialize_argument_information): Call maybe_complain_about_tail_call when clearing *may_tailcall. (can_implement_as_sibling_call_p): Call maybe_complain_about_tail_call when returning false. (expand_call): Read CALL_EXPR_MUST_TAIL_CALL and, if set, ensure try_tail_call is set. Call maybe_complain_about_tail_call if tail-call optimization fails. * cfgexpand.c (expand_call_stmt): Initialize CALL_EXPR_MUST_TAIL_CALL from gimple_call_must_tail_p. * gimple-pretty-print.c (dump_gimple_call): Dump gimple_call_must_tail_p. * gimple.c (gimple_build_call_from_tree): Call gimple_call_set_must_tail with the value of CALL_EXPR_MUST_TAIL_CALL. * gimple.h (enum gf_mask): Add GF_CALL_MUST_TAIL_CALL. (gimple_call_set_must_tail): New function. (gimple_call_must_tail_p): New function. * print-tree.c (print_node): Update printing of TREE_STATIC to reflect its use for CALL_EXPR_MUST_TAIL_CALL. * tree-core.h (struct tree_base): Add MUST_TAIL_CALL to the trailing comment listing applicable flags. * tree.h (CALL_EXPR_MUST_TAIL_CALL): New macro. gcc/testsuite/ChangeLog: * gcc.dg/plugin/must-tail-call-1.c: New test case. * gcc.dg/plugin/must-tail-call-2.c: New test case. * gcc.dg/plugin/must_tail_call_plugin.c: New file. * gcc.dg/plugin/plugin.exp (plugin_test_list): Add the above. --- gcc/calls.c | 123 ++++++++++++++++++--- gcc/cfgexpand.c | 1 + gcc/gimple-pretty-print.c | 2 + gcc/gimple.c | 1 + gcc/gimple.h | 20 ++++ gcc/print-tree.c | 2 +- gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c | 22 ++++ gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c | 58 ++++++++++ .../gcc.dg/plugin/must_tail_call_plugin.c | 76 +++++++++++++ gcc/testsuite/gcc.dg/plugin/plugin.exp | 3 + gcc/tree-core.h | 3 + gcc/tree.h | 5 + 12 files changed, 299 insertions(+), 17 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c create mode 100644 gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c create mode 100644 gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c diff --git a/gcc/calls.c b/gcc/calls.c index ac8092c..1b12eca 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -1102,6 +1102,19 @@ store_unaligned_arguments_into_pseudos (struct arg_data *args, int num_actuals) } } +/* Issue an error if CALL_EXPR was flagged as requiring + tall-call optimization. */ + +static void +maybe_complain_about_tail_call (tree call_expr, const char *reason) +{ + gcc_assert (TREE_CODE (call_expr) == CALL_EXPR); + if (!CALL_EXPR_MUST_TAIL_CALL (call_expr)) + return; + + error_at (EXPR_LOCATION (call_expr), "cannot tail-call: %s", reason); +} + /* Fill in ARGS_SIZE and ARGS array based on the parameters found in CALL_EXPR EXP. @@ -1343,7 +1356,13 @@ initialize_argument_information (int num_actuals ATTRIBUTE_UNUSED, /* We can't use sibcalls if a callee-copied argument is stored in the current function's frame. */ if (!call_from_thunk_p && DECL_P (base) && !TREE_STATIC (base)) - *may_tailcall = false; + { + *may_tailcall = false; + maybe_complain_about_tail_call (exp, + "a callee-copied argument is" + " stored in the current " + " function's frame"); + } args[i].tree_value = build_fold_addr_expr_loc (loc, args[i].tree_value); @@ -1406,6 +1425,9 @@ initialize_argument_information (int num_actuals ATTRIBUTE_UNUSED, = build_fold_addr_expr_loc (loc, make_tree (type, copy)); type = TREE_TYPE (args[i].tree_value); *may_tailcall = false; + maybe_complain_about_tail_call (exp, + "argument must be passed" + " by copying"); } } @@ -2358,48 +2380,87 @@ can_implement_as_sibling_call_p (tree exp, const args_size &args_size) { if (!targetm.have_sibcall_epilogue ()) - return false; + { + maybe_complain_about_tail_call + (exp, + "machine description does not have" + " a sibcall_epilogue instruction pattern"); + return false; + } /* Doing sibling call optimization needs some work, since structure_value_addr can be allocated on the stack. It does not seem worth the effort since few optimizable sibling calls will return a structure. */ if (structure_value_addr != NULL_RTX) - return false; + { + maybe_complain_about_tail_call (exp, "callee returns a structure"); + return false; + } #ifdef REG_PARM_STACK_SPACE /* If outgoing reg parm stack space changes, we can not do sibcall. */ if (OUTGOING_REG_PARM_STACK_SPACE (funtype) != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)) || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl))) - return false; + { + maybe_complain_about_tail_call (exp, + "inconsistent size of stack space" + " allocated for arguments which are" + " passed in registers"); + return false; + } #endif /* Check whether the target is able to optimize the call into a sibcall. */ if (!targetm.function_ok_for_sibcall (fndecl, exp)) - return false; + { + maybe_complain_about_tail_call (exp, + "target is not able to optimize the" + " call into a sibling call"); + return false; + } /* Functions that do not return exactly once may not be sibcall optimized. */ - if (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) - return false; + if (flags & ECF_RETURNS_TWICE) + { + maybe_complain_about_tail_call (exp, "callee returns twice"); + return false; + } + if (flags & ECF_NORETURN) + { + maybe_complain_about_tail_call (exp, "callee does not return"); + return false; + } if (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))) - return false; + { + maybe_complain_about_tail_call (exp, "volatile function type"); + return false; + } /* If the called function is nested in the current one, it might access some of the caller's arguments, but could clobber them beforehand if the argument areas are shared. */ if (fndecl && decl_function_context (fndecl) == current_function_decl) - return false; + { + maybe_complain_about_tail_call (exp, "nested function"); + return false; + } /* If this function requires more stack slots than the current function, we cannot change it into a sibling call. crtl->args.pretend_args_size is not part of the stack allocated by our caller. */ if (args_size.constant > (crtl->args.size - crtl->args.pretend_args_size)) - return false; + { + maybe_complain_about_tail_call (exp, + "callee required more stack slots" + " than the caller"); + return false; + } /* If the callee pops its own arguments, then it must pop exactly the same number of arguments as the current function. */ @@ -2407,10 +2468,19 @@ can_implement_as_sibling_call_p (tree exp, != targetm.calls.return_pops_args (current_function_decl, TREE_TYPE (current_function_decl), crtl->args.size)) - return false; + { + maybe_complain_about_tail_call (exp, + "inconsistent number of" + " popped arguments"); + return false; + } if (!lang_hooks.decls.ok_for_sibcall (fndecl)) - return false; + { + maybe_complain_about_tail_call (exp, "frontend does not support" + " sibling call"); + return false; + } /* All checks passed. */ return true; @@ -2444,6 +2514,7 @@ expand_call (tree exp, rtx target, int ignore) /* The type of the function being called. */ tree fntype; bool try_tail_call = CALL_EXPR_TAILCALL (exp); + bool must_tail_call = CALL_EXPR_MUST_TAIL_CALL (exp); int pass; /* Register in which non-BLKmode value will be returned, @@ -2811,10 +2882,18 @@ expand_call (tree exp, rtx target, int ignore) || dbg_cnt (tail_call) == false) try_tail_call = 0; + /* If the user has marked the function as requiring tail-call + optimization, attempt it. */ + if (must_tail_call) + try_tail_call = 1; + /* Rest of purposes for tail call optimizations to fail. */ if (try_tail_call) - try_tail_call = can_implement_as_sibling_call_p (exp, structure_value_addr, funtype, - reg_parm_stack_space, fndecl, + try_tail_call = can_implement_as_sibling_call_p (exp, + structure_value_addr, + funtype, + reg_parm_stack_space, + fndecl, flags, addr, args_size); /* Check if caller and callee disagree in promotion of function @@ -2845,7 +2924,13 @@ expand_call (tree exp, rtx target, int ignore) && (caller_unsignedp != callee_unsignedp || GET_MODE_BITSIZE (caller_mode) < GET_MODE_BITSIZE (callee_mode))))) - try_tail_call = 0; + { + try_tail_call = 0; + maybe_complain_about_tail_call (exp, + "caller and callee disagree in" + " promotion of function" + " return value"); + } } /* Ensure current function's preferred stack boundary is at least @@ -3743,7 +3828,13 @@ expand_call (tree exp, rtx target, int ignore) crtl->tail_call_emit = true; } else - emit_insn (normal_call_insns); + { + emit_insn (normal_call_insns); + if (try_tail_call) + /* Ideally we'd emit a message for all of the ways that it could + have failed. */ + maybe_complain_about_tail_call (exp, "tail call production failed"); + } currently_expanding_call--; diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c index 77a1964..2a27691 100644 --- a/gcc/cfgexpand.c +++ b/gcc/cfgexpand.c @@ -2626,6 +2626,7 @@ expand_call_stmt (gcall *stmt) TREE_NOTHROW (exp) = 1; CALL_EXPR_TAILCALL (exp) = gimple_call_tail_p (stmt); + CALL_EXPR_MUST_TAIL_CALL (exp) = gimple_call_must_tail_p (stmt); CALL_EXPR_RETURN_SLOT_OPT (exp) = gimple_call_return_slot_opt_p (stmt); if (decl && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c index 4b0dc7c..1806a8c 100644 --- a/gcc/gimple-pretty-print.c +++ b/gcc/gimple-pretty-print.c @@ -742,6 +742,8 @@ dump_gimple_call (pretty_printer *buffer, gcall *gs, int spc, int flags) pp_string (buffer, " [return slot optimization]"); if (gimple_call_tail_p (gs)) pp_string (buffer, " [tail call]"); + if (gimple_call_must_tail_p (gs)) + pp_string (buffer, " [must tail call]"); if (fn == NULL) return; diff --git a/gcc/gimple.c b/gcc/gimple.c index 1a22e82..92f873b 100644 --- a/gcc/gimple.c +++ b/gcc/gimple.c @@ -359,6 +359,7 @@ gimple_build_call_from_tree (tree t) /* Carry all the CALL_EXPR flags to the new GIMPLE_CALL. */ gimple_call_set_chain (call, CALL_EXPR_STATIC_CHAIN (t)); gimple_call_set_tail (call, CALL_EXPR_TAILCALL (t)); + gimple_call_set_must_tail (call, CALL_EXPR_MUST_TAIL_CALL (t)); gimple_call_set_return_slot_opt (call, CALL_EXPR_RETURN_SLOT_OPT (t)); if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL diff --git a/gcc/gimple.h b/gcc/gimple.h index 6d15dab..063e29d 100644 --- a/gcc/gimple.h +++ b/gcc/gimple.h @@ -145,6 +145,7 @@ enum gf_mask { GF_CALL_INTERNAL = 1 << 6, GF_CALL_CTRL_ALTERING = 1 << 7, GF_CALL_WITH_BOUNDS = 1 << 8, + GF_CALL_MUST_TAIL_CALL = 1 << 9, GF_OMP_PARALLEL_COMBINED = 1 << 0, GF_OMP_PARALLEL_GRID_PHONY = 1 << 1, GF_OMP_TASK_TASKLOOP = 1 << 0, @@ -3209,6 +3210,25 @@ gimple_call_tail_p (gcall *s) return (s->subcode & GF_CALL_TAILCALL) != 0; } +/* Mark (or clear) call statement S as requiring tail call optimization. */ + +static inline void +gimple_call_set_must_tail (gcall *s, bool must_tail_p) +{ + if (must_tail_p) + s->subcode |= GF_CALL_MUST_TAIL_CALL; + else + s->subcode &= ~GF_CALL_MUST_TAIL_CALL; +} + +/* Return true if call statement has been marked as requiring + tail call optimization. */ + +static inline bool +gimple_call_must_tail_p (const gcall *s) +{ + return (s->subcode & GF_CALL_MUST_TAIL_CALL) != 0; +} /* If RETURN_SLOT_OPT_P is true mark GIMPLE_CALL S as valid for return slot optimization. This transformation uses the target of the call diff --git a/gcc/print-tree.c b/gcc/print-tree.c index aa6593f..58b6118 100644 --- a/gcc/print-tree.c +++ b/gcc/print-tree.c @@ -324,7 +324,7 @@ print_node (FILE *file, const char *prefix, tree node, int indent) if (TREE_PROTECTED (node)) fputs (" protected", file); if (TREE_STATIC (node)) - fputs (" static", file); + fputs (code == CALL_EXPR ? " must-tail-call" : " static", file); if (TREE_DEPRECATED (node)) fputs (" deprecated", file); if (TREE_VISITED (node)) diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c new file mode 100644 index 0000000..6d74955 --- /dev/null +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c @@ -0,0 +1,22 @@ +extern void abort (void); + +int __attribute__((noinline,noclone)) +callee (int i) +{ + return i * i; +} + +int __attribute__((noinline,noclone)) +caller (int i) +{ + return callee (i + 1); +} + +int +main (int argc, const char **argv) +{ + int result = caller (5); + if (result != 36) + abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c new file mode 100644 index 0000000..c5504f8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c @@ -0,0 +1,58 @@ +/* Allow nested functions. */ +/* { dg-options "-Wno-pedantic" } */ + +struct box { char field[64]; int i; }; + +struct box __attribute__((noinline,noclone)) +returns_struct (int i) +{ + struct box b; + b.i = i * i; + return b; +} + +int __attribute__((noinline,noclone)) +test_1 (int i) +{ + return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: callee returns a structure" } */ +} + +int __attribute__((noinline,noclone)) +test_2_callee (int i, struct box b) +{ + if (b.field[0]) + return 5; + return i * i; +} + +int __attribute__((noinline,noclone)) +test_2_caller (int i) +{ + struct box b; + return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */ +} + +extern void setjmp (void); +void +test_3 (void) +{ + setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */ +} + +void +test_4 (void) +{ + void nested (void) + { + } + nested (); /* { dg-error "cannot tail-call: nested function" } */ +} + +typedef void (fn_ptr_t) (void); +volatile fn_ptr_t fn_ptr; + +void +test_5 (void) +{ + fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */ +} diff --git a/gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c b/gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c new file mode 100644 index 0000000..5294f28 --- /dev/null +++ b/gcc/testsuite/gcc.dg/plugin/must_tail_call_plugin.c @@ -0,0 +1,76 @@ +/* { dg-options "-O" } */ + +/* Mark all CALL_EXPRs not within "main" as requiring tail-call. */ + +#include "gcc-plugin.h" +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "stringpool.h" +#include "toplev.h" +#include "basic-block.h" +#include "hash-table.h" +#include "vec.h" +#include "ggc.h" +#include "basic-block.h" +#include "tree-ssa-alias.h" +#include "internal-fn.h" +#include "gimple-fold.h" +#include "tree-eh.h" +#include "gimple-expr.h" +#include "is-a.h" +#include "tree.h" +#include "tree-pass.h" +#include "intl.h" +#include "plugin-version.h" + +int plugin_is_GPL_compatible; + +tree +cb_walk_tree_fn (tree * tp, int * walk_subtrees, + void * data ATTRIBUTE_UNUSED) +{ + if (TREE_CODE (*tp) != CALL_EXPR) + return NULL_TREE; + + tree call_expr = *tp; + + /* Forcibly mark the CALL_EXPR as requiring tail-call optimization. */ + CALL_EXPR_MUST_TAIL_CALL (call_expr) = 1; + + return NULL_TREE; +} + +static void +callback (void *gcc_data, void *user_data) +{ + tree fndecl = (tree)gcc_data; + gcc_assert (TREE_CODE (fndecl) == FUNCTION_DECL); + + /* Don't mark calls inside "main". */ + tree decl_name = DECL_NAME (fndecl); + if (decl_name) + if (0 == strcmp (IDENTIFIER_POINTER (decl_name), "main")) + return; + + walk_tree (&DECL_SAVED_TREE (fndecl), cb_walk_tree_fn, NULL, NULL); +} + +int +plugin_init (struct plugin_name_args *plugin_info, + struct plugin_gcc_version *version) +{ + const char *plugin_name = plugin_info->base_name; + + if (!plugin_default_version_check (version, &gcc_version)) + return 1; + + register_callback (plugin_name, + PLUGIN_PRE_GENERICIZE, + callback, + NULL); + + return 0; +} diff --git a/gcc/testsuite/gcc.dg/plugin/plugin.exp b/gcc/testsuite/gcc.dg/plugin/plugin.exp index fd1e98e..62f6797 100644 --- a/gcc/testsuite/gcc.dg/plugin/plugin.exp +++ b/gcc/testsuite/gcc.dg/plugin/plugin.exp @@ -74,6 +74,9 @@ set plugin_test_list [list \ { location_overflow_plugin.c \ location-overflow-test-1.c \ location-overflow-test-2.c } \ + { must_tail_call_plugin.c \ + must-tail-call-1.c \ + must-tail-call-2.c } \ ] foreach plugin_test $plugin_test_list { diff --git a/gcc/tree-core.h b/gcc/tree-core.h index ea832fa..078e006 100644 --- a/gcc/tree-core.h +++ b/gcc/tree-core.h @@ -998,6 +998,9 @@ struct GTY(()) tree_base { SSA_NAME_ANTI_RANGE_P in SSA_NAME + MUST_TAIL_CALL in + CALL_EXPR + public_flag: TREE_OVERFLOW in diff --git a/gcc/tree.h b/gcc/tree.h index 37324bf..2510d16 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -661,6 +661,11 @@ extern void omp_clause_range_check_failed (const_tree, const char *, int, #define CALL_EXPR_TAILCALL(NODE) \ (CALL_EXPR_CHECK (NODE)->base.addressable_flag) +/* Set on a CALL_EXPR if the call has been marked as requiring tail call + optimization for correctness. */ +#define CALL_EXPR_MUST_TAIL_CALL(NODE) \ + (CALL_EXPR_CHECK (NODE)->base.static_flag) + /* Used as a temporary field on a CASE_LABEL_EXPR to indicate that the CASE_LOW operand has been processed. */ #define CASE_LOW_SEEN(NODE) \ -- 1.8.5.3 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL 2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm @ 2016-01-01 0:00 ` Jeff Law 2016-01-01 0:00 ` Andreas Schwab 2016-01-01 0:00 ` Andreas Schwab 2 siblings, 0 replies; 22+ messages in thread From: Jeff Law @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm, gcc-patches, jit On 05/17/2016 04:01 PM, David Malcolm wrote: > This patch implements support for marking CALL_EXPRs > as being mandatory for tail-call-optimization. expand_call > tries harder to perform the optimization on such CALL_EXPRs, > and issues an error if it fails. > > Currently this flag isn't accessible from any frontend, > so the patch uses a plugin for testing the functionality. > > Successfully bootstrapped®rtested on x86_64-pc-linux-gnu; > adds 8 PASS results to gcc.sum. > > OK for trunk? > > gcc/ChangeLog: > * calls.c (maybe_complain_about_tail_call): New function. > (initialize_argument_information): Call > maybe_complain_about_tail_call when clearing *may_tailcall. > (can_implement_as_sibling_call_p): Call > maybe_complain_about_tail_call when returning false. > (expand_call): Read CALL_EXPR_MUST_TAIL_CALL and, if set, > ensure try_tail_call is set. Call maybe_complain_about_tail_call > if tail-call optimization fails. > * cfgexpand.c (expand_call_stmt): Initialize > CALL_EXPR_MUST_TAIL_CALL from gimple_call_must_tail_p. > * gimple-pretty-print.c (dump_gimple_call): Dump > gimple_call_must_tail_p. > * gimple.c (gimple_build_call_from_tree): Call > gimple_call_set_must_tail with the value of > CALL_EXPR_MUST_TAIL_CALL. > * gimple.h (enum gf_mask): Add GF_CALL_MUST_TAIL_CALL. > (gimple_call_set_must_tail): New function. > (gimple_call_must_tail_p): New function. > * print-tree.c (print_node): Update printing of TREE_STATIC > to reflect its use for CALL_EXPR_MUST_TAIL_CALL. > * tree-core.h (struct tree_base): Add MUST_TAIL_CALL to the > trailing comment listing applicable flags. > * tree.h (CALL_EXPR_MUST_TAIL_CALL): New macro. It's actually simpler than it looks -- most of the changes are just getting better diagnostics when tail call fails, which I wholeheartedly support. OK for the trunk. Thanks, Jeff ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL 2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm 2016-01-01 0:00 ` Jeff Law @ 2016-01-01 0:00 ` Andreas Schwab 2016-01-01 0:00 ` Andreas Schwab 2 siblings, 0 replies; 22+ messages in thread From: Andreas Schwab @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm; +Cc: gcc-patches, jit David Malcolm <dmalcolm@redhat.com> writes: > diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c > new file mode 100644 > index 0000000..c5504f8 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c > @@ -0,0 +1,58 @@ > +/* Allow nested functions. */ > +/* { dg-options "-Wno-pedantic" } */ > + > +struct box { char field[64]; int i; }; > + > +struct box __attribute__((noinline,noclone)) > +returns_struct (int i) > +{ > + struct box b; > + b.i = i * i; > + return b; > +} > + > +int __attribute__((noinline,noclone)) > +test_1 (int i) > +{ > + return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: callee returns a structure" } */ > +} > + > +int __attribute__((noinline,noclone)) > +test_2_callee (int i, struct box b) > +{ > + if (b.field[0]) > + return 5; > + return i * i; > +} > + > +int __attribute__((noinline,noclone)) > +test_2_caller (int i) > +{ > + struct box b; > + return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */ > +} > + > +extern void setjmp (void); > +void > +test_3 (void) > +{ > + setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */ > +} > + > +void > +test_4 (void) > +{ > + void nested (void) > + { > + } > + nested (); /* { dg-error "cannot tail-call: nested function" } */ > +} > + > +typedef void (fn_ptr_t) (void); > +volatile fn_ptr_t fn_ptr; > + > +void > +test_5 (void) > +{ > + fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */ > +} On aarch64: FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for errors, line 32) FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors) Excess errors: gcc.dg/plugin/must-tail-call-2.c:32:10: error: cannot tail-call: argument must be passed by copying Andreas. -- Andreas Schwab, schwab@linux-m68k.org GPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5 "And now for something completely different." ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL 2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm 2016-01-01 0:00 ` Jeff Law 2016-01-01 0:00 ` Andreas Schwab @ 2016-01-01 0:00 ` Andreas Schwab 2016-01-01 0:00 ` [PATCH] Fixes to must-tail-call tests David Malcolm 2 siblings, 1 reply; 22+ messages in thread From: Andreas Schwab @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm; +Cc: gcc-patches, jit David Malcolm <dmalcolm@redhat.com> writes: > diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c > new file mode 100644 > index 0000000..c5504f8 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c > @@ -0,0 +1,58 @@ > +/* Allow nested functions. */ > +/* { dg-options "-Wno-pedantic" } */ > + > +struct box { char field[64]; int i; }; > + > +struct box __attribute__((noinline,noclone)) > +returns_struct (int i) > +{ > + struct box b; > + b.i = i * i; > + return b; > +} > + > +int __attribute__((noinline,noclone)) > +test_1 (int i) > +{ > + return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: callee returns a structure" } */ > +} > + > +int __attribute__((noinline,noclone)) > +test_2_callee (int i, struct box b) > +{ > + if (b.field[0]) > + return 5; > + return i * i; > +} > + > +int __attribute__((noinline,noclone)) > +test_2_caller (int i) > +{ > + struct box b; > + return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */ > +} > + > +extern void setjmp (void); > +void > +test_3 (void) > +{ > + setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */ > +} > + > +void > +test_4 (void) > +{ > + void nested (void) > + { > + } > + nested (); /* { dg-error "cannot tail-call: nested function" } */ > +} > + > +typedef void (fn_ptr_t) (void); > +volatile fn_ptr_t fn_ptr; > + > +void > +test_5 (void) > +{ > + fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */ > +} On ia64: FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for errors, line 39) FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for errors, line 57) FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors) Excess errors: gcc.dg/plugin/must-tail-call-2.c:39:3: error: cannot tail-call: target is not able to optimize the call into a sibling call gcc.dg/plugin/must-tail-call-2.c:57:3: error: cannot tail-call: target is not able to optimize the call into a sibling call On m68k: FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for errors, line 48) FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors) Excess errors: gcc.dg/plugin/must-tail-call-2.c:48:3: error: cannot tail-call: target is not able to optimize the call into a sibling call Andreas. -- Andreas Schwab, schwab@linux-m68k.org GPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5 "And now for something completely different." ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH] Fixes to must-tail-call tests 2016-01-01 0:00 ` Andreas Schwab @ 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` Rainer Orth 0 siblings, 1 reply; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: gcc-patches, jit, Andreas Schwab; +Cc: David Malcolm The following fixes the known failures of the must-tail-call tests. Tested with --target= * aarch64-unknown-linux-gnu * ia64-unknown-linux-gnu * m68k-unknown-linux-gnu * x86_64-pc-linux-gnu OK for trunk? gcc/testsuite/ChangeLog: * gcc.dg/plugin/must-tail-call-2.c (test_2_caller): Generalize expected error message to allow "argument must by passed by copying". (test_3): Generalize expected error message to allow for failure of targetm.function_ok_for_sibcall. (test_4): Likewise. (test_5): Likewise. --- gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c index c5504f8..ca81b35 100644 --- a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c @@ -29,14 +29,14 @@ int __attribute__((noinline,noclone)) test_2_caller (int i) { struct box b; - return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */ + return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller|argument must be passed by copying" } */ } extern void setjmp (void); void test_3 (void) { - setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */ + setjmp (); /* { dg-error "cannot tail-call: callee returns twice|target is not able to optimize the call into a sibling call" } */ } void @@ -45,7 +45,7 @@ test_4 (void) void nested (void) { } - nested (); /* { dg-error "cannot tail-call: nested function" } */ + nested (); /* { dg-error "cannot tail-call: nested function|target is not able to optimize the call into a sibling call" } */ } typedef void (fn_ptr_t) (void); @@ -54,5 +54,5 @@ volatile fn_ptr_t fn_ptr; void test_5 (void) { - fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */ + fn_ptr (); /* { dg-error "cannot tail-call: callee does not return|target is not able to optimize the call into a sibling call" } */ } -- 1.8.5.3 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH] Fixes to must-tail-call tests 2016-01-01 0:00 ` [PATCH] Fixes to must-tail-call tests David Malcolm @ 2016-01-01 0:00 ` Rainer Orth 2016-01-01 0:00 ` Thomas Preudhomme 0 siblings, 1 reply; 22+ messages in thread From: Rainer Orth @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm; +Cc: gcc-patches, jit, Andreas Schwab David Malcolm <dmalcolm@redhat.com> writes: > The following fixes the known failures of the must-tail-call tests. > > Tested with --target= > * aarch64-unknown-linux-gnu > * ia64-unknown-linux-gnu > * m68k-unknown-linux-gnu > * x86_64-pc-linux-gnu Even with this patch, there are still failures on sparc-sun-solaris2.12: FAIL: gcc.dg/plugin/must-tail-call-1.c -fplugin=./must_tail_call_plugin.so (test for excess errors) Excess errors: /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c:12:10: error: cannot tail-call: target is not able to optimize the call into a sibling call FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so (test for excess errors) Excess errors: /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c:32:10: error: cannot tail-call: target is not able to optimize the call into a sibling call Rainer -- ----------------------------------------------------------------------------- Rainer Orth, Center for Biotechnology, Bielefeld University ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH] Fixes to must-tail-call tests 2016-01-01 0:00 ` Rainer Orth @ 2016-01-01 0:00 ` Thomas Preudhomme 2016-01-01 0:00 ` David Malcolm 0 siblings, 1 reply; 22+ messages in thread From: Thomas Preudhomme @ 2016-01-01 0:00 UTC (permalink / raw) To: gcc-patches; +Cc: Rainer Orth, David Malcolm, jit, Andreas Schwab Hi Rainer, On Wednesday 25 May 2016 11:31:12 Rainer Orth wrote: > David Malcolm <dmalcolm@redhat.com> writes: > > The following fixes the known failures of the must-tail-call tests. > > > > Tested with --target= > > * aarch64-unknown-linux-gnu > > * ia64-unknown-linux-gnu > > * m68k-unknown-linux-gnu > > * x86_64-pc-linux-gnu > > Even with this patch, there are still failures on sparc-sun-solaris2.12: > > FAIL: gcc.dg/plugin/must-tail-call-1.c -fplugin=./must_tail_call_plugin.so > (test for excess errors) > > Excess errors: > /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-1.c:1 > 2:10: error: cannot tail-call: target is not able to optimize the call into > a sibling call > > FAIL: gcc.dg/plugin/must-tail-call-2.c -fplugin=./must_tail_call_plugin.so > (test for excess errors) > > Excess errors: > /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c:3 > 2:10: error: cannot tail-call: target is not able to optimize the call into > a sibling call Now that the logic is in place, you probably want to add sparc-sun-solaris in plugin.exp to the the list of architecture where tail call plugin tests should be skipped, alongside Thumb-1 ARM targets. Best regards, Thomas ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH] Fixes to must-tail-call tests 2016-01-01 0:00 ` Thomas Preudhomme @ 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` Jeff Law 0 siblings, 1 reply; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: Thomas Preudhomme, gcc-patches; +Cc: Rainer Orth, jit, Andreas Schwab [-- Attachment #1: Type: text/plain, Size: 2757 bytes --] On Fri, 2016-05-27 at 13:29 +0100, Thomas Preudhomme wrote: > Hi Rainer, > > On Wednesday 25 May 2016 11:31:12 Rainer Orth wrote: > > David Malcolm <dmalcolm@redhat.com> writes: > > > The following fixes the known failures of the must-tail-call > > > tests. > > > > > > Tested with --target= > > > * aarch64-unknown-linux-gnu > > > * ia64-unknown-linux-gnu > > > * m68k-unknown-linux-gnu > > > * x86_64-pc-linux-gnu > > > > Even with this patch, there are still failures on sparc-sun > > -solaris2.12: > > > > FAIL: gcc.dg/plugin/must-tail-call-1.c > > -fplugin=./must_tail_call_plugin.so > > (test for excess errors) > > > > Excess errors: > > /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail > > -call-1.c:1 > > 2:10: error: cannot tail-call: target is not able to optimize the > > call into > > a sibling call > > > > FAIL: gcc.dg/plugin/must-tail-call-2.c > > -fplugin=./must_tail_call_plugin.so > > (test for excess errors) > > > > Excess errors: > > /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail > > -call-2.c:3 > > 2:10: error: cannot tail-call: target is not able to optimize the > > call into > > a sibling call My aim with these tests was to try to cover the various ways in which mandatory tail-call optimization can fail. However, this is very target-dependent, and, as written, the test over -specifies the output. Sorry about this. I've run the test on all of the configurations in contrib/config -list.mk (using the patch kit in https://gcc.gnu.org/ml/gcc-patches/2016-05/msg02100.html ) Collated output can be seen here: https://dmalcolm.fedorapeople.org/gcc/2016-05-27/must-tail-call-logs.txt showing all the different error messages across every configuration. It's not clear to me what the best way forward here is. We could simply check for error: cannot tail-call: and leave the precise messages we're checking for unspecified. If we care about checking for the precise messages, one of more duplicate copy(s) of the test could be provided, filtering by target to specify precise targets, giving more precise output, where this is known. I'm attaching a patch (sans ChangeLog) which strips the precise messages in the manner described above. Retesting on all targets with this patch, the only remaining failures are of the form: must-tail-call-1.c:12:10: error: cannot tail-call: machine description does not have a sibcall_epilogue instruction pattern on targets lacking the pattern. Thoughts? Sorry again about the breakage Dave > Now that the logic is in place, you probably want to add sparc-sun > -solaris in > plugin.exp to the the list of architecture where tail call plugin > tests should > be skipped, alongside Thumb-1 ARM targets. > > Best regards, > [-- Attachment #2: generic-error-message.patch --] [-- Type: text/x-patch, Size: 1489 bytes --] diff --git a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c index c5504f8..c6dfecd 100644 --- a/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c +++ b/gcc/testsuite/gcc.dg/plugin/must-tail-call-2.c @@ -14,7 +14,7 @@ returns_struct (int i) int __attribute__((noinline,noclone)) test_1 (int i) { - return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: callee returns a structure" } */ + return returns_struct (i * 5).i; /* { dg-error "cannot tail-call: " } */ } int __attribute__((noinline,noclone)) @@ -29,14 +29,14 @@ int __attribute__((noinline,noclone)) test_2_caller (int i) { struct box b; - return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: callee required more stack slots than the caller" } */ + return test_2_callee (i + 1, b); /* { dg-error "cannot tail-call: " } */ } extern void setjmp (void); void test_3 (void) { - setjmp (); /* { dg-error "cannot tail-call: callee returns twice" } */ + setjmp (); /* { dg-error "cannot tail-call: " } */ } void @@ -45,7 +45,7 @@ test_4 (void) void nested (void) { } - nested (); /* { dg-error "cannot tail-call: nested function" } */ + nested (); /* { dg-error "cannot tail-call: " } */ } typedef void (fn_ptr_t) (void); @@ -54,5 +54,5 @@ volatile fn_ptr_t fn_ptr; void test_5 (void) { - fn_ptr (); /* { dg-error "cannot tail-call: callee does not return" } */ + fn_ptr (); /* { dg-error "cannot tail-call: " } */ } ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH] Fixes to must-tail-call tests 2016-01-01 0:00 ` David Malcolm @ 2016-01-01 0:00 ` Jeff Law 0 siblings, 0 replies; 22+ messages in thread From: Jeff Law @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm, Thomas Preudhomme, gcc-patches Cc: Rainer Orth, jit, Andreas Schwab On 05/27/2016 11:44 AM, David Malcolm wrote: > On Fri, 2016-05-27 at 13:29 +0100, Thomas Preudhomme wrote: >> Hi Rainer, >> >> On Wednesday 25 May 2016 11:31:12 Rainer Orth wrote: >>> David Malcolm <dmalcolm@redhat.com> writes: >>>> The following fixes the known failures of the must-tail-call >>>> tests. >>>> >>>> Tested with --target= >>>> * aarch64-unknown-linux-gnu >>>> * ia64-unknown-linux-gnu >>>> * m68k-unknown-linux-gnu >>>> * x86_64-pc-linux-gnu >>> >>> Even with this patch, there are still failures on sparc-sun >>> -solaris2.12: >>> >>> FAIL: gcc.dg/plugin/must-tail-call-1.c >>> -fplugin=./must_tail_call_plugin.so >>> (test for excess errors) >>> >>> Excess errors: >>> /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail >>> -call-1.c:1 >>> 2:10: error: cannot tail-call: target is not able to optimize the >>> call into >>> a sibling call >>> >>> FAIL: gcc.dg/plugin/must-tail-call-2.c >>> -fplugin=./must_tail_call_plugin.so >>> (test for excess errors) >>> >>> Excess errors: >>> /vol/gcc/src/hg/trunk/local/gcc/testsuite/gcc.dg/plugin/must-tail >>> -call-2.c:3 >>> 2:10: error: cannot tail-call: target is not able to optimize the >>> call into >>> a sibling call > > > My aim with these tests was to try to cover the various ways in which > mandatory tail-call optimization can fail. > > However, this is very target-dependent, and, as written, the test over > -specifies the output. > > Sorry about this. > > I've run the test on all of the configurations in contrib/config > -list.mk (using the patch kit in > https://gcc.gnu.org/ml/gcc-patches/2016-05/msg02100.html ) > > Collated output can be seen here: > https://dmalcolm.fedorapeople.org/gcc/2016-05-27/must-tail-call-logs.txt > showing all the different error messages across every configuration. > > It's not clear to me what the best way forward here is. > We could simply check for > error: cannot tail-call: > and leave the precise messages we're checking for unspecified. > > If we care about checking for the precise messages, one of more > duplicate copy(s) of the test could be provided, filtering by target to > specify precise targets, giving more precise output, where this is > known. > > I'm attaching a patch (sans ChangeLog) which strips the precise > messages in the manner described above. Retesting on all targets with > this patch, the only remaining failures are of the form: > must-tail-call-1.c:12:10: error: cannot tail-call: machine > description does not have a sibcall_epilogue instruction pattern > on targets lacking the pattern. > > Thoughts? I probably should have caught this -- there's all kinds of oddball reasons why we might not be able to optimize a tail call, some of which are target dependent. I think trying to give highly precise messages is doomed to long term maintenance headaches because they're going to be target dependent. So I'd go with just stripping the precise messages like you've done. jeff ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 1/3] Introduce can_implement_as_sibling_call_p 2016-01-01 0:00 [PATCH 0/3] Support for mandatory tail calls David Malcolm 2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm @ 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` Kyrill Tkachov 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p Jeff Law 2016-01-01 0:00 ` [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call David Malcolm 2016-01-01 0:00 ` [PATCH 0/3] Support for mandatory tail calls Jeff Law 3 siblings, 2 replies; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: gcc-patches, jit; +Cc: David Malcolm This patch moves part of the logic for determining if tail call optimizations are possible to a new helper function. There are no functional changes. expand_call is 1300 lines long, so there's arguably a case for doing this on its own, but this change also enables the followup patch. The patch changes the logic from a big "if" with joined || clauses: if (first_problem () ||second_problem () /* ...etc... */ ||final_problem ()) try_tail_call = 0; to a series of separate tests: if (first_problem ()) return false; if (second_problem ()) return false; /* ...etc... */ if (final_problem ()) return false; I think the latter form has several advantages over the former: - IMHO it's easier to read - it makes it easy to put breakpoints on individual causes of failure - it makes it easy to put specific error messages on individual causes of failure (as done in the followup patch). Successfully bootstrapped®rtested on x86_64-pc-linux-gnu. OK for trunk? gcc/ChangeLog: * calls.c (expand_call): Move "Rest of purposes for tail call optimizations to fail" to... (can_implement_as_sibling_call_p): ...this new function, and split into multiple "if" statements. --- gcc/calls.c | 114 ++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 76 insertions(+), 38 deletions(-) diff --git a/gcc/calls.c b/gcc/calls.c index 6cc1fc7..ac8092c 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -2344,6 +2344,78 @@ avoid_likely_spilled_reg (rtx x) return x; } +/* Helper function for expand_call. + Return false is EXP is not implementable as a sibling call. */ + +static bool +can_implement_as_sibling_call_p (tree exp, + rtx structure_value_addr, + tree funtype, + int reg_parm_stack_space, + tree fndecl, + int flags, + tree addr, + const args_size &args_size) +{ + if (!targetm.have_sibcall_epilogue ()) + return false; + + /* Doing sibling call optimization needs some work, since + structure_value_addr can be allocated on the stack. + It does not seem worth the effort since few optimizable + sibling calls will return a structure. */ + if (structure_value_addr != NULL_RTX) + return false; + +#ifdef REG_PARM_STACK_SPACE + /* If outgoing reg parm stack space changes, we can not do sibcall. */ + if (OUTGOING_REG_PARM_STACK_SPACE (funtype) + != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)) + || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl))) + return false; +#endif + + /* Check whether the target is able to optimize the call + into a sibcall. */ + if (!targetm.function_ok_for_sibcall (fndecl, exp)) + return false; + + /* Functions that do not return exactly once may not be sibcall + optimized. */ + if (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) + return false; + + if (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))) + return false; + + /* If the called function is nested in the current one, it might access + some of the caller's arguments, but could clobber them beforehand if + the argument areas are shared. */ + if (fndecl && decl_function_context (fndecl) == current_function_decl) + return false; + + /* If this function requires more stack slots than the current + function, we cannot change it into a sibling call. + crtl->args.pretend_args_size is not part of the + stack allocated by our caller. */ + if (args_size.constant > (crtl->args.size - crtl->args.pretend_args_size)) + return false; + + /* If the callee pops its own arguments, then it must pop exactly + the same number of arguments as the current function. */ + if (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant) + != targetm.calls.return_pops_args (current_function_decl, + TREE_TYPE (current_function_decl), + crtl->args.size)) + return false; + + if (!lang_hooks.decls.ok_for_sibcall (fndecl)) + return false; + + /* All checks passed. */ + return true; +} + /* Generate all the code for a CALL_EXPR exp and return an rtx for its value. Store the value in TARGET (specified as an rtx) if convenient. @@ -2740,44 +2812,10 @@ expand_call (tree exp, rtx target, int ignore) try_tail_call = 0; /* Rest of purposes for tail call optimizations to fail. */ - if (!try_tail_call - || !targetm.have_sibcall_epilogue () - /* Doing sibling call optimization needs some work, since - structure_value_addr can be allocated on the stack. - It does not seem worth the effort since few optimizable - sibling calls will return a structure. */ - || structure_value_addr != NULL_RTX -#ifdef REG_PARM_STACK_SPACE - /* If outgoing reg parm stack space changes, we can not do sibcall. */ - || (OUTGOING_REG_PARM_STACK_SPACE (funtype) - != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl))) - || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl)) -#endif - /* Check whether the target is able to optimize the call - into a sibcall. */ - || !targetm.function_ok_for_sibcall (fndecl, exp) - /* Functions that do not return exactly once may not be sibcall - optimized. */ - || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) - || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))) - /* If the called function is nested in the current one, it might access - some of the caller's arguments, but could clobber them beforehand if - the argument areas are shared. */ - || (fndecl && decl_function_context (fndecl) == current_function_decl) - /* If this function requires more stack slots than the current - function, we cannot change it into a sibling call. - crtl->args.pretend_args_size is not part of the - stack allocated by our caller. */ - || args_size.constant > (crtl->args.size - - crtl->args.pretend_args_size) - /* If the callee pops its own arguments, then it must pop exactly - the same number of arguments as the current function. */ - || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant) - != targetm.calls.return_pops_args (current_function_decl, - TREE_TYPE (current_function_decl), - crtl->args.size)) - || !lang_hooks.decls.ok_for_sibcall (fndecl)) - try_tail_call = 0; + if (try_tail_call) + try_tail_call = can_implement_as_sibling_call_p (exp, structure_value_addr, funtype, + reg_parm_stack_space, fndecl, + flags, addr, args_size); /* Check if caller and callee disagree in promotion of function return value. */ -- 1.8.5.3 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 1/3] Introduce can_implement_as_sibling_call_p 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p David Malcolm @ 2016-01-01 0:00 ` Kyrill Tkachov 2016-01-01 0:00 ` [PATCH] calls.c: fix warning on targets without REG_PARM_STACK_SPACE David Malcolm 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p Jeff Law 1 sibling, 1 reply; 22+ messages in thread From: Kyrill Tkachov @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm, gcc-patches, jit Hi David, On 17/05/16 23:01, David Malcolm wrote: > This patch moves part of the logic for determining if tail > call optimizations are possible to a new helper function. > > There are no functional changes. > > expand_call is 1300 lines long, so there's arguably a > case for doing this on its own, but this change also > enables the followup patch. > > The patch changes the logic from a big "if" with joined > || clauses: > > if (first_problem () > ||second_problem () > /* ...etc... */ > ||final_problem ()) > try_tail_call = 0; > > to a series of separate tests: > > if (first_problem ()) > return false; > if (second_problem ()) > return false; > /* ...etc... */ > if (final_problem ()) > return false; > > I think the latter form has several advantages over the former: > - IMHO it's easier to read > - it makes it easy to put breakpoints on individual causes of failure > - it makes it easy to put specific error messages on individual causes > of failure (as done in the followup patch). > > Successfully bootstrapped®rtested on x86_64-pc-linux-gnu. > > OK for trunk? > > gcc/ChangeLog: > * calls.c (expand_call): Move "Rest of purposes for tail call > optimizations to fail" to... > (can_implement_as_sibling_call_p): ...this new function, and > split into multiple "if" statements. > --- > gcc/calls.c | 114 ++++++++++++++++++++++++++++++++++++++++-------------------- > 1 file changed, 76 insertions(+), 38 deletions(-) > > diff --git a/gcc/calls.c b/gcc/calls.c > index 6cc1fc7..ac8092c 100644 > --- a/gcc/calls.c > +++ b/gcc/calls.c > @@ -2344,6 +2344,78 @@ avoid_likely_spilled_reg (rtx x) > return x; > } > > +/* Helper function for expand_call. > + Return false is EXP is not implementable as a sibling call. */ > + > +static bool > +can_implement_as_sibling_call_p (tree exp, > + rtx structure_value_addr, > + tree funtype, > + int reg_parm_stack_space, > + tree fndecl, > + int flags, > + tree addr, > + const args_size &args_size) > +{ > + if (!targetm.have_sibcall_epilogue ()) > + return false; > + > + /* Doing sibling call optimization needs some work, since > + structure_value_addr can be allocated on the stack. > + It does not seem worth the effort since few optimizable > + sibling calls will return a structure. */ > + if (structure_value_addr != NULL_RTX) > + return false; > + > +#ifdef REG_PARM_STACK_SPACE > + /* If outgoing reg parm stack space changes, we can not do sibcall. */ > + if (OUTGOING_REG_PARM_STACK_SPACE (funtype) > + != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl)) > + || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl))) > + return false; > +#endif > + REG_PARM_STACK_SPACE is not defined on arm, which makes reg_parm_stack_space unused in this function and so breaks bootstrap on arm. Can you please add an ATTRIBUTE_UNUSED to reg_parm_stack_space? Thanks, Kyrill > + /* Check whether the target is able to optimize the call > + into a sibcall. */ > + if (!targetm.function_ok_for_sibcall (fndecl, exp)) > + return false; > + > + /* Functions that do not return exactly once may not be sibcall > + optimized. */ > + if (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) > + return false; > + > + if (TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr)))) > + return false; > + > + /* If the called function is nested in the current one, it might access > + some of the caller's arguments, but could clobber them beforehand if > + the argument areas are shared. */ > + if (fndecl && decl_function_context (fndecl) == current_function_decl) > + return false; > + > + /* If this function requires more stack slots than the current > + function, we cannot change it into a sibling call. > + crtl->args.pretend_args_size is not part of the > + stack allocated by our caller. */ > + if (args_size.constant > (crtl->args.size - crtl->args.pretend_args_size)) > + return false; > + > + /* If the callee pops its own arguments, then it must pop exactly > + the same number of arguments as the current function. */ > + if (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant) > + != targetm.calls.return_pops_args (current_function_decl, > + TREE_TYPE (current_function_decl), > + crtl->args.size)) > + return false; > + > + if (!lang_hooks.decls.ok_for_sibcall (fndecl)) > + return false; > + > + /* All checks passed. */ > + return true; > +} > + > /* Generate all the code for a CALL_EXPR exp > and return an rtx for its value. > Store the value in TARGET (specified as an rtx) if convenient. > @@ -2740,44 +2812,10 @@ expand_call (tree exp, rtx target, int ignore) > try_tail_call = 0; > > /* Rest of purposes for tail call optimizations to fail. */ > - if (!try_tail_call > - || !targetm.have_sibcall_epilogue () > - /* Doing sibling call optimization needs some work, since > - structure_value_addr can be allocated on the stack. > - It does not seem worth the effort since few optimizable > - sibling calls will return a structure. */ > - || structure_value_addr != NULL_RTX > -#ifdef REG_PARM_STACK_SPACE > - /* If outgoing reg parm stack space changes, we can not do sibcall. */ > - || (OUTGOING_REG_PARM_STACK_SPACE (funtype) > - != OUTGOING_REG_PARM_STACK_SPACE (TREE_TYPE (current_function_decl))) > - || (reg_parm_stack_space != REG_PARM_STACK_SPACE (current_function_decl)) > -#endif > - /* Check whether the target is able to optimize the call > - into a sibcall. */ > - || !targetm.function_ok_for_sibcall (fndecl, exp) > - /* Functions that do not return exactly once may not be sibcall > - optimized. */ > - || (flags & (ECF_RETURNS_TWICE | ECF_NORETURN)) > - || TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (addr))) > - /* If the called function is nested in the current one, it might access > - some of the caller's arguments, but could clobber them beforehand if > - the argument areas are shared. */ > - || (fndecl && decl_function_context (fndecl) == current_function_decl) > - /* If this function requires more stack slots than the current > - function, we cannot change it into a sibling call. > - crtl->args.pretend_args_size is not part of the > - stack allocated by our caller. */ > - || args_size.constant > (crtl->args.size > - - crtl->args.pretend_args_size) > - /* If the callee pops its own arguments, then it must pop exactly > - the same number of arguments as the current function. */ > - || (targetm.calls.return_pops_args (fndecl, funtype, args_size.constant) > - != targetm.calls.return_pops_args (current_function_decl, > - TREE_TYPE (current_function_decl), > - crtl->args.size)) > - || !lang_hooks.decls.ok_for_sibcall (fndecl)) > - try_tail_call = 0; > + if (try_tail_call) > + try_tail_call = can_implement_as_sibling_call_p (exp, structure_value_addr, funtype, > + reg_parm_stack_space, fndecl, > + flags, addr, args_size); > > /* Check if caller and callee disagree in promotion of function > return value. */ ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH] calls.c: fix warning on targets without REG_PARM_STACK_SPACE 2016-01-01 0:00 ` Kyrill Tkachov @ 2016-01-01 0:00 ` David Malcolm 0 siblings, 0 replies; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: Kyrill Tkachov, gcc-patches, jit; +Cc: David Malcolm On Fri, 2016-05-20 at 18:03 +0100, Kyrill Tkachov wrote: [...snip...] > REG_PARM_STACK_SPACE is not defined on arm, which makes > reg_parm_stack_space > unused in this function and so breaks bootstrap on arm. > Can you please add an ATTRIBUTE_UNUSED to reg_parm_stack_space? > > Thanks, > Kyrill [...snip...] Sorry about the breakage. I manually verified that the following fixes the warning with --target=arm-linux-gnueabi. Successfully bootstrapped®rtested on x86_64-pc-linux-gnu. Committed to trunk as r236527. gcc/ChangeLog: * calls.c (can_implement_as_sibling_call_p): Mark param reg_parm_stack_space with ATTRIBUTE_UNUSED. --- gcc/calls.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/calls.c b/gcc/calls.c index 1b12eca..587969f 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -2373,7 +2373,7 @@ static bool can_implement_as_sibling_call_p (tree exp, rtx structure_value_addr, tree funtype, - int reg_parm_stack_space, + int reg_parm_stack_space ATTRIBUTE_UNUSED, tree fndecl, int flags, tree addr, -- 1.8.5.3 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 1/3] Introduce can_implement_as_sibling_call_p 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p David Malcolm 2016-01-01 0:00 ` Kyrill Tkachov @ 2016-01-01 0:00 ` Jeff Law 1 sibling, 0 replies; 22+ messages in thread From: Jeff Law @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm, gcc-patches, jit On 05/17/2016 04:01 PM, David Malcolm wrote: > This patch moves part of the logic for determining if tail > call optimizations are possible to a new helper function. > > There are no functional changes. > > expand_call is 1300 lines long, so there's arguably a > case for doing this on its own, but this change also > enables the followup patch. > > The patch changes the logic from a big "if" with joined > || clauses: > > if (first_problem () > ||second_problem () > /* ...etc... */ > ||final_problem ()) > try_tail_call = 0; > > to a series of separate tests: > > if (first_problem ()) > return false; > if (second_problem ()) > return false; > /* ...etc... */ > if (final_problem ()) > return false; > > I think the latter form has several advantages over the former: > - IMHO it's easier to read > - it makes it easy to put breakpoints on individual causes of failure > - it makes it easy to put specific error messages on individual causes > of failure (as done in the followup patch). > > Successfully bootstrapped®rtested on x86_64-pc-linux-gnu. > > OK for trunk? > > gcc/ChangeLog: > * calls.c (expand_call): Move "Rest of purposes for tail call > optimizations to fail" to... > (can_implement_as_sibling_call_p): ...this new function, and > split into multiple "if" statements. This is good in and of itself as a refactoring/cleanup change. That code has grown quite a list of "don't tailcall when ..." cases. OK for the trunk. jeff ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call 2016-01-01 0:00 [PATCH 0/3] Support for mandatory tail calls David Malcolm 2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p David Malcolm @ 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` Trevor Saunders 2016-01-01 0:00 ` [PATCH 0/3] Support for mandatory tail calls Jeff Law 3 siblings, 1 reply; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: gcc-patches, jit; +Cc: David Malcolm This implements the libgccjit support for must-tail-call via a new: gcc_jit_rvalue_set_bool_require_tail_call API entrypoint. (I didn't implement a wrapper for this within the C++ bindings) Successfully bootstrapped®rtested on x86_64-pc-linux-gnu. gcc/jit/ChangeLog: * docs/topics/compatibility.rst: Add LIBGCCJIT_ABI_6. * docs/topics/expressions.rst (Function calls): Add documentation of gcc_jit_rvalue_set_bool_require_tail_call. * docs/_build/texinfo/libgccjit.texi: Regenerate. * jit-common.h (gcc::jit::recording::base_call): Add forward decl. * jit-playback.c: Within namespace gcc::jit::playback... (context::build_call) Add "require_tail_call" param and use it to set CALL_EXPR_MUST_TAIL_CALL. (context::new_call): Add "require_tail_call" param. (context::new_call_through_ptr): Likewise. * jit-playback.h: Within namespace gcc::jit::playback... (context::new_call: Add "require_tail_call" param. (context::new_call_through_ptr): Likewise. (context::build_call): Likewise. * jit-recording.c: Within namespace gcc::jit::recording... (base_call::base_call): New constructor. (base_call::write_reproducer_tail_call): New method. (call::call): Update for inheritance from base_call. (call::replay_into): Provide m_require_tail_call to call to new_call. (call::write_reproducer): Call write_reproducer_tail_call. (call_through_ptr::call_through_ptr): Update for inheritance from base_call. (call_through_ptr::replay_into): Provide m_require_tail_call to call to new_call_through_ptr. (recording::call_through_ptr::write_reproducer): Call write_reproducer_tail_call. * jit-recording.h: Within namespace gcc::jit::recording... (rvalue::dyn_cast_base_call): New virtual function. (class base_call): New subclass of class rvalue. (class call): Inherit from base_call rather than directly from rvalue, moving get_precedence and m_args to base_call. (class call_through_ptr): Likewise. * libgccjit.c (gcc_jit_rvalue_set_bool_require_tail_call): New function. * libgccjit.h (LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call): New macro. (gcc_jit_rvalue_set_bool_require_tail_call): New function. * libgccjit.map (LIBGCCJIT_ABI_6): New. (gcc_jit_rvalue_set_bool_require_tail_call): Add. gcc/testsuite/ChangeLog: * jit.dg/all-non-failing-tests.h: Add test-factorial-must-tail-call.c. * jit.dg/test-error-impossible-must-tail-call.c: New test case. * jit.dg/test-factorial-must-tail-call.c: New test case. --- gcc/jit/docs/topics/compatibility.rst | 7 ++ gcc/jit/docs/topics/expressions.rst | 24 +++++ gcc/jit/jit-common.h | 1 + gcc/jit/jit-playback.c | 23 +++-- gcc/jit/jit-playback.h | 9 +- gcc/jit/jit-recording.c | 60 +++++++++--- gcc/jit/jit-recording.h | 46 ++++++--- gcc/jit/libgccjit.c | 20 ++++ gcc/jit/libgccjit.h | 13 +++ gcc/jit/libgccjit.map | 5 + gcc/testsuite/jit.dg/all-non-failing-tests.h | 10 ++ .../jit.dg/test-error-impossible-must-tail-call.c | 93 ++++++++++++++++++ .../jit.dg/test-factorial-must-tail-call.c | 109 +++++++++++++++++++++ 13 files changed, 382 insertions(+), 38 deletions(-) create mode 100644 gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c create mode 100644 gcc/testsuite/jit.dg/test-factorial-must-tail-call.c diff --git a/gcc/jit/docs/topics/compatibility.rst b/gcc/jit/docs/topics/compatibility.rst index d9eacf2..7abd050 100644 --- a/gcc/jit/docs/topics/compatibility.rst +++ b/gcc/jit/docs/topics/compatibility.rst @@ -135,3 +135,10 @@ entrypoints: ------------------- ``LIBGCCJIT_ABI_5`` covers the addition of :func:`gcc_jit_context_set_bool_use_external_driver` + +.. _LIBGCCJIT_ABI_6: + +``LIBGCCJIT_ABI_6`` +------------------- +``LIBGCCJIT_ABI_6`` covers the addition of +:func:`gcc_jit_rvalue_set_bool_require_tail_call` diff --git a/gcc/jit/docs/topics/expressions.rst b/gcc/jit/docs/topics/expressions.rst index 0445332..261483c 100644 --- a/gcc/jit/docs/topics/expressions.rst +++ b/gcc/jit/docs/topics/expressions.rst @@ -424,6 +424,30 @@ Function calls The same caveat as for :c:func:`gcc_jit_context_new_call` applies. +.. function:: void\ + gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *call,\ + int require_tail_call) + + Given an :c:type:`gcc_jit_rvalue *` for a call created through + :c:func:`gcc_jit_context_new_call` or + :c:func:`gcc_jit_context_new_call_through_ptr`, mark/clear the + call as needing tail-call optimization. The optimizer will + attempt to optimize the call into a jump instruction; if it is + unable to do do, an error will be emitted. + + This may be useful when implementing functions that use the + continuation-passing style (e.g. for functional programming + languages), in which every function "returns" by calling a + "continuation" function pointer. This call must be + guaranteed to be implemented as a jump, otherwise the program + could consume an arbitrary amount of stack space as it executed. + + This entrypoint was added in :ref:`LIBGCCJIT_ABI_6`; you can test for + its presence using + + .. code-block:: c + + #ifdef LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call Type-coercion ************* diff --git a/gcc/jit/jit-common.h b/gcc/jit/jit-common.h index 8a6cd74..b48ea0d 100644 --- a/gcc/jit/jit-common.h +++ b/gcc/jit/jit-common.h @@ -126,6 +126,7 @@ namespace recording { class local; class global; class param; + class base_call; class statement; class case_; diff --git a/gcc/jit/jit-playback.c b/gcc/jit/jit-playback.c index 156448d..c9f4084 100644 --- a/gcc/jit/jit-playback.c +++ b/gcc/jit/jit-playback.c @@ -854,7 +854,8 @@ playback::rvalue * playback::context:: build_call (location *loc, tree fn_ptr, - const auto_vec<rvalue *> *args) + const auto_vec<rvalue *> *args, + bool require_tail_call) { vec<tree, va_gc> *tree_args; vec_alloc (tree_args, args->length ()); @@ -868,9 +869,13 @@ build_call (location *loc, tree fn_type = TREE_TYPE (fn); tree return_type = TREE_TYPE (fn_type); - return new rvalue (this, - build_call_vec (return_type, - fn_ptr, tree_args)); + tree call = build_call_vec (return_type, + fn_ptr, tree_args); + + if (require_tail_call) + CALL_EXPR_MUST_TAIL_CALL (call) = 1; + + return new rvalue (this, call); /* see c-typeck.c: build_function_call which calls build_function_call_vec @@ -890,7 +895,8 @@ playback::rvalue * playback::context:: new_call (location *loc, function *func, - const auto_vec<rvalue *> *args) + const auto_vec<rvalue *> *args, + bool require_tail_call) { tree fndecl; @@ -902,7 +908,7 @@ new_call (location *loc, tree fn = build1 (ADDR_EXPR, build_pointer_type (fntype), fndecl); - return build_call (loc, fn, args); + return build_call (loc, fn, args, require_tail_call); } /* Construct a playback::rvalue instance (wrapping a tree) for a @@ -912,12 +918,13 @@ playback::rvalue * playback::context:: new_call_through_ptr (location *loc, rvalue *fn_ptr, - const auto_vec<rvalue *> *args) + const auto_vec<rvalue *> *args, + bool require_tail_call) { gcc_assert (fn_ptr); tree t_fn_ptr = fn_ptr->as_tree (); - return build_call (loc, t_fn_ptr, args); + return build_call (loc, t_fn_ptr, args, require_tail_call); } /* Construct a tree for a cast. */ diff --git a/gcc/jit/jit-playback.h b/gcc/jit/jit-playback.h index 8f7a43d..c00c258 100644 --- a/gcc/jit/jit-playback.h +++ b/gcc/jit/jit-playback.h @@ -133,12 +133,14 @@ public: rvalue * new_call (location *loc, function *func, - const auto_vec<rvalue *> *args); + const auto_vec<rvalue *> *args, + bool require_tail_call); rvalue * new_call_through_ptr (location *loc, rvalue *fn_ptr, - const auto_vec<rvalue *> *args); + const auto_vec<rvalue *> *args, + bool require_tail_call); rvalue * new_cast (location *loc, @@ -236,7 +238,8 @@ private: rvalue * build_call (location *loc, tree fn_ptr, - const auto_vec<rvalue *> *args); + const auto_vec<rvalue *> *args, + bool require_tail_call); tree build_cast (location *loc, diff --git a/gcc/jit/jit-recording.c b/gcc/jit/jit-recording.c index 8f5f914..9376342 100644 --- a/gcc/jit/jit-recording.c +++ b/gcc/jit/jit-recording.c @@ -4681,6 +4681,39 @@ recording::cast::write_reproducer (reproducer &r) r.get_identifier_as_type (get_type ())); } +/* The implementation of class gcc::jit::recording::base_call. */ + +/* The constructor for gcc::jit::recording::base_call. */ + +recording::base_call::base_call (context *ctxt, + location *loc, + type *type_, + int numargs, + rvalue **args) +: rvalue (ctxt, loc, type_), + m_args (), + m_require_tail_call (0) +{ + for (int i = 0; i< numargs; i++) + m_args.safe_push (args[i]); +} + +/* Subroutine for use by call and call_though_ptr's write_reproducer + methods. */ + +void +recording::base_call::write_reproducer_tail_call (reproducer &r, + const char *id) +{ + if (m_require_tail_call) + { + r.write (" gcc_jit_rvalue_set_bool_require_tail_call (%s, /* gcc_jit_rvalue *call*/\n" + " %i); /* int require_tail_call*/\n", + id, + 1); + } +} + /* The implementation of class gcc::jit::recording::call. */ /* The constructor for gcc::jit::recording::call. */ @@ -4690,12 +4723,9 @@ recording::call::call (recording::context *ctxt, recording::function *func, int numargs, rvalue **args) -: rvalue (ctxt, loc, func->get_return_type ()), - m_func (func), - m_args () +: base_call (ctxt, loc, func->get_return_type (), numargs, args), + m_func (func) { - for (int i = 0; i< numargs; i++) - m_args.safe_push (args[i]); } /* Implementation of pure virtual hook recording::memento::replay_into @@ -4711,7 +4741,8 @@ recording::call::replay_into (replayer *r) set_playback_obj (r->new_call (playback_location (r, m_loc), m_func->playback_function (), - &playback_args)); + &playback_args, + m_require_tail_call)); } /* Implementation of pure virtual hook recording::rvalue::visit_children @@ -4790,6 +4821,7 @@ recording::call::write_reproducer (reproducer &r) r.get_identifier (m_func), m_args.length (), args_id); + write_reproducer_tail_call (r, id); } /* The implementation of class gcc::jit::recording::call_through_ptr. */ @@ -4801,14 +4833,12 @@ recording::call_through_ptr::call_through_ptr (recording::context *ctxt, recording::rvalue *fn_ptr, int numargs, rvalue **args) -: rvalue (ctxt, loc, - fn_ptr->get_type ()->dereference () - ->as_a_function_type ()->get_return_type ()), - m_fn_ptr (fn_ptr), - m_args () +: base_call (ctxt, loc, + fn_ptr->get_type ()->dereference () + ->as_a_function_type ()->get_return_type (), + numargs, args), + m_fn_ptr (fn_ptr) { - for (int i = 0; i< numargs; i++) - m_args.safe_push (args[i]); } /* Implementation of pure virtual hook recording::memento::replay_into @@ -4824,7 +4854,8 @@ recording::call_through_ptr::replay_into (replayer *r) set_playback_obj (r->new_call_through_ptr (playback_location (r, m_loc), m_fn_ptr->playback_rvalue (), - &playback_args)); + &playback_args, + m_require_tail_call)); } /* Implementation of pure virtual hook recording::rvalue::visit_children @@ -4907,6 +4938,7 @@ recording::call_through_ptr::write_reproducer (reproducer &r) r.get_identifier_as_rvalue (m_fn_ptr), m_args.length (), args_id); + write_reproducer_tail_call (r, id); } /* The implementation of class gcc::jit::recording::array_access. */ diff --git a/gcc/jit/jit-recording.h b/gcc/jit/jit-recording.h index 1c3e763..0e3511c 100644 --- a/gcc/jit/jit-recording.h +++ b/gcc/jit/jit-recording.h @@ -960,8 +960,9 @@ public: void set_scope (function *scope); function *get_scope () const { return m_scope; } - /* Dynamic cast. */ + /* Dynamic casts. */ virtual param *dyn_cast_param () { return NULL; } + virtual base_call *dyn_cast_base_call () { return NULL; } virtual const char *access_as_rvalue (reproducer &r); @@ -1418,7 +1419,36 @@ private: rvalue *m_rvalue; }; -class call : public rvalue +class base_call : public rvalue +{ + public: + base_call (context *ctxt, + location *loc, + type *type_, + int numargs, + rvalue **args); + + enum precedence get_precedence () const FINAL OVERRIDE + { + return PRECEDENCE_POSTFIX; + } + + base_call *dyn_cast_base_call () FINAL OVERRIDE { return this; } + + void set_require_tail_call (bool require_tail_call) + { + m_require_tail_call = require_tail_call; + } + + protected: + void write_reproducer_tail_call (reproducer &r, const char *id); + + protected: + auto_vec<rvalue *> m_args; + bool m_require_tail_call; +}; + +class call : public base_call { public: call (context *ctxt, @@ -1434,17 +1464,12 @@ public: private: string * make_debug_string () FINAL OVERRIDE; void write_reproducer (reproducer &r) FINAL OVERRIDE; - enum precedence get_precedence () const FINAL OVERRIDE - { - return PRECEDENCE_POSTFIX; - } private: function *m_func; - auto_vec<rvalue *> m_args; }; -class call_through_ptr : public rvalue +class call_through_ptr : public base_call { public: call_through_ptr (context *ctxt, @@ -1460,14 +1485,9 @@ public: private: string * make_debug_string () FINAL OVERRIDE; void write_reproducer (reproducer &r) FINAL OVERRIDE; - enum precedence get_precedence () const FINAL OVERRIDE - { - return PRECEDENCE_POSTFIX; - } private: rvalue *m_fn_ptr; - auto_vec<rvalue *> m_args; }; class array_access : public lvalue diff --git a/gcc/jit/libgccjit.c b/gcc/jit/libgccjit.c index 02ff50c..c2c6aeb 100644 --- a/gcc/jit/libgccjit.c +++ b/gcc/jit/libgccjit.c @@ -2950,3 +2950,23 @@ gcc_jit_timer_print (gcc_jit_timer *timer, timer->start (TV_TOTAL); timer->push (TV_JIT_CLIENT_CODE); } + +/* Public entrypoint. See description in libgccjit.h. + + After error-checking, the real work is effectively done by the + gcc::jit::base_call::set_require_tail_call setter in jit-recording.h. */ + +void +gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *rvalue, + int require_tail_call) +{ + RETURN_IF_FAIL (rvalue, NULL, NULL, "NULL call"); + JIT_LOG_FUNC (rvalue->get_context ()->get_logger ()); + + /* Verify that it's a call. */ + gcc::jit::recording::base_call *call = rvalue->dyn_cast_base_call (); + RETURN_IF_FAIL_PRINTF1 (call, NULL, NULL, "not a call: %s", + rvalue->get_debug_string ()); + + call->set_require_tail_call (require_tail_call); +} diff --git a/gcc/jit/libgccjit.h b/gcc/jit/libgccjit.h index a8b9f55..175cc16c 100644 --- a/gcc/jit/libgccjit.h +++ b/gcc/jit/libgccjit.h @@ -1374,6 +1374,19 @@ extern void gcc_jit_timer_print (gcc_jit_timer *timer, FILE *f_out); + +#define LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call + +/* Mark/clear a call as needing tail-call optimization. + + This API entrypoint was added in LIBGCCJIT_ABI_6; you can test for its + presence using + #ifdef LIBGCCJIT_HAVE_gcc_jit_rvalue_set_bool_require_tail_call +*/ +extern void +gcc_jit_rvalue_set_bool_require_tail_call (gcc_jit_rvalue *call, + int require_tail_call); + #ifdef __cplusplus } #endif /* __cplusplus */ diff --git a/gcc/jit/libgccjit.map b/gcc/jit/libgccjit.map index 65f3166..545b192 100644 --- a/gcc/jit/libgccjit.map +++ b/gcc/jit/libgccjit.map @@ -145,3 +145,8 @@ LIBGCCJIT_ABI_5 { global: gcc_jit_context_set_bool_use_external_driver; } LIBGCCJIT_ABI_4; + +LIBGCCJIT_ABI_6 { + global: + gcc_jit_rvalue_set_bool_require_tail_call; +} LIBGCCJIT_ABI_5; diff --git a/gcc/testsuite/jit.dg/all-non-failing-tests.h b/gcc/testsuite/jit.dg/all-non-failing-tests.h index 463eefb..3e2b3b9 100644 --- a/gcc/testsuite/jit.dg/all-non-failing-tests.h +++ b/gcc/testsuite/jit.dg/all-non-failing-tests.h @@ -105,6 +105,13 @@ #undef create_code #undef verify_code +/* test-factorial-must-tail-call.c */ +#define create_code create_code_factorial_must_tail_call +#define verify_code verify_code_factorial_must_tail_call +#include "test-factorial-must-tail-call.c" +#undef create_code +#undef verify_code + /* test-fibonacci.c */ #define create_code create_code_fibonacci #define verify_code verify_code_fibonacci @@ -272,6 +279,9 @@ const struct testcase testcases[] = { {"factorial", create_code_factorial, verify_code_factorial}, + {"factorial_must_tail_call", + create_code_factorial_must_tail_call, + verify_code_factorial_must_tail_call}, {"fibonacci", create_code_fibonacci, verify_code_fibonacci}, diff --git a/gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c b/gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c new file mode 100644 index 0000000..8848d30 --- /dev/null +++ b/gcc/testsuite/jit.dg/test-error-impossible-must-tail-call.c @@ -0,0 +1,93 @@ +#include <stdlib.h> +#include <stdio.h> + +#include "libgccjit.h" + +#include "harness.h" + +#ifdef __cplusplus +extern "C" { +#endif + + struct box { char dummy[64]; int i; }; + + extern struct box + returns_struct (int i); + +#ifdef __cplusplus +} +#endif + +void +create_code (gcc_jit_context *ctxt, void *user_data) +{ + /* Let's try to inject the equivalent of: + + int test (int i) + { + return [MUST TAIL CALL] returns_struct (i).i; + } + + and verify that we get a sane error when the tail call + optimization can't be done. */ + + gcc_jit_type *char_type = + gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_CHAR); + gcc_jit_type *int_type = + gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_INT); + + /* Declare "struct box. */ + gcc_jit_type *array_type = + gcc_jit_context_new_array_type (ctxt, NULL, char_type, 64); + gcc_jit_field *field_dummy = + gcc_jit_context_new_field (ctxt, NULL, array_type, "dummy"); + gcc_jit_field *field_i = + gcc_jit_context_new_field (ctxt, NULL, int_type, "i"); + gcc_jit_field *fields[2] = {field_dummy, field_i}; + gcc_jit_struct *struct_box = + gcc_jit_context_new_struct_type (ctxt, NULL, "box", 2, fields); + + /* Declare the imported function. */ + gcc_jit_param *called_fn_param_i = + gcc_jit_context_new_param (ctxt, NULL, int_type, "i"); + gcc_jit_function *called_fn = + gcc_jit_context_new_function (ctxt, NULL, + GCC_JIT_FUNCTION_IMPORTED, + gcc_jit_struct_as_type (struct_box), + "called_function", + 1, &called_fn_param_i, + 0); + + /* Build the test_fn. */ + gcc_jit_param *caller_param_i = + gcc_jit_context_new_param (ctxt, NULL, int_type, "i"); + gcc_jit_function *test_fn = + gcc_jit_context_new_function (ctxt, NULL, + GCC_JIT_FUNCTION_EXPORTED, + int_type, + "test_caller", + 1, &caller_param_i, + 0); + gcc_jit_rvalue *arg = gcc_jit_param_as_rvalue (caller_param_i); + + gcc_jit_rvalue *call = + gcc_jit_context_new_call (ctxt, NULL, + called_fn, + 1, &arg); + + /* Mark the call as requiring tail-call optimization. */ + gcc_jit_rvalue_set_bool_require_tail_call (call, 1); + + gcc_jit_block *block = gcc_jit_function_new_block (test_fn, NULL); + gcc_jit_block_end_with_return (block, NULL, + gcc_jit_rvalue_access_field (call, NULL, field_i)); +} + +void +verify_code (gcc_jit_context *ctxt, gcc_jit_result *result) +{ + CHECK_VALUE (result, NULL); + + CHECK_STRING_VALUE (gcc_jit_context_get_first_error (ctxt), + "cannot tail-call: callee returns a structure"); +} diff --git a/gcc/testsuite/jit.dg/test-factorial-must-tail-call.c b/gcc/testsuite/jit.dg/test-factorial-must-tail-call.c new file mode 100644 index 0000000..c862611 --- /dev/null +++ b/gcc/testsuite/jit.dg/test-factorial-must-tail-call.c @@ -0,0 +1,109 @@ +#include <stdlib.h> +#include <stdio.h> +#include <string.h> + +#include "libgccjit.h" + +#include "harness.h" + +void +create_code (gcc_jit_context *ctxt, void *user_data) +{ + /* Let's try to inject the equivalent of: + + int + my_factorial_must_tail_call (int x) + { + if (x < 2) + return x; + else + return x * my_factorial_must_tail_call (x - 1); + } + + and mark the call as requiring tail-call-optimization. + */ + gcc_jit_type *the_type = + gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_INT); + gcc_jit_type *return_type = the_type; + + gcc_jit_param *x = + gcc_jit_context_new_param (ctxt, NULL, the_type, "x"); + gcc_jit_param *params[1] = {x}; + gcc_jit_function *func = + gcc_jit_context_new_function (ctxt, NULL, + GCC_JIT_FUNCTION_EXPORTED, + return_type, + "my_factorial_must_tail_call", + 1, params, 0); + + gcc_jit_block *initial = + gcc_jit_function_new_block (func, "initial"); + gcc_jit_block *on_true = + gcc_jit_function_new_block (func, "on_true"); + gcc_jit_block *on_false = + gcc_jit_function_new_block (func, "on_false"); + + /* if (x < 2) */ + gcc_jit_block_end_with_conditional ( + initial, NULL, + gcc_jit_context_new_comparison ( + ctxt, NULL, + GCC_JIT_COMPARISON_LT, + gcc_jit_param_as_rvalue (x), + gcc_jit_context_new_rvalue_from_int ( + ctxt, + the_type, + 2)), + on_true, + on_false); + + /* true branch: */ + /* return x */ + gcc_jit_block_end_with_return ( + on_true, + NULL, + gcc_jit_param_as_rvalue (x)); + + /* false branch: */ + gcc_jit_rvalue *x_minus_1 = + gcc_jit_context_new_binary_op ( + ctxt, NULL, + GCC_JIT_BINARY_OP_MINUS, the_type, + gcc_jit_param_as_rvalue (x), + gcc_jit_context_new_rvalue_from_int ( + ctxt, + the_type, + 1)); + /* my_factorial_must_tail_call (x - 1) */ + gcc_jit_rvalue *call = + gcc_jit_context_new_call ( + ctxt, NULL, + func, + 1, &x_minus_1); + + /* Mark the call as requiring tail-call optimization. */ + gcc_jit_rvalue_set_bool_require_tail_call (call, 1); + + gcc_jit_block_end_with_return ( + on_false, + NULL, + gcc_jit_context_new_binary_op ( + ctxt, NULL, + GCC_JIT_BINARY_OP_MULT, the_type, + gcc_jit_param_as_rvalue (x), + call)); +} + +void +verify_code (gcc_jit_context *ctxt, gcc_jit_result *result) +{ + typedef int (*my_factorial_fn_type) (int); + CHECK_NON_NULL (result); + my_factorial_fn_type my_factorial_must_tail_call = + (my_factorial_fn_type)gcc_jit_result_get_code (result, "my_factorial_must_tail_call"); + CHECK_NON_NULL (my_factorial_must_tail_call); + int val = my_factorial_must_tail_call (10); + note ("my_factorial_must_tail_call returned: %d", val); + CHECK_VALUE (val, 3628800); +} + -- 1.8.5.3 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call 2016-01-01 0:00 ` [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call David Malcolm @ 2016-01-01 0:00 ` Trevor Saunders 2016-01-01 0:00 ` David Malcolm 0 siblings, 1 reply; 22+ messages in thread From: Trevor Saunders @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm; +Cc: gcc-patches, jit On Tue, May 17, 2016 at 06:01:32PM -0400, David Malcolm wrote: > This implements the libgccjit support for must-tail-call via > a new: > gcc_jit_rvalue_set_bool_require_tail_call > API entrypoint. It seems to me like that's not a great name, the rvalue and bool parts are just about the argument types, not what the function does. Wouldn't gcc_jit_set_call_requires_tail_call be better? Trev ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call 2016-01-01 0:00 ` Trevor Saunders @ 2016-01-01 0:00 ` David Malcolm 0 siblings, 0 replies; 22+ messages in thread From: David Malcolm @ 2016-01-01 0:00 UTC (permalink / raw) To: Trevor Saunders; +Cc: gcc-patches, jit On Tue, 2016-05-17 at 18:49 -0400, Trevor Saunders wrote: > On Tue, May 17, 2016 at 06:01:32PM -0400, David Malcolm wrote: > > This implements the libgccjit support for must-tail-call via > > a new: > > gcc_jit_rvalue_set_bool_require_tail_call > > API entrypoint. > > It seems to me like that's not a great name, the rvalue and bool > parts > are just about the argument types, not what the function does. > Wouldn't > gcc_jit_set_call_requires_tail_call be better? Maybe. I was thinking of it from the point of view of methods; it's effectively a method on gcc_jit_rvalue. The "set_bool" is for consistency with various gcc_jit_context_ entrypoints. FWIW, I've committed the patch as-is; all of the must-tail-call patches are now in trunk, as of r236531. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 0/3] Support for mandatory tail calls 2016-01-01 0:00 [PATCH 0/3] Support for mandatory tail calls David Malcolm ` (2 preceding siblings ...) 2016-01-01 0:00 ` [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call David Malcolm @ 2016-01-01 0:00 ` Jeff Law 2016-01-01 0:00 ` Basile Starynkevitch 3 siblings, 1 reply; 22+ messages in thread From: Jeff Law @ 2016-01-01 0:00 UTC (permalink / raw) To: David Malcolm, gcc-patches, jit On 05/17/2016 04:01 PM, David Malcolm wrote: > There have been requests [1] for libgccjit to better support > functional programming by supporting the contination-passing style, > in which every function "returns" by calling a "continuation" > function pointer. > > These calls must be guaranteed to be implemented as a jump, > otherwise the program could consume an arbitrary amount of stack > space as it executed. > > This patch kit implements this. > > Patch 1 is a preliminary tweak to calls.c > > Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL, > which makes calls.c try harder to implement a flagged call as a > tail-call/sibling call, and makes it issue an error if > the optimization is impossible. It doesn't implement any > frontend support for setting the flag (instead using a plugin > to test it). We had some discussion on the jit list about possibly > introducing a new builtin for this, but the patch punts on this > issue. I wonder if we should have an attribute so that the flag can be set for C/C++ code. I've seen requests for forcing tail calls in C/C++ code several times in the past, precisely to support continuations. Jeff ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 0/3] Support for mandatory tail calls 2016-01-01 0:00 ` [PATCH 0/3] Support for mandatory tail calls Jeff Law @ 2016-01-01 0:00 ` Basile Starynkevitch 2016-01-01 0:00 ` Jason Merrill 0 siblings, 1 reply; 22+ messages in thread From: Basile Starynkevitch @ 2016-01-01 0:00 UTC (permalink / raw) To: Jeff Law, David Malcolm, gcc-patches, jit On 05/19/2016 12:12 AM, Jeff Law wrote: > On 05/17/2016 04:01 PM, David Malcolm wrote: >> There have been requests [1] for libgccjit to better support >> functional programming by supporting the contination-passing style, >> in which every function "returns" by calling a "continuation" >> function pointer. >> >> These calls must be guaranteed to be implemented as a jump, >> otherwise the program could consume an arbitrary amount of stack >> space as it executed. >> >> This patch kit implements this. >> >> Patch 1 is a preliminary tweak to calls.c >> >> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL, >> which makes calls.c try harder to implement a flagged call as a >> tail-call/sibling call, and makes it issue an error if >> the optimization is impossible. It doesn't implement any >> frontend support for setting the flag (instead using a plugin >> to test it). We had some discussion on the jit list about possibly >> introducing a new builtin for this, but the patch punts on this >> issue. > I wonder if we should have an attribute so that the flag can be set > for C/C++ code. I've seen requests for forcing tail calls in C/C++ > code several times in the past, precisely to support continuations. Why an attribute? Attributes are on declarations. I think it should better be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or else some syntax extension like goto return foo(x,y); ...) because what we really want is to annotate a particular call to be tail-recursive. Cheers -- Basile STARYNKEVITCH http://starynkevitch.net/Basile/ email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359 8, rue de la Faiencerie, 92340 Bourg La Reine, France *** opinions {are only mine, sont seulement les miennes} *** ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 0/3] Support for mandatory tail calls 2016-01-01 0:00 ` Basile Starynkevitch @ 2016-01-01 0:00 ` Jason Merrill 2016-01-01 0:00 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Jason Merrill @ 2016-01-01 0:00 UTC (permalink / raw) To: Basile Starynkevitch; +Cc: Jeff Law, David Malcolm, gcc-patches List, jit On Thu, May 19, 2016 at 12:30 AM, Basile Starynkevitch <basile@starynkevitch.net> wrote: > On 05/19/2016 12:12 AM, Jeff Law wrote: >> >> On 05/17/2016 04:01 PM, David Malcolm wrote: >>> >>> There have been requests [1] for libgccjit to better support >>> functional programming by supporting the contination-passing style, >>> in which every function "returns" by calling a "continuation" >>> function pointer. >>> >>> These calls must be guaranteed to be implemented as a jump, >>> otherwise the program could consume an arbitrary amount of stack >>> space as it executed. >>> >>> This patch kit implements this. >>> >>> Patch 1 is a preliminary tweak to calls.c >>> >>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL, >>> which makes calls.c try harder to implement a flagged call as a >>> tail-call/sibling call, and makes it issue an error if >>> the optimization is impossible. It doesn't implement any >>> frontend support for setting the flag (instead using a plugin >>> to test it). We had some discussion on the jit list about possibly >>> introducing a new builtin for this, but the patch punts on this >>> issue. >> >> I wonder if we should have an attribute so that the flag can be set for >> C/C++ code. I've seen requests for forcing tail calls in C/C++ code several >> times in the past, precisely to support continuations. > > Why an attribute? Attributes are on declarations. I think it should better > be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or > else some syntax extension like goto return foo(x,y); ...) because what we > really want is to annotate a particular call to be tail-recursive. C++11 attributes can apply to expression-statements as well, e.g. [[gnu::tail_call]] fn(); though not to sub-expressions. Jason ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 0/3] Support for mandatory tail calls 2016-01-01 0:00 ` Jason Merrill @ 2016-01-01 0:00 ` Richard Biener 2016-01-01 0:00 ` Jason Merrill 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2016-01-01 0:00 UTC (permalink / raw) To: Jason Merrill Cc: Basile Starynkevitch, Jeff Law, David Malcolm, gcc-patches List, jit On Thu, May 19, 2016 at 3:19 PM, Jason Merrill <jason@redhat.com> wrote: > On Thu, May 19, 2016 at 12:30 AM, Basile Starynkevitch > <basile@starynkevitch.net> wrote: >> On 05/19/2016 12:12 AM, Jeff Law wrote: >>> >>> On 05/17/2016 04:01 PM, David Malcolm wrote: >>>> >>>> There have been requests [1] for libgccjit to better support >>>> functional programming by supporting the contination-passing style, >>>> in which every function "returns" by calling a "continuation" >>>> function pointer. >>>> >>>> These calls must be guaranteed to be implemented as a jump, >>>> otherwise the program could consume an arbitrary amount of stack >>>> space as it executed. >>>> >>>> This patch kit implements this. >>>> >>>> Patch 1 is a preliminary tweak to calls.c >>>> >>>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL, >>>> which makes calls.c try harder to implement a flagged call as a >>>> tail-call/sibling call, and makes it issue an error if >>>> the optimization is impossible. It doesn't implement any >>>> frontend support for setting the flag (instead using a plugin >>>> to test it). We had some discussion on the jit list about possibly >>>> introducing a new builtin for this, but the patch punts on this >>>> issue. >>> >>> I wonder if we should have an attribute so that the flag can be set for >>> C/C++ code. I've seen requests for forcing tail calls in C/C++ code several >>> times in the past, precisely to support continuations. >> >> Why an attribute? Attributes are on declarations. I think it should better >> be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or >> else some syntax extension like goto return foo(x,y); ...) because what we >> really want is to annotate a particular call to be tail-recursive. > > C++11 attributes can apply to expression-statements as well, e.g. > > [[gnu::tail_call]] fn(); > > though not to sub-expressions. That's nice. Can they apply to things like loops? [[gnu::no_unroll]] for (int i=0; i<4; ++i) a[i] = 0; Richard. > Jason ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 0/3] Support for mandatory tail calls 2016-01-01 0:00 ` Richard Biener @ 2016-01-01 0:00 ` Jason Merrill 0 siblings, 0 replies; 22+ messages in thread From: Jason Merrill @ 2016-01-01 0:00 UTC (permalink / raw) To: Richard Biener Cc: Basile Starynkevitch, Jeff Law, David Malcolm, gcc-patches List, jit On Thu, May 19, 2016 at 9:28 AM, Richard Biener <richard.guenther@gmail.com> wrote: > On Thu, May 19, 2016 at 3:19 PM, Jason Merrill <jason@redhat.com> wrote: >> On Thu, May 19, 2016 at 12:30 AM, Basile Starynkevitch >> <basile@starynkevitch.net> wrote: >>> On 05/19/2016 12:12 AM, Jeff Law wrote: >>>> >>>> On 05/17/2016 04:01 PM, David Malcolm wrote: >>>>> >>>>> There have been requests [1] for libgccjit to better support >>>>> functional programming by supporting the contination-passing style, >>>>> in which every function "returns" by calling a "continuation" >>>>> function pointer. >>>>> >>>>> These calls must be guaranteed to be implemented as a jump, >>>>> otherwise the program could consume an arbitrary amount of stack >>>>> space as it executed. >>>>> >>>>> This patch kit implements this. >>>>> >>>>> Patch 1 is a preliminary tweak to calls.c >>>>> >>>>> Patch 2 implements a new flag in tree.h: CALL_EXPR_MUST_TAIL_CALL, >>>>> which makes calls.c try harder to implement a flagged call as a >>>>> tail-call/sibling call, and makes it issue an error if >>>>> the optimization is impossible. It doesn't implement any >>>>> frontend support for setting the flag (instead using a plugin >>>>> to test it). We had some discussion on the jit list about possibly >>>>> introducing a new builtin for this, but the patch punts on this >>>>> issue. >>>> >>>> I wonder if we should have an attribute so that the flag can be set for >>>> C/C++ code. I've seen requests for forcing tail calls in C/C++ code several >>>> times in the past, precisely to support continuations. >>> >>> Why an attribute? Attributes are on declarations. I think it should better >>> be some pragma like _Pragma(GCC tail cail, foo(x,y)) or some builtin (or >>> else some syntax extension like goto return foo(x,y); ...) because what we >>> really want is to annotate a particular call to be tail-recursive. >> >> C++11 attributes can apply to expression-statements as well, e.g. >> >> [[gnu::tail_call]] fn(); >> >> though not to sub-expressions. > > That's nice. Can they apply to things like loops? > > [[gnu::no_unroll]] for (int i=0; i<4; ++i) > a[i] = 0; Yes, to any statement. Jason ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2016-06-09 21:00 UTC | newest] Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-01-01 0:00 [PATCH 0/3] Support for mandatory tail calls David Malcolm 2016-01-01 0:00 ` [PATCH 2/3] Implement CALL_EXPR_MUST_TAIL_CALL David Malcolm 2016-01-01 0:00 ` Jeff Law 2016-01-01 0:00 ` Andreas Schwab 2016-01-01 0:00 ` Andreas Schwab 2016-01-01 0:00 ` [PATCH] Fixes to must-tail-call tests David Malcolm 2016-01-01 0:00 ` Rainer Orth 2016-01-01 0:00 ` Thomas Preudhomme 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` Jeff Law 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p David Malcolm 2016-01-01 0:00 ` Kyrill Tkachov 2016-01-01 0:00 ` [PATCH] calls.c: fix warning on targets without REG_PARM_STACK_SPACE David Malcolm 2016-01-01 0:00 ` [PATCH 1/3] Introduce can_implement_as_sibling_call_p Jeff Law 2016-01-01 0:00 ` [PATCH 3/3] jit: implement gcc_jit_rvalue_set_bool_require_tail_call David Malcolm 2016-01-01 0:00 ` Trevor Saunders 2016-01-01 0:00 ` David Malcolm 2016-01-01 0:00 ` [PATCH 0/3] Support for mandatory tail calls Jeff Law 2016-01-01 0:00 ` Basile Starynkevitch 2016-01-01 0:00 ` Jason Merrill 2016-01-01 0:00 ` Richard Biener 2016-01-01 0:00 ` Jason Merrill
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).