This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] DFS fix.
Michael Matz writes:
> No no, the code is nice, and does the right thing :) Only that its not the
> DFSnum what it is calculating. May be I find time to prepare a patch for
> the comments if you want.
How about this then? Does this make more sense?
Michael.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.304
diff -c -3 -p -r1.304 flow.c
*** flow.c 2000/06/29 00:36:10 1.304
--- flow.c 2000/07/06 04:30:19
*************** static void flow_loops_cfg_dump PARAMS
*** 395,401 ****
static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *));
static int flow_loop_exits_find PARAMS ((const sbitmap, edge **));
static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
! static int flow_depth_first_order_compute PARAMS ((int *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
static void flow_loops_tree_build PARAMS ((struct loops *));
--- 397,403 ----
static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *));
static int flow_loop_exits_find PARAMS ((const sbitmap, edge **));
static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
! static int flow_depth_first_order_compute PARAMS ((int *, int *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
static void flow_loops_tree_build PARAMS ((struct loops *));
*************** flow_loops_cfg_dump (loops, file)
*** 7015,7020 ****
--- 7029,7042 ----
fprintf (file, "%d ", loops->cfg.dfs_order[i]);
fputs ("\n", file);
}
+ /* Dump the reverse completion node order. */
+ if (loops->cfg.rc_order)
+ {
+ fputs (";; RC order: ", file);
+ for (i = 0; i < n_basic_blocks; i++)
+ fprintf (file, "%d ", loops->cfg.rc_order[i]);
+ fputs ("\n", file);
+ }
}
*************** flow_loop_nodes_find (header, latch, nod
*** 7252,7267 ****
/* Compute the depth first search order and store in the array
! DFS_ORDER, marking the nodes visited in VISITED. Returns the
! number of nodes visited. A depth first search tries to get as far
! away from the starting point as quickly as possible. */
static int
! flow_depth_first_order_compute (dfs_order)
int *dfs_order;
{
edge *stack;
int sp;
int dfsnum = 0;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
--- 7296,7315 ----
/* 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
! node. Returns the number of nodes visited. A depth first search
! tries to get as far away from the starting point as quickly as
! possible. */
static int
! flow_depth_first_order_compute (dfs_order, rc_order)
int *dfs_order;
+ int *rc_order;
{
edge *stack;
int sp;
int dfsnum = 0;
+ int rcnum = n_basic_blocks - 1;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
*************** flow_depth_first_order_compute (dfs_orde
*** 7293,7298 ****
--- 7341,7349 ----
{
/* Mark that we have visited the destination. */
SET_BIT (visited, dest->index);
+
+ if (dfs_order)
+ dfs_order[dfsnum++] = dest->index;
if (dest->succ)
{
*************** flow_depth_first_order_compute (dfs_orde
*** 7303,7310 ****
else
{
/* There are no successors for the DEST node so assign
! its DFS number. */
! dfs_order[n_basic_blocks - ++dfsnum] = dest->index;
}
}
else
--- 7354,7362 ----
else
{
/* There are no successors for the DEST node so assign
! its reverse completion number. */
! if (rc_order)
! rc_order[rcnum--] = dest->index;
}
}
else
*************** flow_depth_first_order_compute (dfs_orde
*** 7312,7319 ****
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
{
/* There are no more successors for the SRC node
! so assign its DFS number. */
! dfs_order[n_basic_blocks - ++dfsnum] = src->index;
}
if (e->succ_next)
--- 7364,7372 ----
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
{
/* There are no more successors for the SRC node
! so assign its reverse completion number. */
! if (rc_order)
! rc_order[rcnum--] = src->index;
}
if (e->succ_next)
*************** flow_loops_find (loops)
*** 7502,7512 ****
--- 7555,7567 ----
sbitmap headers;
sbitmap *dom;
int *dfs_order;
+ int *rc_order;
loops->num = 0;
loops->array = NULL;
loops->tree = NULL;
dfs_order = NULL;
+ rc_order = NULL;
/* Taking care of this degenerate case makes the rest of
this code simpler. */
*************** flow_loops_find (loops)
*** 7547,7553 ****
/* Compute depth first search order of the CFG so that outer
natural loops will be found before inner natural loops. */
dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
! flow_depth_first_order_compute (dfs_order);
/* Allocate loop structures. */
loops->array
--- 7602,7609 ----
/* Compute depth first search order of the CFG so that outer
natural loops will be found before inner natural loops. */
dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
! rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
! flow_depth_first_order_compute (dfs_order, rc_order);
/* Allocate loop structures. */
loops->array
*************** flow_loops_find (loops)
*** 7568,7574 ****
/* Search the nodes of the CFG in DFS order that we can find
outer loops first. */
! header = BASIC_BLOCK (dfs_order[b]);
/* Look for all the possible latch blocks for this header. */
for (e = header->pred; e; e = e->pred_next)
--- 7624,7630 ----
/* Search the nodes of the CFG in DFS order that we can find
outer loops first. */
! header = BASIC_BLOCK (rc_order[b]);
/* Look for all the possible latch blocks for this header. */
for (e = header->pred; e; e = e->pred_next)
*************** flow_loops_find (loops)
*** 7641,7646 ****
--- 7698,7704 ----
/* Save CFG derived information to avoid recomputing it. */
loops->cfg.dom = dom;
loops->cfg.dfs_order = dfs_order;
+ loops->cfg.rc_order = rc_order;
/* Build the loop hierarchy tree. */
flow_loops_tree_build (loops);
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.71
diff -c -3 -p -r1.71 basic-block.h
*** basic-block.h 2000/06/14 07:41:57 1.71
--- basic-block.h 2000/07/06 04:30:19
*************** struct loops
*** 369,374 ****
--- 373,382 ----
/* The ordering of the basic blocks in a depth first search. */
int *dfs_order;
+
+ /* The reverse completion ordering of the basic blocks found in a
+ depth first search. */
+ int *rc_order;
} cfg;
/* Headers shared by multiple loops that should be merged. */