This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] bsi_for_stmt
Hello,
this patch implements the function that enables to obtain an iterator
for the statement in constant time. This functionality seems to be
needed in several new patches (ivopts, Andrew Pinski's loops to memset
optimization pass, Dale Johannesen's implemenation of value profiling
on tree level).
The patch exposed several minor problems (chain_prev/next fields not
cleared up when statement is removed, removing a single statement
twice, marking the statement list instead of its members as modified)
that are also fixed by the patch.
Bootstrapped & regtested on i686.
Zdenek
* tree-cfg.c (build_tree_cfg): Set up container links for statements.
(modify_and_set_containers): New function.
(bsi_insert_before, bsi_insert_after): Set up container links for
statements. Work correctly with statement lists.
(bsi_replace): Set up the container link.
(tree_verify_flow_info): Verify the container links.
* tree-flow-inline.h (bsi_for_stmt): New function.
* tree-flow.h (struct stmt_ann_d): Add container field.
(bsi_for_stmt): Declare.
* tree-iterator.c (tsi_delink): Clean the prev and next fields.
* tree-ssa-dce.c (remove_dead_stmt): Avoid removing the statement
twice.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.43
diff -c -3 -p -r2.43 tree-cfg.c
*** tree-cfg.c 25 Aug 2004 21:21:12 -0000 2.43
--- tree-cfg.c 30 Aug 2004 11:23:35 -0000
*************** static bool phi_alternatives_equal (basi
*** 117,122 ****
--- 117,125 ----
static void
build_tree_cfg (tree *tp)
{
+ block_stmt_iterator bsi;
+ basic_block bb;
+
/* Register specific tree functions. */
tree_register_cfg_hooks ();
*************** build_tree_cfg (tree *tp)
*** 167,172 ****
--- 170,182 ----
a lot of obvious case merging opportunities. */
group_case_labels ();
+ /* Set up the stmt -> container links. */
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ stmt_ann (bsi_stmt (bsi))->container = bsi.tsi.ptr;
+ }
+
/* Create the edges of the flowgraph. */
make_edges ();
*************** set_bb_for_stmt (tree t, basic_block bb)
*** 2727,2732 ****
--- 2737,2761 ----
}
}
+ /* Mark the statements in list T as modified and set their container
+ links. */
+
+ static void
+ modify_and_set_containers (tree t)
+ {
+ tree_stmt_iterator i;
+
+ if (TREE_CODE (t) != STATEMENT_LIST)
+ abort ();
+
+ for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
+ {
+ tree stmt = tsi_stmt (i);
+
+ modify_stmt (stmt);
+ stmt_ann (stmt)->container = i.ptr;
+ }
+ }
/* Insert statement (or statement list) T before the statement
pointed-to by iterator I. M specifies how to update iterator I
*************** void
*** 2736,2743 ****
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
! tsi_link_before (&i->tsi, t, m);
! modify_stmt (t);
}
--- 2765,2784 ----
bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
!
! if (TREE_CODE (t) == STATEMENT_LIST)
! {
! modify_and_set_containers (t);
! tsi_link_before (&i->tsi, t, m);
! }
! else
! {
! modify_stmt (t);
! tsi_link_before (&i->tsi, t, TSI_NEW_STMT);
! stmt_ann (t)->container = i->tsi.ptr;
! if (m == BSI_SAME_STMT)
! bsi_next (i);
! }
}
*************** void
*** 2749,2756 ****
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
! tsi_link_after (&i->tsi, t, m);
! modify_stmt (t);
}
--- 2790,2809 ----
bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
{
set_bb_for_stmt (t, i->bb);
!
! if (TREE_CODE (t) == STATEMENT_LIST)
! {
! modify_and_set_containers (t);
! tsi_link_after (&i->tsi, t, m);
! }
! else
! {
! modify_stmt (t);
! tsi_link_after (&i->tsi, t, TSI_NEW_STMT);
! stmt_ann (t)->container = i->tsi.ptr;
! if (m == BSI_SAME_STMT)
! bsi_prev (i);
! }
}
*************** bsi_replace (const block_stmt_iterator *
*** 2827,2832 ****
--- 2880,2886 ----
*bsi_stmt_ptr (*bsi) = stmt;
modify_stmt (stmt);
+ stmt_ann (stmt)->container = bsi->tsi.ptr;
}
*************** tree_verify_flow_info (void)
*** 3473,3478 ****
--- 3527,3546 ----
{
bool found_ctrl_stmt = false;
+ /* Check that container field is set correctly for each statement. */
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+
+ if (stmt_ann (stmt)->container != bsi.tsi.ptr)
+ {
+ error ("Wrong container set for statement in bb %d\n",
+ bb->index);
+ print_generic_stmt (stderr, stmt, 0);
+ err = 1;
+ }
+ }
+
/* Skip labels on the start of basic block. */
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.21
diff -c -3 -p -r2.21 tree-flow-inline.h
*** tree-flow-inline.h 25 Aug 2004 21:21:12 -0000 2.21
--- tree-flow-inline.h 30 Aug 2004 11:23:35 -0000
*************** bsi_after_labels (basic_block bb)
*** 553,558 ****
--- 553,573 ----
return bsi;
}
+ /* Return a block statement iterator that points to the statement STMT. */
+
+ static inline block_stmt_iterator
+ bsi_for_stmt (tree stmt)
+ {
+ block_stmt_iterator bsi;
+ basic_block bb = bb_for_stmt (stmt);
+
+ bsi.bb = bb;
+ bsi.tsi.container = bb->stmt_list;
+ bsi.tsi.ptr = stmt_ann (stmt)->container;
+
+ return bsi;
+ }
+
/* Return a block statement iterator that points to the end of basic
block BB. */
static inline block_stmt_iterator
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.38
diff -c -3 -p -r2.38 tree-flow.h
*** tree-flow.h 29 Aug 2004 06:16:02 -0000 2.38
--- tree-flow.h 30 Aug 2004 11:23:35 -0000
*************** struct stmt_ann_d GTY(())
*** 276,281 ****
--- 276,284 ----
by each pass on an as-needed basis in any order convenient for the
pass which needs statement UIDs. */
unsigned int uid;
+
+ /* The statement list member in that the statement is contained. */
+ struct tree_statement_list_node *container;
};
union tree_ann_d GTY((desc ("ann_type ((tree_ann_t)&%h)")))
*************** typedef struct {
*** 414,419 ****
--- 417,423 ----
static inline block_stmt_iterator bsi_start (basic_block);
static inline block_stmt_iterator bsi_last (basic_block);
static inline block_stmt_iterator bsi_after_labels (basic_block);
+ static inline block_stmt_iterator bsi_for_stmt (tree);
static inline bool bsi_end_p (block_stmt_iterator);
static inline void bsi_next (block_stmt_iterator *);
static inline void bsi_prev (block_stmt_iterator *);
Index: tree-iterator.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-iterator.c,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-iterator.c
*** tree-iterator.c 16 Jun 2004 01:21:26 -0000 2.3
--- tree-iterator.c 30 Aug 2004 11:23:35 -0000
*************** tsi_delink (tree_stmt_iterator *i)
*** 241,246 ****
--- 241,253 ----
TREE_SIDE_EFFECTS (i->container) = 0;
i->ptr = next;
+
+ /* Clean the prev and next pointers, since they are marked as
+ chain_{prev,next} in GTY and this would lead to crash in case
+ the removed container is reachable from somewhere, but points
+ to the chain it does not belong to. */
+ cur->prev = NULL;
+ cur->next = NULL;
}
/* Move all statements in the statement list after I to a new
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.13
diff -c -3 -p -r2.13 tree-ssa-dce.c
*** tree-ssa-dce.c 25 Aug 2004 21:21:16 -0000 2.13
--- tree-ssa-dce.c 30 Aug 2004 11:23:35 -0000
*************** remove_dead_phis (basic_block bb)
*** 721,727 ****
static void
remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
{
! tree t = bsi_stmt (*i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 721,730 ----
static void
remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
{
! block_stmt_iterator curr = *i;
! tree t = bsi_stmt (curr);
!
! bsi_next (i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** remove_dead_stmt (block_stmt_iterator *i
*** 753,762 ****
for example with infinite loops. Removing an infinite loop is an
inappropriate transformation anyway... */
if (! post_dom_bb)
! {
! bsi_next (i);
! return;
! }
/* Redirect the first edge out of BB to reach POST_DOM_BB. */
redirect_edge_and_branch (bb->succ, post_dom_bb);
--- 756,762 ----
for example with infinite loops. Removing an infinite loop is an
inappropriate transformation anyway... */
if (! post_dom_bb)
! return;
/* Redirect the first edge out of BB to reach POST_DOM_BB. */
redirect_edge_and_branch (bb->succ, post_dom_bb);
*************** remove_dead_stmt (block_stmt_iterator *i
*** 781,789 ****
e = e->succ_next;
remove_edge (tmp);
}
}
- bsi_remove (i);
release_defs (t);
}
--- 781,795 ----
e = e->succ_next;
remove_edge (tmp);
}
+
+ /* redirect_edge_and_branch might have already removed the statement T
+ in case that tree_try_redirect_by_replacing_jump succeeded. */
+ if (last_stmt (bb) == t)
+ bsi_remove (&curr);
}
+ else
+ bsi_remove (&curr);
release_defs (t);
}