This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
More LCM stuff
- To: gcc-patches at gcc dot gnu dot org
- Subject: More LCM stuff
- From: Jeffrey A Law <law at cygnus dot com>
- Date: Thu, 11 Nov 1999 02:20:19 -0700
- Reply-To: law at cygnus dot com
Ho hum. Wouldn't you know that shortly after I checked in the updated lcm.c
I would find a bug ;(
The optimistic initializations to get maximal solutions for the dataflow
equations have an unpleasant interaction with lazily adding nodes to the
worklist. Basically we have to make sure to add everything to the worklist
initially, then lazily re-add nodes that need to be processed again.
[ This is a behavior I noticed in compute_laterin and should have realized
that it applied to compute_available, compute_antinout, etc), but simply
missed it. ]
I also took this opportunity to clean up gcse slightly to use the generic
compute_availability routine in a couple places. Two less routines to
convert :-)
* flow.c (compute_flow_dominators): Initially put all blocks on
the worklist.
* lcm.c (compute_antinout_edge, compute_available): Similarly.
* gcse.c (compute_cprop_avinout): Remove.
(compute_cprop_data): Use compute_available.
(delete_null_pointer_checks_1): Use compute_available.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.184
diff -c -3 -p -r1.184 flow.c
*** flow.c 1999/11/10 07:05:42 1.184
--- flow.c 1999/11/11 09:08:36
*************** compute_flow_dominators (dominators, pos
*** 5339,5362 ****
if (dominators)
{
! /* Clear the AUX field for each basic block. */
for (bb = 0; bb < n_basic_blocks; bb++)
! BASIC_BLOCK (bb)->aux = NULL;
/* We want a maximal solution, so initially assume everything dominates
everything else. */
sbitmap_vector_ones (dominators, n_basic_blocks);
! /* Put the successors of the entry block on the worklist. */
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
! {
! *tos++ = e->dest;
!
! /* We use the block's aux field to track blocks which are in
! the worklist; we also use it to quickly determine which blocks
! are successors of the ENTRY block. */
! e->dest->aux = ENTRY_BLOCK_PTR;
! }
/* Iterate until the worklist is empty. */
while (tos != worklist)
--- 5339,5359 ----
if (dominators)
{
! /* The optimistic setting of dominators requires us to put every
! block on the work list initially. */
for (bb = 0; bb < n_basic_blocks; bb++)
! {
! *tos++ = BASIC_BLOCK (bb);
! BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
! }
/* We want a maximal solution, so initially assume everything dominates
everything else. */
sbitmap_vector_ones (dominators, n_basic_blocks);
! /* Mark successors of the entry block so we can identify them below.
*/
for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
! e->dest->aux = ENTRY_BLOCK_PTR;
/* Iterate until the worklist is empty. */
while (tos != worklist)
*************** compute_flow_dominators (dominators, pos
*** 5412,5435 ****
if (post_dominators)
{
! /* Clear the AUX field for each basic block. */
for (bb = 0; bb < n_basic_blocks; bb++)
! BASIC_BLOCK (bb)->aux = NULL;
/* We want a maximal solution, so initially assume everything post
dominates everything else. */
sbitmap_vector_ones (post_dominators, n_basic_blocks);
! /* Put the predecessors of the exit block on the worklist. */
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
! {
! *tos++ = e->src;
!
! /* We use the block's aux field to track blocks which are in
! the worklist; we also use it to quickly determine which blocks
! are predecessors of the EXIT block. */
! e->src->aux = EXIT_BLOCK_PTR;
! }
/* Iterate until the worklist is empty. */
while (tos != worklist)
--- 5409,5429 ----
if (post_dominators)
{
! /* The optimistic setting of dominators requires us to put every
! block on the work list initially. */
for (bb = 0; bb < n_basic_blocks; bb++)
! {
! *tos++ = BASIC_BLOCK (bb);
! BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
! }
/* We want a maximal solution, so initially assume everything post
dominates everything else. */
sbitmap_vector_ones (post_dominators, n_basic_blocks);
! /* Mark predecessors of the exit block so we can identify them below.
*/
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
! e->src->aux = EXIT_BLOCK_PTR;
/* Iterate until the worklist is empty. */
while (tos != worklist)
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.68
diff -c -3 -p -r1.68 gcse.c
*** gcse.c 1999/11/11 06:38:15 1.68
--- gcse.c 1999/11/11 09:08:46
*************** static void compute_transp PROTO ((r
*** 581,587 ****
static void compute_transpout PROTO ((void));
static void compute_local_properties PROTO ((sbitmap *, sbitmap *,
sbitmap *, int));
- static void compute_cprop_avinout PROTO ((void));
static void compute_cprop_data PROTO ((void));
static void find_used_regs PROTO ((rtx));
static int try_replace_reg PROTO ((rtx, rtx, rtx));
--- 581,586 ----
*************** compute_transp (x, indx, bmap, set_p)
*** 3591,3630 ****
}
}
- /* Compute the available expressions at the start and end of each
- basic block for cprop. This particular dataflow equation is
- used often enough that we might want to generalize it and make
- as a subroutine for other global optimizations that need available
- in/out information. */
- static void
- compute_cprop_avinout ()
- {
- int bb, changed, passes;
-
- sbitmap_zero (cprop_avin[0]);
- sbitmap_vector_ones (cprop_avout, n_basic_blocks);
-
- passes = 0;
- changed = 1;
- while (changed)
- {
- changed = 0;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- if (bb != 0)
- sbitmap_intersection_of_preds (cprop_avin[bb], cprop_avout, bb);
- changed |= sbitmap_union_of_diff (cprop_avout[bb],
- cprop_pavloc[bb],
- cprop_avin[bb],
- cprop_absaltered[bb]);
- }
- passes++;
- }
-
- if (gcse_file)
- fprintf (gcse_file, "cprop avail expr computation: %d passes\n", passes);
- }
-
/* Top level routine to do the dataflow analysis needed by copy/const
propagation. */
--- 3590,3595 ----
*************** static void
*** 3632,3638 ****
compute_cprop_data ()
{
compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, 1);
! compute_cprop_avinout ();
}
/* Copy/constant propagation. */
--- 3597,3604 ----
compute_cprop_data ()
{
compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, 1);
! compute_available (cprop_pavloc, cprop_absaltered,
! cprop_avout, cprop_avin);
}
/* Copy/constant propagation. */
*************** delete_null_pointer_checks_1 (s_preds, b
*** 5030,5036 ****
sbitmap *nonnull_avout;
struct null_pointer_info *npi;
{
! int changed, bb;
int current_block;
sbitmap *nonnull_local = npi->nonnull_local;
sbitmap *nonnull_killed = npi->nonnull_killed;
--- 4996,5002 ----
sbitmap *nonnull_avout;
struct null_pointer_info *npi;
{
! int bb;
int current_block;
sbitmap *nonnull_local = npi->nonnull_local;
sbitmap *nonnull_killed = npi->nonnull_killed;
*************** delete_null_pointer_checks_1 (s_preds, b
*** 5103,5127 ****
/* Now compute global properties based on the local properties. This
is a classic global availablity algorithm. */
! sbitmap_zero (nonnull_avin[0]);
! sbitmap_vector_ones (nonnull_avout, n_basic_blocks);
! changed = 1;
! while (changed)
! {
! changed = 0;
!
! for (bb = 0; bb < n_basic_blocks; bb++)
! {
! if (bb != 0)
! sbitmap_intersect_of_predecessors (nonnull_avin[bb],
! nonnull_avout, bb, s_preds);
!
! changed |= sbitmap_union_of_diff (nonnull_avout[bb],
! nonnull_local[bb],
! nonnull_avin[bb],
! nonnull_killed[bb]);
! }
! }
/* Now look at each bb and see if it ends with a compare of a value
against zero. */
--- 5069,5076 ----
/* Now compute global properties based on the local properties. This
is a classic global availablity algorithm. */
! compute_available (nonnull_local, nonnull_killed,
! nonnull_avout, nonnull_avin);
/* Now look at each bb and see if it ends with a compare of a value
against zero. */
Index: lcm.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/lcm.c,v
retrieving revision 1.5
diff -c -3 -p -r1.5 lcm.c
*** lcm.c 1999/11/11 06:38:15 1.5
--- lcm.c 1999/11/11 09:12:44
*************** compute_antinout_edge (antloc, transp, a
*** 112,128 ****
ANTIN. */
sbitmap_vector_ones (antin, n_basic_blocks);
! /* Put the predecessors of the exit block on the worklist. */
! for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
{
! *tos++ = e->src;
!
! /* We use the block's aux field to track blocks which are in
! the worklist; we also use it to quickly determine which blocks
! are predecessors of the EXIT block. */
! e->src->aux = EXIT_BLOCK_PTR;
}
/* Iterate until the worklist is empty. */
while (tos != worklist)
{
--- 112,130 ----
ANTIN. */
sbitmap_vector_ones (antin, n_basic_blocks);
! /* Put every block on the worklist; this is necessary because of the
! optimistic initialization of ANTIN above. */
! for (bb = 0; bb < n_basic_blocks; bb++)
{
! *tos++ = BASIC_BLOCK (bb);
! BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ /* Mark blocks which are predecessors of the exit block so that we
+ can easily identify them below. */
+ for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ e->src->aux = EXIT_BLOCK_PTR;
+
/* Iterate until the worklist is empty. */
while (tos != worklist)
{
*************** compute_available (avloc, kill, avout, a
*** 467,482 ****
/* We want a maximal solution. */
sbitmap_vector_ones (avout, n_basic_blocks);
! /* Put the successors of the entry block on the worklist. */
! for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
{
! *tos++ = e->dest;
!
! /* We use the block's aux field to track blocks which are in
! the worklist; we also use it to quickly determine which blocks
! are successors of the ENTRY block. */
! e->dest->aux = ENTRY_BLOCK_PTR;
}
/* Iterate until the worklist is empty. */
while (tos != worklist)
--- 469,486 ----
/* We want a maximal solution. */
sbitmap_vector_ones (avout, n_basic_blocks);
! /* Put every block on the worklist; this is necessary because of the
! optimistic initialization of AVOUT above. */
! for (bb = n_basic_blocks - 1; bb >= 0; bb--)
{
! *tos++ = BASIC_BLOCK (bb);
! BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+
+ /* Mark blocks which are successors of the entry block so that we
+ can easily identify them below. */
+ for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ e->dest->aux = ENTRY_BLOCK_PTR;
/* Iterate until the worklist is empty. */
while (tos != worklist)