From 9a385c2d3d74ffed78f2ed9ad47b844d2f294105 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 20 May 2016 14:20:03 +0000 Subject: Implement CALL_EXPR_MUST_TAIL_CALL 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. 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. From-SVN: r236514 --- gcc/ChangeLog | 26 +++++ 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/ChangeLog | 7 ++ 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 + 14 files changed, 332 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/ChangeLog b/gcc/ChangeLog index 1b5959d..67d7bf8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,31 @@ 2016-05-20 David Malcolm + * 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. + +2016-05-20 David Malcolm + * 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 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 1461ad8..56ef71d 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 f864268..48edacc 100644 --- a/gcc/gimple-pretty-print.c +++ b/gcc/gimple-pretty-print.c @@ -760,6 +760,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 742c907..226b080 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/ChangeLog b/gcc/testsuite/ChangeLog index 9ddd4f9..d5739cb 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,10 @@ +2016-05-20 David Malcolm + + * 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. + 2016-05-20 Jan Hubicka * gcc.dg/tree-ssa/prefetch-5.c: xfail. 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 e4c5068..b069928 100644 --- a/gcc/tree-core.h +++ b/gcc/tree-core.h @@ -1001,6 +1001,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) \ -- cgit v1.1