Skip to main content

Chapter 9 · Programming

Compiler Control Flow in C++: x86-64 Branches, Loops and Jumps

Implement compiler control flow in x86-64 assembly by lowering IR comparisons, conditional branches, if/else statements and while loops.

By Updated 29 min Intermediate

Illustrated compiler pipeline showing source code passing through analysis and code-generation stages before becoming machine code.
On this page

Chapter 8 connected compiled Si functions through the x86-64 System V ABI, added the out() runtime, and automated assembly and linking. The backend can now execute straight-line programs and function calls, but it still cannot change the direction of execution.

That means source-level if, else, and while constructs can already reach the IR, but the x86-64 backend still rejects the comparison and control-flow instructions that make those constructs work.

Those missing instructions are:

equal
not_equal
less
less_equal
greater
greater_equal
jump
branch

They are the instructions behind every if, else and while statement in Si.

In this chapter, we complete compiler control-flow code generation by translating IR comparisons, basic blocks, unconditional jumps, and conditional branches into x86-64 cmp, setcc, jcc, and jmp instructions:

Si if / while
      ↓
AST control-flow nodes
      ↓
IR basic blocks
      ↓
comparison, branch and jump instructions
      ↓
x86-64 cmp, setcc, jcc and jmp

By the end of the chapter, gsisi can compile and execute a program containing a loop, a nested conditional, function calls, assignments, and signed integer comparisons:

fn main(): int {
    let i: int = 0;

    while (i < 5) {
        if (i == 2) {
            out(20);
        } else {
            out(i);
        }

        i = i + 1;
    }

    return 0;
}

It prints:

0
1
20
3
4

What You Will Learn

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

  • explain how compiler control flow is represented with basic blocks;
  • explain how if, else, and while become branches and jumps;
  • materialise comparison results as Si boolean values;
  • map signed integer comparisons to x86-64 condition codes;
  • translate IR block names into function-scoped assembly labels;
  • emit unconditional jumps and two-way conditional branches;
  • compile if, if/else, and while statements;
  • validate duplicate blocks, malformed terminators, and missing branch targets;
  • test generated control flow both structurally and as a native executable.

What Is Control Flow in a Compiler?

Control flow describes the order in which a program’s instructions can execute. A straight-line program has one obvious path from the first instruction to the last. Conditions and loops introduce multiple possible paths and edges that can move execution to different parts of the program.

A compiler usually lowers structured source constructs into a simpler control-flow representation before machine-code generation. In gsisi, that representation uses basic blocks connected by terminator instructions:

  • jump for an unconditional transfer;
  • branch for a two-way conditional transfer;
  • return for leaving the current function.

The backend does not need to reconstruct the original source statement. It only needs to translate each block and preserve the edges between blocks.

How Are if, else, and while Statements Compiled?

The complete lowering path is:

  1. The parser builds structured AST nodes such as IfStatementNode and WhileStatementNode.
  2. The IR generator converts those nodes into basic blocks.
  3. Comparison expressions produce boolean temporaries.
  4. branch terminators select one of two target blocks.
  5. jump terminators move unconditionally to another block.
  6. The assembly backend converts IR block names into labels.
  7. x86-64 cmp, setcc, jne, and jmp instructions implement the final control flow.

An if statement therefore stops being an if long before assembly generation. A while loop stops being a loop node and becomes a collection of blocks containing a back edge.

Basic Blocks, Terminators, and the Control-Flow Graph

A basic block is a straight-line sequence of instructions with one entry point. A terminator is the final instruction that decides what happens after that block.

Taken together, the blocks and their outgoing edges form a control-flow graph (CFG). Chapter 9 does not build a separate graph class, because the current IRFunction::blocks structure and its jump targets already contain enough information for validation and assembly generation.

Control Flow Is Movement Between Basic Blocks

At the source level, an if statement looks like one structured construct:

if (x > 5) {
    out(1);
} else {
    out(0);
}

The IR generator removes the source-level structure and replaces it with several basic blocks connected by explicit terminators:

entry:
  %t0 = load x
  %t1 = const_int 5
  %t2 = greater %t0, %t1
  branch %t2, if_then0, if_else2

if_then0:
  %t3 = const_int 1
  call out(%t3)
  jump if_end1

if_else2:
  %t4 = const_int 0
  call out(%t4)
  jump if_end1

if_end1:
  ...

A basic block is a sequence of instructions with one entry point. Its final instruction is a terminator that decides where execution goes next.

For gsisi, the terminators are:

jump
branch
return

This is the key backend simplification: the assembly generator never needs to reconstruct an IfStatementNode or WhileStatementNode. It emits block labels and translates the terminators already present in the IR.

How x86-64 cmp, setcc, and Condition Codes Work

The x86-64 cmp instruction compares two operands conceptually by subtracting the right operand from the left. The arithmetic result is discarded, but the processor status flags are updated so later instructions can test the relationship between the operands.

mov eax, dword [rbp - 4]
cmp eax, dword [rbp - 8]

Later x86-64 instructions inspect those flags. Two instruction families matter in this chapter:

  • setcc writes 0 or 1 into an 8-bit destination.

  • jcc jumps when a condition is true.

The cc suffix means condition code. The exact suffix determines which combination of CPU flags is interpreted as true.

Because Si int values are signed 32-bit integers, ordering comparisons must use the signed x86-64 condition codes:

