LLVM alloca causes stack overflow on while statement

Question

I am implementing a frontend compiler for a toy language targeting LLVM-IR and I encounter a stack overflow when running compiled while statements:

For example, this code should run forever but our compiled version stack-overflows after some time.

def run(): Void = {
    i = 0;
    while(true) {
        i = i + 1;
    }
}

And here is the comipled LLVM-IR:

define i32 @run() nounwind ssp {
    ; i = 0
    %i = alloca i32, align 4
    %1 = alloca i32, align 4
    store i32 0, i32* %1, align 4
    %2 = load i32* %1, align 4
    store i32 %2, i32* %i, align 4
    br label %3

; <label>: %3
    ; while(true)
    ; Generated by compileExpression(condition)
    %4 = alloca i1, align 4
    store i1 true, i1* %4, align 4
    %5 = load i1* %4, align 4
    br i1 %5, label %6, label %11

; <label>: %6
    ; i = i + 1
    ; Generated by compileExpression(body)
    %7 = load i32* %i, align 4
    %8 = alloca i32, align 4
    store i32 1, i32* %8, align 4
    %9 = load i32* %8, align 4
    %10 = add nsw i32 %7, %9
    store i32 %10, i32* %i, align 4
    br label %3

; <label>: %11
    %12 = load i32* %i, align 4
    ret i32 %12
}

We think our problem comes from every alloca that are not released because we are still in the same function.

LLVM Documentation:

'alloca'd memory is automatically released when the function returns.

How should we compile the while loop?
Can we avoid this problem?

Oak Oak · Accepted Answer · 2014-01-09T18:02:12

You generate bad IR: specifically, alloca in a loop is a bad idea, and can indeed cause a stack overflow.

What I would expect to see is an alloca outside the loop, then a load, add and store sequence inside the loop. Later on you can run the mem2reg pass, which will get rid of the allocas and convert the load and store to a more efficient phi.

Same thing for your alloca for the while condition: You need to do the same, prepare memory in advance and inside the loop only store to it.

LLVM alloca causes stack overflow on while statement

3 Answers