Array allocation in compiler

Question

I'm writing a compiler for a subset of C. I'm trying to implement arrays but I'm stuck on how to know when to allocate space on the stack for my array when the size of the array is not known at compile time.

An array for which I know the size at compile time can be declared using the .space directive. Otherwise, I could allocate the space on my stack as well by decrementing %esp and using that as an address.

However, suppose following code:

int f(int param)
{
    int x;
    x = 2;
    if(param < x)
    {
        // Array declareren van compile time onbekende grootte 
        int new_array[g(param)];
     }
}

There is no way to declare the array at compile time.

The intermediate representation I am using is three address code. So my initial thought would be to create a three adress code statement like ARRAYALLOC _var1 wher _var1 would be the result of the expression that determines the size of the array. This would then allow me, while emitting x86 code, to insert statements that free up space in the stack.

However, I feel that this might not be the idiomatic way of approaching things. Google has left me stranded on this issue.

Could anybody elaborate?

Note: this compiler is a toy compiler. I have learned most things to do it on my own. I.e., it is by far a professional approach and allocating arrays on the stack is not an issue.

The absolute simplest way would just be to subtract the size from esp. That would give you enough space on the stack to put all of the elements and can be done as soon as you know the array size. — sircodesalot, Jun 21 '14 at 23:58
If this is a subset of C then the compiler doesn't know how big an array is, unless it's a statically initialized array. — Hot Licks, Jun 22 '14 at 00:01

score 1 · Answer 1 · answered Jun 22 '14 at 00:05

One possible way, when you know the size of the array, subtract that amount from esp. Then simply fill in the array items by offset. You could do something like:

; Enter the frame
push ebp
mov ebp, esp
sub esp, <The size of the array>

... Code code code ...

mov [ebp - 4], 1 ; Put '1' in the first slot (Assuming size int32)
mov [ebp - 8], 2 ; Put '2' in the second slot
mov eax, [ebp - 12]  ; Grab element 3

; Exit the frame
add esp, <Size of the array>
pop esp

score 1 · Accepted Answer · answered Jun 22 '14 at 02:21

1

You need to allocate space on the stack dynamically by subtracting from %esp the size of the array once you know what it is. You might end up with something like:

; start of function f
f:
    push ebp
    mov  ebp, esp
    sub  esp, <size of other local vars>
            :
    cmp  dword ptr [ebp+8], 2    ; compare param with 2
    bge  label_after_if
    push dword ptr [ebp+8]
    call g
    add  esp,4
    shl  eax, 2    ; compute size of new_array
    sub  esp, eax  ; allocate space -- new_array is at esp
          :
label_after_if:
    mov  esp, ebp
    pop  ebp
    ret

answered Jun 22 '14 at 02:21

Chris Dodd

119,907
13
134
226

1

Your trick of deallocating all space at exit is standard practice. However, OP needs additional code to *remove* the array from the stack control exits the *scope* that allocated it. Otherwise a loop wrapped around the scope would allocate an indefinitely large amount of memory. – Ira Baxter Jun 22 '14 at 03:02
@IraBaxter: only needed if there's a loop -- with no loop (as in the example), it is not needed. – Chris Dodd Jun 22 '14 at 04:16
1

Or a call to *any* function after the scope closes, because that might be a recursive call and thus form a loop (unless the compiler can prove otherwise, pretty hard for C). – Ira Baxter Jun 22 '14 at 08:54
If there's a recursive call, it might overflow the stack regardless. There's no need for the compiler to clean up the stack more than normal in that case. – Chris Dodd Jun 22 '14 at 20:03
1

There's also no excuse for the compiler to leave stack space allocated which is dead. If it does so, the total stack demand can go up considerably, even if the recursion is well-bounded. When building embedded systems, having enough stack space is often a critical problem. – Ira Baxter Jun 22 '14 at 20:09
1

It is common for compilers to 'batch up' stack allocations and only do a single manipulation of the stack pointer to allocate or free multiple objects. As you say, it's a tradeoff, but usually speed wins over space. – Chris Dodd Jun 22 '14 at 20:12

Array allocation in compiler

2 Answers2

Linked