Re: [dataflow][patch] Convert conflict graph to lower triangular bit matrix

[Michael Matz <matz at suse dot de>]

Hi,

On Mon, 6 Feb 2006, Peter Bergner wrote:

> Correct, just using basic block info as part of the conflictno, then
> you'll only be able to partition the local-local conflicts and the
> globals could possibly conflict with any local.  Using a trick the
> IBM iSeries compiler uses by renumbering all global pseudos to have
> smaller numbers than local pseudos and assuming all pseudos local
> to the same basic block have contiguous numbers, the conflict graph

Yes, like I also thought ...

> Seeing the structure above, yes you could implement it as multiple
> matrices as you mention above.  I have thought about doing that, but
> even if I do, it won't be visible from a conflict graph API standpoint.

... but I was trying to envision an efficient implementation of that API
which saves space compared to a triangular bit matrix but isn't too slow,
which I feel will be the problem here.  Most of the time you will have
less than say, hmm, 1000 pseudos.  Let's be very conservative and assume
that each pseudo conflicts with a fourth of all other pseudos, i.e. 250.  
Again assume that these conflicts on average cluster well, then we can
trivially implement that whole list of conflicts in about 40 bytes
(including some bytes for pointers to bitmap elements), less than a cache
line.  Even the full diagonal matrix will only take up 63KB.

A more space efficient implementation of the conflict graph has to have a
quite low constant factor in it to not pessimize most of such normally
sized functions (and an additional indirect load when formerly there was
only one is quite some factor).  Sure, such space effectiveness will pay
off with Brads testcases, but it's not trivial to implement without unduly
slowing down small to medium functions.  Especially considering the usual
clustering effects of code (i.e. pseudos tend to conflict with pseudos
which have number nearby).  In my experience it sometimes is quite
surprising how well a theoretically suboptimal code does when presented
with real world code.  It's also very disturbing when your theoretically
much superior code also only runs half as fast in practice as the
nonoptimal trivial throw-away implementation, because of such clustering
effects, except in the most extreme cases :-)

> As I mentioned in my last note, if in addition to basic block info, you
> also used region info, then you can also partition some global-global
> as well as some global-local conflicts too.

Yes, if the basic infrastructure for partitioning the conflict edges (or
even just the conflict bits) is there, one can do fancy things.  Also
pseudos which don't conflict because they don't have intersecting possible
sets of hardregs (the usable_regs member in my old code, although I never
used it to trim down the size of the conflict matrix, only of the
adjacency lists) would fit there.

> As an aside, one benefit for making global pseudos have smaller register
> numbers than local pseudos (and one of the reasons it was done for the
> iSeries compiler) is that your basic block live_in/live_out, pavin/pavout,
> ... bitmaps only have to be large enough to hold the largest global pseudo
> register number.

As long as these are implemented as bitmaps (in the gcc sense) it doesn't 
make a difference exactly how large the numbers are (although there's a 
small benefit of clustering all bits together of course).  With sbitmaps 
(which allocate exactly enough space to hold all up to the max bit) the 
benefit is much higher.

> you could always create a mapping and hide it behind an API. I don't
> remember if we actually renumbered them or created a mapping on the
> iSeries compiler...it was just too long ago.

:-)


Ciao,
Michael.