Si operatorIR operationBoolean instructionJump instruction
==equalseteje
!=not_equalsetnejne
<lesssetljl
<=less_equalsetlejle
>greatersetgjg
>=greater_equalsetgejge

Unsigned condition codes such as setb and seta interpret the flags differently and would therefore produce incorrect ordering for negative Si integers.

Materialising Comparison Results as Boolean Values

In gsisi, a comparison is still an expression, so the IR gives it a destination temporary rather than turning every comparison directly into a jump:

%t2 = greater %t0, %t1

That temporary may later be stored, returned, negated, passed to a function, or consumed by a branch. The backend therefore materialises a canonical boolean 0 or 1 instead of assuming every comparison exists only for control flow.

For %t0 > %t1, the generated assembly is:

mov eax, dword [rbp - 4]
cmp eax, dword [rbp - 8]
setg al
movzx eax, al
mov dword [rbp - 12], eax

setg al changes only the low 8 bits of eax. The upper bits still contain old data, so we follow it with:

movzx eax, al

movzx zero-extends the byte into the full 32-bit register. Afterward, eax is guaranteed to contain exactly 0 or 1, matching the boolean representation used throughout Si.

Generating Function-Scoped Assembly Labels

Every emitted block definition and every branch destination must use exactly the same label transformation. If definitions and references construct labels differently, NASM will see them as different symbols.

A fragile implementation might build a jump target from the function’s return label:

_context.returnLabel + "_" + instruction.target

If the return label is .L_main_return, this produces a target such as:

.L_main_return_if_then0

But the block may actually have been emitted as:

.L_main_if_then0

NASM will then report an undefined symbol.

Use one helper for both block definitions and branch destinations:

std::string AssemblyGenerator::blockLabel(
    const std::string& functionName,
    const std::string& blockName
) {
    return ".L_" + functionName + "_" + blockName;
}

This gives predictable function-scoped labels:

main / entry       -> .L_main_entry
main / while_cond0 -> .L_main_while_cond0
add  / entry       -> .L_add_entry

Including the function name in the assembly label prevents two different functions from colliding when both contain common IR block names such as entry.

Updating AssemblyGenerator.hpp

Chapter 9 extends the assembly generator with comparison and control-flow emitters and stores the active function name so jump targets can be converted through the shared block-label helper.

Update gsisi/include/AssemblyGenerator.hpp:

#pragma once

#include <cstddef>
#include <ostream>
#include <string>
#include <unordered_map>
#include <unordered_set>

#include "IR.hpp"

class AssemblyGenerator {
public:
    void generate(const IRProgram& program, std::ostream& output);

private:
    struct FunctionContext {
        std::unordered_map<std::string, int> stackSlots;
        int nextOffset{0};
        std::string functionName;
        std::string returnLabel;
    };

    struct FunctionSignature {
        std::size_t parameterCount{};
        Type returnType{Type::Void};
        bool runtimeFunction{false};
    };

    FunctionContext _context;
    std::unordered_map<std::string, FunctionSignature> _signatures;
    std::unordered_set<std::string> _runtimeImports;

    //----------------------------------
    // Setup and validation
    //----------------------------------
    void reset();
    void collectSignatures(const IRProgram& program);
    void collectRuntimeImports(const IRProgram& program);
    void validateProgram(const IRProgram& program) const;
    void validateFunction(const IRFunction& function) const;
    void validateInstruction(
        const IRInstruction& instruction,
        const IRFunction& function
    ) const;

    //----------------------------------
    // Program and function emission
    //----------------------------------
    void emitProgram(const IRProgram& program, std::ostream& output);
    void emitFunction(const IRFunction& function, std::ostream& output);

    //----------------------------------
    // Stack slots
    //----------------------------------
    void allocateStackSlots(const IRFunction& function);
    void allocateSlot(const std::string& name);
    [[nodiscard]] int slotOffset(const std::string& name) const;
    [[nodiscard]] int stackSize() const noexcept;
    [[nodiscard]] std::string stackOperand(const std::string& name) const;

    //----------------------------------
    // Instruction emission
    //----------------------------------
    void emitInstruction(const IRInstruction& instruction, std::ostream& output);
    void emitConstant(const IRInstruction& instruction, std::ostream& output);
    void emitLoad(const IRInstruction& instruction, std::ostream& output);
    void emitStore(const IRInstruction& instruction, std::ostream& output);
    void emitBinary(const IRInstruction& instruction, std::ostream& output);
    void emitComparison(const IRInstruction& instruction, std::ostream& output);
    void emitUnary(const IRInstruction& instruction, std::ostream& output);
    void emitCall(const IRInstruction& instruction, std::ostream& output);
    void emitJump(const IRInstruction& instruction, std::ostream& output);
    void emitBranch(const IRInstruction& instruction, std::ostream& output);
    void emitReturn(const IRInstruction& instruction, std::ostream& output);

    //----------------------------------
    // Helpers
    //----------------------------------
    static void requireDestination(const IRInstruction& instruction);
    static void requireNoDestination(const IRInstruction& instruction);
    static void requireArgumentCount(
        const IRInstruction& instruction,
        std::size_t expected
    );

    [[nodiscard]] static bool isSupported(IROp operation) noexcept;
    [[nodiscard]] static const char* parameterRegister(std::size_t index);
    [[nodiscard]] static std::string functionLabel(const std::string& name);
    [[nodiscard]] static std::string blockLabel(
        const std::string& functionName,
        const std::string& blockName
    );
};

