This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tcb][Bug tree-optimization/16447] Patch for better out-of-ssacode insertion
- From: Andrew MacLeod <amacleod at redhat dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 06 Oct 2004 08:47:43 -0400
- Subject: [tcb][Bug tree-optimization/16447] Patch for better out-of-ssacode insertion
The following patch implements stmt sharing in the SSA->normal pass.
When the same copies are inserted on more than one incoming edge, we
issue the stmts into a block, and redirect all the edges which had those
stmts to the new block.
This problem is documented in bugzilla bug 16447.
bootstrapped and no new regressions on i686-pc-linux-gnu.
Compile time impact is negligible.
Checked into the tcb branch. I imagine this is too late for 4.0, so 4.1
it is.
Andrew
The test case there use to generate:
------------------------
# VUSE <regclass_map_28>;
D.16579 = regclass_map[D.16577];
if (D.16579 - 1 <= 3) goto <L73>; else goto <L26>;
<L73>:;
D.16562 = 1;
goto <bb 26> (<L35>);
<L26>:;
if (D.16579 == 7) goto <L74>; else goto <L27>;
<L74>:;
D.16562 = 1;
goto <bb 26> (<L35>);
<L27>:;
if (D.16579 == 5) goto <L75>; else goto <L28>;
<L75>:;
D.16562 = 1;
goto <bb 26> (<L35>);
<L28>:;
if (D.16579 == 6) goto <L76>; else goto <L29>;
<L76>:;
D.16562 = 1;
goto <bb 26> (<L35>);
<L29>:;
if (D.16579 == 13) goto <L77>; else goto <L30>;
<L77>:;
D.16562 = 1;
goto <bb 26> (<L35>);
<L30>:;
if (D.16579 == 14) goto <L31>; else goto <L78>;
<L78>:;
D.16562 = 0;
goto <bb 26> (<L35>);
<L31>:;
D.16562 = 1;
<L35>:;
return D.16562;
------------------------
And now it generates:
------------------------
D.16579 = regclass_map[D.16577];
if (D.16579 - 1 <= 3) goto <L61>; else goto <L26>;
<L26>:;
if (D.16579 == 7) goto <L61>; else goto <L27>;
<L27>:;
if (D.16579 == 5) goto <L61>; else goto <L28>;
<L28>:;
if (D.16579 == 6) goto <L61>; else goto <L29>;
<L29>:;
if (D.16579 == 13) goto <L61>; else goto <L30>;
<L30>:;
if (D.16579 == 14) goto <L61>; else goto <L35>;
<L35>:;
D.16562 = 0;
goto <bb 27> (<L62>);
<L61>:;
D.16562 = 1;
<L62>:;
return D.16562;
------------------------
2004-10-06 Andrew MacLeod <amacleod@redhat.com>
PR tree-optimization/16447
* tree-cfg.c (bsi_commit_one_edge_insert): Rename from
bsi_commit_edge_inserts_1, and make funtion external. Return new block.
(bsi_commit_edge_inserts): Use renamed bsi_commit_one_edge_insert.
* tree-optimize.c (pass_cleanup_cfg_post_optimizing): Enable listing.
* tree-flow.h (bsi_commit_one_edge_insert): Extern decl.
* tree-outof-ssa.c (rewrite_trees): Don't commit edges here.
(same_stmt_list_p): New. Return TRUE if edge is to be forwarded.
(identical_copies_p): New. Return true is two copies are the same.
(identical_stmt_lists_p): New. Return true if stmt lists are the same.
(analyze_edges_for_bb): New. Determine how best to insert edge stmts
for a basic block.
(perform_edge_inserts): New. Determine what to do with all stmts that
have been inserted on edges.
(remove_ssa_form): Analyze and commit edges from here.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.55.2.3
diff -c -p -r2.55.2.3 tree-cfg.c
*** tree-cfg.c 30 Sep 2004 18:42:26 -0000 2.55.2.3
--- tree-cfg.c 5 Oct 2004 19:04:38 -0000
*************** static int tree_verify_flow_info (void);
*** 93,99 ****
static void tree_make_forwarder_block (edge);
static bool thread_jumps (void);
static bool tree_forwarder_block_p (basic_block);
- static void bsi_commit_edge_inserts_1 (edge e);
static void tree_cfg2vcg (FILE *);
/* Flowgraph optimization and cleanup. */
--- 93,98 ----
*************** bsi_commit_edge_inserts (int *new_blocks
*** 2913,2934 ****
blocks = n_basic_blocks;
! bsi_commit_edge_inserts_1 (EDGE_SUCC (ENTRY_BLOCK_PTR, 0));
FOR_EACH_BB (bb)
FOR_EACH_EDGE (e, ei, bb->succs)
! bsi_commit_edge_inserts_1 (e);
if (new_blocks)
*new_blocks = n_basic_blocks - blocks;
}
! /* Commit insertions pending at edge E. */
! static void
! bsi_commit_edge_inserts_1 (edge e)
{
if (PENDING_STMT (e))
{
block_stmt_iterator bsi;
--- 2912,2936 ----
blocks = n_basic_blocks;
! bsi_commit_one_edge_insert (EDGE_SUCC (ENTRY_BLOCK_PTR, 0), NULL);
FOR_EACH_BB (bb)
FOR_EACH_EDGE (e, ei, bb->succs)
! bsi_commit_one_edge_insert (e, NULL);
if (new_blocks)
*new_blocks = n_basic_blocks - blocks;
}
! /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
! to this block, otherwise set it to NULL. */
! void
! bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
{
+ if (new_bb)
+ *new_bb = NULL;
if (PENDING_STMT (e))
{
block_stmt_iterator bsi;
*************** bsi_commit_edge_inserts_1 (edge e)
*** 2936,2942 ****
PENDING_STMT (e) = NULL_TREE;
! if (tree_find_edge_insert_loc (e, &bsi, NULL))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
--- 2938,2944 ----
PENDING_STMT (e) = NULL_TREE;
! if (tree_find_edge_insert_loc (e, &bsi, new_bb))
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.46.2.2
diff -c -p -r2.46.2.2 tree-flow.h
*** tree-flow.h 30 Sep 2004 18:42:29 -0000 2.46.2.2
--- tree-flow.h 5 Oct 2004 19:04:38 -0000
*************** extern void tree_optimize_tail_calls (bo
*** 489,494 ****
--- 489,495 ----
extern edge tree_block_forwards_to (basic_block bb);
extern void bsi_insert_on_edge (edge, tree);
extern basic_block bsi_insert_on_edge_immediate (edge, tree);
+ extern void bsi_commit_one_edge_insert (edge e, basic_block *);
extern void bsi_commit_edge_inserts (int *);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.47.2.3
diff -c -p -r2.47.2.3 tree-optimize.c
*** tree-optimize.c 30 Sep 2004 18:42:30 -0000 2.47.2.3
--- tree-optimize.c 5 Oct 2004 19:04:38 -0000
*************** execute_cleanup_cfg_post_optimizing (voi
*** 118,124 ****
static struct tree_opt_pass pass_cleanup_cfg_post_optimizing =
{
! NULL, /* name */
NULL, /* gate */
execute_cleanup_cfg_post_optimizing, /* execute */
NULL, /* sub */
--- 118,124 ----
static struct tree_opt_pass pass_cleanup_cfg_post_optimizing =
{
! "final_cleanup", /* name */
NULL, /* gate */
execute_cleanup_cfg_post_optimizing, /* execute */
NULL, /* sub */
*************** static struct tree_opt_pass pass_cleanup
*** 129,135 ****
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
! 0, /* todo_flags_finish */
0 /* letter */
};
--- 129,135 ----
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
! TODO_dump_func, /* todo_flags_finish */
0 /* letter */
};
Index: tree-outof-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-outof-ssa.c,v
retrieving revision 2.22.2.1
diff -c -p -r2.22.2.1 tree-outof-ssa.c
*** tree-outof-ssa.c 30 Sep 2004 18:42:31 -0000 2.22.2.1
--- tree-outof-ssa.c 5 Oct 2004 19:04:39 -0000
*************** rewrite_trees (var_map map, tree *values
*** 1938,1946 ****
}
delete_elim_graph (g);
! /* If any copies were inserted on edges, actually insert them now. */
! bsi_commit_edge_inserts (NULL);
}
--- 1938,2268 ----
}
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 equivilent 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 stmnt 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;
+ /* 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 isn'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;
+ }
+
+ /* ensure 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);
+ #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;
! if (leader_has_match != NULL)
! {
! free (leader_has_match);
! leader_has_match = NULL;
! }
!
! 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
}
*************** remove_ssa_form (FILE *dump, var_map map
*** 2027,2032 ****
--- 2349,2357 ----
}
}
+ /* If any copies were inserted on edges, analyze and insert them now. */
+ perform_edge_inserts (dump_file);
+
dump_file = save;
}