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

From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu]

On Behalf Of Ken Dyck

Sent: Wednesday, December 02, 2009 12:33 PM

To: llvmdev@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

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

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.

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

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

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.

I also agree that the type legalizer is the place to take care of it.

This would be straightforward for someone who has experience with the

type legalizer - the problem is finding someone with some spare time!

Ciao,

Duncan.

I'd prefer to leave it out. When the blackfin backend needs it, it should be easy to add then.

-Chris

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

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.

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.

This is actually exactly what I was proposing. Apparently I didn't

express it clearly enough, though. I'm glad to see that we agree,

anyways.

-Ken