Enabling LCM
Jeffrey A Law
law@upchuck.cygnus.com
Sun Mar 21 20:48:00 GMT 1999
Here's the patches to enable the use of the lazy code motion routines for
global cse/partial redundancy elimination.
For the most part they remove routines which computed global properties
for the old partial redundancy algorithm and replace them with a call
to pre_lcm.
In addition some cleanups have been made to help generalize the code
somewhat. For example, many of the routines left in gcse.c to implement
partial redundancy elimination can also be used by a global code hoising
optimizer. So the "pre" prefix for such routines/variables has been removed.
There's been a couple reports of problems due to the gcse.c changes from
earlier. The gcse.c code should be solidifying, so if these problems are
still occurring, then we need to start tracking them down.
* gcse.c (dump_hash_table): Fix whitespace in declaration.
(compute_transpout): Renamed from pre_compute_transpout.
(compute_pre_*): Deleted
(pre_expr_reaches_here_p): New argument, CHECK_PRE_COMP. All
callers changed.
(insert_insn_end_bb): Renamed from pre_insert_insn.
(pre_*): Delete unused variables. Only leave local properties and
global redundant/optimal computation points.
(alloc_pre_mem, free_pre_mem): Corresponding changes.
(compute_pre_data): Simplify and call pre_lcm to run the lazy
code motion dataflow analysis.
(pre_insert, pre_insert_copies, pre_delete): Revamp to use LCM
based redundant and optimal computation points.
Index: gcse.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcse.c,v
retrieving revision 1.33
diff -c -3 -p -r1.33 gcse.c
*** gcse.c 1999/03/10 21:36:35 1.33
--- gcse.c 1999/03/22 03:00:37
*************** static void compute_set_hash_table PR
*** 550,556 ****
static void alloc_expr_hash_table PROTO ((int));
static void free_expr_hash_table PROTO ((void));
static void compute_expr_hash_table PROTO ((void));
! static void dump_hash_table PROTO ((FILE *, const char *, struct expr **, int, int));
static struct expr *lookup_expr PROTO ((rtx));
static struct expr *lookup_set PROTO ((int, rtx));
static struct expr *next_set PROTO ((int, struct expr *));
--- 550,557 ----
static void alloc_expr_hash_table PROTO ((int));
static void free_expr_hash_table PROTO ((void));
static void compute_expr_hash_table PROTO ((void));
! static void dump_hash_table PROTO ((FILE *, const char *, struct expr **,
! int, int));
static struct expr *lookup_expr PROTO ((rtx));
static struct expr *lookup_set PROTO ((int, rtx));
static struct expr *next_set PROTO ((int, struct expr *));
*************** static void mark_oprs_set PROTO ((r
*** 564,569 ****
--- 565,571 ----
static void alloc_cprop_mem PROTO ((int, int));
static void free_cprop_mem PROTO ((void));
static void compute_transp PROTO ((rtx, int, sbitmap *, int));
+ static void compute_transpout PROTO ((void));
static void compute_local_properties PROTO ((sbitmap *, sbitmap *,
sbitmap *, int));
static void compute_cprop_avinout PROTO ((void));
*************** static int one_cprop_pass PROTO ((i
*** 577,590 ****
static void alloc_pre_mem PROTO ((int, int));
static void free_pre_mem PROTO ((void));
- static void compute_pre_avinout PROTO ((void));
- static void compute_pre_antinout PROTO ((void));
- static void compute_pre_pavinout PROTO ((void));
- static void compute_pre_ppinout PROTO ((void));
static void compute_pre_data PROTO ((void));
! static int pre_expr_reaches_here_p PROTO ((struct occr *, struct expr *,
! int, char *));
! static void pre_insert_insn PROTO ((struct expr *, int));
static void pre_insert PROTO ((struct expr **));
static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
static void pre_insert_copies PROTO ((void));
--- 579,588 ----
static void alloc_pre_mem PROTO ((int, int));
static void free_pre_mem PROTO ((void));
static void compute_pre_data PROTO ((void));
! static int pre_expr_reaches_here_p PROTO ((int, struct expr *,
! int, int, char *));
! static void insert_insn_end_bb PROTO ((struct expr *, int, int));
static void pre_insert PROTO ((struct expr **));
static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
static void pre_insert_copies PROTO ((void));
*************** one_cprop_pass (pass, alter_jumps)
*** 3924,4262 ****
return changed;
}
! /* Compute PRE working variables. */
/* Local properties of expressions. */
/* Nonzero for expressions that are transparent in the block. */
! static sbitmap *pre_transp;
! /* Nonzero for expressions that are computed (available) in the block. */
! static sbitmap *pre_comp;
! /* Nonzero for expressions that are locally anticipatable in the block. */
! static sbitmap *pre_antloc;
- /* Global properties (computed from the expression local properties). */
- /* Nonzero for expressions that are available on block entry/exit. */
- static sbitmap *pre_avin;
- static sbitmap *pre_avout;
- /* Nonzero for expressions that are anticipatable on block entry/exit. */
- static sbitmap *pre_antin;
- static sbitmap *pre_antout;
- /* Nonzero for expressions that are partially available on block entry/exit. */
- static sbitmap *pre_pavin;
- static sbitmap *pre_pavout;
- /* Nonzero for expressions that are "placement possible" on block entry/exit. */
- static sbitmap *pre_ppin;
- static sbitmap *pre_ppout;
-
/* Nonzero for expressions that are transparent at the end of the block.
This is only zero for expressions killed by abnormal critical edge
created by a calls. */
! static sbitmap *pre_transpout;
!
! /* Used while performing PRE to denote which insns are redundant. */
! static sbitmap pre_redundant;
!
! /* Allocate vars used for PRE analysis. */
!
! static void
! alloc_pre_mem (n_blocks, n_exprs)
! int n_blocks, n_exprs;
! {
! pre_transp = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_comp = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
!
! pre_avin = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_avout = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_antin = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_antout = sbitmap_vector_alloc (n_blocks, n_exprs);
!
! pre_pavin = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_pavout = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_ppin = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_ppout = sbitmap_vector_alloc (n_blocks, n_exprs);
!
! pre_transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
! }
! /* Free vars used for PRE analysis. */
! static void
! free_pre_mem ()
! {
! free (pre_transp);
! free (pre_comp);
! free (pre_antloc);
! free (pre_avin);
! free (pre_avout);
! free (pre_antin);
! free (pre_antout);
! free (pre_pavin);
! free (pre_pavout);
! free (pre_ppin);
! free (pre_ppout);
! free (pre_transpout);
! }
! /* Compute expression availability at entrance and exit of each block. */
! static void
! compute_pre_avinout ()
! {
! int bb, changed, passes;
! sbitmap_zero (pre_avin[0]);
! sbitmap_vector_ones (pre_avout, n_basic_blocks);
! passes = 0;
! changed = 1;
! while (changed)
! {
! changed = 0;
! for (bb = 0; bb < n_basic_blocks; bb++)
! {
! if (bb != 0)
! sbitmap_intersect_of_predecessors (pre_avin[bb], pre_avout,
! bb, s_preds);
! changed |= sbitmap_a_or_b_and_c (pre_avout[bb], pre_comp[bb],
! pre_transp[bb], pre_avin[bb]);
! }
! passes++;
! }
!
! if (gcse_file)
! fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
! }
!
! /* Compute expression anticipatability at entrance and exit of each block. */
static void
! compute_pre_antinout ()
{
! int bb, changed, passes;
!
! sbitmap_zero (pre_antout[n_basic_blocks - 1]);
! sbitmap_vector_ones (pre_antin, n_basic_blocks);
!
! passes = 0;
! changed = 1;
! while (changed)
! {
! changed = 0;
! /* We scan the blocks in the reverse order to speed up
! the convergence. */
! for (bb = n_basic_blocks - 1; bb >= 0; bb--)
! {
! if (bb != n_basic_blocks - 1)
! sbitmap_intersect_of_successors (pre_antout[bb], pre_antin,
! bb, s_succs);
! changed |= sbitmap_a_or_b_and_c (pre_antin[bb], pre_antloc[bb],
! pre_transp[bb], pre_antout[bb]);
! }
! passes++;
! }
!
! if (gcse_file)
! fprintf (gcse_file, "antic expr computation: %d passes\n", passes);
}
-
- /* Compute expression partial availability at entrance and exit of
- each block. */
-
- static void
- compute_pre_pavinout ()
- {
- int bb, changed, passes;
! sbitmap_zero (pre_pavin[0]);
! sbitmap_vector_zero (pre_pavout, n_basic_blocks);
!
! passes = 0;
! changed = 1;
! while (changed)
! {
! changed = 0;
! for (bb = 0; bb < n_basic_blocks; bb++)
! {
! if (bb != 0)
! sbitmap_union_of_predecessors (pre_pavin[bb], pre_pavout,
! bb, s_preds);
! changed |= sbitmap_a_or_b_and_c (pre_pavout[bb], pre_comp[bb],
! pre_transp[bb], pre_pavin[bb]);
! }
! passes++;
! }
!
! if (gcse_file)
! fprintf (gcse_file, "partially avail expr computation: %d passes\n", passes);
! }
!
! /* Compute transparent outgoing information for each block.
!
! An expression is transparent to an edge unless it is killed by
! the edge itself. This can only happen with abnormal control flow,
! when the edge is traversed through a call. This happens with
! non-local labels and exceptions.
!
! This would not be necessary if we split the edge. While this is
! normally impossible for abnormal critical edges, with some effort
! it should be possible with exception handling, since we still have
! control over which handler should be invoked. But due to increased
! EH table sizes, this may not be worthwhile. */
!
! static void
! compute_pre_transpout ()
! {
! int bb;
!
! sbitmap_vector_ones (pre_transpout, n_basic_blocks);
!
! for (bb = 0; bb < n_basic_blocks; ++bb)
! {
! int i;
!
! /* Note that flow inserted a nop a the end of basic blocks that
! end in call instructions for reasons other than abnormal
! control flow. */
! if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
! continue;
!
! for (i = 0; i < expr_hash_table_size; i++)
! {
! struct expr *expr;
! for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
! if (GET_CODE (expr->expr) == MEM)
! {
! rtx addr = XEXP (expr->expr, 0);
!
! if (GET_CODE (addr) == SYMBOL_REF
! && CONSTANT_POOL_ADDRESS_P (addr))
! continue;
!
! /* ??? Optimally, we would use interprocedural alias
! analysis to determine if this mem is actually killed
! by this call. */
! RESET_BIT (pre_transpout[bb], expr->bitmap_index);
! }
! }
! }
! }
!
! /* Compute "placement possible" information on entrance and exit of
! each block.
!
! From Fred Chow's Thesis:
! A computation `e' is PP at a point `p' if it is anticipated at `p' and
! all the anticipated e's can be rendered redundant by zero or more
! insertions at that point and some other points in the procedure, and
! these insertions satisfy the conditions that the insertions are always
! at points that `e' is anticipated and the first anticipated e's after the
! insertions are rendered redundant. */
static void
! compute_pre_ppinout ()
{
! int bb, i, changed, size, passes;
!
! sbitmap_vector_ones (pre_ppin, n_basic_blocks);
! /* ??? Inefficient as we set pre_ppin[0] twice, but simple. */
! sbitmap_zero (pre_ppin[0]);
!
! sbitmap_vector_ones (pre_ppout, n_basic_blocks);
! /* ??? Inefficient as we set pre_ppout[n_basic_blocks-1] twice, but simple. */
! sbitmap_zero (pre_ppout[n_basic_blocks - 1]);
!
! size = pre_ppin[0]->size;
! passes = 0;
! changed = 1;
! while (changed)
! {
! changed = 0;
! for (bb = 1; bb < n_basic_blocks; bb++)
! {
! sbitmap_ptr antin = pre_antin[bb]->elms;
! sbitmap_ptr pavin = pre_pavin[bb]->elms;
! sbitmap_ptr antloc = pre_antloc[bb]->elms;
! sbitmap_ptr transp = pre_transp[bb]->elms;
! sbitmap_ptr ppout = pre_ppout[bb]->elms;
! sbitmap_ptr ppin = pre_ppin[bb]->elms;
! for (i = 0; i < size; i++)
! {
! int_list_ptr pred;
! SBITMAP_ELT_TYPE tmp = *antin & *pavin & (*antloc | (*transp & *ppout));
! SBITMAP_ELT_TYPE pred_val = (SBITMAP_ELT_TYPE) -1;
!
! for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
! {
! int pred_bb = INT_LIST_VAL (pred);
! sbitmap_ptr ppout_j,avout_j;
!
! if (pred_bb == ENTRY_BLOCK)
! continue;
!
! /* If this is a back edge, propagate info along the back
! edge to allow for loop invariant code motion.
!
! See FOLLOW_BACK_EDGES at the top of this file for a longer
! discussion about loop invariant code motion in pre. */
! if (! FOLLOW_BACK_EDGES
! && (INSN_CUID (BLOCK_HEAD (bb))
! < INSN_CUID (BLOCK_END (pred_bb))))
! {
! pred_val = 0;
! }
! else
! {
! ppout_j = pre_ppout[pred_bb]->elms + i;
! avout_j = pre_avout[pred_bb]->elms + i;
! pred_val &= *ppout_j | *avout_j;
! }
! }
! tmp &= pred_val;
! *ppin = tmp;
! antin++; pavin++; antloc++; transp++; ppout++; ppin++;
! }
! }
!
! for (bb = 0; bb < n_basic_blocks - 1; bb++)
! {
! sbitmap_ptr ppout = pre_ppout[bb]->elms;
! sbitmap_ptr transpout = pre_transpout[bb]->elms;
!
! for (i = 0; i < size; i++)
! {
! int_list_ptr succ;
! SBITMAP_ELT_TYPE tmp = *transpout;
!
! for (succ = s_succs[bb]; succ != NULL; succ = succ->next)
! {
! int succ_bb = INT_LIST_VAL (succ);
! sbitmap_ptr ppin;
!
! if (succ_bb == EXIT_BLOCK)
! continue;
!
! ppin = pre_ppin[succ_bb]->elms + i;
! tmp &= *ppin;
! }
!
! if (*ppout != tmp)
! {
! changed = 1;
! *ppout = tmp;
! }
!
! ppout++; transpout++;
! }
! }
!
! passes++;
! }
!
! if (gcse_file)
! fprintf (gcse_file, "placement possible computation: %d passes\n", passes);
}
/* Top level routine to do the dataflow analysis needed by PRE. */
--- 3922,3984 ----
return changed;
}
! /* Compute PRE+LCM working variables. */
/* Local properties of expressions. */
/* Nonzero for expressions that are transparent in the block. */
! static sbitmap *transp;
/* Nonzero for expressions that are transparent at the end of the block.
This is only zero for expressions killed by abnormal critical edge
created by a calls. */
! static sbitmap *transpout;
! /* Nonzero for expressions that are computed (available) in the block. */
! static sbitmap *comp;
! /* Nonzero for expressions that are locally anticipatable in the block. */
! static sbitmap *antloc;
! /* Nonzero for expressions where this block is an optimal computation
! point. */
! static sbitmap *pre_optimal;
! /* Nonzero for expressions which are redundant in a particular block. */
! static sbitmap *pre_redundant;
! static sbitmap *temp_bitmap;
! /* Redundant insns. */
! static sbitmap pre_redundant_insns;
! /* Allocate vars used for PRE analysis. */
static void
! alloc_pre_mem (n_blocks, n_exprs)
! int n_blocks, n_exprs;
{
! transp = sbitmap_vector_alloc (n_blocks, n_exprs);
! comp = sbitmap_vector_alloc (n_blocks, n_exprs);
! antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
!
! temp_bitmap = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_optimal = sbitmap_vector_alloc (n_blocks, n_exprs);
! pre_redundant = sbitmap_vector_alloc (n_blocks, n_exprs);
! transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
}
! /* Free vars used for PRE analysis. */
static void
! free_pre_mem ()
{
! free (transp);
! free (comp);
! free (antloc);
! free (pre_optimal);
! free (pre_redundant);
! free (transpout);
}
/* Top level routine to do the dataflow analysis needed by PRE. */
*************** compute_pre_ppinout ()
*** 4264,4286 ****
static void
compute_pre_data ()
{
! compute_local_properties (pre_transp, pre_comp, pre_antloc, 0);
! compute_pre_avinout ();
! compute_pre_antinout ();
! compute_pre_pavinout ();
! compute_pre_transpout ();
! compute_pre_ppinout ();
! if (gcse_file)
! fprintf (gcse_file, "\n");
}
/* PRE utilities */
! /* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
VISITED is a pointer to a working buffer for tracking which BB's have
been visited. It is NULL for the top-level call.
We treat reaching expressions that go through blocks containing the same
reaching expression as "not reaching". E.g. if EXPR is generated in blocks
2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
--- 3986,4009 ----
static void
compute_pre_data ()
{
! compute_local_properties (transp, comp, antloc, 0);
! compute_transpout ();
! pre_lcm (n_basic_blocks, n_exprs, s_preds, s_succs, transp,
! antloc, pre_redundant, pre_optimal);
}
+
/* PRE utilities */
! /* Return non-zero if an occurrence of expression EXPR in OCCR_BB would reach
! block BB.
VISITED is a pointer to a working buffer for tracking which BB's have
been visited. It is NULL for the top-level call.
+ CHECK_PRE_COMP controls whether or not we check for a computation of
+ EXPR in OCCR_BB.
+
We treat reaching expressions that go through blocks containing the same
reaching expression as "not reaching". E.g. if EXPR is generated in blocks
2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
*************** compute_pre_data ()
*** 4289,4298 ****
the closest such expression. */
static int
! pre_expr_reaches_here_p (occr, expr, bb, visited)
! struct occr *occr;
struct expr *expr;
int bb;
char *visited;
{
int_list_ptr pred;
--- 4012,4022 ----
the closest such expression. */
static int
! pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited)
! int occr_bb;
struct expr *expr;
int bb;
+ int check_pre_comp;
char *visited;
{
int_list_ptr pred;
*************** pre_expr_reaches_here_p (occr, expr, bb,
*** 4314,4336 ****
/* Nothing to do. */
}
/* Does this predecessor generate this expression? */
! else if (TEST_BIT (pre_comp[pred_bb], expr->bitmap_index))
{
/* Is this the occurrence we're looking for?
Note that there's only one generating occurrence per block
so we just need to check the block number. */
! if (BLOCK_NUM (occr->insn) == pred_bb)
return 1;
visited[pred_bb] = 1;
}
/* Ignore this predecessor if it kills the expression. */
! else if (! TEST_BIT (pre_transp[pred_bb], expr->bitmap_index))
visited[pred_bb] = 1;
/* Neither gen nor kill. */
else
{
visited[pred_bb] = 1;
! if (pre_expr_reaches_here_p (occr, expr, pred_bb, visited))
return 1;
}
}
--- 4038,4062 ----
/* Nothing to do. */
}
/* Does this predecessor generate this expression? */
! else if ((!check_pre_comp && occr_bb == pred_bb)
! || TEST_BIT (comp[pred_bb], expr->bitmap_index))
{
/* Is this the occurrence we're looking for?
Note that there's only one generating occurrence per block
so we just need to check the block number. */
! if (occr_bb == pred_bb)
return 1;
visited[pred_bb] = 1;
}
/* Ignore this predecessor if it kills the expression. */
! else if (! TEST_BIT (transp[pred_bb], expr->bitmap_index))
visited[pred_bb] = 1;
/* Neither gen nor kill. */
else
{
visited[pred_bb] = 1;
! if (pre_expr_reaches_here_p (occr_bb, expr, pred_bb,
! check_pre_comp, visited))
return 1;
}
}
*************** pre_expr_reaches_here_p (occr, expr, bb,
*** 4339,4358 ****
return 0;
}
! /* Add EXPR to the end of basic block BB. */
static void
! pre_insert_insn (expr, bb)
struct expr *expr;
int bb;
{
rtx insn = BLOCK_END (bb);
rtx new_insn;
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
! rtx pat;
! pat = gen_rtx_SET (VOIDmode, reg, copy_rtx (expr->expr));
/* If the last insn is a jump, insert EXPR in front [taking care to
handle cc0, etc. properly]. */
--- 4065,4097 ----
return 0;
}
! /* Add EXPR to the end of basic block BB.
!
! This is used by both the PRE and code hoisting.
+ For PRE, we want to verify that the expr is either transparent
+ or locally anticipatable in the target block. This check makes
+ no sense for code hoisting. */
+
static void
! insert_insn_end_bb (expr, bb, pre)
struct expr *expr;
int bb;
+ int pre;
{
rtx insn = BLOCK_END (bb);
rtx new_insn;
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
! rtx pat, copied_expr;
! rtx first_new_insn;
! start_sequence ();
! copied_expr = copy_rtx (expr->expr);
! emit_move_insn (reg, copied_expr);
! first_new_insn = get_insns ();
! pat = gen_sequence ();
! end_sequence ();
/* If the last insn is a jump, insert EXPR in front [taking care to
handle cc0, etc. properly]. */
*************** pre_insert_insn (expr, bb)
*** 4387,4393 ****
#endif
/* FIXME: What if something in cc0/jump uses value set in new insn? */
new_insn = emit_insn_before (pat, insn);
- add_label_notes (SET_SRC (pat), new_insn);
if (BLOCK_HEAD (bb) == insn)
BLOCK_HEAD (bb) = new_insn;
}
--- 4126,4131 ----
*************** pre_insert_insn (expr, bb)
*** 4405,4415 ****
presumtion that we'll get better code elsewhere as well. */
/* It should always be the case that we can put these instructions
! anywhere in the basic block. Check this. */
! /* ??? Well, it would be the case if we'd split all critical edges.
! Since we didn't, we may very well abort. */
! if (!TEST_BIT (pre_antloc[bb], expr->bitmap_index)
! && !TEST_BIT (pre_transp[bb], expr->bitmap_index))
abort ();
/* Since different machines initialize their parameter registers
--- 4143,4153 ----
presumtion that we'll get better code elsewhere as well. */
/* It should always be the case that we can put these instructions
! anywhere in the basic block with performing PRE optimizations.
! Check this. */
! if (pre
! && !TEST_BIT (antloc[bb], expr->bitmap_index)
! && !TEST_BIT (transp[bb], expr->bitmap_index))
abort ();
/* Since different machines initialize their parameter registers
*************** pre_insert_insn (expr, bb)
*** 4449,4510 ****
else
{
new_insn = emit_insn_after (pat, insn);
- add_label_notes (SET_SRC (pat), new_insn);
BLOCK_END (bb) = new_insn;
}
! /* Keep block number table up to date. */
! set_block_num (new_insn, bb);
! /* Keep register set table up to date. */
! record_one_set (regno, new_insn);
gcse_create_count++;
if (gcse_file)
{
! fprintf (gcse_file, "PRE: end of bb %d, insn %d, copying expression %d to reg %d\n",
bb, INSN_UID (new_insn), expr->bitmap_index, regno);
}
}
/* Insert partially redundant expressions at the ends of appropriate basic
! blocks making them now redundant. */
static void
pre_insert (index_map)
struct expr **index_map;
{
! int bb, i, size;
! /* Compute INSERT = PPOUT & (~AVOUT) & (~PPIN | ~TRANSP) for each
! expression. Where INSERT == TRUE, add the expression at the end of
! the basic block. */
- size = pre_ppout[0]->size;
for (bb = 0; bb < n_basic_blocks; bb++)
{
int indx;
! sbitmap_ptr ppout = pre_ppout[bb]->elms;
! sbitmap_ptr avout = pre_avout[bb]->elms;
! sbitmap_ptr ppin = pre_ppin[bb]->elms;
! sbitmap_ptr transp = pre_transp[bb]->elms;
!
! for (i = indx = 0;
! i < size;
! i++, indx += SBITMAP_ELT_BITS, ppout++, avout++, ppin++, transp++)
{
int j;
- SBITMAP_ELT_TYPE insert = *ppout & (~*avout) & (~*ppin | ~*transp);
! for (j = indx; insert != 0 && j < n_exprs; j++, insert >>= 1)
{
! if ((insert & 1) != 0
! /* If the basic block isn't reachable, PPOUT will be TRUE.
! However, we don't want to insert a copy here because the
! expression may not really be redundant. So only insert
! an insn if the expression was deleted. */
! && index_map[j]->reaching_reg != NULL)
! pre_insert_insn (index_map[j], bb);
}
}
}
--- 4187,4287 ----
else
{
new_insn = emit_insn_after (pat, insn);
BLOCK_END (bb) = new_insn;
}
! /* Keep block number table up to date.
! Note, PAT could be a multiple insn sequence, we have to make
! sure that each insn in the sequence is handled. */
! if (GET_CODE (pat) == SEQUENCE)
! {
! int i;
!
! for (i = 0; i < XVECLEN (pat, 0); i++)
! {
! rtx insn = XVECEXP (pat, 0, i);
! set_block_num (insn, bb);
! if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
! add_label_notes (PATTERN (insn), new_insn);
! record_set_insn = insn;
! note_stores (PATTERN (insn), record_set_info);
! }
! }
! else
! {
! add_label_notes (SET_SRC (pat), new_insn);
! set_block_num (new_insn, bb);
! /* Keep register set table up to date. */
! record_one_set (regno, new_insn);
! }
gcse_create_count++;
if (gcse_file)
{
! fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, copying expression %d to reg %d\n",
bb, INSN_UID (new_insn), expr->bitmap_index, regno);
}
}
/* Insert partially redundant expressions at the ends of appropriate basic
! blocks making them fully redundant. */
static void
pre_insert (index_map)
struct expr **index_map;
{
! int bb, i, set_size;
! sbitmap *inserted;
! /* Compute INSERT = PRE_OPTIMAL & ~PRE_REDUNDANT.
! Where INSERT is nonzero, we add the expression at the end of the basic
! block if it reaches any of the deleted expressions. */
!
! set_size = pre_optimal[0]->size;
! inserted = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
! sbitmap_vector_zero (inserted, n_basic_blocks);
for (bb = 0; bb < n_basic_blocks; bb++)
{
int indx;
!
! /* This computes the number of potential insertions we need. */
! sbitmap_not (temp_bitmap[bb], pre_redundant[bb]);
! sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_optimal[bb]);
!
! /* TEMP_BITMAP[bb] now contains a bitmap of the expressions that we need
! to insert at the end of this basic block. */
! for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
{
+ SBITMAP_ELT_TYPE insert = temp_bitmap[bb]->elms[i];
int j;
! for (j = indx; insert && j < n_exprs; j++, insert >>= 1)
{
! if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
! {
! struct expr *expr = index_map[j];
! struct occr *occr;
!
! /* Now look at each deleted occurence of this expression. */
! for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
! {
! if (! occr->deleted_p)
! continue;
!
! /* Insert this expression at the end of BB if it would
! reach the deleted occurence. */
! if (!TEST_BIT (inserted[bb], j)
! && pre_expr_reaches_here_p (bb, expr,
! BLOCK_NUM (occr->insn), 0,
! NULL))
! {
! SET_BIT (inserted[bb], j);
! insert_insn_end_bb (index_map[j], bb, 1);
! }
! }
! }
}
}
}
*************** pre_insert_copy_insn (expr, insn)
*** 4548,4555 ****
static void
pre_insert_copies ()
{
! int i;
/* For each available expression in the table, copy the result to
`reaching_reg' if the expression reaches a deleted one.
--- 4325,4337 ----
static void
pre_insert_copies ()
{
! int i, bb;
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ sbitmap_a_and_b (temp_bitmap[bb], pre_optimal[bb], pre_redundant[bb]);
+ }
+
/* For each available expression in the table, copy the result to
`reaching_reg' if the expression reaches a deleted one.
*************** pre_insert_copies ()
*** 4583,4599 ****
for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
{
rtx insn = avail->insn;
/* No need to handle this one if handled already. */
if (avail->copied_p)
continue;
/* Don't handle this one if it's a redundant one. */
! if (TEST_BIT (pre_redundant, INSN_CUID (insn)))
continue;
/* Or if the expression doesn't reach the deleted one. */
! if (! pre_expr_reaches_here_p (avail, expr,
BLOCK_NUM (occr->insn),
! NULL))
continue;
/* Copy the result of avail to reaching_reg. */
--- 4365,4385 ----
for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
{
rtx insn = avail->insn;
+ int bb = BLOCK_NUM (insn);
+
+ if (!TEST_BIT (temp_bitmap[bb], expr->bitmap_index))
+ continue;
/* No need to handle this one if handled already. */
if (avail->copied_p)
continue;
/* Don't handle this one if it's a redundant one. */
! if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
continue;
/* Or if the expression doesn't reach the deleted one. */
! if (! pre_expr_reaches_here_p (BLOCK_NUM (avail->insn), expr,
BLOCK_NUM (occr->insn),
! 1, NULL))
continue;
/* Copy the result of avail to reaching_reg. */
*************** pre_insert_copies ()
*** 4606,4612 ****
}
/* Delete redundant computations.
- These are ones that satisy ANTLOC & PPIN.
Deletion is done by changing the insn to copy the `reaching_reg' of
the expression into the result of the SET. It is left to later passes
(cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
--- 4392,4397 ----
*************** pre_insert_copies ()
*** 4616,4622 ****
static int
pre_delete ()
{
! int i, changed;
changed = 0;
for (i = 0; i < expr_hash_table_size; i++)
--- 4401,4415 ----
static int
pre_delete ()
{
! int i, bb, changed;
!
! /* Compute the expressions which are redundant and need to be replaced by
! copies from the reaching reg to the target reg. */
! for (bb = 0; bb < n_basic_blocks; bb++)
! {
! sbitmap_not (temp_bitmap[bb], pre_optimal[bb]);
! sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_redundant[bb]);
! }
changed = 0;
for (i = 0; i < expr_hash_table_size; i++)
*************** pre_delete ()
*** 4636,4644 ****
rtx insn = occr->insn;
rtx set;
int bb = BLOCK_NUM (insn);
- sbitmap ppin = pre_ppin[bb];
! if (TEST_BIT (ppin, indx))
{
set = single_set (insn);
if (! set)
--- 4429,4436 ----
rtx insn = occr->insn;
rtx set;
int bb = BLOCK_NUM (insn);
! if (TEST_BIT (temp_bitmap[bb], indx))
{
set = single_set (insn);
if (! set)
*************** pre_delete ()
*** 4662,4675 ****
expr->reaching_reg, 0))
{
occr->deleted_p = 1;
! SET_BIT (pre_redundant, INSN_CUID (insn));
changed = 1;
gcse_subst_count++;
}
if (gcse_file)
{
! fprintf (gcse_file, "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n",
INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg));
}
}
--- 4454,4468 ----
expr->reaching_reg, 0))
{
occr->deleted_p = 1;
! SET_BIT (pre_redundant_insns, INSN_CUID (insn));
changed = 1;
gcse_subst_count++;
}
if (gcse_file)
{
! fprintf (gcse_file,
! "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n",
INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg));
}
}
*************** pre_delete ()
*** 4683,4693 ****
/* Perform GCSE optimizations using PRE.
This is called by one_pre_gcse_pass after all the dataflow analysis
has been done.
-
- This is based on the original Morel-Renvoise paper and Fred Chow's thesis.
! The M-R paper uses "TRANSP" to describe an expression as being transparent
! in a block where as Chow's thesis uses "ALTERED". We use TRANSP.
??? A new pseudo reg is created to hold the reaching expression.
The nice thing about the classical approach is that it would try to
--- 4476,4485 ----
/* Perform GCSE optimizations using PRE.
This is called by one_pre_gcse_pass after all the dataflow analysis
has been done.
! This is based on the original Morel-Renvoise paper Fred Chow's thesis,
! and lazy code motion from Knoop, Ruthing and Steffen as described in
! Advanced Compiler Design and Implementation.
??? A new pseudo reg is created to hold the reaching expression.
The nice thing about the classical approach is that it would try to
*************** pre_gcse ()
*** 4722,4729 ****
}
/* Reset bitmap used to track which insns are redundant. */
! pre_redundant = sbitmap_alloc (max_cuid);
! sbitmap_zero (pre_redundant);
/* Delete the redundant insns first so that
- we know what register to use for the new insns and for the other
--- 4514,4521 ----
}
/* Reset bitmap used to track which insns are redundant. */
! pre_redundant_insns = sbitmap_alloc (max_cuid);
! sbitmap_zero (pre_redundant_insns);
/* Delete the redundant insns first so that
- we know what register to use for the new insns and for the other
*************** pre_gcse ()
*** 4739,4745 ****
specially allocated pseudo-reg that reaches the redundant expression. */
pre_insert_copies ();
! free (pre_redundant);
return changed;
}
--- 4531,4537 ----
specially allocated pseudo-reg that reaches the redundant expression. */
pre_insert_copies ();
! free (pre_redundant_insns);
return changed;
}
*************** add_label_notes (x, insn)
*** 4822,4826 ****
--- 4614,4669 ----
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
add_label_notes (XVECEXP (x, i, j), insn);
+ }
+ }
+
+ /* Compute transparent outgoing information for each block.
+
+ An expression is transparent to an edge unless it is killed by
+ the edge itself. This can only happen with abnormal control flow,
+ when the edge is traversed through a call. This happens with
+ non-local labels and exceptions.
+
+ This would not be necessary if we split the edge. While this is
+ normally impossible for abnormal critical edges, with some effort
+ it should be possible with exception handling, since we still have
+ control over which handler should be invoked. But due to increased
+ EH table sizes, this may not be worthwhile. */
+
+ static void
+ compute_transpout ()
+ {
+ int bb;
+
+ sbitmap_vector_ones (transpout, n_basic_blocks);
+
+ for (bb = 0; bb < n_basic_blocks; ++bb)
+ {
+ int i;
+
+ /* Note that flow inserted a nop a the end of basic blocks that
+ end in call instructions for reasons other than abnormal
+ control flow. */
+ if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
+ continue;
+
+ for (i = 0; i < expr_hash_table_size; i++)
+ {
+ struct expr *expr;
+ for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
+ if (GET_CODE (expr->expr) == MEM)
+ {
+ rtx addr = XEXP (expr->expr, 0);
+
+ if (GET_CODE (addr) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (addr))
+ continue;
+
+ /* ??? Optimally, we would use interprocedural alias
+ analysis to determine if this mem is actually killed
+ by this call. */
+ RESET_BIT (transpout[bb], expr->bitmap_index);
+ }
+ }
}
}
More information about the Gcc-patches
mailing list