This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Tremendous performance regression in 1.1.2 -> mainline
- To: Michael Matz <matzmich at cs dot tu-berlin dot de>
- Subject: Re: Tremendous performance regression in 1.1.2 -> mainline
- From: Richard Henderson <rth at cygnus dot com>
- Date: Thu, 6 Apr 2000 23:18:39 -0700
- Cc: Brad Lucier <lucier at math dot purdue dot edu>, gcc at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- References: <200004061821.NAA09259@polya.math.purdue.edu> <Pine.SOL.4.10.10004070644030.28209-101000@platon>
On Fri, Apr 07, 2000 at 07:19:12AM +0200, Michael Matz wrote:
> Nevertheless, can you please try the attached diff against flow.c with
> your testcase?
>
> With a reduced version of your test I had an big improvement in speed:
> (from 85 to 8 seconds in flow).
Keen. Brad's original test case is down to 19 seconds.
I've cleaned up your patch a bit and comitted the following.
r~
2000-04-06 Richard Henderson <rth@cygnus.com>
* flow.c (compute_flow_dominators): Free worklist.
2000-04-06 Michael Matz <matzmich@cs.tu-berlin.de>
* flow.c (compute_flow_dominators): Process blocks FIFO not LIFO.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.244
retrieving revision 1.246
diff -c -p -d -r1.244 -r1.246
*** flow.c 2000/04/06 21:22:48 1.244
--- flow.c 2000/04/07 06:15:22 1.246
*************** compute_flow_dominators (dominators, pos
*** 5252,5264 ****
int bb;
sbitmap *temp_bitmap;
edge e;
! basic_block *worklist, *tos;
/* Allocate a worklist array/queue. Entries are only added to the
list if they were not already on the list. So the size is
bounded by the number of basic blocks. */
! tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
! * n_basic_blocks);
temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
--- 5252,5265 ----
int bb;
sbitmap *temp_bitmap;
edge e;
! basic_block *worklist, *workend, *qin, *qout;
! int qlen;
/* Allocate a worklist array/queue. Entries are only added to the
list if they were not already on the list. So the size is
bounded by the number of basic blocks. */
! worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
! workend = &worklist[n_basic_blocks];
temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
*************** compute_flow_dominators (dominators, pos
*** 5267,5277 ****
{
/* 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. */
--- 5268,5281 ----
{
/* The optimistic setting of dominators requires us to put every
block on the work list initially. */
+ qin = qout = worklist;
for (bb = 0; bb < n_basic_blocks; bb++)
{
! *qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ qlen = n_basic_blocks;
+ qin = worklist;
/* We want a maximal solution, so initially assume everything dominates
everything else. */
*************** compute_flow_dominators (dominators, pos
*** 5282,5291 ****
e->dest->aux = ENTRY_BLOCK_PTR;
/* Iterate until the worklist is empty. */
! while (tos != worklist)
{
/* Take the first entry off the worklist. */
! basic_block b = *--tos;
bb = b->index;
/* Compute the intersection of the dominators of all the
--- 5286,5299 ----
e->dest->aux = ENTRY_BLOCK_PTR;
/* Iterate until the worklist is empty. */
! while (qlen)
{
/* Take the first entry off the worklist. */
! basic_block b = *qout++;
! if (qout >= workend)
! qout = worklist;
! qlen--;
!
bb = b->index;
/* Compute the intersection of the dominators of all the
*************** compute_flow_dominators (dominators, pos
*** 5325,5331 ****
{
if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
{
! *tos++ = e->dest;
e->dest->aux = e;
}
}
--- 5333,5343 ----
{
if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
{
! *qin++ = e->dest;
! if (qin >= workend)
! qin = worklist;
! qlen++;
!
e->dest->aux = e;
}
}
*************** compute_flow_dominators (dominators, pos
*** 5337,5347 ****
{
/* 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. */
--- 5349,5362 ----
{
/* The optimistic setting of dominators requires us to put every
block on the work list initially. */
+ qin = qout = worklist;
for (bb = 0; bb < n_basic_blocks; bb++)
{
! *qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
+ qlen = n_basic_blocks;
+ qin = worklist;
/* We want a maximal solution, so initially assume everything post
dominates everything else. */
*************** compute_flow_dominators (dominators, pos
*** 5352,5361 ****
e->src->aux = EXIT_BLOCK_PTR;
/* Iterate until the worklist is empty. */
! while (tos != worklist)
{
/* Take the first entry off the worklist. */
! basic_block b = *--tos;
bb = b->index;
/* Compute the intersection of the post dominators of all the
--- 5367,5380 ----
e->src->aux = EXIT_BLOCK_PTR;
/* Iterate until the worklist is empty. */
! while (qlen)
{
/* Take the first entry off the worklist. */
! basic_block b = *qout++;
! if (qout >= workend)
! qout = worklist;
! qlen--;
!
bb = b->index;
/* Compute the intersection of the post dominators of all the
*************** compute_flow_dominators (dominators, pos
*** 5398,5410 ****
{
if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
{
! *tos++ = e->src;
e->src->aux = e;
}
}
}
}
}
free (temp_bitmap);
}
--- 5417,5435 ----
{
if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
{
! *qin++ = e->src;
! if (qin >= workend)
! qin = worklist;
! qlen++;
!
e->src->aux = e;
}
}
}
}
}
+
+ free (worklist);
free (temp_bitmap);
}