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. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
static bool
suitable_for_tail_opt_p (void)
{
- int i;
+ referenced_var_iterator rvi;
+ tree var;
if (current_function_stdarg)
return false;
/* No local variable nor structure field should be call-clobbered. We
ignore any kind of memory tag, as these are not real variables. */
- for (i = 0; i < (int) num_referenced_vars; i++)
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = VEC_index (tree, referenced_vars, i);
- if (!(TREE_STATIC (var) || DECL_EXTERNAL (var))
- && (var_ann (var)->mem_tag_kind == NOT_A_TAG
- || var_ann (var)->mem_tag_kind == STRUCT_FIELD)
+ if (!is_global_var (var)
+ && (!MTAG_P (var) || TREE_CODE (var) == STRUCT_FIELD_TAG)
&& is_call_clobbered (var))
return false;
}
}
/* 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
+ statement pointed to 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
basic blocks that have only single successor. Returns the expression
containing the value of EXPR at BSI. */
if (!tail_recursion && (m || a))
return;
- nw = xmalloc (sizeof (struct tailcall));
+ nw = XNEW (struct tailcall);
nw->call_block = bb;
nw->call_bsi = bsi;
var = m_acc;
else
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (MULT_EXPR, ret_type, m_acc, a));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (MULT_EXPR, ret_type, m_acc, a));
tmp = create_tmp_var (ret_type, "acc_tmp");
- add_referenced_tmp_var (tmp);
+ add_referenced_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
else
var = a;
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (PLUS_EXPR, ret_type, a_acc, var));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (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);
if (m)
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (MULT_EXPR, ret_type, m_acc, m));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (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);
if (m)
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (MULT_EXPR, ret_type, m_acc, ret_var));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (MULT_EXPR, ret_type, m_acc, ret_var));
tmp = create_tmp_var (ret_type, "acc_tmp");
- add_referenced_tmp_var (tmp);
+ add_referenced_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
if (a)
{
- stmt = build (MODIFY_EXPR, ret_type, NULL_TREE,
- build (PLUS_EXPR, ret_type, a_acc, var));
+ stmt = build2 (MODIFY_EXPR, ret_type, NULL_TREE,
+ build2 (PLUS_EXPR, ret_type, a_acc, var));
tmp = create_tmp_var (ret_type, "acc_tmp");
- add_referenced_tmp_var (tmp);
+ add_referenced_var (tmp);
var = make_ssa_name (tmp, stmt);
TREE_OPERAND (stmt, 0) = var;
update_stmt (ret_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;
+ }
+ e = single_succ_edge (bb);
+ e->count -= count;
+ if (e->count < 0)
+ 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. */
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);
if (TREE_CODE (t) == RETURN_EXPR)
break;
- bsi_remove (&bsi);
+ bsi_remove (&bsi, true);
release_defs (t);
}
+ /* Number of executions of function has reduced by the tailcall. */
+ e = single_succ_edge (t->call_block);
+ 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 (single_succ_edge (t->call_block), first);
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 = 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));
-
- 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, 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. */
SSA_NAME_DEF_STMT (rslt) = build_empty_stmt ();
}
- bsi_remove (&t->call_bsi);
+ bsi_remove (&t->call_bsi, 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) && 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. */
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. */
- && (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, 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;
}
ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
tmp = create_tmp_var (ret_type, "add_acc");
- add_referenced_tmp_var (tmp);
+ add_referenced_var (tmp);
phi = create_phi_node (tmp, first);
add_phi_arg (phi,
ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
tmp = create_tmp_var (ret_type, "mult_acc");
- add_referenced_tmp_var (tmp);
+ add_referenced_var (tmp);
phi = create_phi_node (tmp, first);
add_phi_arg (phi,
}
}
+
+ 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;
free_dominance_info (CDI_DOMINATORS);
cleanup_tree_cfg ();
}
+
+ if (phis_constructed)
+ add_virtual_phis ();
}
-static void
+static unsigned int
execute_tail_recursion (void)
{
tree_optimize_tail_calls_1 (false);
+ return 0;
}
static bool
return flag_optimize_sibling_calls != 0;
}
-static void
+static unsigned int
execute_tail_calls (void)
{
tree_optimize_tail_calls_1 (true);
+ return 0;
}
struct tree_opt_pass pass_tail_recursion =
{
"tailr", /* name */
- NULL, /* gate */
+ gate_tail_calls, /* gate */
execute_tail_recursion, /* execute */
NULL, /* sub */
NULL, /* next */
OSDN Git Service
