LLVM Code Generation

Now we write the code that turns our typed AST into LLVM IR. We use the inkwell library, which provides safe Rust bindings to LLVM.

The CodeGen Structure

Our code generator keeps track of several things:

/// Code generator state
pub struct CodeGen<'ctx> {
    context: &'ctx Context,
    module: Module<'ctx>,
    builder: Builder<'ctx>,
    /// Map from variable names to their stack allocations
    variables: HashMap<String, PointerValue<'ctx>>,
    /// Map from function names to LLVM functions
    functions: HashMap<String, FunctionValue<'ctx>>,
    /// Current function being compiled
    current_fn: Option<FunctionValue<'ctx>>,
}

secondlang/src/codegen.rs

Let us understand each field:

• context - The LLVM context. All LLVM objects belong to a context. Think of it as the “workspace” for LLVM.
• module - A container for functions. Think of it as a single source file or compilation unit.
• builder - The tool we use to create IR instructions. We position it in a basic block and it adds instructions there.
• variables - Maps variable names to their stack locations (pointers from alloca). When we see x, we look it up here to find where it lives in memory.
• functions - Maps function names to their LLVM function objects. Needed so we can call functions by name.
• current_fn - The function we are currently compiling. Needed to create new basic blocks for conditionals and loops.

The Compilation Process

Compilation happens in three passes:

    /// Compile a program and return the module
    pub fn compile(&mut self, program: &Program) -> Result<(), String> {
        // First pass: declare all functions
        for stmt in program {
            if let Stmt::Function {
                name,
                params,
                return_type,
                ..
            } = stmt
            {
                self.declare_function(name, params, return_type)?;
            }
        }

        // Second pass: compile function bodies only (not top-level expressions)
        for stmt in program {
            if let Stmt::Function { .. } = stmt {
                self.compile_stmt(stmt)?;
            }
        }

        // Third pass: create __main wrapper for top-level expression
        if let Some(Stmt::Expr(expr)) = program.last() {
            self.compile_main_wrapper(expr)?;
        }

        // Verify module
        self.module
            .verify()
            .map_err(|e| format!("Module verification failed: {}", e.to_string()))?;

        Ok(())
    }

secondlang/src/codegen.rs

Pass 1: Declare all functions

Before we can compile function bodies, we need to know about all functions. Why? Because foo might call bar, and bar might call foo. We declare all functions first so calls can find their targets.

A function declaration tells LLVM “there is a function with this name and signature” but does not include the body yet.

Pass 2: Compile function bodies

Now we go through each function and generate its body - the actual instructions.

Pass 3: Create the __main wrapper

If there is a top-level expression (like fib(10)), we wrap it in a __main function. This gives the JIT an entry point to call.

Verify the module

Finally, we ask LLVM to verify that our IR is well-formed. This catches bugs in our code generator.

Compiling Expressions

