[LLVMdev] Register class proliferation

[Jakob Stoklund Olesen]

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.

/jakob