Most of this class remains unchanged from Chapter 8. The new pieces are:

std::string functionName;

void emitComparison(...);
void emitJump(...);
void emitBranch(...);
void requireNoDestination(...);

Validating the IR Control-Flow Graph

The backend receives semantically checked IR, but semantic analysis does not validate backend-specific CFG invariants. The assembly generator should therefore reject malformed internal control flow instead of emitting assembly with missing labels, unreachable trailing instructions, or invalid terminators.

For each function, Chapter 9 validates that:

  • The function contains at least one basic block.
  • Every block has a non-empty, unique name.
  • Every block ends in a terminator.
  • A terminator appears only as the final instruction in its block.
  • Every jump target exists in the same function.
  • Both targets of every branch exist in the same function.
  • Comparisons have two operands and a destination.
  • A branch has one condition operand and no destination.
  • A jump has no operands and no destination.

Update validateFunction() in gsisi/src/AssemblyGenerator.cpp:

void AssemblyGenerator::validateFunction(
    const IRFunction& function
) const {
    if (function.parameters.size() > 6) {
        throw std::runtime_error(
            "Assembly error: function '" + function.name +
            "' has more than 6 parameters"
        );
    }

    if (function.blocks.empty()) {
        throw std::runtime_error(
            "Assembly error: function '" + function.name +
            "' has no basic blocks"
        );
    }

    std::unordered_set<std::string> storageNames;

    for (const IRParameter& parameter : function.parameters) {
        if (parameter.name.empty() || parameter.type == Type::Void) {
            throw std::runtime_error(
                "Assembly error: invalid parameter in function '" +
                function.name + "'"
            );
        }

        if (!storageNames.insert(parameter.name).second) {
            throw std::runtime_error(
                "Assembly error: duplicate storage name '" +
                parameter.name + "' in function '" + function.name + "'"
            );
        }
    }

    for (const IRLocal& local : function.locals) {
        if (local.name.empty() || local.type == Type::Void) {
            throw std::runtime_error(
                "Assembly error: invalid local in function '" +
                function.name + "'"
            );
        }

        if (!storageNames.insert(local.name).second) {
            throw std::runtime_error(
                "Assembly error: duplicate storage name '" +
                local.name + "' in function '" + function.name + "'"
            );
        }
    }

    std::unordered_set<std::string> blockNames;

    for (const IRBlock& block : function.blocks) {
        if (block.name.empty()) {
            throw std::runtime_error(
                "Assembly error: function '" + function.name +
                "' contains an unnamed block"
            );
        }

        if (!blockNames.insert(block.name).second) {
            throw std::runtime_error(
                "Assembly error: duplicate block '" + block.name +
                "' in function '" + function.name + "'"
            );
        }

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

        for (std::size_t index = 0;
             index < block.instructions.size();
             ++index) {
            const IRInstruction& instruction = block.instructions[index];
            validateInstruction(instruction, function);

            if (isTerminator(instruction.op) &&
                index + 1 != block.instructions.size()) {
                throw std::runtime_error(
                    "Assembly error: terminator in block '" + block.name +
                    "' is not the final instruction"
                );
            }
        }

        if (!isTerminator(block.instructions.back().op)) {
            throw std::runtime_error(
                "Assembly error: block '" + block.name +
                "' has no terminator"
            );
        }
    }

    for (const IRBlock& block : function.blocks) {
        const IRInstruction& terminator = block.instructions.back();

        if (terminator.op == IROp::Jump) {
            if (!blockNames.contains(terminator.target)) {
                throw std::runtime_error(
                    "Assembly error: jump from block '" + block.name +
                    "' targets unknown block '" + terminator.target + "'"
                );
            }
        }

        if (terminator.op == IROp::Branch) {
            if (!blockNames.contains(terminator.trueTarget)) {
                throw std::runtime_error(
                    "Assembly error: branch from block '" + block.name +
                    "' targets unknown true block '" +
                    terminator.trueTarget + "'"
                );
            }

            if (!blockNames.contains(terminator.falseTarget)) {
                throw std::runtime_error(
                    "Assembly error: branch from block '" + block.name +
                    "' targets unknown false block '" +
                    terminator.falseTarget + "'"
                );
            }
        }
    }
}

The two-pass block validation matters. We collect all block names first, then validate destinations. A block may jump forward to another block that appears later in the function.

Validating the New Instructions

Extend validateInstruction() with the Chapter 9 operations:

case IROp::Less:
case IROp::LessEqual:
case IROp::Greater:
case IROp::GreaterEqual:
case IROp::Equal:
case IROp::NotEqual:
    requireDestination(instruction);
    requireArgumentCount(instruction, 2);

    if (instruction.type != Type::Bool) {
        throw std::runtime_error(
            "Assembly error: comparison result must have type bool"
        );
    }
    return;

case IROp::Jump:
    requireNoDestination(instruction);
    requireArgumentCount(instruction, 0);

    if (instruction.target.empty()) {
        throw std::runtime_error(
            "Assembly error: jump has no target"
        );
    }
    return;

case IROp::Branch:
    requireNoDestination(instruction);
    requireArgumentCount(instruction, 1);

    if (instruction.trueTarget.empty() ||
        instruction.falseTarget.empty()) {
        throw std::runtime_error(
            "Assembly error: branch requires true and false targets"
        );
    }
    return;

Add the no-destination helper:

