Compiler Optimisation in C++: Constant Folding and Dead Code Elimination

Our compiler now has a complete source-to-executable pipeline. It can tokenise Si source code, build an AST, validate types and scopes, lower the AST into IR, generate x86-64 assembly, link the runtime, and produce a native executable.

Correctness comes first. Once the compiler can reliably preserve program behaviour, the next question is whether it can produce a cheaper equivalent program before machine code is emitted.

In this final chapter, we build a small compiler optimisation pipeline in C++. The optimiser works on the Intermediate Representation and applies four closely related transformations:

• Constant folding.
• Branch simplification.
• Unreachable-block removal.
• Dead instruction elimination.

These passes are deliberately small, but they introduce one of the central ideas of compiler optimisation: repeatedly transform an intermediate representation into a cheaper equivalent form without changing observable program behaviour.

What You Will Learn

By the end of this chapter, you will be able to:

• explain what compiler optimisation is and what makes a transformation valid;
• design a pass-based optimiser for the Si IR;
• fold constant arithmetic, unary operations, and comparisons at compile time;
• propagate known temporary constants within the current IR model;
• simplify branches whose conditions are already known;
• remove control-flow blocks that can no longer be reached;
• eliminate unused pure instructions without deleting observable behaviour;
• preserve trapping and side-effecting operations conservatively;
• insert optimisation cleanly between IR generation and assembly generation;
• test individual optimisation passes and the complete native pipeline.

What Is Compiler Optimisation?

Compiler optimisation transforms a program representation into another form that should be cheaper to execute, easier to analyse, smaller, or more suitable for later stages while preserving the program’s observable behaviour.

A transformation is valid only when it preserves everything the language and runtime make observable, including computed results, function-call side effects, stores, output, control flow, and required runtime traps.

That last point matters in this chapter because an unused division cannot automatically be removed if executing it could still trap.

What Is an Optimisation Pass?

An optimisation pass is one focused transformation or analysis step over the IR.

Pass	Main transformation
Constant folding	Replace operations on known constants with constant results
Branch simplification	Replace a branch on a known boolean with one jump
Unreachable-block removal	Remove basic blocks unreachable from function entry
Dead instruction elimination	Remove unused instructions that are safe to delete

Keeping the passes separate makes each transformation easier to reason about, test, and extend.

How Does an IR Optimisation Pipeline Work?

The optimiser runs after IR generation and before assembly generation:

1. Start with semantically checked, well-formed IR.
2. Fold operations whose inputs are known constants.
3. Simplify branches whose conditions have become constant.
4. Recompute reachability and remove blocks that cannot execute.
5. Remove pure instructions whose results are no longer used.
6. Send the smaller equivalent IR to the existing x86-64 backend.

Each pass can expose opportunities for the next one, so pass ordering matters.

What Is an Optimisation?

An optimisation changes how a program is represented or executed without changing its observable behaviour.

Consider:

let answer: int = 5 + 5;

Without optimisation, the IR might be:

%t0 = const_int 5
%t1 = const_int 5
%t2 = add %t0, %t1
store %t2, answer

The addition does not depend on runtime data. The compiler already knows the result, so it can replace the operation with:

%t2 = const_int 10
store %t2, answer

The program still produces the same value, but the generated machine code no longer needs to perform the addition at runtime.

This transformation is called constant folding.

Why Compilers Optimise an Intermediate Representation

The AST is designed around source-language structure, while assembly is designed around target-machine instructions. The IR sits between those concerns and exposes operations, values, and control flow in a form that is easier to inspect and rewrite safely.

Our complete pipeline becomes:

Si source
   ↓
Lexer
   ↓
Tokens
   ↓
Parser
   ↓
AST
   ↓
Semantic analysis
   ↓
IR generation
   ↓
IR optimisation
   ↓
Assembly generation
   ↓
NASM + linker
   ↓
Native executable

Optimising the IR also keeps the backend simpler. The optimiser reasons about operations such as add, branch and return; the assembly generator can remain focused on translating those operations into x86-64.

Compiler Optimisation Pass Ordering

For this compiler, the passes run in this order:

Constant folding
      ↓
Branch simplification
      ↓
Unreachable-block removal
      ↓
Dead instruction elimination

The ordering matters.

For example, constant folding can turn:

%t0 = const_int 5
%t1 = const_int 2
%t2 = greater %t0, %t1
branch %t2, if_then0, if_else1

into:

%t2 = const_bool true
branch %t2, if_then0, if_else1

Branch simplification can then turn that into:

jump if_then0

Now if_else1 may be unreachable, so the next pass can remove the entire block. Finally, dead instruction elimination can remove constants and temporaries that no longer have any users.

This is a simple example of phase ordering in compiler optimisation: one pass can expose opportunities that a later pass is designed to exploit.

Designing a Pass-Based IROptimiser

Create gsisi/include/IROptimiser.hpp:

#pragma once

#include "IR.hpp"

class IROptimiser {
public:
    void optimise(IRProgram& program) const;

private:
    void constantFold(IRFunction& function) const;
    void simplifyBranches(IRFunction& function) const;
    void removeUnreachableBlocks(IRFunction& function) const;
    void removeDeadInstructions(IRFunction& function) const;

    static bool producesSideEffects(const IRInstruction& instruction) noexcept;
};

The optimiser is intentionally stateless. The same IROptimiser object can therefore optimise multiple programs safely.

Constant Folding in Compiler Optimisation

Constant folding replaces an operation with a constant result when every required operand is already known during compilation.

We will fold:

add
sub
mul
div
negate
not
less
less_equal
greater
greater_equal
equal
not_equal

Arithmetic Example

This IR:

%t0 = const_int 20
%t1 = const_int 22
%t2 = add %t0, %t1

becomes:

%t2 = const_int 42

The old constants may later become dead and disappear in the dead-code pass.

Comparison Example

This IR:

%t0 = const_int 10
%t1 = const_int 5
%t2 = greater %t0, %t1

