/* Convert a program in SSA form into Normal form.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
Contributed by Andrew Macleod <amacleod@redhat.com>
This file is part of GCC.
#define SSANORM_PERFORM_TER 0x1
#define SSANORM_COMBINE_TEMPS 0x2
-#define SSANORM_REMOVE_ALL_PHIS 0x4
-#define SSANORM_COALESCE_PARTITIONS 0x8
-#define SSANORM_USE_COALESCE_LIST 0x10
+#define SSANORM_COALESCE_PARTITIONS 0x4
/* Used to hold all the components required to do SSA PHI elimination.
The node and pred/succ list is a simple linear list of nodes and
static inline int elim_graph_remove_succ_edge (elim_graph, int);
static inline void eliminate_name (elim_graph, tree);
-static void eliminate_build (elim_graph, basic_block, int);
+static void eliminate_build (elim_graph, basic_block);
static void elim_forward (elim_graph, int);
static int elim_unvisited_predecessor (elim_graph, int);
static void elim_backward (elim_graph, int);
static void elim_create (elim_graph, int);
-static void eliminate_phi (edge, int, elim_graph);
+static void eliminate_phi (edge, elim_graph);
static tree_live_info_p coalesce_ssa_name (var_map, int);
static void assign_vars (var_map);
static bool replace_use_variable (var_map, use_operand_p, tree *);
if (name == NULL)
name = "temp";
tmp = create_tmp_var (type, name);
+
+ if (DECL_DEBUG_EXPR (t) && DECL_DEBUG_EXPR_IS_FROM (t))
+ {
+ DECL_DEBUG_EXPR (tmp) = DECL_DEBUG_EXPR (t);
+ DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
+ }
+ else if (!DECL_IGNORED_P (t))
+ {
+ DECL_DEBUG_EXPR (tmp) = t;
+ DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
+ }
DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
+ DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
add_referenced_tmp_var (tmp);
/* add_referenced_tmp_var will create the annotation and set up some
}
-/* Build elimination graph G for basic block BB on incoming PHI edge I. */
+/* Build elimination graph G for basic block BB on incoming PHI edge
+ G->e. */
static void
-eliminate_build (elim_graph g, basic_block B, int i)
+eliminate_build (elim_graph g, basic_block B)
{
tree phi;
tree T0, Ti;
if (T0 == NULL_TREE)
continue;
- if (PHI_ARG_EDGE (phi, i) == g->e)
- Ti = PHI_ARG_DEF (phi, i);
- else
- {
- /* On rare occasions, a PHI node may not have the arguments
- in the same order as all of the other PHI nodes. If they don't
- match, find the appropriate index here. */
- pi = phi_arg_from_edge (phi, g->e);
- gcc_assert (pi != -1);
- Ti = PHI_ARG_DEF (phi, pi);
- }
+ Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
/* If this argument is a constant, or a SSA_NAME which is being
left in SSA form, just queue a copy to be emitted on this
}
-/* Eliminate all the phi nodes on edge E in graph G. I is the usual PHI
- index that edge E's values are found on. */
+/* Eliminate all the phi nodes on edge E in graph G. */
static void
-eliminate_phi (edge e, int i, elim_graph g)
+eliminate_phi (edge e, elim_graph g)
{
- int num_nodes = 0;
int x;
basic_block B = e->dest;
- gcc_assert (i != -1);
gcc_assert (VARRAY_ACTIVE_SIZE (g->const_copies) == 0);
- /* Abnormal edges already have everything coalesced, or the coalescer
- would have aborted. */
+ /* Abnormal edges already have everything coalesced. */
if (e->flags & EDGE_ABNORMAL)
return;
- num_nodes = num_var_partitions (g->map);
g->e = e;
- eliminate_build (g, B, i);
+ eliminate_build (g, B);
if (elim_graph_size (g) != 0)
{
basic_block bb;
edge e;
tree phi, var, tmp;
- int x, y;
+ int x, y, z;
edge_iterator ei;
/* Code cannot be inserted on abnormal edges. Look for all abnormal
if (x == NO_PARTITION)
continue;
- y = phi_arg_from_edge (phi, e);
- gcc_assert (y != -1);
-
- tmp = PHI_ARG_DEF (phi, y);
+ tmp = PHI_ARG_DEF (phi, e->dest_idx);
#ifdef ENABLE_CHECKING
if (!phi_ssa_name_p (tmp))
{
"ABNORMAL: Coalescing ",
var, " and ", tmp);
}
+ z = var_union (map, var, tmp);
#ifdef ENABLE_CHECKING
- if (var_union (map, var, tmp) == NO_PARTITION)
+ if (z == NO_PARTITION)
{
print_exprs_edge (stderr, e, "\nUnable to coalesce",
partition_to_var (map, x), " and ",
internal_error ("SSA corruption");
}
#else
- gcc_assert (var_union (map, var, tmp) != NO_PARTITION);
+ gcc_assert (z != NO_PARTITION);
#endif
- conflict_graph_merge_regs (graph, x, y);
+ gcc_assert (z == x || z == y);
+ if (z == x)
+ conflict_graph_merge_regs (graph, x, y);
+ else
+ conflict_graph_merge_regs (graph, y, x);
}
}
}
if (num_var_partitions (map) <= 1)
return NULL;
- /* If no preference given, use cheap coalescing of all partitions. */
- if ((flags & (SSANORM_COALESCE_PARTITIONS | SSANORM_USE_COALESCE_LIST)) == 0)
- flags |= SSANORM_COALESCE_PARTITIONS;
-
liveinfo = calculate_live_on_entry (map);
calculate_live_on_exit (liveinfo);
rv = root_var_init (map);
/* Remove single element variable from the list. */
root_var_compact (rv);
- if (flags & SSANORM_USE_COALESCE_LIST)
+ cl = create_coalesce_list (map);
+
+ /* Add all potential copies via PHI arguments to the list. */
+ FOR_EACH_BB (bb)
{
- cl = create_coalesce_list (map);
-
- /* Add all potential copies via PHI arguments to the list. */
- FOR_EACH_BB (bb)
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ tree res = PHI_RESULT (phi);
+ int p = var_to_partition (map, res);
+ if (p == NO_PARTITION)
+ continue;
+ for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
{
- tree res = PHI_RESULT (phi);
- int p = var_to_partition (map, res);
- if (p == NO_PARTITION)
+ tree arg = PHI_ARG_DEF (phi, x);
+ int p2;
+
+ if (TREE_CODE (arg) != SSA_NAME)
continue;
- for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
- {
- tree arg = PHI_ARG_DEF (phi, x);
- int p2;
-
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
- if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
- continue;
- p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
- if (p2 != NO_PARTITION)
- add_coalesce (cl, p, p2, 1);
- }
+ if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
+ continue;
+ p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
+ if (p2 != NO_PARTITION)
+ add_coalesce (cl, p, p2, 1);
}
}
+ }
- /* Coalesce all the result decls together. */
- var = NULL_TREE;
- i = 0;
- for (x = 0; x < num_var_partitions (map); x++)
+ /* Coalesce all the result decls together. */
+ var = NULL_TREE;
+ i = 0;
+ for (x = 0; x < num_var_partitions (map); x++)
+ {
+ tree p = partition_to_var (map, x);
+ if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
{
- tree p = partition_to_var (map, x);
- if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
+ if (var == NULL_TREE)
{
- if (var == NULL_TREE)
- {
- var = p;
- i = x;
- }
- else
- add_coalesce (cl, i, x, 1);
+ var = p;
+ i = x;
}
+ else
+ add_coalesce (cl, i, x, 1);
}
}
dump_var_map (dump_file, map);
/* Coalesce partitions. */
- if (flags & SSANORM_USE_COALESCE_LIST)
- coalesce_tpa_members (rv, graph, map, cl,
- ((dump_flags & TDF_DETAILS) ? dump_file
- : NULL));
+ coalesce_tpa_members (rv, graph, map, cl,
+ ((dump_flags & TDF_DETAILS) ? dump_file
+ : NULL));
-
if (flags & SSANORM_COALESCE_PARTITIONS)
- coalesce_tpa_members (rv, graph, map, NULL,
- ((dump_flags & TDF_DETAILS) ? dump_file
- : NULL));
+ coalesce_tpa_members (rv, graph, map, NULL,
+ ((dump_flags & TDF_DETAILS) ? dump_file
+ : NULL));
if (cl)
delete_coalesce_list (cl);
root_var_delete (rv);
}
}
#endif
- remove_phi_node (phi, NULL_TREE, bb);
+ remove_phi_node (phi, NULL_TREE);
}
}
}
t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
sizeof (value_expr_p));
- t->replaceable = BITMAP_XMALLOC ();
- t->partition_in_use = BITMAP_XMALLOC ();
+ t->replaceable = BITMAP_ALLOC (NULL);
+ t->partition_in_use = BITMAP_ALLOC (NULL);
t->saw_replaceable = false;
t->virtual_partition = num_var_partitions (map);
free (p);
}
- BITMAP_XFREE (t->partition_in_use);
- BITMAP_XFREE (t->replaceable);
+ BITMAP_FREE (t->partition_in_use);
+ BITMAP_FREE (t->replaceable);
free (t->partition_dep_list);
if (t->saw_replaceable)
}
-/* Find VALUE if its in LIST. Return a pointer to the list object if found,
+/* Find VALUE if it's in LIST. Return a pointer to the list object if found,
else return NULL. If LAST_PTR is provided, it will point to the previous
item upon return, or NULL if this is the first item in the list. */
static bool
check_replaceable (temp_expr_table_p tab, tree stmt)
{
- stmt_ann_t ann;
- vuse_optype vuseops;
- def_optype defs;
- use_optype uses;
tree var, def;
- int num_use_ops, version;
+ int version;
var_map map = tab->map;
ssa_op_iter iter;
+ tree call_expr;
if (TREE_CODE (stmt) != MODIFY_EXPR)
return false;
- ann = stmt_ann (stmt);
- defs = DEF_OPS (ann);
-
/* Punt if there is more than 1 def, or more than 1 use. */
- if (NUM_DEFS (defs) != 1)
- return false;
- def = DEF_OP (defs, 0);
- if (version_ref_count (map, def) != 1)
+ def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+ if (!def)
return false;
- /* There must be no V_MAY_DEFS. */
- if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
+ if (version_ref_count (map, def) != 1)
return false;
- /* There must be no V_MUST_DEFS. */
- if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
+ /* There must be no V_MAY_DEFS or V_MUST_DEFS. */
+ if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
return false;
/* Float expressions must go through memory if float-store is on. */
if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
return false;
- uses = USE_OPS (ann);
- num_use_ops = NUM_USES (uses);
- vuseops = VUSE_OPS (ann);
-
- /* Any expression which has no virtual operands and no real operands
- should have been propagated if it's possible to do anything with them.
- If this happens here, it probably exists that way for a reason, so we
- won't touch it. An example is:
- b_4 = &tab
- There are no virtual uses nor any real uses, so we just leave this
- alone to be safe. */
-
- if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
- return false;
+ /* Calls to functions with side-effects cannot be replaced. */
+ if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
+ {
+ int call_flags = call_expr_flags (call_expr);
+ if (TREE_SIDE_EFFECTS (call_expr)
+ && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
+ return false;
+ }
version = SSA_NAME_VERSION (def);
}
/* If there are VUSES, add a dependence on virtual defs. */
- if (NUM_VUSES (vuseops) != 0)
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
{
add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
VIRTUAL_PARTITION (tab));
{
if (tab->version_info[SSA_NAME_VERSION (def)])
{
- /* Mark expression as replaceable unless stmt is volatile. */
- if (!ann->has_volatile_ops)
+ bool same_root_var = false;
+ tree def2;
+ ssa_op_iter iter2;
+
+ /* See if the root variables are the same. If they are, we
+ do not want to do the replacement to avoid problems with
+ code size, see PR tree-optimization/17549. */
+ FOR_EACH_SSA_TREE_OPERAND (def2, stmt, iter2, SSA_OP_DEF)
+ if (SSA_NAME_VAR (def) == SSA_NAME_VAR (def2))
+ {
+ same_root_var = true;
+ break;
+ }
+
+ /* Mark expression as replaceable unless stmt is volatile
+ or DEF sets the same root variable as STMT. */
+ if (!ann->has_volatile_ops && !same_root_var)
mark_replaceable (tab, def);
else
finish_expr (tab, SSA_NAME_VERSION (def), false);
free_value_expr (tab, p);
}
- /* A V_MAY_DEF kills any expression using a virtual operand. */
- if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
- kill_virtual_exprs (tab, true);
-
- /* A V_MUST_DEF kills any expression using a virtual operand. */
- if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
+ /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand. */
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
kill_virtual_exprs (tab, true);
}
}
if (expr[x])
{
stmt = expr[x];
- var = DEF_OP (STMT_DEF_OPS (stmt), 0);
+ var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+ gcc_assert (var != NULL_TREE);
print_generic_expr (f, var, TDF_SLIM);
fprintf (f, " replace with --> ");
print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
{
for (si = bsi_start (bb); !bsi_end_p (si); )
{
- size_t num_uses, num_defs;
- use_optype uses;
- def_optype defs;
tree stmt = bsi_stmt (si);
- use_operand_p use_p;
+ use_operand_p use_p, copy_use_p;
def_operand_p def_p;
- int remove = 0, is_copy = 0;
+ bool remove = false, is_copy = false;
+ int num_uses = 0;
stmt_ann_t ann;
ssa_op_iter iter;
- get_stmt_operands (stmt);
ann = stmt_ann (stmt);
changed = false;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
- is_copy = 1;
+ is_copy = true;
- uses = USE_OPS (ann);
- num_uses = NUM_USES (uses);
+ copy_use_p = NULL_USE_OPERAND_P;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
if (replace_use_variable (map, use_p, values))
- changed = true;
+ changed = true;
+ copy_use_p = use_p;
+ num_uses++;
}
- defs = DEF_OPS (ann);
- num_defs = NUM_DEFS (defs);
+ if (num_uses != 1)
+ is_copy = false;
- /* Mark this stmt for removal if it is the list of replaceable
- expressions. */
- if (values && num_defs == 1)
- {
- tree def = DEF_OP (defs, 0);
- tree val;
- val = values[SSA_NAME_VERSION (def)];
- if (val)
- remove = 1;
- }
- if (!remove)
+ def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
+
+ if (def_p != NULL)
{
- FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+ /* Mark this stmt for removal if it is the list of replaceable
+ expressions. */
+ if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
+ remove = true;
+ else
{
if (replace_def_variable (map, def_p, NULL))
changed = true;
-
/* If both SSA_NAMEs coalesce to the same variable,
mark the now redundant copy for removal. */
- if (is_copy
- && num_uses == 1
- && (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
- remove = 1;
+ if (is_copy)
+ {
+ gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
+ if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
+ remove = true;
+ }
}
- if (changed & !remove)
- modify_stmt (stmt);
}
+ else
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+ if (replace_def_variable (map, def_p, NULL))
+ changed = true;
/* Remove any stmts marked for removal. */
if (remove)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
- eliminate_phi (e, phi_arg_from_edge (phi, e), g);
+ eliminate_phi (e, g);
}
}
}
+DEF_VEC_ALLOC_P(edge,heap);
+
/* These are the local work structures used to determine the best place to
insert the copies that were placed on edges by the SSA->normal pass.. */
-static varray_type edge_leader = NULL;
-static varray_type GTY(()) stmt_list = NULL;
+static VEC(edge,heap) *edge_leader;
+static VEC(tree,heap) *stmt_list;
static bitmap leader_has_match = NULL;
static edge leader_match = NULL;
}
+/* Allocate data structures used in analyze_edges_for_bb. */
+
+static void
+init_analyze_edges_for_bb (void)
+{
+ edge_leader = VEC_alloc (edge, heap, 25);
+ stmt_list = VEC_alloc (tree, heap, 25);
+ leader_has_match = BITMAP_ALLOC (NULL);
+}
+
+
+/* Free data structures used in analyze_edges_for_bb. */
+
+static void
+fini_analyze_edges_for_bb (void)
+{
+ VEC_free (edge, heap, edge_leader);
+ VEC_free (tree, heap, stmt_list);
+ BITMAP_FREE (leader_has_match);
+}
+
+
/* Look at all the incoming edges to block BB, and decide where the best place
to insert the stmts on each edge are, and perform those insertions. Output
- any debug information to DEBUG_FILE. Return true if anything other than a
- standard edge insertion is done. */
+ any debug information to DEBUG_FILE. */
-static bool
+static void
analyze_edges_for_bb (basic_block bb, FILE *debug_file)
{
edge e;
tree stmt;
edge single_edge = NULL;
bool is_label;
+ edge leader;
count = 0;
FOR_EACH_EDGE (e, ei, bb->preds)
if (PENDING_STMT (e))
bsi_commit_one_edge_insert (e, NULL);
- return false;
+ return;
}
/* Find out how many edges there are with interesting pending stmts on them.
Commit the stmts on edges we are not interested in. */
{
if (single_edge)
bsi_commit_one_edge_insert (single_edge, NULL);
- return false;
+ return;
}
/* Ensure that we have empty worklists. */
- if (edge_leader == NULL)
- {
- VARRAY_EDGE_INIT (edge_leader, 25, "edge_leader");
- VARRAY_TREE_INIT (stmt_list, 25, "stmt_list");
- leader_has_match = BITMAP_XMALLOC ();
- }
- else
- {
#ifdef ENABLE_CHECKING
- gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
- gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
- gcc_assert (bitmap_first_set_bit (leader_has_match) == -1);
+ gcc_assert (VEC_length (edge, edge_leader) == 0);
+ gcc_assert (VEC_length (tree, stmt_list) == 0);
+ gcc_assert (bitmap_empty_p (leader_has_match));
#endif
- }
/* Find the "leader" block for each set of unique stmt lists. Preference is
given to FALLTHRU blocks since they would need a GOTO to arrive at another
bool found = false;
/* Look for the same stmt list in edge leaders list. */
- for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
+ for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
{
- edge leader = VARRAY_EDGE (edge_leader, x);
if (identical_stmt_lists_p (leader, e))
{
/* Give this edge the same stmt list pointer. */
/* If no similar stmt list, add this edge to the leader list. */
if (!found)
{
- VARRAY_PUSH_EDGE (edge_leader, e);
- VARRAY_PUSH_TREE (stmt_list, PENDING_STMT (e));
+ VEC_safe_push (edge, heap, edge_leader, e);
+ VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
}
}
}
/* If there are no similar lists, just issue the stmts. */
if (!have_opportunity)
{
- for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
- bsi_commit_one_edge_insert (VARRAY_EDGE (edge_leader, x), NULL);
- VARRAY_POP_ALL (edge_leader);
- VARRAY_POP_ALL (stmt_list);
+ for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
+ bsi_commit_one_edge_insert (leader, NULL);
+ VEC_truncate (edge, edge_leader, 0);
+ VEC_truncate (tree, stmt_list, 0);
bitmap_clear (leader_has_match);
- return false;
+ return;
}
/* For each common list, create a forwarding block and issue the stmt's
in that block. */
- for (x = 0 ; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
+ for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
if (bitmap_bit_p (leader_has_match, x))
{
- edge new_edge, leader_edge;
+ edge new_edge;
block_stmt_iterator bsi;
tree curr_stmt_list;
- leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
+ leader_match = leader;
/* The tree_* cfg manipulation routines use the PENDING_EDGE field
for various PHI manipulations, so it gets cleared whhen calls are
made to make_forwarder_block(). So make sure the edge is clear,
and use the saved stmt list. */
- PENDING_STMT (leader_edge) = NULL;
- leader_edge->aux = leader_edge;
- curr_stmt_list = VARRAY_TREE (stmt_list, x);
+ PENDING_STMT (leader) = NULL;
+ leader->aux = leader;
+ curr_stmt_list = VEC_index (tree, stmt_list, x);
- new_edge = make_forwarder_block (leader_edge->dest, same_stmt_list_p,
+ new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
NULL);
bb = new_edge->dest;
if (debug_file)
{
fprintf (debug_file, "Splitting BB %d for Common stmt list. ",
- leader_edge->dest->index);
+ leader->dest->index);
fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
}
e->src->index, e->dest->index);
}
- bsi = bsi_last (leader_edge->dest);
+ bsi = bsi_last (leader->dest);
bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
leader_match = NULL;
}
else
{
- e = VARRAY_EDGE (edge_leader, x);
- PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
- bsi_commit_one_edge_insert (e, NULL);
+ PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
+ bsi_commit_one_edge_insert (leader, NULL);
}
/* Clear the working data structures. */
- VARRAY_POP_ALL (edge_leader);
- VARRAY_POP_ALL (stmt_list);
+ VEC_truncate (edge, edge_leader, 0);
+ VEC_truncate (tree, stmt_list, 0);
bitmap_clear (leader_has_match);
-
- return true;
}
perform_edge_inserts (FILE *dump_file)
{
basic_block bb;
- bool changed = false;
if (dump_file)
fprintf(dump_file, "Analyzing Edge Insertions.\n");
- FOR_EACH_BB (bb)
- changed |= analyze_edges_for_bb (bb, dump_file);
+ /* analyze_edges_for_bb calls make_forwarder_block, which tries to
+ incrementally update the dominator information. Since we don't
+ need dominator information after this pass, go ahead and free the
+ dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
- changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
+ /* Allocate data structures used in analyze_edges_for_bb. */
+ init_analyze_edges_for_bb ();
- /* Clear out any tables which were created. */
- edge_leader = NULL;
- if (leader_has_match != NULL)
- {
- free (leader_has_match);
- leader_has_match = NULL;
- }
+ FOR_EACH_BB (bb)
+ analyze_edges_for_bb (bb, dump_file);
- if (changed)
- {
- free_dominance_info (CDI_DOMINATORS);
- free_dominance_info (CDI_POST_DOMINATORS);
- }
+ analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
+
+ /* Free data structures used in analyze_edges_for_bb. */
+ fini_analyze_edges_for_bb ();
#ifdef ENABLE_CHECKING
{
for (phi = phi_nodes (bb); phi; phi = next)
{
next = PHI_CHAIN (phi);
- if ((flags & SSANORM_REMOVE_ALL_PHIS)
- || var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
- remove_phi_node (phi, NULL_TREE, bb);
+ remove_phi_node (phi, NULL_TREE);
}
}
+ /* we no longer maintain the SSA operand cache at this point. */
+ fini_ssa_operands ();
+
/* If any copies were inserted on edges, analyze and insert them now. */
perform_edge_inserts (dump_file);
dump_file = save;
}
+/* Search every PHI node for arguments associated with backedges which
+ we can trivially determine will need a copy (the argument is either
+ not an SSA_NAME or the argument has a different underlying variable
+ than the PHI result).
+
+ Insert a copy from the PHI argument to a new destination at the
+ end of the block with the backedge to the top of the loop. Update
+ the PHI argument to reference this new destination. */
+
+static void
+insert_backedge_copies (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree result = PHI_RESULT (phi);
+ tree result_var;
+ int i;
+
+ if (!is_gimple_reg (result))
+ continue;
+
+ result_var = SSA_NAME_VAR (result);
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ tree arg = PHI_ARG_DEF (phi, i);
+ edge e = PHI_ARG_EDGE (phi, i);
+
+ /* If the argument is not an SSA_NAME, then we will
+ need a constant initialization. If the argument is
+ an SSA_NAME with a different underlying variable and
+ we are not combining temporaries, then we will
+ need a copy statement. */
+ if ((e->flags & EDGE_DFS_BACK)
+ && (TREE_CODE (arg) != SSA_NAME
+ || (!flag_tree_combine_temps
+ && SSA_NAME_VAR (arg) != result_var)))
+ {
+ tree stmt, name, last = NULL;
+ block_stmt_iterator bsi;
+
+ bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
+ if (!bsi_end_p (bsi))
+ last = bsi_stmt (bsi);
+
+ /* In theory the only way we ought to get back to the
+ start of a loop should be with a COND_EXPR or GOTO_EXPR.
+ However, better safe than sorry.
+
+ If the block ends with a control statement or
+ something that might throw, then we have to
+ insert this assignment before the last
+ statement. Else insert it after the last statement. */
+ if (last && stmt_ends_bb_p (last))
+ {
+ /* If the last statement in the block is the definition
+ site of the PHI argument, then we can't insert
+ anything after it. */
+ if (TREE_CODE (arg) == SSA_NAME
+ && SSA_NAME_DEF_STMT (arg) == last)
+ continue;
+ }
+
+ /* Create a new instance of the underlying
+ variable of the PHI result. */
+ stmt = build (MODIFY_EXPR, TREE_TYPE (result_var),
+ NULL, PHI_ARG_DEF (phi, i));
+ name = make_ssa_name (result_var, stmt);
+ TREE_OPERAND (stmt, 0) = name;
+
+ /* Insert the new statement into the block and update
+ the PHI node. */
+ if (last && stmt_ends_bb_p (last))
+ bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+ else
+ bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
+ SET_PHI_ARG_DEF (phi, i, name);
+ }
+ }
+ }
+ }
+}
+
/* Take the current function out of SSA form, as described in
R. Morgan, ``Building an Optimizing Compiler'',
Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */
{
var_map map;
int var_flags = 0;
- int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
+ int ssa_flags = 0;
+
+ /* If elimination of a PHI requires inserting a copy on a backedge,
+ then we will have to split the backedge which has numerous
+ undesirable performance effects.
+
+ A significant number of such cases can be handled here by inserting
+ copies into the loop itself. */
+ insert_backedge_copies ();
if (!flag_tree_live_range_split)
ssa_flags |= SSANORM_COALESCE_PARTITIONS;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
- /* Do some cleanups which reduce the amount of data the
- tree->rtl expanders deal with. */
- cfg_remove_useless_stmts ();
-
/* Flush out flow graph and SSA data. */
delete_var_map (map);
/* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
discover_nonconstant_array_refs ();
+
+ in_ssa_p = false;
}