#include "tree-inline.h"
#include "varray.h"
#include "timevar.h"
-#include "tree-alias-common.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-ssa-live.h"
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 *);
}
-/* 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
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)
{
edge e;
tree phi, var, tmp;
int x, y;
+ edge_iterator ei;
/* Code cannot be inserted on abnormal edges. Look for all abnormal
edges, and coalesce any PHI results with their arguments across
that edge. */
FOR_EACH_BB (bb)
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
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))
{
internal_error ("SSA corruption");
}
#else
- gcc_assert (phi_ssa_name (tmp));
+ gcc_assert (phi_ssa_name_p (tmp));
#endif
y = var_to_partition (map, tmp);
gcc_assert (x != NO_PARTITION);
static tree_live_info_p
coalesce_ssa_name (var_map map, int flags)
{
- int num, x, i;
+ unsigned num, x, i;
sbitmap live;
tree var, phi;
root_var_p rv;
int p = var_to_partition (map, res);
if (p == NO_PARTITION)
continue;
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
+ for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
{
tree arg = PHI_ARG_DEF (phi, x);
int p2;
basic_block bb;
type_var_p tv;
tree var;
- int x, p, p2;
+ unsigned x, p, p2;
coalesce_list_p cl;
conflict_graph graph;
FOR_EACH_BB (bb)
{
tree phi, arg;
- int p;
+ unsigned p;
+
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
p = var_to_partition (map, PHI_RESULT (phi));
/* Skip virtual PHI nodes. */
- if (p == NO_PARTITION)
+ if (p == (unsigned)NO_PARTITION)
continue;
make_live_on_entry (liveinfo, bb, p);
/* Each argument is a potential copy operation. Add any arguments
which are not coalesced to the result to the coalesce list. */
- for (x = 0; x < PHI_NUM_ARGS (phi); x++)
+ for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
{
arg = PHI_ARG_DEF (phi, x);
if (!phi_ssa_name_p (arg))
continue;
p2 = var_to_partition (map, arg);
- if (p2 == NO_PARTITION)
+ if (p2 == (unsigned)NO_PARTITION)
continue;
if (p != p2)
add_coalesce (cl, p, p2, 1);
tree *ret = NULL;
#ifdef ENABLE_CHECKING
- int x;
+ unsigned x;
for (x = 0; x <= num_var_partitions (t->map); x++)
- if (t->partition_dep_list[x] != NULL)
- gcc_unreachable ();
+ gcc_assert (!t->partition_dep_list[x]);
#endif
while ((p = t->free_list))
}
-/* 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. */
if (version_ref_count (map, def) != 1)
return false;
- /* Assignments to variables assigned to hard registers are not
- replaceable. */
- if (DECL_HARD_REGISTER (SSA_NAME_VAR (def)))
- return false;
-
/* There must be no V_MAY_DEFS. */
if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
return false;
find_replaceable_exprs (var_map map)
{
basic_block bb;
- int i;
+ unsigned i;
temp_expr_table_p table;
tree *ret;
table = new_temp_expr_table (map);
FOR_EACH_BB (bb)
{
+ bitmap_iterator bi;
+
find_replaceable_in_bb (table, bb);
- EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i,
+ EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
{
kill_expr (table, i, false);
- });
+ }
}
ret = free_temp_expr_table (table);
{
tree t = *tp;
- if (TYPE_P (t) || DECL_P (t))
+ if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
{
phi = phi_nodes (bb);
if (phi)
{
- for (e = bb->pred; e; e = e->pred_next)
- eliminate_phi (e, phi_arg_from_edge (phi, e), g);
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ eliminate_phi (e, g);
}
}
delete_elim_graph (g);
+}
+
+
+/* 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 bitmap leader_has_match = NULL;
+static edge leader_match = NULL;
+
+
+/* Pass this function to make_forwarder_block so that all the edges with
+ matching PENDING_STMT lists to 'curr_stmt_list' get redirected. */
+static bool
+same_stmt_list_p (edge e)
+{
+ return (e->aux == (PTR) leader_match) ? true : false;
+}
+
+
+/* Return TRUE if S1 and S2 are equivalent copies. */
+static inline bool
+identical_copies_p (tree s1, tree s2)
+{
+#ifdef ENABLE_CHECKING
+ gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
+ gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
+ gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
+ gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
+#endif
+
+ if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
+ return false;
+
+ s1 = TREE_OPERAND (s1, 1);
+ s2 = TREE_OPERAND (s2, 1);
+
+ if (s1 != s2)
+ return false;
+
+ return true;
+}
+
+
+/* Compare the PENDING_STMT list for two edges, and return true if the lists
+ contain the same sequence of copies. */
+
+static inline bool
+identical_stmt_lists_p (edge e1, edge e2)
+{
+ tree t1 = PENDING_STMT (e1);
+ tree t2 = PENDING_STMT (e2);
+ tree_stmt_iterator tsi1, tsi2;
+
+ gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
+ gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
+
+ for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
+ !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
+ tsi_next (&tsi1), tsi_next (&tsi2))
+ {
+ if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
+ break;
+ }
+
+ if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
+ return false;
+
+ return true;
+}
+
+
+/* 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. */
+
+static bool
+analyze_edges_for_bb (basic_block bb, FILE *debug_file)
+{
+ edge e;
+ edge_iterator ei;
+ int count;
+ unsigned int x;
+ bool have_opportunity;
+ block_stmt_iterator bsi;
+ tree stmt;
+ edge single_edge = NULL;
+ bool is_label;
+
+ count = 0;
+
+ /* Blocks which contain at least one abnormal edge cannot use
+ make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
+ found on edges in these block. */
+ have_opportunity = true;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ have_opportunity = false;
+ break;
+ }
+
+ if (!have_opportunity)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (PENDING_STMT (e))
+ bsi_commit_one_edge_insert (e, NULL);
+ return false;
+ }
+ /* Find out how many edges there are with interesting pending stmts on them.
+ Commit the stmts on edges we are not interested in. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (PENDING_STMT (e))
+ {
+ gcc_assert (!(e->flags & EDGE_ABNORMAL));
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ bsi = bsi_start (e->src);
+ if (!bsi_end_p (bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ bsi_next (&bsi);
+ gcc_assert (stmt != NULL_TREE);
+ is_label = (TREE_CODE (stmt) == LABEL_EXPR);
+ /* Punt if it has non-label stmts, or isn't local. */
+ if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
+ || !bsi_end_p (bsi))
+ {
+ bsi_commit_one_edge_insert (e, NULL);
+ continue;
+ }
+ }
+ }
+ single_edge = e;
+ count++;
+ }
+ }
+
+ /* If there aren't at least 2 edges, no sharing will happen. */
+ if (count < 2)
+ {
+ if (single_edge)
+ bsi_commit_one_edge_insert (single_edge, NULL);
+ return false;
+ }
- /* If any copies were inserted on edges, actually insert them now. */
- bsi_commit_edge_inserts (NULL);
+ /* 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_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
+ block. The leader edge destination is the block which all the other edges
+ with the same stmt list will be redirected to. */
+ have_opportunity = false;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (PENDING_STMT (e))
+ {
+ bool found = false;
+
+ /* Look for the same stmt list in edge leaders list. */
+ for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
+ {
+ edge leader = VARRAY_EDGE (edge_leader, x);
+ if (identical_stmt_lists_p (leader, e))
+ {
+ /* Give this edge the same stmt list pointer. */
+ PENDING_STMT (e) = NULL;
+ e->aux = leader;
+ bitmap_set_bit (leader_has_match, x);
+ have_opportunity = found = true;
+ break;
+ }
+ }
+
+ /* 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));
+ }
+ }
+ }
+
+ /* 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);
+ bitmap_clear (leader_has_match);
+ return false;
+ }
+
+
+ if (debug_file)
+ fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
+ bb->index);
+
+
+ /* 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++)
+ if (bitmap_bit_p (leader_has_match, x))
+ {
+ edge new_edge, leader_edge;
+ block_stmt_iterator bsi;
+ tree curr_stmt_list;
+
+ leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
+
+ /* 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);
+
+ new_edge = make_forwarder_block (leader_edge->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);
+ fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
+ print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
+ }
+
+ FOR_EACH_EDGE (e, ei, new_edge->src->preds)
+ {
+ e->aux = NULL;
+ if (debug_file)
+ fprintf (debug_file, " Edge (%d->%d) lands here.\n",
+ e->src->index, e->dest->index);
+ }
+
+ bsi = bsi_last (leader_edge->dest);
+ bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
+
+ leader_match = NULL;
+ /* We should never get a new block now. */
+ }
+ else
+ {
+ e = VARRAY_EDGE (edge_leader, x);
+ PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
+ bsi_commit_one_edge_insert (e, NULL);
+ }
+
+
+ /* Clear the working data structures. */
+ VARRAY_POP_ALL (edge_leader);
+ VARRAY_POP_ALL (stmt_list);
+ bitmap_clear (leader_has_match);
+
+ return true;
+}
+
+
+/* This function will analyze the insertions which were performed on edges,
+ and decide whether they should be left on that edge, or whether it is more
+ efficient to emit some subset of them in a single block. All stmts are
+ inserted somewhere, and if non-NULL, debug information is printed via
+ DUMP_FILE. */
+
+static void
+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);
+
+ changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
+
+ /* Clear out any tables which were created. */
+ edge_leader = NULL;
+ BITMAP_XFREE (leader_has_match);
+
+ if (changed)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ }
+
+#ifdef ENABLE_CHECKING
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_BB (bb)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on PRED edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ }
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
+ {
+ if (PENDING_STMT (e))
+ error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
+ e->src->index, e->dest->index);
+ }
+ }
+#endif
}
}
}
+ /* If any copies were inserted on edges, analyze and insert them now. */
+ perform_edge_inserts (dump_file);
+
dump_file = save;
}
OSDN Git Service