becomes:

%t2 = const_bool true

That boolean can then drive branch simplification.

Unary Example

These expressions can also be folded:

let x: int = -5;
let b: bool = !false;

For example:

%t0 = const_bool false
%t1 = not %t0

becomes:

%t1 = const_bool true

Preserving 32-bit Integer Semantics During Optimisation

Si currently uses signed 32-bit integers. The backend performs arithmetic with 32-bit x86 registers, so addition, subtraction, multiplication and negation naturally wrap to 32 bits.

The optimiser must preserve that behaviour instead of relying on signed C++ overflow, which is undefined behaviour.

The implementation therefore performs wrapping operations through std::uint32_t bit patterns and converts the result back to std::int32_t.

Division needs even more care. x86 idiv can trap for:

divisor == 0

and for the signed overflow case:

INT_MIN / -1

The optimiser deliberately does not fold either case. Keeping the original div instruction preserves the backend’s runtime behaviour instead of accidentally removing a trap.

This is an important compiler rule:

An optimisation is only valid when it preserves behaviour, including observable errors and traps.

Local Constant Propagation Inside Constant Folding

The optimiser stores known temporary values in a small map:

%t0 -> int 5
%t1 -> int 10
%t2 -> bool true

This works well for our current IR because compiler-generated temporaries are immutable and each temporary has a single definition.

We are not trying to prove that mutable source variables such as x remain constant. Loads and stores still behave normally. A later data-flow chapter could add full constant propagation for mutable values.

Branch Simplification

Once a condition is a constant boolean, a two-way branch no longer needs to make a decision at runtime.

This IR:

%t0 = const_bool true
branch %t0, if_then0, if_else1

can become:

jump if_then0

Likewise:

%t0 = const_bool false
branch %t0, while_body0, while_end1

becomes:

jump while_end1

The branch instruction itself disappears.

Why Clear the Old Branch Fields?

An IRInstruction has fields for several instruction kinds. A Branch uses args, trueTarget and falseTarget, while a Jump only uses target.

When a branch becomes a jump, the optimiser clears the fields that no longer belong to the instruction. Keeping the transformed IR internally clean makes later debugging and validation easier.

Unreachable-Block Elimination

Branch simplification can make entire blocks impossible to reach.

Consider:

while (false) {
    out(999);
}

Before optimisation, the IR still contains a condition block, body block and end block.

After branch simplification, the condition block jumps directly to the end:

while_cond0:
  jump while_end2

while_body1:
  ...

while_end2:
  ...

while_body1 can never execute.

It is important that we remove the entire unreachable block rather than merely deleting unused temporary values inside it. A dead block may contain instructions with side effects such as call out(...); those calls are safe to remove only because the control-flow graph proves the whole block is unreachable.

Reachability Algorithm

The pass starts at the function’s entry block and follows terminators:

jump   -> follow target
branch -> follow true and false targets
return -> stop

Every visited block is reachable. Blocks that are never visited can be erased.

This is a small graph traversal over the function’s control-flow graph.

Dead Instruction Elimination

After folding and control-flow simplification, some pure values may no longer be used.

For example:

%t0 = const_int 5
%t1 = const_int 10
%t2 = add %t0, %t1
%t3 = const_int 0
return %t3

%t2 is unused. Once %t2 disappears, %t0 and %t1 are also unused.

A single deletion pass is not enough because removing one unused result can make its inputs dead as well. The pass therefore repeats until it reaches a fixed point.

After optimisation:

%t3 = const_int 0
return %t3

Side Effects and Traps Must Be Preserved

Dead-code elimination cannot remove an instruction merely because its destination is unused. Some instructions matter because executing them changes program behaviour.

These instructions are always preserved:

store
call
jump
branch
return

They can change program behaviour even when they do not produce a value used by another instruction.

We also conservatively preserve div. An unused division can still trap, so deleting it without proving that the operation is safe could change the behaviour of the program.

This means our dead-code pass is intentionally conservative. A more advanced optimiser could prove that some stores, calls or divisions are safe to remove, but that requires more analysis than we need in this series.

Implementing the IR Optimiser in C++

Create gsisi/src/IROptimiser.cpp:

#include "IROptimiser.hpp"

#include <algorithm>
#include <bit>
#include <cstdint>
#include <limits>
#include <queue>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <unordered_set>

namespace {

struct ConstantValue {
    Type type{Type::Unknown};
    std::int32_t intValue{};
    bool boolValue{};
};

using ConstantMap = std::unordered_map<std::string, ConstantValue>;

std::uint32_t rawBits(std::int32_t value) noexcept {
    return std::bit_cast<std::uint32_t>(value);
}

std::int32_t signedBits(std::uint32_t value) noexcept {
    return std::bit_cast<std::int32_t>(value);
}

std::int32_t wrappingAdd(std::int32_t lhs, std::int32_t rhs) noexcept {
    return signedBits(rawBits(lhs) + rawBits(rhs));
}

std::int32_t wrappingSubtract(std::int32_t lhs, std::int32_t rhs) noexcept {
    return signedBits(rawBits(lhs) - rawBits(rhs));
}

std::int32_t wrappingMultiply(std::int32_t lhs, std::int32_t rhs) noexcept {
    return signedBits(rawBits(lhs) * rawBits(rhs));
}

std::int32_t wrappingNegate(std::int32_t value) noexcept {
    return signedBits(0U - rawBits(value));
}

void clearNonConstantFields(IRInstruction& instruction) {
    instruction.args.clear();
    instruction.callee.clear();
    instruction.target.clear();
    instruction.trueTarget.clear();
    instruction.falseTarget.clear();
}

void replaceWithIntConstant(IRInstruction& instruction, std::int32_t value) {
    instruction.op = IROp::ConstInt;
    instruction.type = Type::Int;
    instruction.intValue = value;
    instruction.boolValue = false;
    clearNonConstantFields(instruction);
}

void replaceWithBoolConstant(IRInstruction& instruction, bool value) {
    instruction.op = IROp::ConstBool;
    instruction.type = Type::Bool;
    instruction.intValue = 0;
    instruction.boolValue = value;
    clearNonConstantFields(instruction);
}

const ConstantValue* findConstant(
    const ConstantMap& constants,
    const std::string& name
) {
    auto found = constants.find(name);
    return found == constants.end() ? nullptr : &found->second;
}

bool isBinaryFoldCandidate(IROp op) noexcept {
    switch (op) {
        case IROp::Add:
        case IROp::Subtract:
        case IROp::Multiply:
        case IROp::Divide:
        case IROp::Less:
        case IROp::LessEqual:
        case IROp::Greater:
        case IROp::GreaterEqual:
        case IROp::Equal:
        case IROp::NotEqual:
            return true;
        default:
            return false;
    }
}

}

