llvm dev - Dec 2009 - [LLVMdev] Fwd: 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?

Adding the types to MVT (and ValueTypes.td) would allow LLVM to be
targeted to architectures that have registers and operations of these
sizes (for example, a 24-bit DSP that I'd like to develop a back end for
has 24-, 48- and 56-bit native integer types). Back ends are currently
limited to using power-of-2 types in their TableGen descriptions. 

Besides the obvious changes to ValueTypes.h, ValueTypes.td, and
ValueTypes.cpp, the addition of the new integer types would also require
changing (at least):

1. TableGen/CodeGenTarget.cpp - recognize and generate code for the new
types

2. LegalizeDAG.cpp - eliminate power-of-2 assumptions in the
legalization of extload and truncstore operations.

3. SelectionDAGBuild.cpp - add types to assertsext/assertzext generation
in getCopyFromRegs()

4. TargetLowering.cpp - eliminate power-of-2 assumptions in
computeRegisterProperties()

5. <Arch>ISelLowering.cpp - specify actions to lower the new types and
the operations that use them on all existing architectures (ouch!)

Are there more? 

The main drawback of adding the new types is the extra burden it would
put on back ends that don't use them, since they would need to add
special lowering code for all the types they don't use. On the other
hand, it opens the possibility of targeting architectures that LLVM
previously couldn't. 

Thoughts?

Regards,
-Ken

Instead of putting the burden on the back-ends to implement special
lowering code, why not implement code in the legalizer that would
automatically sign extend them to the next largest power of 2 integer if
the specific integer types were not supported. This would then remove
the need of the back-ends to implement anything as LLVM would just
generate extend the values to i32/i64 silently.

Micah 
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
> On Behalf Of Ken Dyck
> Sent: Wednesday, December 02, 2009 12:33 PM
> To: llvmdev at cs.uiuc.edu
> Subject: [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?
> 
> Adding the types to MVT (and ValueTypes.td) would allow LLVM to be
> targeted to architectures that have registers and operations of these
> sizes (for example, a 24-bit DSP that I'd like to develop a back end
> for
> has 24-, 48- and 56-bit native integer types). Back ends are currently
> limited to using power-of-2 types in their TableGen descriptions.
> 
> Besides the obvious changes to ValueTypes.h, ValueTypes.td, and
> ValueTypes.cpp, the addition of the new integer types would also
> require
> changing (at least):
> 
> 1. TableGen/CodeGenTarget.cpp - recognize and generate code for the
new
> types
> 
> 2. LegalizeDAG.cpp - eliminate power-of-2 assumptions in the
> legalization of extload and truncstore operations.
> 
> 3. SelectionDAGBuild.cpp - add types to assertsext/assertzext
> generation
> in getCopyFromRegs()
> 
> 4. TargetLowering.cpp - eliminate power-of-2 assumptions in
> computeRegisterProperties()
> 
> 5. <Arch>ISelLowering.cpp - specify actions to lower the new types
and
> the operations that use them on all existing architectures (ouch!)
> 
> Are there more?
> 
> The main drawback of adding the new types is the extra burden it would
> put on back ends that don't use them, since they would need to add
> special lowering code for all the types they don't use. On the other
> hand, it opens the possibility of targeting architectures that LLVM
> previously couldn't.
> 
> Thoughts?
> 
> Regards,
> -Ken
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

We have plans to implement 24-bit integers on PIC16 in future. So this
addition can help us a lot :)

I was hoping that by only supporting the desired sizes in
<Arch>TargetMachine::DataLayout, different targets would be able to
filter out the unsupported sizes. Besides, these sizes would be there
only if the front end generates them, and that is something that
different targets have control over. If what you say is true, needing to
modify other targets makes the problem more complicated than I
originally thought. 

One more thing that is of concern is that on architectures with such
integer sizes, there may be need for multiple pointer sizes. Currently
LLVM only assumes one size for pointers and that it usually assumed to
be the size of int. This may be another big thing to look at.


