[patch] Avoid using BB_VISITED everywhere
Steven Bosscher
stevenb@suse.de
Sun Jan 9 01:01:00 GMT 2005
Hi,
Following the discussion on gcc@, this patch documents that BB_VISITED
is not supposed to be used by any pass.
Bootstrapped and tested on {i686,x86_64,ia64,ppc64,ppc)-suse-linux-gnu.
OK?
Gr.
Steven
* basic-block.h: Document BB_* flags.
* regrename.c (copyprop_hardreg_forward): Don't use BB_VISITED,
use an sbitmap instead.
* sched-rgn.c (compute_trg_info): Likewise.
* tree-ssa-dce.c (visited_control_parents): New sbitmap to
replace BB_VISITED uses.
(find_obviously_necessary_stmts): Don't clear BB_VISITED.
(propagate_necessity): Check the bitmap instead of BB_VISITED.
(tree_dce_done): Free visited_control_parents.
(perform_tree_ssa_dce): Allocate and clear it.
* tree-ssa-pre.c (compute_antic_aux): Make non-recursive.
(compute_antic): Iterate from here using a DFS. Use an sbitmap
instead of BB_VISITED.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.233
diff -c -3 -p -r1.233 basic-block.h
*** basic-block.h 13 Dec 2004 20:44:31 -0000 1.233
--- basic-block.h 7 Jan 2005 23:49:20 -0000
*************** typedef struct reorder_block_def
*** 285,302 ****
#define BB_FREQ_MAX 10000
! /* Masks for basic_block.flags. */
! #define BB_DIRTY 1
! #define BB_NEW 2
! #define BB_REACHABLE 4
! #define BB_VISITED 8
! #define BB_IRREDUCIBLE_LOOP 16
! #define BB_SUPERBLOCK 32
! #define BB_DISABLE_SCHEDULE 64
!
! #define BB_HOT_PARTITION 128
! #define BB_COLD_PARTITION 256
! #define BB_UNPARTITIONED 0
/* Partitions, to be used when partitioning hot and cold basic blocks into
separate sections. */
--- 285,322 ----
#define BB_FREQ_MAX 10000
! /* Masks for basic_block.flags. BB_VISITED should not be used by passes,
! it is used internally by dfs_enumerate_from().
! BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
! the compilation, so they are never cleared.
! All other flags may be cleared by clear_bb_flags(). It is generally
! a bad idea to rely on any flags being up-to-date. */
!
! #define BB_DIRTY 1 /* Set if insns in BB have are
! modified. Used for updating
! liveness information. */
! #define BB_NEW 2 /* Only set on blocks that have
! just been created by create_bb. */
! #define BB_REACHABLE 4 /* Set by find_unreachable_blocks.
! Don't rely on this being set in
! any pass. */
! #define BB_VISITED 8 /* Used by dfs_enumerate_from(). */
! #define BB_IRREDUCIBLE_LOOP 16 /* Set for blocks in an irreducible
! loop by loop analysis. */
! #define BB_SUPERBLOCK 32 /* Set on blocks that may actually
! not be single-entry single-exit
! basic blocks. */
! #define BB_DISABLE_SCHEDULE 64 /* Set on basic blocks that the
! scheduler should not touch. This
! is used by SMS to prevent the
! other schedulers from messing
! with the loop schedule. */
! #define BB_HOT_PARTITION 128 /* Set on blocks that should be put
! in a hot section. */
! #define BB_COLD_PARTITION 256 /* Set on blocks that should be put
! in a cold section. */
! #define BB_UNPARTITIONED 0 /* Dummy flag for convenience in the
! hot/cold partitioning code. */
/* Partitions, to be used when partitioning hot and cold basic blocks into
separate sections. */
Index: regrename.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/regrename.c,v
retrieving revision 1.92
diff -c -3 -p -r1.92 regrename.c
*** regrename.c 22 Nov 2004 15:18:50 -0000 1.92
--- regrename.c 7 Jan 2005 23:49:21 -0000
*************** copyprop_hardreg_forward (void)
*** 1746,1774 ****
struct value_data *all_vd;
bool need_refresh;
basic_block bb;
need_refresh = false;
all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
! /* Clear all BB_VISITED flags. We use BB_VISITED flags to indicate
! whether we have processed a given basic block or not. Note that
! we never put BB_VISITED flag on ENTRY_BLOCK_PTR throughout this
! function because we want to call init_value_data for all
! successors of ENTRY_BLOCK_PTR. */
! FOR_ALL_BB (bb)
! bb->flags &= ~BB_VISITED;
FOR_EACH_BB (bb)
{
! bb->flags |= BB_VISITED;
/* If a block has a single predecessor, that we've already
processed, begin with the value data that was live at
the end of the predecessor block. */
/* ??? Ought to use more intelligent queuing of blocks. */
if (EDGE_COUNT (bb->preds) == 1
! && ((EDGE_PRED (bb, 0)->src->flags & BB_VISITED) != 0)
&& ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
else
--- 1746,1771 ----
struct value_data *all_vd;
bool need_refresh;
basic_block bb;
+ sbitmap visited;
need_refresh = false;
all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
! visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
! sbitmap_zero (visited);
FOR_EACH_BB (bb)
{
! SET_BIT (visited, bb->index - (INVALID_BLOCK + 1));
/* If a block has a single predecessor, that we've already
processed, begin with the value data that was live at
the end of the predecessor block. */
/* ??? Ought to use more intelligent queuing of blocks. */
if (EDGE_COUNT (bb->preds) == 1
! && TEST_BIT (visited,
! EDGE_PRED (bb, 0)->src->index - (INVALID_BLOCK + 1))
&& ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
else
*************** copyprop_hardreg_forward (void)
*** 1778,1788 ****
need_refresh = true;
}
! /* Clear BB_VISITED flag on each basic block. We do not need to
! clear the one on ENTRY_BLOCK_PTR because it's already cleared
! above. */
! FOR_EACH_BB (bb)
! bb->flags &= ~BB_VISITED;
if (need_refresh)
{
--- 1775,1781 ----
need_refresh = true;
}
! sbitmap_free (visited);
if (need_refresh)
{
Index: sched-rgn.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sched-rgn.c,v
retrieving revision 1.89
diff -c -3 -p -r1.89 sched-rgn.c
*** sched-rgn.c 5 Jan 2005 23:19:22 -0000 1.89
--- sched-rgn.c 7 Jan 2005 23:49:21 -0000
*************** compute_trg_info (int trg)
*** 997,1002 ****
--- 997,1003 ----
edgelst el;
int i, j, k, update_idx;
basic_block block;
+ sbitmap visited;
edge_iterator ei;
edge e;
*************** compute_trg_info (int trg)
*** 1006,1011 ****
--- 1007,1014 ----
sp->is_speculative = 0;
sp->src_prob = 100;
+ visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
+
for (i = trg + 1; i < current_nr_blocks; i++)
{
sp = candidate_table + i;
*************** compute_trg_info (int trg)
*** 1043,1054 ****
overrunning the end of the bblst_table. */
update_idx = 0;
for (j = 0; j < el.nr_members; j++)
{
block = el.first_member[j]->src;
FOR_EACH_EDGE (e, ei, block->succs)
{
! if (!(e->dest->flags & BB_VISITED))
{
for (k = 0; k < el.nr_members; k++)
if (e == el.first_member[k])
--- 1046,1059 ----
overrunning the end of the bblst_table. */
update_idx = 0;
+ sbitmap_zero (visited);
for (j = 0; j < el.nr_members; j++)
{
block = el.first_member[j]->src;
FOR_EACH_EDGE (e, ei, block->succs)
{
! if (!TEST_BIT (visited,
! e->dest->index - (INVALID_BLOCK + 1)))
{
for (k = 0; k < el.nr_members; k++)
if (e == el.first_member[k])
*************** compute_trg_info (int trg)
*** 1057,1063 ****
if (k >= el.nr_members)
{
bblst_table[bblst_last++] = e->dest;
! e->dest->flags |= BB_VISITED;
update_idx++;
}
}
--- 1062,1069 ----
if (k >= el.nr_members)
{
bblst_table[bblst_last++] = e->dest;
! SET_BIT (visited,
! e->dest->index - (INVALID_BLOCK + 1));
update_idx++;
}
}
*************** compute_trg_info (int trg)
*** 1065,1073 ****
}
sp->update_bbs.nr_members = update_idx;
- FOR_ALL_BB (block)
- block->flags &= ~BB_VISITED;
-
/* Make sure we didn't overrun the end of bblst_table. */
gcc_assert (bblst_last <= bblst_size);
}
--- 1071,1076 ----
*************** compute_trg_info (int trg)
*** 1079,1084 ****
--- 1082,1089 ----
sp->src_prob = 0;
}
}
+
+ sbitmap_free (visited);
}
/* Print candidates info, for debugging purposes. Callable from debugger. */
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.29
diff -c -3 -p -r2.29 tree-ssa-dce.c
*** tree-ssa-dce.c 13 Dec 2004 16:03:40 -0000 2.29
--- tree-ssa-dce.c 7 Jan 2005 23:49:21 -0000
*************** static sbitmap last_stmt_necessary;
*** 93,98 ****
--- 93,102 ----
on the Ith edge. */
bitmap *control_dependence_map;
+ /* Vector indicating that a basic block has already had all the edges
+ processed that it is control dependent on. */
+ sbitmap visited_control_parents;
+
/* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
for which the block with index N is control dependent. */
#define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE) \
*************** find_obviously_necessary_stmts (struct e
*** 482,492 ****
NECESSARY (stmt) = 0;
mark_stmt_if_obviously_necessary (stmt, el != NULL);
}
-
- /* Mark this basic block as `not visited'. A block will be marked
- visited when the edges that it is control dependent on have been
- marked. */
- bb->flags &= ~BB_VISITED;
}
if (el)
--- 486,491 ----
*************** propagate_necessity (struct edge_list *e
*** 565,573 ****
containing `i' is control dependent on, but only if we haven't
already done so. */
basic_block bb = bb_for_stmt (i);
! if (! (bb->flags & BB_VISITED))
{
! bb->flags |= BB_VISITED;
mark_control_dependent_edges_necessary (bb, el);
}
}
--- 564,573 ----
containing `i' is control dependent on, but only if we haven't
already done so. */
basic_block bb = bb_for_stmt (i);
! if (bb != ENTRY_BLOCK_PTR
! && ! TEST_BIT (visited_control_parents, bb->index))
{
! SET_BIT (visited_control_parents, bb->index);
mark_control_dependent_edges_necessary (bb, el);
}
}
*************** propagate_necessity (struct edge_list *e
*** 593,601 ****
for (k = 0; k < PHI_NUM_ARGS (i); k++)
{
basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
! if (! (arg_bb->flags & BB_VISITED))
{
! arg_bb->flags |= BB_VISITED;
mark_control_dependent_edges_necessary (arg_bb, el);
}
}
--- 593,602 ----
for (k = 0; k < PHI_NUM_ARGS (i); k++)
{
basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
! if (arg_bb != ENTRY_BLOCK_PTR
! && ! TEST_BIT (visited_control_parents, arg_bb->index))
{
! SET_BIT (visited_control_parents, arg_bb->index);
mark_control_dependent_edges_necessary (arg_bb, el);
}
}
*************** tree_dce_done (bool aggressive)
*** 903,908 ****
--- 904,910 ----
BITMAP_XFREE (control_dependence_map[i]);
free (control_dependence_map);
+ sbitmap_free (visited_control_parents);
sbitmap_free (last_stmt_necessary);
}
*************** perform_tree_ssa_dce (bool aggressive)
*** 939,944 ****
--- 941,949 ----
find_all_control_dependences (el);
timevar_pop (TV_CONTROL_DEPENDENCES);
+ visited_control_parents = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (visited_control_parents);
+
mark_dfs_back_edges ();
}
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.59
diff -c -3 -p -r2.59 tree-ssa-pre.c
*** tree-ssa-pre.c 8 Dec 2004 00:09:30 -0000 2.59
--- tree-ssa-pre.c 7 Jan 2005 23:49:21 -0000
*************** DEF_VEC_MALLOC_P (basic_block);
*** 1113,1164 ****
ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
- Iterate until fixpointed.
-
XXX: It would be nice to either write a set_clear, and use it for
ANTIC_OUT, or to mark the antic_out set as deleted at the end
of this routine, so that the pool can hand the same memory back out
again for the next ANTIC_OUT. */
-
static bool
! compute_antic_aux (basic_block block)
{
- basic_block son;
- edge e;
bool changed = false;
value_set_t S, old, ANTIC_OUT;
value_set_node_t node;
!
ANTIC_OUT = S = NULL;
! /* If any edges from predecessors are abnormal, antic_in is empty, so
! punt. Remember that the block has an incoming abnormal edge by
! setting the BB_VISITED flag. */
! if (! (block->flags & BB_VISITED))
! {
! edge_iterator ei;
! FOR_EACH_EDGE (e, ei, block->preds)
! if (e->flags & EDGE_ABNORMAL)
! {
! block->flags |= BB_VISITED;
! break;
! }
! }
! if (block->flags & BB_VISITED)
! {
! S = NULL;
! goto visit_sons;
! }
!
old = set_new (false);
set_copy (old, ANTIC_IN (block));
ANTIC_OUT = set_new (true);
! /* If the block has no successors, ANTIC_OUT is empty, because it is
! the exit block. */
! if (EDGE_COUNT (block->succs) == 0);
!
/* If we have one successor, we could have some phi nodes to
translate through. */
else if (EDGE_COUNT (block->succs) == 1)
--- 1113,1144 ----
ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
XXX: It would be nice to either write a set_clear, and use it for
ANTIC_OUT, or to mark the antic_out set as deleted at the end
of this routine, so that the pool can hand the same memory back out
again for the next ANTIC_OUT. */
static bool
! compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
{
bool changed = false;
value_set_t S, old, ANTIC_OUT;
value_set_node_t node;
!
ANTIC_OUT = S = NULL;
!
! /* If any edges from predecessors are abnormal, antic_in is empty,
! so do nothing. */
! if (block_has_abnormal_pred_edge)
! goto maybe_dump_sets;
old = set_new (false);
set_copy (old, ANTIC_IN (block));
ANTIC_OUT = set_new (true);
! /* If the block has no successors, ANTIC_OUT is empty. */
! if (EDGE_COUNT (block->succs) == 0)
! ;
/* If we have one successor, we could have some phi nodes to
translate through. */
else if (EDGE_COUNT (block->succs) == 1)
*************** compute_antic_aux (basic_block block)
*** 1206,1226 ****
TMP_GEN (block),
true);
! /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
! EXP_GEN - TMP_GEN */
! for (node = S->head;
! node;
! node = node->next)
! {
! value_insert_into_set (ANTIC_IN (block), node->expr);
! }
! clean (ANTIC_IN (block));
!
if (!set_equal (old, ANTIC_IN (block)))
changed = true;
! visit_sons:
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (ANTIC_OUT)
--- 1186,1201 ----
TMP_GEN (block),
true);
! /* Then union in the ANTIC_OUT - TMP_GEN values,
! to get ANTIC_OUT U EXP_GEN - TMP_GEN */
! for (node = S->head; node; node = node->next)
! value_insert_into_set (ANTIC_IN (block), node->expr);
+ clean (ANTIC_IN (block));
if (!set_equal (old, ANTIC_IN (block)))
changed = true;
! maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (ANTIC_OUT)
*************** compute_antic_aux (basic_block block)
*** 1228,1270 ****
print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
if (S)
print_value_set (dump_file, S, "S", block->index);
-
}
- for (son = first_dom_son (CDI_POST_DOMINATORS, block);
- son;
- son = next_dom_son (CDI_POST_DOMINATORS, son))
- {
- changed |= compute_antic_aux (son);
- }
return changed;
}
! /* Compute ANTIC sets. */
static void
compute_antic (void)
{
! bool changed = true;
! basic_block bb;
int num_iterations = 0;
! FOR_ALL_BB (bb)
{
! ANTIC_IN (bb) = set_new (true);
! gcc_assert (!(bb->flags & BB_VISITED));
}
while (changed)
{
! num_iterations++;
changed = false;
! changed = compute_antic_aux (EXIT_BLOCK_PTR);
! }
! FOR_ALL_BB (bb)
! {
! bb->flags &= ~BB_VISITED;
}
! if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
}
--- 1203,1284 ----
print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
if (S)
print_value_set (dump_file, S, "S", block->index);
}
return changed;
}
! /* Compute ANTIC sets. Iterates until fixpointed. */
static void
compute_antic (void)
{
! bool changed= true;
int num_iterations = 0;
! basic_block block, *worklist;
! size_t sp = 0;
! sbitmap has_abnormal_preds;
!
! /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
! We pre-build the map of blocks with incoming abnormal edges here. */
! has_abnormal_preds = sbitmap_alloc (last_basic_block);
! sbitmap_zero (has_abnormal_preds);
! FOR_EACH_BB (block)
{
! edge_iterator ei;
! edge e;
!
! FOR_EACH_EDGE (e, ei, block->preds)
! if (e->flags & EDGE_ABNORMAL)
! {
! SET_BIT (has_abnormal_preds, block->index);
! break;
! }
!
! /* While we are here, give empty ANTIC_IN sets to each block. */
! ANTIC_IN (block) = set_new (true);
}
+ /* At the exit block we anticipate nothing. */
+ ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
+ /* Allocate the worklist. */
+ worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+
+ /* Loop until fixpointed. */
while (changed)
{
! basic_block son, bb;
!
changed = false;
! num_iterations++;
!
! /* Seed the algorithm by putting post-dominator children of
! the exit block in the worklist. */
! for (son = first_dom_son (CDI_POST_DOMINATORS, EXIT_BLOCK_PTR);
! son;
! son = next_dom_son (CDI_POST_DOMINATORS, son))
! worklist[sp++] = son;
!
! /* Now visit all blocks in a DFS of the post dominator tree. */
! while (sp)
! {
! bool bb_has_abnormal_pred;
!
! bb = worklist[--sp];
! bb_has_abnormal_pred = TEST_BIT (has_abnormal_preds, bb->index);
! changed |= compute_antic_aux (bb, bb_has_abnormal_pred);
!
! for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
! son;
! son = next_dom_son (CDI_POST_DOMINATORS, son))
! worklist[sp++] = son;
! }
}
!
! free (worklist);
! sbitmap_free (has_abnormal_preds);
!
! if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
}
More information about the Gcc-patches
mailing list