void IROptimiser::optimise(IRProgram& program) const {
    for (IRFunction& function : program.functions) {
        constantFold(function);
        simplifyBranches(function);
        removeUnreachableBlocks(function);
        removeDeadInstructions(function);
    }
}

void IROptimiser::constantFold(IRFunction& function) const {
    ConstantMap constants;

    for (IRBlock& block : function.blocks) {
        for (IRInstruction& instruction : block.instructions) {
            if (instruction.op == IROp::ConstInt) {
                constants[instruction.dst] = ConstantValue{
                    Type::Int,
                    static_cast<std::int32_t>(instruction.intValue),
                    false
                };
                continue;
            }

            if (instruction.op == IROp::ConstBool) {
                constants[instruction.dst] = ConstantValue{
                    Type::Bool,
                    0,
                    instruction.boolValue
                };
                continue;
            }

            if (instruction.op == IROp::Negate ||
                instruction.op == IROp::Not) {
                if (instruction.args.size() != 1) {
                    continue;
                }

                const ConstantValue* operand =
                    findConstant(constants, instruction.args[0]);

                if (!operand) {
                    continue;
                }

                if (instruction.op == IROp::Negate &&
                    operand->type == Type::Int) {
                    const std::int32_t result =
                        wrappingNegate(operand->intValue);

                    replaceWithIntConstant(instruction, result);
                    constants[instruction.dst] = ConstantValue{
                        Type::Int, result, false
                    };
                }
                else if (instruction.op == IROp::Not &&
                         operand->type == Type::Bool) {
                    const bool result = !operand->boolValue;

                    replaceWithBoolConstant(instruction, result);
                    constants[instruction.dst] = ConstantValue{
                        Type::Bool, 0, result
                    };
                }

                continue;
            }

            if (!isBinaryFoldCandidate(instruction.op) ||
                instruction.args.size() != 2) {
                continue;
            }

            const ConstantValue* lhs =
                findConstant(constants, instruction.args[0]);
            const ConstantValue* rhs =
                findConstant(constants, instruction.args[1]);

            if (!lhs || !rhs) {
                continue;
            }

            switch (instruction.op) {
                case IROp::Add:
                case IROp::Subtract:
                case IROp::Multiply:
                case IROp::Divide: {
                    if (lhs->type != Type::Int || rhs->type != Type::Int) {
                        break;
                    }

                    if (instruction.op == IROp::Divide &&
                        (rhs->intValue == 0 ||
                         (lhs->intValue == std::numeric_limits<std::int32_t>::min() &&
                          rhs->intValue == -1))) {
                        break;
                    }

                    std::int32_t result{};

                    switch (instruction.op) {
                        case IROp::Add:
                            result = wrappingAdd(lhs->intValue, rhs->intValue);
                            break;
                        case IROp::Subtract:
                            result = wrappingSubtract(lhs->intValue, rhs->intValue);
                            break;
                        case IROp::Multiply:
                            result = wrappingMultiply(lhs->intValue, rhs->intValue);
                            break;
                        case IROp::Divide:
                            result = lhs->intValue / rhs->intValue;
                            break;
                        default:
                            break;
                    }

                    replaceWithIntConstant(instruction, result);
                    constants[instruction.dst] = ConstantValue{
                        Type::Int, result, false
                    };
                    break;
                }

                case IROp::Less:
                case IROp::LessEqual:
                case IROp::Greater:
                case IROp::GreaterEqual: {
                    if (lhs->type != Type::Int || rhs->type != Type::Int) {
                        break;
                    }

                    bool result{};

                    switch (instruction.op) {
                        case IROp::Less:
                            result = lhs->intValue < rhs->intValue;
                            break;
                        case IROp::LessEqual:
                            result = lhs->intValue <= rhs->intValue;
                            break;
                        case IROp::Greater:
                            result = lhs->intValue > rhs->intValue;
                            break;
                        case IROp::GreaterEqual:
                            result = lhs->intValue >= rhs->intValue;
                            break;
                        default:
                            break;
                    }

                    replaceWithBoolConstant(instruction, result);
                    constants[instruction.dst] = ConstantValue{
                        Type::Bool, 0, result
                    };
                    break;
                }

                case IROp::Equal:
                case IROp::NotEqual: {
                    if (lhs->type != rhs->type) {
                        break;
                    }

                    bool equal{};

                    if (lhs->type == Type::Int) {
                        equal = lhs->intValue == rhs->intValue;
                    }
                    else if (lhs->type == Type::Bool) {
                        equal = lhs->boolValue == rhs->boolValue;
                    }
                    else {
                        break;
                    }

                    const bool result =
                        instruction.op == IROp::Equal ? equal : !equal;

                    replaceWithBoolConstant(instruction, result);
                    constants[instruction.dst] = ConstantValue{
                        Type::Bool, 0, result
                    };
                    break;
                }

                default:
                    break;
            }
        }
    }
}

