LLVM IR optimization of nested functions

Question

I'm writing a compiler for a toy functional language by generating LLVM IR code. However, I'm having some issues optimizing cases with nested functions.

Functions and operators are curried, so y = 10 + 20 is performed as f = plus(10); y = f(20). So far, the LLVM optimization passes have been smart enough to optimize the above to just ret i32 30.

Once I added support for nested functions (by lambda-lifting with an additional env argument for the free identifiers), LLVM could no longer optimize even simple examples like above.

Here's how the nested functions work: when a nested function is called, every free variable it needs are written into an array of pointers (env) and passed to the nested function. The nested function loads env and reads each index into a local register. I would expect the optimizer to in-line the call and then eliminate the redundant storing and re-loading of env. The optimizer inlines the call but can't eliminate the envs.

A minimal example of the original and optimized code is below:

declare i8* @malloc(i32)

@x = private constant i32 42

define i32 @main() {
  %env_pass = insertvalue [1 x i32*] zeroinitializer, i32* @x, 0
  %env_pass_ptr = call i8* @malloc(i32 8)
  %env_pass_cast = bitcast i8* %env_pass_ptr to [1 x i32*]*
  store [1 x i32*] %env_pass, [1 x i32*]* %env_pass_cast
  %res = call i32 @nested_func(i8* %env_pass_ptr)
  ret i32 %res
}

define private i32 @nested_func(i8* %env) {
  %env_ptr = bitcast i8* %env to [1 x i32*]*
  %env_val = load [1 x i32*]* %env_ptr
  %my_x = extractvalue [1 x i32*] %env_val, 0
  %val = load i32* %my_x
  ret i32 %val
}

Optimizing to:

@x = private constant i32 42

declare noalias i8* @malloc(i32) #0

define i32 @main() #0 {
  %env_pass_ptr = tail call i8* @malloc(i32 8)
  %env_pass_cast = bitcast i8* %env_pass_ptr to [1 x i32*]*
  store [1 x i32*] [i32* @x], [1 x i32*]* %env_pass_cast
  %1 = getelementptr inbounds [1 x i32*]* %env_pass_cast, i32 0, i32 0
  %2 = load i32** %1
  %val.i = load i32* %2
  ret i32 %val.i
}

attributes #0 = { nounwind }

This example ought to reduce down to just ret i32 42. I suspect the problem is with getelementptr, which is produced by the optimizer.

Here's some pastes of the full original and optimized code for the expression 10 + 20: original, optimized

In this case I could choose to not pass the 'add' function in the environment, as it's a global. However, I would still expect this example to optimize correctly.

Felix Chapman Felix Chapman · Accepted Answer · 2015-04-15T21:58:57

I found the problem was lessened if I instead wrote directly to the indices with getelementptr, instead of using insertvalue. This came about after finding this other question suggesting LLVM isn't great at optimizing insertvalue.

After using getelementptr, the example above reduces to ret i32 42 and now more basic arithmetic in my language is reduced to a constant. Methods that use more than one operator (e.g. (10+20)*5) still don't reduce completely.

LLVM IR optimization of nested functions

2 Answers