This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Cleanup and enhance dominator infrastructure
Hello,
> > as pointed out by Daniel, there is a mistake in the part of the patch in
> > tree-ssa-pre.c (I did not notice that the arguments of
> > fast_a_dominates_b are reversed wrto dominated_by_p).
>
> Could you send me a complete patch including these new fixes?
here is the actual version of the patch; nothing else was changed
(except for resolving a few conflicts), so the comments/changelogs at
the original message should be applicable.
Zdenek
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.153.2.38
diff -c -3 -p -r1.153.2.38 basic-block.h
*** basic-block.h 8 Dec 2003 12:58:21 -0000 1.153.2.38
--- basic-block.h 18 Dec 2003 14:34:51 -0000
*************** struct basic_block_def GTY((chain_next (
*** 255,260 ****
--- 255,263 ----
/* Innermost loop containing the block. */
struct loop * GTY ((skip (""))) loop_father;
+ /* The dominance and postdominance information node. */
+ struct et_node * GTY ((skip (""))) dom[2];
+
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
*************** extern void clear_edges (void);
*** 399,408 ****
extern void mark_critical_edges (void);
extern rtx first_insn_after_basic_block_note (basic_block);
- /* Dominator information for basic blocks. */
-
- typedef struct dominance_info *dominance_info;
-
/* Structure to group all of the information to process IF-THEN and
IF-THEN-ELSE blocks for the conditional execution support. This
needs to be in a public file in case the IFCVT macros call
--- 402,407 ----
*************** enum cdi_direction
*** 637,658 ****
CDI_POST_DOMINATORS
};
! extern dominance_info calculate_dominance_info (enum cdi_direction);
! extern void free_dominance_info (dominance_info);
! extern basic_block nearest_common_dominator (dominance_info,
basic_block, basic_block);
! extern void set_immediate_dominator (dominance_info, basic_block,
basic_block);
! extern basic_block get_immediate_dominator (dominance_info, basic_block);
! extern bool dominated_by_p (dominance_info, basic_block, basic_block);
! extern int get_dominated_by (dominance_info, basic_block, basic_block **);
! extern void add_to_dominance_info (dominance_info, basic_block);
! extern void delete_from_dominance_info (dominance_info, basic_block);
! basic_block recount_dominator (dominance_info, basic_block);
! extern void redirect_immediate_dominators (dominance_info, basic_block,
basic_block);
! void iterate_fix_dominators (dominance_info, basic_block *, int);
! extern void verify_dominators (dominance_info);
#include "cfghooks.h"
--- 636,670 ----
CDI_POST_DOMINATORS
};
! enum dom_state
! {
! DOM_NONE, /* Not computed at all. */
! DOM_CONS_OK, /* The data is conservatively OK, i.e. if it says you that A dominates B,
! it indeed does. */
! DOM_NO_FAST_QUERY, /* The data is OK, but the fast query data are not usable. */
! DOM_OK /* Everything is ok. */
! };
!
! extern enum dom_state dom_computed[2];
!
! extern void calculate_dominance_info (enum cdi_direction);
! extern void free_dominance_info (enum cdi_direction);
! extern basic_block nearest_common_dominator (enum cdi_direction,
basic_block, basic_block);
! extern void set_immediate_dominator (enum cdi_direction, basic_block,
basic_block);
! extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
! extern bool dominated_by_p (enum cdi_direction, basic_block, basic_block);
! extern int get_dominated_by (enum cdi_direction, basic_block, basic_block **);
! extern void add_to_dominance_info (enum cdi_direction, basic_block);
! extern void delete_from_dominance_info (enum cdi_direction, basic_block);
! basic_block recount_dominator (enum cdi_direction, basic_block);
! extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
basic_block);
! extern void iterate_fix_dominators (enum cdi_direction, basic_block *, int);
! extern void verify_dominators (enum cdi_direction);
! extern basic_block first_dom_son (enum cdi_direction, basic_block);
! extern basic_block next_dom_son (enum cdi_direction, basic_block);
#include "cfghooks.h"
Index: bt-load.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bt-load.c,v
retrieving revision 2.9.2.2
diff -c -3 -p -r2.9.2.2 bt-load.c
*** bt-load.c 23 Jul 2003 16:59:28 -0000 2.9.2.2
--- bt-load.c 18 Dec 2003 14:34:51 -0000
*************** static void note_btr_set (rtx, rtx, void
*** 155,163 ****
migrating branch target load instructions. */
static struct obstack migrate_btrl_obstack;
- /* Basic block dominator information used when migrating PT instructions */
- static dominance_info dom;
-
/* Array indexed by basic block number, giving the set of registers
live in that block. */
static HARD_REG_SET *btrs_live;
--- 155,160 ----
*************** augment_live_range (bitmap live_range, H
*** 840,848 ****
tos = worklist = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
! if (dominated_by_p (dom, new_bb, head_bb))
*tos++ = new_bb;
! else if (dominated_by_p (dom, head_bb, new_bb))
{
edge e;
int new_block = new_bb->index;
--- 837,845 ----
tos = worklist = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
! if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
*tos++ = new_bb;
! else if (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb))
{
edge e;
int new_block = new_bb->index;
*************** combine_btr_defs (btr_def def, HARD_REG_
*** 974,980 ****
if (other_def != def
&& other_def->uses != NULL
&& ! other_def->has_ambiguous_use
! && dominated_by_p (dom, other_def->bb, def->bb))
{
/* def->bb dominates the other def, so def and other_def could
be combined. */
--- 971,977 ----
if (other_def != def
&& other_def->uses != NULL
&& ! other_def->has_ambiguous_use
! && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
{
/* def->bb dominates the other def, so def and other_def could
be combined. */
*************** migrate_btr_def (btr_def def, int min_co
*** 1226,1234 ****
def_basic_block_freq = basic_block_freq (def->bb);
! for (try = get_immediate_dominator (dom, def->bb);
!give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
! try = get_immediate_dominator (dom, try))
{
/* Try to move the instruction that sets the target register into
basic block TRY. */
--- 1223,1231 ----
def_basic_block_freq = basic_block_freq (def->bb);
! for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb);
!give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
! try = get_immediate_dominator (CDI_DOMINATORS, try))
{
/* Try to move the instruction that sets the target register into
basic block TRY. */
*************** migrate_btr_defs (enum reg_class btr_cla
*** 1299,1305 ****
"Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
" loop-depth = %d idom = %d\n",
i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
! get_immediate_dominator (dom, bb)->index);
}
}
--- 1296,1302 ----
"Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
" loop-depth = %d idom = %d\n",
i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
! get_immediate_dominator (CDI_DOMINATORS, bb)->index);
}
}
*************** branch_target_load_optimize (rtx insns,
*** 1367,1378 ****
life_analysis (insns, NULL, 0);
/* Dominator info is also needed for migrate_btr_def. */
! dom = calculate_dominance_info (CDI_DOMINATORS);
migrate_btr_defs (class,
((*targetm.branch_target_register_callee_saved)
(after_prologue_epilogue_gen)));
! free_dominance_info (dom);
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
PROP_DEATH_NOTES | PROP_REG_INFO);
--- 1364,1375 ----
life_analysis (insns, NULL, 0);
/* Dominator info is also needed for migrate_btr_def. */
! calculate_dominance_info (CDI_DOMINATORS);
migrate_btr_defs (class,
((*targetm.branch_target_register_callee_saved)
(after_prologue_epilogue_gen)));
! free_dominance_info (CDI_DOMINATORS);
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
PROP_DEATH_NOTES | PROP_REG_INFO);
Index: cfglayout.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.c,v
retrieving revision 1.19.2.14
diff -c -3 -p -r1.19.2.14 cfglayout.c
*** cfglayout.c 26 Oct 2003 18:16:53 -0000 1.19.2.14
--- cfglayout.c 18 Dec 2003 14:34:51 -0000
*************** end:
*** 1263,1269 ****
void
copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
edge *edges, unsigned n_edges, edge *new_edges,
! struct loop *base, struct loops *loops)
{
unsigned i, j;
basic_block bb, new_bb, dom_bb;
--- 1263,1269 ----
void
copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
edge *edges, unsigned n_edges, edge *new_edges,
! struct loop *base)
{
unsigned i, j;
basic_block bb, new_bb, dom_bb;
*************** copy_bbs (basic_block *bbs, unsigned n,
*** 1278,1284 ****
bb->rbi->duplicated = 1;
/* Add to loop. */
add_bb_to_loop (new_bb, bb->loop_father->copy);
! add_to_dominance_info (loops->cfg.dom, new_bb);
/* Possibly set header. */
if (bb->loop_father->header == bb && bb->loop_father != base)
new_bb->loop_father->header = new_bb;
--- 1278,1284 ----
bb->rbi->duplicated = 1;
/* Add to loop. */
add_bb_to_loop (new_bb, bb->loop_father->copy);
! add_to_dominance_info (CDI_DOMINATORS, new_bb);
/* Possibly set header. */
if (bb->loop_father->header == bb && bb->loop_father != base)
new_bb->loop_father->header = new_bb;
*************** copy_bbs (basic_block *bbs, unsigned n,
*** 1293,1303 ****
bb = bbs[i];
new_bb = new_bbs[i];
! dom_bb = get_immediate_dominator (loops->cfg.dom, bb);
if (dom_bb->rbi->duplicated)
{
dom_bb = dom_bb->rbi->copy;
! set_immediate_dominator (loops->cfg.dom, new_bb, dom_bb);
}
}
--- 1293,1303 ----
bb = bbs[i];
new_bb = new_bbs[i];
! dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
if (dom_bb->rbi->duplicated)
{
dom_bb = dom_bb->rbi->copy;
! set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
}
}
Index: cfglayout.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.h,v
retrieving revision 1.3.2.2
diff -c -3 -p -r1.3.2.2 cfglayout.h
*** cfglayout.h 21 Jul 2003 13:50:30 -0000 1.3.2.2
--- cfglayout.h 18 Dec 2003 14:34:51 -0000
*************** extern void insn_locators_initialize (vo
*** 43,47 ****
extern void reemit_insn_block_notes (void);
extern bool can_copy_bbs_p (basic_block *, unsigned);
extern void copy_bbs (basic_block *, unsigned, basic_block *,
! edge *, unsigned, edge *, struct loop *, struct loops *);
! extern void cfg_layout_initialize_rbi (basic_block);
--- 43,47 ----
extern void reemit_insn_block_notes (void);
extern bool can_copy_bbs_p (basic_block *, unsigned);
extern void copy_bbs (basic_block *, unsigned, basic_block *,
! edge *, unsigned, edge *, struct loop *);
! extern void cfg_layout_initialize_rbi (basic_block);
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.14.2.11
diff -c -3 -p -r1.14.2.11 cfgloop.c
*** cfgloop.c 23 Jul 2003 16:59:32 -0000 1.14.2.11
--- cfgloop.c 18 Dec 2003 14:34:51 -0000
*************** static void flow_loop_entry_edges_find (
*** 40,46 ****
static void flow_loop_exit_edges_find (struct loop *);
static int flow_loop_nodes_find (basic_block, struct loop *);
static void flow_loop_pre_header_scan (struct loop *);
! static basic_block flow_loop_pre_header_find (basic_block, dominance_info);
static int flow_loop_level_compute (struct loop *);
static int flow_loops_level_compute (struct loops *);
static void establish_preds (struct loop *);
--- 40,46 ----
static void flow_loop_exit_edges_find (struct loop *);
static int flow_loop_nodes_find (basic_block, struct loop *);
static void flow_loop_pre_header_scan (struct loop *);
! static basic_block flow_loop_pre_header_find (basic_block);
static int flow_loop_level_compute (struct loop *);
static int flow_loops_level_compute (struct loops *);
static void establish_preds (struct loop *);
*************** flow_loops_cfg_dump (const struct loops
*** 55,61 ****
int i;
basic_block bb;
! if (! loops->num || ! file || ! loops->cfg.dom)
return;
FOR_EACH_BB (bb)
--- 55,61 ----
int i;
basic_block bb;
! if (! loops->num || ! file)
return;
FOR_EACH_BB (bb)
*************** flow_loops_free (struct loops *loops)
*** 212,220 ****
free (loops->parray);
loops->parray = NULL;
- if (loops->cfg.dom)
- free_dominance_info (loops->cfg.dom);
-
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
if (loops->cfg.rc_order)
--- 212,217 ----
*************** flow_loop_pre_header_scan (struct loop *
*** 391,401 ****
}
/* Return the block for the pre-header of the loop with header
! HEADER where DOM specifies the dominator information. Return NULL if
! there is no pre-header. */
static basic_block
! flow_loop_pre_header_find (basic_block header, dominance_info dom)
{
basic_block pre_header;
edge e;
--- 388,397 ----
}
/* Return the block for the pre-header of the loop with header
! HEADER. Return NULL if there is no pre-header. */
static basic_block
! flow_loop_pre_header_find (basic_block header)
{
basic_block pre_header;
edge e;
*************** flow_loop_pre_header_find (basic_block h
*** 408,414 ****
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
! && ! dominated_by_p (dom, node, header))
{
if (pre_header == NULL)
pre_header = node;
--- 404,410 ----
basic_block node = e->src;
if (node != ENTRY_BLOCK_PTR
! && ! dominated_by_p (CDI_DOMINATORS, node, header))
{
if (pre_header == NULL)
pre_header = node;
*************** flow_loops_level_compute (struct loops *
*** 522,528 ****
about it specified by FLAGS. */
int
! flow_loop_scan (struct loops *loops, struct loop *loop, int flags)
{
if (flags & LOOP_ENTRY_EDGES)
{
--- 518,524 ----
about it specified by FLAGS. */
int
! flow_loop_scan (struct loop *loop, int flags)
{
if (flags & LOOP_ENTRY_EDGES)
{
*************** flow_loop_scan (struct loops *loops, str
*** 541,548 ****
if (flags & LOOP_PRE_HEADER)
{
/* Look to see if the loop has a pre-header node. */
! loop->pre_header
! = flow_loop_pre_header_find (loop->header, loops->cfg.dom);
/* Find the blocks within the extended basic block of
the loop pre-header. */
--- 537,543 ----
if (flags & LOOP_PRE_HEADER)
{
/* Look to see if the loop has a pre-header node. */
! loop->pre_header = flow_loop_pre_header_find (loop->header);
/* Find the blocks within the extended basic block of
the loop pre-header. */
*************** flow_loop_scan (struct loops *loops, str
*** 556,567 ****
static void
canonicalize_loop_headers (void)
{
- 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));
--- 551,561 ----
static void
canonicalize_loop_headers (void)
{
basic_block header;
edge e;
/* Compute the dominators. */
! calculate_dominance_info (CDI_DOMINATORS);
alloc_aux_for_blocks (sizeof (int));
alloc_aux_for_edges (sizeof (int));
*************** canonicalize_loop_headers (void)
*** 580,586 ****
have_abnormal_edge = 1;
if (latch != ENTRY_BLOCK_PTR
! && dominated_by_p (dom, latch, header))
{
num_latches++;
LATCH_EDGE (e) = 1;
--- 574,580 ----
have_abnormal_edge = 1;
if (latch != ENTRY_BLOCK_PTR
! && dominated_by_p (CDI_DOMINATORS, latch, header))
{
num_latches++;
LATCH_EDGE (e) = 1;
*************** canonicalize_loop_headers (void)
*** 592,597 ****
--- 586,593 ----
HEADER_BLOCK (header) = num_latches;
}
+ free_dominance_info (CDI_DOMINATORS);
+
if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
{
basic_block bb;
*************** canonicalize_loop_headers (void)
*** 657,663 ****
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
--- 653,658 ----
*************** flow_loops_find (struct loops *loops, in
*** 673,679 ****
int num_loops;
edge e;
sbitmap headers;
- dominance_info dom;
int *dfs_order;
int *rc_order;
basic_block header;
--- 668,673 ----
*************** flow_loops_find (struct loops *loops, in
*** 699,705 ****
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. */
--- 693,699 ----
canonicalize_loop_headers ();
/* Compute the dominators. */
! 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 (struct loops *loops, in
*** 733,739 ****
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)
--- 727,734 ----
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 (CDI_DOMINATORS, latch, header))
{
/* Shared headers should be eliminated by now. */
if (more_latches)
*************** flow_loops_find (struct loops *loops, in
*** 778,784 ****
flow_depth_first_order_compute (dfs_order, rc_order);
/* Save CFG derived information to avoid recomputing it. */
- loops->cfg.dom = dom;
loops->cfg.dfs_order = dfs_order;
loops->cfg.rc_order = rc_order;
--- 773,778 ----
*************** flow_loops_find (struct loops *loops, in
*** 807,813 ****
basic_block latch = e->src;
if (latch != ENTRY_BLOCK_PTR
! && dominated_by_p (dom, latch, header))
{
loop->latch = latch;
break;
--- 801,807 ----
basic_block latch = e->src;
if (latch != ENTRY_BLOCK_PTR
! && dominated_by_p (CDI_DOMINATORS, latch, header))
{
loop->latch = latch;
break;
*************** flow_loops_find (struct loops *loops, in
*** 826,839 ****
/* Scan the loops. */
for (i = 1; i < num_loops; i++)
! flow_loop_scan (loops, loops->parray[i], flags);
loops->num = num_loops;
}
else
{
! loops->cfg.dom = NULL;
! free_dominance_info (dom);
}
loops->state = 0;
--- 820,832 ----
/* Scan the loops. */
for (i = 1; i < num_loops; i++)
! flow_loop_scan (loops->parray[i], flags);
loops->num = num_loops;
}
else
{
! free_dominance_info (CDI_DOMINATORS);
}
loops->state = 0;
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.2.4.8
diff -c -3 -p -r1.2.4.8 cfgloop.h
*** cfgloop.h 13 Nov 2003 02:37:36 -0000 1.2.4.8
--- cfgloop.h 18 Dec 2003 14:34:51 -0000
*************** struct loops
*** 230,238 ****
/* Information derived from the CFG. */
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;
--- 230,235 ----
*************** extern void flow_loops_dump (const struc
*** 265,271 ****
void (*)(const struct loop *, FILE *, int), int);
extern void flow_loop_dump (const struct loop *, FILE *,
void (*)(const struct loop *, FILE *, int), int);
! extern int flow_loop_scan (struct loops *, struct loop *, int);
extern void flow_loop_free (struct loop *);
void mark_irreducible_loops (struct loops *);
extern void create_loop_notes (void);
--- 262,268 ----
void (*)(const struct loop *, FILE *, int), int);
extern void flow_loop_dump (const struct loop *, FILE *,
void (*)(const struct loop *, FILE *, int), int);
! extern int flow_loop_scan (struct loop *, int);
extern void flow_loop_free (struct loop *);
void mark_irreducible_loops (struct loops *);
extern void create_loop_notes (void);
*************** extern void remove_bb_from_loops (basic_
*** 293,299 ****
extern void cancel_loop (struct loops *, struct loop *);
extern void cancel_loop_tree (struct loops *, struct loop *);
! extern basic_block loop_split_edge_with (edge, rtx, struct loops *);
extern int fix_loop_placement (struct loop *);
enum
--- 290,296 ----
extern void cancel_loop (struct loops *, struct loop *);
extern void cancel_loop_tree (struct loops *, struct loop *);
! extern basic_block loop_split_edge_with (edge, rtx);
extern int fix_loop_placement (struct loop *);
enum
*************** extern void force_single_succ_latches (s
*** 307,316 ****
extern void verify_loop_structure (struct loops *);
/* Loop analysis. */
! extern bool simple_loop_p (struct loops *, struct loop *, struct loop_desc *);
extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
! extern bool just_once_each_iteration_p (struct loops *,struct loop *,
! basic_block);
extern unsigned expected_loop_iterations (const struct loop *);
/* Loop manipulation. */
--- 304,312 ----
extern void verify_loop_structure (struct loops *);
/* Loop analysis. */
! extern bool simple_loop_p (struct loop *, struct loop_desc *);
extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
! extern bool just_once_each_iteration_p (struct loop *, basic_block);
extern unsigned expected_loop_iterations (const struct loop *);
/* Loop manipulation. */
*************** extern int duplicate_loop_to_header_edge
*** 325,331 ****
extern struct loop *loopify (struct loops *, edge, edge, basic_block);
extern void unloop (struct loops *, struct loop *);
extern bool remove_path (struct loops *, edge);
! extern edge split_loop_bb (struct loops *, basic_block, rtx);
/* Loop optimizer initialization. */
extern struct loops *rtl_loop_optimizer_init (FILE *);
--- 321,327 ----
extern struct loop *loopify (struct loops *, edge, edge, basic_block);
extern void unloop (struct loops *, struct loop *);
extern bool remove_path (struct loops *, edge);
! extern edge split_loop_bb (basic_block, rtx);
/* Loop optimizer initialization. */
extern struct loops *rtl_loop_optimizer_init (FILE *);
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopanal.c,v
retrieving revision 1.2.4.8
diff -c -3 -p -r1.2.4.8 cfgloopanal.c
*** cfgloopanal.c 13 Nov 2003 02:37:36 -0000 1.2.4.8
--- cfgloopanal.c 18 Dec 2003 14:34:51 -0000
*************** static bool invariant_rtx_wrto_regs_p (r
*** 39,52 ****
static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
bool *);
! static bool simple_loop_exit_p (struct loops *, struct loop *, edge, regset,
rtx *, struct loop_desc *);
static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
static rtx variable_initial_values (edge, rtx, enum machine_mode);
static bool simple_condition_p (struct loop *, rtx, regset,
struct loop_desc *);
! static basic_block simple_increment (struct loops *, struct loop *, rtx *,
! struct loop_desc *);
static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
int, rtx, enum machine_mode,
enum machine_mode);
--- 39,51 ----
static rtx test_for_iteration (struct loop_desc *desc, unsigned HOST_WIDE_INT);
static bool constant_iterations (struct loop_desc *, unsigned HOST_WIDE_INT *,
bool *);
! static bool simple_loop_exit_p (struct loop *, edge, regset,
rtx *, struct loop_desc *);
static rtx variable_initial_value (rtx, regset, rtx, rtx *, enum machine_mode);
static rtx variable_initial_values (edge, rtx, enum machine_mode);
static bool simple_condition_p (struct loop *, rtx, regset,
struct loop_desc *);
! static basic_block simple_increment (struct loop *, rtx *, struct loop_desc *);
static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
int, rtx, enum machine_mode,
enum machine_mode);
*************** inverse (unsigned HOST_WIDEST_INT x, int
*** 73,82 ****
/* Checks whether BB is executed exactly once in each LOOP iteration. */
bool
! just_once_each_iteration_p (struct loops *loops, struct loop *loop, basic_block bb)
{
/* It must be executed at least once each iteration. */
! if (!dominated_by_p (loops->cfg.dom, loop->latch, bb))
return false;
/* And just once. */
--- 72,81 ----
/* Checks whether BB is executed exactly once in each LOOP iteration. */
bool
! just_once_each_iteration_p (struct loop *loop, basic_block bb)
{
/* It must be executed at least once each iteration. */
! if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
return false;
/* And just once. */
*************** simple_condition_p (struct loop *loop AT
*** 295,302 ****
iteration. Fills in DESC->stride and returns block in that DESC->var is
modified. */
static basic_block
! simple_increment (struct loops *loops, struct loop *loop,
! rtx *simple_increment_regs, struct loop_desc *desc)
{
rtx mod_insn, mod_insn1, set, set_src, set_add;
basic_block mod_bb, mod_bb1;
--- 294,301 ----
iteration. Fills in DESC->stride and returns block in that DESC->var is
modified. */
static basic_block
! simple_increment (struct loop *loop, rtx *simple_increment_regs,
! struct loop_desc *desc)
{
rtx mod_insn, mod_insn1, set, set_src, set_add;
basic_block mod_bb, mod_bb1;
*************** simple_increment (struct loops *loops, s
*** 308,314 ****
mod_bb = BLOCK_FOR_INSN (mod_insn);
/* Check that it is executed exactly once each iteration. */
! if (!just_once_each_iteration_p (loops, loop, mod_bb))
return NULL;
/* mod_insn must be a simple increment/decrement. */
--- 307,313 ----
mod_bb = BLOCK_FOR_INSN (mod_insn);
/* Check that it is executed exactly once each iteration. */
! if (!just_once_each_iteration_p (loop, mod_bb))
return NULL;
/* mod_insn must be a simple increment/decrement. */
*************** simple_increment (struct loops *loops, s
*** 355,361 ****
return NULL;
mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
! if (!dominated_by_p (loops->cfg.dom, mod_bb, mod_bb1))
return NULL;
if (mod_bb1 == mod_bb)
{
--- 354,360 ----
return NULL;
mod_bb1 = BLOCK_FOR_INSN (mod_insn1);
! if (!dominated_by_p (CDI_DOMINATORS, mod_bb, mod_bb1))
return NULL;
if (mod_bb1 == mod_bb)
{
*************** test_for_iteration (struct loop_desc *de
*** 962,968 ****
description joined to it in in DESC. INVARIANT_REGS and SINGLE_SET_REGS
are results of blocks_{invariant,single_set}_regs over BODY. */
static bool
! simple_loop_exit_p (struct loops *loops, struct loop *loop, edge exit_edge,
regset invariant_regs, rtx *single_set_regs,
struct loop_desc *desc)
{
--- 961,967 ----
description joined to it in in DESC. INVARIANT_REGS and SINGLE_SET_REGS
are results of blocks_{invariant,single_set}_regs over BODY. */
static bool
! simple_loop_exit_p (struct loop *loop, edge exit_edge,
regset invariant_regs, rtx *single_set_regs,
struct loop_desc *desc)
{
*************** simple_loop_exit_p (struct loops *loops,
*** 979,985 ****
return false;
/* It must be tested (at least) once during any iteration. */
! if (!dominated_by_p (loops->cfg.dom, loop->latch, exit_bb))
return false;
/* It must end in a simple conditional jump. */
--- 978,984 ----
return false;
/* It must be tested (at least) once during any iteration. */
! if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
return false;
/* It must end in a simple conditional jump. */
*************** simple_loop_exit_p (struct loops *loops,
*** 1003,1013 ****
/* Var must be simply incremented or decremented in exactly one insn that
is executed just once every iteration. */
! if (!(mod_bb = simple_increment (loops, loop, single_set_regs, desc)))
return false;
/* OK, it is simple loop. Now just fill in remaining info. */
! desc->postincr = !dominated_by_p (loops->cfg.dom, exit_bb, mod_bb);
desc->neg = !fallthru_out;
/* Find initial value of var and alternative values for lim. */
--- 1002,1012 ----
/* Var must be simply incremented or decremented in exactly one insn that
is executed just once every iteration. */
! if (!(mod_bb = simple_increment (loop, single_set_regs, desc)))
return false;
/* OK, it is simple loop. Now just fill in remaining info. */
! desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
desc->neg = !fallthru_out;
/* Find initial value of var and alternative values for lim. */
*************** simple_loop_exit_p (struct loops *loops,
*** 1026,1032 ****
/* Tests whether LOOP is simple for loop. Returns simple loop description
in DESC. */
bool
! simple_loop_p (struct loops *loops, struct loop *loop, struct loop_desc *desc)
{
unsigned i;
basic_block *body;
--- 1025,1031 ----
/* Tests whether LOOP is simple for loop. Returns simple loop description
in DESC. */
bool
! simple_loop_p (struct loop *loop, struct loop_desc *desc)
{
unsigned i;
basic_block *body;
*************** simple_loop_p (struct loops *loops, stru
*** 1051,1057 ****
{
for (e = body[i]->succ; e; e = e->succ_next)
if (!flow_bb_inside_loop_p (loop, e->dest)
! && simple_loop_exit_p (loops, loop, e,
invariant_regs, single_set_regs, &act))
{
/* Prefer constant iterations; the less the better. */
--- 1050,1056 ----
{
for (e = body[i]->succ; e; e = e->succ_next)
if (!flow_bb_inside_loop_p (loop, e->dest)
! && simple_loop_exit_p (loop, e,
invariant_regs, single_set_regs, &act))
{
/* Prefer constant iterations; the less the better. */
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.3.2.9
diff -c -3 -p -r1.3.2.9 cfgloopmanip.c
*** cfgloopmanip.c 13 Nov 2003 02:37:37 -0000 1.3.2.9
--- cfgloopmanip.c 18 Dec 2003 14:34:51 -0000
*************** static void copy_loops_to (struct loops
*** 36,44 ****
struct loop *);
static void loop_redirect_edge (edge, basic_block);
static bool loop_delete_branch_edge (edge, int);
! static void remove_bbs (dominance_info, basic_block *, int);
static bool rpe_enum_p (basic_block, void *);
! static int find_path (edge, dominance_info, basic_block **);
static bool alp_enum_p (basic_block, void *);
static void add_loop (struct loops *, struct loop *);
static void fix_loop_placements (struct loop *);
--- 36,44 ----
struct loop *);
static void loop_redirect_edge (edge, basic_block);
static bool loop_delete_branch_edge (edge, int);
! static void remove_bbs (basic_block *, int);
static bool rpe_enum_p (basic_block, void *);
! static int find_path (edge, basic_block **);
static bool alp_enum_p (basic_block, void *);
static void add_loop (struct loops *, struct loop *);
static void fix_loop_placements (struct loop *);
*************** static void fix_bb_placements (struct lo
*** 47,63 ****
static void place_new_loop (struct loops *, struct loop *);
static void scale_loop_frequencies (struct loop *, int, int);
static void scale_bbs_frequencies (basic_block *, int, int, int);
! static basic_block create_preheader (struct loop *, dominance_info, int);
static void fix_irreducible_loops (basic_block);
/* Splits basic block BB after INSN, returns created edge. Updates loops
and dominators. */
edge
! split_loop_bb (struct loops *loops, basic_block bb, rtx insn)
{
edge e;
- basic_block *dom_bbs;
- int n_dom_bbs, i;
/* Split the block. */
e = split_block (bb, insn);
--- 47,61 ----
static void place_new_loop (struct loops *, struct loop *);
static void scale_loop_frequencies (struct loop *, int, int);
static void scale_bbs_frequencies (basic_block *, int, int, int);
! static basic_block create_preheader (struct loop *, int);
static void fix_irreducible_loops (basic_block);
/* Splits basic block BB after INSN, returns created edge. Updates loops
and dominators. */
edge
! split_loop_bb (basic_block bb, rtx insn)
{
edge e;
/* Split the block. */
e = split_block (bb, insn);
*************** split_loop_bb (struct loops *loops, basi
*** 66,107 ****
add_bb_to_loop (e->dest, e->src->loop_father);
/* Fix dominators. */
! add_to_dominance_info (loops->cfg.dom, e->dest);
! n_dom_bbs = get_dominated_by (loops->cfg.dom, e->src, &dom_bbs);
! for (i = 0; i < n_dom_bbs; i++)
! set_immediate_dominator (loops->cfg.dom, dom_bbs[i], e->dest);
! free (dom_bbs);
! set_immediate_dominator (loops->cfg.dom, e->dest, e->src);
return e;
}
! /* Checks whether basic block BB is dominated by RPE->DOM, where
! RPE is passed through DATA. */
! struct rpe_data
! {
! basic_block dom;
! dominance_info doms;
! };
!
static bool
rpe_enum_p (basic_block bb, void *data)
{
! struct rpe_data *rpe = data;
! return dominated_by_p (rpe->doms, bb, rpe->dom);
}
/* Remove basic blocks BBS from loop structure and dominance info,
and delete them afterwards. */
static void
! remove_bbs (dominance_info dom, basic_block *bbs, int nbbs)
{
int i;
for (i = 0; i < nbbs; i++)
{
remove_bb_from_loops (bbs[i]);
! delete_from_dominance_info (dom, bbs[i]);
delete_basic_block (bbs[i]);
}
}
--- 64,94 ----
add_bb_to_loop (e->dest, e->src->loop_father);
/* Fix dominators. */
! add_to_dominance_info (CDI_DOMINATORS, e->dest);
! redirect_immediate_dominators (CDI_DOMINATORS, e->src, e->dest);
! set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
return e;
}
! /* Checks whether basic block BB is dominated by DATA. */
static bool
rpe_enum_p (basic_block bb, void *data)
{
! return dominated_by_p (CDI_DOMINATORS, bb, data);
}
/* Remove basic blocks BBS from loop structure and dominance info,
and delete them afterwards. */
static void
! remove_bbs (basic_block *bbs, int nbbs)
{
int i;
for (i = 0; i < nbbs; i++)
{
remove_bb_from_loops (bbs[i]);
! delete_from_dominance_info (CDI_DOMINATORS, bbs[i]);
delete_basic_block (bbs[i]);
}
}
*************** remove_bbs (dominance_info dom, basic_bl
*** 113,131 ****
alter anything by this function). The number of basic blocks in the
path is returned. */
static int
! find_path (edge e, dominance_info doms, basic_block **bbs)
{
- struct rpe_data rpe;
-
if (e->dest->pred->pred_next)
abort ();
/* Find bbs in the path. */
- rpe.dom = e->dest;
- rpe.doms = doms;
*bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
! n_basic_blocks, &rpe);
}
/* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
--- 100,114 ----
alter anything by this function). The number of basic blocks in the
path is returned. */
static int
! find_path (edge e, basic_block **bbs)
{
if (e->dest->pred->pred_next)
abort ();
/* Find bbs in the path. */
*bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
! n_basic_blocks, e->dest);
}
/* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
*************** remove_path (struct loops *loops, edge e
*** 353,371 ****
fix -- when e->dest has exactly one predecessor, this corresponds
to blocks dominated by e->dest, if not, split the edge. */
if (e->dest->pred->pred_next)
! e = loop_split_edge_with (e, NULL_RTX, loops)->pred;
/* It may happen that by removing path we remove one or more loops
we belong to. In this case first unloop the loops, then proceed
normally. We may assume that e->dest is not a header of any loop,
as it now has exactly one predecessor. */
while (e->src->loop_father->outer
! && dominated_by_p (loops->cfg.dom,
e->src->loop_father->latch, e->dest))
unloop (loops, e->src->loop_father);
/* Identify the path. */
! nrem = find_path (e, loops->cfg.dom, &rem_bbs);
n_bord_bbs = 0;
bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
--- 336,354 ----
fix -- when e->dest has exactly one predecessor, this corresponds
to blocks dominated by e->dest, if not, split the edge. */
if (e->dest->pred->pred_next)
! e = loop_split_edge_with (e, NULL_RTX)->pred;
/* It may happen that by removing path we remove one or more loops
we belong to. In this case first unloop the loops, then proceed
normally. We may assume that e->dest is not a header of any loop,
as it now has exactly one predecessor. */
while (e->src->loop_father->outer
! && dominated_by_p (CDI_DOMINATORS,
e->src->loop_father->latch, e->dest))
unloop (loops, e->src->loop_father);
/* Identify the path. */
! nrem = find_path (e, &rem_bbs);
n_bord_bbs = 0;
bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
*************** remove_path (struct loops *loops, edge e
*** 397,403 ****
if (rem_bbs[i]->loop_father->header == rem_bbs[i])
cancel_loop_tree (loops, rem_bbs[i]->loop_father);
! remove_bbs (loops->cfg.dom, rem_bbs, nrem);
free (rem_bbs);
/* Find blocks whose dominators may be affected. */
--- 380,386 ----
if (rem_bbs[i]->loop_father->header == rem_bbs[i])
cancel_loop_tree (loops, rem_bbs[i]->loop_father);
! remove_bbs (rem_bbs, nrem);
free (rem_bbs);
/* Find blocks whose dominators may be affected. */
*************** remove_path (struct loops *loops, edge e
*** 405,429 ****
sbitmap_zero (seen);
for (i = 0; i < n_bord_bbs; i++)
{
! int j, nldom;
! basic_block *ldom;
! bb = get_immediate_dominator (loops->cfg.dom, bord_bbs[i]);
if (TEST_BIT (seen, bb->index))
continue;
SET_BIT (seen, bb->index);
! nldom = get_dominated_by (loops->cfg.dom, bb, &ldom);
! for (j = 0; j < nldom; j++)
! if (!dominated_by_p (loops->cfg.dom, from, ldom[j]))
! dom_bbs[n_dom_bbs++] = ldom[j];
! free(ldom);
}
free (seen);
/* Recount dominators. */
! iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
free (dom_bbs);
/* These blocks have lost some predecessor(s), thus their irreducible
--- 388,411 ----
sbitmap_zero (seen);
for (i = 0; i < n_bord_bbs; i++)
{
! basic_block ldom;
! bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
if (TEST_BIT (seen, bb->index))
continue;
SET_BIT (seen, bb->index);
! for (ldom = first_dom_son (CDI_DOMINATORS, bb);
! ldom;
! ldom = next_dom_son (CDI_DOMINATORS, ldom))
! if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
! dom_bbs[n_dom_bbs++] = ldom;
}
free (seen);
/* Recount dominators. */
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
free (dom_bbs);
/* These blocks have lost some predecessor(s), thus their irreducible
*************** loopify (struct loops *loops, edge latch
*** 513,519 ****
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
basic_block *dom_bbs, *body;
! unsigned n_dom_bbs, i, j;
sbitmap seen;
struct loop *loop = xcalloc (1, sizeof (struct loop));
struct loop *outer = succ_bb->loop_father->outer;
--- 495,501 ----
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
basic_block *dom_bbs, *body;
! unsigned n_dom_bbs, i;
sbitmap seen;
struct loop *loop = xcalloc (1, sizeof (struct loop));
struct loop *outer = succ_bb->loop_father->outer;
*************** loopify (struct loops *loops, edge latch
*** 538,546 ****
loop_redirect_edge (switch_bb->succ, succ_bb);
/* Update dominators. */
! set_immediate_dominator (loops->cfg.dom, switch_bb, pred_bb);
! set_immediate_dominator (loops->cfg.dom, loop->header, switch_bb);
! set_immediate_dominator (loops->cfg.dom, succ_bb, switch_bb);
/* Compute new loop. */
add_loop (loops, loop);
--- 520,528 ----
loop_redirect_edge (switch_bb->succ, succ_bb);
/* Update dominators. */
! set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
! set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
! set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
/* Compute new loop. */
add_loop (loops, loop);
*************** loopify (struct loops *loops, edge latch
*** 569,588 ****
for (i = 0; i < loop->num_nodes; i++)
{
! unsigned nldom;
! basic_block *ldom;
! nldom = get_dominated_by (loops->cfg.dom, body[i], &ldom);
! for (j = 0; j < nldom; j++)
! if (!TEST_BIT (seen, ldom[j]->index))
{
! SET_BIT (seen, ldom[j]->index);
! dom_bbs[n_dom_bbs++] = ldom[j];
}
- free (ldom);
}
! iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
free (body);
free (seen);
--- 551,569 ----
for (i = 0; i < loop->num_nodes; i++)
{
! basic_block ldom;
! for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
! ldom;
! ldom = next_dom_son (CDI_DOMINATORS, ldom))
! if (!TEST_BIT (seen, ldom->index))
{
! SET_BIT (seen, ldom->index);
! dom_bbs[n_dom_bbs++] = ldom;
}
}
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
free (body);
free (seen);
*************** duplicate_loop_to_header_edge (struct lo
*** 990,996 ****
copy_loops_to (loops, orig_loops, n_orig_loops, target);
/* Copy bbs. */
! copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, loops);
/* Note whether the blocks and edges belong to an irreducible loop. */
if (add_irreducible_flag)
--- 971,977 ----
copy_loops_to (loops, orig_loops, n_orig_loops, target);
/* Copy bbs. */
! copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop);
/* Note whether the blocks and edges belong to an irreducible loop. */
if (add_irreducible_flag)
*************** duplicate_loop_to_header_edge (struct lo
*** 1019,1025 ****
redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
loop->header);
! set_immediate_dominator (loops->cfg.dom, new_bbs[0], latch);
latch = loop->latch = new_bbs[1];
e = latch_edge = new_spec_edges[SE_LATCH];
}
--- 1000,1006 ----
redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
loop->header);
! set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
latch = loop->latch = new_bbs[1];
e = latch_edge = new_spec_edges[SE_LATCH];
}
*************** duplicate_loop_to_header_edge (struct lo
*** 1028,1034 ****
redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
loop->header);
redirect_edge_and_branch_force (e, new_bbs[0]);
! set_immediate_dominator (loops->cfg.dom, new_bbs[0], e->src);
e = new_spec_edges[SE_LATCH];
}
--- 1009,1015 ----
redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
loop->header);
redirect_edge_and_branch_force (e, new_bbs[0]);
! set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
e = new_spec_edges[SE_LATCH];
}
*************** duplicate_loop_to_header_edge (struct lo
*** 1056,1062 ****
/* Update the original loop. */
if (!is_latch)
! set_immediate_dominator (loops->cfg.dom, e->dest, e->src);
if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
scale_bbs_frequencies (bbs, n, scale_main, REG_BR_PROB_BASE);
--- 1037,1043 ----
/* Update the original loop. */
if (!is_latch)
! set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
scale_bbs_frequencies (bbs, n, scale_main, REG_BR_PROB_BASE);
*************** duplicate_loop_to_header_edge (struct lo
*** 1070,1084 ****
int n_dom_bbs,j;
bb = bbs[i];
! n_dom_bbs = get_dominated_by (loops->cfg.dom, bb, &dom_bbs);
for (j = 0; j < n_dom_bbs; j++)
{
dominated = dom_bbs[j];
if (flow_bb_inside_loop_p (loop, dominated))
continue;
dom_bb = nearest_common_dominator (
! loops->cfg.dom, first_active[i], first_active_latch);
! set_immediate_dominator (loops->cfg.dom, dominated, dom_bb);
}
free (dom_bbs);
}
--- 1051,1065 ----
int n_dom_bbs,j;
bb = bbs[i];
! n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
for (j = 0; j < n_dom_bbs; j++)
{
dominated = dom_bbs[j];
if (flow_bb_inside_loop_p (loop, dominated))
continue;
dom_bb = nearest_common_dominator (
! CDI_DOMINATORS, first_active[i], first_active_latch);
! set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
}
free (dom_bbs);
}
*************** duplicate_loop_to_header_edge (struct lo
*** 1094,1100 ****
entry; otherwise we also force preheader block to have only one successor.
The function also updates dominators stored in DOM. */
static basic_block
! create_preheader (struct loop *loop, dominance_info dom, int flags)
{
edge e, fallthru;
basic_block dummy;
--- 1075,1081 ----
entry; otherwise we also force preheader block to have only one successor.
The function also updates dominators stored in DOM. */
static basic_block
! create_preheader (struct loop *loop, int flags)
{
edge e, fallthru;
basic_block dummy;
*************** create_preheader (struct loop *loop, dom
*** 1141,1147 ****
if (ploop->latch == dummy)
ploop->latch = fallthru->dest;
! add_to_dominance_info (dom, fallthru->dest);
/* Redirect edges. */
for (e = dummy->pred; e; e = e->pred_next)
--- 1122,1128 ----
if (ploop->latch == dummy)
ploop->latch = fallthru->dest;
! add_to_dominance_info (CDI_DOMINATORS, fallthru->dest);
/* Redirect edges. */
for (e = dummy->pred; e; e = e->pred_next)
*************** create_preheader (struct loop *loop, dom
*** 1159,1173 ****
jump = redirect_edge_and_branch_force (e, loop->header);
if (jump)
{
! add_to_dominance_info (dom, jump);
! set_immediate_dominator (dom, jump, src);
add_bb_to_loop (jump, loop);
loop->latch = jump;
}
/* Update structures. */
! redirect_immediate_dominators (dom, dummy, loop->header);
! set_immediate_dominator (dom, loop->header, dummy);
loop->header->loop_father = loop;
add_bb_to_loop (dummy, cloop);
if (rtl_dump_file)
--- 1140,1154 ----
jump = redirect_edge_and_branch_force (e, loop->header);
if (jump)
{
! add_to_dominance_info (CDI_DOMINATORS, jump);
! set_immediate_dominator (CDI_DOMINATORS, jump, src);
add_bb_to_loop (jump, loop);
loop->latch = jump;
}
/* Update structures. */
! redirect_immediate_dominators (CDI_DOMINATORS, dummy, loop->header);
! set_immediate_dominator (CDI_DOMINATORS, loop->header, dummy);
loop->header->loop_father = loop;
add_bb_to_loop (dummy, cloop);
if (rtl_dump_file)
*************** create_preheaders (struct loops *loops,
*** 1184,1190 ****
{
unsigned i;
for (i = 1; i < loops->num; i++)
! create_preheader (loops->parray[i], loops->cfg.dom, flags);
loops->state |= LOOPS_HAVE_PREHEADERS;
}
--- 1165,1171 ----
{
unsigned i;
for (i = 1; i < loops->num; i++)
! create_preheader (loops->parray[i], flags);
loops->state |= LOOPS_HAVE_PREHEADERS;
}
*************** force_single_succ_latches (struct loops
*** 1207,1213 ****
for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
continue;
! loop_split_edge_with (e, NULL_RTX, loops);
}
loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
}
--- 1188,1194 ----
for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
continue;
! loop_split_edge_with (e, NULL_RTX);
}
loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
}
*************** force_single_succ_latches (struct loops
*** 1217,1223 ****
be ok after this function. The created block is placed on correct place
in LOOPS structure and its dominator is set. */
basic_block
! loop_split_edge_with (edge e, rtx insns, struct loops *loops)
{
basic_block src, dest, new_bb;
struct loop *loop_c;
--- 1198,1204 ----
be ok after this function. The created block is placed on correct place
in LOOPS structure and its dominator is set. */
basic_block
! loop_split_edge_with (edge e, rtx insns)
{
basic_block src, dest, new_bb;
struct loop *loop_c;
*************** loop_split_edge_with (edge e, rtx insns,
*** 1231,1237 ****
/* Create basic block for it. */
new_bb = split_edge (e);
! add_to_dominance_info (loops->cfg.dom, new_bb);
add_bb_to_loop (new_bb, loop_c);
new_bb->flags = insns ? BB_SUPERBLOCK : 0;
--- 1212,1218 ----
/* Create basic block for it. */
new_bb = split_edge (e);
! add_to_dominance_info (CDI_DOMINATORS, new_bb);
add_bb_to_loop (new_bb, loop_c);
new_bb->flags = insns ? BB_SUPERBLOCK : 0;
*************** loop_split_edge_with (edge e, rtx insns,
*** 1245,1253 ****
if (insns)
emit_insn_after (insns, new_bb->end);
! set_immediate_dominator (loops->cfg.dom, new_bb, src);
! set_immediate_dominator (loops->cfg.dom, dest,
! recount_dominator (loops->cfg.dom, dest));
if (dest->loop_father->latch == src)
dest->loop_father->latch = new_bb;
--- 1226,1234 ----
if (insns)
emit_insn_after (insns, new_bb->end);
! set_immediate_dominator (CDI_DOMINATORS, new_bb, src);
! set_immediate_dominator (CDI_DOMINATORS, dest,
! recount_dominator (CDI_DOMINATORS, dest));
if (dest->loop_father->latch == src)
dest->loop_father->latch = new_bb;
*************** create_loop_notes (void)
*** 1274,1279 ****
--- 1255,1261 ----
#endif
flow_loops_find (&loops, LOOP_TREE);
+ free_dominance_info (CDI_DOMINATORS);
if (loops.num > 1)
{
last = xcalloc (loops.num, sizeof (basic_block));
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dominance.c,v
retrieving revision 1.10.2.9
diff -c -3 -p -r1.10.2.9 dominance.c
*** dominance.c 25 Oct 2003 17:48:23 -0000 1.10.2.9
--- dominance.c 18 Dec 2003 14:34:51 -0000
***************
*** 43,59 ****
#include "errors.h"
#include "et-forest.h"
! struct dominance_info
! {
! et_forest_t forest;
! varray_type varray;
! basic_block *idom;
! };
!
! #define BB_NODE(info, bb) \
! ((et_forest_node_t)VARRAY_GENERIC_PTR_NOGC ((info)->varray, (bb)->index + 2))
! #define SET_BB_NODE(info, bb, node) \
! (VARRAY_GENERIC_PTR_NOGC ((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
--- 43,50 ----
#include "errors.h"
#include "et-forest.h"
! /* Whether the dominators and the postdominators are available. */
! enum dom_state dom_computed[2];
/* 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 void compress (struct dom_info *,
*** 125,131 ****
static TBB eval (struct dom_info *, TBB);
static void link_roots (struct dom_info *, TBB, TBB);
static void calc_idoms (struct dom_info *, enum cdi_direction);
! void debug_dominance_info (dominance_info);
/* Helper macro for allocating and initializing an array,
for aesthetic reasons. */
--- 116,122 ----
static TBB eval (struct dom_info *, TBB);
static void link_roots (struct dom_info *, TBB, TBB);
static void calc_idoms (struct dom_info *, enum cdi_direction);
! void debug_dominance_info (enum cdi_direction);
/* Helper macro for allocating and initializing an array,
for aesthetic reasons. */
*************** calc_idoms (struct dom_info *di, enum cd
*** 527,711 ****
di->dom[v] = di->dom[di->dom[v]];
}
! /* 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
! know post-dominators.
!
! On return IDOM[i] will be the BB->index of the immediate (post) dominator
! of basic block i, and DOMS[i] will have set bit j if basic block j is a
! (post)dominator for block i.
! Either IDOM or DOMS may be NULL (meaning the caller is not interested in
! immediate resp. all dominators). */
! dominance_info
! calculate_dominance_info (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 ();
! info->idom = xcalloc (last_basic_block, sizeof (basic_block));
! VARRAY_GENERIC_PTR_NOGC_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 (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->idom);
! free (info);
}
/* Return the immediate dominator of basic block BB. */
basic_block
! get_immediate_dominator (dominance_info dom, basic_block bb)
{
! basic_block answer;
! if (bb->index >= 0 && dom->idom[bb->index] != NULL)
! return dom->idom[bb->index];
! answer = et_forest_node_value (dom->forest,
! et_forest_parent (dom->forest,
! BB_NODE (dom, bb)));
! if (bb->index >= 0)
! dom->idom[bb->index] = answer;
! return answer;
}
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
inline void
! set_immediate_dominator (dominance_info dom, basic_block bb, basic_block 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 ();
}
! if (bb->index >= 0)
! dom->idom[bb->index] = dominated_by;
}
! /* Store all basic blocks dominated by BB into BBS and return their number. */
int
! get_dominated_by (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 (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;
!
! memset (dom->idom, 0, last_basic_block * sizeof (basic_block));
! 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 (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 (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 (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;
}
}
--- 518,767 ----
di->dom[v] = di->dom[di->dom[v]];
}
! /* Assign dfs numbers starting from NUM to NODE and its sons. */
!
! static void
! assign_dfs_numbers (struct et_node *node, int *num)
! {
! struct et_node *son;
!
! node->dfs_num_in = (*num)++;
!
! if (node->son)
! {
! assign_dfs_numbers (node->son, num);
! for (son = node->son->right; son != node->son; son = son->right)
! assign_dfs_numbers (son, num);
! }
!
! node->dfs_num_out = (*num)++;
! }
!
! /* Compute the data neccesary for fast resolving of dominator queries in a
! static dominator tree. */
!
! static void
! compute_dom_fast_query (enum cdi_direction dir)
! {
! int num = 0;
! basic_block bb;
!
! if (dom_computed[dir] < DOM_NO_FAST_QUERY)
! abort ();
!
! if (dom_computed[dir] == DOM_OK)
! return;
!
! FOR_ALL_BB (bb)
! {
! if (!bb->dom[dir]->father)
! assign_dfs_numbers (bb->dom[dir], &num);
! }
!
! dom_computed[dir] = DOM_OK;
! }
! /* The main entry point into this module. DIR is set depending on whether
! we want to compute dominators or postdominators. */
! void
! calculate_dominance_info (enum cdi_direction dir)
{
struct dom_info di;
basic_block b;
! if (dom_computed[dir] == DOM_OK)
! return;
! if (dom_computed[dir] != DOM_NO_FAST_QUERY)
! {
! if (dom_computed[dir] != DOM_NONE)
! free_dominance_info (dir);
! FOR_ALL_BB (b)
! {
! b->dom[dir] = et_new_tree (b);
! }
! init_dom_info (&di);
! calc_dfs_tree (&di, dir);
! calc_idoms (&di, dir);
+ FOR_EACH_BB (b)
+ {
+ TBB d = di.dom[di.dfs_order[b->index]];
! if (di.dfs_to_bb[d])
! et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]);
! }
! free_dom_info (&di);
! dom_computed[dir] = DOM_NO_FAST_QUERY;
}
! compute_dom_fast_query (dir);
}
! /* Free dominance information for direction DIR. */
void
! free_dominance_info (enum cdi_direction dir)
{
basic_block bb;
! if (!dom_computed[dir])
! return;
!
! FOR_ALL_BB (bb)
! {
! delete_from_dominance_info (dir, bb);
! }
!
! dom_computed[dir] = DOM_NONE;
}
/* Return the immediate dominator of basic block BB. */
basic_block
! get_immediate_dominator (enum cdi_direction dir, basic_block bb)
{
! struct et_node *node = bb->dom[dir];
!
! if (!dom_computed[dir])
! abort ();
!
! if (!node->father)
! return NULL;
+ return node->father->data;
}
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
inline void
! set_immediate_dominator (enum cdi_direction dir, basic_block bb,
! basic_block dominated_by)
{
! struct et_node *node = bb->dom[dir];
! if (!dom_computed[dir])
! abort ();
!
! if (node->father)
{
! if (node->father->data == dominated_by)
! return;
! et_split (node);
}
!
! if (dominated_by)
! et_set_father (node, dominated_by->dom[dir]);
!
! if (dom_computed[dir] == DOM_OK)
! dom_computed[dir] = DOM_NO_FAST_QUERY;
}
! /* Store all basic blocks immediatelly dominated by BB into BBS and return
! their number. */
int
! get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
{
! int n;
! struct et_node *node = bb->dom[dir], *son = node->son, *ason;
!
! if (!dom_computed[dir])
! abort ();
!
! if (!son)
! {
! *bbs = NULL;
! return 0;
! }
!
! for (ason = son->right, n = 1; ason != son; ason = ason->right)
! n++;
!
! *bbs = xmalloc (n * sizeof (basic_block));
! (*bbs)[0] = son->data;
! for (ason = son->right, n = 1; ason != son; ason = ason->right)
! (*bbs)[n++] = ason->data;
return n;
}
/* Redirect all edges pointing to BB to TO. */
void
! redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
! basic_block to)
{
! struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
!
! if (!dom_computed[dir])
! abort ();
!
! if (!bb_node->son)
! return;
!
! while (bb_node->son)
{
! son = bb_node->son;
!
! et_split (son);
! et_set_father (son, to_node);
}
!
! if (dom_computed[dir] == DOM_OK)
! dom_computed[dir] = DOM_NO_FAST_QUERY;
}
/* Find first basic block in the tree dominating both BB1 and BB2. */
basic_block
! nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
{
+ if (!dom_computed[dir])
+ abort ();
+
if (!bb1)
return bb2;
if (!bb2)
return bb1;
!
! return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
}
/* Return TRUE in case BB1 is dominated by BB2. */
bool
! dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
! {
! struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir];
!
! if (!dom_computed[dir])
! abort ();
!
! if (dom_computed[dir] == DOM_OK)
! return (n1->dfs_num_in >= n2->dfs_num_in
! && n1->dfs_num_out <= n2->dfs_num_out);
!
! return et_below (n1, n2);
}
/* Verify invariants of dominator structure. */
void
! verify_dominators (enum cdi_direction dir)
{
int err = 0;
basic_block bb;
+ if (!dom_computed[dir])
+ abort ();
+
FOR_EACH_BB (bb)
{
basic_block dom_bb;
! dom_bb = recount_dominator (dir, bb);
! if (dom_bb != get_immediate_dominator (dir, bb))
{
error ("dominator of %d should be %d, not %d",
! bb->index, dom_bb->index, get_immediate_dominator(dir, bb)->index);
err = 1;
}
}
*************** verify_dominators (dominance_info dom)
*** 715,729 ****
/* Recount dominator of BB. */
basic_block
! recount_dominator (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;
--- 771,788 ----
/* Recount dominator of BB. */
basic_block
! recount_dominator (enum cdi_direction dir, basic_block bb)
{
basic_block dom_bb = NULL;
edge e;
+ if (!dom_computed[dir])
+ abort ();
+
for (e = bb->pred; e; e = e->pred_next)
{
! if (!dominated_by_p (dir, e->src, bb))
! dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
}
return dom_bb;
*************** recount_dominator (dominance_info dom, b
*** 732,786 ****
/* Iteratively recount dominators of BBS. The change is supposed to be local
and not to grow further. */
void
! iterate_fix_dominators (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 (dominance_info dom, basic_block bb)
{
! VARRAY_GROW (dom->varray, last_basic_block + 3);
! dom->idom = xrealloc (dom->idom, last_basic_block * sizeof (basic_block));
! #ifdef ENABLE_CHECKING
! if (BB_NODE (dom, bb))
! abort ();
! #endif
! SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
! if (bb->index >= 0)
! dom->idom[bb->index] = NULL;
}
void
! delete_from_dominance_info (dominance_info dom, basic_block bb)
{
! et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
! if (bb->index >= 0)
! dom->idom[bb->index] = NULL;
! SET_BB_NODE (dom, bb, NULL);
}
void
! debug_dominance_info (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);
}
--- 791,875 ----
/* Iteratively recount dominators of BBS. The change is supposed to be local
and not to grow further. */
void
! iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
{
int i, changed = 1;
basic_block old_dom, new_dom;
+ if (!dom_computed[dir])
+ abort ();
+
while (changed)
{
changed = 0;
for (i = 0; i < n; i++)
{
! old_dom = get_immediate_dominator (dir, bbs[i]);
! new_dom = recount_dominator (dir, bbs[i]);
if (old_dom != new_dom)
{
changed = 1;
! set_immediate_dominator (dir, bbs[i], new_dom);
}
}
}
}
void
! add_to_dominance_info (enum cdi_direction dir, basic_block bb)
{
! if (!dom_computed[dir])
! abort ();
!
! if (bb->dom[dir])
! abort ();
!
! bb->dom[dir] = et_new_tree (bb);
!
! if (dom_computed[dir] == DOM_OK)
! dom_computed[dir] = DOM_NO_FAST_QUERY;
}
void
! delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
! {
! if (!dom_computed[dir])
! abort ();
!
! et_free_tree (bb->dom[dir]);
! bb->dom[dir] = NULL;
!
! if (dom_computed[dir] == DOM_OK)
! dom_computed[dir] = DOM_NO_FAST_QUERY;
! }
!
! /* Returns the first son of BB in the dominator or postdominator tree
! as determined by DIR. */
!
! basic_block
! first_dom_son (enum cdi_direction dir, basic_block bb)
{
! struct et_node *son = bb->dom[dir]->son;
!
! return son ? son->data : NULL;
! }
!
! /* Returns the next dominance son after BB in the dominator or postdominator
! tree as determined by DIR, or NULL if it was the last one. */
!
! extern basic_block
! next_dom_son (enum cdi_direction dir, basic_block bb)
! {
! struct et_node *next = bb->dom[dir]->right;
!
! return next->father->son == next ? NULL : next->data;
}
void
! debug_dominance_info (enum cdi_direction dir)
{
basic_block bb, bb2;
FOR_EACH_BB (bb)
! if ((bb2 = get_immediate_dominator (dir, bb)))
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
}
Index: domwalk.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/domwalk.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 domwalk.c
*** domwalk.c 26 Nov 2003 03:22:23 -0000 1.1.2.5
--- domwalk.c 18 Dec 2003 14:34:51 -0000
*************** walk_dominator_tree (struct dom_walk_dat
*** 60,67 ****
basic_block bb,
tree last)
{
- bitmap children;
void *bd = NULL;
/* Callback to initialize the local data structure. */
if (walk_data->initialize_block_local_data)
--- 60,68 ----
basic_block bb,
tree last)
{
void *bd = NULL;
+ basic_block dest;
+ tree clast;
/* Callback to initialize the local data structure. */
if (walk_data->initialize_block_local_data)
*************** walk_dominator_tree (struct dom_walk_dat
*** 104,131 ****
if (walk_data->before_dom_children_after_stmts)
(*walk_data->before_dom_children_after_stmts) (walk_data, bb, last);
/* Recursively call ourselves on the dominator children of BB. */
! children = dom_children (bb);
! if (children)
{
! tree clast;
! unsigned long i;
!
! /* If this block ends with a control statement, pass it down
! so that we might reason with it. */
! clast = last_stmt (bb);
! if (clast && !is_ctrl_stmt (clast))
! clast = NULL;
!
! EXECUTE_IF_SET_IN_BITMAP (children, 0, i,
! {
! basic_block dest = BASIC_BLOCK (i);
!
! /* The destination block may have become unreachable, in
! which case there's no point in optimizing it. */
! if (dest->pred)
! walk_dominator_tree (walk_data, dest, clast);
! });
}
/* Callback for operations to execute after we have walked the
--- 105,125 ----
if (walk_data->before_dom_children_after_stmts)
(*walk_data->before_dom_children_after_stmts) (walk_data, bb, last);
+ /* If this block ends with a control statement, pass it down so that we
+ might reason with it. */
+ clast = last_stmt (bb);
+ if (clast && !is_ctrl_stmt (clast))
+ clast = NULL;
+
/* Recursively call ourselves on the dominator children of BB. */
! for (dest = first_dom_son (CDI_DOMINATORS, bb);
! dest;
! dest = next_dom_son (CDI_DOMINATORS, dest))
{
! /* The destination block may have become unreachable, in
! which case there's no point in optimizing it. */
! if (dest->pred)
! walk_dominator_tree (walk_data, dest, clast);
}
/* Callback for operations to execute after we have walked the
Index: et-forest.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/et-forest.c,v
retrieving revision 1.1.4.7
diff -c -3 -p -r1.1.4.7 et-forest.c
*** et-forest.c 21 Jul 2003 13:50:44 -0000 1.1.4.7
--- et-forest.c 18 Dec 2003 14:34:51 -0000
*************** Boston, MA 02111-1307, USA.
*** 30,667 ****
#include "et-forest.h"
#include "alloc-pool.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;
! alloc_pool node_pool;
! alloc_pool occur_pool;
};
! /* 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 (et_forest_occurrence_t);
! static void remove_all_occurrences (et_forest_t, et_forest_node_t);
! static inline et_forest_occurrence_t find_leftmost_node
! (et_forest_occurrence_t);
! static inline et_forest_occurrence_t find_rightmost_node
! (et_forest_occurrence_t);
! static int calculate_value (et_forest_occurrence_t);
! /* Return leftmost node present in the tree roted by OCC. */
! static inline et_forest_occurrence_t
! find_leftmost_node (et_forest_occurrence_t occ)
{
! while (occ->left)
! occ = occ->left;
! return occ;
}
! /* Return rightmost node present in the tree roted by OCC. */
! static inline et_forest_occurrence_t
! find_rightmost_node (et_forest_occurrence_t occ)
{
! while (occ->right)
! occ = occ->right;
! return occ;
}
! /* Operation splay for splay tree structure representing occurrences. */
! static et_forest_occurrence_t
! splay (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;
}
! /* Remove all occurrences of the given node before destroying the node. */
static void
! remove_all_occurrences (et_forest_t forest, 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 occurrences
! 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;
! pool_free (forest->occur_pool, 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;
! pool_free (forest->occur_pool, node);
! node = next_node;
! }
! }
! pool_free (forest->occur_pool, first);
! if (first != last)
! pool_free (forest->occur_pool, last);
}
! /* Calculate ET value of the given node. */
! static inline int
! calculate_value (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 (void)
{
! et_forest_t forest = xmalloc (sizeof (struct et_forest));
! forest->nnodes = 0;
! forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
! forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
! return forest;
}
! /* Deallocate the structure. */
! void
! et_forest_delete (et_forest_t forest)
{
! if (forest->nnodes)
! abort ();
! free_alloc_pool (forest->occur_pool);
! free_alloc_pool (forest->node_pool);
! 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 (et_forest_t forest, void *value)
! {
! /* Create node with one occurrence. */
! et_forest_node_t node;
! et_forest_occurrence_t occ;
! node = pool_alloc (forest->node_pool);
! occ = pool_alloc (forest->occur_pool);
! 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 successful.
! 0 indicates that creation of the edge will close the cycle in graph. */
! int
! et_forest_add_edge (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 = pool_alloc (forest->occur_pool);
! 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 (et_forest_t forest, et_forest_node_t node)
{
! remove_all_occurrences (forest, node);
! forest->nnodes--;
! pool_free (forest->node_pool, node);
}
! /* Remove edge from the tree, return 1 if successful,
! 0 indicates nonexisting edge. */
! int
! et_forest_remove_edge (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;
! pool_free (forest->occur_pool, parent_post_occ);
! return 1;
}
! /* Return the parent of the NODE if any, NULL otherwise. */
! et_forest_node_t
! et_forest_parent (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 (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 (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 (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 occurrences having no right successor
! 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;
}
--- 30,743 ----
#include "et-forest.h"
#include "alloc-pool.h"
! /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
! #undef DEBUG_ET
! #ifdef DEBUG_ET
! #include "basic-block.h"
! #endif
!
! /* The occurence of a node in the et tree. */
! struct et_occ
! {
! struct et_node *of; /* The node. */
!
! struct et_occ *parent; /* Parent in the splay-tree. */
! struct et_occ *prev; /* Left son in the splay-tree. */
! struct et_occ *next; /* Right son in the splay-tree. */
!
! int depth; /* The depth of the node is the sum of depth
! fields on the path to the root. */
! int min; /* The minimum value of the depth in the subtree
! is obtained by adding sum of depth fields
! on the path to the root. */
! struct et_occ *min_occ; /* The occurence in the subtree with the minimal
! depth. */
};
! static alloc_pool et_nodes;
! static alloc_pool et_occurences;
! /* Changes depth of OCC to D. */
! static inline void
! set_depth (struct et_occ *occ, int d)
! {
! if (!occ)
! return;
! occ->min += d - occ->depth;
! occ->depth = d;
! }
+ /* Adds D to the depth of OCC. */
! static inline void
! set_depth_add (struct et_occ *occ, int d)
{
! if (!occ)
! return;
+ occ->min += d;
+ occ->depth += d;
+ }
! /* Sets prev field of OCC to P. */
! static inline void
! set_prev (struct et_occ *occ, struct et_occ *t)
{
! #ifdef DEBUG_ET
! if (occ == t)
! abort ();
! #endif
! occ->prev = t;
! if (t)
! t->parent = occ;
}
! /* Sets next field of OCC to P. */
!
! static inline void
! set_next (struct et_occ *occ, struct et_occ *t)
{
! #ifdef DEBUG_ET
! if (occ == t)
! abort ();
! #endif
!
! occ->next = t;
! if (t)
! t->parent = occ;
}
+ /* Recompute minimum for occurence OCC. */
! static inline void
! et_recomp_min (struct et_occ *occ)
{
! struct et_occ *mson = occ->prev;
! if (!mson
! || (occ->next
! && mson->min > occ->next->min))
! mson = occ->next;
! if (mson && mson->min < 0)
! {
! occ->min = mson->min + occ->depth;
! occ->min_occ = mson->min_occ;
! }
! else
! {
! occ->min = occ->depth;
! occ->min_occ = occ;
! }
! }
! #ifdef DEBUG_ET
! /* Checks whether neighbourhood of OCC seems sane. */
! static void
! et_check_occ_sanity (struct et_occ *occ)
! {
! if (!occ)
! return;
! if (occ->parent == occ)
! abort ();
! if (occ->prev == occ)
! abort ();
! if (occ->next == occ)
! abort ();
! if (occ->next && occ->next == occ->prev)
! abort ();
! if (occ->next)
{
! if (occ->next == occ->parent)
! abort ();
! if (occ->next->parent != occ)
! abort ();
}
!
! if (occ->prev)
{
! if (occ->prev == occ->parent)
! abort ();
! if (occ->prev->parent != occ)
! abort ();
}
! if (occ->parent
! && occ->parent->prev != occ
! && occ->parent->next != occ)
! abort ();
}
! /* Checks whether tree rooted at OCC is sane. */
!
static void
! et_check_sanity (struct et_occ *occ)
{
! et_check_occ_sanity (occ);
! if (occ->prev)
! et_check_sanity (occ->prev);
! if (occ->next)
! et_check_sanity (occ->next);
! }
! /* Checks whether tree containing OCC is sane. */
! static void
! et_check_tree_sanity (struct et_occ *occ)
! {
! while (occ->parent)
! occ = occ->parent;
! et_check_sanity (occ);
! }
! /* For recording the paths. */
! static int len;
! static void *datas[100000];
! static int depths[100000];
! /* Records the path represented by OCC, with depth incremented by DEPTH. */
! static int
! record_path_before_1 (struct et_occ *occ, int depth)
! {
! int mn, m;
! depth += occ->depth;
! mn = depth;
! if (occ->prev)
! {
! m = record_path_before_1 (occ->prev, depth);
! if (m < mn)
! mn = m;
}
! fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
! depths[len] = depth;
! datas[len] = occ->of;
! len++;
!
! if (occ->next)
{
! m = record_path_before_1 (occ->next, depth);
! if (m < mn)
! mn = m;
! }
! if (mn != occ->min + depth - occ->depth)
! abort ();
!
! return mn;
! }
! /* Records the path represented by a tree containing OCC. */
! static void
! record_path_before (struct et_occ *occ)
! {
! while (occ->parent)
! occ = occ->parent;
! len = 0;
! record_path_before_1 (occ, 0);
! fprintf (stderr, "\n");
}
! /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
! was not changed since the last recording. */
!
! static int
! check_path_after_1 (struct et_occ *occ, int depth)
{
! int mn, m;
! depth += occ->depth;
! mn = depth;
! if (occ->next)
! {
! m = check_path_after_1 (occ->next, depth);
! if (m < mn)
! mn = m;
}
! len--;
! if (depths[len] != depth
! || datas[len] != occ->of)
! abort ();
!
! if (occ->prev)
! {
! m = check_path_after_1 (occ->prev, depth);
! if (m < mn)
! mn = m;
! }
+ if (mn != occ->min + depth - occ->depth)
+ abort ();
+ return mn;
+ }
+ /* Checks whether the path represented by a tree containing OCC was
+ not changed since the last recording. */
! static void
! check_path_after (struct et_occ *occ)
{
! while (occ->parent)
! occ = occ->parent;
! check_path_after_1 (occ, 0);
! if (len != 0)
! abort ();
}
+ #endif
+ /* Splay the occurence OCC to the root of the tree. */
! static inline void
! et_splay (struct et_occ *occ)
{
! struct et_occ *f, *gf, *ggf;
! int occ_depth, f_depth, gf_depth;
! #ifdef DEBUG_ET
! record_path_before (occ);
! et_check_tree_sanity (occ);
! #endif
!
! while (occ->parent)
! {
! occ_depth = occ->depth;
!
! f = occ->parent;
! f_depth = f->depth;
!
! gf = f->parent;
!
! if (!gf)
! {
! set_depth_add (occ, f_depth);
! occ->min_occ = f->min_occ;
! occ->min = f->min;
!
! if (f->prev == occ)
! {
! /* zig */
! set_prev (f, occ->next);
! set_next (occ, f);
! set_depth_add (f->prev, occ_depth);
! }
! else
! {
! /* zag */
! set_next (f, occ->prev);
! set_prev (occ, f);
! set_depth_add (f->next, occ_depth);
! }
! set_depth (f, -occ_depth);
! occ->parent = NULL;
! et_recomp_min (f);
! #ifdef DEBUG_ET
! et_check_tree_sanity (occ);
! check_path_after (occ);
! #endif
! return;
! }
!
! gf_depth = gf->depth;
!
! set_depth_add (occ, f_depth + gf_depth);
! occ->min_occ = gf->min_occ;
! occ->min = gf->min;
! ggf = gf->parent;
! if (gf->prev == f)
! {
! if (f->prev == occ)
! {
! /* zig zig */
! set_prev (gf, f->next);
! set_prev (f, occ->next);
! set_next (occ, f);
! set_next (f, gf);
!
! set_depth (f, -occ_depth);
! set_depth_add (f->prev, occ_depth);
! set_depth (gf, -f_depth);
! set_depth_add (gf->prev, f_depth);
! }
! else
! {
! /* zag zig */
! set_prev (gf, occ->next);
! set_next (f, occ->prev);
! set_prev (occ, f);
! set_next (occ, gf);
!
! set_depth (f, -occ_depth);
! set_depth_add (f->next, occ_depth);
! set_depth (gf, -occ_depth - f_depth);
! set_depth_add (gf->prev, occ_depth + f_depth);
! }
! }
! else
! {
! if (f->prev == occ)
! {
! /* zig zag */
! set_next (gf, occ->prev);
! set_prev (f, occ->next);
! set_prev (occ, gf);
! set_next (occ, f);
!
! set_depth (f, -occ_depth);
! set_depth_add (f->prev, occ_depth);
! set_depth (gf, -occ_depth - f_depth);
! set_depth_add (gf->next, occ_depth + f_depth);
! }
! else
! {
! /* zag zag */
! set_next (gf, f->prev);
! set_next (f, occ->prev);
! set_prev (occ, f);
! set_prev (f, gf);
!
! set_depth (f, -occ_depth);
! set_depth_add (f->next, occ_depth);
! set_depth (gf, -f_depth);
! set_depth_add (gf->next, f_depth);
! }
! }
!
! occ->parent = ggf;
! if (ggf)
! {
! if (ggf->prev == gf)
! ggf->prev = occ;
! else
! ggf->next = occ;
! }
!
! et_recomp_min (gf);
! et_recomp_min (f);
! #ifdef DEBUG_ET
! et_check_tree_sanity (occ);
! #endif
! }
!
! #ifdef DEBUG_ET
! et_check_sanity (occ);
! check_path_after (occ);
! #endif
}
! /* Create a new et tree occurence of NODE. */
!
! static struct et_occ *
! et_new_occ (struct et_node *node)
{
! struct et_occ *nw;
!
! if (!et_occurences)
! et_occurences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
! nw = pool_alloc (et_occurences);
! nw->of = node;
! nw->parent = NULL;
! nw->prev = NULL;
! nw->next = NULL;
! nw->depth = 0;
! nw->min_occ = nw;
! nw->min = 0;
! return nw;
! }
! /* Create a new et tree containing DATA. */
! struct et_node *
! et_new_tree (void *data)
! {
! struct et_node *nw;
!
! if (!et_nodes)
! et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
! nw = pool_alloc (et_nodes);
! nw->data = data;
! nw->father = NULL;
! nw->left = NULL;
! nw->right = NULL;
! nw->son = NULL;
! nw->rightmost_occ = et_new_occ (nw);
! nw->parent_occ = NULL;
! return nw;
}
! /* Releases et tree T. */
!
void
! et_free_tree (struct et_node *t)
{
! while (t->son)
! et_split (t->son);
! if (t->father)
! et_split (t);
!
! pool_free (et_occurences, t->rightmost_occ);
! pool_free (et_nodes, t);
}
! /* Sets father of et tree T to FATHER. */
!
! void
! et_set_father (struct et_node *t, struct et_node *father)
{
! struct et_node *left, *right;
! struct et_occ *rmost, *left_part, *new_f_occ, *p;
! /* Update the path represented in the splay tree. */
! new_f_occ = et_new_occ (father);
! rmost = father->rightmost_occ;
! et_splay (rmost);
! left_part = rmost->prev;
! p = t->rightmost_occ;
! et_splay (p);
! set_prev (new_f_occ, left_part);
! set_next (new_f_occ, p);
! p->depth++;
! p->min++;
! et_recomp_min (new_f_occ);
! set_prev (rmost, new_f_occ);
! if (new_f_occ->min + rmost->depth < rmost->min)
! {
! rmost->min = new_f_occ->min + rmost->depth;
! rmost->min_occ = new_f_occ->min_occ;
! }
!
! t->parent_occ = new_f_occ;
!
! /* Update the tree. */
! t->father = father;
! right = father->son;
! if (right)
! left = right->left;
! else
! left = right = t;
!
! left->right = t;
! right->left = t;
! t->left = left;
! t->right = right;
! father->son = t;
! #ifdef DEBUG_ET
! et_check_tree_sanity (rmost);
! record_path_before (rmost);
! #endif
}
! /* Splits the edge from T to its father. */
!
! void
! et_split (struct et_node *t)
{
! struct et_node *father = t->father;
! struct et_occ *r, *l, *rmost, *p_occ;
!
! /* Update the path represented by the splay tree. */
! rmost = t->rightmost_occ;
! et_splay (rmost);
!
! for (r = rmost->next; r->prev; r = r->prev)
! continue;
! et_splay (r);
!
! r->prev->parent = NULL;
! p_occ = t->parent_occ;
! et_splay (p_occ);
! t->parent_occ = NULL;
!
! l = p_occ->prev;
! p_occ->next->parent = NULL;
!
! set_prev (r, l);
! et_recomp_min (r);
!
! et_splay (rmost);
! rmost->depth = 0;
! rmost->min = 0;
!
! pool_free (et_occurences, p_occ);
!
! /* Update the tree. */
! if (father->son == t)
! father->son = t->right;
! if (father->son == t)
! father->son = NULL;
else
! {
! t->left->right = t->right;
! t->right->left = t->left;
! }
! t->left = t->right = NULL;
! t->father = NULL;
!
! #ifdef DEBUG_ET
! et_check_tree_sanity (rmost);
! record_path_before (rmost);
!
! et_check_tree_sanity (r);
! record_path_before (r);
! #endif
}
+ /* Finds the nearest common ancestor of the nodes N1 and N2. */
! struct et_node *
! et_nca (struct et_node *n1, struct et_node *n2)
{
! struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
! struct et_occ *l, *r, *ret;
! int mn;
! if (n1 == n2)
! return n1;
! et_splay (o1);
! l = o1->prev;
! r = o1->next;
! if (l)
! l->parent = NULL;
! if (r)
! r->parent = NULL;
! et_splay (o2);
! if (l == o2 || (l && l->parent != NULL))
! {
! ret = o2->next;
! set_prev (o1, o2);
! if (r)
! r->parent = o1;
! }
! else
! {
! ret = o2->prev;
! set_next (o1, o2);
! if (l)
! l->parent = o1;
! }
! if (0 < o2->depth)
{
! om = o1;
! mn = o1->depth;
}
else
{
! om = o2;
! mn = o2->depth + o1->depth;
}
! #ifdef DEBUG_ET
! et_check_tree_sanity (o2);
! #endif
! if (ret && ret->min + o1->depth + o2->depth < mn)
! return ret->min_occ->of;
! else
! return om->of;
}
! /* Checks whether the node UP is an ancestor of the node DOWN. */
! bool
! et_below (struct et_node *down, struct et_node *up)
{
! struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
! struct et_occ *l, *r;
!
! if (up == down)
! return true;
!
! et_splay (u);
! l = u->prev;
! r = u->next;
!
! if (!l)
! return false;
!
! l->parent = NULL;
!
! if (r)
! r->parent = NULL;
! et_splay (d);
!
! if (l == d || l->parent != NULL)
{
! if (r)
! r->parent = u;
! set_prev (u, d);
! #ifdef DEBUG_ET
! et_check_tree_sanity (u);
! #endif
}
! else
! {
! l->parent = u;
!
! /* In case O1 and O2 are in two different trees, we must just restore the
! original state. */
! if (r && r->parent != NULL)
! set_next (u, d);
! else
! set_next (u, r);
!
! #ifdef DEBUG_ET
! et_check_tree_sanity (u);
! #endif
! return false;
! }
!
! if (0 >= d->depth)
! return false;
!
! return !d->next || d->next->min + d->depth >= 0;
}
Index: et-forest.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/et-forest.h,v
retrieving revision 1.1.4.4
diff -c -3 -p -r1.1.4.4 et-forest.h
*** et-forest.h 25 Nov 2003 02:09:43 -0000 1.1.4.4
--- et-forest.h 18 Dec 2003 14:34:51 -0000
*************** Foundation, Inc., 59 Temple Place - Suit
*** 55,80 ****
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 (void);
! extern void et_forest_delete (et_forest_t);
! extern et_forest_node_t et_forest_add_node (et_forest_t, void *);
! extern int et_forest_add_edge (et_forest_t, et_forest_node_t,
! et_forest_node_t);
! extern void et_forest_remove_node (et_forest_t, et_forest_node_t);
! extern int et_forest_remove_edge (et_forest_t, et_forest_node_t,
! et_forest_node_t);
! extern et_forest_node_t et_forest_parent (et_forest_t, et_forest_node_t);
! extern et_forest_node_t et_forest_common_ancestor (et_forest_t,
! et_forest_node_t,
! et_forest_node_t);
! extern void * et_forest_node_value (et_forest_t, et_forest_node_t);
! extern int et_forest_enumerate_sons (et_forest_t, et_forest_node_t,
! et_forest_node_t *);
#ifdef __cplusplus
}
--- 55,82 ----
extern "C" {
#endif /* __cplusplus */
! /* The node representing the node in an et tree. */
! struct et_node
! {
! void *data; /* The data represented by the node. */
! int dfs_num_in, dfs_num_out; /* Number of the node in the dfs ordering. */
! struct et_node *father; /* Father of the node. */
! struct et_node *son; /* The first of the sons of the node. */
! struct et_node *left;
! struct et_node *right; /* The brothers of the node. */
! struct et_occ *rightmost_occ; /* The rightmost occurence. */
! struct et_occ *parent_occ; /* The occurence of the parent node. */
! };
!
! struct et_node *et_new_tree (void *data);
! void et_free_tree (struct et_node *);
! void et_set_father (struct et_node *, struct et_node *);
! void et_split (struct et_node *);
! struct et_node *et_nca (struct et_node *, struct et_node *);
! bool et_below (struct et_node *, struct et_node *);
#ifdef __cplusplus
}
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.205.2.27
diff -c -3 -p -r1.205.2.27 gcse.c
*** gcse.c 25 Nov 2003 02:09:46 -0000 1.205.2.27
--- gcse.c 18 Dec 2003 14:34:51 -0000
*************** static sbitmap *hoist_vbeout;
*** 6146,6154 ****
/* Hoistable expressions. */
static sbitmap *hoist_exprs;
- /* Dominator bitmaps. */
- dominance_info dominators;
-
/* ??? We could compute post dominators and run this algorithm in
reverse to perform tail merging, doing so would probably be
more effective than the tail merging code in jump.c.
--- 6146,6151 ----
*************** free_code_hoist_mem (void)
*** 6185,6191 ****
sbitmap_vector_free (hoist_exprs);
sbitmap_vector_free (transpout);
! free_dominance_info (dominators);
}
/* Compute the very busy expressions at entry/exit from each block.
--- 6182,6188 ----
sbitmap_vector_free (hoist_exprs);
sbitmap_vector_free (transpout);
! free_dominance_info (CDI_DOMINATORS);
}
/* Compute the very busy expressions at entry/exit from each block.
*************** compute_code_hoist_data (void)
*** 6234,6240 ****
compute_local_properties (transp, comp, antloc, &expr_hash_table);
compute_transpout ();
compute_code_hoist_vbeinout ();
! dominators = calculate_dominance_info (CDI_DOMINATORS);
if (gcse_file)
fprintf (gcse_file, "\n");
}
--- 6231,6237 ----
compute_local_properties (transp, comp, antloc, &expr_hash_table);
compute_transpout ();
compute_code_hoist_vbeinout ();
! calculate_dominance_info (CDI_DOMINATORS);
if (gcse_file)
fprintf (gcse_file, "\n");
}
*************** hoist_code (void)
*** 6326,6332 ****
int found = 0;
int insn_inserted_p;
! domby_len = get_dominated_by (dominators, bb, &domby);
/* Examine each expression that is very busy at the exit of this
block. These are the potentially hoistable expressions. */
for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
--- 6323,6329 ----
int found = 0;
int insn_inserted_p;
! domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby);
/* Examine each expression that is very busy at the exit of this
block. These are the potentially hoistable expressions. */
for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ifcvt.c,v
retrieving revision 1.95.2.23
diff -c -3 -p -r1.95.2.23 ifcvt.c
*** ifcvt.c 11 Dec 2003 01:29:50 -0000 1.95.2.23
--- ifcvt.c 18 Dec 2003 14:34:51 -0000
*************** static int cond_exec_changed_p;
*** 84,92 ****
/* True if life data ok at present. */
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 (basic_block);
static rtx first_active_insn (basic_block);
--- 84,89 ----
*************** mark_loop_exit_edges (void)
*** 123,128 ****
--- 120,126 ----
edge e;
flow_loops_find (&loops, LOOP_TREE);
+ free_dominance_info (CDI_DOMINATORS);
if (loops.num > 1)
{
*************** merge_if_block (struct ce_if_block * ce_
*** 2086,2093 ****
{
bb = fallthru;
fallthru = block_fallthru (bb);
! if (post_dominators)
! delete_from_dominance_info (post_dominators, bb);
merge_blocks (combo_bb, bb);
num_true_changes++;
}
--- 2084,2091 ----
{
bb = fallthru;
fallthru = block_fallthru (bb);
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
merge_blocks (combo_bb, bb);
num_true_changes++;
}
*************** merge_if_block (struct ce_if_block * ce_
*** 2103,2110 ****
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 (combo_bb, then_bb);
num_true_changes++;
}
--- 2101,2108 ----
if (combo_bb->global_live_at_end)
COPY_REG_SET (combo_bb->global_live_at_end,
then_bb->global_live_at_end);
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, then_bb);
merge_blocks (combo_bb, then_bb);
num_true_changes++;
}
*************** merge_if_block (struct ce_if_block * ce_
*** 2114,2121 ****
get their addresses taken. */
if (else_bb)
{
! if (post_dominators)
! delete_from_dominance_info (post_dominators, else_bb);
merge_blocks (combo_bb, else_bb);
num_true_changes++;
}
--- 2112,2119 ----
get their addresses taken. */
if (else_bb)
{
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, else_bb);
merge_blocks (combo_bb, else_bb);
num_true_changes++;
}
*************** merge_if_block (struct ce_if_block * ce_
*** 2171,2178 ****
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 (combo_bb, join_bb);
num_true_changes++;
}
--- 2169,2176 ----
COPY_REG_SET (combo_bb->global_live_at_end,
join_bb->global_live_at_end);
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, join_bb);
merge_blocks (combo_bb, join_bb);
num_true_changes++;
}
*************** find_if_header (basic_block test_bb, int
*** 2252,2258 ****
&& find_cond_trap (test_bb, then_edge, else_edge))
goto success;
! if (post_dominators
&& (! HAVE_conditional_execution || reload_completed))
{
if (find_if_case_1 (test_bb, then_edge, else_edge))
--- 2250,2256 ----
&& find_cond_trap (test_bb, then_edge, else_edge))
goto success;
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY
&& (! HAVE_conditional_execution || reload_completed))
{
if (find_if_case_1 (test_bb, then_edge, else_edge))
*************** find_cond_trap (basic_block test_bb, edg
*** 2627,2634 ****
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);
delete_basic_block (trap_bb);
}
--- 2625,2632 ----
remove_edge (trap_bb == then_bb ? then_edge : else_edge);
if (trap_bb->pred == NULL)
{
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, trap_bb);
delete_basic_block (trap_bb);
}
*************** find_if_case_1 (basic_block test_bb, edg
*** 2812,2819 ****
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);
delete_basic_block (then_bb);
/* Make rest of code believe that the newly created block is the THEN_BB
--- 2810,2817 ----
new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
then_bb_index = then_bb->index;
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, then_bb);
delete_basic_block (then_bb);
/* Make rest of code believe that the newly created block is the THEN_BB
*************** find_if_case_1 (basic_block test_bb, edg
*** 2822,2829 ****
{
new_bb->index = then_bb_index;
BASIC_BLOCK (then_bb_index) = new_bb;
! if (post_dominators)
! add_to_dominance_info (post_dominators, new_bb);
}
/* We've possibly created jump to next insn, cleanup_cfg will solve that
later. */
--- 2820,2827 ----
{
new_bb->index = then_bb_index;
BASIC_BLOCK (then_bb_index) = new_bb;
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! add_to_dominance_info (CDI_POST_DOMINATORS, new_bb);
}
/* We've possibly created jump to next insn, cleanup_cfg will solve that
later. */
*************** find_if_case_2 (basic_block test_bb, edg
*** 2865,2871 ****
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
--- 2863,2869 ----
if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
;
else if (else_succ->dest->index < 0
! || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
else_succ->dest))
;
else
*************** find_if_case_2 (basic_block test_bb, edg
*** 2892,2899 ****
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);
delete_basic_block (else_bb);
num_true_changes++;
--- 2890,2897 ----
then_bb->global_live_at_start,
else_bb->global_live_at_end, BITMAP_IOR);
! if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY)
! delete_from_dominance_info (CDI_POST_DOMINATORS, else_bb);
delete_basic_block (else_bb);
num_true_changes++;
*************** if_convert (int x_life_data_ok)
*** 3198,3208 ****
free_basic_block_vars (1);
/* Compute postdominators if we think we'll use them. */
- 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 ();
--- 3196,3204 ----
free_basic_block_vars (1);
/* Compute postdominators if we think we'll use them. */
if (HAVE_conditional_execution || life_data_ok)
! calculate_dominance_info (CDI_POST_DOMINATORS);
!
if (life_data_ok)
clear_bb_flags ();
*************** if_convert (int x_life_data_ok)
*** 3239,3246 ****
fprintf (rtl_dump_file, "\n\n========== no more changes\n");
#endif
! if (post_dominators)
! free_dominance_info (post_dominators);
if (rtl_dump_file)
fflush (rtl_dump_file);
--- 3235,3241 ----
fprintf (rtl_dump_file, "\n\n========== no more changes\n");
#endif
! free_dominance_info (CDI_POST_DOMINATORS);
if (rtl_dump_file)
fflush (rtl_dump_file);
Index: loop-init.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-init.c,v
retrieving revision 1.2.2.6
diff -c -3 -p -r1.2.2.6 loop-init.c
*** loop-init.c 4 Aug 2003 18:44:02 -0000 1.2.2.6
--- loop-init.c 18 Dec 2003 14:34:51 -0000
*************** rtl_loop_optimizer_init (FILE *dumpfile)
*** 53,59 ****
--- 53,61 ----
/* No loops. */
flow_loops_free (loops);
+ free_dominance_info (CDI_DOMINATORS);
free (loops);
+
/* Make chain. */
FOR_EACH_BB (bb)
if (bb->next_bb != EXIT_BLOCK_PTR)
*************** rtl_loop_optimizer_init (FILE *dumpfile)
*** 81,87 ****
flow_loops_dump (loops, dumpfile, NULL, 1);
#ifdef ENABLE_CHECKING
! verify_dominators (loops->cfg.dom);
verify_loop_structure (loops);
#endif
--- 83,89 ----
flow_loops_dump (loops, dumpfile, NULL, 1);
#ifdef ENABLE_CHECKING
! verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
*************** rtl_loop_optimizer_finalize (struct loop
*** 105,110 ****
--- 107,113 ----
/* Clean up. */
flow_loops_free (loops);
+ free_dominance_info (CDI_DOMINATORS);
free (loops);
/* Finalize changes. */
Index: loop-unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unroll.c,v
retrieving revision 1.2.2.5
diff -c -3 -p -r1.2.2.5 loop-unroll.c
*** loop-unroll.c 23 Jul 2003 16:59:50 -0000 1.2.2.5
--- loop-unroll.c 18 Dec 2003 14:34:51 -0000
*************** Software Foundation, 59 Temple Place - S
*** 68,81 ****
static void decide_unrolling_and_peeling (struct loops *, int);
static void peel_loops_completely (struct loops *, int);
! static void decide_peel_simple (struct loops *, struct loop *, int);
! static void decide_peel_once_rolling (struct loops *, struct loop *, int);
! static void decide_peel_completely (struct loops *, struct loop *, int);
! static void decide_unroll_stupid (struct loops *, struct loop *, int);
! static void decide_unroll_constant_iterations (struct loops *,
! struct loop *, int);
! static void decide_unroll_runtime_iterations (struct loops *, struct loop *,
! int);
static void peel_loop_simple (struct loops *, struct loop *);
static void peel_loop_completely (struct loops *, struct loop *);
static void unroll_loop_stupid (struct loops *, struct loop *);
--- 68,79 ----
static void decide_unrolling_and_peeling (struct loops *, int);
static void peel_loops_completely (struct loops *, int);
! static void decide_peel_simple (struct loop *, int);
! static void decide_peel_once_rolling (struct loop *, int);
! static void decide_peel_completely (struct loop *, int);
! static void decide_unroll_stupid (struct loop *, int);
! static void decide_unroll_constant_iterations (struct loop *, int);
! static void decide_unroll_runtime_iterations (struct loop *, int);
static void peel_loop_simple (struct loops *, struct loop *);
static void peel_loop_completely (struct loops *, struct loop *);
static void unroll_loop_stupid (struct loops *, struct loop *);
*************** unroll_and_peel_loops (struct loops *loo
*** 140,146 ****
if (check)
{
#ifdef ENABLE_CHECKING
! verify_dominators (loops->cfg.dom);
verify_loop_structure (loops);
#endif
}
--- 138,144 ----
if (check)
{
#ifdef ENABLE_CHECKING
! verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
*************** peel_loops_completely (struct loops *loo
*** 178,192 ****
loop->ninsns = num_loop_insns (loop);
! decide_peel_once_rolling (loops, loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_peel_completely (loops, loop, flags);
if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
{
peel_loop_completely (loops, loop);
#ifdef ENABLE_CHECKING
! verify_dominators (loops->cfg.dom);
verify_loop_structure (loops);
#endif
}
--- 176,190 ----
loop->ninsns = num_loop_insns (loop);
! decide_peel_once_rolling (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_peel_completely (loop, flags);
if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
{
peel_loop_completely (loops, loop);
#ifdef ENABLE_CHECKING
! verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
*************** decide_unrolling_and_peeling (struct loo
*** 254,266 ****
/* Try transformations one by one in decreasing order of
priority. */
! decide_unroll_constant_iterations (loops, loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_unroll_runtime_iterations (loops, loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_unroll_stupid (loops, loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_peel_simple (loops, loop, flags);
loop = next;
}
--- 252,264 ----
/* Try transformations one by one in decreasing order of
priority. */
! decide_unroll_constant_iterations (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_unroll_runtime_iterations (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_unroll_stupid (loop, flags);
if (loop->lpt_decision.decision == LPT_NONE)
! decide_peel_simple (loop, flags);
loop = next;
}
*************** decide_unrolling_and_peeling (struct loo
*** 269,276 ****
/* Decide whether the LOOP is once rolling and suitable for complete
peeling. */
static void
! decide_peel_once_rolling (struct loops *loops, struct loop *loop,
! int flags ATTRIBUTE_UNUSED)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Considering peeling once rolling loop\n");
--- 267,273 ----
/* Decide whether the LOOP is once rolling and suitable for complete
peeling. */
static void
! decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Considering peeling once rolling loop\n");
*************** decide_peel_once_rolling (struct loops *
*** 284,290 ****
}
/* Check for simple loops. */
! loop->simple = simple_loop_p (loops, loop, &loop->desc);
loop->has_desc = 1;
/* Check number of iterations. */
--- 281,287 ----
}
/* Check for simple loops. */
! loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
/* Check number of iterations. */
*************** decide_peel_once_rolling (struct loops *
*** 303,310 ****
/* Decide whether the LOOP is suitable for complete peeling. */
static void
! decide_peel_completely (struct loops *loops, struct loop *loop,
! int flags ATTRIBUTE_UNUSED)
{
unsigned npeel;
--- 300,306 ----
/* Decide whether the LOOP is suitable for complete peeling. */
static void
! decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
{
unsigned npeel;
*************** decide_peel_completely (struct loops *lo
*** 352,358 ****
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loops, loop, &loop->desc);
loop->has_desc = 1;
}
--- 348,354 ----
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
}
*************** peel_loop_completely (struct loops *loop
*** 441,448 ****
/* Decide whether to unroll LOOP iterating constant number of times and how much. */
static void
! decide_unroll_constant_iterations (struct loops *loops, struct loop *loop,
! int flags)
{
unsigned nunroll, nunroll_by_av, best_copies, best_unroll = -1, n_copies, i;
--- 437,443 ----
/* Decide whether to unroll LOOP iterating constant number of times and how much. */
static void
! decide_unroll_constant_iterations (struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, best_copies, best_unroll = -1, n_copies, i;
*************** decide_unroll_constant_iterations (struc
*** 475,481 ****
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loops, loop, &loop->desc);
loop->has_desc = 1;
}
--- 470,476 ----
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
}
*************** unroll_loop_constant_iterations (struct
*** 649,656 ****
/* Decide whether to unroll LOOP iterating runtime computable number of times
and how much. */
static void
! decide_unroll_runtime_iterations (struct loops *loops, struct loop *loop,
! int flags)
{
unsigned nunroll, nunroll_by_av, i;
--- 644,650 ----
/* Decide whether to unroll LOOP iterating runtime computable number of times
and how much. */
static void
! decide_unroll_runtime_iterations (struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, i;
*************** decide_unroll_runtime_iterations (struct
*** 683,689 ****
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loops, loop, &loop->desc);
loop->has_desc = 1;
}
--- 677,683 ----
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
}
*************** unroll_loop_runtime_iterations (struct l
*** 774,780 ****
unsigned nldom;
basic_block *ldom;
! nldom = get_dominated_by (loops->cfg.dom, body[i], &ldom);
for (j = 0; j < nldom; j++)
if (!flow_bb_inside_loop_p (loop, ldom[j]))
dom_bbs[n_dom_bbs++] = ldom[j];
--- 768,774 ----
unsigned nldom;
basic_block *ldom;
! nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
for (j = 0; j < nldom; j++)
if (!flow_bb_inside_loop_p (loop, ldom[j]))
dom_bbs[n_dom_bbs++] = ldom[j];
*************** unroll_loop_runtime_iterations (struct l
*** 821,827 ****
end_sequence ();
/* Precondition the loop. */
! loop_split_edge_with (loop_preheader_edge (loop), init_code, loops);
remove_edges = xcalloc (max_unroll + n_peel + 1, sizeof (edge));
n_remove_edges = 0;
--- 815,821 ----
end_sequence ();
/* Precondition the loop. */
! loop_split_edge_with (loop_preheader_edge (loop), init_code);
remove_edges = xcalloc (max_unroll + n_peel + 1, sizeof (edge));
n_remove_edges = 0;
*************** unroll_loop_runtime_iterations (struct l
*** 844,850 ****
/* Record the place where switch will be built for preconditioning. */
swtch = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX, loops);
for (i = 0; i < n_peel; i++)
{
--- 838,844 ----
/* Record the place where switch will be built for preconditioning. */
swtch = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX);
for (i = 0; i < n_peel; i++)
{
*************** unroll_loop_runtime_iterations (struct l
*** 862,869 ****
j = n_peel - i - (extra_zero_check ? 0 : 1);
p = REG_BR_PROB_BASE / (i + 2);
! preheader = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX, loops);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), GEN_INT (j), EQ, 0,
--- 856,862 ----
j = n_peel - i - (extra_zero_check ? 0 : 1);
p = REG_BR_PROB_BASE / (i + 2);
! preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), GEN_INT (j), EQ, 0,
*************** unroll_loop_runtime_iterations (struct l
*** 879,886 ****
branch_code = get_insns ();
end_sequence ();
! swtch = loop_split_edge_with (swtch->pred, branch_code, loops);
! set_immediate_dominator (loops->cfg.dom, preheader, swtch);
swtch->succ->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
--- 872,879 ----
branch_code = get_insns ();
end_sequence ();
! swtch = loop_split_edge_with (swtch->pred, branch_code);
! set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
swtch->succ->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
*************** unroll_loop_runtime_iterations (struct l
*** 892,899 ****
/* Add branch for zero iterations. */
p = REG_BR_PROB_BASE / (max_unroll + 1);
swtch = ezc_swtch;
! preheader = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX, loops);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), const0_rtx, EQ, 0,
--- 885,891 ----
/* Add branch for zero iterations. */
p = REG_BR_PROB_BASE / (max_unroll + 1);
swtch = ezc_swtch;
! preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), const0_rtx, EQ, 0,
*************** unroll_loop_runtime_iterations (struct l
*** 909,916 ****
branch_code = get_insns ();
end_sequence ();
! swtch = loop_split_edge_with (swtch->succ, branch_code, loops);
! set_immediate_dominator (loops->cfg.dom, preheader, swtch);
swtch->succ->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
--- 901,908 ----
branch_code = get_insns ();
end_sequence ();
! swtch = loop_split_edge_with (swtch->succ, branch_code);
! set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
swtch->succ->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
swtch->succ->flags & EDGE_IRREDUCIBLE_LOOP);
*************** unroll_loop_runtime_iterations (struct l
*** 918,924 ****
}
/* Recount dominators for outer blocks. */
! iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
/* And unroll loop. */
--- 910,916 ----
}
/* Recount dominators for outer blocks. */
! iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
/* And unroll loop. */
*************** unroll_loop_runtime_iterations (struct l
*** 946,952 ****
/* Decide whether to simply peel LOOP and how much. */
static void
! decide_peel_simple (struct loops *loops, struct loop *loop, int flags)
{
unsigned npeel;
--- 938,944 ----
/* Decide whether to simply peel LOOP and how much. */
static void
! decide_peel_simple (struct loop *loop, int flags)
{
unsigned npeel;
*************** decide_peel_simple (struct loops *loops,
*** 975,981 ****
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loops, loop, &loop->desc);
loop->has_desc = 1;
}
--- 967,973 ----
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
}
*************** peel_loop_simple (struct loops *loops, s
*** 1062,1068 ****
/* Decide whether to unroll LOOP stupidly and how much. */
static void
! decide_unroll_stupid (struct loops *loops, struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, i;
--- 1054,1060 ----
/* Decide whether to unroll LOOP stupidly and how much. */
static void
! decide_unroll_stupid (struct loop *loop, int flags)
{
unsigned nunroll, nunroll_by_av, i;
*************** decide_unroll_stupid (struct loops *loop
*** 1095,1101 ****
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loops, loop, &loop->desc);
loop->has_desc = 1;
}
--- 1087,1093 ----
/* Check for simple loops. */
if (!loop->has_desc)
{
! loop->simple = simple_loop_p (loop, &loop->desc);
loop->has_desc = 1;
}
Index: loop-unswitch.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unswitch.c,v
retrieving revision 1.2.2.5
diff -c -3 -p -r1.2.2.5 loop-unswitch.c
*** loop-unswitch.c 28 Sep 2003 06:06:29 -0000 1.2.2.5
--- loop-unswitch.c 18 Dec 2003 14:34:51 -0000
*************** Software Foundation, 59 Temple Place - S
*** 81,87 ****
static struct loop *unswitch_loop (struct loops *, struct loop *,
basic_block);
static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
! static bool may_unswitch_on_p (struct loops *, basic_block, struct loop *,
basic_block *);
static rtx reversed_condition (rtx);
--- 81,87 ----
static struct loop *unswitch_loop (struct loops *, struct loop *,
basic_block);
static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
! static bool may_unswitch_on_p (basic_block, struct loop *,
basic_block *);
static rtx reversed_condition (rtx);
*************** unswitch_loops (struct loops *loops)
*** 107,113 ****
unswitch_single_loop (loops, loop, NULL_RTX, 0);
#ifdef ENABLE_CHECKING
! verify_dominators (loops->cfg.dom);
verify_loop_structure (loops);
#endif
}
--- 107,113 ----
unswitch_single_loop (loops, loop, NULL_RTX, 0);
#ifdef ENABLE_CHECKING
! verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
*************** unswitch_loops (struct loops *loops)
*** 117,124 ****
basic blocks (for what it means see comments below). List of basic blocks
inside LOOP is provided in BODY to save time. */
static bool
! may_unswitch_on_p (struct loops *loops, basic_block bb, struct loop *loop,
! basic_block *body)
{
rtx test;
unsigned i;
--- 117,123 ----
basic blocks (for what it means see comments below). List of basic blocks
inside LOOP is provided in BODY to save time. */
static bool
! may_unswitch_on_p (basic_block bb, struct loop *loop, basic_block *body)
{
rtx test;
unsigned i;
*************** may_unswitch_on_p (struct loops *loops,
*** 136,142 ****
/* It must be executed just once each iteration (because otherwise we
are unable to update dominator/irreducible loop information correctly). */
! if (!just_once_each_iteration_p (loops, loop, bb))
return false;
/* Condition must be invariant. We use just a stupid test of invariantness
--- 135,141 ----
/* It must be executed just once each iteration (because otherwise we
are unable to update dominator/irreducible loop information correctly). */
! if (!just_once_each_iteration_p (loop, bb))
return false;
/* Condition must be invariant. We use just a stupid test of invariantness
*************** unswitch_single_loop (struct loops *loop
*** 239,245 ****
/* Find a bb to unswitch on. */
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
! if (may_unswitch_on_p (loops, bbs[i], loop, bbs))
break;
if (i == loop->num_nodes)
--- 238,244 ----
/* Find a bb to unswitch on. */
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
! if (may_unswitch_on_p (bbs[i], loop, bbs))
break;
if (i == loop->num_nodes)
*************** unswitch_single_loop (struct loops *loop
*** 295,301 ****
rconds = cond_checked;
/* Separate condition in a single basic block. */
! bb = split_loop_bb (loops, bbs[i], PREV_INSN (split_before))->dest;
free (bbs);
true_first = !(bb->succ->flags & EDGE_FALLTHRU);
if (rtl_dump_file)
--- 294,300 ----
rconds = cond_checked;
/* Separate condition in a single basic block. */
! bb = split_loop_bb (bbs[i], PREV_INSN (split_before))->dest;
free (bbs);
true_first = !(bb->succ->flags & EDGE_FALLTHRU);
if (rtl_dump_file)
*************** unswitch_loop (struct loops *loops, stru
*** 335,341 ****
if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
unswitch_on->succ->succ_next->succ_next)
abort ();
! if (!just_once_each_iteration_p (loops, loop, unswitch_on))
abort ();
if (loop->inner)
abort ();
--- 334,340 ----
if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
unswitch_on->succ->succ_next->succ_next)
abort ();
! if (!just_once_each_iteration_p (loop, unswitch_on))
abort ();
if (loop->inner)
abort ();
*************** unswitch_loop (struct loops *loops, stru
*** 382,388 ****
switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
! add_to_dominance_info (loops->cfg.dom, switch_bb);
unswitch_on->rbi->copy = unswitch_on_alt;
/* Loopify from the copy of LOOP body, constructing the new loop. */
--- 381,387 ----
switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
! add_to_dominance_info (CDI_DOMINATORS, switch_bb);
unswitch_on->rbi->copy = unswitch_on_alt;
/* Loopify from the copy of LOOP body, constructing the new loop. */
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.71.2.13
diff -c -3 -p -r1.71.2.13 predict.c
*** predict.c 28 Sep 2003 06:06:32 -0000 1.71.2.13
--- predict.c 18 Dec 2003 14:34:51 -0000
*************** static void estimate_loops_at_level (str
*** 72,81 ****
static void propagate_freq (struct loop *);
static void estimate_bb_frequencies (struct loops *);
static void counts_to_freqs (void);
! static void process_note_predictions (basic_block, int *, dominance_info,
! dominance_info);
! static void process_note_prediction (basic_block, int *, dominance_info,
! dominance_info, int, int);
static bool last_basic_block_p (basic_block);
static void compute_function_frequency (void);
static void choose_function_section (void);
--- 72,79 ----
static void propagate_freq (struct loop *);
static void estimate_bb_frequencies (struct loops *);
static void counts_to_freqs (void);
! static void process_note_predictions (basic_block, int *);
! static void process_note_prediction (basic_block, int *, int, int);
static bool last_basic_block_p (basic_block);
static void compute_function_frequency (void);
static void choose_function_section (void);
*************** combine_predictions_for_insn (rtx insn,
*** 393,405 ****
void
estimate_probability (struct loops *loops_info)
{
- dominance_info dominators, post_dominators;
basic_block bb;
unsigned 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. */
--- 391,402 ----
void
estimate_probability (struct loops *loops_info)
{
basic_block bb;
unsigned i;
connect_infinite_loops_to_exit ();
! calculate_dominance_info (CDI_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 (struct loops *loop
*** 412,422 ****
struct loop_desc desc;
unsigned HOST_WIDE_INT niter;
! flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
! if (simple_loop_p (loops_info, loop, &desc)
! && desc.const_iter)
{
int prob;
niter = desc.niter + 1;
--- 409,418 ----
struct loop_desc desc;
unsigned HOST_WIDE_INT niter;
! flow_loop_scan (loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
! if (simple_loop_p (loop, &desc) && desc.const_iter)
{
int prob;
niter = desc.niter + 1;
*************** estimate_probability (struct loops *loop
*** 500,507 ****
/* 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;
--- 496,503 ----
/* 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 (CDI_DOMINATORS, e->dest, e->src)
! && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
{
rtx insn;
*************** estimate_probability (struct loops *loop
*** 618,625 ****
&& 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);
--- 614,620 ----
&& bb->succ->succ_next != NULL)
combine_predictions_for_insn (bb->end, bb);
! free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_edges ();
estimate_bb_frequencies (loops_info);
*************** last_basic_block_p (basic_block bb)
*** 719,728 ****
on demand, so -1 may be there in case this was not needed yet). */
static void
! process_note_prediction (basic_block bb, int *heads,
! dominance_info dominators,
! dominance_info post_dominators, int pred,
! int flags)
{
edge e;
int y;
--- 714,720 ----
on demand, so -1 may be there in case this was not needed yet). */
static void
! process_note_prediction (basic_block bb, int *heads, int pred, int flags)
{
edge e;
int y;
*************** process_note_prediction (basic_block bb,
*** 736,753 ****
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];
--- 728,745 ----
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 (CDI_DOMINATORS, bb);
int head;
while (heads[next_ai->index] < 0)
{
! if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
break;
heads[next_ai->index] = ai->index;
ai = next_ai;
! next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
}
! if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
head = next_ai->index;
else
head = heads[next_ai->index];
*************** process_note_prediction (basic_block bb,
*** 769,775 ****
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);
}
--- 761,767 ----
return;
for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
if (e->dest->index >= 0
! && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
predict_edge_def (e, pred, taken);
}
*************** process_note_prediction (basic_block bb,
*** 778,786 ****
process_note_prediction. */
static void
! process_note_predictions (basic_block bb, int *heads,
! dominance_info dominators,
! dominance_info post_dominators)
{
rtx insn;
edge e;
--- 770,776 ----
process_note_prediction. */
static void
! process_note_predictions (basic_block bb, int *heads)
{
rtx insn;
edge e;
*************** process_note_predictions (basic_block bb
*** 813,820 ****
/* Process single prediction note. */
process_note_prediction (bb,
heads,
- dominators,
- post_dominators,
alg, (int) NOTE_PREDICTION_FLAGS (insn));
delete_insn (insn);
}
--- 803,808 ----
*************** process_note_predictions (basic_block bb
*** 827,836 ****
/* This block ended from other reasons than because of return.
If it is because of noreturn call, this should certainly not
be taken. Otherwise it is probably some error recovery. */
! process_note_prediction (bb,
! heads,
! dominators,
! post_dominators, PRED_NORETURN, NOT_TAKEN);
}
}
--- 815,821 ----
/* This block ended from other reasons than because of return.
If it is because of noreturn call, this should certainly not
be taken. Otherwise it is probably some error recovery. */
! process_note_prediction (bb, heads, PRED_NORETURN, NOT_TAKEN);
}
}
*************** void
*** 841,855 ****
note_prediction_to_br_prob (void)
{
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);
--- 826,839 ----
note_prediction_to_br_prob (void)
{
basic_block bb;
int *heads;
/* To enable handling of noreturn blocks. */
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
! calculate_dominance_info (CDI_POST_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 (void)
*** 858,867 ****
/* Process all prediction notes. */
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 ();
--- 842,851 ----
/* Process all prediction notes. */
FOR_EACH_BB (bb)
! process_note_predictions (bb, heads);
! free_dominance_info (CDI_POST_DOMINATORS);
! free_dominance_info (CDI_DOMINATORS);
free (heads);
remove_fake_edges ();
Index: sched-rgn.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sched-rgn.c,v
retrieving revision 1.46.2.14
diff -c -3 -p -r1.46.2.14 sched-rgn.c
*** sched-rgn.c 25 Nov 2003 02:09:52 -0000 1.46.2.14
--- sched-rgn.c 18 Dec 2003 14:34:51 -0000
*************** static int *containing_rgn;
*** 155,161 ****
void debug_regions (void);
static void find_single_block_region (void);
! static void find_rgns (struct edge_list *, dominance_info);
static int too_large (int, int *, int *);
extern void debug_live (int, int);
--- 155,161 ----
void debug_regions (void);
static void find_single_block_region (void);
! static void find_rgns (struct edge_list *);
static int too_large (int, int *, int *);
extern void debug_live (int, int);
*************** too_large (int block, int *num_bbs, int
*** 613,619 ****
of edge tables. That would simplify it somewhat. */
static void
! find_rgns (struct edge_list *edge_list, dominance_info dom)
{
int *max_hdr, *dfs_nr, *stack, *degree;
char no_loops = 1;
--- 613,619 ----
of edge tables. That would simplify it somewhat. */
static void
! find_rgns (struct edge_list *edge_list)
{
int *max_hdr, *dfs_nr, *stack, *degree;
char no_loops = 1;
*************** find_rgns (struct edge_list *edge_list,
*** 827,833 ****
{
/* Now verify that the block is dominated by the loop
header. */
! if (!dominated_by_p (dom, jbb, bb))
break;
}
}
--- 827,833 ----
{
/* Now verify that the block is dominated by the loop
header. */
! if (!dominated_by_p (CDI_DOMINATORS, jbb, bb))
break;
}
}
*************** init_regions (void)
*** 2597,2603 ****
}
else
{
- dominance_info dom;
struct edge_list *edge_list;
/* The scheduler runs after estimate_probabilities; therefore, we
--- 2597,2602 ----
*************** init_regions (void)
*** 2607,2613 ****
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
--- 2606,2612 ----
edge_list = create_edge_list ();
/* Compute the dominators and post dominators. */
! 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 (void)
*** 2615,2621 ****
if (build_control_flow (edge_list) != 0)
find_single_block_region ();
else
! find_rgns (edge_list, dom);
if (sched_verbose >= 3)
debug_regions ();
--- 2614,2620 ----
if (build_control_flow (edge_list) != 0)
find_single_block_region ();
else
! find_rgns (edge_list);
if (sched_verbose >= 3)
debug_regions ();
*************** init_regions (void)
*** 2625,2631 ****
/* 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);
}
}
--- 2624,2630 ----
/* For now. This will move as more and more of haifa is converted
to using the cfg code in flow.c. */
! free_dominance_info (CDI_DOMINATORS);
}
}
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.83
diff -c -3 -p -r1.654.2.83 toplev.c
*** toplev.c 17 Dec 2003 19:53:01 -0000 1.654.2.83
--- toplev.c 18 Dec 2003 14:34:51 -0000
*************** rest_of_handle_branch_prob (tree decl, r
*** 2529,2534 ****
--- 2529,2535 ----
estimate_probability (&loops);
flow_loops_free (&loops);
+ free_dominance_info (CDI_DOMINATORS);
close_dump_file (DFI_bp, print_rtl_with_bb, insns);
timevar_pop (TV_BRANCH_PROB);
}
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.238
diff -c -3 -p -r1.1.4.238 tree-cfg.c
*** tree-cfg.c 17 Dec 2003 23:19:03 -0000 1.1.4.238
--- tree-cfg.c 18 Dec 2003 14:34:51 -0000
*************** struct cfg_stats_d
*** 65,72 ****
long num_merged_labels;
};
- static dominance_info pdom_info = NULL;
-
static struct cfg_stats_d cfg_stats;
/* Nonzero if we found a computed goto while building basic blocks. */
--- 65,70 ----
*************** create_bb (tree stmt_list, basic_block a
*** 388,393 ****
--- 386,394 ----
n_basic_blocks++;
last_basic_block++;
+ if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
+ add_to_dominance_info (CDI_DOMINATORS, bb);
+
return bb;
}
*************** make_goto_expr_edges (basic_block bb)
*** 707,717 ****
void
cleanup_tree_cfg (void)
{
- int orig_n_basic_blocks = n_basic_blocks;
bool something_changed = true;
timevar_push (TV_TREE_CLEANUP_CFG);
- pdom_info = NULL;
/* These three transformations can cascade, so we iterate on them until nothing
changes. */
--- 708,716 ----
*************** cleanup_tree_cfg (void)
*** 722,744 ****
something_changed |= remove_unreachable_blocks ();
}
- if (pdom_info != NULL)
- {
- free_dominance_info (pdom_info);
- pdom_info = NULL;
- }
compact_blocks ();
- /* If we expunged any basic blocks, then the dominator tree is
- no longer valid. */
- if (n_basic_blocks != orig_n_basic_blocks)
- {
- basic_block bb;
-
- FOR_ALL_BB (bb)
- clear_dom_children (bb);
- }
-
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
--- 721,728 ----
*************** remove_bb (basic_block bb)
*** 1449,1459 ****
remove_phi_nodes_and_edges_for_unreachable_block (bb);
- /* If we have pdom information, then we must also make sure to
- clean up the dominance information. */
- if (pdom_info)
- delete_from_dominance_info (pdom_info, bb);
-
/* Remove the basic block from the array. */
expunge_block (bb);
}
--- 1433,1438 ----
*************** cleanup_control_expr_graph (basic_block
*** 1596,1601 ****
--- 1575,1584 ----
bsi_remove (&bsi);
taken_edge->flags = EDGE_FALLTHRU;
+ /* We removed some paths from the cfg. */
+ if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
+ dom_computed[CDI_DOMINATORS] = DOM_CONS_OK;
+
return retval;
}
*************** phi_alternatives_equal (basic_block dest
*** 1766,1848 ****
*/
static void
! compute_dominance_frontiers_1 (bitmap *frontiers, dominance_info idom,
! int bb, sbitmap done)
{
- basic_block b = BASIC_BLOCK (bb);
edge e;
basic_block c;
- unsigned int i;
- bitmap dominated;
-
- /* Ugh. This could be called via the tree SSA code or via the
- RTL SSA code. The former has bb annotations, the latter does
- not. */
- if (bb_ann (b))
- dominated = dom_children (b);
- else
- {
- basic_block *dominated_array;
- unsigned int n_dominated;
-
- /* Build a sparse bitmap. This can be expensive as
- get_domianted_by allocates an array large enough to
- hold every basic block. We should probably either
- make the RTL SSA code use bb annotations or rip it
- out. */
- dominated = BITMAP_XMALLOC ();
- n_dominated = get_dominated_by (idom, b, &dominated_array);
-
- for (i = 0; i < n_dominated; i++)
- bitmap_set_bit (dominated, dominated_array[i]->index);
-
- free (dominated_array);
- }
! SET_BIT (done, bb);
/* 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. */
! if (dominated)
! EXECUTE_IF_SET_IN_BITMAP (dominated, 0, i,
! {
! c = BASIC_BLOCK (i);
! if (! TEST_BIT (done, c->index))
! compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
! });
/* Find blocks conforming to rule (1) above. */
! for (e = b->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
! if (get_immediate_dominator (idom, e->dest)->index != bb)
! bitmap_set_bit (frontiers[bb], e->dest->index);
}
/* Find blocks conforming to rule (2). */
! if (dominated)
! EXECUTE_IF_SET_IN_BITMAP (dominated, 0, i,
! {
! int x;
! c = BASIC_BLOCK (i);
!
! EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x,
! {
! if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb)
! bitmap_set_bit (frontiers[bb], x);
! });
! });
! /* If we built the dominated bitmap rather than using the
! one in the bb's annotation, then make sure we free it. */
! if (! bb_ann (b))
! BITMAP_XFREE (dominated);
}
void
! compute_dominance_frontiers (bitmap *frontiers, dominance_info idom)
{
sbitmap done = sbitmap_alloc (last_basic_block);
--- 1749,1798 ----
*/
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);
*************** compute_dominance_frontiers (bitmap *fro
*** 1850,1858 ****
sbitmap_zero (done);
! compute_dominance_frontiers_1 (frontiers, idom,
! ENTRY_BLOCK_PTR->succ->dest->index,
! done);
sbitmap_free (done);
--- 1800,1806 ----
sbitmap_zero (done);
! compute_dominance_frontiers_1 (frontiers, ENTRY_BLOCK_PTR->succ->dest, done);
sbitmap_free (done);
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 2688,2694 ****
basic_block
tree_split_edge (edge edge_in)
{
! basic_block new_bb, after_bb, dest;
edge new_edge, e;
tree phi;
int i, num_elem;
--- 2636,2642 ----
basic_block
tree_split_edge (edge edge_in)
{
! basic_block new_bb, after_bb, dest, src;
edge new_edge, e;
tree phi;
int i, num_elem;
*************** tree_split_edge (edge edge_in)
*** 2697,2702 ****
--- 2645,2651 ----
if (edge_in->flags & EDGE_ABNORMAL)
abort ();
+ src = edge_in->src;
dest = edge_in->dest;
/* Place the new block in the block list. Try to keep the new block
*************** tree_split_edge (edge edge_in)
*** 2731,2736 ****
--- 2680,2692 ----
}
}
+ if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
+ set_immediate_dominator (CDI_DOMINATORS, new_bb, src);
+
+ if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
+ set_immediate_dominator (CDI_DOMINATORS, dest,
+ recount_dominator (CDI_DOMINATORS, dest));
+
return new_bb;
}
*************** tree_verify_flow_info (void)
*** 3168,3173 ****
--- 3124,3132 ----
}
}
+ if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
+ verify_dominators (CDI_DOMINATORS);
+
return err;
}
*************** tree_make_forwarder_block (basic_block b
*** 3187,3192 ****
--- 3146,3153 ----
bool first;
block_stmt_iterator bsi, bsi_tgt;
+ free_dominance_info (CDI_DOMINATORS);
+
dummy = create_bb (NULL, bb->prev_bb);
create_block_annotation (dummy);
dummy->count = bb->count;
*************** tree_loop_optimizer_init (FILE *dumpfile
*** 3320,3326 ****
flow_loops_dump (loops, dumpfile, NULL, 1);
#ifdef ENABLE_CHECKING
! verify_dominators (loops->cfg.dom);
verify_loop_structure (loops);
#endif
--- 3281,3287 ----
flow_loops_dump (loops, dumpfile, NULL, 1);
#ifdef ENABLE_CHECKING
! verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
*************** thread_jumps (void)
*** 3507,3512 ****
--- 3468,3477 ----
/* Perform the redirection. */
retval = true;
e = tree_redirect_edge_and_branch (e, dest);
+
+ /* TODO -- updating dominators in this case is simple. */
+ free_dominance_info (CDI_DOMINATORS);
+
if (!old)
{
/* Update phi nodes. We know that the new argument should
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.63
diff -c -3 -p -r1.1.2.63 tree-flow-inline.h
*** tree-flow-inline.h 16 Dec 2003 21:42:31 -0000 1.1.2.63
--- tree-flow-inline.h 18 Dec 2003 14:34:51 -0000
*************** phi_element_for_edge (tree phi, edge e)
*** 378,417 ****
return (struct phi_arg_d *)NULL;
}
- static inline void
- add_dom_child (basic_block bb, basic_block child_bb)
- {
- bb_ann_t ann = bb_ann (bb);
- if (ann->dom_children == NULL)
- ann->dom_children = BITMAP_GGC_ALLOC ();
- bitmap_set_bit (ann->dom_children, child_bb->index);
- }
-
- static inline void
- remove_dom_child (basic_block bb, basic_block child_bb)
- {
- bb_ann_t ann = bb_ann (bb);
-
- #if defined ENABLE_CHECKING
- if (ann->dom_children == NULL)
- abort ();
- #endif
-
- bitmap_clear_bit (ann->dom_children, child_bb->index);
- }
-
- static inline void
- clear_dom_children (basic_block bb)
- {
- bb_ann (bb)->dom_children = NULL;
- }
-
- static inline bitmap
- dom_children (basic_block bb)
- {
- return bb_ann (bb)->dom_children;
- }
-
/* ----------------------------------------------------------------------- */
static inline bool
--- 378,383 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.173
diff -c -3 -p -r1.1.4.173 tree-flow.h
*** tree-flow.h 17 Dec 2003 19:53:01 -0000 1.1.4.173
--- tree-flow.h 18 Dec 2003 14:34:51 -0000
*************** struct bb_ann_d GTY(())
*** 294,302 ****
SSA rewriting. It is not maintained after conversion into SSA form. */
int num_preds;
- /* Set of blocks immediately dominated by this node. */
- bitmap dom_children;
-
/* Nonzero if this block is forwardable during cfg cleanups. This is also
used to detect loops during cfg cleanups. */
unsigned forwardable: 1;
--- 294,299 ----
*************** typedef struct bb_ann_d *bb_ann_t;
*** 308,315 ****
static inline bb_ann_t bb_ann (basic_block);
static inline tree phi_nodes (basic_block);
static inline void set_phi_nodes (basic_block, tree);
- static inline void add_dom_child (basic_block, basic_block);
- static inline bitmap dom_children (basic_block);
/*---------------------------------------------------------------------------
Global declarations
--- 305,310 ----
*************** extern void bsi_commit_edge_inserts (boo
*** 425,431 ****
extern void bsi_insert_on_edge_immediate (edge, tree);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
! extern void compute_dominance_frontiers (bitmap *, dominance_info);
extern bool verify_stmt (tree);
extern void verify_stmts (void);
--- 420,426 ----
extern void bsi_insert_on_edge_immediate (edge, tree);
extern void notice_special_calls (tree);
extern void clear_special_calls (void);
! extern void compute_dominance_frontiers (bitmap *);
extern bool verify_stmt (tree);
extern void verify_stmts (void);
*************** extern edge ssa_redirect_edge (edge, bas
*** 497,503 ****
extern void set_is_used (tree);
extern bool tree_ssa_useless_type_conversion (tree);
extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
- extern void build_dominator_tree (dominance_info);
extern void verify_ssa (void);
extern void delete_tree_ssa (void);
extern unsigned int highest_ssa_version;
--- 492,497 ----
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.96
diff -c -3 -p -r1.1.4.96 tree-optimize.c
*** tree-optimize.c 17 Dec 2003 19:53:02 -0000 1.1.4.96
--- tree-optimize.c 18 Dec 2003 14:34:51 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 257,262 ****
--- 257,264 ----
/* Flush out flow graph and SSA data. */
BITMAP_XFREE (vars_to_rename);
+
+ free_dominance_info (CDI_DOMINATORS);
}
tree_ssa_finish (chain);
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.99
diff -c -3 -p -r1.1.2.99 tree-ssa-dom.c
*** tree-ssa-dom.c 17 Dec 2003 23:19:04 -0000 1.1.2.99
--- tree-ssa-dom.c 18 Dec 2003 14:34:52 -0000
*************** tree_ssa_dominator_optimize (tree fndecl
*** 335,360 ****
FOR_EACH_BB (bb)
bb_ann (bb)->forwardable = 1;
! /* Build the dominator tree if necessary.
!
! We don't have a flag indicating if the dominator tree is available,
! but we can make a very accurate approximation by checking to see if
! the successors of the entry block have any dominator children. If
! they do not, then we assume that the dominator tree is not available. */
! for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
! if (dom_children (e->dest))
! break;
!
! /* If we did not find any dominator children in the successors of the
! entry block, then rebuild the dominator tree. */
! if (e == NULL)
! {
! dominance_info idom;
!
! idom = calculate_dominance_info (CDI_DOMINATORS);
! build_dominator_tree (idom);
! free_dominance_info (idom);
! }
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
--- 335,341 ----
FOR_EACH_BB (bb)
bb_ann (bb)->forwardable = 1;
! calculate_dominance_info (CDI_DOMINATORS);
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
*************** tree_ssa_dominator_optimize (tree fndecl
*** 435,440 ****
--- 416,424 ----
src = e->src;
e = redirect_edge_and_branch (e, tgt);
+
+ /* Updating the dominance information would be nontrivial. */
+ free_dominance_info (CDI_DOMINATORS);
if ((dump_file && (dump_flags & TDF_DETAILS))
&& e->src != src)
*************** tree_ssa_dominator_optimize (tree fndecl
*** 454,464 ****
the dominator tree is strictly necessary. */
if (cfg_altered)
{
- dominance_info idom;
cleanup_tree_cfg ();
! idom = calculate_dominance_info (CDI_DOMINATORS);
! build_dominator_tree (idom);
! free_dominance_info (idom);
}
for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
--- 438,445 ----
the dominator tree is strictly necessary. */
if (cfg_altered)
{
cleanup_tree_cfg ();
! calculate_dominance_info (CDI_DOMINATORS);
}
for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
*************** dom_opt_finalize_block (struct dom_walk_
*** 691,698 ****
if (bb->succ
&& ! bb->succ->succ_next
&& (bb->succ->flags & EDGE_ABNORMAL) == 0
! && (! dom_children (bb)
! || ! bitmap_bit_p (dom_children (bb), bb->succ->dest->index)))
{
thread_across_edge (bb->succ);
}
--- 672,678 ----
if (bb->succ
&& ! bb->succ->succ_next
&& (bb->succ->flags & EDGE_ABNORMAL) == 0
! && get_immediate_dominator (CDI_DOMINATORS, bb->succ->dest) != bb)
{
thread_across_edge (bb->succ);
}
*************** dom_opt_finalize_block (struct dom_walk_
*** 725,732 ****
/* If the THEN arm is the end of a dominator tree, then try to thread
through its edge. */
! if (! dom_children (bb)
! || ! bitmap_bit_p (dom_children (bb), true_edge->dest->index))
{
unsigned true_limit;
unsigned false_limit;
--- 705,711 ----
/* If the THEN arm is the end of a dominator tree, then try to thread
through its edge. */
! if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb)
{
unsigned true_limit;
unsigned false_limit;
*************** dom_opt_finalize_block (struct dom_walk_
*** 752,759 ****
}
/* Similarly for the ELSE arm. */
! if (! dom_children (bb)
! || ! bitmap_bit_p (dom_children (bb), false_edge->dest->index))
{
unsigned true_limit;
unsigned false_limit;
--- 731,737 ----
}
/* Similarly for the ELSE arm. */
! if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb)
{
unsigned true_limit;
unsigned false_limit;
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-pre.c,v
retrieving revision 1.1.4.117
diff -c -3 -p -r1.1.4.117 tree-ssa-pre.c
*** tree-ssa-pre.c 16 Dec 2003 21:42:31 -0000 1.1.4.117
--- tree-ssa-pre.c 18 Dec 2003 14:34:52 -0000
*************** static bool split_critical_edges (void);
*** 245,262 ****
static void collect_expressions (basic_block, varray_type *);
static int build_dfn_array (basic_block, int);
static int eref_compare (const void *, const void *);
- static inline bool fast_a_dominates_b (basic_block, basic_block);
- static void build_dfs_id_array_1 (basic_block, int *);
- static void build_dfs_id_array (void);
/* Bitmap of E-PHI predecessor operands have already been created.
We only create one phi-pred per block. */
static bitmap created_phi_preds;
- /* PRE dominance info. */
- static dominance_info pre_idom;
-
/* PRE dominance frontiers. */
static bitmap *pre_dfs;
--- 245,256 ----
*************** ephi_at_block (basic_block bb)
*** 867,909 ****
return NULL_TREE;
}
- static int *dfs_id;
- static int *dfs_id_last;
-
- /* Depth first ID calculation.
- In order to not have to deal with the et-forest, which can be slow,
- we calculate two arrays that can quickly tell us whether one block
- dominates another. One array tracks the dfs_id of each block.
- The other array tracks the last dfs_id of the dominator children of
- the block. */
-
- static void
- build_dfs_id_array_1 (basic_block bb, int *id)
- {
- int i;
- if (bb->index >= 0)
- dfs_id[bb->index] = *id;
-
- ++(*id);
- if (dom_children (bb))
- EXECUTE_IF_SET_IN_BITMAP(dom_children (bb), 0, i,
- {
- build_dfs_id_array_1 (BASIC_BLOCK (i), id);
- });
- if (bb->index >= 0)
- dfs_id_last[bb->index] = *id - 1;
-
- }
- static void
- build_dfs_id_array (void)
- {
- int id = 0;
- dfs_id = xcalloc (last_basic_block + 1, sizeof (int));
- dfs_id_last = xcalloc (last_basic_block + 1, sizeof (int));
- build_dfs_id_array_1 (ENTRY_BLOCK_PTR, &id);
- }
-
-
static int *dfn;
/* Build a depth first numbering array to be used in sorting in
--- 861,866 ----
*************** static int *dfn;
*** 912,925 ****
static int
build_dfn_array (basic_block bb, int num)
{
! int i;
if (bb->index >= 0)
dfn[bb->index] = num;
! if (dom_children (bb))
! EXECUTE_IF_SET_IN_BITMAP (dom_children (bb), 0, i,
! {
! num = build_dfn_array (BASIC_BLOCK (i), ++num);
! });
return num;
}
--- 869,883 ----
static int
build_dfn_array (basic_block bb, int num)
{
! basic_block son;
!
if (bb->index >= 0)
dfn[bb->index] = num;
!
! for (son = first_dom_son (CDI_DOMINATORS, bb);
! son;
! son = next_dom_son (CDI_DOMINATORS, son))
! num = build_dfn_array (son, ++num);
return num;
}
*************** eref_compare (const void *elem1, const v
*** 964,970 ****
{
if (dfn[bb1->index] == dfn[bb2->index])
{
! if (dominated_by_p (pre_idom, bb1, bb2))
return 1;
else
return -1;
--- 922,928 ----
{
if (dfn[bb1->index] == dfn[bb2->index])
{
! if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
return 1;
else
return -1;
*************** bool load_modified_phi_result (basic_blo
*** 1394,1400 ****
basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (cr));
if (defbb != bb)
{
! if (fast_a_dominates_b (defbb, bb))
return false;
}
else
--- 1352,1361 ----
basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (cr));
if (defbb != bb)
{
! if (!defbb)
! return true;
!
! if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
return false;
}
else
*************** process_delayed_rename (struct expr_info
*** 1545,1563 ****
}
}
- /* Return whether BB A dominates BB B without using the slow
- et-forest all the time. */
-
- static inline bool
- fast_a_dominates_b (basic_block bb1, basic_block bb2)
- {
- if (!bb1 || !bb2 || bb1->index < 0 || bb2->index < 0)
- return dominated_by_p (pre_idom, bb1, bb2);
-
- return (dfs_id[bb2->index] >= dfs_id[bb1->index])
- && (dfs_id[bb2->index] <= dfs_id_last[bb1->index]);
- }
-
/* Renaming is done like Open64 does it. Basically as the paper says,
except that we try to use earlier defined occurrences if they are
available in order to keep the number of saves down. */
--- 1506,1511 ----
*************** rename_1 (struct expr_info *ei)
*** 1579,1586 ****
occur = VARRAY_TREE (ei->euses_dt_order, i);
while (VARRAY_ACTIVE_SIZE (stack) > 0
! && !fast_a_dominates_b (bb_for_stmt (VARRAY_TOP_TREE (stack)),
! bb_for_stmt (occur)))
VARRAY_POP (stack);
if (VARRAY_TOP_TREE (stack) == NULL || VARRAY_ACTIVE_SIZE (stack) == 0)
--- 1527,1535 ----
occur = VARRAY_TREE (ei->euses_dt_order, i);
while (VARRAY_ACTIVE_SIZE (stack) > 0
! && !dominated_by_p (CDI_DOMINATORS,
! bb_for_stmt (occur),
! bb_for_stmt (VARRAY_TOP_TREE (stack))))
VARRAY_POP (stack);
if (VARRAY_TOP_TREE (stack) == NULL || VARRAY_ACTIVE_SIZE (stack) == 0)
*************** reaching_def (tree var, tree currstmt, b
*** 1975,1981 ****
}
if (curruse != NULL_TREE)
return curruse;
! dom = get_immediate_dominator (pre_idom, bb);
if (bb == ENTRY_BLOCK_PTR)
{
htab_t temp;
--- 1924,1930 ----
}
if (curruse != NULL_TREE)
return curruse;
! dom = get_immediate_dominator (CDI_DOMINATORS, bb);
if (bb == ENTRY_BLOCK_PTR)
{
htab_t temp;
*************** finalize_1 (struct expr_info *ei)
*** 2083,2089 ****
else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
{
if (avdefs[nx] == NULL
! || !dominated_by_p (pre_idom, bb_for_stmt (x),
bb_for_stmt (avdefs[nx])))
{
EREF_RELOAD (x) = false;
--- 2032,2038 ----
else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
{
if (avdefs[nx] == NULL
! || !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (x),
bb_for_stmt (avdefs[nx])))
{
EREF_RELOAD (x) = false;
*************** static void
*** 3093,3100 ****
collect_expressions (basic_block block, varray_type *bexprsp)
{
size_t k;
- int i;
block_stmt_iterator j;
varray_type bexprs = *bexprsp;
--- 3042,3049 ----
collect_expressions (basic_block block, varray_type *bexprsp)
{
size_t k;
block_stmt_iterator j;
+ basic_block son;
varray_type bexprs = *bexprsp;
*************** collect_expressions (basic_block block,
*** 3182,3193 ****
process_left_occs_and_kills (bexprs, orig_expr);
}
*bexprsp = bexprs;
! if (dom_children (block))
! EXECUTE_IF_SET_IN_BITMAP (dom_children (block), 0, i,
! {
! collect_expressions (BASIC_BLOCK (i), bexprsp);
! });
!
}
/* Main entry point to the SSA-PRE pass.
--- 3131,3141 ----
process_left_occs_and_kills (bexprs, orig_expr);
}
*bexprsp = bexprs;
!
! for (son = first_dom_son (CDI_DOMINATORS, block);
! son;
! son = next_dom_son (CDI_DOMINATORS, son))
! collect_expressions (son, bexprsp);
}
/* Main entry point to the SSA-PRE pass.
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3220,3232 ****
sizeof (struct ephi_use_entry), 30);
VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
VARRAY_TREE_INIT (added_phis, 1, "Added phis");
/* Compute immediate dominators. */
! pre_idom = calculate_dominance_info (CDI_DOMINATORS);
/* DCE screws the dom_children up, without bothering to fix it. So fix it. */
currbbs = n_basic_blocks;
- build_dominator_tree (pre_idom);
- build_dfs_id_array ();
dfn = xcalloc (last_basic_block + 1, sizeof (int));
build_dfn_array (ENTRY_BLOCK_PTR, 0);
--- 3168,3179 ----
sizeof (struct ephi_use_entry), 30);
VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
VARRAY_TREE_INIT (added_phis, 1, "Added phis");
+
/* Compute immediate dominators. */
! calculate_dominance_info (CDI_DOMINATORS);
/* DCE screws the dom_children up, without bothering to fix it. So fix it. */
currbbs = n_basic_blocks;
dfn = xcalloc (last_basic_block + 1, sizeof (int));
build_dfn_array (ENTRY_BLOCK_PTR, 0);
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3237,3243 ****
pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
for (i = 0; i < currbbs; i++)
pre_dfs[i] = BITMAP_XMALLOC ();
! compute_dominance_frontiers (pre_dfs, pre_idom);
created_phi_preds = BITMAP_XMALLOC ();
--- 3184,3190 ----
pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
for (i = 0; i < currbbs; i++)
pre_dfs[i] = BITMAP_XMALLOC ();
! compute_dominance_frontiers (pre_dfs);
created_phi_preds = BITMAP_XMALLOC ();
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3281,3287 ****
free_alloc_pool (euse_node_pool);
free_alloc_pool (eref_node_pool);
VARRAY_CLEAR (bexprs);
- free_dominance_info (pre_idom);
for (i = 0; i < currbbs; i++)
BITMAP_XFREE (pre_dfs[i]);
free (pre_dfs);
--- 3228,3233 ----
*************** tree_perform_ssapre (tree fndecl, enum t
*** 3295,3302 ****
if (bitmap_first_set_bit (vars_to_rename) != -1)
rewrite_into_ssa (fndecl, vars_to_rename, TDI_pre);
BITMAP_XFREE (vars_to_rename);
- free (dfs_id);
- free (dfs_id_last);
free (dfn);
timevar_pop (TV_TREE_PRE);
}
--- 3241,3246 ----
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.178
diff -c -3 -p -r1.1.4.178 tree-ssa.c
*** tree-ssa.c 15 Dec 2003 22:58:36 -0000 1.1.4.178
--- tree-ssa.c 18 Dec 2003 14:34:52 -0000
*************** struct mark_def_sites_global_data
*** 88,97 ****
solely to avoid the overhead of allocating and deallocating
the bitmap. */
sbitmap kills;
-
- /* We need dominance information when we find a use of a variable
- that is not proceeded by a set of the variable in the same block. */
- dominance_info idom;
};
/* Table to store the current reaching definition for every variable in
--- 88,93 ----
*************** static void mark_def_sites (struct dom_w
*** 183,189 ****
tree parent_block_last_stmt ATTRIBUTE_UNUSED);
static void compute_global_livein (bitmap, bitmap);
static void set_def_block (tree, basic_block);
! static void set_livein_block (tree, basic_block, dominance_info);
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *);
static void rewrite_stmt (block_stmt_iterator, varray_type *);
--- 179,185 ----
tree parent_block_last_stmt ATTRIBUTE_UNUSED);
static void compute_global_livein (bitmap, bitmap);
static void set_def_block (tree, basic_block);
! static void set_livein_block (tree, basic_block);
static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *);
static void rewrite_stmt (block_stmt_iterator, varray_type *);
*************** static void print_exprs (FILE *, const c
*** 226,234 ****
static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
tree);
static bool verify_def (basic_block, basic_block *, tree, tree);
! static bool verify_use (basic_block, basic_block, tree, tree, dominance_info,
! bool);
! static bool verify_phi_args (tree, basic_block, dominance_info, basic_block *);
/* Return the value associated with variable VAR in TABLE. */
--- 222,229 ----
static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
tree);
static bool verify_def (basic_block, basic_block *, tree, tree);
! static bool verify_use (basic_block, basic_block, tree, tree, bool);
! static bool verify_phi_args (tree, basic_block, basic_block *);
/* Return the value associated with variable VAR in TABLE. */
*************** void
*** 339,345 ****
rewrite_into_ssa (tree fndecl, bitmap vars, enum tree_dump_index phase)
{
bitmap *dfs;
- dominance_info idom;
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
--- 334,339 ----
*************** rewrite_into_ssa (tree fndecl, bitmap va
*** 377,393 ****
dfs[bb->index] = BITMAP_XMALLOC ();
}
! /* Compute immediate dominators, dominance frontiers and the dominator
! tree. FIXME: DFS and dominator tree information should be cached.
! Although, right now the only pass that doesn't mess dominance
! information is must-alias.
!
! We also use the dominator information during the dominator walk to
! find def/use sites. So the dominator information can not be freed
! until after the mark_def_sites dominator walk. */
! idom = calculate_dominance_info (CDI_DOMINATORS);
! build_dominator_tree (idom);
! compute_dominance_frontiers (dfs, idom);
/* Setup callbacks for the generic dominator tree walker to find and
mark definition sites. */
--- 371,381 ----
dfs[bb->index] = BITMAP_XMALLOC ();
}
! /* Ensure that the dominance information is OK. */
! calculate_dominance_info (CDI_DOMINATORS);
!
! /* Compute dominance frontiers. */
! compute_dominance_frontiers (dfs);
/* Setup callbacks for the generic dominator tree walker to find and
mark definition sites. */
*************** rewrite_into_ssa (tree fndecl, bitmap va
*** 403,409 ****
large enough to accommodate all the variables referenced in the
function, not just the ones we are renaming. */
mark_def_sites_global_data.kills = sbitmap_alloc (num_referenced_vars);
- mark_def_sites_global_data.idom = idom;
walk_data.global_data = &mark_def_sites_global_data;
/* We do not have any local data. */
--- 391,396 ----
*************** rewrite_into_ssa (tree fndecl, bitmap va
*** 421,429 ****
/* We no longer need this bitmap, clear and free it. */
sbitmap_free (mark_def_sites_global_data.kills);
- /* We are done with the dominance information. Release it. */
- free_dominance_info (idom);
-
/* Insert PHI nodes at dominance frontiers of definition blocks. */
insert_phi_nodes (dfs);
--- 408,413 ----
*************** rewrite_into_ssa (tree fndecl, bitmap va
*** 477,504 ****
timevar_pop (TV_TREE_SSA_OTHER);
}
- /* Given immediate dominator information IDOM, build the dominator
- tree. */
-
- void
- build_dominator_tree (dominance_info idom)
- {
- basic_block bb;
-
- FOR_ALL_BB (bb)
- clear_dom_children (bb);
-
- /* Using the immediate dominators, build a dominator tree. */
- FOR_EACH_BB (bb)
- {
- /* Add BB to the set of dominator children of BB's immediate
- dominator. */
- basic_block idom_bb = get_immediate_dominator (idom, bb);
- if (idom_bb)
- add_dom_child (idom_bb, bb);
- }
- }
-
/* Compute global livein information given the set of blockx where
an object is locally live at the start of the block (LIVEIN)
and the set of blocks where the object is defined (DEF_BLOCKS).
--- 461,466 ----
*************** mark_def_sites (struct dom_walk_data *wa
*** 563,569 ****
{
struct mark_def_sites_global_data *gd = walk_data->global_data;
sbitmap kills = gd->kills;
- dominance_info idom = gd->idom;
block_stmt_iterator si;
/* Mark all the blocks that have definitions for each variable in the
--- 525,530 ----
*************** mark_def_sites (struct dom_walk_data *wa
*** 593,599 ****
if (prepare_operand_for_rename (use_p, &uid)
&& !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb, idom);
}
/* Similarly for virtual uses. */
--- 554,560 ----
if (prepare_operand_for_rename (use_p, &uid)
&& !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb);
}
/* Similarly for virtual uses. */
*************** mark_def_sites (struct dom_walk_data *wa
*** 604,610 ****
if (prepare_operand_for_rename (use_p, &uid)
&& !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb, idom);
}
/* Note that virtual definitions are irrelevant for computing
--- 565,571 ----
if (prepare_operand_for_rename (use_p, &uid)
&& !TEST_BIT (kills, uid))
! set_livein_block (*use_p, bb);
}
/* Note that virtual definitions are irrelevant for computing
*************** mark_def_sites (struct dom_walk_data *wa
*** 625,631 ****
set_def_block (VDEF_RESULT (vdefs, i), bb);
if (!TEST_BIT (kills, uid))
! set_livein_block (VDEF_OP (vdefs, i), bb, idom);
}
}
--- 586,592 ----
set_def_block (VDEF_RESULT (vdefs, i), bb);
if (!TEST_BIT (kills, uid))
! set_livein_block (VDEF_OP (vdefs, i), bb);
}
}
*************** set_def_block (tree var, basic_block bb)
*** 691,697 ****
/* Mark block BB as having VAR live at the entry to BB. */
static void
! set_livein_block (tree var, basic_block bb, dominance_info idom)
{
struct def_blocks_d db, *db_p;
void **slot;
--- 652,658 ----
/* Mark block BB as having VAR live at the entry to BB. */
static void
! set_livein_block (tree var, basic_block bb)
{
struct def_blocks_d db, *db_p;
void **slot;
*************** set_livein_block (tree var, basic_block
*** 725,731 ****
int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
if (def_block_index == -1
! || ! dominated_by_p (idom, bb, BASIC_BLOCK (def_block_index)))
var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
}
else
--- 686,692 ----
int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
if (def_block_index == -1
! || ! dominated_by_p (CDI_DOMINATORS, bb, BASIC_BLOCK (def_block_index)))
var_ann (var)->need_phi_state = NEED_PHI_STATE_MAYBE;
}
else
*************** verify_def (basic_block bb, basic_block
*** 2926,2932 ****
static bool
verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
! tree stmt, dominance_info idom, bool check_abnormal)
{
bool err = false;
--- 2887,2893 ----
static bool
verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
! tree stmt, bool check_abnormal)
{
bool err = false;
*************** verify_use (basic_block bb, basic_block
*** 2938,2944 ****
err = true;
}
else if (bb != def_bb
! && !dominated_by_p (idom, bb, def_bb))
{
error ("Definition in block %i does not dominate use in block %i",
def_bb->index, bb->index);
--- 2899,2905 ----
err = true;
}
else if (bb != def_bb
! && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
{
error ("Definition in block %i does not dominate use in block %i",
def_bb->index, bb->index);
*************** verify_use (basic_block bb, basic_block
*** 2974,2981 ****
block in that array slot contains the definition of SSA_NAME. */
static bool
! verify_phi_args (tree phi, basic_block bb, dominance_info idom,
! basic_block *definition_block)
{
edge e;
bool err = false;
--- 2935,2941 ----
block in that array slot contains the definition of SSA_NAME. */
static bool
! verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
{
edge e;
bool err = false;
*************** verify_phi_args (tree phi, basic_block b
*** 2993,2999 ****
if (TREE_CODE (op) == SSA_NAME)
err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
! phi, idom, e->flags & EDGE_ABNORMAL);
if (e->dest != bb)
{
--- 2953,2959 ----
if (TREE_CODE (op) == SSA_NAME)
err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
! phi, e->flags & EDGE_ABNORMAL);
if (e->dest != bb)
{
*************** verify_ssa (void)
*** 3055,3067 ****
{
bool err = false;
basic_block bb;
- dominance_info idom;
basic_block *definition_block = xcalloc (highest_ssa_version,
sizeof (basic_block));
timevar_push (TV_TREE_SSA_VERIFY);
! idom = calculate_dominance_info (CDI_DOMINATORS);
/* Verify and register all the SSA_NAME definitions found in the
function. */
--- 3015,3026 ----
{
bool err = false;
basic_block bb;
basic_block *definition_block = xcalloc (highest_ssa_version,
sizeof (basic_block));
timevar_push (TV_TREE_SSA_VERIFY);
! calculate_dominance_info (CDI_DOMINATORS);
/* Verify and register all the SSA_NAME definitions found in the
function. */
*************** verify_ssa (void)
*** 3135,3141 ****
/* Verify the arguments for every PHI node in the block. */
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! err |= verify_phi_args (phi, bb, idom, definition_block);
/* Now verify all the uses and vuses in every statement of the block. */
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 3094,3100 ----
/* Verify the arguments for every PHI node in the block. */
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! err |= verify_phi_args (phi, bb, definition_block);
/* Now verify all the uses and vuses in every statement of the block. */
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
*************** verify_ssa (void)
*** 3158,3164 ****
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
! op, stmt, idom, false);
}
uses = STMT_USE_OPS (stmt);
--- 3117,3123 ----
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
! op, stmt, false);
}
uses = STMT_USE_OPS (stmt);
*************** verify_ssa (void)
*** 3174,3185 ****
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
! op, stmt, idom, false);
}
}
}
- free_dominance_info (idom);
free (definition_block);
timevar_pop (TV_TREE_SSA_VERIFY);
--- 3133,3143 ----
err = true;
}
err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
! op, stmt, false);
}
}
}
free (definition_block);
timevar_pop (TV_TREE_SSA_VERIFY);
Index: tree-tailcall.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-tailcall.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-tailcall.c
*** tree-tailcall.c 17 Dec 2003 19:53:02 -0000 1.1.2.10
--- tree-tailcall.c 18 Dec 2003 14:34:52 -0000
*************** tree_optimize_tail_calls (bool opt_tailc
*** 395,401 ****
}
if (changed)
! cleanup_tree_cfg ();
if (dump_file)
{
--- 395,404 ----
}
if (changed)
! {
! free_dominance_info (CDI_DOMINATORS);
! cleanup_tree_cfg ();
! }
if (dump_file)
{