diff options
| -rw-r--r-- | gcc/ChangeLog | 13 | ||||
| -rw-r--r-- | gcc/basic-block.h | 3 | ||||
| -rw-r--r-- | gcc/flow.c | 146 | ||||
| -rw-r--r-- | gcc/gcse.c | 5 | ||||
| -rw-r--r-- | gcc/haifa-sched.c | 6 |
5 files changed, 96 insertions, 77 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 57a8b85b46a..be5b313e903 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +Sat Nov 6 17:34:39 1999 Jeffrey A Law (law@cygnus.com) + + * gcse.c (post_dominators): Kill. + (alloc_code_hoist_mem, free_code_hoist_mem); Kill post_dominators. + (compute_code_hoist_data): Use compute_flow_dominators. Do not + pass in a pdom array since we do not need pdoms. + * haifa-sched.c (schedule_insns): Similarly. + * flow.c (compute_dominators): Remove dead function. + (compute_flow_dominators): Do not compute doms or pdoms if the + caller does not request them. Split up loop to build doms and + pdoms. Use a worklist to compute doms and pdoms. + * basic-block.h (compute_dominators): Remove prototype. + Sat Nov 6 11:38:39 1999 Richard Henderson <rth@cygnus.com> * haifa-sched.c (struct haifa_insn_data, h_i_d): New. diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 4de631ad9be..16537b79b8b 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -294,9 +294,6 @@ int find_edge_index PROTO ((struct edge_list *, extern void compute_preds_succs PROTO ((int_list_ptr *, int_list_ptr *, int *, int *)); -extern void compute_dominators PROTO ((sbitmap *, sbitmap *, - int_list_ptr *, - int_list_ptr *)); extern void compute_flow_dominators PROTO ((sbitmap *, sbitmap *)); extern void compute_immediate_dominators PROTO ((int *, sbitmap *)); diff --git a/gcc/flow.c b/gcc/flow.c index 43688ae11d3..bf482632bcb 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -5317,95 +5317,109 @@ free_bb_mem () free_int_list (&pred_int_list_blocks); } -/* Compute dominator relationships. */ +/* Compute dominator relationships using new flow graph structures. */ void -compute_dominators (dominators, post_dominators, s_preds, s_succs) +compute_flow_dominators (dominators, post_dominators) sbitmap *dominators; sbitmap *post_dominators; - int_list_ptr *s_preds; - int_list_ptr *s_succs; { - int bb, changed, passes; + int bb; sbitmap *temp_bitmap; + edge e; + basic_block *worklist, *tos; + + /* Allocate a worklist array/queue. Entries are only added to the + list if they were not already on the list. So the size is + bounded by the number of basic blocks. */ + tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) + * n_basic_blocks); temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - sbitmap_vector_ones (dominators, n_basic_blocks); - sbitmap_vector_ones (post_dominators, n_basic_blocks); sbitmap_vector_zero (temp_bitmap, n_basic_blocks); - sbitmap_zero (dominators[0]); - SET_BIT (dominators[0], 0); - - sbitmap_zero (post_dominators[n_basic_blocks - 1]); - SET_BIT (post_dominators[n_basic_blocks - 1], 0); - - passes = 0; - changed = 1; - while (changed) + if (dominators) { - changed = 0; - for (bb = 1; bb < n_basic_blocks; bb++) + sbitmap_vector_ones (dominators, n_basic_blocks); + sbitmap_zero (dominators[0]); + SET_BIT (dominators[0], 0); + + /* Put the successors of the entry block on the worklist. */ + for (e = BASIC_BLOCK (0)->succ; e; e = e->succ_next) { - sbitmap_intersect_of_predecessors (temp_bitmap[bb], dominators, - bb, s_preds); - SET_BIT (temp_bitmap[bb], bb); - changed |= sbitmap_a_and_b (dominators[bb], - dominators[bb], - temp_bitmap[bb]); - sbitmap_intersect_of_successors (temp_bitmap[bb], post_dominators, - bb, s_succs); - SET_BIT (temp_bitmap[bb], bb); - changed |= sbitmap_a_and_b (post_dominators[bb], - post_dominators[bb], - temp_bitmap[bb]); + *tos++ = e->dest; + e->dest->aux = e; } - passes++; - } - free (temp_bitmap); -} + /* Iterate until the worklist is empty. */ + while (tos != worklist) + { + /* Take the first entry off the worklist. */ + basic_block b = *--tos; + b->aux = NULL; + bb = b->index; -/* Compute dominator relationships using new flow graph structures. */ -void -compute_flow_dominators (dominators, post_dominators) - sbitmap *dominators; - sbitmap *post_dominators; -{ - int bb, changed, passes; - sbitmap *temp_bitmap; + sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb); + SET_BIT (temp_bitmap[bb], bb); - temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - sbitmap_vector_ones (dominators, n_basic_blocks); - sbitmap_vector_ones (post_dominators, n_basic_blocks); - sbitmap_vector_zero (temp_bitmap, n_basic_blocks); + /* If the out state of this block changed, then we need to + add the successors of this block to the worklist if they + are not already on the worklist. */ + if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb])) + { + for (e = b->succ; e; e = e->succ_next) + { + if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) + { + *tos++ = e->dest; + e->dest->aux = e; + } + } + } + } + } - sbitmap_zero (dominators[0]); - SET_BIT (dominators[0], 0); + if (post_dominators) + { + sbitmap_vector_ones (post_dominators, n_basic_blocks); + sbitmap_zero (post_dominators[n_basic_blocks - 1]); + SET_BIT (post_dominators[n_basic_blocks - 1], 0); - sbitmap_zero (post_dominators[n_basic_blocks - 1]); - SET_BIT (post_dominators[n_basic_blocks - 1], 0); + /* Put the predecessors of the exit block on the worklist. */ + for (e = BASIC_BLOCK (n_basic_blocks - 1)->pred; e; e = e->pred_next) + { + *tos++ = e->src; + e->src->aux = e; + } - passes = 0; - changed = 1; - while (changed) - { - changed = 0; - for (bb = 1; bb < n_basic_blocks; bb++) + /* Iterate until the worklist is empty. */ + while (tos != worklist) { - sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb); - SET_BIT (temp_bitmap[bb], bb); - changed |= sbitmap_a_and_b (dominators[bb], - dominators[bb], - temp_bitmap[bb]); + /* Take the first entry off the worklist. */ + basic_block b = *--tos; + b->aux = NULL; + bb = b->index; + sbitmap_intersection_of_succs (temp_bitmap[bb], post_dominators, bb); SET_BIT (temp_bitmap[bb], bb); - changed |= sbitmap_a_and_b (post_dominators[bb], - post_dominators[bb], - temp_bitmap[bb]); + + /* If the out state of this block changed, then we need to + add the successors of this block to the worklist if they + are not already on the worklist. */ + if (sbitmap_a_and_b (post_dominators[bb], + post_dominators[bb], + temp_bitmap[bb])) + { + for (e = b->pred; e; e = e->pred_next) + { + if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) + { + *tos++ = e->src; + e->src->aux = e; + } + } + } } - passes++; } - free (temp_bitmap); } diff --git a/gcc/gcse.c b/gcc/gcse.c index 067cfbfdd91..69af46346b9 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -5330,7 +5330,6 @@ static sbitmap *hoist_exprs; /* Dominator bitmaps. */ static sbitmap *dominators; -static sbitmap *post_dominators; /* ??? We could compute post dominators and run this algorithm in reverse to to perform tail merging, doing so would probably be @@ -5355,7 +5354,6 @@ alloc_code_hoist_mem (n_blocks, n_exprs) transpout = sbitmap_vector_alloc (n_blocks, n_exprs); dominators = sbitmap_vector_alloc (n_blocks, n_blocks); - post_dominators = sbitmap_vector_alloc (n_blocks, n_blocks); } /* Free vars used for code hoisting analysis. */ @@ -5373,7 +5371,6 @@ free_code_hoist_mem () free (transpout); free (dominators); - free (post_dominators); } /* Compute the very busy expressions at entry/exit from each block. @@ -5418,7 +5415,7 @@ compute_code_hoist_data () compute_local_properties (transp, comp, antloc, 0); compute_transpout (); compute_code_hoist_vbeinout (); - compute_flow_dominators (dominators, post_dominators); + compute_flow_dominators (dominators, NULL); if (gcse_file) fprintf (gcse_file, "\n"); } diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 305a145543c..a4fdd75f2c8 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -6965,7 +6965,7 @@ schedule_insns (dump_file) { int_list_ptr *s_preds, *s_succs; int *num_preds, *num_succs; - sbitmap *dom, *pdom; + sbitmap *dom; s_preds = (int_list_ptr *) xmalloc (n_basic_blocks * sizeof (int_list_ptr)); @@ -6974,7 +6974,6 @@ schedule_insns (dump_file) num_preds = (int *) xmalloc (n_basic_blocks * sizeof (int)); num_succs = (int *) xmalloc (n_basic_blocks * sizeof (int)); dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - pdom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); /* The scheduler runs after flow; therefore, we can't blindly call back into find_basic_blocks since doing so could invalidate the @@ -6993,7 +6992,7 @@ schedule_insns (dump_file) /* Compute the dominators and post dominators. We don't currently use post dominators, but we should for speculative motion analysis. */ - compute_dominators (dom, pdom, s_preds, s_succs); + compute_flow_dominators (dom, NULL); /* build_control_flow will return nonzero if it detects unreachable blocks or any other irregularity with the cfg which prevents @@ -7010,7 +7009,6 @@ schedule_insns (dump_file) to using the cfg code in flow.c. */ free_bb_mem (); free (dom); - free (pdom); free (s_preds); free (s_succs); free (num_preds); |