The heart of code generation is compile_expr. It takes a typed expression and produces an LLVM value:

    /// Compile an expression
    fn compile_expr(&mut self, expr: &TypedExpr) -> Result<IntValue<'ctx>, String> {
        match &expr.expr {
            Expr::Int(n) => Ok(self.context.i64_type().const_int(*n as u64, false)),

            Expr::Bool(b) => Ok(self.context.bool_type().const_int(*b as u64, false)),

            Expr::Var(name) => {
                let ptr = self
                    .variables
                    .get(name)
                    .ok_or_else(|| format!("Undefined variable: {}", name))?;
                let val = self
                    .builder
                    .build_load(self.context.i64_type(), *ptr, name)
                    .unwrap();
                Ok(val.into_int_value())
            }

            Expr::Unary { op, expr: inner } => {
                let val = self.compile_expr(inner)?;
                match op {
                    UnaryOp::Neg => Ok(self.builder.build_int_neg(val, "neg").unwrap()),
                    UnaryOp::Not => Ok(self.builder.build_not(val, "not").unwrap()),
                }
            }

            Expr::Binary { op, left, right } => {
                let l = self.compile_expr(left)?;
                let r = self.compile_expr(right)?;

                match op {
                    BinaryOp::Add => Ok(self.builder.build_int_add(l, r, "add").unwrap()),
                    BinaryOp::Sub => Ok(self.builder.build_int_sub(l, r, "sub").unwrap()),
                    BinaryOp::Mul => Ok(self.builder.build_int_mul(l, r, "mul").unwrap()),
                    BinaryOp::Div => Ok(self.builder.build_int_signed_div(l, r, "div").unwrap()),
                    BinaryOp::Mod => Ok(self.builder.build_int_signed_rem(l, r, "mod").unwrap()),
                    BinaryOp::Lt => {
                        let cmp = self
                            .builder
                            .build_int_compare(IntPredicate::SLT, l, r, "lt")
                            .unwrap();
                        Ok(self
                            .builder
                            .build_int_z_extend(cmp, self.context.i64_type(), "ext")
                            .unwrap())
                    }
                    BinaryOp::Gt => {
                        let cmp = self
                            .builder
                            .build_int_compare(IntPredicate::SGT, l, r, "gt")
                            .unwrap();
                        Ok(self
                            .builder
                            .build_int_z_extend(cmp, self.context.i64_type(), "ext")
                            .unwrap())
                    }
                    BinaryOp::Le => {
                        let cmp = self
                            .builder
                            .build_int_compare(IntPredicate::SLE, l, r, "le")
                            .unwrap();
                        Ok(self
                            .builder
                            .build_int_z_extend(cmp, self.context.i64_type(), "ext")
                            .unwrap())
                    }
                    BinaryOp::Ge => {
                        let cmp = self
                            .builder
                            .build_int_compare(IntPredicate::SGE, l, r, "ge")
                            .unwrap();
                        Ok(self
                            .builder
                            .build_int_z_extend(cmp, self.context.i64_type(), "ext")
                            .unwrap())
                    }
                    BinaryOp::Eq => {
                        let cmp = self
                            .builder
                            .build_int_compare(IntPredicate::EQ, l, r, "eq")
                            .unwrap();
                        Ok(self
                            .builder
                            .build_int_z_extend(cmp, self.context.i64_type(), "ext")
                            .unwrap())
                    }
                    BinaryOp::Ne => {
                        let cmp = self
                            .builder
                            .build_int_compare(IntPredicate::NE, l, r, "ne")
                            .unwrap();
                        Ok(self
                            .builder
                            .build_int_z_extend(cmp, self.context.i64_type(), "ext")
                            .unwrap())
                    }
                }
            }

            Expr::Call { name, args } => {
                let function = self
                    .functions
                    .get(name)
                    .cloned()
                    .ok_or_else(|| format!("Undefined function: {}", name))?;

                let arg_values: Vec<BasicMetadataValueEnum> = args
                    .iter()
                    .map(|a| self.compile_expr(a).map(|v| v.into()))
                    .collect::<Result<_, _>>()?;

                let call = self
                    .builder
                    .build_call(function, &arg_values, "call")
                    .unwrap();
                Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
            }

            Expr::If {
                cond,
                then_branch,
                else_branch,
            } => {
                let cond_val = self.compile_expr(cond)?;
                // Convert to i1 for branch
                let cond_bool = self
                    .builder
                    .build_int_truncate(cond_val, self.context.bool_type(), "cond")
                    .unwrap();

                let function = self.current_fn.unwrap();
                let then_bb = self.context.append_basic_block(function, "then");
                let else_bb = self.context.append_basic_block(function, "else");
                let merge_bb = self.context.append_basic_block(function, "merge");

                self.builder
                    .build_conditional_branch(cond_bool, then_bb, else_bb)
                    .unwrap();

                // Then branch
                self.builder.position_at_end(then_bb);
                let mut then_val = self.context.i64_type().const_int(0, false);
                for stmt in then_branch {
                    if let Some(v) = self.compile_stmt(stmt)? {
                        then_val = v;
                    }
                }
                let then_end = self.builder.get_insert_block().unwrap();
                let then_has_terminator = then_end.get_terminator().is_some();
                if !then_has_terminator {
                    self.builder.build_unconditional_branch(merge_bb).unwrap();
                }

                // Else branch
                self.builder.position_at_end(else_bb);
                let mut else_val = self.context.i64_type().const_int(0, false);
                for stmt in else_branch {
                    if let Some(v) = self.compile_stmt(stmt)? {
                        else_val = v;
                    }
                }
                let else_end = self.builder.get_insert_block().unwrap();
                let else_has_terminator = else_end.get_terminator().is_some();
                if !else_has_terminator {
                    self.builder.build_unconditional_branch(merge_bb).unwrap();
                }

                // Merge - only if at least one branch reaches it
                if then_has_terminator && else_has_terminator {
                    // Both branches return/terminate, merge block is unreachable
                    // Remove it and return a dummy value
                    unsafe {
                        merge_bb.delete().unwrap();
                    }
                    // Return a dummy value - the actual return happened in the branches
                    Ok(self.context.i64_type().const_int(0, false))
                } else {
                    self.builder.position_at_end(merge_bb);
                    let phi = self
                        .builder
                        .build_phi(self.context.i64_type(), "phi")
                        .unwrap();

                    // Only add incoming from branches that don't have terminators
                    if !then_has_terminator {
                        phi.add_incoming(&[(&then_val, then_end)]);
                    }
                    if !else_has_terminator {
                        phi.add_incoming(&[(&else_val, else_end)]);
                    }

                    Ok(phi.as_basic_value().into_int_value())
                }
            }

            Expr::While { cond, body } => {
                let function = self.current_fn.unwrap();
                let cond_bb = self.context.append_basic_block(function, "while_cond");
                let body_bb = self.context.append_basic_block(function, "while_body");
                let end_bb = self.context.append_basic_block(function, "while_end");

                self.builder.build_unconditional_branch(cond_bb).unwrap();

                // Condition
                self.builder.position_at_end(cond_bb);
                let cond_val = self.compile_expr(cond)?;
                let cond_bool = self
                    .builder
                    .build_int_truncate(cond_val, self.context.bool_type(), "cond")
                    .unwrap();
                self.builder
                    .build_conditional_branch(cond_bool, body_bb, end_bb)
                    .unwrap();

                // Body
                self.builder.position_at_end(body_bb);
                for stmt in body {
                    self.compile_stmt(stmt)?;
                }
                if self
                    .builder
                    .get_insert_block()
                    .unwrap()
                    .get_terminator()
                    .is_none()
                {
                    self.builder.build_unconditional_branch(cond_bb).unwrap();
                }

                // End
                self.builder.position_at_end(end_bb);
                Ok(self.context.i64_type().const_int(0, false))
            }

            Expr::Block(stmts) => {
                let mut last_val = self.context.i64_type().const_int(0, false);
                for stmt in stmts {
                    if let Some(v) = self.compile_stmt(stmt)? {
                        last_val = v;
                    }
                }
                Ok(last_val)
            }
        }
    }