void AssemblyGenerator::requireNoDestination(
    const IRInstruction& instruction
) {
    if (!instruction.dst.empty()) {
        throw std::runtime_error(
            "Assembly error: instruction '" +
            std::string(toString(instruction.op)) +
            "' cannot have a destination"
        );
    }
}

The backend is not replacing semantic analysis. It is checking invariants that should be true after semantic analysis and IR generation.

Supporting the New Operations

Update isSupported():

bool AssemblyGenerator::isSupported(IROp operation) noexcept {
    switch (operation) {
        case IROp::ConstInt:
        case IROp::ConstBool:
        case IROp::Load:
        case IROp::Store:
        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:
        case IROp::Negate:
        case IROp::Not:
        case IROp::Call:
        case IROp::Jump:
        case IROp::Branch:
        case IROp::Return:
            return true;
    }

    return false;
}

At this point, every operation in the current IR has a backend path.

Storing the Active Function Name

The jump emitters need the active function name so they can call blockLabel().

Update allocateStackSlots():

void AssemblyGenerator::allocateStackSlots(
    const IRFunction& function
) {
    _context = FunctionContext{};
    _context.functionName = function.name;
    _context.returnLabel = ".L_" + function.name + "_return";

    for (const IRParameter& parameter : function.parameters) {
        allocateSlot(parameter.name);
    }

    for (const IRLocal& local : function.locals) {
        allocateSlot(local.name);
    }

    for (const IRBlock& block : function.blocks) {
        for (const IRInstruction& instruction : block.instructions) {
            if (!instruction.dst.empty()) {
                allocateSlot(instruction.dst);
            }
        }
    }
}

Block definitions already use the shared helper:

for (const IRBlock& block : function.blocks) {
    output << blockLabel(function.name, block.name) << ":\n";

    for (const IRInstruction& instruction : block.instructions) {
        emitInstruction(instruction, output);
    }
}

Emitting Comparisons

Add emitComparison() to gsisi/src/AssemblyGenerator.cpp:

void AssemblyGenerator::emitComparison(
    const IRInstruction& instruction,
    std::ostream& output
) {
    output
        << "    mov eax, "
        << stackOperand(instruction.args[0])
        << '\n';

    output
        << "    cmp eax, "
        << stackOperand(instruction.args[1])
        << '\n';

    switch (instruction.op) {
        case IROp::Equal:
            output << "    sete al\n";
            break;

        case IROp::NotEqual:
            output << "    setne al\n";
            break;

        case IROp::Less:
            output << "    setl al\n";
            break;

        case IROp::LessEqual:
            output << "    setle al\n";
            break;

        case IROp::Greater:
            output << "    setg al\n";
            break;

        case IROp::GreaterEqual:
            output << "    setge al\n";
            break;

        default:
            throw std::runtime_error(
                "Assembly internal error: invalid comparison instruction"
            );
    }

    output << "    movzx eax, al\n";
    output
        << "    mov " << stackOperand(instruction.dst)
        << ", eax\n";
}

This implementation works for comparison expressions in any context:

let small: bool = x < 10;
let same: bool = x == y;
return x != 0;

Semantic analysis has already verified that the comparison operands are type-compatible. The backend therefore only needs to preserve the comparison semantics and materialise the boolean result.

Generating Unconditional jmp Instructions

An IR jump terminator has one job: transfer execution unconditionally to one target block.

jump while_cond0

Add:

void AssemblyGenerator::emitJump(
    const IRInstruction& instruction,
    std::ostream& output
) {
    output
        << "    jmp "
        << blockLabel(_context.functionName, instruction.target)
        << '\n';
}

For a function named main, this IR:

jump while_cond0

becomes:

jmp .L_main_while_cond0

Generating Conditional Branches

An IR branch reads a previously materialised Si boolean and selects one of two block targets:

branch %t2, if_then0, if_else2

A false value is represented by 0; any nonzero value is treated as true. Valid generated Si booleans are canonical 0 or 1, but the branch logic remains robust for any nonzero value.

Add:

void AssemblyGenerator::emitBranch(
    const IRInstruction& instruction,
    std::ostream& output
) {
    output
        << "    cmp "
        << stackOperand(instruction.args[0])
        << ", 0\n";

    output
        << "    jne "
        << blockLabel(
            _context.functionName,
            instruction.trueTarget
        )
        << '\n';

    output
        << "    jmp "
        << blockLabel(
            _context.functionName,
            instruction.falseTarget
        )
        << '\n';
}

This produces a simple and readable two-way branch:

cmp dword [rbp - 12], 0
jne .L_main_if_then0
jmp .L_main_if_else2

A later optimisation could fuse a comparison and branch into one cmp followed directly by jg, jl, or another conditional jump. Chapter 9 deliberately keeps the materialised boolean because that mirrors the current IR exactly and keeps expression semantics independent from branch semantics.

Updating the Instruction Dispatcher

The final dispatcher change routes comparison and control-flow IR operations to their new emitters:

