This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Routine to compute dfs back edges
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com, patches at x86-64 dot org
- Subject: Routine to compute dfs back edges
- From: Jan Hubicka <jh at suse dot cz>
- Date: Mon, 30 Jul 2001 12:48:55 +0200
Hi,
this patch takes the loop_p routine, that basically computes back edges
in DFS traversal, but does not save the infromation anywhere to do the trick.
It is usefull for some algorithms that want to do smart tree traversal and
can stop on loops otherwise. I am going to send example shortly.
Also the BB frequency propagation code can be updated to handle irreducible
regions more easilly with this code.
Honza
Bootstrapped/regtested i686 together with other weekend work.
Mon Jul 30 12:28:29 CEST 2001 Jan Hubicka <jh@suse.cz>
* flow.c (mark_dfs_back_edges): Move here from .... ; mark back
edges by EDGE_DFS_BACK flag.
(dump_edge_info): Add dfs_back flag.
* basic-block.h (EDGE_DFS_BACK): New constant.
(mark_dfs_back_edges): Declare.
* alias.c (loop_p): Here.
(mark_constant_function): Use mark_dfs_back_edges.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.435
diff -c -3 -p -r1.435 flow.c
*** flow.c 2001/07/23 14:08:11 1.435
--- flow.c 2001/07/30 09:52:26
*************** mark_critical_edges ()
*** 1476,1481 ****
--- 1534,1632 ----
}
}
+ /* Mark the back edges in DFS traversal.
+ Return non-zero if a loop (natural or otherwise) is present.
+ Inspired by Depth_First_Search_PP described in:
+
+ Advanced Compiler Design and Implementation
+ Steven Muchnick
+ Morgan Kaufmann, 1997
+
+ and heavily borrowed from flow_depth_first_order_compute. */
+
+ bool
+ mark_dfs_back_edges ()
+ {
+ edge *stack;
+ int *pre;
+ int *post;
+ int sp;
+ int prenum = 1;
+ int postnum = 1;
+ sbitmap visited;
+ bool found = false;
+
+ /* Allocate the preorder and postorder number arrays. */
+ pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
+ post = (int *) xcalloc (n_basic_blocks, sizeof (int));
+
+ /* 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;
+ e->flags &= ~EDGE_DFS_BACK;
+
+ /* 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);
+
+ pre[dest->index] = prenum++;
+
+ if (dest->succ)
+ {
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = dest->succ;
+ }
+ else
+ post[dest->index] = postnum++;
+ }
+ else
+ {
+ if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
+ && pre[src->index] >= pre[dest->index]
+ && post[dest->index] == 0)
+ e->flags |= EDGE_DFS_BACK, found = true;
+
+ if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ post[src->index] = postnum++;
+
+ if (e->succ_next)
+ stack[sp - 1] = e->succ_next;
+ else
+ sp--;
+ }
+ }
+
+ free (pre);
+ free (post);
+ free (stack);
+ sbitmap_free (visited);
+
+ return found;
+ }
+
/* Split a block BB after insn INSN creating a new fallthru edge.
Return the new edge. Note that to keep other parts of the compiler happy,
this function renumbers all the basic blocks so that the new
*************** dump_edge_info (file, e, do_succ)
*** 7587,7593 ****
if (e->flags)
{
static const char * const bitnames[] = {
! "fallthru", "crit", "ab", "abcall", "eh", "fake"
};
int comma = 0;
int i, flags = e->flags;
--- 7786,7792 ----
if (e->flags)
{
static const char * const bitnames[] = {
! "fallthru", "crit", "ab", "abcall", "eh", "fake", "dfs_back"
};
int comma = 0;
int i, flags = e->flags;
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.104
diff -c -3 -p -r1.104 basic-block.h
*** basic-block.h 2001/07/23 14:08:10 1.104
--- basic-block.h 2001/07/30 10:19:11
*************** typedef struct edge_def {
*** 145,150 ****
--- 145,151 ----
#define EDGE_ABNORMAL_CALL 8
#define EDGE_EH 16
#define EDGE_FAKE 32
+ #define EDGE_DFS_BACK 64
#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
*************** extern void conflict_graph_print
*** 639,644 ****
--- 647,653 ----
extern conflict_graph conflict_graph_compute
PARAMS ((regset,
partition));
+ extern bool mark_dfs_back_edges PARAMS ((void));
/* In dominance.c */
Index: alias.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/alias.c,v
retrieving revision 1.127
diff -c -3 -p -r1.127 alias.c
*** alias.c 2001/07/11 20:35:50 1.127
--- alias.c 2001/07/30 10:19:12
*************** static int aliases_everything_p
*** 107,114 ****
static int write_dependence_p PARAMS ((rtx, rtx, int));
static int nonlocal_mentioned_p PARAMS ((rtx));
- static int loop_p PARAMS ((void));
-
/* Set up all info needed to perform alias analysis on memory references. */
/* Returns the size in bytes of the mode of X. */
--- 107,112 ----
*************** nonlocal_mentioned_p (x)
*** 2045,2140 ****
return 0;
}
- /* Return non-zero if a loop (natural or otherwise) is present.
- Inspired by Depth_First_Search_PP described in:
-
- Advanced Compiler Design and Implementation
- Steven Muchnick
- Morgan Kaufmann, 1997
-
- and heavily borrowed from flow_depth_first_order_compute. */
-
- static int
- loop_p ()
- {
- edge *stack;
- int *pre;
- int *post;
- int sp;
- int prenum = 1;
- int postnum = 1;
- sbitmap visited;
-
- /* Allocate the preorder and postorder number arrays. */
- pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
- post = (int *) xcalloc (n_basic_blocks, sizeof (int));
-
- /* 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);
-
- pre[dest->index] = prenum++;
-
- if (dest->succ)
- {
- /* Since the DEST node has been visited for the first
- time, check its successors. */
- stack[sp++] = dest->succ;
- }
- else
- post[dest->index] = postnum++;
- }
- else
- {
- if (dest != EXIT_BLOCK_PTR
- && pre[src->index] >= pre[dest->index]
- && post[dest->index] == 0)
- break;
-
- if (! e->succ_next && src != ENTRY_BLOCK_PTR)
- post[src->index] = postnum++;
-
- if (e->succ_next)
- stack[sp - 1] = e->succ_next;
- else
- sp--;
- }
- }
-
- free (pre);
- free (post);
- free (stack);
- sbitmap_free (visited);
-
- return sp;
- }
-
/* Mark the function if it is constant. */
void
--- 2043,2048 ----
*************** mark_constant_function ()
*** 2151,2157 ****
return;
/* A loop might not return which counts as a side effect. */
! if (loop_p ())
return;
nonlocal_mentioned = 0;
--- 2059,2065 ----
return;
/* A loop might not return which counts as a side effect. */
! if (mark_dfs_back_edges ())
return;
nonlocal_mentioned = 0;