secondlang/src/codegen.rs

Let us walk through the important cases:

Integers and Booleans

Expr::Int(n) => Ok(self.context.i64_type().const_int(*n as u64, false)),
Expr::Bool(b) => Ok(self.context.bool_type().const_int(*b as u64, false)),

Constants are simple. We create a constant integer value of the right type. The false argument means the value is unsigned (we use signed arithmetic in operations).

Variables: The Alloca/Load Pattern

Expr::Var(name) => {
    let ptr = self.variables.get(name)
        .ok_or_else(|| format!("Undefined variable: {}", name))?;
    let val = self.builder.build_load(self.context.i64_type(), *ptr, name)?;
    Ok(val.into_int_value())
}

Variables are stored on the stack using the alloca/load/store pattern we discussed in the IR chapter:

1. When we declare a variable, we use alloca to reserve stack space and store the pointer
2. When we read a variable, we load from that pointer
3. When we write a variable, we store to that pointer

This pattern handles mutable variables naturally and LLVM optimizes it away when possible (promoting stack slots to registers).

Binary Operations

Expr::Binary { op, left, right } => {
    let l = self.compile_expr(left)?;  // compile left operand
    let r = self.compile_expr(right)?; // compile right operand

    match op {
        BinaryOp::Add => Ok(self.builder.build_int_add(l, r, "add")?),
        BinaryOp::Sub => Ok(self.builder.build_int_sub(l, r, "sub")?),
        // ... etc
    }
}