void IROptimiser::simplifyBranches(IRFunction& function) const {
    std::unordered_map<std::string, bool> booleanConstants;

    for (const IRBlock& block : function.blocks) {
        for (const IRInstruction& instruction : block.instructions) {
            if (instruction.op == IROp::ConstBool && !instruction.dst.empty()) {
                booleanConstants[instruction.dst] = instruction.boolValue;
            }
        }
    }

    for (IRBlock& block : function.blocks) {
        for (IRInstruction& instruction : block.instructions) {
            if (instruction.op != IROp::Branch ||
                instruction.args.size() != 1) {
                continue;
            }

            auto found = booleanConstants.find(instruction.args[0]);
            if (found == booleanConstants.end()) {
                continue;
            }

            const std::string target =
                found->second
                    ? instruction.trueTarget
                    : instruction.falseTarget;

            instruction.op = IROp::Jump;
            instruction.type = Type::Void;
            instruction.dst.clear();
            instruction.args.clear();
            instruction.callee.clear();
            instruction.target = target;
            instruction.trueTarget.clear();
            instruction.falseTarget.clear();
        }
    }
}

void IROptimiser::removeUnreachableBlocks(IRFunction& function) const {
    if (function.blocks.empty()) {
        return;
    }

    std::unordered_map<std::string, const IRBlock*> blocks;

    for (const IRBlock& block : function.blocks) {
        if (!blocks.emplace(block.name, &block).second) {
            throw std::runtime_error(
                "IR optimisation error: duplicate block '" + block.name + "'"
            );
        }
    }

    std::unordered_set<std::string> reachable;
    std::queue<std::string> work;

    work.push(function.blocks.front().name);

    while (!work.empty()) {
        std::string name = std::move(work.front());
        work.pop();

        if (!reachable.insert(name).second) {
            continue;
        }

        auto foundBlock = blocks.find(name);
        if (foundBlock == blocks.end()) {
            throw std::runtime_error(
                "IR optimisation error: missing block '" + name + "'"
            );
        }

        const IRBlock& block = *foundBlock->second;

        if (block.instructions.empty()) {
            throw std::runtime_error(
                "IR optimisation error: block '" + name + "' is empty"
            );
        }

        const IRInstruction& terminator = block.instructions.back();

        auto enqueueTarget = [&](const std::string& target) {
            if (!blocks.contains(target)) {
                throw std::runtime_error(
                    "IR optimisation error: block '" + name +
                    "' targets missing block '" + target + "'"
                );
            }

            work.push(target);
        };

        switch (terminator.op) {
            case IROp::Jump:
                enqueueTarget(terminator.target);
                break;

            case IROp::Branch:
                enqueueTarget(terminator.trueTarget);
                enqueueTarget(terminator.falseTarget);
                break;

            case IROp::Return:
                break;

            default:
                throw std::runtime_error(
                    "IR optimisation error: block '" + name +
                    "' does not end in a terminator"
                );
        }
    }

    std::erase_if(
        function.blocks,
        [&](const IRBlock& block) {
            return !reachable.contains(block.name);
        }
    );
}

bool IROptimiser::producesSideEffects(
    const IRInstruction& instruction
) noexcept {
    switch (instruction.op) {
        case IROp::Store:
        case IROp::Call:
        case IROp::Jump:
        case IROp::Branch:
        case IROp::Return:
            return true;

        // idiv can trap on division by zero or INT_MIN / -1.
        // Removing it without proving safety could change behaviour.
        case IROp::Divide:
            return true;

        default:
            return false;
    }
}

void IROptimiser::removeDeadInstructions(IRFunction& function) const {
    bool changed = false;

    do {
        std::unordered_set<std::string> usedValues;

        for (const IRBlock& block : function.blocks) {
            for (const IRInstruction& instruction : block.instructions) {
                for (const std::string& argument : instruction.args) {
                    usedValues.insert(argument);
                }
            }
        }

        changed = false;

        for (IRBlock& block : function.blocks) {
            const auto oldSize = block.instructions.size();

            std::erase_if(
                block.instructions,
                [&](const IRInstruction& instruction) {
                    if (producesSideEffects(instruction)) {
                        return false;
                    }

                    if (instruction.dst.empty()) {
                        return false;
                    }

                    return !usedValues.contains(instruction.dst);
                }
            );

            if (block.instructions.size() != oldSize) {
                changed = true;
            }
        }
    }
    while (changed);
}

There are four important ideas in this implementation:

1. Constant folding replaces known expressions with constant instructions.
2. Branch simplification converts known branches into jumps.
3. Reachability analysis removes blocks that can no longer execute.
4. Iterative dead-code elimination repeatedly removes unused pure value instructions until the IR stops changing.

Updating the Compiler Driver

The optimiser belongs after semantic analysis and IR generation, but before assembly generation.

Update gsisi/src/main.cpp:

#include <filesystem>
#include <fstream>
#include <iostream>
#include <memory>
#include <sstream>
#include <stdexcept>
#include <string>
#include <system_error>
#include <utility>
#include <vector>

#include "AssemblyGenerator.hpp"
#include "BuildDriver.hpp"
#include "IR.hpp"
#include "IRGenerator.hpp"
#include "IROptimiser.hpp"
#include "IRPrinter.hpp"
#include "Lexer.hpp"
#include "Parser.hpp"
#include "SemanticAnalyser.hpp"
#include "Token.hpp"

