This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: if-conversion a performance bottleneck
- To: Brad Lucier <lucier at math dot purdue dot edu>
- Subject: Re: if-conversion a performance bottleneck
- From: Michael Matz <matzmich at cs dot tu-berlin dot de>
- Date: Wed, 3 May 2000 07:53:00 +0200 (MET DST)
- cc: Richard Henderson <rth at cygnus dot com>, gcc at gcc dot gnu dot org
Hi,
On Tue, 2 May 2000, Michael Matz wrote:
> > time seconds seconds calls ms/call ms/call name
> > 57.51 111.67 111.67 40604 2.75 2.75 sbitmap_intersection_of_succs
> > 12.83 136.59 24.92 15025 1.66 1.66 sbitmap_intersection_of_preds
>
> I once had faster versions of these two functions, if I get home I'll see
> if they make any difference on your input data.
Before fiddling with sbitmap_intersection_of_xx() I first reworked
compute_flow_dominators() to also behave normally in calculating the
post_doms. At least the order of work-queue initialization was wrong (in
post_dom the changes are propagating from the _end_). I then also
implemented a poor man's topological sort for cyclic graphs ;), which
again gave a better performance. (I also did this once for doms, but there
it didn't make a great difference on Brads test cases)
Please try the attached diff (against actual CVS) if they make also a
difference for you ;)
Ciao,
Michael.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.272
diff -u -r1.272 flow.c
--- flow.c 2000/05/02 00:02:24 1.272
+++ flow.c 2000/05/03 05:39:53
@@ -5896,13 +5896,43 @@
/* 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);
+ for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
+ {
+ if (e->src != ENTRY_BLOCK_PTR)
+ {
+ *qin++ = e->src;
+ e->src->aux = e->src;
+ }
}
+ bb = n_basic_blocks - 1;
+ while (bb >= 0)
+ {
+ /* add all predecessors of queued blocks
+ if they are not already there */
+ while (qout < qin)
+ {
+ basic_block cc = *qout++;
+ for (e = cc->pred; e; e = e->pred_next)
+ {
+ if (e->src != ENTRY_BLOCK_PTR && !e->src->aux)
+ {
+ *qin++ = e->src;
+ e->src->aux = e->src;
+ }
+ }
+ }
+
+ /* look if we oversaw some blocks, add one of them
+ and again try to add predecessors of it */
+ while (bb >= 0 && BASIC_BLOCK (bb)->aux) bb--;
+ if (bb >= 0)
+ {
+ *qin++ = BASIC_BLOCK (bb);
+ BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
+ }
+ }
qlen = n_basic_blocks;
- qin = worklist;
+ qin = qout = worklist;
/* We want a maximal solution, so initially assume everything post
dominates everything else. */