We recursively compile left and right operands, then emit the appropriate instruction. The "add" string is a name for the result (helps when reading the IR).

Function Calls

Expr::Call { name, args } => {
    let function = self.functions.get(name)
        .ok_or_else(|| format!("Undefined function: {}", name))?;

    let arg_values: Vec<_> = args.iter()
        .map(|a| self.compile_expr(a).map(|v| v.into()))
        .collect::<Result<_, _>>()?;

    let call = self.builder.build_call(*function, &arg_values, "call")?;
    Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
}

We look up the function, compile each argument, then emit a call instruction.

The try_as_basic_value().unwrap_basic() deserves explanation. In LLVM, function calls can return either:

• A “basic value” (like an integer or pointer) that we can use
• Nothing (for void functions)

try_as_basic_value() returns an enum with both possibilities. Since our functions always return int, we know we have a basic value and can safely unwrap it. The into_int_value() converts it to the specific integer type we need.

Conditionals

Conditionals need multiple basic blocks:

Expr::If { cond, then_branch, else_branch } => {
    // Compile condition and convert to i1 for branching
    let cond_val = self.compile_expr(cond)?;
    let cond_bool = self.builder.build_int_truncate(cond_val, self.context.bool_type(), "cond")?;

    // Create basic blocks for then, else, and merge
    let function = self.current_fn.unwrap();
    let then_bb = self.context.append_basic_block(function, "then");
    let else_bb = self.context.append_basic_block(function, "else");
    let merge_bb = self.context.append_basic_block(function, "merge");

    // Branch based on condition
    self.builder.build_conditional_branch(cond_bool, then_bb, else_bb)?;

    // Compile then branch
    self.builder.position_at_end(then_bb);
    // ... compile statements ...
    self.builder.build_unconditional_branch(merge_bb)?;

    // Compile else branch
    self.builder.position_at_end(else_bb);
    // ... compile statements ...
    self.builder.build_unconditional_branch(merge_bb)?;

    // Continue at merge point
    self.builder.position_at_end(merge_bb);
    // ... use phi node to select result ...
}

The key insight: we create separate basic blocks, compile each branch by positioning the builder at the right block, then use a phi node to merge the results.

Remember from the IR chapter: a phi node selects a value based on which block we came from. If the condition was true and we came from then_bb, use the then-result. Otherwise use the else-result.

JIT Execution

Finally, we can run our compiled code:

/// JIT compile and run a program
pub fn jit_run(program: &Program) -> Result<i64, String> {
    let context = Context::create();
    let mut codegen = CodeGen::new(&context, "secondlang");

    codegen.compile(program)?;

    // Create execution engine
    let engine = codegen
        .module
        .create_jit_execution_engine(OptimizationLevel::Default)
        .map_err(|e| format!("Failed to create JIT: {}", e.to_string()))?;

    // Call the __main wrapper function which contains the top-level expression
    unsafe {
        let func: inkwell::execution_engine::JitFunction<unsafe extern "C" fn() -> i64> =
            engine.get_function("__main").map_err(|e| e.to_string())?;
        Ok(func.call())
    }
}

secondlang/src/codegen.rs

This function:

1. Creates a code generator
2. Compiles the program to IR
3. Creates a JIT execution engine
4. Gets a pointer to __main (our entry point)
5. Calls it and returns the result

The JIT engine compiles our IR to native machine code on the fly, then executes it. This is much faster than interpretation because we are running actual machine code, not walking a tree.

The unsafe block is required because we are calling raw machine code. We have to trust that our code generator produced valid code.

Putting It All Together

Here is what happens when you run cargo run -- examples/fibonacci.sl:

1. Parse the source file → Typed AST (with Unknown types)
2. Type check → Typed AST (all types resolved)
3. Optimize (optional) → Simplified AST
4. Compile → LLVM IR
5. JIT → Native machine code
6. Execute → Result

All in a fraction of a second.

Testing

rustup run nightly cargo test compile

In the next chapter, we put it all together and run Fibonacci.