This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Move compute_dominance_frontiers to cfganal.c
- From: Steven Bosscher <stevenb at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 18 Aug 2004 22:50:31 +0200
- Subject: Move compute_dominance_frontiers to cfganal.c
- Organization: SUSE Labs
Hi,
If there are no objections, I'm going to apply the following
patch as obvious. It simply moves compute_dominance_frontiers
to a more appropriate place.
Gr.
Steven
* Makefile.in (cfganal.o): Depend on TIMEVAR_H.
* tree-flow.h (compute_dominance_frontiers): Move prototype...
* basic-block.h: ...here.
* tree-cfg.c (compute_dominance_frontiers_1,
compute_dominance_frontiers): Move from here...
* cfganal.c: ...to here. Include timevar.h.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1350
diff -c -3 -p -r1.1350 Makefile.in
*** Makefile.in 18 Aug 2004 16:21:42 -0000 1.1350
--- Makefile.in 18 Aug 2004 20:44:46 -0000
*************** cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM
*** 1970,1976 ****
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(EXPR_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
! $(BASIC_BLOCK_H) hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(FLAGS_H) \
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H)
--- 1970,1977 ----
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(EXPR_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
! $(BASIC_BLOCK_H) hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H) \
! $(TIMEVAR_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(FLAGS_H) \
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H)
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.205
diff -c -3 -p -r1.205 basic-block.h
*** basic-block.h 4 Aug 2004 21:37:03 -0000 1.205
--- basic-block.h 18 Aug 2004 20:44:46 -0000
*************** extern void flow_preorder_transversal_co
*** 444,449 ****
--- 444,450 ----
extern int dfs_enumerate_from (basic_block, int,
bool (*)(basic_block, void *),
basic_block *, int, void *);
+ extern void compute_dominance_frontiers (bitmap *);
extern void dump_edge_info (FILE *, edge, int);
extern void brief_dump_cfg (FILE *);
extern void clear_edges (void);
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.46
diff -c -3 -p -r1.46 cfganal.c
*** cfganal.c 16 Jul 2004 22:28:27 -0000 1.46
--- cfganal.c 18 Aug 2004 20:44:47 -0000
*************** Software Foundation, 59 Temple Place - S
*** 31,36 ****
--- 31,37 ----
#include "recog.h"
#include "toplev.h"
#include "tm_p.h"
+ #include "timevar.h"
/* Store the data structures necessary for depth-first search. */
struct depth_first_search_dsS {
*************** dfs_enumerate_from (basic_block bb, int
*** 1041,1043 ****
--- 1042,1122 ----
rslt[sp]->flags &= ~BB_VISITED;
return tv;
}
+
+
+ /* Computing the Dominance Frontier:
+
+ As described in Morgan, section 3.5, this may be done simply by
+ walking the dominator tree bottom-up, computing the frontier for
+ the children before the parent. When considering a block B,
+ there are two cases:
+
+ (1) A flow graph edge leaving B that does not lead to a child
+ of B in the dominator tree must be a block that is either equal
+ to B or not dominated by B. Such blocks belong in the frontier
+ of B.
+
+ (2) Consider a block X in the frontier of one of the children C
+ of B. If X is not equal to B and is not dominated by B, it
+ is in the frontier of B. */
+
+ static void
+ compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
+ {
+ edge e;
+ basic_block c;
+
+ SET_BIT (done, bb->index);
+
+ /* Do the frontier of the children first. Not all children in the
+ dominator tree (blocks dominated by this one) are children in the
+ CFG, so check all blocks. */
+ for (c = first_dom_son (CDI_DOMINATORS, bb);
+ c;
+ c = next_dom_son (CDI_DOMINATORS, c))
+ {
+ if (! TEST_BIT (done, c->index))
+ compute_dominance_frontiers_1 (frontiers, c, done);
+ }
+
+ /* Find blocks conforming to rule (1) above. */
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
+ bitmap_set_bit (frontiers[bb->index], e->dest->index);
+ }
+
+ /* Find blocks conforming to rule (2). */
+ for (c = first_dom_son (CDI_DOMINATORS, bb);
+ c;
+ c = next_dom_son (CDI_DOMINATORS, c))
+ {
+ int x;
+
+ EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x,
+ {
+ if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
+ bitmap_set_bit (frontiers[bb->index], x);
+ });
+ }
+ }
+
+
+ void
+ compute_dominance_frontiers (bitmap *frontiers)
+ {
+ sbitmap done = sbitmap_alloc (last_basic_block);
+
+ timevar_push (TV_DOM_FRONTIERS);
+
+ sbitmap_zero (done);
+
+ compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done);
+
+ sbitmap_free (done);
+
+ timevar_pop (TV_DOM_FRONTIERS);
+ }
+
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.40
diff -c -3 -p -r2.40 tree-cfg.c
*** tree-cfg.c 10 Aug 2004 18:31:25 -0000 2.40
--- tree-cfg.c 18 Aug 2004 20:44:52 -0000
*************** phi_alternatives_equal (basic_block dest
*** 2171,2254 ****
}
- /* Computing the Dominance Frontier:
-
- As described in Morgan, section 3.5, this may be done simply by
- walking the dominator tree bottom-up, computing the frontier for
- the children before the parent. When considering a block B,
- there are two cases:
-
- (1) A flow graph edge leaving B that does not lead to a child
- of B in the dominator tree must be a block that is either equal
- to B or not dominated by B. Such blocks belong in the frontier
- of B.
-
- (2) Consider a block X in the frontier of one of the children C
- of B. If X is not equal to B and is not dominated by B, it
- is in the frontier of B. */
-
- static void
- compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
- {
- edge e;
- basic_block c;
-
- SET_BIT (done, bb->index);
-
- /* Do the frontier of the children first. Not all children in the
- dominator tree (blocks dominated by this one) are children in the
- CFG, so check all blocks. */
- for (c = first_dom_son (CDI_DOMINATORS, bb);
- c;
- c = next_dom_son (CDI_DOMINATORS, c))
- {
- if (! TEST_BIT (done, c->index))
- compute_dominance_frontiers_1 (frontiers, c, done);
- }
-
- /* Find blocks conforming to rule (1) above. */
- for (e = bb->succ; e; e = e->succ_next)
- {
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
- if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
- bitmap_set_bit (frontiers[bb->index], e->dest->index);
- }
-
- /* Find blocks conforming to rule (2). */
- for (c = first_dom_son (CDI_DOMINATORS, bb);
- c;
- c = next_dom_son (CDI_DOMINATORS, c))
- {
- int x;
-
- EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x,
- {
- if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
- bitmap_set_bit (frontiers[bb->index], x);
- });
- }
- }
-
-
- void
- compute_dominance_frontiers (bitmap *frontiers)
- {
- sbitmap done = sbitmap_alloc (last_basic_block);
-
- timevar_push (TV_DOM_FRONTIERS);
-
- sbitmap_zero (done);
-
- compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done);
-
- sbitmap_free (done);
-
- timevar_pop (TV_DOM_FRONTIERS);
- }
-
-
-
/*---------------------------------------------------------------------------
Debugging functions
---------------------------------------------------------------------------*/
--- 2171,2176 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.35
diff -c -3 -p -r2.35 tree-flow.h
*** tree-flow.h 18 Aug 2004 18:21:22 -0000 2.35
--- tree-flow.h 18 Aug 2004 20:44:53 -0000
*************** extern void bsi_insert_on_edge (edge, tr
*** 489,495 ****
extern void bsi_commit_edge_inserts (int *);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
- extern void compute_dominance_frontiers (bitmap *);
extern void verify_stmts (void);
extern tree tree_block_label (basic_block bb);
extern void extract_true_false_edges_from_block (basic_block, edge *, edge *);
--- 489,494 ----