/* Tail call optimization on trees.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
This file is part of GCC.
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
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
bb->aux = &bb->aux;
while (1)
- {
+ {
at = SSA_NAME_DEF_STMT (expr);
bb = gimple_bb (at);
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
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;
{
basic_block dest = e->dest;
gimple_stmt_iterator gsi;
-
+
for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
stmt = gsi_stmt (gsi);
/* Ignore labels. */
- if (gimple_code (stmt) == GIMPLE_LABEL)
+ if (gimple_code (stmt) == GIMPLE_LABEL || is_gimple_debug (stmt))
continue;
/* Check for a call. */
return;
}
- /* If the LHS of our call is not just a simple register, we can't
+ /* 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
agsi = gsi;
while (1)
{
+ tree tmp_a = NULL_TREE;
+ tree tmp_m = NULL_TREE;
gsi_next (&agsi);
while (gsi_end_p (agsi))
if (gimple_code (stmt) == GIMPLE_RETURN)
break;
+ if (is_gimple_debug (stmt))
+ continue;
+
if (gimple_code (stmt) != GIMPLE_ASSIGN)
return;
/* This is a gimple assign. */
- if (! process_assignment (stmt, gsi, &m, &a, &ass_var))
+ if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
return;
+
+ 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. */
break;
gcc_assert (!gsi_end_p (gsi));
- add_phi_arg (gsi_stmt (gsi), phi_arg, e);
+ add_phi_arg (gsi_stmt (gsi), phi_arg, e, UNKNOWN_LOCATION);
}
/* Creates a GIMPLE statement which computes the operation specified by
tree node of the statement's result. */
static tree
-adjust_return_value_with_ops (enum tree_code code, const char *label,
+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)
{
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);
return result;
}
-/* Creates a new GIMPLE statement that adjusts the value of accumulator ACC by
+/* 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 void
adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
{
- tree var, a_acc_arg = a_acc, m_acc_arg = m_acc;
+ 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)
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)
phi = gsi_stmt (gsi);
gcc_assert (param == SSA_NAME_VAR (PHI_RESULT (phi)));
- add_phi_arg (phi, arg, e);
+ add_phi_arg (phi, arg, e, gimple_location (stmt));
gsi_next (&gsi);
}
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));
+ 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. */
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));
+ add_phi_arg (phi, new_name, single_pred_edge (first),
+ EXPR_LOCATION (param));
}
phis_constructed = true;
}
return tree_optimize_tail_calls_1 (true);
}
-struct gimple_opt_pass pass_tail_recursion =
+struct gimple_opt_pass pass_tail_recursion =
{
{
GIMPLE_PASS,
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
- 0, /* tv_id */
+ TV_NONE, /* tv_id */
PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
}
};
-struct gimple_opt_pass pass_tail_calls =
+struct gimple_opt_pass pass_tail_calls =
{
{
GIMPLE_PASS,
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 */
OSDN Git Service
