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);
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. */
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. */
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));
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;
}
}
}
+
+ 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 =
OSDN Git Service
