<div><span class="gmail_quote">On 4/9/07, <b class="gmail_sendername">David Greene</b> <<a href="mailto:greened@obbligato.org">greened@obbligato.org</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Anton Vayvod wrote:<br><br>> Sure, but where these comparisons are needed, for example? RAX and<br>> EAX alias sets intersect and that's enough to decide that these regs
<br>> can't be assigned simultaneously.<br><br>One place these comparisons are used is to build a provably optimal<br>register class tree in a Smith/Ramsey/Holloway allocator.  Building it<br>algorithmically is portable to all architectures without requiring
<br>the person writing the machine-specific parts to care about what<br>the register allocator does.</blockquote>
<div> </div>
<div>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).
</div>
<div> </div>
<div>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.</div><br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">> In general, that what you would check anyway because for some<br>> architectures you won't (theoretically, AFAIK) have equal alias sets
<br>> at all, but they'll intersect. Consider the following example (as I<br>> remember it from some paper on representing irregular<br>> architechtures):<br><br>As Smith, et. al. point out, such architectures practically don't
<br>exist in the real world.  Most alias sets are either completely<br>disjoint, exactly equal or entirely contained. </blockquote><br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">> There are 8 32-bit general purpose registers (R0-R7) and there are 7<br>>  64-bit registers (W0-W6). Ri reg is a high word of Wi and R(i+1) is
<br>>  a low word of Wi (i runs from 0 to 6). So the alias set for Wi is {<br>> Ri, R(i + 1)} (you can include Wi, of course). You can't allocate<br>> neighbouring W-regs the same time as their alias sets intersect (but
<br>> not equal).<br><br>Sure, the alias sets won't be equal, but that's not the point.  The<br>point is that when they _are_ equal some very important register<br>allocation optimizations can be done.</blockquote>

<div> </div>
<div>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.</div><br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">BTW, is there an architecture out there that has register overlaps<br>like this?  Maybe some DSP chip or something?
</blockquote>
<div> </div>
<div>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.
</div><br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">In any case I can work around the problem by building temporary<br>alias sets, but that's ugly and wasteful.  It sounds like there
<br>are too many dependencies on the current specification to make<br>changing it possible, though.</blockquote>
<div> </div></div>