diff options
| -rw-r--r-- | gcc/ChangeLog | 8 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.c-torture/compile/20060202-1.c | 54 | ||||
| -rw-r--r-- | gcc/tree-tailcall.c | 150 |
3 files changed, 142 insertions, 70 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ac296e0d73b..7525f4c8258 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2006-02-02 Zdenek Dvorak <dvorakz@suse.cz> + Daniel Berlin <dberlin@dberlin.org> + + * tree-tailcall.c (arg_needs_copy_p): New function. + (eliminate_tail_call): Use arg_needs_copy_p. + (tree_optimize_tail_calls_1): Ditto. Also call add_virtual_phis. + (add_virtual_phis): New function. + 2006-02-02 Jakub Jelinek <jakub@redhat.com> * config/sparc/sparc.c (sparc_output_scratch_registers): Use diff --git a/gcc/testsuite/gcc.c-torture/compile/20060202-1.c b/gcc/testsuite/gcc.c-torture/compile/20060202-1.c new file mode 100644 index 00000000000..9d440741c6b --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/compile/20060202-1.c @@ -0,0 +1,54 @@ +typedef unsigned int size_t; +typedef const struct objc_selector +{ + void *sel_id; +} + *SEL; +typedef struct objc_object +{ +} + *id; +typedef struct objc_class *Class; +struct objc_class +{ + struct sarray *dtable; +}; +typedef size_t sidx; +struct soffset +{ + unsigned int boffset:(sizeof (size_t) * 8) / 2; + unsigned int eoffset:(sizeof (size_t) * 8) / 2; +}; +union sofftype +{ + struct soffset off; + sidx idx; +}; +struct sarray +{ + size_t capacity; +}; +static __inline__ unsigned int +soffset_decode (sidx indx) +{ + union sofftype x; + x.idx = indx; + return x.off.eoffset + (x.off.boffset * (1 << 5)); +} +static __inline__ void * +sarray_get_safe (struct sarray *array, sidx indx) +{ + if (soffset_decode (indx) < array->capacity) + return (void *)sarray_get (array, indx); +} +void * +get_imp (Class class, SEL sel) +{ + void *res = sarray_get_safe (class->dtable, (size_t) sel->sel_id); + if (res == 0) + { + { + res = get_imp (class, sel); + } + } +} diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index 1a3116effad..b0f74ffbc70 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -690,6 +690,25 @@ decrease_profile (basic_block bb, gcov_type count, int frequency) e->count = 0; } +/* Returns true if argument PARAM of the tail recursive call needs to be copied + when the call is eliminated. */ + +static bool +arg_needs_copy_p (tree param) +{ + tree def; + + if (!is_gimple_reg (param) || !var_ann (param)) + return false; + + /* Parameters that are only defined but never used need not be copied. */ + def = default_def (param); + if (!def) + return false; + + return true; +} + /* Eliminates tail call described by T. TMP_VARS is a list of temporary variables used to copy the function arguments. */ @@ -701,9 +720,6 @@ eliminate_tail_call (struct tailcall *t) edge e; tree phi; block_stmt_iterator bsi; - use_operand_p mayuse; - def_operand_p maydef; - ssa_op_iter iter; tree orig_stmt; stmt = orig_stmt = bsi_stmt (t->call_bsi); @@ -751,65 +767,21 @@ eliminate_tail_call (struct tailcall *t) gcc_assert (e); PENDING_STMT (e) = NULL_TREE; - /* Add phi node entries for arguments. Not every PHI node corresponds to - a function argument (there may be PHI nodes for virtual definitions of the - eliminated calls), so we search for a PHI corresponding to each argument - rather than searching for which argument a PHI node corresponds to. */ - + /* Add phi node entries for arguments. The ordering of the phi nodes should + be the same as the ordering of the arguments. */ for (param = DECL_ARGUMENTS (current_function_decl), - args = TREE_OPERAND (stmt, 1); + args = TREE_OPERAND (stmt, 1), + phi = phi_nodes (first); param; param = TREE_CHAIN (param), args = TREE_CHAIN (args)) { - - for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi)) - if (param == SSA_NAME_VAR (PHI_RESULT (phi))) - break; - - /* The phi node indeed does not have to be there, in case the operand is - invariant in the function. */ - if (!phi) + if (!arg_needs_copy_p (param)) continue; + gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi))); add_phi_arg (phi, TREE_VALUE (args), e); - } - - /* Add phi nodes for the call clobbered variables. */ - FOR_EACH_SSA_MAYDEF_OPERAND (maydef, mayuse, orig_stmt, iter) - { - param = SSA_NAME_VAR (DEF_FROM_PTR (maydef)); - for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi)) - if (param == SSA_NAME_VAR (PHI_RESULT (phi))) - break; - - if (!phi) - { - tree name = default_def (param); - tree new_name; - - if (!name) - { - /* It may happen that the tag does not have a default_def in case - when all uses of it are dominated by a MUST_DEF. This however - means that it is not necessary to add a phi node for this - tag. */ - continue; - } - new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); - - set_default_def (param, new_name); - phi = create_phi_node (name, first); - SSA_NAME_DEF_STMT (name) = phi; - add_phi_arg (phi, new_name, single_succ_edge (ENTRY_BLOCK_PTR)); - - /* For all calls the same set of variables should be clobbered. This - means that there always should be the appropriate phi node except - for the first time we eliminate the call. */ - gcc_assert (EDGE_COUNT (first->preds) <= 2); - } - - add_phi_arg (phi, USE_FROM_PTR (mayuse), e); + phi = PHI_CHAIN (phi); } /* Update the values of accumulators. */ @@ -829,6 +801,38 @@ eliminate_tail_call (struct tailcall *t) release_defs (call); } +/* Add phi nodes for the virtual operands defined in the function to the + header of the loop created by tail recursion elimination. + + Originally, we used to add phi nodes only for call clobbered variables, + as the value of the non-call clobbered ones obviously cannot be used + or changed within the recursive call. However, the local variables + from multiple calls now share the same location, so the virtual ssa form + requires us to say that the location dies on further iterations of the loop, + which requires adding phi nodes. +*/ +static void +add_virtual_phis (void) +{ + referenced_var_iterator rvi; + tree var; + + /* The problematic part is that there is no way how to know what + to put into phi nodes (there in fact does not have to be such + ssa name available). A solution would be to have an artificial + use/kill for all virtual operands in EXIT node. Unless we have + this, we cannot do much better than to rebuild the ssa form for + possibly affected virtual ssa names from scratch. */ + + FOR_EACH_REFERENCED_VAR (var, rvi) + { + if (!is_gimple_reg (var) && default_def (var) != NULL_TREE) + mark_sym_for_renaming (var); + } + + update_ssa (TODO_update_ssa_only_virtuals); +} + /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also mark the tailcalls for the sibcall optimization. */ @@ -897,7 +901,6 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) if (!phis_constructed) { - tree name; /* Ensure that there is only one predecessor of the block. */ if (!single_pred_p (first)) first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); @@ -906,21 +909,17 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) for (param = DECL_ARGUMENTS (current_function_decl); param; param = TREE_CHAIN (param)) - if (is_gimple_reg (param) - && var_ann (param) - /* Also parameters that are only defined but never used need not - be copied. */ - && ((name = default_def (param)) - && TREE_CODE (name) == SSA_NAME)) - { - tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); - tree phi; - - set_default_def (param, new_name); - phi = create_phi_node (name, first); - SSA_NAME_DEF_STMT (name) = phi; - add_phi_arg (phi, new_name, single_pred_edge (first)); - } + if (arg_needs_copy_p (param)) + { + tree name = default_def (param); + tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); + tree phi; + + set_default_def (param, new_name); + phi = create_phi_node (name, first); + SSA_NAME_DEF_STMT (name) = phi; + add_phi_arg (phi, new_name, single_pred_edge (first)); + } phis_constructed = true; } @@ -957,6 +956,14 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) } } + + if (phis_constructed) + { + /* Reverse the order of the phi nodes, so that it matches the order + of operands of the function, as assumed by eliminate_tail_call. */ + set_phi_nodes (first, phi_reverse (phi_nodes (first))); + } + for (; tailcalls; tailcalls = next) { next = tailcalls->next; @@ -982,6 +989,9 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) free_dominance_info (CDI_DOMINATORS); cleanup_tree_cfg (); } + + if (phis_constructed) + add_virtual_phis (); } static void |