namespace {

std::string readSourceFile(const std::filesystem::path& path) {
    std::ifstream input(path, std::ios::binary);

    if (!input) {
        throw std::runtime_error(
            "could not open source file '" + path.string() + "'"
        );
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();

    if (input.bad()) {
        throw std::runtime_error(
            "failed while reading source file '" + path.string() + "'"
        );
    }

    return buffer.str();
}

std::filesystem::path compilerDirectory() {
    std::error_code error;
    const std::filesystem::path executable =
        std::filesystem::read_symlink("/proc/self/exe", error);

    if (error) {
        throw std::runtime_error(
            "could not locate the compiler executable: " + error.message()
        );
    }

    return executable.parent_path();
}

void writeAssemblyFile(
    const std::filesystem::path& path,
    const std::string& assembly
) {
    if (!path.parent_path().empty()) {
        std::filesystem::create_directories(path.parent_path());
    }

    std::ofstream output(
        path,
        std::ios::binary | std::ios::trunc
    );

    if (!output) {
        throw std::runtime_error(
            "could not open assembly file '" + path.string() + "'"
        );
    }

    output << assembly;
    output.close();

    if (!output) {
        throw std::runtime_error(
            "failed while writing assembly file '" + path.string() + "'"
        );
    }
}

} // namespace

/**
 * Usage:
 * ./si_compiler <source_file.si> <output_executable>
 */
int main(int argc, char* argv[]) {
    if (argc != 3) {
        std::cerr
            << "Usage: " << argv[0]
            << " <source_file.si> <output_executable>";

        return 1;
    }

    try {
        const std::filesystem::path sourcePath = argv[1];
        const std::filesystem::path executablePath = argv[2];

        std::filesystem::path assemblyPath = executablePath;
        assemblyPath += ".asm";

        const std::filesystem::path runtimePath =
            compilerDirectory() / "libsi" / "out.asm";

        // 1. Lexing
        Lexer lexer(readSourceFile(sourcePath));
        std::vector<Token> tokens = lexer.tokenise();

        // 2. Parsing
        Parser parser(std::move(tokens));
        std::unique_ptr<ProgramNode> ast = parser.parseProgram();

        // 3. Semantic analysis
        SemanticAnalyser analyser;
        analyser.analyze(*ast);

        // 4. IR generation
        IRGenerator irGenerator;
        IRProgram ir = irGenerator.generate(*ast);

        std::cout << "--- IR before optimisation ---";
        dumpIR(std::cout, ir);
        std::cout << "--------------------------------";

        // 5. IR optimisation
        IROptimiser optimiser;
        optimiser.optimise(ir);

        std::cout << "--- IR after optimisation ---";
        dumpIR(std::cout, ir);
        std::cout << "-------------------------------";

        // 6. Assembly generation
        std::ostringstream assemblyBuffer;
        AssemblyGenerator assemblyGenerator;
        assemblyGenerator.generate(ir, assemblyBuffer);

        writeAssemblyFile(assemblyPath, assemblyBuffer.str());

        // 7. Assemble and link
        BuildDriver buildDriver;
        buildDriver.build(
            assemblyPath,
            runtimePath,
            executablePath
        );

        std::cout
            << "Built executable: "
            << executablePath;
    }
    catch (const std::exception& error) {
        std::cerr
            << "Compilation error: "
            << error.what();

        return 1;
    }

    return 0;
}

Generating assembly in memory before replacing the .asm file preserves the fail-before-output behaviour from the backend chapters: parsing, semantic analysis, IR generation, optimisation, and backend validation must all succeed before generated assembly is written.

End-to-End Optimisation Test Program

Keep the end-to-end test program at gsisi/tests/test-7.si:

fn main(): int {
    let folded: int = 5 + 5;

    if (true) {
        out(folded);
    } else {
        out(999);
    }

    while (false) {
        out(888);
    }

    return 0;
}

Without changing its behaviour, the optimiser can:

• Fold 5 + 5 into 10.
• Replace the constant if branch with one jump.
• Remove the unreachable else block.
• Replace the while (false) branch with a jump to the loop end.
• Remove the unreachable loop body, including its out(888) call.
• Remove temporary constants that are no longer used.

The only output should be:

10

Testing the Optimiser

Native tests are useful, but the optimiser also needs focused unit tests. Looking only at program output can hide a broken pass that happens to produce the same result for one example.

Create gsisi/tests/IROptimiserTests.cpp:

#include "IROptimiser.hpp"
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

static void expect(bool c, const char* m) { if(!c) throw std::runtime_error(m); }
static IRInstruction make(IROp op) { IRInstruction i{}; i.op=op; return i; }
IRInstruction ci(std::string d,int v){ auto i=make(IROp::ConstInt); i.type=Type::Int;i.dst=std::move(d);i.intValue=v;return i;}
IRInstruction cb(std::string d,bool v){ auto i=make(IROp::ConstBool); i.type=Type::Bool;i.dst=std::move(d);i.boolValue=v;return i;}
IRInstruction bin(IROp op,std::string d,std::string a,std::string b,Type t){auto i=make(op);i.type=t;i.dst=std::move(d);i.args={std::move(a),std::move(b)};return i;}
IRInstruction ret(std::string a=""){auto i=make(IROp::Return); if(!a.empty())i.args={std::move(a)};return i;}
IRInstruction jump(std::string t){auto i=make(IROp::Jump);i.target=std::move(t);return i;}
IRInstruction branch(std::string c,std::string t,std::string f){auto i=make(IROp::Branch);i.args={std::move(c)};i.trueTarget=std::move(t);i.falseTarget=std::move(f);return i;}
IRInstruction call(std::string c,std::vector<std::string> a={}){auto i=make(IROp::Call);i.callee=std::move(c);i.args=std::move(a);return i;}

IRProgram programOf(std::vector<IRBlock> blocks) {
    IRFunction f; f.name="main"; f.returnType=Type::Int; f.blocks=std::move(blocks);
    IRProgram p; p.functions.push_back(std::move(f)); return p;
}
IRBlock block(std::string n,std::vector<IRInstruction> is){return IRBlock{std::move(n),std::move(is)};}

int main(){
 int passed=0;
 auto run=[&](const char* n, auto fn){try{fn();++passed;std::cout<<"PASS "<<n<<"\n";}catch(const std::exception&e){std::cerr<<"FAIL "<<n<<": "<<e.what()<<"\n";std::exit(1);}};

 run("fold arithmetic", []{
   auto p=programOf({block("entry",{ci("%t0",5),ci("%t1",5),bin(IROp::Add,"%t2","%t0","%t1",Type::Int),ret("%t2")})});
   IROptimiser{}.optimise(p);
   auto &v=p.functions[0].blocks[0].instructions;
   expect(v.size()==2,"expected const + return");
   expect(v[0].op==IROp::ConstInt && v[0].intValue==10 && v[0].dst=="%t2","fold bad");
 });
 run("fold comparison branch and unreachable", []{
   auto p=programOf({
      block("entry",{ci("%a",3),ci("%b",2),bin(IROp::Greater,"%c","%a","%b",Type::Bool),branch("%c","then","else")}),
      block("then",{ci("%x",1),ret("%x")}),
      block("else",{ci("%y",0),ret("%y")})
   });
   IROptimiser{}.optimise(p);
   expect(p.functions[0].blocks.size()==2,"else should be unreachable");
   auto &e=p.functions[0].blocks[0].instructions;
   expect(e.size()==1 && e[0].op==IROp::Jump && e[0].target=="then","branch not simplified");
 });
 run("remove unreachable side effects", []{
   auto p=programOf({
      block("entry",{cb("%c",false),branch("%c","body","end")}),
      block("body",{ci("%x",999),call("out",{"%x"}),jump("end")}),
      block("end",{ci("%z",0),ret("%z")})
   });
   IROptimiser{}.optimise(p);
   expect(p.functions[0].blocks.size()==2,"body should be removed");
   for(auto &b:p.functions[0].blocks) expect(b.name!="body","body remains");
 });
 run("iterative dce", []{
   auto p=programOf({block("entry",{ci("%a",1),ci("%b",2),bin(IROp::Add,"%dead","%a","%b",Type::Int),ci("%r",0),ret("%r")})});
   IROptimiser{}.optimise(p);
   auto &v=p.functions[0].blocks[0].instructions;
   expect(v.size()==2,"dead chain remains");
   expect(v[0].dst=="%r","wrong survivor");
 });
 run("preserve divide by zero", []{
   auto p=programOf({block("entry",{ci("%a",1),ci("%b",0),bin(IROp::Divide,"%q","%a","%b",Type::Int),ci("%r",0),ret("%r")})});
   IROptimiser{}.optimise(p);
   bool found=false; for(auto&i:p.functions[0].blocks[0].instructions) if(i.op==IROp::Divide) found=true;
   expect(found,"trapping divide removed/folded");
 });
 run("preserve calls", []{
   auto p=programOf({block("entry",{ci("%x",42),call("out",{"%x"}),ci("%r",0),ret("%r")})});
   IROptimiser{}.optimise(p);
   bool found=false; for(auto&i:p.functions[0].blocks[0].instructions) if(i.op==IROp::Call) found=true;
   expect(found,"call removed");
 });
 run("fold bool not", []{
   auto n=make(IROp::Not); n.type=Type::Bool;n.dst="%n";n.args={"%b"};
   auto p=programOf({
     block("entry",{cb("%b",false),n,branch("%n","yes","no")}),
     block("yes",{ci("%r",0),ret("%r")}),
     block("no",{ci("%q",1),ret("%q")})
   });
   IROptimiser{}.optimise(p);
   expect(p.functions[0].blocks.size()==2,"wrong bool fold");
   expect(p.functions[0].blocks[1].name=="yes","not false should choose yes");
 });
 std::cout<<passed<<"/7 tests passed\n";
}

These tests cover:

• Integer constant folding.
• Comparison folding.
• Branch simplification.
• Unreachable-block removal.
• Iterative dead instruction elimination.
• Preservation of potentially trapping division.
• Preservation of function calls.
• Boolean unary folding.

Updating CMakeLists.txt

Add IROptimiser.cpp to the compiler core and register the optimiser tests.

A complete Chapter 10 setup can look like this:

cmake_minimum_required(VERSION 3.10)

# Name of your project
project(gsisi LANGUAGES CXX)

# Use C++20
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

file(GLOB SOURCES "src/*.cpp")
list(REMOVE_ITEM SOURCES "${CMAKE_CURRENT_SOURCE_DIR}/src/main.cpp")

add_library(gsisi_frontend ${SOURCES})

target_include_directories(gsisi_frontend
    PUBLIC
        ${CMAKE_CURRENT_SOURCE_DIR}/include
)


add_executable(si_compiler src/main.cpp)

target_link_libraries(si_compiler
    PRIVATE
        gsisi_frontend
)

add_custom_command(
    TARGET si_compiler
    POST_BUILD
    COMMAND
        ${CMAKE_COMMAND} -E make_directory
        $<TARGET_FILE_DIR:si_compiler>/libsi
    COMMAND
        ${CMAKE_COMMAND} -E copy_if_different
        ${CMAKE_CURRENT_SOURCE_DIR}/libsi/out.asm
        $<TARGET_FILE_DIR:si_compiler>/libsi/out.asm
    COMMENT "Copying the Si runtime next to the compiler"
)

# --------------------------------------------------
# Tests
# --------------------------------------------------
option(BUILD_TESTING "Build the gsisi tests" ON)

if(BUILD_TESTING)
    enable_testing()

