On Wed, Jul 16, 2008 at 8:19 PM, Bill Wendling <isanbard at gmail.com> wrote:> On Wed, Jul 16, 2008 at 11:07 AM, HyperQuantum <hyperquantum at gmail.com> wrote: >> How can I allocate an array with a size that is not known at compile time?> Do you mean a variable length array (as in C99) or something else?I guess I should have explained what I'm trying to do. I'm working on a front end for my programming language and using the LLVM libraries as back end. The arrays in my language are currently represented by an LLVM structure type that contains integer fields to hold the size for each array dimension, and then an array type with the actual data for the array. A simple example, an array with 3 integers: var x : [3] int For this example the following code is generated: %x = alloca { i32, [3 x i32] } ; <{ i32, [3 x i32] }*> [#uses=4] getelementptr { i32, [3 x i32] }* %x, i32 0, i32 0 ; <i32*>:1 [#uses=1] store i32 3, i32* %1 (and followed by a loop that initializes the three elements) But I only tested this with arrays that have an integer constant as size. Now if I try it with a size that comes from an expression like this: var size : nat = 9 var x : [size] int Then my compiler does not know the size of the array and uses a zero for the type: %size = alloca i32 ; <i32*> [#uses=2] store i32 9, i32* %size %x = alloca { i32, [0 x i32] } ; <{ i32, [0 x i32] }*> [#uses=4] load i32* %size ; <i32>:1 [#uses=1] getelementptr { i32, [0 x i32] }* %x, i32 0, i32 0 ; <i32*>:2 [#uses=1] store i32 %1, i32* %2 Obviously this is wrong, but I don't see how I can use the value from 'size' to allocate the necessary space for this array with alloca. I could use a pointer to an array in the struct type, instead of a direct array, and use two allocas (one for the struct and one for the array data). But then there is no real reason to use the array type anymore, a pointer to the first element (like llvm-gcc generates for C/C++ arrays) would be much simpler. Or am I missing something? Regards, Kevin André
On Wed, Jul 16, 2008 at 1:13 PM, HyperQuantum <hyperquantum at gmail.com> wrote:> > I guess I should have explained what I'm trying to do. I'm working on > a front end for my programming language and using the LLVM libraries > as back end. The arrays in my language are currently represented by an > LLVM structure type that contains integer fields to hold the size for > each array dimension, and then an array type with the actual data for > the array. > > A simple example, an array with 3 integers: > > var x : [3] int > > For this example the following code is generated: > > %x = alloca { i32, [3 x i32] } ; <{ i32, [3 x i32] }*> [#uses=4] > getelementptr { i32, [3 x i32] }* %x, i32 0, i32 0 ; <i32*>:1 [#uses=1] > store i32 3, i32* %1 > > (and followed by a loop that initializes the three elements) > > But I only tested this with arrays that have an integer constant as > size. Now if I try it with a size that comes from an expression like > this: > > var size : nat = 9 > var x : [size] int > > Then my compiler does not know the size of the array and uses a zero > for the type: > > %size = alloca i32 ; <i32*> [#uses=2] > store i32 9, i32* %size > %x = alloca { i32, [0 x i32] } ; <{ i32, [0 x i32] }*> [#uses=4] > load i32* %size ; <i32>:1 [#uses=1] > getelementptr { i32, [0 x i32] }* %x, i32 0, i32 0 ; > <i32*>:2 [#uses=1] > store i32 %1, i32* %2 > > Obviously this is wrong, but I don't see how I can use the value from > 'size' to allocate the necessary space for this array with alloca. I > could use a pointer to an array in the struct type, instead of a > direct array, and use two allocas (one for the struct and one for the > array data). But then there is no real reason to use the array type > anymore, a pointer to the first element (like llvm-gcc generates for > C/C++ arrays) would be much simpler. Or am I missing something? >Okay, so it's more like the second example I gave. The equivalent C program would be something like this: int x = 37; struct a { int f1; int a1[0]; }; int foo(int b, int c) { struct a *s = malloc(sizeof(struct a) + x * sizeof(10)); int i; for (i = 0; i < x; ++i) s->a1[i] = i; return s->a1[b] * c; } int bar(int b, int c, int d) { struct a *s = malloc(sizeof(struct a) + b * sizeof(10)); int i; for (i = 0; i < b; ++i) s->a1[i] = i; return s->a1[c] * d; } Compile this program at -O0 to see the initial code. Then compile it at -O3 to see what it is after optimizations. At -O3, there's still the calls to malloc, but you might not be able to get around that. One thing that gets rid of the malloc in "foo" is to mark x as static. The compile then knows it's size and that it's not modified in the current file, so it can use the value it's been assigned. If your programming language has this capacity, it would improve your code generation. Hope this helps. -bw
Hi,> Obviously this is wrong, but I don't see how I can use the value from > 'size' to allocate the necessary space for this array with alloca. I > could use a pointer to an array in the struct type, instead of a > direct array, and use two allocas (one for the struct and one for the > array data). But then there is no real reason to use the array type > anymore, a pointer to the first element (like llvm-gcc generates for > C/C++ arrays) would be much simpler. Or am I missing something?if the length is %n, you can alloca %n i8's: %x = alloca i8, i32 %n [Well, I guess you need to allocate a bit more to include the overhead of the length field in your struct.] Then bitcast %x (which is an i8*) to a pointer to your struct type. Ciao, Duncan.
> if the length is %n, you can alloca %n i8's: > %x = alloca i8, i32 %nIf the array element type is i32 (like the size field), then you may as well use an alloca i32; if you use an alloca i8 then you would have to use 4*%n rather than %n in order to get the right amount of memory. Ciao, Duncan.