This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Minor gcse/lcm cleanups
- To: gcc-patches at gcc dot gnu dot org
- Subject: Minor gcse/lcm cleanups
- From: Jeffrey A Law <law at cygnus dot com>
- Date: Sun, 14 Nov 1999 23:11:27 -0700
- Reply-To: law at cygnus dot com
Andrew and I have been speculating (privately) that some or all of the
calls to pre_expr_reaches_here_p can be killed now that we have moved
to an edge based LCM implementation.
So I started poking at gcse to see if we still got insertions requested
where pre_expr_reaches_here_p returned zero.
Interestingly enough, I found a few cases where it could happen.
The first was a minor bug in the recent speedups to computer_laterin; we
would end up computing the wrong value for LATER for out edges from the
entry block. This caused some requested insertions in "weird" places which
were being pruned out via the reachability check.
The second case was more interesting. Given a path sequence that included
A->B->C->D where a evaluation of an expression E occurred in block B and
we tried to compute if an evaluation placed in block A would reach block D
pre_expr_reaches_here_p would return zero. [ There's a reason for this
somewhat odd behavior. Read the code. ]
Anyway, there are two issues with this case:
1. We're looking at reachability assuming an expression is inserted
in a block, rather than on an outgoing edge of a block. This doesn't
ever cause problems, but it does cause pre_expr_reaches_here_p to do
more work than it really needs to.
2. The evaluation of E in block B above is going to be deleted as it
must be redundant (otherwise we would not be trying to place an
evaluation on an outgoing edge from A). If the evaluation is deleted,
then E placed on an outgoing edge of A would reach D.
In fact, the fundamental basis behind LCM guarantees that if we
want to insert in A above that the result will reach D.
So, we want to do two things:
1. Fix the initialization of LATER (and NEARER).
2. Remove the calls to pre_expr_reaches_here_p from pre_edge_insert.
This both speeds up the compiler *and* allows us to optimize more
effectively in some cases.
This patch does both.
* gcse.c (pre_expr_reaches_here_p): Kill CHECK_PRE_COM argument.
All callers changed.
(pre_expr_reaches_here_p_work): Likewise.
(pre_edge_insert): No longer call pre_expr_reaches_here_p.
* lcm.c (compute_laterin): Fix initialization of LATER.
(compute_nearerout): Similarly for NEARER.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.69
diff -c -3 -p -r1.69 gcse.c
*** gcse.c 1999/11/11 09:21:12 1.69
--- gcse.c 1999/11/15 06:09:33
*************** static int one_cprop_pass PROTO ((i
*** 596,603 ****
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));
static void insert_insn_end_bb PROTO ((struct expr *, int, int));
static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
static void pre_insert_copies PROTO ((void));
--- 596,602 ----
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));
static void insert_insn_end_bb PROTO ((struct expr *, int, int));
static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
static void pre_insert_copies PROTO ((void));
*************** static void delete_null_pointer_checks_1
*** 640,646 ****
static rtx process_insert_insn PROTO ((struct expr *));
static int pre_edge_insert PROTO ((struct edge_list *, struct expr **));
static int expr_reaches_here_p_work PROTO ((struct occr *, struct expr *, int, int, char *));
! static int pre_expr_reaches_here_p_work PROTO ((int, struct expr *, int, int, char *));
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
--- 639,646 ----
static rtx process_insert_insn PROTO ((struct expr *));
static int pre_edge_insert PROTO ((struct edge_list *, struct expr **));
static int expr_reaches_here_p_work PROTO ((struct occr *, struct expr *, int, int, char *));
! static int pre_expr_reaches_here_p_work PROTO ((int, struct expr *,
! int, char *));
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
*************** compute_pre_data ()
*** 4213,4221 ****
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
--- 4213,4218 ----
*************** compute_pre_data ()
*** 4224,4234 ****
the closest such expression. */
static int
! pre_expr_reaches_here_p_work (occr_bb, expr, bb, check_pre_comp, visited)
int occr_bb;
struct expr *expr;
int bb;
- int check_pre_comp;
char *visited;
{
edge pred;
--- 4221,4230 ----
the closest such expression. */
static int
! pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited)
int occr_bb;
struct expr *expr;
int bb;
char *visited;
{
edge pred;
*************** pre_expr_reaches_here_p_work (occr_bb, e
*** 4244,4251 ****
/* 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
--- 4240,4246 ----
/* Nothing to do. */
}
/* Does this predecessor generate this expression? */
! else if (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
*************** pre_expr_reaches_here_p_work (occr_bb, e
*** 4261,4268 ****
else
{
visited[pred_bb] = 1;
! if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb,
! check_pre_comp, visited))
return 1;
}
}
--- 4256,4262 ----
else
{
visited[pred_bb] = 1;
! if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
return 1;
}
}
*************** pre_expr_reaches_here_p_work (occr_bb, e
*** 4275,4291 ****
memory allocated for that function is returned. */
static int
! pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp)
int occr_bb;
struct expr *expr;
int bb;
- int check_pre_comp;
{
int rval;
char * visited = (char *) xcalloc (n_basic_blocks, 1);
! rval = pre_expr_reaches_here_p_work(occr_bb, expr, bb, check_pre_comp,
! visited);
free (visited);
--- 4269,4283 ----
memory allocated for that function is returned. */
static int
! pre_expr_reaches_here_p (occr_bb, expr, bb)
int occr_bb;
struct expr *expr;
int bb;
{
int rval;
char * visited = (char *) xcalloc (n_basic_blocks, 1);
! rval = pre_expr_reaches_here_p_work(occr_bb, expr, bb, visited);
free (visited);
*************** pre_edge_insert (edge_list, index_map)
*** 4529,4538 ****
/* Insert this expression on this edge if if it would
reach the deleted occurence in BB. */
! if (!TEST_BIT (inserted[e], j)
! && (bb == ENTRY_BLOCK
! || pre_expr_reaches_here_p (bb, expr,
! BLOCK_NUM (occr->insn), 0)))
{
rtx insn;
edge eg = INDEX_EDGE (edge_list, e);
--- 4521,4527 ----
/* Insert this expression on this edge if if it would
reach the deleted occurence in BB. */
! if (!TEST_BIT (inserted[e], j))
{
rtx insn;
edge eg = INDEX_EDGE (edge_list, e);
*************** pre_insert_copies ()
*** 4660,4666 ****
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))
continue;
/* Copy the result of avail to reaching_reg. */
--- 4649,4655 ----
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)))
continue;
/* Copy the result of avail to reaching_reg. */
Index: lcm.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/lcm.c,v
retrieving revision 1.6
diff -c -3 -p -r1.6 lcm.c
*** lcm.c 1999/11/11 09:21:12 1.6
--- lcm.c 1999/11/15 06:09:34
*************** compute_laterin (edge_list, earliest, an
*** 269,274 ****
--- 269,281 ----
of the optimistic edge. That will requeue the affected blocks. */
sbitmap_vector_ones (later, num_edges);
+ /* Note that even though we want an optimistic setting of LATER, we
+ do not want to be overly optimistic. Consider an outgoing edge from
+ the entry block. That edge should always have a LATER value the
+ same as EARLIEST for that edge. */
+ for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ sbitmap_copy (later[(int)e->aux], earliest[(int)e->aux]);
+
/* Add all the blocks to the worklist. This prevents an early exit from
the loop given our optimistic initialization of LATER above. */
for (bb = n_basic_blocks - 1; bb >= 0; bb--)
*************** compute_nearerout (edge_list, farthest,
*** 597,602 ****
--- 604,616 ----
/* We want a maximal solution. */
sbitmap_vector_ones (nearer, num_edges);
+
+ /* Note that even though we want an optimistic setting of NEARER, we
+ do not want to be overly optimistic. Consider an incoming edge to
+ the exit block. That edge should always have a NEARER value the
+ same as FARTHEST for that edge. */
+ for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ sbitmap_copy (nearer[(int)e->aux], farthest[(int)e->aux]);
/* Add all the blocks to the worklist. This prevents an early exit
from the loop given our optimistic initialization of NEARER. */