    add_executable(parser_tests
        tests/ParserTests.cpp
        ${SOURCES}
    )

    add_executable(semantic_tests
        tests/SemanticAnalyserTests.cpp
    )

    add_executable(ir_generator_tests
        tests/IRGeneratorTests.cpp
    )

    add_executable(assembly_generator_tests
        tests/AssemblyGeneratorTests.cpp
    )

    add_executable(control_flow_assembly_tests
        tests/ControlFlowAssemblyTests.cpp
    )

    add_executable(optimiser_tests
        tests/IROptimiserTests.cpp
    )

    target_include_directories(parser_tests PRIVATE include)
    target_link_libraries(semantic_tests PRIVATE gsisi_frontend)
    target_link_libraries(ir_generator_tests PRIVATE gsisi_frontend)
    target_link_libraries(assembly_generator_tests PRIVATE gsisi_frontend)
    target_link_libraries(control_flow_assembly_tests PRIVATE gsisi_frontend)
    target_link_libraries(optimiser_tests PRIVATE gsisi_frontend)

    add_test(
        NAME parser_tests
        COMMAND parser_tests
    )

    add_test(
        NAME semantic_tests
        COMMAND semantic_tests
    )

    add_test(
        NAME ir_generator_tests
        COMMAND ir_generator_tests
    )

