Re: Regclass cleanups

[Jan Hubicka <hubicka at atrey dot karlin dot mff dot cuni dot cz>]

> 
> I haven't looked at the change, but I suspect it could get rather expensive
> if we're presented with a long dependency chain.

I was taking the time complexity very seriously. We really need to climb down
that chain in case we want to generate sane code on architectures like
Ultra/VIS or i386/MMX, so what I made is that I always re-calculate only the
insns that contins registers with changed preferrences (thats why the patch is
so long). Even I am recalculating only the insns, that contains register in the
cases, that changing it's prefererce may changes other's preferrences.

In the expectation, that every insn contains only constant number of registers
referenced (10, since only the real operands, not memory addresses are in the
play), every register changes preferrence only constant amout of
times (once in initial pass, second time it gets the specific class and in
future possibly third time once it is assegned to hardreg).
We scan only linear amout of insns (30*number_of_insn in the really worst
case expecting that each insn has exactly 10 operands).

Fact is that to store the insns required to calculate I am using bitmaps,
that may turn out to be somewhat expensive in future, but I don't expect so,
since they are likely very sparse.
Ideally these would be linked lists sorted in some order and merged using
heaps..

I was trying to force insn chains to be 5000 insns long using asm insns
and the time of my patched regclass was only 1.5*original_time


Honza
> 
> jeff