This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
patch for sbitmap
- To: egcs-patches@egcs.cygnus.com
- Subject: patch for sbitmap
- From: Andrew Macleod <amacleod@cygnus.com>
- Date: Wed, 25 Aug 1999 11:03:59 -0700
Ive applied the following patch to the source base. I've provides
a set of sbitmap routines which work off the flow graph data
structures directly rather than through the s_pred and s_succ
mechanisms. I've also changed routines in gcse.c and flow.c
to make use of these new routines.
Bootstraps on solaris and approved by rth.
Andrew
* 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.
Index: sbitmap.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/sbitmap.h,v
retrieving revision 1.2
diff -c -p -r1.2 sbitmap.h
*** sbitmap.h 1999/03/06 05:34:20 1.2
--- sbitmap.h 1999/08/24 22:08:03
*************** extern void sbitmap_union_of_predsucc PR
*** 120,122 ****
--- 120,131 ----
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));
+
Index: sbitmap.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/sbitmap.c,v
retrieving revision 1.3
diff -c -p -r1.3 sbitmap.c
*** sbitmap.c 1999/03/06 05:34:19 1.3
--- sbitmap.c 1999/08/24 22:08:05
*************** sbitmap_union_of_predsucc (dst, src, bb,
*** 429,434 ****
--- 429,594 ----
}
}
+ /* 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;
Index: gcse.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcse.c,v
retrieving revision 1.42
diff -c -p -r1.42 gcse.c
*** gcse.c 1999/08/20 23:05:08 1.42
--- gcse.c 1999/08/24 22:08:17
*************** compute_rd ()
*** 2626,2633 ****
changed = 0;
for (bb = 0; bb < n_basic_blocks; bb++)
{
! sbitmap_union_of_predecessors (reaching_defs[bb], rd_out,
! bb, s_preds);
changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
reaching_defs[bb], rd_kill[bb]);
}
--- 2626,2632 ----
changed = 0;
for (bb = 0; bb < n_basic_blocks; bb++)
{
! 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]);
}
*************** compute_available ()
*** 2827,2833 ****
changed = 0;
for (bb = 1; bb < n_basic_blocks; bb++)
{
! sbitmap_intersect_of_predecessors (ae_in[bb], ae_out, bb, s_preds);
changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb],
ae_in[bb], ae_kill[bb]);
}
--- 2826,2832 ----
changed = 0;
for (bb = 1; bb < n_basic_blocks; bb++)
{
! 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]);
}
*************** expr_reaches_here_p (occr, expr, bb, che
*** 2864,2870 ****
int check_self_loop;
char *visited;
{
! int_list_ptr pred;
if (visited == NULL)
{
--- 2863,2869 ----
int check_self_loop;
char *visited;
{
! edge pred;
if (visited == NULL)
{
*************** expr_reaches_here_p (occr, expr, bb, che
*** 2872,2880 ****
bzero (visited, n_basic_blocks);
}
! for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
{
! int pred_bb = INT_LIST_VAL (pred);
if (visited[pred_bb])
{
--- 2871,2879 ----
bzero (visited, n_basic_blocks);
}
! for (pred = BASIC_BLOCK(bb)->pred; pred != NULL; pred = pred->pred_next)
{
! int pred_bb = pred->src->index;
if (visited[pred_bb])
{
*************** compute_cprop_avinout ()
*** 3506,3513 ****
for (bb = 0; bb < n_basic_blocks; bb++)
{
if (bb != 0)
! sbitmap_intersect_of_predecessors (cprop_avin[bb],
! cprop_avout, bb, s_preds);
changed |= sbitmap_union_of_diff (cprop_avout[bb],
cprop_pavloc[bb],
cprop_avin[bb],
--- 3505,3511 ----
for (bb = 0; bb < n_basic_blocks; bb++)
{
if (bb != 0)
! sbitmap_intersection_of_preds (cprop_avin[bb], cprop_avout, bb);
changed |= sbitmap_union_of_diff (cprop_avout[bb],
cprop_pavloc[bb],
cprop_avin[bb],
*************** pre_expr_reaches_here_p (occr_bb, expr,
*** 4027,4033 ****
int check_pre_comp;
char *visited;
{
! int_list_ptr pred;
if (visited == NULL)
{
--- 4025,4031 ----
int check_pre_comp;
char *visited;
{
! edge pred;
if (visited == NULL)
{
*************** pre_expr_reaches_here_p (occr_bb, expr,
*** 4035,4045 ****
bzero (visited, n_basic_blocks);
}
! for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
{
! int pred_bb = INT_LIST_VAL (pred);
! if (pred_bb == ENTRY_BLOCK
/* Has predecessor has already been visited? */
|| visited[pred_bb])
{
--- 4033,4043 ----
bzero (visited, n_basic_blocks);
}
! for (pred = BASIC_BLOCK (bb)->pred; pred != NULL; pred = pred->pred_next)
{
! int pred_bb = pred->src->index;
! if (pred->src == ENTRY_BLOCK_PTR
/* Has predecessor has already been visited? */
|| visited[pred_bb])
{
Index: flow.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/flow.c,v
retrieving revision 1.137
diff -c -p -r1.137 flow.c
*** flow.c 1999/08/20 23:05:07 1.137
--- flow.c 1999/08/24 22:08:27
*************** compute_dominators (dominators, post_dom
*** 4670,4675 ****
--- 4670,4719 ----
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