    add_test(
        NAME semantic_sample
        COMMAND si_compiler
            ${CMAKE_CURRENT_SOURCE_DIR}/tests/test-2.si
            ${CMAKE_CURRENT_SOURCE_DIR}/build/test-2.asm
    )

    add_test(
        NAME compiler_ir_smoke_test
        COMMAND si_compiler
                ${CMAKE_CURRENT_SOURCE_DIR}/tests/test-3.si
                ${CMAKE_CURRENT_SOURCE_DIR}/build/test-3.asm
    )

    add_test(
        NAME assembly_generator_tests
        COMMAND assembly_generator_tests
    )

    add_test(
        NAME control_flow_assembly_tests
        COMMAND control_flow_assembly_tests
    )

    add_test(
        NAME optimiser_tests
        COMMAND optimiser_tests
    )

    find_program(
        NASM_EXECUTABLE
        nasm
        REQUIRED
    )

    find_program(
        LD_EXECUTABLE
        ld
        REQUIRED
    )

    if(NASM_EXECUTABLE AND LD_EXECUTABLE)
        add_test(
            NAME backend_native_smoke
            COMMAND
                bash
                ${CMAKE_CURRENT_SOURCE_DIR}/tests/run_backend_smoke_test.sh
                $<TARGET_FILE:si_compiler>
                ${CMAKE_CURRENT_SOURCE_DIR}
                ${CMAKE_CURRENT_BINARY_DIR}/backend-smoke
        )

        add_test(
            NAME control_flow_native_smoke
            COMMAND
                bash
                ${CMAKE_CURRENT_SOURCE_DIR}/tests/run_control_flow_smoke_test.sh
                $<TARGET_FILE:si_compiler>
                ${CMAKE_CURRENT_SOURCE_DIR}
                ${CMAKE_CURRENT_BINARY_DIR}/control-flow-smoke
    )

    add_test(
        NAME optimiser_native_smoke
        COMMAND
            bash
            ${CMAKE_CURRENT_SOURCE_DIR}/tests/run_optimiser_smoke_test.sh
            $<TARGET_FILE:si_compiler>
            ${CMAKE_CURRENT_SOURCE_DIR}
            ${CMAKE_CURRENT_BINARY_DIR}/optimiser-smoke
    )

