PATCH: Lengauer/Tarjan version of dominator computing
Brad Lucier
lucier@math.purdue.edu
Thu Oct 5 13:27:00 GMT 2000
This patch bootstraps and passes make check on alphaev6-unknown-linux-gnu
with no new regressions.
I could not get the patch to apply cleanly to today's CVS sources, so
I applied the changes by hand and prepared a new diff file, which I've
included below.
I guess next I will profile cc1 with the patch ...
Brad Lucier
===================================================================
RCS file: RCS/Makefile.in,v
retrieving revision 1.1
diff -p -r1.1 Makefile.in
*** Makefile.in 2000/10/05 19:00:32 1.1
--- Makefile.in 2000/10/05 19:06:19
*************** OBJS = diagnostic.o version.o tree.o pri
*** 698,704 ****
profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o \
mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o \
lists.o ggc-common.o $(GGC) simplify-rtx.o ssa.o bb-reorder.o \
! sibcall.o conflict.o timevar.o ifcvt.o dependence.o dce.o
BACKEND = toplev.o libbackend.a
--- 698,704 ----
profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o \
mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o \
lists.o ggc-common.o $(GGC) simplify-rtx.o ssa.o bb-reorder.o \
! sibcall.o conflict.o timevar.o ifcvt.o dominance.o dependence.o dce.o
BACKEND = toplev.o libbackend.a
*************** unroll.o : unroll.c $(CONFIG_H) system.h
*** 1353,1358 ****
--- 1353,1360 ----
flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
insn-flags.h function.h except.h $(EXPR_H) ssa.h
+ dominance.o : dominance.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h \
+ $(BASIC_BLOCK_H)
combine.o : combine.c $(CONFIG_H) system.h $(RTL_H) flags.h function.h \
insn-config.h insn-flags.h insn-codes.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
$(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h
===================================================================
RCS file: RCS/basic-block.h,v
retrieving revision 1.1
diff -p -r1.1 basic-block.h
*** basic-block.h 2000/10/05 19:00:32 1.1
--- basic-block.h 2000/10/05 19:07:36
*************** void verify_edge_list PARAMS ((FILE *,
*** 456,466 ****
int find_edge_index PARAMS ((struct edge_list *,
basic_block, basic_block));
- extern void compute_flow_dominators PARAMS ((sbitmap *, sbitmap *));
- extern void compute_immediate_dominators PARAMS ((int *, sbitmap *));
- extern void compute_immediate_postdominators PARAMS ((int *, sbitmap *));
-
-
enum update_life_extent
{
UPDATE_LIFE_LOCAL = 0,
--- 456,461 ----
*************** extern void conflict_graph_print
*** 560,564 ****
--- 555,563 ----
extern conflict_graph conflict_graph_compute
PARAMS ((regset,
partition));
+
+ /* In dominance.c */
+ extern void calculate_dominance_info PARAMS ((int *, sbitmap *,
+ unsigned int));
#endif /* _BASIC_BLOCK_H */
===================================================================
RCS file: RCS/dce.c,v
retrieving revision 1.1
diff -p -r1.1 dce.c
*** dce.c 2000/10/05 19:00:32 1.1
--- dce.c 2000/10/05 19:16:42
*************** eliminate_dead_code ()
*** 485,491 ****
/* Map element (b,e) is nonzero if the block is control dependent on
edge. "cdbte" abbreviates control dependent block to edge. */
control_dependent_block_to_edge_map cdbte;
- sbitmap *postdominators;
/* Element I is the immediate postdominator of block I. */
int *pdom;
struct edge_list *el;
--- 485,490 ----
*************** eliminate_dead_code ()
*** 504,520 ****
compute_bb_for_insn (max_insn_uid);
/* Compute control dependence. */
- postdominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- compute_flow_dominators (NULL, postdominators);
pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
for (i = 0; i < n_basic_blocks; ++i)
pdom[i] = INVALID_BLOCK;
! compute_immediate_postdominators (pdom, postdominators);
/* Assume there is a path from each node to the exit block. */
for (i = 0; i < n_basic_blocks; ++i)
if (pdom[i] == INVALID_BLOCK)
pdom[i] = EXIT_BLOCK;
- sbitmap_vector_free (postdominators);
el = create_edge_list();
find_all_control_dependences (el, pdom, cdbte);
--- 503,516 ----
compute_bb_for_insn (max_insn_uid);
/* Compute control dependence. */
pdom = (int *) xmalloc (n_basic_blocks * sizeof (int));
for (i = 0; i < n_basic_blocks; ++i)
pdom[i] = INVALID_BLOCK;
! calculate_dominance_info (pdom, NULL, 1);
/* Assume there is a path from each node to the exit block. */
for (i = 0; i < n_basic_blocks; ++i)
if (pdom[i] == INVALID_BLOCK)
pdom[i] = EXIT_BLOCK;
el = create_edge_list();
find_all_control_dependences (el, pdom, cdbte);
===================================================================
RCS file: RCS/flow.c,v
retrieving revision 1.1
diff -p -r1.1 flow.c
*** flow.c 2000/10/05 19:00:32 1.1
--- flow.c 2000/10/05 19:11:06
*************** print_rtl_with_bb (outf, rtx_first)
*** 6177,6426 ****
}
}
- /* Compute dominator relationships using new flow graph structures. */
-
- void
- compute_flow_dominators (dominators, post_dominators)
- sbitmap *dominators;
- sbitmap *post_dominators;
- {
- int bb;
- sbitmap *temp_bitmap;
- edge e;
- basic_block *worklist, *workend, *qin, *qout;
- int qlen;
-
- /* Allocate a worklist array/queue. Entries are only added to the
- list if they were not already on the list. So the size is
- bounded by the number of basic blocks. */
- worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
- workend = &worklist[n_basic_blocks];
-
- temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
-
- if (dominators)
- {
- /* The optimistic setting of dominators requires us to put every
- block on the work list initially. */
- qin = qout = worklist;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- *qin++ = BASIC_BLOCK (bb);
- BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
- }
- qlen = n_basic_blocks;
- qin = worklist;
-
- /* We want a maximal solution, so initially assume everything dominates
- everything else. */
- sbitmap_vector_ones (dominators, n_basic_blocks);
-
- /* Mark successors of the entry block so we can identify them below. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- e->dest->aux = ENTRY_BLOCK_PTR;
-
- /* Iterate until the worklist is empty. */
- while (qlen)
- {
- /* Take the first entry off the worklist. */
- basic_block b = *qout++;
- if (qout >= workend)
- qout = worklist;
- qlen--;
-
- bb = b->index;
-
- /* Compute the intersection of the dominators of all the
- predecessor blocks.
-
- If one of the predecessor blocks is the ENTRY block, then the
- intersection of the dominators of the predecessor blocks is
- defined as the null set. We can identify such blocks by the
- special value in the AUX field in the block structure. */
- if (b->aux == ENTRY_BLOCK_PTR)
- {
- /* Do not clear the aux field for blocks which are
- successors of the ENTRY block. That way we never add
- them to the worklist again.
-
- The intersect of dominators of the preds of this block is
- defined as the null set. */
- sbitmap_zero (temp_bitmap[bb]);
- }
- else
- {
- /* Clear the aux field of this block so it can be added to
- the worklist again if necessary. */
- b->aux = NULL;
- sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
- }
-
- /* Make sure each block always dominates itself. */
- SET_BIT (temp_bitmap[bb], bb);
-
- /* If the out state of this block changed, then we need to
- add the successors of this block to the worklist if they
- are not already on the worklist. */
- if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
- {
- for (e = b->succ; e; e = e->succ_next)
- {
- if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
- {
- *qin++ = e->dest;
- if (qin >= workend)
- qin = worklist;
- qlen++;
-
- e->dest->aux = e;
- }
- }
- }
- }
- }
-
- if (post_dominators)
- {
- /* The optimistic setting of dominators requires us to put every
- block on the work list initially. */
- qin = qout = worklist;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- *qin++ = BASIC_BLOCK (bb);
- BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
- }
- qlen = n_basic_blocks;
- qin = worklist;
-
- /* We want a maximal solution, so initially assume everything post
- dominates everything else. */
- sbitmap_vector_ones (post_dominators, n_basic_blocks);
-
- /* Mark predecessors of the exit block so we can identify them below. */
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- e->src->aux = EXIT_BLOCK_PTR;
-
- /* Iterate until the worklist is empty. */
- while (qlen)
- {
- /* Take the first entry off the worklist. */
- basic_block b = *qout++;
- if (qout >= workend)
- qout = worklist;
- qlen--;
-
- bb = b->index;
-
- /* Compute the intersection of the post dominators of all the
- successor blocks.
-
- If one of the successor blocks is the EXIT block, then the
- intersection of the dominators of the successor blocks is
- defined as the null set. We can identify such blocks by the
- special value in the AUX field in the block structure. */
- if (b->aux == EXIT_BLOCK_PTR)
- {
- /* Do not clear the aux field for blocks which are
- predecessors of the EXIT block. That way we we never
- add them to the worklist again.
-
- The intersect of dominators of the succs of this block is
- defined as the null set. */
- sbitmap_zero (temp_bitmap[bb]);
- }
- else
- {
- /* Clear the aux field of this block so it can be added to
- the worklist again if necessary. */
- b->aux = NULL;
- sbitmap_intersection_of_succs (temp_bitmap[bb],
- post_dominators, bb);
- }
-
- /* Make sure each block always post dominates itself. */
- SET_BIT (temp_bitmap[bb], bb);
-
- /* If the out state of this block changed, then we need to
- add the successors of this block to the worklist if they
- are not already on the worklist. */
- if (sbitmap_a_and_b (post_dominators[bb],
- post_dominators[bb],
- temp_bitmap[bb]))
- {
- for (e = b->pred; e; e = e->pred_next)
- {
- if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
- {
- *qin++ = e->src;
- if (qin >= workend)
- qin = worklist;
- qlen++;
-
- e->src->aux = e;
- }
- }
- }
- }
- }
-
- free (worklist);
- free (temp_bitmap);
- }
-
- /* Given DOMINATORS, compute the immediate dominators into IDOM. If a
- block dominates only itself, its entry remains as INVALID_BLOCK. */
-
- void
- compute_immediate_dominators (idom, dominators)
- int *idom;
- sbitmap *dominators;
- {
- sbitmap *tmp;
- int b;
-
- tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-
- /* Begin with tmp(n) = dom(n) - { n }. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- sbitmap_copy (tmp[b], dominators[b]);
- RESET_BIT (tmp[b], b);
- }
-
- /* Subtract out all of our dominator's dominators. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- sbitmap tmp_b = tmp[b];
- int s;
-
- for (s = n_basic_blocks; --s >= 0;)
- if (TEST_BIT (tmp_b, s))
- sbitmap_difference (tmp_b, tmp_b, tmp[s]);
- }
-
- /* Find the one bit set in the bitmap and put it in the output array. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- int t;
- EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
- }
-
- sbitmap_vector_free (tmp);
- }
-
- /* Given POSTDOMINATORS, compute the immediate postdominators into
- IDOM. If a block is only dominated by itself, its entry remains as
- INVALID_BLOCK. */
-
- void
- compute_immediate_postdominators (idom, postdominators)
- int *idom;
- sbitmap *postdominators;
- {
- compute_immediate_dominators (idom, postdominators);
- }
-
/* Recompute register set/reference counts immediately prior to register
allocation.
--- 6177,6182 ----
*************** flow_loops_find (loops, flags)
*** 8071,8077 ****
/* Compute the dominators. */
dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
! compute_flow_dominators (dom, NULL);
/* Count the number of loop edges (back edges). This should be the
same as the number of natural loops. */
--- 7827,7833 ----
/* Compute the dominators. */
dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
! calculate_dominance_info (NULL, dom, 0);
/* Count the number of loop edges (back edges). This should be the
same as the number of natural loops. */
===================================================================
RCS file: RCS/gcse.c,v
retrieving revision 1.1
diff -p -r1.1 gcse.c
*** gcse.c 2000/10/05 19:00:32 1.1
--- gcse.c 2000/10/05 19:11:39
*************** compute_code_hoist_data ()
*** 5291,5297 ****
compute_local_properties (transp, comp, antloc, 0);
compute_transpout ();
compute_code_hoist_vbeinout ();
! compute_flow_dominators (dominators, NULL);
if (gcse_file)
fprintf (gcse_file, "\n");
}
--- 5291,5297 ----
compute_local_properties (transp, comp, antloc, 0);
compute_transpout ();
compute_code_hoist_vbeinout ();
! calculate_dominance_info (NULL, dominators, 0);
if (gcse_file)
fprintf (gcse_file, "\n");
}
===================================================================
RCS file: RCS/haifa-sched.c,v
retrieving revision 1.1
diff -p -r1.1 haifa-sched.c
*** haifa-sched.c 2000/10/05 19:00:32 1.1
--- haifa-sched.c 2000/10/05 19:12:28
*************** schedule_insns (dump_file)
*** 6897,6903 ****
/* Compute the dominators and post dominators. We don't
currently use post dominators, but we should for
speculative motion analysis. */
! compute_flow_dominators (dom, NULL);
/* build_control_flow will return nonzero if it detects unreachable
blocks or any other irregularity with the cfg which prevents
--- 6897,6903 ----
/* Compute the dominators and post dominators. We don't
currently use post dominators, but we should for
speculative motion analysis. */
! calculate_dominance_info (NULL, dom, 0);
/* build_control_flow will return nonzero if it detects unreachable
blocks or any other irregularity with the cfg which prevents
===================================================================
RCS file: RCS/ifcvt.c,v
retrieving revision 1.1
diff -p -r1.1 ifcvt.c
*** ifcvt.c 2000/10/05 19:00:32 1.1
--- ifcvt.c 2000/10/05 19:12:54
*************** if_convert (life_data_ok)
*** 2104,2110 ****
if (HAVE_conditional_execution || life_data_ok)
{
post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
! compute_flow_dominators (NULL, post_dominators);
}
/* Record initial block numbers. */
--- 2104,2110 ----
if (HAVE_conditional_execution || life_data_ok)
{
post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
! calculate_dominance_info (NULL, post_dominators, 1);
}
/* Record initial block numbers. */
===================================================================
RCS file: RCS/ssa.c,v
retrieving revision 1.1
diff -p -r1.1 ssa.c
*** ssa.c 2000/10/05 19:00:32 1.1
--- ssa.c 2000/10/05 19:14:03
*************** convert_to_ssa ()
*** 1148,1154 ****
sbitmap *evals;
/* Dominator bitmaps. */
- sbitmap *dominators;
sbitmap *dfs;
sbitmap *idfs;
--- 1148,1153 ----
*************** convert_to_ssa ()
*** 1165,1178 ****
life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
/* Compute dominators. */
- dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- compute_flow_dominators (dominators, NULL);
-
idom = (int *) alloca (n_basic_blocks * sizeof (int));
memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
! compute_immediate_dominators (idom, dominators);
!
! sbitmap_vector_free (dominators);
if (rtl_dump_file)
{
--- 1164,1172 ----
life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
/* Compute dominators. */
idom = (int *) alloca (n_basic_blocks * sizeof (int));
memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
! calculate_dominance_info (idom, NULL, 0);
if (rtl_dump_file)
{
More information about the Gcc-patches
mailing list