This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: big slowdown in egcs-1.1.2->gcc-2.95 on alpha
- To: law at cygnus dot com
- Subject: Re: big slowdown in egcs-1.1.2->gcc-2.95 on alpha
- From: Joern Rennecke <amylaar at cygnus dot co dot uk>
- Date: Fri, 13 Aug 1999 00:24:26 +0100 (BST)
- Cc: amylaar at cygnus dot co dot uk, lucier at math dot purdue dot edu, gcc at gcc dot gnu dot org, gcc-bugs at gcc dot gnu dot org, staff at math dot purdue dot edu, hosking at cs dot purdue dot edu, wilker at math dot purdue dot edu, bernds at cygnus dot com
> > * global.c (prune_preferences): Move some invariants out of the
> > inner loop.
> This patch is fine, even if it did not make a significant difference for
> the compile time slowdown in question. Thanks.
I have tested and comitted the patch.
I think I understand the bottleneck in prune_preferences better. It is
indeed the CONFLICTP check.
We can expect the conflicts to be sparse, because typically we have a lot
of pseudos that live only during a single basic block or during a loop.
Moreover, CONFLICTS are naturally symmetric, yet as the comment for
conflicts says:
`conflicts' is not symmetric; a conflict between allocno's i and j
is recorded either in element i,j or in element j,i. */
All CONFLICT_P tests are therefore duplicated, thus causing yet more
unnecessary overhead. `conflicts' is not symmetric; a conflict between allocno's i and j
is recorded either in element i,j or in element j,i. */
So, I think we can get better compiling performance for large programs
if conflicts allocnos_live use a representation that is efficient for
sparse sets, e.g. a hash table or a balanced tree.
Moreover, it makes sense to normalize conflicts before we store them,
e.g. we could say CONFLICTP (i, j) is normalized if i <= j. If the
conflict is not normalized, swapping the operands will normalize it.
Or if we go for hash tables and want to encourage a more uniform distribution
of has table filling, we could say CONFLICTP (i, j) is normalized if
(unsigned)(j - i) % n <= n >> 1 , where n is the total number of allocnos.
This does not work for even allocnos, so we just bump up n to an odd number.
The implementation is left as an exercise to the reader ;-)