[dataflow][patch] Convert conflict graph to lower triangular bit matrix
Michael Matz
matz@suse.de
Sun Feb 5 04:20:00 GMT 2006
Hi,
On Fri, 3 Feb 2006, Peter Bergner wrote:
> I'm not too familiar with how efficient bitmaps are for iterating over,
They are quite good for that.
> but I'll have a look. My initial implementation doesn't use a normal
> linked list (ie, 1 neighbor, 1 next pointer), but more of a small vector
> of neighbors (size is tunable) and 1 next pointer.
Ahh, then using bitmaps shouldn't be difficult, they are basically the
same, just that they hold indices and factorize large common offsets of
these indices.
> My plan for the future is to implement an idea I came up with a while
> back (but never tried) for minimizing the size of the bit matrix to
> something even smaller than a lower triangular bit matrix, hopefully a
> lot smaller. Conceptually, my idea is to create another mapping similar
> to the pseudo regno -> allocno mapping (conflictno?) that allows us to
> determine for a (large?) class(es) of pseudos, that two pseudos do not
> conflict simply by comparing their conflictnos, For this class(es) of
> pseudos, since we can tell they don't conflict simply by looking at
> their conflictnos, there's no need to allocate space in the bit matrix
> for them.
But wouldn't that complicate the layout and hence slow down access to the
bit matrix quite a bit? For instance with the simple form of basic-block
nr as conflictno for local regs, and say -1 for global regs. Then it's
true that pseudos with non-negative different conflictnos can't conflict
and would need no space in the matrix. But how do you actually make that
hole not take up space? Also considering that all global regs can still
conflict with the local ones. The problem is that this definition of
conflictno would not partition the conflicts itself. It would partition
only the conflicts restricted to local-local regs.
...*thinking*... I see how that could help. But it requires remapping of
regnos to indices depending on which conflict pair one is interested in.
E.g. a row for a local reg needs to contain elements for all global regs
plus all local regs with the same conflictno. A row for global regs needs
to contain elements for all pseudos. So one could arrange for not storing
any bits for local-local conflicts with nonequal conflictnos. How that
plays with a triangular matrix form I don't immediately see. Perhaps one
could simply use multiple matrices, one for each conflictno-pair which has
potentially a conflict. Interesting, interesting :-)
Ciao,
Michael.
More information about the Gcc-patches
mailing list