void AssemblyGenerator::emitInstruction(
    const IRInstruction& instruction,
    std::ostream& output
) {
    switch (instruction.op) {
        case IROp::ConstInt:
        case IROp::ConstBool:
            emitConstant(instruction, output);
            return;

        case IROp::Load:
            emitLoad(instruction, output);
            return;

        case IROp::Store:
            emitStore(instruction, output);
            return;

        case IROp::Add:
        case IROp::Subtract:
        case IROp::Multiply:
        case IROp::Divide:
            emitBinary(instruction, output);
            return;

        case IROp::Less:
        case IROp::LessEqual:
        case IROp::Greater:
        case IROp::GreaterEqual:
        case IROp::Equal:
        case IROp::NotEqual:
            emitComparison(instruction, output);
            return;

        case IROp::Negate:
        case IROp::Not:
            emitUnary(instruction, output);
            return;

        case IROp::Call:
            emitCall(instruction, output);
            return;

        case IROp::Jump:
            emitJump(instruction, output);
            return;

        case IROp::Branch:
            emitBranch(instruction, output);
            return;

        case IROp::Return:
            emitReturn(instruction, output);
            return;
    }

    throw std::runtime_error(
        "Assembly internal error: unsupported instruction reached emission"
    );
}

How an if Statement Reaches Assembly

Consider:

if (x > 5) {
    out(1);
}

The IR generator creates a true block and an end block:

%t0 = load x
%t1 = const_int 5
%t2 = greater %t0, %t1
branch %t2, if_then0, if_end1

if_then0:
  %t3 = const_int 1
  call out(%t3)
  jump if_end1

if_end1:
  ...

The backend emits:

mov eax, dword [rbp - 4]
cmp eax, dword [rbp - 8]
setg al
movzx eax, al
mov dword [rbp - 12], eax

cmp dword [rbp - 12], 0
jne .L_main_if_then0
jmp .L_main_if_end1

.L_main_if_then0:
    mov dword [rbp - 16], 1
    mov edi, dword [rbp - 16]
    call si_out
    jmp .L_main_if_end1

.L_main_if_end1:

The if statement no longer exists at the assembly level. Only comparisons, labels and jumps remain.

How if/else Control Flow Rejoins

For:

if (x > 5) {
    out(1);
} else {
    out(0);
}

control can follow either branch before potentially rejoining at a merge block:

              entry
                |
              branch
              /    \
          if_then  if_else
              \    /
               if_end

The IR generator terminates both branch blocks with a jump to the merge block when they fall through:

if_then0:
  ...
  jump if_end1

if_else2:
  ...
  jump if_end1

If one branch returns, it does not need a jump:

if (x > 5) {
    return 1;
} else {
    out(0);
}

The then block ends in return, so it has no edge to the merge block. The else block falls through logically and therefore jumps to the merge. The assembly generator simply preserves the terminators already encoded by the IR generator.

How a Compiler Lowers a while Loop

The current IR lowering represents a while loop with three main blocks:

while_cond0
while_body1
while_end2

The block layout is:

entry
  |
  jump
  v
while_cond0 ----false----> while_end2
  |
 true
  v
while_body1
  |
  jump
  +----------------------> while_cond0

The jump from the loop body back to the earlier condition block is called a back edge. That edge is what turns an otherwise forward-moving control-flow graph into a loop.

For:

while (i < 5) {
    i = i + 1;
}

we get assembly shaped like:

jmp .L_main_while_cond0

.L_main_while_cond0:
    ; load i and compare it with 5
    cmp dword [rbp - 12], 0
    jne .L_main_while_body1
    jmp .L_main_while_end2

.L_main_while_body1:
    ; increment i
    jmp .L_main_while_cond0

.L_main_while_end2:

Each iteration re-enters the condition block, recomputes the comparison, and branches either to the body again or to the loop exit. Nothing in the assembly needs to know that the source construct was named while.

End-to-End Control-Flow Test Program

The end-to-end sample should exercise the new control-flow path together with features from earlier chapters: loops, equality, calls, assignments, and if/else.

Create gsisi/tests/test-6.si:

fn main(): int {
    let i: int = 0;

    while (i < 5) {
        if (i == 2) {
            out(20);
        } else {
            out(i);
        }

        i = i + 1;
    }

    return 0;
}

Expected output:

0
1
20
3
4

Unit Testing x86-64 Control-Flow Generation

Native execution proves that the whole compiler toolchain works, while focused C++ tests make a broken condition code, label transformation, terminator rule, or CFG edge much easier to diagnose.

Create gsisi/tests/ControlFlowAssemblyTests.cpp:

#include <functional>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "AssemblyGenerator.hpp"
#include "IR.hpp"

