[PATCH]: Whoops, ignore that last patch
Daniel Berlin
dan@cgsoftware.com
Sun Aug 19 11:34:00 GMT 2001
I sent the wrong version of flow.c, the
flow_reverse_top_sort_order_compute in it was wrong.
This patch should be correct now.
2001-08-19 Daniel Berlin <dan@cgsoftware.com>
* df.h (struct df): Add rts_order variable.
* df.c (df_visit_next_rts): New function.
(df_visit_next): Renamed to df_visit_next_rc
(df_analyse_1): Allocate/compute/free rts_order as well.
(df_rd_global_compute): Use df_visit_next_rc instead of
df_visit_next.
(df_ru_global_compute): Use df_visit_next_rts instead of
df_visit_next.
* flow.c (flow_reverse_top_sort_order_compute): New function.
* basic-block.h: Add prototype.
Index: df.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/df.c,v
retrieving revision 1.7
diff -c -3 -p -w -B -b -r1.7 df.c
*** df.c 2001/08/08 22:06:45 1.7
--- df.c 2001/08/19 17:59:19
*************** static void df_insn_refs_record PARAMS((
*** 238,244 ****
static void df_bb_refs_record PARAMS((struct df *, basic_block));
static void df_refs_record PARAMS((struct df *, bitmap));
! static int df_visit_next PARAMS ((struct df *, sbitmap));
static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
--- 238,245 ----
static void df_bb_refs_record PARAMS((struct df *, basic_block));
static void df_refs_record PARAMS((struct df *, bitmap));
! static int df_visit_next_rc PARAMS ((struct df *, sbitmap));
! static int df_visit_next_rts PARAMS ((struct df *, sbitmap));
static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
*************** df_ud_chain_create (df, blocks)
*** 1599,1609 ****
}
! /* Use depth first order, and the worklist, to figure out what block
to look at next. */
static int
! df_visit_next (df, blocks)
struct df *df ATTRIBUTE_UNUSED;
sbitmap blocks;
{
--- 1600,1610 ----
}
! /* Use reverse completion order, and the worklist, to figure out what block
to look at next. */
static int
! df_visit_next_rc (df, blocks)
struct df *df ATTRIBUTE_UNUSED;
sbitmap blocks;
{
*************** df_visit_next (df, blocks)
*** 1614,1619 ****
--- 1615,1636 ----
return sbitmap_first_set_bit (blocks);
}
+ /* Use reverse topsort order, and the worklist, to figure out what block
+ to look at next. */
+
+ static int
+ df_visit_next_rts (df, blocks)
+ struct df *df ATTRIBUTE_UNUSED;
+ sbitmap blocks;
+ {
+ int i=0;
+ for (i = 0; i < n_basic_blocks; i++)
+ if (TEST_BIT (blocks, df->rts_order[i]))
+ return df->rts_order[i];
+ return sbitmap_first_set_bit (blocks);
+ }
+
+
/* Calculate reaching defs for each basic block in BLOCKS, i.e., the
defs that are live at the start of a basic block. */
static void
*************** df_rd_global_compute (df, blocks)
*** 1643,1649 ****
bitmap_copy (bb_info->rd_out, bb_info->rd_gen);
});
! while ((i = df_visit_next (df, worklist)) >= 0)
{
struct bb_info *bb_info;
edge e;
--- 1660,1666 ----
bitmap_copy (bb_info->rd_out, bb_info->rd_gen);
});
! while ((i = df_visit_next_rc (df, worklist)) >= 0)
{
struct bb_info *bb_info;
edge e;
*************** df_ru_global_compute (df, blocks)
*** 1721,1727 ****
});
! while ((i = df_visit_next (df, worklist)) >= 0)
{
struct bb_info *bb_info;
edge e;
--- 1738,1744 ----
});
! while ((i = df_visit_next_rts (df, worklist)) >= 0)
{
struct bb_info *bb_info;
edge e;
*************** df_analyse_1 (df, blocks, flags, update)
*** 2220,2228 ****
df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof(int) * n_basic_blocks);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
!
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
--- 2237,2246 ----
df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof(int) * n_basic_blocks);
+ df->rts_order = xmalloc (sizeof(int) * n_basic_blocks);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
! flow_reverse_top_sort_order_compute (df->rts_order);
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
*************** df_analyse_1 (df, blocks, flags, update)
*** 2279,2284 ****
--- 2297,2303 ----
}
free (df->dfs_order);
free (df->rc_order);
+ free (df->rts_order);
}
Index: df.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/df.h,v
retrieving revision 1.2
diff -c -3 -p -w -B -b -r1.2 df.h
*** df.h 2001/06/28 22:11:18 1.2
--- df.h 2001/08/19 17:59:19
*************** struct df
*** 140,145 ****
--- 140,146 ----
bitmap *dom;
int * dfs_order;
int * rc_order;
+ int * rts_order;
};
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.465
diff -c -3 -p -w -B -b -r1.465 flow.c
*** flow.c 2001/08/19 03:04:17 1.465
--- flow.c 2001/08/19 17:59:21
*************** flow_loop_nodes_find (header, latch, nod
*** 9451,9456 ****
--- 9451,9521 ----
return num_nodes;
}
+ /* Compute reverse top sort order */
+ void
+ flow_reverse_top_sort_order_compute (rts_order)
+ int *rts_order;
+ {
+ edge *stack;
+ int sp;
+ int postnum = 0;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (n_basic_blocks);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Push the first edge on to the stack. */
+ stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+ while (sp)
+ {
+ edge e;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ e = stack[sp - 1];
+ src = e->src;
+ dest = e->dest;
+
+ /* Check if the edge destination has been visited yet. */
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ if (dest->succ)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = dest->succ;
+ }
+ else
+ rts_order[postnum++] = dest->index;
+ }
+ else
+ {
+ if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ rts_order[postnum++] = src->index;
+
+ if (e->succ_next)
+ stack[sp - 1] = e->succ_next;
+ else
+ sp--;
+ }
+ }
+
+ free (stack);
+ sbitmap_free (visited);
+ }
+
/* Compute the depth first search order and store in the array
DFS_ORDER if non-zero, marking the nodes visited in VISITED. If
RC_ORDER is non-zero, return the reverse completion number for each
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.111
diff -c -3 -p -w -B -b -r1.111 basic-block.h
*** basic-block.h 2001/08/06 06:39:20 1.111
--- basic-block.h 2001/08/19 17:59:21
*************** extern int flow_delete_block PARAMS ((b
*** 304,309 ****
--- 304,310 ----
extern void merge_blocks_nomove PARAMS ((basic_block, basic_block));
extern void tidy_fallthru_edge PARAMS ((edge, basic_block,
basic_block));
+ extern void flow_reverse_top_sort_order_compute PARAMS ((int *));
extern int flow_depth_first_order_compute PARAMS ((int *, int *));
extern void dump_edge_info PARAMS ((FILE *, edge, int));
extern void clear_edges PARAMS ((void));
--
"If you can't hear me, it's because I'm in parentheses.
"-Steven Wright
More information about the Gcc-patches
mailing list