    else()
        message(WARNING
            "NASM or ld was not found; the native runtime smoke test is disabled"
        )
    endif()
endif()

As in the previous chapters, we use enable_testing() directly instead of include(CTest).

Native Optimiser Smoke Test

Unit tests inspect the IR transformation itself. The native smoke test verifies that the optimised IR still survives assembly generation, NASM, linking and execution.

Create gsisi/tests/run_optimiser_smoke_test.sh:

#!/usr/bin/env bash
set -euo pipefail

compiler="$1"
source_root="$2"
work_dir="$3"

rm -rf "$work_dir"
mkdir -p "$work_dir/path with spaces"

program="$work_dir/path with spaces/optimised-program"

"$compiler"     "$source_root/tests/test-7.si"     "$program"

if [[ ! -x "$program" ]]; then
    echo "Compiler did not create an executable at: $program" >&2
    exit 1
fi

actual_output="$("$program")"
expected_output="10"

if [[ "$actual_output" != "$expected_output" ]]; then
    echo "Unexpected optimiser smoke-test output:" >&2
    printf '%s
' "$actual_output" >&2
    exit 1
fi

echo "Optimiser native smoke test passed"

Notice the quoted command substitution:

actual_output="$("$program")"

The executable path deliberately contains spaces, so the quotes are required to execute the complete path as one command.

Make the script executable:

chmod +x tests/run_optimiser_smoke_test.sh

Build and Run the Tests

From the repository root:

cmake -S . -B build -DBUILD_TESTING=ON
cmake --build build
ctest --test-dir build --output-on-failure

Expected result:

100% tests passed, 0 tests failed out of 11

You can also run the C++ test executable directly:

./build/optimiser_tests

Expected summary:

7/7 tests passed

Compile tests/test-7.si directly into a native executable:

./build/si_compiler tests/test-7.si build/test

The compiler creates:

build/test.asm
build/test

Run the executable:

./build/test

Expected output:

10

You can inspect the generated assembly with:

less build/test.asm

IR Before and After Optimisation

For a small example such as:

fn main(): int {
    let a: int = 5 + 5;

    if (true) {
        out(a);
    } else {
        out(999);
    }

    return 0;
}

IR before optimisation may contain:

%t0 = const_int 5
%t1 = const_int 5
%t2 = add %t0, %t1
store %t2, a
%t3 = const_bool true
branch %t3, if_then0, if_else2

After constant folding and branch simplification:

%t2 = const_int 10
store %t2, a
jump if_then0

After unreachable-block and dead-instruction removal, the constants feeding the original addition and the unreachable if_else2 block disappear as well.

The final assembly has less work to perform, but the program still prints the same result.

Constant Folding vs Constant Propagation

Constant folding evaluates an operation when its operands are already known constants. Constant propagation carries a known constant value forward so later instructions can reuse that information.

The implementation in this chapter performs limited propagation for immutable compiler-generated temporaries. It does not yet perform full data-flow propagation through mutable local variables or arbitrary CFG joins.

Unreachable Code Elimination vs Dead Code Elimination

These passes remove different kinds of unnecessary IR:

Optimisation	What it proves
Unreachable-block removal	The code can never execute
Dead instruction elimination	The result is unused and removing the instruction is safe

A call inside an unreachable block can therefore be removed, while an unused call in a reachable block must still be preserved.

Common Compiler Optimisation Mistakes

• Using host-language undefined behaviour when folding. Optimisation must reproduce the target integer semantics.
• Folding operations that may trap. Division by zero and INT_MIN / -1 must preserve runtime behaviour.
• Deleting unused instructions without checking side effects. Calls, stores, terminators, and potentially trapping operations are not ordinary dead values.
• Running dead-code elimination only once. Removing one value can make its inputs dead.
• Ignoring pass ordering. Folding can enable branch simplification, which can enable reachability cleanup and more DCE.
• Leaving stale fields after changing an instruction kind. A branch converted to a jump should no longer carry branch-only fields.
• Optimising malformed IR instead of rejecting it. Optimisation passes should operate on well-formed compiler IR.

Frequently Asked Questions

What is compiler optimisation?

Compiler optimisation transforms a program into an equivalent form intended to reduce runtime work, code size, or later compilation complexity without changing observable behaviour.

What is constant folding?

Constant folding evaluates an expression during compilation when all required inputs are already known.

What is constant propagation?

Constant propagation records that a value is known and carries that information forward. This chapter performs a limited form for immutable IR temporaries.

What is dead code elimination?

Dead code elimination removes instructions whose results are unused when removing those instructions cannot change observable behaviour.

What is unreachable code elimination?

Unreachable code elimination removes basic blocks that cannot be reached from a function’s entry block.

Why does optimisation order matter?

One pass can create opportunities for another. A folded comparison can create a constant branch; simplifying that branch can make blocks unreachable; removing those blocks can make more values dead.

Why not remove an unused division?

Division can still trap even when its result is unused. Removing it could change runtime behaviour.

Why preserve calls with unused return values?

Calls can have side effects such as output or state changes. An unused result does not make the call itself dead.

Why optimise IR instead of x86-64 assembly?

IR exposes program operations and control flow in a machine-independent form that is easier to analyse and rewrite.

Is this optimiser using SSA?

No. The compiler has single-definition generated temporaries, but it does not build full Static Single Assignment form or phi nodes.

What optimisation should be added next?

Natural extensions include full constant propagation, copy propagation, common subexpression elimination, SSA construction, data-flow analysis, loop optimisations, register allocation, and interprocedural optimisation.

What This Optimiser Does Not Do

This optimiser is intentionally local, conservative, and small enough to inspect end to end.

It does not yet implement:

• Constant propagation through mutable local variables.
• Common subexpression elimination.
• Copy propagation.
• Global value numbering.
• Loop-invariant code motion.
• Function inlining.
• Register allocation.
• SSA form.
• Interprocedural analysis.
• Vectorisation.

It also assumes the IR produced by our compiler is well formed: temporaries have a single definition and blocks end in explicit terminators.

Those limitations are deliberate. They keep the first optimiser understandable while still demonstrating pass ordering, semantic preservation, CFG reachability, side-effect reasoning, and fixed-point dead-code elimination.

Compiler Optimisation: Key Takeaways

• The compiler now has a dedicated optimisation stage between IR generation and assembly generation.
• Valid optimisations preserve observable behaviour, including side effects and runtime traps.
• Constant folding evaluates known integer, boolean, unary, arithmetic, and comparison expressions during compilation.
• Limited propagation reuses known values for immutable generated temporaries.
• Branch simplification replaces branches with jumps when conditions are known.
• Reachability analysis removes basic blocks that can no longer execute.
• Dead instruction elimination repeatedly removes unused pure value chains until the IR reaches a fixed point.
• Calls, stores, terminators, and potentially trapping divisions are preserved conservatively.
• Pass ordering matters because each transformation can expose opportunities for later passes.
• Unit tests verify the IR transformations, while a native smoke test verifies the complete optimised executable pipeline.

Series Review

Across ten chapters, gsisi grew from a compiler diagram into a complete educational native compiler for the Si language. Each chapter introduced one clear compiler responsibility:

1. We opened the compiler black box and followed source code to machine code.
2. We designed the Si language and compiler project.
3. We built lexical analysis and token generation.
4. We implemented a recursive descent parser and AST.
5. We added symbols, scopes and static type checking.
6. We lowered the checked AST into a three-address-style IR.
7. We generated our first x86-64 NASM assembly.
8. We implemented System V function calls and a small runtime.
9. We added comparisons, branches and loops.
10. We added the first optimisation passes.

The final pipeline is:

Source code
    ↓
Lexer
    ↓
Tokens
    ↓
Parser
    ↓
Abstract Syntax Tree
    ↓
Semantic analyser
    ↓
Intermediate Representation
    ↓
IR optimiser
    ↓
x86-64 assembly
    ↓
NASM + linker
    ↓
Native executable

Where to Go Next

The compiler is deliberately small, which makes it a good foundation for further experiments.

Natural next steps include:

• Strings and string literals.
• Arrays.
• Structs.
• Pointers.
• More integer widths.
• Better diagnostics and source ranges.
• Register allocation.
• SSA form.
• Data-flow analysis.
• More advanced optimisation passes.
• ARM64 code generation.
• An LLVM backend.

Each feature introduces a different part of language implementation and compiler engineering.

Series Conclusion

A compiler brings together language design, parsing, type systems, intermediate representations, control-flow analysis, machine architecture, operating-system interfaces, runtime support, and program optimisation.

Building each stage ourselves makes the path from source code to native instructions concrete:

characters
→ tokens
→ syntax
→ meaning
→ IR
→ optimised IR
→ assembly
→ executable

The important result of this series is not only that Si programs now compile into native executables. We also have a compiler architecture in which every major stage has a clear responsibility and can be tested or extended independently.

The lexer recognises source text. The parser builds structure. Semantic analysis validates meaning. The IR exposes lower-level operations. The optimiser transforms that IR while preserving behaviour. The backend converts the result into target-specific code.

That turns the compiler from a black box into a system we can inspect, reason about, test, and continue improving.