[LLVMdev] Register Alias Sets

[Anton Vayvod]

On 4/9/07, David Greene <greened at obbligato.org> wrote:
>
> Anton Vayvod wrote:
>
> > Sure, but where these comparisons are needed, for example? RAX and
> > EAX alias sets intersect and that's enough to decide that these regs
> > can't be assigned simultaneously.
>
> One place these comparisons are used is to build a provably optimal
> register class tree in a Smith/Ramsey/Holloway allocator.  Building it
> algorithmically is portable to all architectures without requiring
> the person writing the machine-specific parts to care about what
> the register allocator does.


I think Smith/Ramsey and Holloway compare alias sets of the whole register
classes, not individual registers. So anyway you'd build alias sets of the
register classes at the start of your allocator pass. And whether you add a
register and its alias set to class' alias set or you add just the alias set
with one more register in it doesn't make any difference (except one more
line of code in the first case, of course).

LLVM represent target's registers almost the same way Smith, et al. suggest
except for the difference in alias(R) definition that you've mentioned
above.

> In general, that what you would check anyway because for some
> > architectures you won't (theoretically, AFAIK) have equal alias sets
> > at all, but they'll intersect. Consider the following example (as I
> > remember it from some paper on representing irregular
> > architechtures):
>
> As Smith, et. al. point out, such architectures practically don't
> exist in the real world.  Most alias sets are either completely
> disjoint, exactly equal or entirely contained.


> There are 8 32-bit general purpose registers (R0-R7) and there are 7
> >  64-bit registers (W0-W6). Ri reg is a high word of Wi and R(i+1) is
> >  a low word of Wi (i runs from 0 to 6). So the alias set for Wi is {
> > Ri, R(i + 1)} (you can include Wi, of course). You can't allocate
> > neighbouring W-regs the same time as their alias sets intersect (but
> > not equal).
>
> Sure, the alias sets won't be equal, but that's not the point.  The
> point is that when they _are_ equal some very important register
> allocation optimizations can be done.


The alias sets of R and W register _classes_ are equal and again that is
what Smith, et al. use in their work to build an optimal register class
tree.

BTW, is there an architecture out there that has register overlaps
> like this?  Maybe some DSP chip or something?


Don't know really :) When I reviewed the Smith/Ramsey/Holloway paper it
turned out my example was almost the same they used on the first
figure. Though some other people mention unaligned register pairs (like if
Wi weren't single registers but register pairs). For example, Briggs writes
about it when talks about coloring of register pairs.

In any case I can work around the problem by building temporary
> alias sets, but that's ugly and wasteful.  It sounds like there
> are too many dependencies on the current specification to make
> changing it possible, though.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070410/97876701/attachment.html>