This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] jump threading
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 30 Oct 2003 23:09:41 -0700
- Subject: [tree-ssa] jump threading
- Reply-to: law at redhat dot com
The lowering of COND_EXPRs has resulted in largely disabling the
threading of jumps through blocks starting with conditionals. This
is the first step in restoring that capability.
Basically instead of threading the successors of a block, we thread through
the destination of a specific edge. This is necessary so that we can
eventually thread through a naked GOTO_EXPR or a GOTO_EXPR embedded inside
a COND_EXPR.
Nothing terribly exciting here.
* tree-ssa-dom.c (thread_across_edge): Renamed from
thread_through_successor. Revamp to thread the destination of an edge
rather than the successors of a block.
(dom_opt_finalize_block): Corresponding changes. Do not bother calling
thread_across_edge unless we are at a leaf in the dominator tree.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.68
diff -c -p -r1.1.2.68 tree-ssa-dom.c
*** tree-ssa-dom.c 30 Oct 2003 02:49:41 -0000 1.1.2.68
--- tree-ssa-dom.c 31 Oct 2003 06:00:50 -0000
*************** static void record_equivalences_from_inc
*** 201,207 ****
static bool eliminate_redundant_computations (tree, varray_type *,
stmt_ann_t);
static void record_equivalences_from_stmt (tree, varray_type *,
int, stmt_ann_t);
! static void thread_through_successor (basic_block, varray_type *);
static void dom_opt_finalize_block (struct dom_walk_data *, basic_block,
tree);
static void dom_opt_initialize_block (struct dom_walk_data *,
basic_block, tree);
--- 201,207 ----
static bool eliminate_redundant_computations (tree, varray_type *,
stmt_ann_t);
static void record_equivalences_from_stmt (tree, varray_type *,
int, stmt_ann_t);
! static void thread_across_edge (edge, varray_type *);
static void dom_opt_finalize_block (struct dom_walk_data *, basic_block,
tree);
static void dom_opt_initialize_block (struct dom_walk_data *,
basic_block, tree);
*************** tree_ssa_dominator_optimize_1 (tree fnde
*** 485,500 ****
jump which has a known value when reached via BB. */
static void
! thread_through_successor (basic_block bb, varray_type *block_avail_exprs)
{
/* If we have a single successor, then we may be able to thread
the edge out of our block to a destination of our successor.
Only thread through a successor with PHI nodes if explicitly asked to.
*/
! if (bb->succ && bb->succ->succ_next == NULL
! && (thread_through_phis || ! phi_nodes (bb->succ->dest)))
{
! block_stmt_iterator bsi = bsi_start (bb->succ->dest);
tree stmt = NULL;
/* Walk past any empty statements and labels. */
--- 485,499 ----
jump which has a known value when reached via BB. */
static void
! thread_across_edge (edge e, varray_type *block_avail_exprs)
{
/* If we have a single successor, then we may be able to thread
the edge out of our block to a destination of our successor.
Only thread through a successor with PHI nodes if explicitly asked to.
*/
! if (thread_through_phis || ! phi_nodes (e->dest))
{
! block_stmt_iterator bsi = bsi_start (e->dest);
tree stmt = NULL;
/* Walk past any empty statements and labels. */
*************** thread_through_successor (basic_block bb
*** 531,537 ****
BB's successor. If it is, then we can not thread
this jump. */
if (TREE_CODE (def_stmt) == PHI_NODE
! && bb_for_stmt (def_stmt) == bb->succ->dest)
return;
}
}
--- 530,536 ----
BB's successor. If it is, then we can not thread
this jump. */
if (TREE_CODE (def_stmt) == PHI_NODE
! && bb_for_stmt (def_stmt) == e->dest)
return;
}
}
*************** thread_through_successor (basic_block bb
*** 539,547 ****
cached_lhs = lookup_avail_expr (stmt, block_avail_exprs, false);
if (cached_lhs)
{
! edge taken_edge = find_taken_edge (bb->succ->dest, cached_lhs);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
/* If we have a known destination for the conditional, then
we can perform this optimization, which saves at least one
conditional jump each time it applies since we get to
--- 538,549 ----
cached_lhs = lookup_avail_expr (stmt, block_avail_exprs, false);
if (cached_lhs)
{
! edge taken_edge = find_taken_edge (e->dest, cached_lhs);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
+ if (dest == e->src)
+ return;
+
/* If we have a known destination for the conditional, then
we can perform this optimization, which saves at least one
conditional jump each time it applies since we get to
*************** thread_through_successor (basic_block bb
*** 549,563 ****
if (dest && ! phi_nodes (dest))
{
basic_block forwards_to;
! int saved_forwardable = bb_ann (bb)->forwardable;
! bb_ann (bb)->forwardable = 0;
forwards_to = tree_block_forwards_to (dest);
! bb_ann (bb)->forwardable = saved_forwardable;
dest = (forwards_to ? forwards_to : dest);
! VARRAY_PUSH_EDGE (edges_to_redirect, bb->succ);
VARRAY_PUSH_BB (redirection_targets, dest);
}
}
--- 551,565 ----
if (dest && ! phi_nodes (dest))
{
basic_block forwards_to;
! int saved_forwardable = bb_ann (e->src)->forwardable;
! bb_ann (e->src)->forwardable = 0;
forwards_to = tree_block_forwards_to (dest);
! bb_ann (e->src)->forwardable = saved_forwardable;
dest = (forwards_to ? forwards_to : dest);
! VARRAY_PUSH_EDGE (edges_to_redirect, e);
VARRAY_PUSH_BB (redirection_targets, dest);
}
}
*************** dom_opt_finalize_block (struct dom_walk_
*** 627,635 ****
varray_type vrp_variables = bd->vrp_variables;
varray_type stmts_to_rescan = bd->stmts_to_rescan;
! /* See if we can thread the edge from BB through its successor.
Do this before we remove entries from our equivalence tables. */
! thread_through_successor (bb, NULL);
/* Remove all the expressions made available in this block. */
while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
--- 629,646 ----
varray_type vrp_variables = bd->vrp_variables;
varray_type stmts_to_rescan = bd->stmts_to_rescan;
! /* If we are at a leaf node in the dominator graph, see if we can thread
! the edge from BB through its successor.
!
Do this before we remove entries from our equivalence tables. */
! 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, NULL);
! }
/* Remove all the expressions made available in this block. */
while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)