From cb7e28c369135e0ed896d8a5fd5efb40387e79c8 Mon Sep 17 00:00:00 2001 From: amacleod Date: Wed, 25 Aug 1999 18:01:48 +0000 Subject: [PATCH] Wed Aug 25 13:55:47 EDT 1999 Andrew MacLeod * sbitmap.h (sbitmap_intersection_of_succs): Add prototype. (sbitmap_intersection_of_preds, sbitmap_union_of_succs, sbitmap_union_of_preds): Add prototypes. * sbitmap.c (sbitmap_intersection_of_succs): New function to compute the intersection of successors with the new flow graph structures. (sbitmap_intersection_of_preds): New function to compute the intersection of predecessors with the new flow graph structures. (sbitmap_union_of_succs): New function to compute the union of successors with the new flow graph structures. (sbitmap_union_of_preds): New function to compute the union of predecessors with the new flow graph structures. * gcse.c (compute_rdm, compute_available): Use new sbitmap routines. (expr_reaches_here_p): Use edge and basic_block structures instead of s_preds and s_succs. (compute_cprop_avinout): Use new sbitmap routines. (pre_expr_reaches_here_p): Use edge and basic_block structures instead of s_preds and s_succs. * flow.c (compute_flow_dominators): Compute dominators using edges and basic blocks instead of s_preds and s_succs. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@28866 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 22 ++++++++ gcc/flow.c | 44 ++++++++++++++++ gcc/gcse.c | 22 ++++---- gcc/sbitmap.c | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/sbitmap.h | 9 ++++ 5 files changed, 245 insertions(+), 12 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3e39ae7c08c..7267f064574 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,25 @@ +Wed Aug 25 13:55:47 EDT 1999 Andrew MacLeod + + * sbitmap.h (sbitmap_intersection_of_succs): Add prototype. + (sbitmap_intersection_of_preds, sbitmap_union_of_succs, + sbitmap_union_of_preds): Add prototypes. + * sbitmap.c (sbitmap_intersection_of_succs): New function to compute + the intersection of successors with the new flow graph structures. + (sbitmap_intersection_of_preds): New function to compute the + intersection of predecessors with the new flow graph structures. + (sbitmap_union_of_succs): New function to compute the union of + successors with the new flow graph structures. + (sbitmap_union_of_preds): New function to compute the union of + predecessors with the new flow graph structures. + * gcse.c (compute_rdm, compute_available): Use new sbitmap routines. + (expr_reaches_here_p): Use edge and basic_block structures instead + of s_preds and s_succs. + (compute_cprop_avinout): Use new sbitmap routines. + (pre_expr_reaches_here_p): Use edge and basic_block structures instead + of s_preds and s_succs. + * flow.c (compute_flow_dominators): Compute dominators using + edges and basic blocks instead of s_preds and s_succs. + Wed Aug 25 13:41:47 EDT 1999 Andrew MacLeod * lists.c (unused_insn_list, unused_expr_list): New file for diff --git a/gcc/flow.c b/gcc/flow.c index d1b493bbe5a..a6420a74507 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -4678,6 +4678,50 @@ compute_dominators (dominators, post_dominators, s_preds, s_succs) free (temp_bitmap); } +/* 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; + + 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) + { + changed = 0; + for (bb = 1; bb < n_basic_blocks; bb++) + { + 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]); + 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]); + } + passes++; + } + + free (temp_bitmap); +} + /* Given DOMINATORS, compute the immediate dominators into IDOM. */ void diff --git a/gcc/gcse.c b/gcc/gcse.c index f5fe9b9cd6f..7a484ab2be7 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -2632,8 +2632,7 @@ compute_rd () changed = 0; for (bb = 0; bb < n_basic_blocks; bb++) { - sbitmap_union_of_predecessors (reaching_defs[bb], rd_out, - bb, s_preds); + sbitmap_union_of_preds (reaching_defs[bb], rd_out, bb); changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb], reaching_defs[bb], rd_kill[bb]); } @@ -2833,7 +2832,7 @@ compute_available () changed = 0; for (bb = 1; bb < n_basic_blocks; bb++) { - sbitmap_intersect_of_predecessors (ae_in[bb], ae_out, bb, s_preds); + sbitmap_intersection_of_preds (ae_in[bb], ae_out, bb); changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb], ae_in[bb], ae_kill[bb]); } @@ -2870,7 +2869,7 @@ expr_reaches_here_p (occr, expr, bb, check_self_loop, visited) int check_self_loop; char *visited; { - int_list_ptr pred; + edge pred; if (visited == NULL) { @@ -2878,9 +2877,9 @@ expr_reaches_here_p (occr, expr, bb, check_self_loop, visited) bzero (visited, n_basic_blocks); } - for (pred = s_preds[bb]; pred != NULL; pred = pred->next) + for (pred = BASIC_BLOCK(bb)->pred; pred != NULL; pred = pred->pred_next) { - int pred_bb = INT_LIST_VAL (pred); + int pred_bb = pred->src->index; if (visited[pred_bb]) { @@ -3512,8 +3511,7 @@ compute_cprop_avinout () for (bb = 0; bb < n_basic_blocks; bb++) { if (bb != 0) - sbitmap_intersect_of_predecessors (cprop_avin[bb], - cprop_avout, bb, s_preds); + sbitmap_intersection_of_preds (cprop_avin[bb], cprop_avout, bb); changed |= sbitmap_union_of_diff (cprop_avout[bb], cprop_pavloc[bb], cprop_avin[bb], @@ -4125,7 +4123,7 @@ pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited) int check_pre_comp; char *visited; { - int_list_ptr pred; + edge pred; if (visited == NULL) { @@ -4133,11 +4131,11 @@ pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited) bzero (visited, n_basic_blocks); } - for (pred = s_preds[bb]; pred != NULL; pred = pred->next) + for (pred = BASIC_BLOCK (bb)->pred; pred != NULL; pred = pred->pred_next) { - int pred_bb = INT_LIST_VAL (pred); + int pred_bb = pred->src->index; - if (pred_bb == ENTRY_BLOCK + if (pred->src == ENTRY_BLOCK_PTR /* Has predecessor has already been visited? */ || visited[pred_bb]) { diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index 2a417922300..89d6600927d 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -429,6 +429,166 @@ sbitmap_union_of_predsucc (dst, src, bb, pred_succ) } } +/* Set the bitmap DST to the intersection of SRC of successors of + block number BB, using the new flow graph structures. */ + +void +sbitmap_intersection_of_succs (dst, src, bb) + sbitmap dst; + sbitmap *src; + int bb; +{ + basic_block b = BASIC_BLOCK (bb); + edge e = b->succ; + int set_size = dst->size; + + for ( ; e != NULL; e = e->succ_next) + { + if (e->dest == EXIT_BLOCK_PTR) + continue; + sbitmap_copy (dst, src[e->dest->index]); + break; + } + if (e == NULL) + sbitmap_ones (dst); + else + { + for ( e = e->succ_next; e != NULL; e = e->succ_next) + { + int i; + sbitmap_ptr p,r; + + if (e->dest == EXIT_BLOCK_PTR) + continue; + + p = src[e->dest->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ &= *p++; + } + } +} + +/* Set the bitmap DST to the intersection of SRC of predecessors of + block number BB, using the new flow graph structures. */ + +void +sbitmap_intersection_of_preds (dst, src, bb) + sbitmap dst; + sbitmap *src; + int bb; +{ + basic_block b = BASIC_BLOCK (bb); + edge e = b->pred; + int set_size = dst->size; + + for ( ; e != NULL; e = e->pred_next) + { + if (e->src== ENTRY_BLOCK_PTR) + continue; + sbitmap_copy (dst, src[e->src->index]); + break; + } + if (e == NULL) + sbitmap_ones (dst); + else + { + for ( e = e->pred_next; e != NULL; e = e->pred_next) + { + int i; + sbitmap_ptr p,r; + + if (e->src == ENTRY_BLOCK_PTR) + continue; + + p = src[e->src->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ &= *p++; + } + } +} + +/* Set the bitmap DST to the union of SRC of successors of + block number BB, using the new flow graph structures. */ + +void +sbitmap_union_of_succs (dst, src, bb) + sbitmap dst; + sbitmap *src; + int bb; +{ + basic_block b = BASIC_BLOCK (bb); + edge e = b->succ; + int set_size = dst->size; + + for ( ; e != NULL; e = e->succ_next) + { + if (e->dest == EXIT_BLOCK_PTR) + continue; + sbitmap_copy (dst, src[e->dest->index]); + break; + } + if (e == NULL) + sbitmap_zero (dst); + else + { + for ( e = e->succ_next; e != NULL; e = e->succ_next) + { + int i; + sbitmap_ptr p,r; + + if (e->dest == EXIT_BLOCK_PTR) + continue; + + p = src[e->dest->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } + } +} + +/* Set the bitmap DST to the union of SRC of predecessors of + block number BB, using the new flow graph structures. */ + +void +sbitmap_union_of_preds (dst, src, bb) + sbitmap dst; + sbitmap *src; + int bb; +{ + basic_block b = BASIC_BLOCK (bb); + edge e = b->pred; + int set_size = dst->size; + + for ( ; e != NULL; e = e->pred_next) + { + if (e->src== ENTRY_BLOCK_PTR) + continue; + sbitmap_copy (dst, src[e->src->index]); + break; + } + if (e == NULL) + sbitmap_zero (dst); + else + { + for ( e = e->pred_next; e != NULL; e = e->pred_next) + { + int i; + sbitmap_ptr p,r; + + if (e->src == ENTRY_BLOCK_PTR) + continue; + + p = src[e->src->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } + } +} + void dump_sbitmap (file, bmap) FILE *file; diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index ca475fa756c..ca2f99730a5 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -120,3 +120,12 @@ extern void sbitmap_union_of_predsucc PROTO ((sbitmap, sbitmap *, int, struct int_list **)); #define sbitmap_union_of_predecessors sbitmap_union_of_predsucc #define sbitmap_union_of_successors sbitmap_union_of_predsucc + +/* Intersection and Union of preds/succs using the new flow graph + structure instead of the pred/succ arrays. */ + +extern void sbitmap_intersection_of_succs PROTO ((sbitmap, sbitmap *, int)); +extern void sbitmap_intersection_of_preds PROTO ((sbitmap, sbitmap *, int)); +extern void sbitmap_union_of_succs PROTO ((sbitmap, sbitmap *, int)); +extern void sbitmap_union_of_preds PROTO ((sbitmap, sbitmap *, int)); + -- 2.11.4.GIT