llvm dev - Jun 2007 - [LLVMdev] a possible alternative for pre-legalize extended ValueTypes

After doing a bunch of work for moving pre-legalize extended ValueTypes
into a table in SelectionDAG, I may have just found a simpler approach.

There are under 32 simple ValueType values, so we only really need 5 bits
to represent those. ValueType is already a 32-bit type on most hosts; what
if we make use of the remaining 27 bits instead of using an external
table?

If we can assume that vector lengths will always be a fixed multiple of 2,
we can encode vector lengths for extended vector types as the log2 of the
length, biased by one. Using only 6 bits gets us vector lengths up to
(2**64)-2, which Ought To Be Enough For Anyone. The bias allows an all-zero
pattern to be available to be interpreted as a scalar type, while still
permitting encodings of vectors with length 1, distinct from scalars.

That's 11 bits used, so we've got 21 left to play with, for
arbitrary-size
integers, custom floating-point formats, or whatever else. It would be
less if we need to support non-power-of-two vector lengths. Either way,
it's less that can be imagined being used, if people get into this kind of
thing. However, maybe we can get by with creating encodings.

If the high 27 bits of a ValueType are all zero, then it's a simple
ValueType, and it can be used directly to index various tables.

Obviously there would be helper functions to encapsulate all of this
encoding complexity.

I don't have any code written yet; I wanted to run the idea by the list
first :-).

Dan

-- 
Dan Gohman, Cray Inc.

On Jun 22, 2007, at 11:06 AM, Dan Gohman wrote:
> After doing a bunch of work for moving pre-legalize extended  
> ValueTypes
> into a table in SelectionDAG, I may have just found a simpler  
> approach.
>
> There are under 32 simple ValueType values, so we only really need  
> 5 bits
> to represent those. ValueType is already a 32-bit type on most  
> hosts; what
> if we make use of the remaining 27 bits instead of using an external
> table?
>
> If we can assume that vector lengths will always be a fixed  
> multiple of 2,
> we can encode vector lengths for extended vector types as the log2  
> of the
> length, biased by one. Using only 6 bits gets us vector lengths up to
> (2**64)-2, which Ought To Be Enough For Anyone.
Yerk! This would throw a serious wrench in supporting non power of  
two vector lengths, which is needed by us. We needed to add v3f32 and  
v3i32 ValueTypes just to define our register file in the .td.

--
Christopher Lamb



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20070622/f3ce0d40/attachment.html>

On Fri, Jun 22, 2007 at 11:57:27AM -0700, Christopher Lamb
wrote:
> 
> On Jun 22, 2007, at 11:06 AM, Dan Gohman wrote:
> 
> >If we can assume that vector lengths will always be a fixed  
> >multiple of 2,
> >we can encode vector lengths for extended vector types as the log2  
> >of the
> >length, biased by one. Using only 6 bits gets us vector lengths up to
> >(2**64)-2, which Ought To Be Enough For Anyone.
> 
> Yerk! This would throw a serious wrench in supporting non power of  
> two vector lengths, which is needed by us. We needed to add v3f32 and  
> v3i32 ValueTypes just to define our register file in the .td.
Ok. You'll probably want to have dedicated simple values for vector types
which are legal, and those would still fit within the initial 5 (or maybe
6) bits. But then you may want to do things like v6f32 and so on, so
you'll still need more flexibility than the log2 encoding.

I'm ok with a linear encoding for extended vector lengths. I don't know
offhand how many bits will be needed for it, so I don't know how many
bits that leaves for arbitrary bitwidth integers and such, but this may
be a situation where we shouldn't worry it until someone actually wants
to do it.

Dan

-- 
Dan Gohman, Cray Inc.

On Fri, 22 Jun 2007, Dan Gohman wrote:
> After doing a bunch of work for moving pre-legalize extended ValueTypes
> into a table in SelectionDAG, I may have just found a simpler approach.
ooh simple is good :)
> There are under 32 simple ValueType values, so we only really need 5 bits
> to represent those. ValueType is already a 32-bit type on most hosts; what
> if we make use of the remaining 27 bits instead of using an external
> table?
Hrm, interesting.  If you do this, please reserve 6 bits for the simple 
VTs, to permit future expansion without having to shuffle bits around.
> If we can assume that vector lengths will always be a fixed multiple of 2,
> we can encode vector lengths for extended vector types as the log2 of the
> length, biased by one. Using only 6 bits gets us vector lengths up to
> (2**64)-2, which Ought To Be Enough For Anyone. The bias allows an all-zero
> pattern to be available to be interpreted as a scalar type, while still
> permitting encodings of vectors with length 1, distinct from scalars.
As Christopher says, I think that non-power-of-two vectors are going to be 
important in the future.  That said, I wouldn't have a problem with 
limiting vector width to be something capped, say at 4096 elements?  If 
people want really large vectors we could bump this up in the future.
> I don't have any code written yet; I wanted to run the idea by the list
> first :-).
Sounds very interesting!

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/