namespace {

void require(bool condition, const std::string& message) {
    if (!condition) {
        throw std::runtime_error(message);
    }
}

void requireContains(
    const std::string& text,
    const std::string& expected
) {
    require(
        text.find(expected) != std::string::npos,
        "Expected generated assembly to contain: " + expected
    );
}

void requireThrows(
    const std::function<void()>& action,
    const std::string& expectedMessage
) {
    try {
        action();
    } catch (const std::exception& error) {
        requireContains(error.what(), expectedMessage);
        return;
    }

    throw std::runtime_error("Expected an exception");
}

IRInstruction constInt(const std::string& dst, int value) {
    return IRInstruction{
        .op = IROp::ConstInt,
        .type = Type::Int,
        .dst = dst,
        .intValue = value
    };
}

IRInstruction comparison(
    IROp operation,
    const std::string& dst,
    const std::string& left,
    const std::string& right
) {
    return IRInstruction{
        .op = operation,
        .type = Type::Bool,
        .dst = dst,
        .args = {left, right}
    };
}

IRInstruction returnValue(const std::string& value) {
    return IRInstruction{
        .op = IROp::Return,
        .args = {value}
    };
}

IRProgram comparisonProgram() {
    IRFunction main;
    main.name = "main";
    main.returnType = Type::Int;

    IRBlock entry;
    entry.name = "entry";
    entry.instructions = {
        constInt("%left", -2),
        constInt("%right", 3),
        comparison(IROp::Equal, "%eq", "%left", "%right"),
        comparison(IROp::NotEqual, "%ne", "%left", "%right"),
        comparison(IROp::Less, "%lt", "%left", "%right"),
        comparison(IROp::LessEqual, "%le", "%left", "%right"),
        comparison(IROp::Greater, "%gt", "%left", "%right"),
        comparison(IROp::GreaterEqual, "%ge", "%left", "%right"),
        constInt("%result", 0),
        returnValue("%result")
    };

    main.blocks.push_back(std::move(entry));

    IRProgram program;
    program.functions.push_back(std::move(main));
    return program;
}

IRProgram branchProgram() {
    IRFunction main;
    main.name = "main";
    main.returnType = Type::Int;

    IRBlock entry;
    entry.name = "entry";
    entry.instructions = {
        IRInstruction{
            .op = IROp::ConstBool,
            .type = Type::Bool,
            .dst = "%condition",
            .boolValue = true
        },
        IRInstruction{
            .op = IROp::Branch,
            .args = {"%condition"},
            .trueTarget = "then",
            .falseTarget = "else"
        }
    };

    IRBlock thenBlock;
    thenBlock.name = "then";
    thenBlock.instructions = {
        IRInstruction{
            .op = IROp::Jump,
            .target = "end"
        }
    };

    IRBlock elseBlock;
    elseBlock.name = "else";
    elseBlock.instructions = {
        IRInstruction{
            .op = IROp::Jump,
            .target = "end"
        }
    };

    IRBlock end;
    end.name = "end";
    end.instructions = {
        constInt("%result", 0),
        returnValue("%result")
    };

    main.blocks.push_back(std::move(entry));
    main.blocks.push_back(std::move(thenBlock));
    main.blocks.push_back(std::move(elseBlock));
    main.blocks.push_back(std::move(end));

    IRProgram program;
    program.functions.push_back(std::move(main));
    return program;
}

IRProgram loopProgram() {
    IRFunction main;
    main.name = "main";
    main.returnType = Type::Int;

    IRBlock entry;
    entry.name = "entry";
    entry.instructions = {
        IRInstruction{
            .op = IROp::Jump,
            .target = "while_cond"
        }
    };

    IRBlock condition;
    condition.name = "while_cond";
    condition.instructions = {
        IRInstruction{
            .op = IROp::ConstBool,
            .type = Type::Bool,
            .dst = "%condition",
            .boolValue = true
        },
        IRInstruction{
            .op = IROp::Branch,
            .args = {"%condition"},
            .trueTarget = "while_body",
            .falseTarget = "while_end"
        }
    };

    IRBlock body;
    body.name = "while_body";
    body.instructions = {
        IRInstruction{
            .op = IROp::Jump,
            .target = "while_cond"
        }
    };

    IRBlock end;
    end.name = "while_end";
    end.instructions = {
        constInt("%result", 0),
        returnValue("%result")
    };

    main.blocks.push_back(std::move(entry));
    main.blocks.push_back(std::move(condition));
    main.blocks.push_back(std::move(body));
    main.blocks.push_back(std::move(end));

    IRProgram program;
    program.functions.push_back(std::move(main));
    return program;
}

std::string generate(IRProgram program) {
    AssemblyGenerator generator;
    std::ostringstream output;
    generator.generate(program, output);
    return output.str();
}

void testSignedComparisonConditionCodes() {
    const std::string assembly = generate(comparisonProgram());

    requireContains(assembly, "sete al");
    requireContains(assembly, "setne al");
    requireContains(assembly, "setl al");
    requireContains(assembly, "setle al");
    requireContains(assembly, "setg al");
    requireContains(assembly, "setge al");
    requireContains(assembly, "movzx eax, al");
}

void testBranchUsesFunctionScopedLabels() {
    const std::string assembly = generate(branchProgram());

    requireContains(assembly, ".L_main_then:");
    requireContains(assembly, ".L_main_else:");
    requireContains(assembly, ".L_main_end:");
    requireContains(assembly, "jne .L_main_then");
    requireContains(assembly, "jmp .L_main_else");
    requireContains(assembly, "jmp .L_main_end");
}

void testLoopContainsBackEdge() {
    const std::string assembly = generate(loopProgram());

    requireContains(assembly, ".L_main_while_cond:");
    requireContains(assembly, ".L_main_while_body:");
    requireContains(assembly, ".L_main_while_end:");
    requireContains(assembly, "jmp .L_main_while_cond");
}

void testUnknownJumpTargetIsRejected() {
    IRProgram program = branchProgram();
    program.functions[0].blocks[1].instructions[0].target = "missing";

    requireThrows(
        [&] { generate(std::move(program)); },
        "targets unknown block 'missing'"
    );
}

void testDuplicateBlockNameIsRejected() {
    IRProgram program = branchProgram();
    program.functions[0].blocks[1].name = "entry";

    requireThrows(
        [&] { generate(std::move(program)); },
        "duplicate block 'entry'"
    );
}

void testInstructionAfterTerminatorIsRejected() {
    IRProgram program = branchProgram();
    auto& entry = program.functions[0].blocks[0].instructions;
    entry.push_back(constInt("%late", 99));

    requireThrows(
        [&] { generate(std::move(program)); },
        "terminator in block 'entry' is not the final instruction"
    );
}

void testGeneratorCanBeReused() {
    AssemblyGenerator generator;

    std::ostringstream first;
    IRProgram branches = branchProgram();
    generator.generate(branches, first);

    std::ostringstream second;
    IRProgram comparisons = comparisonProgram();
    generator.generate(comparisons, second);

    requireContains(first.str(), "jne .L_main_then");
    requireContains(second.str(), "setl al");
}

} // namespace