Regards
Ali

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]
On Behalf Of Ken Dyck
Sent: Wednesday, December 02, 2009 1:33 PM
To: llvmdev at cs.uiuc.edu
Subject: [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?

Adding the types to MVT (and ValueTypes.td) would allow LLVM to be
targeted to architectures that have registers and operations of these
sizes (for example, a 24-bit DSP that I'd like to develop a back end for
has 24-, 48- and 56-bit native integer types). Back ends are currently
limited to using power-of-2 types in their TableGen descriptions. 

Besides the obvious changes to ValueTypes.h, ValueTypes.td, and
ValueTypes.cpp, the addition of the new integer types would also require
changing (at least):

1. TableGen/CodeGenTarget.cpp - recognize and generate code for the new
types

2. LegalizeDAG.cpp - eliminate power-of-2 assumptions in the
legalization of extload and truncstore operations.

3. SelectionDAGBuild.cpp - add types to assertsext/assertzext generation
in getCopyFromRegs()

4. TargetLowering.cpp - eliminate power-of-2 assumptions in
computeRegisterProperties()

5. <Arch>ISelLowering.cpp - specify actions to lower the new types and
the operations that use them on all existing architectures (ouch!)

Are there more? 

The main drawback of adding the new types is the extra burden it would
put on back ends that don't use them, since they would need to add
special lowering code for all the types they don't use. On the other
hand, it opens the possibility of targeting architectures that LLVM
previously couldn't. 

Thoughts?

Regards,
-Ken


_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Dec 2, 2009, at 12:32 PM, Ken Dyck 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?
>
> Adding the types to MVT (and ValueTypes.td) would allow LLVM to be
> targeted to architectures that have registers and operations of these
> sizes (for example, a 24-bit DSP that I'd like to develop a back end  
> for
> has 24-, 48- and 56-bit native integer types). Back ends are currently
> limited to using power-of-2 types in their TableGen descriptions.
I'm fine with doing this, but please only add the MVT types you  
actually need.  Don't bother adding i40 unless you support i40.  If  
someone needs it in the future, we can add it at that point.

Thanks Ken,

-Chris

Hi Ken,
> 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?
the type legalizer would need some work.  Consider an architecture which has a
24 bit register.  Then the type legalizer should legalize an i40 by first
promoting it to an i48, then expanding that to two lots of i24.

Another issue is how vectors of i24 would be represented in memory.  Would
successive vector elements be 3 bytes apart or 4 bytes apart?  The current
code for vector codegen assumes that vectors are tightly packed (this is
already wrong for x86 long double).

Ciao,

Duncan.

On Wednesday, December 02, 2009 3:45 PM, Micah Villmow
wrote:
>
> On Wednesday, December 02, 2009 12:33 PM, Ken Dyck wrote:
>
> > The main drawback of adding the new types is the extra 
> > burden it would 
> > put on back ends that don't use them, since they would need to add
> > special lowering code for all the types they don't use. On 
> > the other 
> > hand, it opens the possibility of targeting architectures that LLVM 
> > previously couldn't.
>
> Instead of putting the burden on the back-ends to implement 
> special lowering code, why not implement code in the 
> legalizer that would automatically sign extend them to the 
> next largest power of 2 integer if the specific integer types 
> were not supported. This would then remove the need of the 
> back-ends to implement anything as LLVM would just generate 
> extend the values to i32/i64 silently.
I agree. It would be ideal to limit the changes to the legalizer. I've
been working on this in a private branch for a little while and so far I
haven't figured out a way to make it work. I'm fairly new to LLVM,
though, so there's a good chance my failure is due to a personal lack of
understanding rather than some fundamental technical issue. I'll keep
working on it.  

-Ken

On Wednesday, December 02, 2009 7:09 PM, Chris Lattner
wrote:
> 
> On Dec 2, 2009, at 12:32 PM, Ken Dyck 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?
> >
> > Adding the types to MVT (and ValueTypes.td) would allow LLVM to be 
> > targeted to architectures that have registers and 
> operations of these 
> > sizes (for example, a 24-bit DSP that I'd like to develop a 
> back end 
> > for has 24-, 48- and 56-bit native integer types). Back ends are 
> > currently limited to using power-of-2 types in their TableGen 
> > descriptions.
> 
> I'm fine with doing this, but please only add the MVT types 
> you actually need.  Don't bother adding i40 unless you 
> support i40.  If someone needs it in the future, we can add 
> it at that point.
Judging from a comment near the end of BlackfinRegisterInfo.td, it looks
like the Blackfin back end could make use i40. Would you still like it
left out?

-Ken

On Thursday, December 03, 2009 3:52 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?
> 
> the type legalizer would need some work.  Consider an 
> architecture which has a
> 24 bit register.  Then the type legalizer should legalize an 
> i40 by first promoting it to an i48, then expanding that to 
> two lots of i24.
>From what I can tell, this is mostly a matter of making sure that the
lowering tables in TargetLowering are initialized correctly in
computeRegisterProperties(). The rest of it is finding the code that are
bypassing these lowering tables to legalize types.
 
> Another issue is how vectors of i24 would be represented in 
> memory.  Would successive vector elements be 3 bytes apart or 
> 4 bytes apart?  The current code for vector codegen assumes 
> that vectors are tightly packed (this is already wrong for 
> x86 long double).
FWIW, I would hope they continue to be packed. Otherwise, they would be
very difficult to process efficiently on native 24-bit machines. On
architectures without 24-bit types, I guess it would be up to the
legalizer to generate code to pad them appropriately in a promotion to
an i32 vector.

-Ken

>> 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.

Grr...


---------- Forwarded message ----------
From: OvermindDL1 <overminddl1 at gmail.com>
Date: Sat, Dec 5, 2009 at 5:58 PM
Subject: Re: [LLVMdev] Adding multiples-of-8 integer types to MVT
To: Duncan Sands <duncan.sands at math.u-psud.fr>


On Sat, Dec 5, 2009 at 5:33 AM, Duncan Sands
<duncan.sands at math.u-psud.fr> 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.
>
> 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.
This makes the most sense to me as well.  I have used some embedded
chips (long time ago, but still...) that had a 7-bit wide bus and
register setup, certainly not a power of 2, not even even.

ya, when you targeting some backend like FPGA, you are able to meet a
integer with any bitwitdh.

On Sun, Dec 6, 2009 at 8:58 AM, OvermindDL1 <overminddl1 at gmail.com>
wrote:
> Grr...
>
>
> ---------- Forwarded message ----------
> From: OvermindDL1 <overminddl1 at gmail.com>
> Date: Sat, Dec 5, 2009 at 5:58 PM
> Subject: Re: [LLVMdev] Adding multiples-of-8 integer types to MVT
> To: Duncan Sands <duncan.sands at math.u-psud.fr>
>
>
> On Sat, Dec 5, 2009 at 5:33 AM, Duncan Sands
> <duncan.sands at math.u-psud.fr> 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.
>>
>> 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.
>
> This makes the most sense to me as well.  I have used some embedded
> chips (long time ago, but still...) that had a 7-bit wide bus and
> register setup, certainly not a power of 2, not even even.
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

---------- Forwarded message ----------
From: OvermindDL1 <overminddl1 at gmail.com>
Date: Sat, Dec 5, 2009 at 8:12 PM
Subject: Re: [LLVMdev] Fwd: Adding multiples-of-8 integer types to MVT
To: ether zhhb <etherzhhb at gmail.com>


On Sat, Dec 5, 2009 at 7:24 PM, ether zhhb <etherzhhb at gmail.com>
wrote:
> ya, when you targeting some backend like FPGA, you are able to meet a
> integer with any bitwitdh.
That is a *very* good point.  Since most FPGA boards are configurable
right down to the bitwidth of the lines, any possible bitwidth could
possibly exist.