On 2008/4/27 J.C. Pizarro <[EMAIL PROTECTED]> wrote:
> On Fri 25 Apr 2008 22:22:55 -0500, Peter Bergner <[EMAIL PROTECTED]> wrote:
> > The difference between a compressed upper triangular bit matrix from a
> standard
> > upper triangular bit matrix like the one above, is we eliminate space from
> the
> > bit matrix for conflicts we _know_ can never exist. The easiest case to
> catch,
> > and the only one we catch at the moment, is that allocnos that are "local"
> to a
> > basic block B1 cannot conflict with allocnos that are local to basic block
> B2,
> > where B1 != B2. To take advantage of this fact, I updated the code in
> global.c
> > to sort the allocnos such that all "global" allocnos (allocnos that are
> live in
> > more than one basic block) are given smaller allocno numbers than the
> "local"
> > allocnos, and all allocnos for a given basic block are grouped together in
> a
> > contiguous range to allocno numbers. The sorting is accomplished by:
> >
> > /* ...so we can sort them in the order we want them to receive
> > their allocnos. */
> > qsort (reg_allocno, max_allocno, sizeof (int), regno_compare);
> >
>
> ...
> It's useful when there are increases or decreases in the number of BBs.
Topicing off about the recent stupidity's discussion, the chained
upper triangulars
and rectangulars are more flexible than a bigger compressed upper triangular
because
how expensive is modifying the compressed upper triangular when
1) add o remove basic blocks?
2) add o remove allocnos?
In the chained case, you can call to subroutine to make it consistent after of
adding or removing basic blocks or allocnos, it's traversing the chains and
remallocing the many local memoryspaces of BBs.
In the compressed case, you have to realize complex and expensive routines
for remallocing the big compressed upper triangular.
J.C.Pizarro
