Re: big slowdown in egcs-1.1.2->gcc-2.95 on alpha

[Joern Rennecke <amylaar@cygnus.co.uk>]

>   > 	* 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 ;-)