X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-tailcall.c;h=de2a45e949c955a02eb304c036ac55a8f6978ed7;hp=e1c1f672ac6c44ba6b8624f4c27dd533db54e0fd;hb=dd9d9ac28b56faa0c480877b29e1a74fb856214f;hpb=2d1c59766105d5d61f9ec9f79bb87ec1d65e974e diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index e1c1f672ac6..de2a45e949c 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -1,11 +1,12 @@ /* Tail call optimization on trees. - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -14,9 +15,8 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -35,6 +35,7 @@ Boston, MA 02111-1307, USA. */ #include "tree-pass.h" #include "flags.h" #include "langhooks.h" +#include "dbgcnt.h" /* The file implements the tail recursion elimination. It is also used to analyze the tail calls in general, passing the results to the rtl level @@ -64,7 +65,7 @@ Boston, MA 02111-1307, USA. */ return acc; } - To do this, we maintain two accumulators (a_acc and m_acc) that indicate + To do this, we maintain two accumulators (a_acc and m_acc) that indicate when we reach the return x statement, we should return a_acc + x * m_acc instead. They are initially initialized to 0 and 1, respectively, so the semantics of the function is obviously preserved. If we are @@ -78,12 +79,12 @@ Boston, MA 02111-1307, USA. */ 1) Just return x, where x is not in any of the remaining special shapes. We rewrite this to a gimple equivalent of return m_acc * x + a_acc. - + 2) return f (...), where f is the current function, is rewritten in a classical tail-recursion elimination way, into assignment of arguments and jump to the start of the function. Values of the accumulators are unchanged. - + 3) return a + m * f(...), where a and m do not depend on call to f. To preserve the semantics described before we want this to be rewritten in such a way that we finally return @@ -100,11 +101,8 @@ Boston, MA 02111-1307, USA. */ struct tailcall { - /* The block in that the call occur. */ - basic_block call_block; - /* The iterator pointing to the call statement. */ - block_stmt_iterator call_bsi; + gimple_stmt_iterator call_gsi; /* True if it is a call to the current function. */ bool tail_recursion; @@ -132,20 +130,17 @@ static void find_tail_calls (basic_block, struct tailcall **); static bool suitable_for_tail_opt_p (void) { - int i; + referenced_var_iterator rvi; + tree var; - if (current_function_stdarg) + if (cfun->stdarg) return false; - /* No local variable should be call-clobbered. We ignore any kind - of memory tag, as these are not real variables. */ - for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (referenced_vars); i++) + /* No local variable nor structure field should be call-used. */ + FOR_EACH_REFERENCED_VAR (var, rvi) { - tree var = VARRAY_TREE (referenced_vars, i); - - if (!(TREE_STATIC (var) || DECL_EXTERNAL (var)) - && var_ann (var)->mem_tag_kind == NOT_A_TAG - && is_call_clobbered (var)) + if (!is_global_var (var) + && is_call_used (var)) return false; } @@ -159,9 +154,11 @@ suitable_for_tail_opt_p (void) static bool suitable_for_tail_call_opt_p (void) { + tree param; + /* alloca (until we have stack slot life analysis) inhibits sibling call optimizations, but not tail recursion. */ - if (current_function_calls_alloca) + if (cfun->calls_alloca) return false; /* If we are using sjlj exceptions, we may need to add a call to @@ -173,23 +170,32 @@ suitable_for_tail_call_opt_p (void) /* Any function that calls setjmp might have longjmp called from any called function. ??? We really should represent this properly in the CFG so that this needn't be special cased. */ - if (current_function_calls_setjmp) + if (cfun->calls_setjmp) return false; + /* ??? It is OK if the argument of a function is taken in some cases, + but not in all cases. See PR15387 and PR19616. Revisit for 4.1. */ + for (param = DECL_ARGUMENTS (current_function_decl); + param; + param = TREE_CHAIN (param)) + if (TREE_ADDRESSABLE (param)) + return false; + return true; } /* Checks whether the expression EXPR in stmt AT is independent of the - statement pointed by BSI (in a sense that we already know EXPR's value - at BSI). We use the fact that we are only called from the chain of + statement pointed to by GSI (in a sense that we already know EXPR's value + at GSI). We use the fact that we are only called from the chain of basic blocks that have only single successor. Returns the expression - containing the value of EXPR at BSI. */ + containing the value of EXPR at GSI. */ static tree -independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi) +independent_of_stmt_p (tree expr, gimple at, gimple_stmt_iterator gsi) { basic_block bb, call_bb, at_bb; edge e; + edge_iterator ei; if (is_gimple_min_invariant (expr)) return expr; @@ -198,16 +204,16 @@ independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi) return NULL_TREE; /* Mark the blocks in the chain leading to the end. */ - at_bb = bb_for_stmt (at); - call_bb = bb_for_stmt (bsi_stmt (bsi)); - for (bb = call_bb; bb != at_bb; bb = bb->succ->dest) + at_bb = gimple_bb (at); + call_bb = gimple_bb (gsi_stmt (gsi)); + for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) bb->aux = &bb->aux; bb->aux = &bb->aux; while (1) - { + { at = SSA_NAME_DEF_STMT (expr); - bb = bb_for_stmt (at); + bb = gimple_bb (at); /* The default definition or defined before the chain. */ if (!bb || !bb->aux) @@ -215,22 +221,22 @@ independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi) if (bb == call_bb) { - for (; !bsi_end_p (bsi); bsi_next (&bsi)) - if (bsi_stmt (bsi) == at) + for (; !gsi_end_p (gsi); gsi_next (&gsi)) + if (gsi_stmt (gsi) == at) break; - if (!bsi_end_p (bsi)) + if (!gsi_end_p (gsi)) expr = NULL_TREE; break; } - if (TREE_CODE (at) != PHI_NODE) + if (gimple_code (at) != GIMPLE_PHI) { expr = NULL_TREE; break; } - for (e = bb->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, bb->preds) if (e->src->aux) break; gcc_assert (e); @@ -244,34 +250,40 @@ independent_of_stmt_p (tree expr, tree at, block_stmt_iterator bsi) } /* Unmark the blocks. */ - for (bb = call_bb; bb != at_bb; bb = bb->succ->dest) + for (bb = call_bb; bb != at_bb; bb = single_succ (bb)) bb->aux = NULL; bb->aux = NULL; return expr; } -/* Simulates the effect of an assignment of ASS in STMT on the return value - of the tail recursive CALL passed in ASS_VAR. M and A are the - multiplicative and the additive factor for the real return value. */ +/* Simulates the effect of an assignment STMT on the return value of the tail + recursive CALL passed in ASS_VAR. M and A are the multiplicative and the + additive factor for the real return value. */ static bool -process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m, +process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, tree *a, tree *ass_var) { tree op0, op1, non_ass_var; - tree dest = TREE_OPERAND (ass, 0); - tree src = TREE_OPERAND (ass, 1); - enum tree_code code = TREE_CODE (src); - tree src_var = src; + tree dest = gimple_assign_lhs (stmt); + enum tree_code code = gimple_assign_rhs_code (stmt); + enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code); + tree src_var = gimple_assign_rhs1 (stmt); /* See if this is a simple copy operation of an SSA name to the function result. In that case we may have a simple tail call. Ignore type conversions that can never produce extra code between the function call and the function return. */ - STRIP_NOPS (src_var); - if (TREE_CODE (src_var) == SSA_NAME) + if ((rhs_class == GIMPLE_SINGLE_RHS || gimple_assign_cast_p (stmt)) + && (TREE_CODE (src_var) == SSA_NAME)) { + /* Reject a tailcall if the type conversion might need + additional code. */ + if (gimple_assign_cast_p (stmt) + && TYPE_MODE (TREE_TYPE (dest)) != TYPE_MODE (TREE_TYPE (src_var))) + return false; + if (src_var != *ass_var) return false; @@ -279,13 +291,13 @@ process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m, return true; } - if (TREE_CODE_CLASS (code) != '2') + if (rhs_class != GIMPLE_BINARY_RHS) return false; /* Accumulator optimizations will reverse the order of operations. We can only do that for floating-point types if we're assuming that addition and multiplication are associative. */ - if (!flag_unsafe_math_optimizations) + if (!flag_associative_math) if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) return false; @@ -299,8 +311,8 @@ process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m, TODO -- Extend it for cases where the linear transformation of the output is expressed in a more complicated way. */ - op0 = TREE_OPERAND (src, 0); - op1 = TREE_OPERAND (src, 1); + op0 = gimple_assign_rhs1 (stmt); + op1 = gimple_assign_rhs2 (stmt); if (op0 == *ass_var && (non_ass_var = independent_of_stmt_p (op1, stmt, call))) @@ -314,27 +326,17 @@ process_assignment (tree ass, tree stmt, block_stmt_iterator call, tree *m, switch (code) { case PLUS_EXPR: - /* There should be no previous addition. TODO -- it should be fairly - straightforward to lift this restriction -- just allow storing - more complicated expressions in *A, and gimplify it in - adjust_accumulator_values. */ - if (*a) - return false; *a = non_ass_var; *ass_var = dest; return true; case MULT_EXPR: - /* Similar remark applies here. Handling multiplication after addition - is just slightly more complicated -- we need to multiply both *A and - *M. */ - if (*a || *m) - return false; *m = non_ass_var; *ass_var = dest; return true; - /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR). */ + /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR, + POINTER_PLUS_EXPR). */ default: return false; @@ -347,12 +349,14 @@ static tree propagate_through_phis (tree var, edge e) { basic_block dest = e->dest; - tree phi; - - for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) - if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var) - return PHI_RESULT (phi); + gimple_stmt_iterator gsi; + for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple phi = gsi_stmt (gsi); + if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var) + return PHI_RESULT (phi); + } return var; } @@ -362,84 +366,99 @@ propagate_through_phis (tree var, edge e) static void find_tail_calls (basic_block bb, struct tailcall **ret) { - tree ass_var, ret_var, stmt, func, param, args, call = NULL_TREE; - block_stmt_iterator bsi, absi; + tree ass_var = NULL_TREE, ret_var, func, param; + gimple stmt, call = NULL; + gimple_stmt_iterator gsi, agsi; bool tail_recursion; struct tailcall *nw; edge e; tree m, a; basic_block abb; - stmt_ann_t ann; + size_t idx; - if (bb->succ->succ_next) + if (!single_succ_p (bb)) return; - for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) + for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) { - stmt = bsi_stmt (bsi); + stmt = gsi_stmt (gsi); /* Ignore labels. */ - if (TREE_CODE (stmt) == LABEL_EXPR) + if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt)) continue; - get_stmt_operands (stmt); - /* Check for a call. */ - if (TREE_CODE (stmt) == MODIFY_EXPR) - { - ass_var = TREE_OPERAND (stmt, 0); - call = TREE_OPERAND (stmt, 1); - if (TREE_CODE (call) == WITH_SIZE_EXPR) - call = TREE_OPERAND (call, 0); - } - else + if (is_gimple_call (stmt)) { - ass_var = NULL_TREE; call = stmt; + ass_var = gimple_call_lhs (stmt); + break; } - if (TREE_CODE (call) == CALL_EXPR) - break; - - /* If the statement has virtual or volatile operands, fail. */ - ann = stmt_ann (stmt); - if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) - || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) - || NUM_VUSES (VUSE_OPS (ann)) - || ann->has_volatile_ops) + /* If the statement references memory or volatile operands, fail. */ + if (gimple_references_memory_p (stmt) + || gimple_has_volatile_ops (stmt)) return; } - if (bsi_end_p (bsi)) + if (gsi_end_p (gsi)) { + edge_iterator ei; /* Recurse to the predecessors. */ - for (e = bb->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, bb->preds) find_tail_calls (e->src, ret); return; } + /* If the LHS of our call is not just a simple register, we can't + transform this into a tail or sibling call. This situation happens, + in (e.g.) "*p = foo()" where foo returns a struct. In this case + we won't have a temporary here, but we need to carry out the side + effect anyway, so tailcall is impossible. + + ??? In some situations (when the struct is returned in memory via + invisible argument) we could deal with this, e.g. by passing 'p' + itself as that argument to foo, but it's too early to do this here, + and expand_call() will not handle it anyway. If it ever can, then + we need to revisit this here, to allow that situation. */ + if (ass_var && !is_gimple_reg (ass_var)) + return; + /* We found the call, check whether it is suitable. */ tail_recursion = false; - func = get_callee_fndecl (call); + func = gimple_call_fndecl (call); if (func == current_function_decl) { - for (param = DECL_ARGUMENTS (func), args = TREE_OPERAND (call, 1); - param && args; - param = TREE_CHAIN (param), args = TREE_CHAIN (args)) + tree arg; + for (param = DECL_ARGUMENTS (func), idx = 0; + param && idx < gimple_call_num_args (call); + param = TREE_CHAIN (param), idx ++) { - tree arg = TREE_VALUE (args); - if (param != arg - /* Make sure there are no problems with copying. Note we must + arg = gimple_call_arg (call, idx); + if (param != arg) + { + /* Make sure there are no problems with copying. The parameter have a copyable type and the two arguments must have reasonably equivalent types. The latter requirement could be relaxed if we emitted a suitable type conversion statement. */ - && (!is_gimple_reg_type (TREE_TYPE (param)) - || !lang_hooks.types_compatible_p (TREE_TYPE (param), - TREE_TYPE (arg)))) - break; + if (!is_gimple_reg_type (TREE_TYPE (param)) + || !useless_type_conversion_p (TREE_TYPE (param), + TREE_TYPE (arg))) + break; + + /* The parameter should be a real operand, so that phi node + created for it at the start of the function has the meaning + of copying the value. This test implies is_gimple_reg_type + from the previous condition, however this one could be + relaxed by being more careful with copying the new value + of the parameter (emitting appropriate GIMPLE_ASSIGN and + updating the virtual operands). */ + if (!is_gimple_reg (param)) + break; + } } - if (!args && !param) + if (idx == gimple_call_num_args (call) && !param) tail_recursion = true; } @@ -451,49 +470,60 @@ find_tail_calls (basic_block bb, struct tailcall **ret) a = NULL_TREE; abb = bb; - absi = bsi; + agsi = gsi; while (1) { - bsi_next (&absi); + tree tmp_a = NULL_TREE; + tree tmp_m = NULL_TREE; + gsi_next (&agsi); - while (bsi_end_p (absi)) + while (gsi_end_p (agsi)) { - ass_var = propagate_through_phis (ass_var, abb->succ); - abb = abb->succ->dest; - absi = bsi_start (abb); + ass_var = propagate_through_phis (ass_var, single_succ_edge (abb)); + abb = single_succ (abb); + agsi = gsi_start_bb (abb); } - stmt = bsi_stmt (absi); + stmt = gsi_stmt (agsi); - if (TREE_CODE (stmt) == LABEL_EXPR) + if (gimple_code (stmt) == GIMPLE_LABEL) continue; - if (TREE_CODE (stmt) == RETURN_EXPR) + if (gimple_code (stmt) == GIMPLE_RETURN) break; - if (TREE_CODE (stmt) != MODIFY_EXPR) - return; + if (is_gimple_debug (stmt)) + continue; - if (!process_assignment (stmt, stmt, bsi, &m, &a, &ass_var)) + if (gimple_code (stmt) != GIMPLE_ASSIGN) return; - } - /* See if this is a tail call we can handle. */ - ret_var = TREE_OPERAND (stmt, 0); - if (ret_var - && TREE_CODE (ret_var) == MODIFY_EXPR) - { - tree ret_op = TREE_OPERAND (ret_var, 1); - STRIP_NOPS (ret_op); - if (!tail_recursion - && TREE_CODE (ret_op) != SSA_NAME) + /* This is a gimple assign. */ + if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var)) return; - if (!process_assignment (ret_var, stmt, bsi, &m, &a, &ass_var)) - return; - ret_var = TREE_OPERAND (ret_var, 0); + if (tmp_a) + { + if (a) + a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a); + else + a = tmp_a; + } + if (tmp_m) + { + if (m) + m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m); + else + m = tmp_m; + + if (a) + a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m); + } } + /* See if this is a tail call we can handle. */ + ret_var = gimple_return_retval (stmt); + /* We may proceed if there either is no return value, or the return value is identical to the call's return. */ if (ret_var @@ -505,10 +535,9 @@ find_tail_calls (basic_block bb, struct tailcall **ret) if (!tail_recursion && (m || a)) return; - nw = xmalloc (sizeof (struct tailcall)); + nw = XNEW (struct tailcall); - nw->call_block = bb; - nw->call_bsi = bsi; + nw->call_gsi = gsi; nw->tail_recursion = tail_recursion; @@ -519,16 +548,81 @@ find_tail_calls (basic_block bb, struct tailcall **ret) *ret = nw; } -/* Adjust the accumulator values according to A and M after BSI, and update - the phi nodes on edge BACK. */ +/* Helper to insert PHI_ARGH to the phi of VAR in the destination of edge E. */ static void -adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back) +add_successor_phi_arg (edge e, tree var, tree phi_arg) +{ + gimple_stmt_iterator gsi; + + for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) + if (PHI_RESULT (gsi_stmt (gsi)) == var) + break; + + gcc_assert (!gsi_end_p (gsi)); + add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION); +} + +/* Creates a GIMPLE statement which computes the operation specified by + CODE, OP0 and OP1 to a new variable with name LABEL and inserts the + statement in the position specified by GSI and UPDATE. Returns the + tree node of the statement's result. */ + +static tree +adjust_return_value_with_ops (enum tree_code code, const char *label, + tree op0, tree op1, gimple_stmt_iterator gsi, + enum gsi_iterator_update update) { - tree stmt, var, phi, tmp; + tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); - tree a_acc_arg = a_acc, m_acc_arg = m_acc; + tree tmp = create_tmp_var (ret_type, label); + gimple stmt = gimple_build_assign_with_ops (code, tmp, op0, op1); + tree result; + + if (TREE_CODE (ret_type) == COMPLEX_TYPE + || TREE_CODE (ret_type) == VECTOR_TYPE) + DECL_GIMPLE_REG_P (tmp) = 1; + add_referenced_var (tmp); + result = make_ssa_name (tmp, stmt); + gimple_assign_set_lhs (stmt, result); + update_stmt (stmt); + gsi_insert_before (&gsi, stmt, update); + return result; +} + +/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by + the computation specified by CODE and OP1 and insert the statement + at the position specified by GSI as a new statement. Returns new SSA name + of updated accumulator. */ + +static tree +update_accumulator_with_ops (enum tree_code code, tree acc, tree op1, + gimple_stmt_iterator gsi) +{ + gimple stmt = gimple_build_assign_with_ops (code, SSA_NAME_VAR (acc), acc, + op1); + tree var = make_ssa_name (SSA_NAME_VAR (acc), stmt); + gimple_assign_set_lhs (stmt, var); + update_stmt (stmt); + gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); + return var; +} +/* Adjust the accumulator values according to A and M after GSI, and update + the phi nodes on edge BACK. */ + +static void +adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back) +{ + tree var, a_acc_arg, m_acc_arg; + + if (m) + m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT); + if (a) + a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT); + + a_acc_arg = a_acc; + m_acc_arg = m_acc; if (a) { if (m_acc) @@ -536,56 +630,23 @@ adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back) if (integer_onep (a)) var = m_acc; else - { - stmt = build (MODIFY_EXPR, ret_type, NULL_TREE, - build (MULT_EXPR, ret_type, m_acc, a)); - - tmp = create_tmp_var (ret_type, "acc_tmp"); - add_referenced_tmp_var (tmp); - - var = make_ssa_name (tmp, stmt); - TREE_OPERAND (stmt, 0) = var; - bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); - } + var = adjust_return_value_with_ops (MULT_EXPR, "acc_tmp", m_acc, + a, gsi, GSI_NEW_STMT); } else var = a; - stmt = build (MODIFY_EXPR, ret_type, NULL_TREE, - build (PLUS_EXPR, ret_type, a_acc, var)); - var = make_ssa_name (SSA_NAME_VAR (a_acc), stmt); - TREE_OPERAND (stmt, 0) = var; - bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); - a_acc_arg = var; + a_acc_arg = update_accumulator_with_ops (PLUS_EXPR, a_acc, var, gsi); } if (m) - { - stmt = build (MODIFY_EXPR, ret_type, NULL_TREE, - build (MULT_EXPR, ret_type, m_acc, m)); - var = make_ssa_name (SSA_NAME_VAR (m_acc), stmt); - TREE_OPERAND (stmt, 0) = var; - bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); - m_acc_arg = var; - } + m_acc_arg = update_accumulator_with_ops (MULT_EXPR, m_acc, m, gsi); if (a_acc) - { - for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi)) - if (PHI_RESULT (phi) == a_acc) - break; - - add_phi_arg (&phi, a_acc_arg, back); - } + add_successor_phi_arg (back, a_acc, a_acc_arg); if (m_acc) - { - for (phi = phi_nodes (back->dest); phi; phi = PHI_CHAIN (phi)) - if (PHI_RESULT (phi) == m_acc) - break; - - add_phi_arg (&phi, m_acc_arg, back); - } + add_successor_phi_arg (back, m_acc, m_acc_arg); } /* Adjust value of the return at the end of BB according to M and A @@ -594,56 +655,66 @@ adjust_accumulator_values (block_stmt_iterator bsi, tree m, tree a, edge back) static void adjust_return_value (basic_block bb, tree m, tree a) { - tree ret_stmt = last_stmt (bb), ret_var, var, stmt, tmp; - tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); - block_stmt_iterator bsi = bsi_last (bb); + tree retval; + gimple ret_stmt = gimple_seq_last_stmt (bb_seq (bb)); + gimple_stmt_iterator gsi = gsi_last_bb (bb); - gcc_assert (TREE_CODE (ret_stmt) == RETURN_EXPR); + gcc_assert (gimple_code (ret_stmt) == GIMPLE_RETURN); - ret_var = TREE_OPERAND (ret_stmt, 0); - if (!ret_var) + retval = gimple_return_retval (ret_stmt); + if (!retval || retval == error_mark_node) return; - if (TREE_CODE (ret_var) == MODIFY_EXPR) - { - ret_var->common.ann = (tree_ann_t) stmt_ann (ret_stmt); - bsi_replace (&bsi, ret_var, true); - SSA_NAME_DEF_STMT (TREE_OPERAND (ret_var, 0)) = ret_var; - ret_var = TREE_OPERAND (ret_var, 0); - ret_stmt = build1 (RETURN_EXPR, TREE_TYPE (ret_stmt), ret_var); - bsi_insert_after (&bsi, ret_stmt, BSI_NEW_STMT); - } - if (m) - { - stmt = build (MODIFY_EXPR, ret_type, NULL_TREE, - build (MULT_EXPR, ret_type, m_acc, ret_var)); - - tmp = create_tmp_var (ret_type, "acc_tmp"); - add_referenced_tmp_var (tmp); + retval = adjust_return_value_with_ops (MULT_EXPR, "mul_tmp", m_acc, retval, + gsi, GSI_SAME_STMT); + if (a) + retval = adjust_return_value_with_ops (PLUS_EXPR, "acc_tmp", a_acc, retval, + gsi, GSI_SAME_STMT); + gimple_return_set_retval (ret_stmt, retval); + update_stmt (ret_stmt); +} - var = make_ssa_name (tmp, stmt); - TREE_OPERAND (stmt, 0) = var; - bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); +/* Subtract COUNT and FREQUENCY from the basic block and it's + outgoing edge. */ +static void +decrease_profile (basic_block bb, gcov_type count, int frequency) +{ + edge e; + bb->count -= count; + if (bb->count < 0) + bb->count = 0; + bb->frequency -= frequency; + if (bb->frequency < 0) + bb->frequency = 0; + if (!single_succ_p (bb)) + { + gcc_assert (!EDGE_COUNT (bb->succs)); + return; } - else - var = ret_var; + e = single_succ_edge (bb); + e->count -= count; + if (e->count < 0) + e->count = 0; +} - if (a) - { - stmt = build (MODIFY_EXPR, ret_type, NULL_TREE, - build (PLUS_EXPR, ret_type, a_acc, var)); +/* Returns true if argument PARAM of the tail recursive call needs to be copied + when the call is eliminated. */ - tmp = create_tmp_var (ret_type, "acc_tmp"); - add_referenced_tmp_var (tmp); +static bool +arg_needs_copy_p (tree param) +{ + tree def; - var = make_ssa_name (tmp, stmt); - TREE_OPERAND (stmt, 0) = var; - bsi_insert_before (&bsi, stmt, BSI_SAME_STMT); - } + if (!is_gimple_reg (param) || !var_ann (param)) + return false; + + /* Parameters that are only defined but never used need not be copied. */ + def = gimple_default_def (cfun, param); + if (!def) + return false; - TREE_OPERAND (ret_stmt, 0) = var; - modify_stmt (ret_stmt); + return true; } /* Eliminates tail call described by T. TMP_VARS is a list of @@ -652,134 +723,125 @@ adjust_return_value (basic_block bb, tree m, tree a) static void eliminate_tail_call (struct tailcall *t) { - tree param, stmt, args, rslt, call; + tree param, rslt; + gimple stmt, call; + tree arg; + size_t idx; basic_block bb, first; edge e; - tree phi; - stmt_ann_t ann; - v_may_def_optype v_may_defs; - unsigned i; - block_stmt_iterator bsi; + gimple phi; + gimple_stmt_iterator gsi; + gimple orig_stmt; - stmt = bsi_stmt (t->call_bsi); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); - bb = t->call_block; + stmt = orig_stmt = gsi_stmt (t->call_gsi); + bb = gsi_bb (t->call_gsi); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Eliminated tail recursion in bb %d : ", bb->index); - print_generic_stmt (dump_file, stmt, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); fprintf (dump_file, "\n"); } - if (TREE_CODE (stmt) == MODIFY_EXPR) - stmt = TREE_OPERAND (stmt, 1); + gcc_assert (is_gimple_call (stmt)); - first = ENTRY_BLOCK_PTR->succ->dest; + first = single_succ (ENTRY_BLOCK_PTR); - /* Remove the code after call_bsi that will become unreachable. The + /* Remove the code after call_gsi that will become unreachable. The possibly unreachable code in other blocks is removed later in cfg cleanup. */ - bsi = t->call_bsi; - bsi_next (&bsi); - while (!bsi_end_p (bsi)) + gsi = t->call_gsi; + gsi_next (&gsi); + while (!gsi_end_p (gsi)) { - tree t = bsi_stmt (bsi); + gimple t = gsi_stmt (gsi); /* Do not remove the return statement, so that redirect_edge_and_branch sees how the block ends. */ - if (TREE_CODE (t) == RETURN_EXPR) + if (gimple_code (t) == GIMPLE_RETURN) break; - bsi_remove (&bsi); + gsi_remove (&gsi, true); release_defs (t); } + /* Number of executions of function has reduced by the tailcall. */ + e = single_succ_edge (gsi_bb (t->call_gsi)); + decrease_profile (EXIT_BLOCK_PTR, e->count, EDGE_FREQUENCY (e)); + decrease_profile (ENTRY_BLOCK_PTR, e->count, EDGE_FREQUENCY (e)); + if (e->dest != EXIT_BLOCK_PTR) + decrease_profile (e->dest, e->count, EDGE_FREQUENCY (e)); + /* Replace the call by a jump to the start of function. */ - e = redirect_edge_and_branch (t->call_block->succ, first); + e = redirect_edge_and_branch (single_succ_edge (gsi_bb (t->call_gsi)), + first); gcc_assert (e); - PENDING_STMT (e) = NULL_TREE; + PENDING_STMT (e) = NULL; - /* 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); + idx = 0, gsi = gsi_start_phis (first); param; - param = TREE_CHAIN (param), - args = TREE_CHAIN (args)) + param = TREE_CHAIN (param), idx++) { - - 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; - add_phi_arg (&phi, TREE_VALUE (args), e); - } - - /* Add phi nodes for the call clobbered variables. */ - v_may_defs = V_MAY_DEF_OPS (ann); - for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) - { - param = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i)); - for (phi = phi_nodes (first); phi; phi = PHI_CHAIN (phi)) - if (param == SSA_NAME_VAR (PHI_RESULT (phi))) - break; - - if (!phi) - { - tree name = var_ann (param)->default_def; - 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)); + arg = gimple_call_arg (stmt, idx); + phi = gsi_stmt (gsi); + gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi))); - var_ann (param)->default_def = new_name; - phi = create_phi_node (name, first); - SSA_NAME_DEF_STMT (name) = phi; - add_phi_arg (&phi, new_name, ENTRY_BLOCK_PTR->succ); - - /* 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 (!first->pred->pred_next->pred_next); - } - - add_phi_arg (&phi, V_MAY_DEF_OP (v_may_defs, i), e); + add_phi_arg (phi, arg, e, gimple_location (stmt)); + gsi_next (&gsi); } /* Update the values of accumulators. */ - adjust_accumulator_values (t->call_bsi, t->mult, t->add, e); + adjust_accumulator_values (t->call_gsi, t->mult, t->add, e); - call = bsi_stmt (t->call_bsi); - if (TREE_CODE (call) == MODIFY_EXPR) + call = gsi_stmt (t->call_gsi); + rslt = gimple_call_lhs (call); + if (rslt != NULL_TREE) { - rslt = TREE_OPERAND (call, 0); - /* Result of the call will no longer be defined. So adjust the SSA_NAME_DEF_STMT accordingly. */ - SSA_NAME_DEF_STMT (rslt) = build_empty_stmt (); + SSA_NAME_DEF_STMT (rslt) = gimple_build_nop (); } - bsi_remove (&t->call_bsi); + gsi_remove (&t->call_gsi, true); 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) && gimple_default_def (cfun, var) != NULL_TREE) + mark_sym_for_renaming (var); + } +} + /* Optimizes the tailcall described by T. If OPT_TAILCALLS is true, also mark the tailcalls for the sibcall optimization. */ @@ -794,47 +856,72 @@ optimize_tail_call (struct tailcall *t, bool opt_tailcalls) if (opt_tailcalls) { - tree stmt = bsi_stmt (t->call_bsi); + gimple stmt = gsi_stmt (t->call_gsi); - stmt = get_call_expr_in (stmt); - CALL_EXPR_TAILCALL (stmt) = 1; + gimple_call_set_tail (stmt, true); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Found tail call "); - print_generic_expr (dump_file, stmt, dump_flags); - fprintf (dump_file, " in bb %i\n", t->call_block->index); + print_gimple_stmt (dump_file, stmt, 0, dump_flags); + fprintf (dump_file, " in bb %i\n", (gsi_bb (t->call_gsi))->index); } } return false; } +/* Creates a tail-call accumulator of the same type as the return type of the + current function. LABEL is the name used to creating the temporary + variable for the accumulator. The accumulator will be inserted in the + phis of a basic block BB with single predecessor with an initial value + INIT converted to the current function return type. */ + +static tree +create_tailcall_accumulator (const char *label, basic_block bb, tree init) +{ + tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); + tree tmp = create_tmp_var (ret_type, label); + gimple phi; + + if (TREE_CODE (ret_type) == COMPLEX_TYPE + || TREE_CODE (ret_type) == VECTOR_TYPE) + DECL_GIMPLE_REG_P (tmp) = 1; + add_referenced_var (tmp); + phi = create_phi_node (tmp, bb); + /* RET_TYPE can be a float when -ffast-maths is enabled. */ + add_phi_arg (phi, fold_convert (ret_type, init), single_pred_edge (bb), + UNKNOWN_LOCATION); + return PHI_RESULT (phi); +} + /* Optimizes tail calls in the function, turning the tail recursion into iteration. */ -static void +static unsigned int tree_optimize_tail_calls_1 (bool opt_tailcalls) { edge e; bool phis_constructed = false; struct tailcall *tailcalls = NULL, *act, *next; bool changed = false; - basic_block first = ENTRY_BLOCK_PTR->succ->dest; - tree stmt, param, ret_type, tmp, phi; + basic_block first = single_succ (ENTRY_BLOCK_PTR); + tree param; + gimple stmt; + edge_iterator ei; if (!suitable_for_tail_opt_p ()) - return; + return 0; if (opt_tailcalls) opt_tailcalls = suitable_for_tail_call_opt_p (); - for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) { /* Only traverse the normal exits, i.e. those that end with return statement. */ stmt = last_stmt (e->src); if (stmt - && TREE_CODE (stmt) == RETURN_EXPR) + && gimple_code (stmt) == GIMPLE_RETURN) find_tail_calls (e->src, &tailcalls); } @@ -847,55 +934,38 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) if (!phis_constructed) { - /* Ensure that there is only one predecessor of the block. */ - if (first->pred->pred_next) - first = split_edge (ENTRY_BLOCK_PTR->succ); + /* Ensure that there is only one predecessor of the block + or if there are existing degenerate PHI nodes. */ + if (!single_pred_p (first) + || !gimple_seq_empty_p (phi_nodes (first))) + first = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); /* Copy the args if needed. */ for (param = DECL_ARGUMENTS (current_function_decl); param; param = TREE_CHAIN (param)) - if (var_ann (param) - /* Also parameters that are only defined but never used need not - be copied. */ - && (var_ann (param)->default_def - && TREE_CODE (var_ann (param)->default_def) == SSA_NAME)) - { - tree name = var_ann (param)->default_def; - tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); - tree phi; - - var_ann (param)->default_def = new_name; - phi = create_phi_node (name, first); - SSA_NAME_DEF_STMT (name) = phi; - add_phi_arg (&phi, new_name, first->pred); - } + if (arg_needs_copy_p (param)) + { + tree name = gimple_default_def (cfun, param); + tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT (name)); + gimple 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), + EXPR_LOCATION (param)); + } phis_constructed = true; } if (act->add && !a_acc) - { - ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); - - tmp = create_tmp_var (ret_type, "add_acc"); - add_referenced_tmp_var (tmp); - - phi = create_phi_node (tmp, first); - add_phi_arg (&phi, build_int_cst (ret_type, 0), first->pred); - a_acc = PHI_RESULT (phi); - } + a_acc = create_tailcall_accumulator ("add_acc", first, + integer_zero_node); if (act->mult && !m_acc) - { - ret_type = TREE_TYPE (DECL_RESULT (current_function_decl)); - - tmp = create_tmp_var (ret_type, "mult_acc"); - add_referenced_tmp_var (tmp); - - phi = create_phi_node (tmp, first); - add_phi_arg (&phi, build_int_cst (ret_type, 1), first->pred); - m_acc = PHI_RESULT (phi); - } + m_acc = create_tailcall_accumulator ("mult_acc", first, + integer_one_node); } for (; tailcalls; tailcalls = next) @@ -908,71 +978,78 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls) if (a_acc || m_acc) { /* Modify the remaining return statements. */ - for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) { stmt = last_stmt (e->src); if (stmt - && TREE_CODE (stmt) == RETURN_EXPR) + && gimple_code (stmt) == GIMPLE_RETURN) adjust_return_value (e->src, m_acc, a_acc); } } if (changed) - { - free_dominance_info (CDI_DOMINATORS); - cleanup_tree_cfg (); - } + free_dominance_info (CDI_DOMINATORS); + + if (phis_constructed) + add_virtual_phis (); + if (changed) + return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals; + return 0; } -static void +static unsigned int execute_tail_recursion (void) { - tree_optimize_tail_calls_1 (false); + return tree_optimize_tail_calls_1 (false); } static bool gate_tail_calls (void) { - return flag_optimize_sibling_calls != 0; + return flag_optimize_sibling_calls != 0 && dbg_cnt (tail_call); } -static void +static unsigned int execute_tail_calls (void) { - tree_optimize_tail_calls_1 (true); + return tree_optimize_tail_calls_1 (true); } -struct tree_opt_pass pass_tail_recursion = +struct gimple_opt_pass pass_tail_recursion = { + { + GIMPLE_PASS, "tailr", /* name */ - NULL, /* gate */ + gate_tail_calls, /* gate */ execute_tail_recursion, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - 0, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + TV_NONE, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + } }; -struct tree_opt_pass pass_tail_calls = +struct gimple_opt_pass pass_tail_calls = { + { + GIMPLE_PASS, "tailc", /* name */ gate_tail_calls, /* gate */ execute_tail_calls, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - 0, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + TV_NONE, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ - 0 /* letter */ + TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ + } };