llvm dev - Dec 2009 - [LLVMdev] Adding multiples-of-8 integer types to MVT

>> Would there be any interest/opposition to extending the set of simple
>> integer types in MVT to include the missing multiples of 8 (up to 64
>> bits)? That is: i24, i40, i48, i56?
By the way, the integer type legalization logic should probably go like
this: let T be an integer type.

(1) If T is legal, do nothing.
(2) If there is a legal integer type which is bigger (in bitwidth) than T,
then promote T to the smallest legal type which is bigger than T.
(3) In the remaining case, T is necessarily bigger than the largest legal
integer type (call this type L).  Take the smallest positive N such that
  (bitwidth of T) <= (bitwidth of L) * 2^N
If you have equality in the equation, i.e. if the bitwidth of T is a power
of two multiple of the bitwidth of L, then expand T into two equal integer
types of half the size.  Otherwise promote T to the type with bitwidth equal
to the right-hand-side of the equation, i.e. (bitwidth of L) * 2^N.

If all legal integer types have a power of two size, then this coincides
with what we have today.  If some legal types do not have a power of 2
size then finding the type to promote to in (2) requires more computation
than in the power-of-two case.  For (3), you need to know the largest legal
type L, which currently isn't exposed in a convenient way for this.  For
simple integer types everything can of course be pre-calculated in tables,
like now.  For extended integer types it would be good to have an efficient
algorithm for calculating this on the fly.  At worst, values can be cached.

Ciao,

Duncan.

On Saturday, December 05, 2009 7:34 AM, Duncan Sands
wrote,
>
> >> Would there be any interest/opposition to extending the 
> set of simple 
> >> integer types in MVT to include the missing multiples of 8 
> (up to 64 
> >> bits)? That is: i24, i40, i48, i56?
> 
> By the way, the integer type legalization logic should 
> probably go like
> this: let T be an integer type.
> 
> (1) If T is legal, do nothing.
> (2) If there is a legal integer type which is bigger (in 
> bitwidth) than T, then promote T to the smallest legal type 
> which is bigger than T.
> (3) In the remaining case, T is necessarily bigger than the 
> largest legal integer type (call this type L).  Take the 
> smallest positive N such that
>   (bitwidth of T) <= (bitwidth of L) * 2^N If you have 
> equality in the equation, i.e. if the bitwidth of T is a 
> power of two multiple of the bitwidth of L, then expand T 
> into two equal integer types of half the size.  Otherwise 
> promote T to the type with bitwidth equal to the 
> right-hand-side of the equation, i.e. (bitwidth of L) * 2^N.

What would do you think of modifying case (3) slightly as follows?

(3) In the remaining case, T is necessarily bigger than the largest
legal integer type (call this type L).  Take the smallest positive N
such that for some legal type, Leg, 
  
  (bitwidth of T) <= (bitwidth of Leg) * 2^N 

Of the types that satisfy this relation, call the smallest S. If you
have equality in the equation when Leg:=S, i.e. if the bitwidth of T is
a power of two multiple of the bitwidth of the smallest legal type to
which it can be expanded, then expand T into two equal integer types of
half the size.  Otherwise promote T to the type with bitwidth equal to
the right-hand-side of the equation, i.e. (bitwidth of S) * 2^N. 

On a target with 32- and 24-bit registers, for example, this
modification would allow i48 to be expanded directly to 24-bit registers
instead of promoting to an i64 and expanding to 32-bit.

-Ken

Hi Ken,
> What would do you think of modifying case (3) slightly as follows?
well, that special cases the smallest legal type, which might not be
a good idea.  Imagine that i10 is legal, and also i32.  Is it better
to turn i40 into four lots of i10 or two lots of i32 with a promotion?
Expansion is expensive, so two lots of i32 would be best.  I suggest the
following scheme:

(3) Suppose T is larger than the largest legal type.  Look at all the
legal types LT for which
   bitwidth T <= 2 * bitwidth of LT
If there is one, take the smallest one (SLT) and promote T to 2*SLT.
If there are none (because bitwidth T is too big), look at all the
legal types LT for which
   bitwidth T <= 4 * bitwidth of LT
If there is one, take the smallest one (SLT) and promote T to 4*SLT.
Continue with 8*, 16* etc.

For example, if i24 and i32 are the legal types, with this algorithm
types i33, ..., i48 would be promoted to i48 then expanded to two lots
of i24.  Types i49, ..., i64 would be promoted to i64 then expanded to
two lots of i32.

For example, if i10 and i32 are the legal types, i40 would be promoted
to i64 then expanded to two lots of i32.

Ciao,

Duncan.