[LLVMdev] Register class proliferation

[Andrew Trick]

On Jun 21, 2011, at 10:20 AM, Jakob Stoklund Olesen wrote:

> 
> On Jun 21, 2011, at 9:23 AM, Jim Grosbach wrote:
> 
>> 
>> On Jun 21, 2011, at 8:51 AM, Jakob Stoklund Olesen wrote:
>> 
>>> In the past, I've seen some pushback on the list against adding more register classes. You can see it in the code as well, TargetLowering::getRegClassForInlineAsmConstraint() returns a vector of registers instead of a real register class.
>>> 
>>> What is the reason we don't like adding register classes? Is it still a valid reason?
>>> 
>> 
>> As I recall, it's a performance issue, as some of the algorithms involved were non-linear and expensive. I think you've refactored most of that away by now, though.
> 
> I can't think of any super-linear algorithms remaining except for getCommonSubClass() which could easily be fixed. I've never seen it show up on a Shark trace, though.
> 
> If we give each register class a bit vector of sub-classes, the currently linear isSubClass() / isSuperClass() would become constant time, and getCommonSubClass() could be made linear with CountTrailingZeros(A and B).
> 
> Yes, those bit vectors would require N^2 space, but the constant factor is 1 bit, so I don't care. I am not adding that many register classes.


We should make it clear that the performance problem is with register aliases, not classes. Register aliasing is a serious problem with the current implementation. The postRA scheduler is *cubic* in the size of the alias list. You dramatically improved compile time with this simple fix:

------------------------------------------------------------------------
r130801 | stoklund | 2011-05-03 15:31:24 -0700 (Tue, 03 May 2011) | 10 lines
Mark ultra-super-registers QQQQ as call-clobbered instead of the D sub-registers.

And the new regalloc is not yet designed to scale with the number of register aliases. (But that could be fixed under some limited definition of aliasing).

Whereas, I don't see a reason that proliferating register classes would be a problem now or in the future.

Is it easy to distinguish a a couple classes that make up a disjoint coverage set (e.g. int regs, float regs, ...)? Some algorithms partition the problem this way.

-Andy