int main() {
    using Test = std::pair<std::string, std::function<void()>>;

    const std::vector<Test> tests{
        {"signed comparison condition codes", testSignedComparisonConditionCodes},
        {"function-scoped branch labels", testBranchUsesFunctionScopedLabels},
        {"loop back edge", testLoopContainsBackEdge},
        {"reject unknown jump target", testUnknownJumpTargetIsRejected},
        {"reject duplicate block name", testDuplicateBlockNameIsRejected},
        {"reject instruction after terminator", testInstructionAfterTerminatorIsRejected},
        {"generator reuse", testGeneratorCanBeReused}
    };

    int failures = 0;

    for (const auto& [name, test] : tests) {
        try {
            test();
            std::cout << "[PASS] " << name << '\n';
        } catch (const std::exception& error) {
            ++failures;
            std::cerr << "[FAIL] " << name
                      << ": " << error.what() << '\n';
        }
    }

    std::cout << (tests.size() - failures) << "/"
              << tests.size() << " tests passed\n";

    return failures == 0 ? 0 : 1;
}

These tests inspect the assembly and verify important backend invariants without invoking NASM.

Native Control-Flow Smoke Test

The native smoke test compiles tests/test-6.si, runs the generated executable and checks its complete output.

Create gsisi/tests/run_control_flow_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/control-flow-program"

"$compiler" \
    "$source_root/tests/test-6.si" \
    "$program"

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

actual_output="$("$program")"
expected_output=$'0\n1\n20\n3\n4'

if [[ "$actual_output" != "$expected_output" ]]; then
    echo "Unexpected control-flow output" >&2
    echo "Expected:" >&2
    printf '%s\n' "$expected_output" >&2
    echo "Actual:" >&2
    printf '%s\n' "$actual_output" >&2
    exit 1
fi

echo "Control-flow smoke test passed"

The nested quoting in:

actual_output="$("$program")"

is important because the executable path contains spaces. Quoting the variable inside command substitution ensures Bash executes the complete path as one command.

Make the script executable:

chmod +x tests/run_control_flow_smoke_test.sh

Updating CMakeLists.txt

Register both the focused control-flow unit test and the native smoke test. Continue using enable_testing() directly rather than include(CTest) for this project.

Add this inside the existing if(BUILD_TESTING) section:

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
    )

    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)

    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
    )

    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
    )

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

If Chapter 8’s run_backend_smoke_test test is still registered, you can keep it. The Chapter 9 test covers a broader program and can also replace it if you prefer one native smoke test per branch.

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 9

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

./build/control_flow_assembly_tests

Expected summary:

7/7 tests passed

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

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

The compiler creates:

build/test.asm
build/test

Run the executable:

./build/test

Expected output:

0
1
20
3
4

You can inspect the generated assembly with:

less build/test.asm

Signed vs Unsigned x86-64 Comparisons

The distinction between signed and unsigned condition codes is critical for compiler correctness.

Si currently treats int as a signed 32-bit type. Therefore:

RelationshipSigned conditionUnsigned equivalent to avoid for Si int
<setl / jlsetb / jb
<=setle / jlesetbe / jbe
>setg / jgseta / ja
>=setge / jgesetae / jae

Equality and inequality use sete/je and setne/jne because equality itself is not signed or unsigned.

Common Compiler Control-Flow Mistakes

Control-flow code generation tends to fail through small mismatches between IR structure and assembly labels. Common mistakes include:

  • Using unsigned condition codes for signed integers. Negative values then compare incorrectly.
  • Generating block labels differently from jump targets. The assembler sees two different symbols and reports an undefined label.
  • Allowing instructions after a terminator. Those instructions violate the basic-block invariant and should be rejected.
  • Forgetting to validate branch targets. Every target must name a block in the same function.
  • Omitting the loop back edge. Without the body-to-condition jump, a while loop executes at most once.
  • Always creating a merge edge after if/else. A branch that already returns does not fall through to the merge block.
  • Using stale comparison flags. Materialising a boolean immediately after cmp ensures the intended comparison result is captured before later instructions change the flags.
  • Optimising compare-and-branch too early. A direct conditional jump can be useful later, but first preserving the IR exactly makes the backend easier to verify.

Basic Blocks vs Source-Level Control Flow

Source code uses structured constructs because they are easier for humans to write and read. The backend operates on basic blocks because explicit edges are easier to translate and validate.

Source constructTypical IR shape
ifcondition block → then block → end block
if / elsecondition block → then/else blocks → optional merge
whileentry → condition → body or exit, with a back edge
returnblock terminator with no successor in the current function

The control-flow graph is therefore the bridge between structured source syntax and machine-level jumps.

Frequently Asked Questions

What is control flow in compiler design?

Control flow describes the possible execution paths through a function. Compilers commonly represent those paths as basic blocks connected by branches, jumps, and returns.

What is a basic block?

