This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
cfg merge part 24 - real datastructure for dominance information.
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com,gcc-pdo at atrey dot karlin dot mff dot cuni dot cz,Pavel Nejedly <bim at atrey dot karlin dot mff dot cuni dot cz>
- Date: Wed, 12 Jun 2002 20:38:21 +0200
- Subject: cfg merge part 24 - real datastructure for dominance information.
Hi,
this patch adds new datastructure for dominance information. The underlying
datstructure has been implemented by Pavel and supports logarithmic updating of
the structure as well as polylogarithmic lookup of nearest common ancestor that
is important for the new loop duplication code.
The patch has been bootstrapped on mainline on i386 and on the branch i386/sparc.
Also it shown no perofrmance degradation on the daily tester.
On peak runs (with unrolling) it shows little speedup, but the main
point of the patch is the ABI and to avoid deadly worst case scenarios.
Honza
Mon Jun 10 20:42:34 CEST 2002 Jan Hubicka <jh@suse.cz>
Pavel Nejedly <bim@atrey.karlin.mff.cuni.cz>
Mon Jun 10 20:42:34 CEST 2002 Jan Hubicka <jh@suse.cz>
* basic-block.h: Do not include et-forest.h
(dominance_info): Declare as struct dominance-info.
* cfglayout.c (cleanup_unconditional_jumps): Remove the edge before
deleting block.
* dominance.c (struct dominance_info): Define.
(BB_NODE, SET_BB_NODE): New macros.
(bb_hash_func, bb_eq_func): Kill.
(calculate_dominace_info, free_dominacne_info, set_immediate_dominator,
nearest_common_dominator, dominated_by_p, recount_dominator,
add_to_dominance_info, delete_from_dominance_info): update for new
representation.
(get_dominated_by, redirect_immediate_dominators): Rewrite using enumerate_sons.
* ifcvt.c (process_double_test_block, merge_if_block, find_cond_trap,
find_if_case_1, find_if_case_2): Remove killed blocks from dominance structure.
* et-forest.h: Update copyright; revamp all function to operate on
nodes
(et_forest_value): Kill.
(et_forest_enumerate_sons, et_forest_node_value): New.
* et-forest.c: Update copyright.
* et-forest.h: Update copyright; revamp all function to operate on
nodes
(et_forest_value): Kill.
(et_forest_enumerate_sons, et_forest_node_value): New.
Thu Jun 6 22:43:43 CEST 2002 Jan Hubicka <jh@suse.cz>
* basic-block.h: Inlude et-forest.h
(basic_block_def): Kill dominator.
(dominance_info): New type.
(loops): Use dominace_info.
(dominace handling functions): Take dominace_info as argument
instead of bitmaps.
(create_preheader): Likewise.
* cfg.c (entry_exit_blocks): Kill dominator.
(dump_flow_info): Do not dump dominators.
* cfglayout.c (cleanup_unconditonal_jumps): Delete deleted block from
dominators.
* cfgloop.c (flow_pre_header_find): Use dominacne_info.
(flow_loops_pre_header_scan, make_forwarder_block,
canonicale_loop_headers, flow_loops_find): Likewise.
* dominance.c: Include error.h
(idoms_to_doms): Kill.
(bb_hash_func, bb_eq_func): New static functions.
(debug_dominace_info): New global function.
(calculate_dominance_info): Use new et forest structure.
(free_dominace_info, get_immediate_dominator, set_immediate_dominator,
get_dominated_by, redirect_immediate_dominators,
nearest_common_dominator, dominated_by_p, verify_dominators,
recount_dominator, iterate_fix_dominators, add_to_dominace_info,
delete_from_dominance_info): New global functions.
* gcse.c (domnators): CHange to dominance_info.
(alloc_hoist_mem): Do not alloc dominators
(free_code_hoist_mem): Use free_dominance_info.
(compute_code_hoist_data): Use dominance_info.
(hoist_code): Likewise.
* ifcvt.c (post_dominators): Likewise.
(find_if_case_2, if_convert): Likewise.
* predict.c (process_note_predictions, process_note_prediction,
estimate-probability): Likewise.
* sched-rgn.c (find_rgns, init_regions): Likewise.
* ssa-dce.c (find_all_control_dependences, fint_control_depemndence,
find_pdom, delete_insn_bb, ssa_eliminate_dead_code): Likewise.
* ssa.c (compute_dominance_frontiers_1, rename_block, rename_registers,
find_evaluations, convert_to_ssa): Likewise.
* ssa.h (compute_dominance_frontiers): Likewise.
Thu Jun 6 22:57:34 CEST 2002 Pavel Nejedly <bim@atrey.karlin.mff.cuni.cz>
* Makefile.in (et-forest.c): Add.
* et-forest.c: New file.
* at-forest.h: New file.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.899
diff -c -3 -p -r1.899 Makefile.in
*** Makefile.in 11 Jun 2002 20:06:04 -0000 1.899
--- Makefile.in 12 Jun 2002 18:20:01 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 735,741 ****
sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
! $(GGC) $(out_object_file) $(EXTRA_OBJS)
BACKEND = main.o libbackend.a
--- 735,741 ----
sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
! et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
BACKEND = main.o libbackend.a
*************** cfgcleanup.o : cfgcleanup.c $(CONFIG_H)
*** 1538,1544 ****
cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.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_ATTR_H) $(REGS_H) $(EXPR_H) \
$(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h $(TM_P_H)
--- 1538,1545 ----
cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h
dominance.o : dominance.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
! $(BASIC_BLOCK_H) et-forest.h
! et-forest.o : et-forest.c $(CONFIG_H) $(SYSTEM_H) et-forest.h
combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h function.h \
insn-config.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
$(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h $(TM_P_H)
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.153
diff -c -3 -p -r1.153 basic-block.h
*** basic-block.h 10 Jun 2002 22:33:06 -0000 1.153
--- basic-block.h 12 Jun 2002 18:20:01 -0000
*************** extern void clear_edges PARAMS ((void)
*** 350,355 ****
--- 350,359 ----
extern void mark_critical_edges PARAMS ((void));
extern rtx first_insn_after_basic_block_note PARAMS ((basic_block));
+ /* Dominator information for basic blocks. */
+
+ typedef struct dominance_info *dominance_info;
+
/* Structure to hold information for each natural loop. */
struct loop
{
*************** struct loops
*** 498,504 ****
struct cfg
{
/* The bitmap vector of dominators or NULL if not computed. */
! sbitmap *dom;
/* The ordering of the basic blocks in a depth first search. */
int *dfs_order;
--- 502,508 ----
struct cfg
{
/* The bitmap vector of dominators or NULL if not computed. */
! dominance_info dom;
/* The ordering of the basic blocks in a depth first search. */
int *dfs_order;
*************** enum cdi_direction
*** 770,776 ****
CDI_POST_DOMINATORS
};
! extern void calculate_dominance_info PARAMS ((int *, sbitmap *,
! enum cdi_direction));
!
#endif /* GCC_BASIC_BLOCK_H */
--- 774,794 ----
CDI_POST_DOMINATORS
};
! extern dominance_info calculate_dominance_info PARAMS ((enum cdi_direction));
! extern void free_dominance_info PARAMS ((dominance_info));
! extern basic_block nearest_common_dominator PARAMS ((dominance_info,
! basic_block, basic_block));
! extern void set_immediate_dominator PARAMS ((dominance_info,
! basic_block, basic_block));
! extern basic_block get_immediate_dominator PARAMS ((dominance_info,
! basic_block));
! extern bool dominated_by_p PARAMS ((dominance_info, basic_block, basic_block));
! extern int get_dominated_by PARAMS ((dominance_info, basic_block, basic_block **));
! extern void add_to_dominance_info PARAMS ((dominance_info, basic_block));
! extern void delete_from_dominance_info PARAMS ((dominance_info, basic_block));
! basic_block recount_dominator PARAMS ((dominance_info, basic_block));
! extern void redirect_immediate_dominators PARAMS ((dominance_info, basic_block,
! basic_block));
! void iterate_fix_dominators PARAMS ((dominance_info, basic_block *, int));
! extern void verify_dominators PARAMS ((dominance_info));
#endif /* GCC_BASIC_BLOCK_H */
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgloop.c,v
retrieving revision 1.14
diff -c -3 -p -r1.14 cfgloop.c
*** cfgloop.c 1 Jun 2002 09:24:41 -0000 1.14
--- cfgloop.c 12 Jun 2002 18:20:01 -0000
*************** static void flow_loop_exit_edges_find PA
*** 36,42 ****
static int flow_loop_nodes_find PARAMS ((basic_block, struct loop *));
static void flow_loop_pre_header_scan PARAMS ((struct loop *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
! const sbitmap *));
static int flow_loop_level_compute PARAMS ((struct loop *));
static int flow_loops_level_compute PARAMS ((struct loops *));
static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
--- 36,42 ----
static int flow_loop_nodes_find PARAMS ((basic_block, struct loop *));
static void flow_loop_pre_header_scan PARAMS ((struct loop *));
static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
! dominance_info));
static int flow_loop_level_compute PARAMS ((struct loop *));
static int flow_loops_level_compute PARAMS ((struct loops *));
static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
*************** flow_loops_free (loops)
*** 224,230 ****
loops->parray = NULL;
if (loops->cfg.dom)
! sbitmap_vector_free (loops->cfg.dom);
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
--- 224,230 ----
loops->parray = NULL;
if (loops->cfg.dom)
! free_dominance_info (loops->cfg.dom);
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
*************** flow_loop_pre_header_scan (loop)
*** 415,421 ****
static basic_block
flow_loop_pre_header_find (header, dom)
basic_block header;
! const sbitmap *dom;
{
basic_block pre_header;
edge e;
--- 415,421 ----
static basic_block
flow_loop_pre_header_find (header, dom)
basic_block header;
! dominance_info dom;
{
basic_block pre_header;
edge e;
*************** flow_loop_pre_header_find (header, dom)
*** 428,434 ****
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
! && ! TEST_BIT (dom[node->index], header->index))
{
if (pre_header == NULL)
pre_header = node;
--- 428,434 ----
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
! && ! dominated_by_p (dom, node, header))
{
if (pre_header == NULL)
pre_header = node;
*************** make_forwarder_block (bb, redirect_latch
*** 645,657 ****
static void
canonicalize_loop_headers ()
{
! sbitmap *dom;
basic_block header;
edge e;
/* Compute the dominators. */
! dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
! calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
alloc_aux_for_blocks (sizeof (int));
alloc_aux_for_edges (sizeof (int));
--- 645,656 ----
static void
canonicalize_loop_headers ()
{
! dominance_info dom;
basic_block header;
edge e;
/* Compute the dominators. */
! dom = calculate_dominance_info (CDI_DOMINATORS);
alloc_aux_for_blocks (sizeof (int));
alloc_aux_for_edges (sizeof (int));
*************** canonicalize_loop_headers ()
*** 670,676 ****
have_abnormal_edge = 1;
if (latch != ENTRY_BLOCK_PTR
! && TEST_BIT (dom[latch->index], header->index))
{
num_latches++;
LATCH_EDGE (e) = 1;
--- 669,675 ----
have_abnormal_edge = 1;
if (latch != ENTRY_BLOCK_PTR
! && dominated_by_p (dom, latch, header))
{
num_latches++;
LATCH_EDGE (e) = 1;
*************** canonicalize_loop_headers ()
*** 747,753 ****
free_aux_for_blocks ();
free_aux_for_edges ();
! sbitmap_vector_free (dom);
}
/* Find all the natural loops in the function and save in LOOPS structure and
--- 746,752 ----
free_aux_for_blocks ();
free_aux_for_edges ();
! free_dominance_info (dom);
}
/* Find all the natural loops in the function and save in LOOPS structure and
*************** flow_loops_find (loops, flags)
*** 765,774 ****
int num_loops;
edge e;
sbitmap headers;
! sbitmap *dom;
int *dfs_order;
int *rc_order;
! basic_block header, bb;
/* This function cannot be repeatedly called with different
flags to build up the loop information. The loop tree
--- 764,774 ----
int num_loops;
edge e;
sbitmap headers;
! dominance_info dom;
int *dfs_order;
int *rc_order;
! basic_block header;
! basic_block bb;
/* This function cannot be repeatedly called with different
flags to build up the loop information. The loop tree
*************** flow_loops_find (loops, flags)
*** 790,797 ****
canonicalize_loop_headers ();
/* Compute the dominators. */
! loops->cfg.dom = dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
! calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
/* Count the number of loop headers. This should be the
same as the number of natural loops. */
--- 790,796 ----
canonicalize_loop_headers ();
/* Compute the dominators. */
! dom = loops->cfg.dom = calculate_dominance_info (CDI_DOMINATORS);
/* Count the number of loop headers. This should be the
same as the number of natural loops. */
*************** flow_loops_find (loops, flags)
*** 824,831 ****
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
from a latch node. */
! if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index],
! header->index))
{
/* Shared headers should be eliminated by now. */
if (more_latches)
--- 823,829 ----
node (header) that dominates all the nodes in the
loop. It also has single back edge to the header
from a latch node. */
! if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header))
{
/* Shared headers should be eliminated by now. */
if (more_latches)
*************** flow_loops_find (loops, flags)
*** 899,905 ****
basic_block latch = e->src;
if (latch != ENTRY_BLOCK_PTR
! && TEST_BIT (dom[latch->index], header->index))
{
loop->latch = latch;
break;
--- 897,903 ----
basic_block latch = e->src;
if (latch != ENTRY_BLOCK_PTR
! && dominated_by_p (dom, latch, header))
{
loop->latch = latch;
break;
*************** flow_loops_find (loops, flags)
*** 925,931 ****
else
{
loops->cfg.dom = NULL;
! sbitmap_vector_free (dom);
}
#ifdef ENABLE_CHECKING
verify_flow_info ();
--- 923,929 ----
else
{
loops->cfg.dom = NULL;
! free_dominance_info (dom);
}
#ifdef ENABLE_CHECKING
verify_flow_info ();
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/dominance.c,v
retrieving revision 1.10
diff -c -3 -p -r1.10 dominance.c
*** dominance.c 27 May 2002 13:45:19 -0000 1.10
--- dominance.c 12 Jun 2002 18:20:02 -0000
***************
*** 38,44 ****
--- 38,56 ----
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+ #include "error.h"
+ #include "et-forest.h"
+ struct dominance_info
+ {
+ et_forest_t forest;
+ varray_type varray;
+ };
+
+ #define BB_NODE(info, bb) \
+ ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
+ #define SET_BB_NODE(info, bb, node) \
+ (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
/* We name our nodes with integers, beginning with 1. Zero is reserved for
'undefined' or 'end of list'. The name of each node is given by the dfs
*************** static TBB eval PARAMS ((struct dom_i
*** 113,120 ****
static void link_roots PARAMS ((struct dom_info *, TBB, TBB));
static void calc_idoms PARAMS ((struct dom_info *,
enum cdi_direction));
! static void idoms_to_doms PARAMS ((struct dom_info *,
! sbitmap *));
/* Helper macro for allocating and initializing an array,
for aesthetic reasons. */
--- 125,131 ----
static void link_roots PARAMS ((struct dom_info *, TBB, TBB));
static void calc_idoms PARAMS ((struct dom_info *,
enum cdi_direction));
! void debug_dominance_info PARAMS ((dominance_info));
/* Helper macro for allocating and initializing an array,
for aesthetic reasons. */
*************** calc_idoms (di, reverse)
*** 531,580 ****
di->dom[v] = di->dom[di->dom[v]];
}
- /* Convert the information about immediate dominators (in DI) to sets of all
- dominators (in DOMINATORS). */
-
- static void
- idoms_to_doms (di, dominators)
- struct dom_info *di;
- sbitmap *dominators;
- {
- TBB i, e_index;
- int bb, bb_idom;
- sbitmap_vector_zero (dominators, last_basic_block);
- /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK
- in the list of (post)-doms, so remember that in e_index. */
- e_index = di->dfs_order[last_basic_block];
-
- for (i = 1; i <= di->nodes; i++)
- {
- if (i == e_index)
- continue;
- bb = di->dfs_to_bb[i]->index;
-
- if (di->dom[i] && (di->dom[i] != e_index))
- {
- bb_idom = di->dfs_to_bb[di->dom[i]]->index;
- sbitmap_copy (dominators[bb], dominators[bb_idom]);
- }
- else
- {
- /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
- If it is a child of ENTRY_BLOCK that's OK, and it's only
- dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
- means, it is unreachable. That case has been disallowed in the
- building of the DFS tree, so we are save here. For the reverse
- flow graph it means, it has no children, so, to be compatible
- with the old code, we set the post_dominators to all one. */
- if (!di->dom[i])
- {
- sbitmap_ones (dominators[bb]);
- }
- }
- SET_BIT (dominators[bb], bb);
- }
- }
-
/* The main entry point into this module. IDOM is an integer array with room
for last_basic_block integers, DOMS is a preallocated sbitmap array having
room for last_basic_block^2 bits, and POST is true if the caller wants to
--- 542,547 ----
*************** idoms_to_doms (di, dominators)
*** 587,623 ****
Either IDOM or DOMS may be NULL (meaning the caller is not interested in
immediate resp. all dominators). */
! void
! calculate_dominance_info (idom, doms, reverse)
! int *idom;
! sbitmap *doms;
enum cdi_direction reverse;
{
struct dom_info di;
- if (!doms && !idom)
- return;
init_dom_info (&di);
calc_dfs_tree (&di, reverse);
calc_idoms (&di, reverse);
! if (idom)
{
! basic_block b;
! FOR_EACH_BB (b)
{
! TBB d = di.dom[di.dfs_order[b->index]];
! /* The old code didn't modify array elements of nodes having only
! itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK)
! (d==1). */
! if (d > 1)
! idom[b->index] = di.dfs_to_bb[d]->index;
}
}
! if (doms)
! idoms_to_doms (&di, doms);
! free_dom_info (&di);
}
--- 554,812 ----
Either IDOM or DOMS may be NULL (meaning the caller is not interested in
immediate resp. all dominators). */
! dominance_info
! calculate_dominance_info (reverse)
enum cdi_direction reverse;
{
struct dom_info di;
+ dominance_info info;
+ basic_block b;
+
+ /* allocate structure for dominance information. */
+ info = xmalloc (sizeof (struct dominance_info));
+ info->forest = et_forest_create ();
+ VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
+
+ /* Add the two well-known basic blocks. */
+ SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
+ ENTRY_BLOCK_PTR));
+ SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
+ EXIT_BLOCK_PTR));
+ FOR_EACH_BB (b)
+ SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
init_dom_info (&di);
calc_dfs_tree (&di, reverse);
calc_idoms (&di, reverse);
!
! FOR_EACH_BB (b)
{
! TBB d = di.dom[di.dfs_order[b->index]];
!
! if (di.dfs_to_bb[d])
! et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
! }
!
! free_dom_info (&di);
! return info;
! }
!
! /* Free dominance information. */
! void
! free_dominance_info (info)
! dominance_info info;
! {
! basic_block bb;
!
! /* Allow users to create new basic block without setting up the dominance
! information for them. */
! FOR_EACH_BB (bb)
! if (bb->index < (int)(info->varray->num_elements - 2)
! && BB_NODE (info, bb))
! delete_from_dominance_info (info, bb);
! delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
! delete_from_dominance_info (info, EXIT_BLOCK_PTR);
! et_forest_delete (info->forest);
! VARRAY_GROW (info->varray, 0);
! free (info);
! }
!
! /* Return the immediate dominator of basic block BB. */
! basic_block
! get_immediate_dominator (dom, bb)
! dominance_info dom;
! basic_block bb;
! {
! return et_forest_node_value (dom->forest,
! et_forest_parent (dom->forest,
! BB_NODE (dom, bb)));
! }
!
! /* Set the immediate dominator of the block possibly removing
! existing edge. NULL can be used to remove any edge. */
! inline void
! set_immediate_dominator (dom, bb, dominated_by)
! dominance_info dom;
! basic_block bb, dominated_by;
! {
! void *aux_bb_node;
! et_forest_node_t bb_node = BB_NODE (dom, bb);
!
! aux_bb_node = et_forest_parent (dom->forest, bb_node);
! if (aux_bb_node)
! et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
! if (dominated_by != NULL)
! {
! if (bb == dominated_by)
! abort ();
! if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
! abort ();
! }
! }
!
! /* Store all basic blocks dominated by BB into BBS and return their number. */
! int
! get_dominated_by (dom, bb, bbs)
! dominance_info dom;
! basic_block bb;
! basic_block **bbs;
! {
! int n, i;
!
! *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
! n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
! for (i = 0; i < n; i++)
! (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
! return n;
! }
!
! /* Redirect all edges pointing to BB to TO. */
! void
! redirect_immediate_dominators (dom, bb, to)
! dominance_info dom;
! basic_block bb;
! basic_block to;
! {
! et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
! et_forest_node_t node = BB_NODE (dom, bb);
! et_forest_node_t node2 = BB_NODE (dom, to);
! int n = et_forest_enumerate_sons (dom->forest, node, bbs);
! int i;
!
! for (i = 0; i < n; i++)
! {
! et_forest_remove_edge (dom->forest, node, bbs[i]);
! et_forest_add_edge (dom->forest, node2, bbs[i]);
! }
! free (bbs);
! }
!
! /* Find first basic block in the tree dominating both BB1 and BB2. */
! basic_block
! nearest_common_dominator (dom, bb1, bb2)
! dominance_info dom;
! basic_block bb1;
! basic_block bb2;
! {
! if (!bb1)
! return bb2;
! if (!bb2)
! return bb1;
! return et_forest_node_value (dom->forest,
! et_forest_common_ancestor (dom->forest,
! BB_NODE (dom, bb1),
! BB_NODE (dom,
! bb2)));
! }
!
! /* Return TRUE in case BB1 is dominated by BB2. */
! bool
! dominated_by_p (dom, bb1, bb2)
! dominance_info dom;
! basic_block bb1;
! basic_block bb2;
! {
! return nearest_common_dominator (dom, bb1, bb2) == bb2;
! }
!
! /* Verify invariants of dominator structure. */
! void
! verify_dominators (dom)
! dominance_info dom;
! {
! int err = 0;
! basic_block bb;
!
! FOR_EACH_BB (bb)
! {
! basic_block dom_bb;
! dom_bb = recount_dominator (dom, bb);
! if (dom_bb != get_immediate_dominator (dom, bb))
{
! error ("dominator of %d should be %d, not %d",
! bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
! err = 1;
! }
! }
! if (err)
! abort ();
! }
!
! /* Recount dominator of BB. */
! basic_block
! recount_dominator (dom, bb)
! dominance_info dom;
! basic_block bb;
! {
! basic_block dom_bb = NULL;
! edge e;
!
! for (e = bb->pred; e; e = e->pred_next)
! {
! if (!dominated_by_p (dom, e->src, bb))
! dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
! }
! return dom_bb;
! }
!
! /* Iteratively recount dominators of BBS. The change is supposed to be local
! and not to grow further. */
! void
! iterate_fix_dominators (dom, bbs, n)
! dominance_info dom;
! basic_block *bbs;
! int n;
! {
! int i, changed = 1;
! basic_block old_dom, new_dom;
!
! while (changed)
! {
! changed = 0;
! for (i = 0; i < n; i++)
! {
! old_dom = get_immediate_dominator (dom, bbs[i]);
! new_dom = recount_dominator (dom, bbs[i]);
! if (old_dom != new_dom)
! {
! changed = 1;
! set_immediate_dominator (dom, bbs[i], new_dom);
! }
}
}
! }
! void
! add_to_dominance_info (dom, bb)
! dominance_info dom;
! basic_block bb;
! {
! VARRAY_GROW (dom->varray, last_basic_block + 3);
! #ifdef ENABLE_CHECKING
! if (BB_NODE (dom, bb))
! abort ();
! #endif
! SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
! }
!
! void
! delete_from_dominance_info (dom, bb)
! dominance_info dom;
! basic_block bb;
! {
! et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
! SET_BB_NODE (dom, bb, NULL);
! }
!
! void
! debug_dominance_info (dom)
! dominance_info dom;
! {
! basic_block bb, bb2;
! FOR_EACH_BB (bb)
! if ((bb2 = get_immediate_dominator (dom, bb)))
! fprintf (stderr, "%i %i\n", bb->index, bb2->index);
}
Index: et-forest.c
===================================================================
RCS file: et-forest.c
diff -N et-forest.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- et-forest.c 12 Jun 2002 18:20:02 -0000
***************
*** 0 ****
--- 1,670 ----
+ /* ET-trees datastructure implementation.
+ Contributed by Pavel Nejedly
+ Copyright (C) 2002 Free Software Foundation, Inc.
+
+ This file is part of the libiberty library.
+ Libiberty is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ Libiberty is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public
+ License along with libiberty; see the file COPYING.LIB. If
+ not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "et-forest.h"
+
+ struct et_forest_occurrence;
+ typedef struct et_forest_occurrence* et_forest_occurrence_t;
+
+ /* The ET-forest type. */
+ struct et_forest
+ {
+ /* Linked list of nodes is used to destroy the structure. */
+ int nnodes;
+ };
+
+ /* Single occurrence of node in ET-forest.
+ A single node may have multiple occurrences.
+ */
+ struct et_forest_occurrence
+ {
+ /* Parent in the splay-tree. */
+ et_forest_occurrence_t parent;
+
+ /* Children in the splay-tree. */
+ et_forest_occurrence_t left, right;
+
+ /* Counts of vertices in the two splay-subtrees. */
+ int count_left, count_right;
+
+ /* Next occurrence of this node in the sequence. */
+ et_forest_occurrence_t next;
+
+ /* The node, which this occurrence is of. */
+ et_forest_node_t node;
+ };
+
+
+ /* ET-forest node. */
+ struct et_forest_node
+ {
+ et_forest_t forest;
+ void *value;
+
+ /* First and last occurrence of this node in the sequence. */
+ et_forest_occurrence_t first, last;
+ };
+
+
+ static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
+ static void remove_all_occurrences PARAMS ((et_forest_node_t));
+ static inline et_forest_occurrence_t find_leftmost_node
+ PARAMS ((et_forest_occurrence_t));
+ static inline et_forest_occurrence_t find_rightmost_node
+ PARAMS ((et_forest_occurrence_t));
+ static int calculate_value PARAMS ((et_forest_occurrence_t));
+
+ static inline et_forest_occurrence_t find_leftmost_node (occ)
+ et_forest_occurrence_t occ;
+ {
+ while (occ->left)
+ occ = occ->left;
+
+ return occ;
+ }
+
+ static inline et_forest_occurrence_t find_rightmost_node (occ)
+ et_forest_occurrence_t occ;
+ {
+ while (occ->right)
+ occ = occ->right;
+ return occ;
+ }
+
+
+
+ static et_forest_occurrence_t splay (node)
+ et_forest_occurrence_t node;
+ {
+ et_forest_occurrence_t parent;
+ et_forest_occurrence_t grandparent;
+
+ while (1)
+ {
+ parent = node->parent;
+
+ if (! parent)
+ return node; /* node == root. */
+
+ grandparent = parent->parent;
+
+ if (! grandparent)
+ break;
+
+ /* Now there are four possible combinations: */
+
+ if (node == parent->left)
+ {
+ if (parent == grandparent->left)
+ {
+ et_forest_occurrence_t node1, node2;
+ int count1, count2;
+
+ node1 = node->right;
+ count1 = node->count_right;
+ node2 = parent->right;
+ count2 = parent->count_right;
+
+ grandparent->left = node2;
+ grandparent->count_left = count2;
+ if (node2)
+ node2->parent = grandparent;
+ parent->left = node1;
+ parent->count_left = count1;
+ if (node1)
+ node1->parent = parent;
+ parent->right = grandparent;
+ parent->count_right = count2 + grandparent->count_right + 1;
+ node->right = parent;
+ node->count_right = count1 + parent->count_right + 1;
+
+ node->parent = grandparent->parent;
+ parent->parent = node;
+ grandparent->parent = parent;
+
+ if (node->parent)
+ {
+ if (node->parent->left == grandparent)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
+ }
+ else
+ {
+ /* parent == grandparent->right && node == parent->left*/
+ et_forest_occurrence_t node1, node2;
+ int count1, count2;
+
+ node1 = node->left;
+ count1 = node->count_left;
+ node2 = node->right;
+ count2 = node->count_right;
+
+ grandparent->right = node1;
+ grandparent->count_right = count1;
+ if (node1)
+ node1->parent = grandparent;
+ parent->left = node2;
+ parent->count_left = count2;
+ if (node2)
+ node2->parent = parent;
+ node->left = grandparent;
+ node->count_left = grandparent->count_left + count1 + 1;
+ node->right = parent;
+ node->count_right = parent->count_right + count2 + 1;
+
+ node->parent = grandparent->parent;
+ parent->parent = node;
+ grandparent->parent = node;
+
+ if (node->parent)
+ {
+ if (node->parent->left == grandparent)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
+ }
+ }
+ else
+ {
+ /* node == parent->right. */
+ if (parent == grandparent->left)
+ {
+ et_forest_occurrence_t node1, node2;
+ int count1, count2;
+
+ node1 = node->left;
+ count1 = node->count_left;
+ node2 = node->right;
+ count2 = node->count_right;
+
+ parent->right = node1;
+ parent->count_right = count1;
+ if (node1)
+ node1->parent = parent;
+ grandparent->left = node2;
+ grandparent->count_left = count2;
+ if (node2)
+ node2->parent = grandparent;
+ node->left = parent;
+ node->count_left = parent->count_left + count1 + 1;
+ node->right = grandparent;
+ node->count_right = grandparent->count_right + count2 + 1;
+
+ node->parent = grandparent->parent;
+ parent->parent = node;
+ grandparent->parent = node;
+
+ if (node->parent)
+ {
+ if (node->parent->left == grandparent)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
+ }
+ else
+ {
+ /* parent == grandparent->right && node == parent->right*/
+ et_forest_occurrence_t node1, node2;
+ int count1, count2;
+
+ node1 = node->left;
+ count1 = node->count_left;
+ node2 = parent->left;
+ count2 = parent->count_left;
+
+ grandparent->right = node2;
+ grandparent->count_right = count2;
+ if (node2)
+ node2->parent = grandparent;
+ parent->right = node1;
+ parent->count_right = count1;
+ if (node1)
+ node1->parent = parent;
+ parent->left = grandparent;
+ parent->count_left = count2 + grandparent->count_left + 1;
+ node->left = parent;
+ node->count_left = count1 + parent->count_left + 1;
+
+ node->parent = grandparent->parent;
+ parent->parent = node;
+ grandparent->parent = parent;
+
+ if (node->parent)
+ {
+ if (node->parent->left == grandparent)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
+ }
+ }
+
+ }
+
+ /* parent == root. */
+ /* There are two possible combinations: */
+
+ if (node == parent->left)
+ {
+ et_forest_occurrence_t node1;
+ int count1;
+
+ node1 = node->right;
+ count1 = node->count_right;
+
+ parent->left = node1;
+ parent->count_left = count1;
+ if (node1)
+ node1->parent = parent;
+ node->right = parent;
+ node->count_right = parent->count_right + 1 + count1;
+ node->parent = parent->parent; /* the same as = 0; */
+ parent->parent = node;
+
+ if (node->parent)
+ {
+ if (node->parent->left == parent)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
+ }
+ else
+ {
+ /* node == parent->right. */
+ et_forest_occurrence_t node1;
+ int count1;
+
+ node1 = node->left;
+ count1 = node->count_left;
+
+ parent->right = node1;
+ parent->count_right = count1;
+ if (node1)
+ node1->parent = parent;
+ node->left = parent;
+ node->count_left = parent->count_left + 1 + count1;
+ node->parent = parent->parent; /* the same as = 0; */
+ parent->parent = node;
+
+ if (node->parent)
+ {
+ if (node->parent->left == parent)
+ node->parent->left = node;
+ else
+ node->parent->right = node;
+ }
+ }
+
+ return node;
+ }
+
+
+ static void
+ remove_all_occurrences (forest_node)
+ et_forest_node_t forest_node;
+ {
+ et_forest_occurrence_t first = forest_node->first;
+ et_forest_occurrence_t last = forest_node->last;
+ et_forest_occurrence_t node;
+
+ splay (first);
+
+ if (first->left)
+ first->left->parent = 0;
+ if (first->right)
+ first->right->parent = 0;
+
+ if (last != first)
+ {
+ splay (last);
+
+ if (last->left)
+ last->left->parent = 0;
+ if (last->right)
+ last->right->parent = 0;
+ }
+
+ if (last->right && first->left) /* actually, first->left would suffice. */
+ {
+ /* Need to join them. */
+ et_forest_occurrence_t prev_node, next_node;
+
+ prev_node = splay (find_rightmost_node (first->left));
+ next_node = splay (find_leftmost_node (last->right));
+ /* prev_node and next_node are consecutive occurencies
+ of the same node. */
+ if (prev_node->next != next_node)
+ abort ();
+
+ prev_node->right = next_node->right;
+ prev_node->count_right = next_node->count_right;
+ prev_node->next = next_node->next;
+ if (prev_node->right)
+ prev_node->right->parent = prev_node;
+
+ if (prev_node->node->last == next_node)
+ prev_node->node->last = prev_node;
+
+ free (next_node);
+ }
+
+ if (first != last)
+ {
+ node = first->next;
+
+ while (node != last)
+ {
+ et_forest_occurrence_t next_node;
+
+ splay (node);
+
+ if (node->left)
+ node->left->parent = 0;
+ if (node->right)
+ node->right->parent = 0;
+
+ next_node = node->next;
+ free (node);
+ node = next_node;
+ }
+ }
+
+ free (first);
+ if (first != last)
+ free (last);
+ }
+
+
+ static inline int
+ calculate_value (node)
+ et_forest_occurrence_t node;
+ {
+ int value = node->count_left;
+
+ while (node->parent)
+ {
+ if (node == node->parent->right)
+ value += node->parent->count_left + 1;
+
+ node = node->parent;
+ }
+
+ return value;
+ }
+
+
+
+
+ /* Create ET-forest structure. */
+ et_forest_t
+ et_forest_create ()
+ {
+
+ et_forest_t forest = xmalloc (sizeof (struct et_forest));
+
+ forest->nnodes = 0;
+ return forest;
+ }
+
+
+
+ /* Deallocate the structure. */
+ void
+ et_forest_delete (forest)
+ et_forest_t forest;
+ {
+ if (forest->nnodes)
+ abort ();
+
+ free (forest);
+ }
+
+ /* Create new node with VALUE and return the edge.
+ Return NULL when memory allocation failed. */
+ et_forest_node_t
+ et_forest_add_node (forest, value)
+ et_forest_t forest;
+ void *value;
+ {
+ /* Create node with one occurrence. */
+ et_forest_node_t node;
+ et_forest_occurrence_t occ;
+
+ node = xmalloc (sizeof (struct et_forest_node));
+ occ = xmalloc (sizeof (struct et_forest_occurrence));
+
+ node->first = node->last = occ;
+ node->value = value;
+ forest->nnodes++;
+
+ occ->node = node;
+ occ->left = occ->right = occ->parent = 0;
+ occ->next = 0;
+ occ->count_left = occ->count_right = 0;
+ return node;
+ }
+
+ /* Add new edge to the tree, return 1 if succesfull.
+ 0 indicates that creation of the edge will close the cycle in graph. */
+ int
+ et_forest_add_edge (forest, parent_node, child_node)
+ et_forest_t forest ATTRIBUTE_UNUSED;
+ et_forest_node_t parent_node;
+ et_forest_node_t child_node;
+ {
+ et_forest_occurrence_t new_occ, parent_occ, child_occ;
+
+ if (! parent_node || ! child_node)
+ abort ();
+
+ parent_occ = parent_node->first;
+ child_occ = child_node->first;
+
+ splay (parent_occ);
+ splay (child_occ);
+
+ if (parent_occ->parent)
+ return 0; /* Both child and parent are in the same tree. */
+
+ if (child_occ->left)
+ abort (); /* child must be root of its containing tree. */
+
+ new_occ = xmalloc (sizeof (struct et_forest_occurrence));
+
+ new_occ->node = parent_node;
+ new_occ->left = child_occ;
+ new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */
+ new_occ->right = parent_occ->right;
+ new_occ->count_right = parent_occ->count_right;
+ new_occ->parent = parent_occ;
+ new_occ->next = parent_occ->next;
+ child_occ->parent = new_occ;
+ parent_occ->right = new_occ;
+ parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
+ parent_occ->next = new_occ;
+ if (new_occ->right)
+ new_occ->right->parent = new_occ;
+
+ if (parent_node->last == parent_occ)
+ parent_node->last = new_occ;
+ return 1;
+ }
+
+ /* Remove NODE from the tree and all connected edges. */
+ void
+ et_forest_remove_node (forest, node)
+ et_forest_t forest;
+ et_forest_node_t node;
+ {
+ remove_all_occurrences (node);
+ forest->nnodes--;
+
+ free (node);
+ }
+
+ /* Remove edge from the tree, return 1 if sucesfull,
+ 0 indicates nonexisting edge. */
+ int
+ et_forest_remove_edge (forest, parent_node, child_node)
+ et_forest_t forest ATTRIBUTE_UNUSED;
+ et_forest_node_t parent_node;
+ et_forest_node_t child_node;
+ {
+ et_forest_occurrence_t parent_pre_occ, parent_post_occ;
+
+ splay (child_node->first);
+
+ if (! child_node->first->left)
+ return 0;
+
+ parent_pre_occ = find_rightmost_node (child_node->first->left);
+ if (parent_pre_occ->node != parent_node)
+ abort ();
+
+ splay (parent_pre_occ);
+ parent_pre_occ->right->parent = 0;
+
+ parent_post_occ = parent_pre_occ->next;
+ splay (parent_post_occ);
+
+ parent_post_occ->left->parent = 0;
+
+ parent_pre_occ->right = parent_post_occ->right;
+ parent_pre_occ->count_right = parent_post_occ->count_right;
+ if (parent_post_occ->right)
+ parent_post_occ->right->parent = parent_pre_occ;
+
+ parent_pre_occ->next = parent_post_occ->next;
+
+ if (parent_post_occ == parent_node->last)
+ parent_node->last = parent_pre_occ;
+
+ free (parent_post_occ);
+ return 1;
+ }
+
+ /* Return the parent of the NODE if any, NULL otherwise. */
+ et_forest_node_t
+ et_forest_parent (forest, node)
+ et_forest_t forest ATTRIBUTE_UNUSED;
+ et_forest_node_t node;
+ {
+ splay (node->first);
+
+ if (node->first->left)
+ return find_rightmost_node (node->first->left)->node;
+ else
+ return 0;
+ }
+
+
+ /* Return nearest common ancestor of NODE1 and NODE2.
+ Return NULL of they are in different trees. */
+ et_forest_node_t
+ et_forest_common_ancestor (forest, node1, node2)
+ et_forest_t forest ATTRIBUTE_UNUSED;
+ et_forest_node_t node1;
+ et_forest_node_t node2;
+ {
+ int value1, value2, max_value;
+ et_forest_node_t ancestor;
+
+ if (node1 == node2)
+ return node1;
+
+ if (! node1 || ! node2)
+ abort ();
+
+ splay (node1->first);
+ splay (node2->first);
+
+ if (! node1->first->parent) /* The two vertices are in different trees. */
+ return 0;
+
+ value2 = calculate_value (node2->first);
+ value1 = calculate_value (node1->first);
+
+ if (value1 < value2)
+ {
+ ancestor = node1;
+ max_value = value2;
+ }
+ else
+ {
+ ancestor = node2;
+ max_value = value1;
+ }
+
+ while (calculate_value (ancestor->last) < max_value)
+ {
+ /* Find parent node. */
+ splay (ancestor->first);
+ ancestor = find_rightmost_node (ancestor->first->left) ->node;
+ }
+
+ return ancestor;
+ }
+
+ /* Return the value pointer of node set during it's creation. */
+ void *
+ et_forest_node_value (forest, node)
+ et_forest_t forest ATTRIBUTE_UNUSED;
+ et_forest_node_t node;
+ {
+ /* Alloc threading NULL as a special node of the forest. */
+ if (!node)
+ return NULL;
+ return node->value;
+ }
+
+ /* Find all sons of NODE and store them into ARRAY allocated by the caller.
+ Return number of nodes found. */
+ int
+ et_forest_enumerate_sons (forest, node, array)
+ et_forest_t forest ATTRIBUTE_UNUSED;
+ et_forest_node_t node;
+ et_forest_node_t *array;
+ {
+ int n = 0;
+ et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
+
+ /* Parent is the rightmost node of the left successor.
+ Look for all occurences having no right succesor
+ and lookup the sons. */
+ while (occ != stop)
+ {
+ splay (occ);
+ if (occ->right)
+ {
+ occ1 = find_leftmost_node (occ->right);
+ if (occ1->node->first == occ1)
+ array[n++] = occ1->node;
+ }
+ occ = occ->next;
+ }
+ return n;
+ }
Index: et-forest.h
===================================================================
RCS file: et-forest.h
diff -N et-forest.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- et-forest.h 12 Jun 2002 18:20:02 -0000
***************
*** 0 ****
--- 1,83 ----
+ /* Et-forest data structure implementation.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+
+ /* This package implements ET forest data structure. Each tree in
+ the structure maintains a tree structure and offers logarithmic time
+ for tree operations (insertion and removal of nodes and edges) and
+ poly-logarithmic time for nearest common ancesto.
+
+ ET tree strores its structue as a sequence of symbols obtained
+ by dfs(root)
+
+ dfs (node)
+ {
+ s = node;
+ for each child c of node do
+ s = concat (s, c, node);
+ return s;
+ }
+
+ For example for tree
+
+ 1
+ / | \
+ 2 3 4
+ / |
+ 4 5
+
+ the sequence is 1 2 4 2 5 3 1 3 1 4 1.
+
+ The sequence is stored in a sligtly modified splay tree.
+ In order to support various types of node values, a hashtable
+ is used to convert node values to the internal representation. */
+
+ #ifndef _ET_TREE_H
+ #define _ET_TREE_H
+
+ #include <ansidecl.h>
+ #include <stddef.h>
+
+ #ifdef __cplusplus
+ extern "C" {
+ #endif /* __cplusplus */
+
+ typedef struct et_forest *et_forest_t;
+ typedef struct et_forest_node *et_forest_node_t;
+
+ extern et_forest_t et_forest_create PARAMS ((void));
+
+ extern void et_forest_delete PARAMS ((et_forest_t));
+
+ extern et_forest_node_t et_forest_add_node PARAMS ((et_forest_t, void *));
+ extern int et_forest_add_edge PARAMS ((et_forest_t, et_forest_node_t,
+ et_forest_node_t));
+ extern void et_forest_remove_node PARAMS ((et_forest_t, et_forest_node_t));
+ extern int et_forest_remove_edge PARAMS ((et_forest_t, et_forest_node_t,
+ et_forest_node_t));
+ extern et_forest_node_t et_forest_parent PARAMS ((et_forest_t, et_forest_node_t));
+ extern et_forest_node_t et_forest_common_ancestor PARAMS ((et_forest_t,
+ et_forest_node_t,
+ et_forest_node_t));
+ extern void * et_forest_node_value PARAMS ((et_forest_t, et_forest_node_t));
+ extern int et_forest_enumerate_sons PARAMS ((et_forest_t, et_forest_node_t,
+ et_forest_node_t *));
+
+ #ifdef __cplusplus
+ }
+ #endif /* __cplusplus */
+
+ #endif /* _ET_TREE_H */
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.204
diff -c -3 -p -r1.204 gcse.c
*** gcse.c 11 Jun 2002 19:58:04 -0000 1.204
--- gcse.c 12 Jun 2002 18:20:03 -0000
*************** static sbitmap *hoist_vbeout;
*** 5743,5749 ****
static sbitmap *hoist_exprs;
/* Dominator bitmaps. */
! static sbitmap *dominators;
/* ??? We could compute post dominators and run this algorithm in
reverse to to perform tail merging, doing so would probably be
--- 5743,5749 ----
static sbitmap *hoist_exprs;
/* Dominator bitmaps. */
! dominance_info dominators;
/* ??? We could compute post dominators and run this algorithm in
reverse to to perform tail merging, doing so would probably be
*************** alloc_code_hoist_mem (n_blocks, n_exprs)
*** 5766,5773 ****
hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- dominators = sbitmap_vector_alloc (n_blocks, n_blocks);
}
/* Free vars used for code hoisting analysis. */
--- 5766,5771 ----
*************** free_code_hoist_mem ()
*** 5784,5790 ****
sbitmap_vector_free (hoist_exprs);
sbitmap_vector_free (transpout);
! sbitmap_vector_free (dominators);
}
/* Compute the very busy expressions at entry/exit from each block.
--- 5782,5788 ----
sbitmap_vector_free (hoist_exprs);
sbitmap_vector_free (transpout);
! free_dominance_info (dominators);
}
/* Compute the very busy expressions at entry/exit from each block.
*************** compute_code_hoist_data ()
*** 5833,5839 ****
compute_local_properties (transp, comp, antloc, 0);
compute_transpout ();
compute_code_hoist_vbeinout ();
! calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
if (gcse_file)
fprintf (gcse_file, "\n");
}
--- 5831,5837 ----
compute_local_properties (transp, comp, antloc, 0);
compute_transpout ();
compute_code_hoist_vbeinout ();
! dominators = calculate_dominance_info (CDI_DOMINATORS);
if (gcse_file)
fprintf (gcse_file, "\n");
}
*************** hoist_code ()
*** 5940,5946 ****
{
/* Ignore self dominance. */
if (bb == dominated
! || ! TEST_BIT (dominators[dominated->index], bb->index))
continue;
/* We've found a dominated block, now see if it computes
--- 5938,5944 ----
{
/* Ignore self dominance. */
if (bb == dominated
! || dominated_by_p (dominators, dominated, bb))
continue;
/* We've found a dominated block, now see if it computes
*************** hoist_code ()
*** 5997,6003 ****
{
/* Ignore self dominance. */
if (bb == dominated
! || ! TEST_BIT (dominators[dominated->index], bb->index))
continue;
/* We've found a dominated block, now see if it computes
--- 5995,6001 ----
{
/* Ignore self dominance. */
if (bb == dominated
! || ! dominated_by_p (dominators, dominated, bb))
continue;
/* We've found a dominated block, now see if it computes
Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ifcvt.c,v
retrieving revision 1.95
diff -c -3 -p -r1.95 ifcvt.c
*** ifcvt.c 11 Jun 2002 12:21:45 -0000 1.95
--- ifcvt.c 12 Jun 2002 18:20:03 -0000
*************** static int num_removed_blocks;
*** 77,83 ****
static bool life_data_ok;
/* The post-dominator relation on the original block numbers. */
! static sbitmap *post_dominators;
/* Forward references. */
static int count_bb_insns PARAMS ((basic_block));
--- 77,83 ----
static bool life_data_ok;
/* The post-dominator relation on the original block numbers. */
! static dominance_info post_dominators;
/* Forward references. */
static int count_bb_insns PARAMS ((basic_block));
*************** merge_if_block (test_bb, then_bb, else_b
*** 1814,1819 ****
--- 1814,1821 ----
if (combo_bb->global_live_at_end)
COPY_REG_SET (combo_bb->global_live_at_end,
then_bb->global_live_at_end);
+ if (post_dominators)
+ delete_from_dominance_info (post_dominators, then_bb);
merge_blocks_nomove (combo_bb, then_bb);
num_removed_blocks++;
}
*************** merge_if_block (test_bb, then_bb, else_b
*** 1823,1828 ****
--- 1825,1832 ----
get their addresses taken. */
if (else_bb)
{
+ if (post_dominators)
+ delete_from_dominance_info (post_dominators, else_bb);
merge_blocks_nomove (combo_bb, else_bb);
num_removed_blocks++;
}
*************** merge_if_block (test_bb, then_bb, else_b
*** 1877,1882 ****
--- 1881,1888 ----
if (combo_bb->global_live_at_end)
COPY_REG_SET (combo_bb->global_live_at_end,
join_bb->global_live_at_end);
+ if (post_dominators)
+ delete_from_dominance_info (post_dominators, join_bb);
merge_blocks_nomove (combo_bb, join_bb);
num_removed_blocks++;
}
*************** find_cond_trap (test_bb, then_edge, else
*** 2135,2140 ****
--- 2141,2148 ----
remove_edge (trap_bb == then_bb ? then_edge : else_edge);
if (trap_bb->pred == NULL)
{
+ if (post_dominators)
+ delete_from_dominance_info (post_dominators, trap_bb);
flow_delete_block (trap_bb);
num_removed_blocks++;
}
*************** find_if_case_1 (test_bb, then_edge, else
*** 2316,2321 ****
--- 2324,2331 ----
new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
then_bb_index = then_bb->index;
+ if (post_dominators)
+ delete_from_dominance_info (post_dominators, then_bb);
flow_delete_block (then_bb);
/* Make rest of code believe that the newly created block is the THEN_BB
block we removed. */
*************** find_if_case_2 (test_bb, then_edge, else
*** 2366,2373 ****
if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
;
else if (else_succ->dest->index < 0
! || TEST_BIT (post_dominators[then_bb->index],
! else_succ->dest->index))
;
else
return FALSE;
--- 2376,2383 ----
if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
;
else if (else_succ->dest->index < 0
! || dominated_by_p (post_dominators, then_bb,
! else_succ->dest))
;
else
return FALSE;
*************** find_if_case_2 (test_bb, then_edge, else
*** 2393,2398 ****
--- 2403,2410 ----
then_bb->global_live_at_start,
else_bb->global_live_at_end, BITMAP_IOR);
+ if (post_dominators)
+ delete_from_dominance_info (post_dominators, else_bb);
flow_delete_block (else_bb);
num_removed_blocks++;
*************** if_convert (x_life_data_ok)
*** 2700,2707 ****
post_dominators = NULL;
if (HAVE_conditional_execution || life_data_ok)
{
! post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
! calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
}
if (life_data_ok)
clear_bb_flags ();
--- 2712,2718 ----
post_dominators = NULL;
if (HAVE_conditional_execution || life_data_ok)
{
! post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
}
if (life_data_ok)
clear_bb_flags ();
*************** if_convert (x_life_data_ok)
*** 2712,2718 ****
continue;
if (post_dominators)
! sbitmap_vector_free (post_dominators);
if (rtl_dump_file)
fflush (rtl_dump_file);
--- 2723,2729 ----
continue;
if (post_dominators)
! free_dominance_info (post_dominators);
if (rtl_dump_file)
fflush (rtl_dump_file);
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.71
diff -c -3 -p -r1.71 predict.c
*** predict.c 1 Jun 2002 09:24:41 -0000 1.71
--- predict.c 12 Jun 2002 18:20:04 -0000
*************** Software Foundation, 59 Temple Place - S
*** 49,54 ****
--- 49,55 ----
#include "real.h"
#include "params.h"
#include "target.h"
+ #include "loop.h"
/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
REAL_BB_FREQ_MAX. */
*************** static void estimate_loops_at_level PAR
*** 73,82 ****
static void propagate_freq PARAMS ((struct loop *));
static void estimate_bb_frequencies PARAMS ((struct loops *));
static void counts_to_freqs PARAMS ((void));
! static void process_note_predictions PARAMS ((basic_block, int *, int *,
! sbitmap *));
! static void process_note_prediction PARAMS ((basic_block, int *, int *,
! sbitmap *, int, int));
static bool last_basic_block_p PARAMS ((basic_block));
static void compute_function_frequency PARAMS ((void));
static void choose_function_section PARAMS ((void));
--- 74,85 ----
static void propagate_freq PARAMS ((struct loop *));
static void estimate_bb_frequencies PARAMS ((struct loops *));
static void counts_to_freqs PARAMS ((void));
! static void process_note_predictions PARAMS ((basic_block, int *,
! dominance_info,
! dominance_info));
! static void process_note_prediction PARAMS ((basic_block, int *,
! dominance_info,
! dominance_info, int, int));
static bool last_basic_block_p PARAMS ((basic_block));
static void compute_function_frequency PARAMS ((void));
static void choose_function_section PARAMS ((void));
*************** void
*** 408,421 ****
estimate_probability (loops_info)
struct loops *loops_info;
{
! sbitmap *dominators, *post_dominators;
basic_block bb;
int i;
! dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
! post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
! calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
! calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
--- 411,423 ----
estimate_probability (loops_info)
struct loops *loops_info;
{
! dominance_info dominators, post_dominators;
basic_block bb;
int i;
! connect_infinite_loops_to_exit ();
! dominators = calculate_dominance_info (CDI_DOMINATORS);
! post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
*************** estimate_probability (loops_info)
*** 495,502 ****
/* Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us). */
if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
! && TEST_BIT (dominators[e->dest->index], e->src->index)
! && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
{
rtx insn;
--- 497,504 ----
/* Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us). */
if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
! && dominated_by_p (dominators, e->dest, e->src)
! && !dominated_by_p (post_dominators, e->src, e->dest))
{
rtx insn;
*************** estimate_probability (loops_info)
*** 613,621 ****
&& bb->succ->succ_next != NULL)
combine_predictions_for_insn (bb->end, bb);
! sbitmap_vector_free (post_dominators);
! sbitmap_vector_free (dominators);
estimate_bb_frequencies (loops_info);
}
--- 615,624 ----
&& bb->succ->succ_next != NULL)
combine_predictions_for_insn (bb->end, bb);
! free_dominance_info (post_dominators);
! free_dominance_info (dominators);
+ remove_fake_edges ();
estimate_bb_frequencies (loops_info);
}
*************** static void
*** 717,724 ****
process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
basic_block bb;
int *heads;
! int *dominators;
! sbitmap *post_dominators;
int pred;
int flags;
{
--- 720,727 ----
process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
basic_block bb;
int *heads;
! dominance_info dominators;
! dominance_info post_dominators;
int pred;
int flags;
{
*************** process_note_prediction (bb, heads, domi
*** 733,759 ****
/* This is first time we need this field in heads array; so
find first dominator that we do not post-dominate (we are
using already known members of heads array). */
! int ai = bb->index;
! int next_ai = dominators[bb->index];
int head;
! while (heads[next_ai] < 0)
{
! if (!TEST_BIT (post_dominators[next_ai], bb->index))
break;
! heads[next_ai] = ai;
ai = next_ai;
! next_ai = dominators[next_ai];
}
! if (!TEST_BIT (post_dominators[next_ai], bb->index))
! head = next_ai;
else
! head = heads[next_ai];
! while (next_ai != bb->index)
{
next_ai = ai;
! ai = heads[ai];
! heads[next_ai] = head;
}
}
y = heads[bb->index];
--- 736,765 ----
/* This is first time we need this field in heads array; so
find first dominator that we do not post-dominate (we are
using already known members of heads array). */
! basic_block ai = bb;
! basic_block next_ai = get_immediate_dominator (dominators, bb);
int head;
! while (heads[next_ai->index] < 0)
{
! if (!dominated_by_p (post_dominators, next_ai, bb))
break;
! heads[next_ai->index] = ai->index;
ai = next_ai;
! next_ai = get_immediate_dominator (dominators, next_ai);
}
! if (!dominated_by_p (post_dominators, next_ai, bb))
! head = next_ai->index;
else
! head = heads[next_ai->index];
! while (next_ai != bb)
{
next_ai = ai;
! if (heads[ai->index] == ENTRY_BLOCK)
! ai = ENTRY_BLOCK_PTR;
! else
! ai = BASIC_BLOCK (heads[ai->index]);
! heads[next_ai->index] = head;
}
}
y = heads[bb->index];
*************** process_note_prediction (bb, heads, domi
*** 764,770 ****
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
! && TEST_BIT (post_dominators[e->dest->index], bb->index))
predict_edge_def (e, pred, taken);
}
--- 770,776 ----
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
! && dominated_by_p (post_dominators, e->dest, bb))
predict_edge_def (e, pred, taken);
}
*************** static void
*** 776,783 ****
process_note_predictions (bb, heads, dominators, post_dominators)
basic_block bb;
int *heads;
! int *dominators;
! sbitmap *post_dominators;
{
rtx insn;
edge e;
--- 782,789 ----
process_note_predictions (bb, heads, dominators, post_dominators)
basic_block bb;
int *heads;
! dominance_info dominators;
! dominance_info post_dominators;
{
rtx insn;
edge e;
*************** void
*** 838,855 ****
note_prediction_to_br_prob ()
{
basic_block bb;
! sbitmap *post_dominators;
! int *dominators, *heads;
/* To enable handling of noreturn blocks. */
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
! dominators = xmalloc (sizeof (int) * last_basic_block);
! memset (dominators, -1, sizeof (int) * last_basic_block);
! post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
! calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
! calculate_dominance_info (dominators, NULL, CDI_DOMINATORS);
heads = xmalloc (sizeof (int) * last_basic_block);
memset (heads, -1, sizeof (int) * last_basic_block);
--- 844,858 ----
note_prediction_to_br_prob ()
{
basic_block bb;
! dominance_info post_dominators, dominators;
! int *heads;
/* To enable handling of noreturn blocks. */
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
! post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
! dominators = calculate_dominance_info (CDI_DOMINATORS);
heads = xmalloc (sizeof (int) * last_basic_block);
memset (heads, -1, sizeof (int) * last_basic_block);
*************** note_prediction_to_br_prob ()
*** 860,867 ****
FOR_EACH_BB (bb)
process_note_predictions (bb, heads, dominators, post_dominators);
! sbitmap_vector_free (post_dominators);
! free (dominators);
free (heads);
remove_fake_edges ();
--- 863,870 ----
FOR_EACH_BB (bb)
process_note_predictions (bb, heads, dominators, post_dominators);
! free_dominance_info (post_dominators);
! free_dominance_info (dominators);
free (heads);
remove_fake_edges ();
Index: sched-rgn.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/sched-rgn.c,v
retrieving revision 1.45
diff -c -3 -p -r1.45 sched-rgn.c
*** sched-rgn.c 10 Jun 2002 22:33:07 -0000 1.45
--- sched-rgn.c 12 Jun 2002 18:20:04 -0000
*************** static int *containing_rgn;
*** 153,159 ****
void debug_regions PARAMS ((void));
static void find_single_block_region PARAMS ((void));
! static void find_rgns PARAMS ((struct edge_list *, sbitmap *));
static int too_large PARAMS ((int, int *, int *));
extern void debug_live PARAMS ((int, int));
--- 153,159 ----
void debug_regions PARAMS ((void));
static void find_single_block_region PARAMS ((void));
! static void find_rgns PARAMS ((struct edge_list *, dominance_info));
static int too_large PARAMS ((int, int *, int *));
extern void debug_live PARAMS ((int, int));
*************** too_large (block, num_bbs, num_insns)
*** 624,630 ****
static void
find_rgns (edge_list, dom)
struct edge_list *edge_list;
! sbitmap *dom;
{
int *max_hdr, *dfs_nr, *stack, *degree;
char no_loops = 1;
--- 624,630 ----
static void
find_rgns (edge_list, dom)
struct edge_list *edge_list;
! dominance_info dom;
{
int *max_hdr, *dfs_nr, *stack, *degree;
char no_loops = 1;
*************** find_rgns (edge_list, dom)
*** 837,843 ****
{
/* Now verify that the block is dominated by the loop
header. */
! if (!TEST_BIT (dom[jbb->index], bb->index))
break;
}
}
--- 837,843 ----
{
/* Now verify that the block is dominated by the loop
header. */
! if (!dominated_by_p (dom, jbb, bb))
break;
}
}
*************** init_regions ()
*** 2909,2919 ****
}
else
{
! sbitmap *dom;
struct edge_list *edge_list;
- dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
-
/* The scheduler runs after flow; therefore, we can't blindly call
back into find_basic_blocks since doing so could invalidate the
info in global_live_at_start.
--- 2909,2917 ----
}
else
{
! dominance_info dom;
struct edge_list *edge_list;
/* The scheduler runs after flow; therefore, we can't blindly call
back into find_basic_blocks since doing so could invalidate the
info in global_live_at_start.
*************** init_regions ()
*** 2928,2934 ****
edge_list = create_edge_list ();
/* Compute the dominators and post dominators. */
! calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
/* build_control_flow will return nonzero if it detects unreachable
blocks or any other irregularity with the cfg which prevents
--- 2926,2932 ----
edge_list = create_edge_list ();
/* Compute the dominators and post dominators. */
! dom = calculate_dominance_info (CDI_DOMINATORS);
/* build_control_flow will return nonzero if it detects unreachable
blocks or any other irregularity with the cfg which prevents
*************** init_regions ()
*** 2946,2952 ****
/* For now. This will move as more and more of haifa is converted
to using the cfg code in flow.c. */
! free (dom);
}
}
--- 2944,2950 ----
/* For now. This will move as more and more of haifa is converted
to using the cfg code in flow.c. */
! free_dominance_info (dom);
}
}
Index: ssa-dce.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa-dce.c,v
retrieving revision 1.21
diff -c -3 -p -r1.21 ssa-dce.c
*** ssa-dce.c 12 Jun 2002 14:51:03 -0000 1.21
--- ssa-dce.c 12 Jun 2002 18:20:04 -0000
*************** static void set_control_dependent_block_
*** 98,110 ****
static void control_dependent_block_to_edge_map_free
PARAMS ((control_dependent_block_to_edge_map c));
static void find_all_control_dependences
! PARAMS ((struct edge_list *el, int *pdom,
control_dependent_block_to_edge_map cdbte));
static void find_control_dependence
! PARAMS ((struct edge_list *el, int edge_index, int *pdom,
control_dependent_block_to_edge_map cdbte));
static basic_block find_pdom
! PARAMS ((int *pdom, basic_block block));
static int inherently_necessary_register_1
PARAMS ((rtx *current_rtx, void *data));
static int inherently_necessary_register
--- 98,110 ----
static void control_dependent_block_to_edge_map_free
PARAMS ((control_dependent_block_to_edge_map c));
static void find_all_control_dependences
! PARAMS ((struct edge_list *el, dominance_info pdom,
control_dependent_block_to_edge_map cdbte));
static void find_control_dependence
! PARAMS ((struct edge_list *el, int edge_index, dominance_info pdom,
control_dependent_block_to_edge_map cdbte));
static basic_block find_pdom
! PARAMS ((dominance_info pdom, basic_block block));
static int inherently_necessary_register_1
PARAMS ((rtx *current_rtx, void *data));
static int inherently_necessary_register
*************** control_dependent_block_to_edge_map_free
*** 218,224 ****
static void
find_all_control_dependences (el, pdom, cdbte)
struct edge_list *el;
! int *pdom;
control_dependent_block_to_edge_map cdbte;
{
int i;
--- 218,224 ----
static void
find_all_control_dependences (el, pdom, cdbte)
struct edge_list *el;
! dominance_info pdom;
control_dependent_block_to_edge_map cdbte;
{
int i;
*************** static void
*** 237,243 ****
find_control_dependence (el, edge_index, pdom, cdbte)
struct edge_list *el;
int edge_index;
! int *pdom;
control_dependent_block_to_edge_map cdbte;
{
basic_block current_block;
--- 237,243 ----
find_control_dependence (el, edge_index, pdom, cdbte)
struct edge_list *el;
int edge_index;
! dominance_info pdom;
control_dependent_block_to_edge_map cdbte;
{
basic_block current_block;
*************** find_control_dependence (el, edge_index,
*** 266,272 ****
static basic_block
find_pdom (pdom, block)
! int *pdom;
basic_block block;
{
if (!block)
--- 266,272 ----
static basic_block
find_pdom (pdom, block)
! dominance_info pdom;
basic_block block;
{
if (!block)
*************** find_pdom (pdom, block)
*** 276,285 ****
if (block == ENTRY_BLOCK_PTR)
return ENTRY_BLOCK_PTR->next_bb;
! else if (block == EXIT_BLOCK_PTR || pdom[block->index] == EXIT_BLOCK)
return EXIT_BLOCK_PTR;
else
! return BASIC_BLOCK (pdom[block->index]);
}
/* Determine if the given CURRENT_RTX uses a hard register not
--- 276,290 ----
if (block == ENTRY_BLOCK_PTR)
return ENTRY_BLOCK_PTR->next_bb;
! else if (block == EXIT_BLOCK_PTR)
return EXIT_BLOCK_PTR;
else
! {
! basic_block bb = get_immediate_dominator (pdom, block);
! if (!bb)
! return EXIT_BLOCK_PTR;
! return bb;
! }
}
/* Determine if the given CURRENT_RTX uses a hard register not
*************** delete_insn_bb (insn)
*** 488,494 ****
void
ssa_eliminate_dead_code ()
{
- int i;
rtx insn;
basic_block bb;
/* Necessary instructions with operands to explore. */
--- 493,498 ----
*************** ssa_eliminate_dead_code ()
*** 497,503 ****
edge. "cdbte" abbreviates control dependent block to edge. */
control_dependent_block_to_edge_map cdbte;
/* Element I is the immediate postdominator of block I. */
! int *pdom;
struct edge_list *el;
/* Initialize the data structures. */
--- 501,507 ----
edge. "cdbte" abbreviates control dependent block to edge. */
control_dependent_block_to_edge_map cdbte;
/* Element I is the immediate postdominator of block I. */
! dominance_info pdom;
struct edge_list *el;
/* Initialize the data structures. */
*************** ssa_eliminate_dead_code ()
*** 510,523 ****
connect_infinite_loops_to_exit ();
/* Compute control dependence. */
! pdom = (int *) xmalloc (last_basic_block * sizeof (int));
! for (i = 0; i < last_basic_block; ++i)
! pdom[i] = INVALID_BLOCK;
! calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS);
! /* Assume there is a path from each node to the exit block. */
! for (i = 0; i < last_basic_block; ++i)
! if (pdom[i] == INVALID_BLOCK)
! pdom[i] = EXIT_BLOCK;
el = create_edge_list ();
find_all_control_dependences (el, pdom, cdbte);
--- 514,520 ----
connect_infinite_loops_to_exit ();
/* Compute control dependence. */
! pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
el = create_edge_list ();
find_all_control_dependences (el, pdom, cdbte);
Index: ssa.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa.c,v
retrieving revision 1.52
diff -c -3 -p -r1.52 ssa.c
*** ssa.c 11 Jun 2002 12:21:57 -0000 1.52
--- ssa.c 12 Jun 2002 18:20:05 -0000
*************** struct rename_context;
*** 165,171 ****
static inline rtx * phi_alternative
PARAMS ((rtx, int));
static void compute_dominance_frontiers_1
! PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
static void find_evaluations_1
PARAMS ((rtx dest, rtx set, void *data));
static void find_evaluations
--- 165,171 ----
static inline rtx * phi_alternative
PARAMS ((rtx, int));
static void compute_dominance_frontiers_1
! PARAMS ((sbitmap *frontiers, dominance_info idom, int bb, sbitmap done));
static void find_evaluations_1
PARAMS ((rtx dest, rtx set, void *data));
static void find_evaluations
*************** static void apply_delayed_renames
*** 183,191 ****
static int rename_insn_1
PARAMS ((rtx *ptr, void *data));
static void rename_block
! PARAMS ((int b, int *idom));
static void rename_registers
! PARAMS ((int nregs, int *idom));
static inline int ephi_add_node
PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
--- 183,191 ----
static int rename_insn_1
PARAMS ((rtx *ptr, void *data));
static void rename_block
! PARAMS ((int b, dominance_info dom));
static void rename_registers
! PARAMS ((int nregs, dominance_info idom));
static inline int ephi_add_node
PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
*************** find_evaluations (evals, nregs)
*** 516,522 ****
static void
compute_dominance_frontiers_1 (frontiers, idom, bb, done)
sbitmap *frontiers;
! int *idom;
int bb;
sbitmap done;
{
--- 516,522 ----
static void
compute_dominance_frontiers_1 (frontiers, idom, bb, done)
sbitmap *frontiers;
! dominance_info idom;
int bb;
sbitmap done;
{
*************** compute_dominance_frontiers_1 (frontiers
*** 531,537 ****
dominator tree (blocks dominated by this one) are children in the
CFG, so check all blocks. */
FOR_EACH_BB (c)
! if (idom[c->index] == bb && ! TEST_BIT (done, c->index))
compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
/* Find blocks conforming to rule (1) above. */
--- 531,538 ----
dominator tree (blocks dominated by this one) are children in the
CFG, so check all blocks. */
FOR_EACH_BB (c)
! if (get_immediate_dominator (idom, c)->index == bb
! && ! TEST_BIT (done, c->index))
compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
/* Find blocks conforming to rule (1) above. */
*************** compute_dominance_frontiers_1 (frontiers
*** 539,556 ****
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
! if (idom[e->dest->index] != bb)
SET_BIT (frontiers[bb], e->dest->index);
}
/* Find blocks conforming to rule (2). */
FOR_EACH_BB (c)
! if (idom[c->index] == bb)
{
int x;
EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
{
! if (idom[x] != bb)
SET_BIT (frontiers[bb], x);
});
}
--- 540,557 ----
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
! if (get_immediate_dominator (idom, e->dest)->index != bb)
SET_BIT (frontiers[bb], e->dest->index);
}
/* Find blocks conforming to rule (2). */
FOR_EACH_BB (c)
! if (get_immediate_dominator (idom, c)->index == bb)
{
int x;
EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
{
! if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb)
SET_BIT (frontiers[bb], x);
});
}
*************** compute_dominance_frontiers_1 (frontiers
*** 559,565 ****
void
compute_dominance_frontiers (frontiers, idom)
sbitmap *frontiers;
! int *idom;
{
sbitmap done = sbitmap_alloc (last_basic_block);
sbitmap_zero (done);
--- 560,566 ----
void
compute_dominance_frontiers (frontiers, idom)
sbitmap *frontiers;
! dominance_info idom;
{
sbitmap done = sbitmap_alloc (last_basic_block);
sbitmap_zero (done);
*************** gen_sequence ()
*** 1001,1007 ****
static void
rename_block (bb, idom)
int bb;
! int *idom;
{
basic_block b = BASIC_BLOCK (bb);
edge e;
--- 1002,1008 ----
static void
rename_block (bb, idom)
int bb;
! dominance_info idom;
{
basic_block b = BASIC_BLOCK (bb);
edge e;
*************** rename_block (bb, idom)
*** 1111,1117 ****
dominator order. */
FOR_EACH_BB (c)
! if (idom[c->index] == bb)
rename_block (c->index, idom);
/* Step Four: Update the sets to refer to their new register,
--- 1112,1118 ----
dominator order. */
FOR_EACH_BB (c)
! if (get_immediate_dominator (idom, c)->index == bb)
rename_block (c->index, idom);
/* Step Four: Update the sets to refer to their new register,
*************** rename_block (bb, idom)
*** 1137,1143 ****
static void
rename_registers (nregs, idom)
int nregs;
! int *idom;
{
VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
ssa_rename_from_initialize ();
--- 1138,1144 ----
static void
rename_registers (nregs, idom)
int nregs;
! dominance_info idom;
{
VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
ssa_rename_from_initialize ();
*************** convert_to_ssa ()
*** 1168,1174 ****
sbitmap *idfs;
/* Element I is the immediate dominator of block I. */
! int *idom;
int nregs;
--- 1169,1175 ----
sbitmap *idfs;
/* Element I is the immediate dominator of block I. */
! dominance_info idom;
int nregs;
*************** convert_to_ssa ()
*** 1182,1196 ****
dead code. We'll let the SSA optimizers do that. */
life_analysis (get_insns (), NULL, 0);
! idom = (int *) alloca (last_basic_block * sizeof (int));
! memset ((void *) idom, -1, (size_t) last_basic_block * sizeof (int));
! calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
if (rtl_dump_file)
{
fputs (";; Immediate Dominators:\n", rtl_dump_file);
FOR_EACH_BB (bb)
! fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index, idom[bb->index]);
fflush (rtl_dump_file);
}
--- 1183,1196 ----
dead code. We'll let the SSA optimizers do that. */
life_analysis (get_insns (), NULL, 0);
! idom = calculate_dominance_info (CDI_DOMINATORS);
if (rtl_dump_file)
{
fputs (";; Immediate Dominators:\n", rtl_dump_file);
FOR_EACH_BB (bb)
! fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index,
! get_immediate_dominator (idom, bb)->index);
fflush (rtl_dump_file);
}
*************** convert_to_ssa ()
*** 1241,1246 ****
--- 1241,1247 ----
in_ssa_form = 1;
reg_scan (get_insns (), max_reg_num (), 1);
+ free_dominance_info (idom);
}
/* REG is the representative temporary of its partition. Add it to the
Index: ssa.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ssa.h,v
retrieving revision 1.7
diff -c -3 -p -r1.7 ssa.h
*** ssa.h 4 Jun 2002 07:07:56 -0000 1.7
--- ssa.h 12 Jun 2002 18:20:05 -0000
*************** typedef int (*successor_phi_fn)
*** 27,33 ****
extern int for_each_successor_phi PARAMS ((basic_block bb,
successor_phi_fn,
void *));
! void compute_dominance_frontiers PARAMS ((sbitmap *frontiers, int *idom));
extern int remove_phi_alternative PARAMS ((rtx, basic_block));
--- 27,34 ----
extern int for_each_successor_phi PARAMS ((basic_block bb,
successor_phi_fn,
void *));
! void compute_dominance_frontiers PARAMS ((sbitmap *frontiers,
! dominance_info idom));
extern int remove_phi_alternative PARAMS ((rtx, basic_block));