This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Fix bug in tree-ssa-dom
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: law at redhat dot com
- Date: Thu, 28 Aug 2003 21:46:00 +0200
- Subject: [tree-ssa] Fix bug in tree-ssa-dom
Hello,
this patch fixes the bug caused by the fact that jump threading changes
the dominator tree (the one Jeff claimed that it does not exist, so
here is a testcase).
It adds these changes:
1) redirection of edges in jump threading is postponed and done only
after optimization, so the dominator tree does not change due to it
in the middle of optimization
2) blocks that are made unreachable are removed between the iterations
3) if cfg is altered, dominator tree is recomputed
3) is probably a bit time consuming, but it may reveal new possibilities
for optimization, so it might be worth that.
Zdenek
testcase:
void abort ();
void exit (int);
void test(int x, int y)
{
if (x == y)
abort ();
}
void foo(int x, int y)
{
if (x == y)
goto a;
else
{
a:;
if (x == y)
goto b;
else
{
b:;
if (x != y)
test (x, y);
}
}
}
int main(void)
{
foo (0, 0);
exit (0);
}
* tree-flow.h (remove_unreachable_blocks): Declare.
* tree-cfg.c (remove_unreachable_blocks): Export. Make it work
when blocks are non-contiguous.
* tree-ssa-dom.c (optimize_block, optimize_stmt): Record whether
cfg has changed. Just schedule jump threading.
(edges_to_redirect, redirection_targets): New variables.
(thread_edge): Split of optimize_block.
(tree_ssa_dominator_optimize): Recompute dominator tree when cfg
is changed.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.107
diff -c -3 -p -r1.1.4.107 tree-flow.h
*** tree-flow.h 28 Aug 2003 01:14:21 -0000 1.1.4.107
--- tree-flow.h 28 Aug 2003 18:35:32 -0000
*************** extern void debug_cfg_stats (void);
*** 423,428 ****
--- 423,429 ----
extern void tree_cfg2dot (FILE *);
extern void insert_bb_before (basic_block, basic_block);
extern void cleanup_tree_cfg (void);
+ extern bool remove_unreachable_blocks (void);
extern void remove_phi_nodes_and_edges_for_unreachable_block (basic_block);
extern tree first_stmt (basic_block);
extern tree last_stmt (basic_block);
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.155
diff -c -3 -p -r1.1.4.155 tree-cfg.c
*** tree-cfg.c 24 Aug 2003 03:04:40 -0000 1.1.4.155
--- tree-cfg.c 28 Aug 2003 18:35:37 -0000
*************** static void tree_loop_optimizer_finalize
*** 130,136 ****
#define REMOVE_NON_CONTROL_STMTS 0x1
#define REMOVE_CONTROL_STMTS 0x2
- static void remove_unreachable_blocks (void);
static void remove_unreachable_block (basic_block);
static void remove_bb (basic_block, int);
static void remove_stmt (tree *, bool);
--- 130,135 ----
*************** remove_useless_stmts_and_vars (tree *fir
*** 1849,1864 ****
/* Delete all unreachable basic blocks. */
! static void
remove_unreachable_blocks (void)
{
int i;
find_unreachable_blocks ();
/* Remove unreachable blocks in reverse. That will expose more unnecessary
COMPOUND_EXPRs that we can remove. */
! for (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
--- 1848,1864 ----
/* Delete all unreachable basic blocks. */
! bool
remove_unreachable_blocks (void)
{
int i;
+ bool ret = false;
find_unreachable_blocks ();
/* Remove unreachable blocks in reverse. That will expose more unnecessary
COMPOUND_EXPRs that we can remove. */
! for (i = last_basic_block - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
*************** remove_unreachable_blocks (void)
*** 1868,1875 ****
continue;
if (!(bb->flags & BB_REACHABLE))
! remove_unreachable_block (bb);
}
}
--- 1868,1880 ----
continue;
if (!(bb->flags & BB_REACHABLE))
! {
! remove_unreachable_block (bb);
! ret = true;
! }
}
+
+ return ret;
}
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.31
diff -c -3 -p -r1.1.2.31 tree-ssa-dom.c
*** tree-ssa-dom.c 25 Aug 2003 22:24:10 -0000 1.1.2.31
--- tree-ssa-dom.c 28 Aug 2003 18:35:38 -0000
*************** struct opt_stats_d
*** 81,89 ****
static struct opt_stats_d opt_stats;
/* Local functions. */
! static void optimize_block (basic_block, tree, int, sbitmap);
! static bool optimize_stmt (block_stmt_iterator, varray_type *);
static tree get_value_for (tree, htab_t);
static void set_value_for (tree, tree, htab_t);
static hashval_t var_value_hash (const void *);
--- 81,93 ----
static struct opt_stats_d opt_stats;
+ /* Redirections scheduled by jump threading. */
+ static varray_type edges_to_redirect;
+ static varray_type redirection_targets;
+
/* Local functions. */
! static void optimize_block (basic_block, tree, int, sbitmap, bool *);
! static bool optimize_stmt (block_stmt_iterator, varray_type *, bool *);
static tree get_value_for (tree, htab_t);
static void set_value_for (tree, tree, htab_t);
static hashval_t var_value_hash (const void *);
*************** static int avail_expr_eq (const void *,
*** 95,100 ****
--- 99,105 ----
static void htab_statistics (FILE *, htab_t);
static void record_cond_is_false (tree, varray_type *, htab_t);
static void record_cond_is_true (tree, varray_type *, htab_t);
+ static void thread_edge (edge, basic_block);
static void find_new_vars_to_rename (tree, sbitmap);
/* Optimize function FNDECL based on the dominator tree. This does
*************** static void find_new_vars_to_rename (tre
*** 108,116 ****
void
tree_ssa_dominator_optimize (tree fndecl, sbitmap vars_to_rename)
{
! bool found_unreachable;
edge e;
- bitmap unreachable_bitmap = BITMAP_XMALLOC ();
timevar_push (TV_TREE_SSA_DOMINATOR_OPTS);
--- 113,120 ----
void
tree_ssa_dominator_optimize (tree fndecl, sbitmap vars_to_rename)
{
! bool cfg_altered;
edge e;
timevar_push (TV_TREE_SSA_DOMINATOR_OPTS);
*************** tree_ssa_dominator_optimize (tree fndecl
*** 141,147 ****
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
have turned into copies which allows better propagation of
--- 145,154 ----
build_dominator_tree (idom);
free_dominance_info (idom);
}
!
! VARRAY_EDGE_INIT (edges_to_redirect, 20, "edges_to_redirect");
! VARRAY_BB_INIT (redirection_targets, 20, "redirection_targets");
!
/* If we prove certain blocks are unreachable, then we want to
repeat the dominator optimization process as PHI nodes may
have turned into copies which allows better propagation of
*************** tree_ssa_dominator_optimize (tree fndecl
*** 149,192 ****
blocks. */
do
{
- int i;
-
/* Optimize the dominator tree. */
! optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename);
/* Wipe the hash tables. */
htab_empty (const_and_copies);
htab_empty (avail_exprs);
! /* We may have made some basic blocks unreachable. We do not
! want to call tree_cleanup_cfg here as it renumbers the blocks
! which makes dom_children invalid.
!
! Instead we simplify identify the unreachable blocks and
! remove their edges and PHI nodes. After rewriting we will
! complete removal of the unreachable blocks. */
! find_unreachable_blocks ();
!
! found_unreachable = false;
!
! for (i = 0; i < n_basic_blocks; i++)
{
! basic_block bb = BASIC_BLOCK (i);
! if (! (bb->flags & BB_REACHABLE))
{
! /* If a previous iteration determined this block was
! unreachable, then just ignore the block. */
! if (bitmap_bit_p (unreachable_bitmap, bb->index))
! continue;
! found_unreachable = true;
! bitmap_set_bit (unreachable_bitmap, bb->index);
! remove_phi_nodes_and_edges_for_unreachable_block (bb);
}
}
}
! while (found_unreachable);
/* Debugging dumps. */
if (dump_file)
--- 156,204 ----
blocks. */
do
{
/* Optimize the dominator tree. */
! cfg_altered = false;
! optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename, &cfg_altered);
/* Wipe the hash tables. */
htab_empty (const_and_copies);
htab_empty (avail_exprs);
! /* If some edges were threaded, perform the redirections, recompute
! dominators and try again. */
! if (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
{
! basic_block tgt;
! while (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
{
! e = VARRAY_TOP_EDGE (edges_to_redirect);
! tgt = VARRAY_TOP_BB (redirection_targets);
! VARRAY_POP (edges_to_redirect);
! VARRAY_POP (redirection_targets);
! thread_edge (e, tgt);
}
+
+ cfg_altered = true;
+ }
+
+ /* We may have made some basic blocks unreachable; remove them. */
+ cfg_altered |= remove_unreachable_blocks ();
+
+ /* If jumps were threaded the dominator tree could have changed
+ significantly, so we must recompute it. If there were unreachable
+ blocks or edges, the dominator tree could have changed, so recomputing
+ it may yield better results, but it is not strictly neccesary (it
+ would be enough to prune removed blocks from dom_children). */
+ if (cfg_altered)
+ {
+ dominance_info idom = calculate_dominance_info (CDI_DOMINATORS);
+ build_dominator_tree (idom);
+ free_dominance_info (idom);
}
}
! while (cfg_altered);
/* Debugging dumps. */
if (dump_file)
*************** tree_ssa_dominator_optimize (tree fndecl
*** 199,209 ****
htab_delete (const_and_copies);
htab_delete (avail_exprs);
! BITMAP_XFREE (unreachable_bitmap);
timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
}
/* Perform a depth-first traversal of the dominator tree looking for
redundant expressions and copy/constant propagation opportunities.
--- 211,287 ----
htab_delete (const_and_copies);
htab_delete (avail_exprs);
!
! VARRAY_FREE (edges_to_redirect);
! VARRAY_FREE (redirection_targets);
timevar_pop (TV_TREE_SSA_DOMINATOR_OPTS);
}
+ /* Redirects edge E to basic block DEST. */
+ static void
+ thread_edge (edge e, basic_block dest)
+ {
+ block_stmt_iterator dest_iterator = bsi_start (dest);
+ tree dest_stmt = first_stmt (dest);
+ tree label, goto_stmt, stmt;
+ basic_block bb = e->src, new_bb;
+ int flags = e->flags;
+
+ if (e != bb->succ
+ || bb->succ->succ_next)
+ abort ();
+
+ /* We need a label at our final destination. If it does not already exist,
+ create it. */
+ if (!dest_stmt
+ || TREE_CODE (dest_stmt) != LABEL_EXPR)
+ {
+ label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+ DECL_CONTEXT (label) = current_function_decl;
+ dest_stmt = build1 (LABEL_EXPR, void_type_node, label);
+ bsi_insert_before (&dest_iterator, dest_stmt, BSI_NEW_STMT);
+ }
+ else
+ label = LABEL_EXPR_LABEL (dest_stmt);
+
+ /* If our block does not end with a GOTO, then create one. Otherwise redirect
+ the existing GOTO_EXPR to LABEL. */
+ stmt = last_stmt (bb);
+ if (!stmt || TREE_CODE (stmt) != GOTO_EXPR)
+ {
+ goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
+ bsi_insert_on_edge_immediate (e, goto_stmt, NULL, &new_bb);
+ }
+ else
+ {
+ GOTO_DESTINATION (stmt) = label;
+ new_bb = NULL;
+ }
+
+ /* Update/insert PHI nodes as necessary. */
+
+ /* Now update the edges in the CFG. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
+ e->src->index, e->dest->index, dest->index);
+ if (new_bb)
+ fprintf (dump_file, " basic block %d created\n", new_bb->index);
+ }
+
+ if (new_bb)
+ {
+ ssa_remove_edge (new_bb->succ);
+ make_edge (new_bb, dest, 0);
+ }
+ else
+ {
+ ssa_remove_edge (e);
+ make_edge (bb, dest, flags);
+ }
+ }
+
/* Perform a depth-first traversal of the dominator tree looking for
redundant expressions and copy/constant propagation opportunities.
*************** tree_ssa_dominator_optimize (tree fndecl
*** 227,237 ****
of a THEN_CLAUSE or an ELSE_CLAUSE.
VARS_TO_RENAME is a bitmap representing variables that will need to be
! renamed into SSA after dominator optimization. */
static void
optimize_block (basic_block bb, tree parent_block_last_stmt, int edge_flags,
! sbitmap vars_to_rename)
{
varray_type block_avail_exprs;
varray_type stmts_to_rescan;
--- 305,317 ----
of a THEN_CLAUSE or an ELSE_CLAUSE.
VARS_TO_RENAME is a bitmap representing variables that will need to be
! renamed into SSA after dominator optimization.
!
! CFG_ALTERED is set to true if cfg is altered. */
static void
optimize_block (basic_block bb, tree parent_block_last_stmt, int edge_flags,
! sbitmap vars_to_rename, bool *cfg_altered)
{
varray_type block_avail_exprs;
varray_type stmts_to_rescan;
*************** optimize_block (basic_block bb, tree par
*** 395,401 ****
because that would change the statement's value number. If the
statement had been added to AVAIL_EXPRS, we would not be able to
find it again. */
! if (optimize_stmt (si, &block_avail_exprs))
VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
}
--- 475,481 ----
because that would change the statement's value number. If the
statement had been added to AVAIL_EXPRS, we would not be able to
find it again. */
! if (optimize_stmt (si, &block_avail_exprs, cfg_altered))
VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
}
*************** optimize_block (basic_block bb, tree par
*** 450,458 ****
also ensures that the predecessor is BB. */
if (!dest->pred->pred_next)
optimize_block (dest, last, dest->pred->flags,
! vars_to_rename);
else
! optimize_block (dest, NULL_TREE, 0, vars_to_rename);
}
});
}
--- 530,539 ----
also ensures that the predecessor is BB. */
if (!dest->pred->pred_next)
optimize_block (dest, last, dest->pred->flags,
! vars_to_rename, cfg_altered);
else
! optimize_block (dest, NULL_TREE, 0, vars_to_rename,
! cfg_altered);
}
});
}
*************** optimize_block (basic_block bb, tree par
*** 465,471 ****
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, NULL_TREE, 0, vars_to_rename);
});
}
}
--- 546,553 ----
/* The destination block may have become unreachable, in
which case there's no point in optimizing it. */
if (dest->pred)
! optimize_block (dest, NULL_TREE, 0, vars_to_rename,
! cfg_altered);
});
}
}
*************** optimize_block (basic_block bb, tree par
*** 505,559 ****
bypass the conditional at our original destination. */
if (dest && ! phi_nodes (dest))
{
! block_stmt_iterator dest_iterator = bsi_start (dest);
! tree dest_stmt = first_stmt (dest);
! tree label, goto_stmt;
!
! /* We need a label at our final destination. If it does
! not already exist, create it. */
! if (!dest_stmt
! || TREE_CODE (dest_stmt) != LABEL_EXPR)
! {
! label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
! DECL_CONTEXT (label) = current_function_decl;
! dest_stmt = build1 (LABEL_EXPR, void_type_node, label);
! bsi_insert_before (&dest_iterator,
! dest_stmt,
! BSI_NEW_STMT);
! }
! else
! label = LABEL_EXPR_LABEL (dest_stmt);
!
!
! /* If our block does not end with a GOTO, then create
! one. Otherwise redirect the existing GOTO_EXPR to
! LABEL. */
! stmt = last_stmt (bb);
! if (!stmt || TREE_CODE (stmt) != GOTO_EXPR)
! {
! basic_block tmp_bb;
!
! goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
! bsi_insert_on_edge_immediate (bb->succ, goto_stmt,
! NULL, &tmp_bb);
!
! #ifdef ENABLE_CHECKING
! if (tmp_bb)
! abort ();
! #endif
! }
! else
! GOTO_DESTINATION (stmt) = label;
!
! /* Update/insert PHI nodes as necessary. */
!
! /* Now update the edges in the CFG. */
! if (dump_file && (dump_flags & TDF_DETAILS))
! fprintf (dump_file, " Threaded jump from %d to %d\n",
! bb->succ->dest->index, dest->index);
!
! ssa_remove_edge (bb->succ);
! make_edge (bb, dest, 0);
}
}
}
--- 587,594 ----
bypass the conditional at our original destination. */
if (dest && ! phi_nodes (dest))
{
! VARRAY_PUSH_EDGE (edges_to_redirect, bb->succ);
! VARRAY_PUSH_BB (redirection_targets, dest);
}
}
}
*************** record_cond_is_false (tree cond,
*** 694,700 ****
the variable in the LHS in the CONST_AND_COPIES table. */
static bool
! optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p)
{
size_t i;
stmt_ann_t ann;
--- 729,736 ----
the variable in the LHS in the CONST_AND_COPIES table. */
static bool
! optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p,
! bool *cfg_altered)
{
size_t i;
stmt_ann_t ann;
*************** optimize_stmt (block_stmt_iterator si, v
*** 1160,1166 ****
{
next = e->succ_next;
if (e != taken_edge)
! ssa_remove_edge (e);
}
}
}
--- 1196,1205 ----
{
next = e->succ_next;
if (e != taken_edge)
! {
! ssa_remove_edge (e);
! *cfg_altered = true;
! }
}
}
}