A basic block is a straight-line sequence of instructions with one entry point. In this IR, every block ends with a terminator that determines where execution goes next.

What is a control-flow graph?

A control-flow graph, or CFG, models basic blocks as nodes and possible transfers of execution as edges. The current gsisi IR stores enough block and target information to validate these relationships without a separate graph object.

How is an if statement compiled?

The IR generator creates separate blocks for the true path and continuation, plus an optional false path. The backend emits a comparison, tests the boolean result, and jumps to the appropriate assembly label.

How is a while loop compiled?

A while loop is lowered into a condition block, body block, and exit block. The body ends with a back edge to the condition so the condition is reevaluated before each iteration.

What does cmp do in x86-64?

cmp updates CPU status flags as though it had subtracted its right operand from its left operand, but it does not store the subtraction result. Later setcc or jcc instructions interpret those flags.

What is the difference between setcc and jcc?

setcc materialises a condition as a byte value, while jcc changes control flow when a condition is true. This chapter uses setcc to create Si boolean values and later branches on those values.

Why does the compiler use movzx after setcc?

A setcc instruction writes only an 8-bit register such as al. movzx eax, al clears the upper bits and produces the canonical 32-bit 0 or 1 boolean value expected by Si.

Why must signed comparisons use setl, setle, setg, and setge?

Those condition codes interpret the CPU flags according to signed arithmetic. Unsigned conditions such as setb and seta would order negative Si integers incorrectly.

Why validate jump targets in the backend?

Backend validation protects the IR-to-assembly contract. A missing target would otherwise become an undefined assembly label or, worse, malformed generated control flow.

Could comparisons branch directly without creating a boolean temporary?

Yes. A future optimisation could combine cmp with a direct conditional jump. The current implementation first materialises the boolean because that matches the IR design and allows comparison results to be used outside branches.

What comes after control-flow code generation?

Chapter 10 optimises the IR before it reaches the backend, including constant folding, constant propagation, branch simplification, and dead-code elimination.

Common Errors

NASM reports an undefined .L_... label

Make sure block definitions, jumps and branch destinations all use the same helper:

blockLabel(functionName, blockName)

Do not derive normal basic-block destinations from _context.returnLabel; the return label belongs to the shared function epilogue, not to the block-label namespace.

The smoke test tries to execute a path only up to the first space

The program variable must be quoted inside command substitution:

actual_output="$("$program")"

This is incorrect:

actual_output="$($program)"

The incorrect form allows Bash word splitting to break an executable path that contains spaces.

A negative comparison behaves incorrectly

Use signed condition codes:

setl, setle, setg, setge

Do not use unsigned ordering conditions such as setb or seta for signed Si integers.

Assembly error: block ... has no terminator

Every IR basic block must end in exactly one of:

jump
branch
return

This normally indicates an IR-generation bug because every generated basic block should already have a valid terminator before it reaches assembly generation.

Assembly error: ... targets unknown block

A jump or branch refers to a block name that does not exist in the same IRFunction. Compare the terminator target fields with the names stored in IRFunction::blocks.

Docker reports permission errors in build/

Remove the build directory and recreate it as the container’s dev user:

sudo rm -rf build
cmake -S . -B build
cmake --build build

Current Control-Flow Backend Limitations

The compiler now supports the complete comparison and control-flow instruction set required by the current Si language, but the generated code remains intentionally straightforward rather than optimised:

  • Every local and temporary receives a stack slot.
  • Comparisons are materialised as 0 or 1 before branching.
  • There is no register allocator.
  • There is no direct compare-and-branch optimisation.
  • There is no short-circuit && or || operator yet.
  • There are no break, continue or for statements.
  • Integer overflow and division by zero are not diagnosed at runtime.
  • The target remains Linux x86-64 with NASM and GNU ld.

Despite those limitations, the backend can now compile functions containing arithmetic, user and runtime calls, comparisons, nested conditions, and loops into native Linux executables. The remaining limitations are primarily optimisation and language-feature gaps rather than a missing control-flow foundation.

Compiler Control Flow: Key Takeaways

  • Compiler control flow is represented as basic blocks connected by terminators.
  • Structured if, else, and while statements are already lowered into explicit CFG edges before the assembly backend runs.
  • IR comparison instructions produce canonical Si booleans with cmp, signed setcc instructions, and movzx.
  • Signed condition codes preserve correct ordering for negative 32-bit integers.
  • Every basic block uses one consistent, function-scoped assembly label transformation.
  • IR jump instructions become x86-64 jmp instructions.
  • IR branch instructions test a materialised boolean and select one of two target blocks.
  • A loop is created by a back edge from the body block to the condition block.
  • Backend CFG validation rejects duplicate blocks, missing targets, malformed terminators, and instructions after terminators.
  • Focused unit tests inspect labels, comparisons, branches, and CFG invariants without requiring NASM.
  • The native smoke test proves that real if, else, and while code survives the complete compile → assemble → link → execute pipeline.
  • The backend is now ready for IR optimisation in Chapter 10.

Next Chapter

In Chapter 10, we will optimise this now-complete IR path with constant folding, constant propagation, branch simplification, and dead-code elimination before the instructions reach the x86-64 backend.

Subscribe / Stdin

Get the next part

New parts of From Source to Machine Code land in your inbox the day they publish. No spam, unsubscribe in one click.

We send your address to Kit, our email provider, and ask you to confirm by email before anything is sent. See our Privacy Statement.