Cleanup tree-ssa-dom -> tree-ssa-threadupdate inteface
Jeffrey A Law
law@redhat.com
Thu Jan 12 00:10:00 GMT 2006
I've never liked using e->aux to communicate between DOM
and tree-ssa-threadupdate. This patch removes that little
wart. Oddly enough, while I would have expected a tiny
compile-time slowdown, actual testing shows a tiny compile-time
speedup. That may be some kind of unexpected cache effect or
something similar.
Bootstrapped and regression tested on i686-pc-linux-gnu. I
also verified that for one of my test buckets that we get
identical assembly code before/after this change.
Jeff
-------------- next part --------------
* tree-ssa-threadupdate.c (threaded_edges): New VEC to
hold edge pairs.
(mark_threaded_blocks, register_jump_thread): New functions.
(thread_through_all_blocks): Remove unwanted argument. No
longer rely on e->aux to communicate thread target info.
Call mark_threaded_blocks. Release the threaded_blocks
bitmap and threaded_edges vector when complete.
* tree-ssa-dom.c (struct edge_info): Remove redirection_target field.
(threaded_blocks): Remove.
(tree_ssa_dominator_optimize): Remove initialization and
finalization of threaded_blocks. Simplify call to
thread_through_all_blocks.
(thread_across_edge): Call register_jump_thread rather than
storing thread information into e->aux.
(free_all_edge_infos): Simplify now that e->aux is no longer
used to communicate with thread_through_all_blocks.
* tree-flow.h (thread_through_all_blocks): Update prototype.
(register_jump_thread): Prototype.
Index: gcc/tree-ssa-threadupdate.c
===================================================================
*** gcc/tree-ssa-threadupdate.c (revision 109600)
--- gcc/tree-ssa-threadupdate.c (working copy)
*************** struct local_info
*** 147,152 ****
--- 147,160 ----
bool jumps_threaded;
};
+ /* Passes which use the jump threading code register jump threading
+ opportunities as they are discovered. We keep the registered
+ jump threading opportunities in this vector as edge pairs
+ (original_edge, target_edge). */
+ DEF_VEC_ALLOC_P(edge,heap);
+ static VEC(edge,heap) *threaded_edges;
+
+
/* Jump threading statistics. */
struct thread_stats_d
*************** thread_block (basic_block bb)
*** 802,819 ****
return local_info.jumps_threaded;
}
! /* Walk through all blocks and thread incoming edges to the block's
! destinations as requested. This is the only entry point into this
! file.
! Blocks which have one or more incoming edges have INCOMING_EDGE_THREADED
! set in the block's annotation.
- Each edge that should be threaded has the new destination edge stored in
- the original edge's AUX field.
! This routine (or one of its callees) will clear INCOMING_EDGE_THREADED
! in the block annotations and the AUX field in the edges.
It is the caller's responsibility to fix the dominance information
and rewrite duplicated SSA_NAMEs back into SSA form.
--- 810,846 ----
return local_info.jumps_threaded;
}
! /* Walk through the registered jump threads and convert them into a
! form convienent for this pass.
!
! Any block which has incoming edges threaded to outgoing edges
! will have its entry in THREADED_BLOCK set.
!
! Any threaded edge will have its new outgoing edge stored in the
! original edge's AUX field.
!
! This form avoids the need to walk all the edges in the CFG to
! discover blocks which need processing and avoids unnecessary
! hash table lookups to map from threaded edge to new target. */
!
! static void
! mark_threaded_blocks (bitmap threaded_blocks)
! {
! unsigned int i;
!
! for (i = 0; i < VEC_length (edge, threaded_edges); i += 2)
! {
! edge e = VEC_index (edge, threaded_edges, i);
! edge e2 = VEC_index (edge, threaded_edges, i + 1);
! e->aux = e2;
! bitmap_set_bit (threaded_blocks, e->dest->index);
! }
! }
! /* Walk through all blocks and thread incoming edges to the appropriate
! outgoing edge for each edge pair recorded in THREADED_EDGES.
It is the caller's responsibility to fix the dominance information
and rewrite duplicated SSA_NAMEs back into SSA form.
*************** thread_block (basic_block bb)
*** 821,835 ****
Returns true if one or more edges were threaded, false otherwise. */
bool
! thread_through_all_blocks (bitmap threaded_blocks)
{
bool retval = false;
unsigned int i;
bitmap_iterator bi;
rediscover_loops_after_threading = false;
memset (&thread_stats, 0, sizeof (thread_stats));
EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
{
basic_block bb = BASIC_BLOCK (i);
--- 848,869 ----
Returns true if one or more edges were threaded, false otherwise. */
bool
! thread_through_all_blocks (void)
{
bool retval = false;
unsigned int i;
bitmap_iterator bi;
+ bitmap threaded_blocks;
+ if (threaded_edges == NULL)
+ return false;
+
+ threaded_blocks = BITMAP_ALLOC (NULL);
rediscover_loops_after_threading = false;
memset (&thread_stats, 0, sizeof (thread_stats));
+ mark_threaded_blocks (threaded_blocks);
+
EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi)
{
basic_block bb = BASIC_BLOCK (i);
*************** thread_through_all_blocks (bitmap thread
*** 842,846 ****
--- 876,902 ----
fprintf (dump_file, "\nJumps threaded: %lu\n",
thread_stats.num_threaded_edges);
+ BITMAP_FREE (threaded_blocks);
+ threaded_blocks = NULL;
+ VEC_free (edge, heap, threaded_edges);
+ threaded_edges = NULL;
return retval;
}
+
+ /* Register a jump threading opportunity. We queue up all the jump
+ threading opportunities discovered by a pass and update the CFG
+ and SSA form all at once.
+
+ E is the edge we can thread, E2 is the new target edge. ie, we
+ are effectively recording that E->dest can be changed to E2->dest
+ after fixing the SSA graph. */
+
+ void
+ register_jump_thread (edge e, edge e2)
+ {
+ if (threaded_edges == NULL)
+ threaded_edges = VEC_alloc (edge, heap, 10);
+
+ VEC_safe_push (edge, heap, threaded_edges, e);
+ VEC_safe_push (edge, heap, threaded_edges, e2);
+ }
Index: gcc/tree-ssa-dom.c
===================================================================
*** gcc/tree-ssa-dom.c (revision 109600)
--- gcc/tree-ssa-dom.c (working copy)
*************** struct edge_info
*** 74,82 ****
and its maximum index rather than use a varray. */
tree *cond_equivalences;
unsigned int max_cond_equivalences;
-
- /* If we can thread this edge this field records the new target. */
- edge redirection_target;
};
--- 74,79 ----
*************** static VEC(tree,heap) *const_and_copies_
*** 141,150 ****
know their exact value. */
static bitmap nonzero_vars;
- /* Bitmap of blocks that are scheduled to be threaded through. This
- is used to communicate with thread_through_blocks. */
- static bitmap threaded_blocks;
-
/* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
when the current block is finalized.
--- 138,143 ----
*************** free_all_edge_infos (void)
*** 326,335 ****
if (edge_info)
{
- e->aux = edge_info->redirection_target;
if (edge_info->cond_equivalences)
free (edge_info->cond_equivalences);
free (edge_info);
}
}
}
--- 319,328 ----
if (edge_info)
{
if (edge_info->cond_equivalences)
free (edge_info->cond_equivalences);
free (edge_info);
+ e->aux = NULL;
}
}
}
*************** tree_ssa_dominator_optimize (void)
*** 372,378 ****
vrp_variables_stack = VEC_alloc (tree, heap, 20);
stmts_to_rescan = VEC_alloc (tree, heap, 20);
nonzero_vars = BITMAP_ALLOC (NULL);
- threaded_blocks = BITMAP_ALLOC (NULL);
need_eh_cleanup = BITMAP_ALLOC (NULL);
/* Setup callbacks for the generic dominator tree walker. */
--- 365,370 ----
*************** tree_ssa_dominator_optimize (void)
*** 448,454 ****
free_all_edge_infos ();
/* Thread jumps, creating duplicate blocks as needed. */
! cfg_altered |= thread_through_all_blocks (threaded_blocks);
/* Removal of statements may make some EH edges dead. Purge
such edges from the CFG as needed. */
--- 440,446 ----
free_all_edge_infos ();
/* Thread jumps, creating duplicate blocks as needed. */
! cfg_altered |= thread_through_all_blocks ();
/* Removal of statements may make some EH edges dead. Purge
such edges from the CFG as needed. */
*************** tree_ssa_dominator_optimize (void)
*** 487,493 ****
/* Reinitialize the various tables. */
bitmap_clear (nonzero_vars);
- bitmap_clear (threaded_blocks);
htab_empty (avail_exprs);
htab_empty (vrp_data);
--- 479,484 ----
*************** tree_ssa_dominator_optimize (void)
*** 533,539 ****
/* Free nonzero_vars. */
BITMAP_FREE (nonzero_vars);
- BITMAP_FREE (threaded_blocks);
BITMAP_FREE (need_eh_cleanup);
VEC_free (tree, heap, avail_exprs_stack);
--- 524,529 ----
*************** thread_across_edge (struct dom_walk_data
*** 924,931 ****
edge_info = (struct edge_info *) e->aux;
else
edge_info = allocate_edge_info (e);
! edge_info->redirection_target = taken_edge;
! bitmap_set_bit (threaded_blocks, e->dest->index);
}
}
}
--- 914,920 ----
edge_info = (struct edge_info *) e->aux;
else
edge_info = allocate_edge_info (e);
! register_jump_thread (e, taken_edge);
}
}
}
Index: gcc/tree-flow.h
===================================================================
*** gcc/tree-flow.h (revision 109600)
--- gcc/tree-flow.h (working copy)
*************** bool multiplier_allowed_in_address_p (HO
*** 807,813 ****
unsigned multiply_by_cost (HOST_WIDE_INT, enum machine_mode);
/* In tree-ssa-threadupdate.c. */
! extern bool thread_through_all_blocks (bitmap);
/* In gimplify.c */
tree force_gimple_operand (tree, tree *, bool, tree);
--- 807,814 ----
unsigned multiply_by_cost (HOST_WIDE_INT, enum machine_mode);
/* In tree-ssa-threadupdate.c. */
! extern bool thread_through_all_blocks (void);
! extern void register_jump_thread (edge, edge);
/* In gimplify.c */
tree force_gimple_operand (tree, tree *, bool, tree);
More information about the Gcc-patches
mailing list