Kaleidoscope Tutorial

This tutorial teaches pliron by building a small Kaleidoscope-like language and a compiler pipeline for it.

The tutorial takes you through the following chapters:

1. Parse source text (in the Kaleidoscope language) into an AST.
2. Define a new Kaleidoscope dialect for the language.
3. Lower AST nodes into the Kaleidoscope dialect IR.
4. Lower the Kaleidoscope dialect into LLVM dialect IR.
5. Use LLVM-JIT to compile and run the resulting LLVM IR.

Prerequisites

• Comfortable with Rust (did you read the Rust book?).
• Familiarity with basic compiler terms (AST, IR, lowering).

How to use this tutorial

1. Read a chapter.
2. Try out the example tests.
3. Modify it (as desired) or add new tests and re-run.
4. Move to the next chapter.

Each chapter mentions runnable example tests that you can execute. Typically, you can run them with:

cargo test --example kaleidoscope -- <test_name> --show-output

For a chapter-to-test map, see the Examples and Tests Index.

Build and view the tutorial offline (optional):

mdbook build kaleidoscope
mdbook serve kaleidoscope

Chapter 1: Parsing Kaleidoscope

This chapter implements a complete combine-based parser for the Kaleidoscope language used throughout the tutorial.

You may skip this chapter if you already have an AST (or know how to build one) and want to use pliron to build a compiler pipeline on top of it. The rest of the tutorial only requires the AST and not the parser implementation.

The implementation for this chapter lives in examples/kaleidoscope/ast.rs

What is combine?

combine is a parser combinator library.

“Parser combinators are higher-order functions that accept parsers as input and return a new parser as output.” – Wikipedia.

They allow for the construction of complex parsers by combining simpler ones.

As an example, a parser for an integer literal can be combined with a parser for a plus sign and another integer literal to create a parser for an addition expression.

Why combine?

We use combine in this tutorial because pliron itself already uses combine for most IR parsing tasks. Learning it here makes it easier to read and extend parser-related code in the pliron codebase.

At the same time, combine is not a requirement for your own compiler front end. If you are already productive with another parser library or approach, you can use that instead. The rest of the tutorial only requires an AST.

This flexibility is especially useful because combine may have a steeper learning curve than some alternatives.

The language

Kaleidoscope as used here is a simple integer language.

Example: Fibonacci program in Kaleidoscope:

def main(n) {
    return fib(n);
}

def fib(n) {
    if n < 2 {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Example: Factorial program in Kaleidoscope:

def main(n) {
    return factorial(n);
}

def factorial(n) {
    var result = 1;
    var i = n;
    while i > 0 {
        result = result * i;
        i = i - 1;
    }
    return result;
}

Supported constructs:

if and while are statements, so neither directly produces a value.

Grammar

program  := func_def* eof
func_def := 'def' ident '(' params ')' block
params   := (ident (',' ident)*)?
block    := '{' stmt* '}'
stmt     := 'var' ident ('=' expr)? ';'
           | ident '=' expr ';'
           | 'return' expr ';'
           | 'while' expr block
           | 'if' expr block 'else' block
           | expr ';'
expr     := cmp_expr
cmp_expr := add_expr (cmp_op add_expr)?
add_expr := mul_expr (('+' | '-') mul_expr)*
mul_expr := primary ('*' primary)*
primary  := integer
           | ident '(' (expr (',' expr)*)? ')'
           | ident
           | '(' expr ')'
cmp_op   := '<' | '>' | '==' | '!=' | '<=' | '>='
integer  := [0-9]+
ident    := [a-zA-Z_][a-zA-Z0-9_]*

Parsing into an AST

Before looking at any parsing code, it helps to know what we are building towards. The parser’s sole job is to turn source text into this tree of Rust types:

Expressions

Expressions always produce a value. All values are implicitly 64-bit integers.

#![allow(unused)]
fn main() {
/// An expression (has a value).
#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    /// A non-negative integer literal.
    Integer(i64),
    /// A variable reference.
    Variable(String),
    /// A binary operation.
    BinOp {
        op: BinOp,
        lhs: Box<Expr>,
        rhs: Box<Expr>,
    },
    /// A function call.
    Call { callee: String, args: Vec<Expr> },
}
}

Statements

Statements do not produce a value. If and While are the structured statement forms.

#![allow(unused)]
fn main() {
/// A statement (no direct value).
#[derive(Debug, Clone, PartialEq)]
pub enum Stmt {
    /// Variable declaration: `var name;` or `var name = expr;`
    VarDecl { name: String, init: Option<Expr> },
    /// Assignment to an existing variable: `name = expr;`
    Assign { name: String, value: Expr },
    /// Return statement: `return expr;`
    Return(Expr),
    /// While loop: `while cond { body }`.
    While { cond: Expr, body: Vec<Stmt> },
    /// Conditional statement: `if cond { then_body } else { else_body }`.
    If {
        cond: Expr,
        then_body: Vec<Stmt>,
        else_body: Vec<Stmt>,
    },
    /// An expression used as a statement: `expr;`
    Expr(Expr),
}
}

Functions

A function is just a name, a list of parameter names, and a list of statements.

#![allow(unused)]
fn main() {
/// A top-level function definition.
#[derive(Debug, Clone, PartialEq)]
pub struct Function {
    pub name: String,
    pub params: Vec<String>,
    pub body: Vec<Stmt>,
}
}

Note:

• The AST intentionally does not include types, all values are implicitly 64-bit integers.
• Expr and Stmt are recursive
  • BinOp and Call contain nested expression nodes,
  • If and While statements recursively contain statement blocks.
• This shapes how the parser must be structured (see below).

Lexical building blocks

Before we dive into the small parsers, here is how to read their signature:

#![allow(unused)]
fn main() {
fn my_parser<Input>() -> impl Parser<Input, Output = T> where Input: Stream<Token = char>, ...
}

Here, Input is the input stream type (here, a stream of chars), Output = T is the AST/token value the parser produces, and impl Parser<...> means “some concrete parser type” chosen by combine and inferred by Rust. The long where clause is mostly plumbing so the parser works with any compatible character stream; for learning, the key part is just:

Calling my_parser returns a parser that parses characters and returns a T on success.

Skipping Whitespaces

combine provides the spaces() parser, which matches zero or more whitespace characters. We wrap it once so that every token parser can end with .skip(ws()) and consume trailing spaces and newlines automatically.

#![allow(unused)]
fn main() {
fn ws<Input>() -> impl Parser<Input, Output = ()>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    spaces().map(|_| ())
}
}

Parsing Identifiers

An identifier starts with a letter or _, followed by any number of letters, digits, or _. combine’s letter(), alpha_num(), and char('_') match single characters; .or() tries alternatives; many() collects zero or more into a String. The first character and the rest are sequenced with a tuple and joined by .map().

#![allow(unused)]
fn main() {
fn ident_<Input>() -> impl Parser<Input, Output = String>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    (letter().or(char('_')), many(alpha_num().or(char('_'))))
        .map(|(first, rest): (char, String)| {
            let mut s = String::new();
            s.push(first);
            s.push_str(&rest);
            s
        })
        .skip(ws())
}
}

Keywords

A plain string("if") would match the prefix of iffy, leaving fy in the stream — wrong. not_followed_by(alpha_num().or(char('_'))) asserts that the matched text is not followed by an identifier character. attempt() wraps the whole thing so that on failure the cursor is rewound; without it, a partial match would leave the stream half-consumed.

#![allow(unused)]
fn main() {
fn keyword<Input>(kw: &'static str) -> impl Parser<Input, Output = ()>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    attempt(string(kw).skip(not_followed_by(alpha_num().or(char('_')))))
        .skip(ws())
        .map(|_| ())
}
}

Parsing expressions

Expressions are parsed in layers from highest to lowest precedence: primary -> mul_expr -> add_expr -> cmp_expr. Each layer calls the one below it, so precedence emerges naturally.

Primary expressions

A primary is the highest-precedence building block. choice!() tries each alternative in order and returns the first that succeeds.

A function call and a plain variable both start with an identifier, so the call branch is wrapped in attempt() to allow backtracking when no ( follows. between(tok('('), tok(')'), sep_by(...)) handles the argument list cleanly.

#![allow(unused)]
fn main() {
fn primary_<Input>() -> impl Parser<Input, Output = Expr>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    choice!(
        integer_(),
        // Function call must be tried before plain variable reference so that
        // `foo(...)` doesn't parse as variable `foo` followed by junk.
        attempt(
            ident_()
                .and(between(
                    tok('('),
                    tok(')'),
                    sep_by(
                        // Each argument is a full expression; trailing whitespace
                        // after the comma is already consumed by tok(',').
                        combine::parser(expr_fn::<Input>),
                        tok(','),
                    ),
                ))
                .map(|(callee, args)| Expr::Call { callee, args })
        ),
        between(tok('('), tok(')'), combine::parser(expr_fn::<Input>)),
        ident_().map(Expr::Variable)
    )
}
}

Arithmetic expressions and operator precedence

mul_expr_() handles * (higher precedence) and add_expr_() handles + and - on top of it. Both follow the same fold pattern:

1. Parse the leftmost operand.
2. Collect zero or more (operator, operand) pairs with many().
3. Fold left-to-right into nested Expr::BinOp nodes, so 1 + 2 + 3 becomes BinOp(Add, BinOp(Add, 1, 2), 3).

Multiplication is parsed in its own layer first:

#![allow(unused)]
fn main() {
fn mul_expr_<Input>() -> impl Parser<Input, Output = Expr>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    (
        primary_(),
        many::<Vec<_>, _, _>((tok('*').map(|_| BinOp::Mul)).and(primary_())),
    )
        .map(|(first, rest)| {
            rest.into_iter().fold(first, |acc, (op, rhs)| Expr::BinOp {
                op,
                lhs: Box::new(acc),
                rhs: Box::new(rhs),
            })
        })
}
}

and addition/subtraction on top of it:

#![allow(unused)]
fn main() {
fn add_expr_<Input>() -> impl Parser<Input, Output = Expr>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    (
        mul_expr_(),
        many::<Vec<_>, _, _>(
            choice!(tok('+').map(|_| BinOp::Add), tok('-').map(|_| BinOp::Sub)).and(mul_expr_()),
        ),
    )
        .map(|(first, rest)| {
            rest.into_iter().fold(first, |acc, (op, rhs)| Expr::BinOp {
                op,
                lhs: Box::new(acc),
                rhs: Box::new(rhs),
            })
        })
}
}

Handling recursion in combine

The grammar is recursive: expr -> primary -> if expr or (expr). combine’s impl Parser return type does not allow self-reference, so a named function pointer breaks the type cycle:

#![allow(unused)]
fn main() {
fn expr_fn<Input>(input: &mut Input) -> StdParseResult<Expr, Input>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    cmp_expr_().parse_stream(input).into_result()
}
}

expr_fn calls cmp_expr_() specifically because cmp_expr is the top expression layer in the grammar (expr := cmp_expr). That makes expr_fn the single “parse any expression” entry point while still preserving the full precedence stack (cmp on top of add on top of mul on top of primary).

Because fn(&mut Input) -> StdParseResult<O, Input> implements Parser<Input> in combine, expr_fn::<Input> can be used directly wherever a parser is expected. The concrete function-pointer type is what breaks the infinite type recursion that chained impl Parser returns would otherwise cause.

Parsing statements

Statements are what a function body contains. The while parser shows a typical pattern: parse a keyword, parse an expression for the condition, then parse a brace-delimited block of nested statements. The nested statements require the same stmt_fn function-pointer trick used for expressions above.

#![allow(unused)]
fn main() {
fn while_stmt_<Input>() -> impl Parser<Input, Output = Stmt>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    (
        keyword("while"),
        combine::parser(expr_fn::<Input>),
        between(tok('{'), tok('}'), many(combine::parser(stmt_fn::<Input>))),
    )
        .map(|(_, cond, body)| Stmt::While { cond, body })
}
}

The if statement parser follows the same block-structured pattern, with both branches containing nested statements:

#![allow(unused)]
fn main() {
fn if_stmt_<Input>() -> impl Parser<Input, Output = Stmt>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    (
        keyword("if"),
        combine::parser(expr_fn::<Input>),
        between(tok('{'), tok('}'), many(combine::parser(stmt_fn::<Input>))),
        keyword("else"),
        between(tok('{'), tok('}'), many(combine::parser(stmt_fn::<Input>))),
    )
        .map(|(_, cond, then_body, _, else_body)| Stmt::If {
            cond,
            then_body,
            else_body,
        })
}
}

The other statement kinds (var declaration, assignment, return, expression-statement) follow the same shape. They are all wired together in a single dispatcher:

#![allow(unused)]
fn main() {
fn stmt_<Input>() -> impl Parser<Input, Output = Stmt>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    choice!(
        var_decl_stmt_(),
        return_stmt_(),
        while_stmt_(),
        if_stmt_(),
        attempt(assign_stmt_()),
        expr_stmt_()
    )
}
}

Parsing functions and the full program

A function definition is a def keyword followed by a name, a parenthesised parameter list, and a block. sep_by(ident_(), tok(',')) collects the comma-separated parameter names into a Vec<String>.

#![allow(unused)]
fn main() {
fn func_def_<Input>() -> impl Parser<Input, Output = Function>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    (
        keyword("def"),
        ident_(),
        between(tok('('), tok(')'), sep_by(ident_(), tok(','))),
        block_(),
    )
        .map(|(_, name, params, body)| Function { name, params, body })
}
}

A program is just zero or more function definitions followed by end-of-file. ws().with(...) skips any leading whitespace before the first definition.

#![allow(unused)]
fn main() {
fn program_<Input>() -> impl Parser<Input, Output = Vec<Function>>
where
    Input: Stream<Token = char>,
    Input::Error: ParseError<Input::Token, Input::Range, Input::Position>,
{
    ws().with(many(func_def_())).skip(eof())
}
}

parse_program is the public entry point that drives the parser and converts combine’s error type into a plain String:

#![allow(unused)]
fn main() {
pub fn parse_program(src: &str) -> Result<Vec<Function>, String> {
    program_()
        .easy_parse(src)
        .map(|(funcs, _rest)| funcs)
        .map_err(|err| err.to_string())
}
}

Try it out

cargo test --example kaleidoscope -- test_ast_fibonacci --show-output
cargo test --example kaleidoscope -- test_ast_factorial --show-output

Next step

Chapter 2 defines the Kaleidoscope dialect operation set in a reusable module and demonstrates constructing those ops.

Chapter 2: The Kaleidoscope Dialect

In this chapter, we’ll learn some of pliron’s core IR concepts by defining a dialect for the Kaleidoscope language. As new IR concepts are introduced, you may find it useful to refer to the pliron documentation for details and examples.

The implementation for this chapter lives in examples/kaleidoscope/dialect.rs.

What is a Dialect?

pliron is an extensible compiler IR framework. This means that it does not restrict you to a fixed set of operations (or instructions) or types. Instead, you can define your own operations and types that capture the semantics of your source language.

A dialect is merely a grouping of operations, types, and attributes that define the IR for a particular domain, language or purpose. It serves as the foundation for representing and manipulating programs in that domain.

IR Entities / Structure

Every IR entity (such as an operation or type) is owned by a Context. Almost every method in the framework requires a Context argument to either look up existing entities or create new ones.

An Operation is a basic unit of execution. It has operands (or input values), results (or output values), attributes (or metadata), and may own regions.

A sequential list of operations forms a BasicBlock. At the end of a block, a terminator operation (like ReturnOp or BranchOp) indicates the end of the sequence and a possible transfer of control. Basic-blocks can have one or more arguments.

Operation results and BasicBlock arguments are SSA values. BasicBlock arguments are an alternative (but equivalent and more convenient) form of SSA ϕ-nodes.

The control-flow-graph (i.e., a directed graph of BasicBlocks) is contained within a Region. The Region itself is owned by a parent operation. For example, an IfOp owns two regions: one for the “then” block and one for the “else” block.

These three entities (Operation, BasicBlock, Region) form the core structural IR elements. They are the building blocks for representing programs in pliron.

All of these entities are owned by a Context, and are handled in the IR through a Ptr (e.g., Ptr<Operation>, Ptr<Region>, etc.). A Ptr can be dereferenced to access the underlying entity using the deref and deref_mut methods, which return the underlying Ref or RefMut of the entity. See interior mutability.

Types and Attributes

Every value (BasicBlock operand or Operation result) has a type. Types are first-class IR entities that can be defined by the user. For example, IntegerType in the builtin dialect represents integers. Dialects can define new types as needed.

Attributes allow attaching arbitrary metadata to operations. For example, in a ConstantOp, the constant value is stored as an attribute (e.g., IntegerAttr).

Ops

Operations are the core IR entities that represent instructions or statements in the program. Ops are thin wrappers around the underlying Operation struct, providing “opcode” specific APIs and invariants. For example, a BinOp represents a binary operation (like addition) and has specific attributes to indicate the kind of binary operation (e.g., BinOpKind::Add). You can imagine an Op to look like:

struct MyOp {
    op: Ptr<Operation>
}

impl MyOp {
  ...
}

Defining The Kaleidoscope Dialect

Let’s dive in now and see how we can define a ConstantOp.

ConstantOp: A Simple Example

The constant operation represents a literal integer value in the IR. It has no operands and one result (the constant value). The constant value is stored as an attribute of the operation.

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.constant",
    format = "attr($value, $IntegerAttr) ` : ` type($0)",
    interfaces = [NOpdsInterface<0>, OneResultInterface, NResultsInterface<1>],
    attributes = (value: IntegerAttr),
    verifier = "succ",
)]
pub struct ConstantOp;
}

We define ConstantOp as simply an empty struct, annotated with the pliron_op macro. In addition to adding the op: Ptr<Operation> field (that we saw above), this macro fills up boilerplate code required for implementing pliron’s Op trait.

The pliron_op macro has one mandatory argument: A string specifying the dialect and opcode name (e.g., "kaleidoscope.constant").

We then specify, using the attributes field in the macro, that this operation has one attribute named value of type IntegerAttr.

In this example, we’re also specifying the format for the Op. This defines the syntax for the operation when printed as IR. The full specification for the format syntax string is available in the docs. In this case, the format string says that the attribute (named value) containing the constant value (as an IntegerAttr) should be printed first, followed by the result type (after a colon).

Defining a syntax amounts to automatically deriving the Printable and Parsable traits for the operation, which are used by pliron’s IR printer and parser respectively.

The format field can have its string argument skipped, in which case a canonical (default) syntax is used.

Next, we have the interfaces field in the macro. Interfaces are Rust traits that are annotated with the #[op_interface] macro. Interfaces allow capturing common behaviour and invariants across multiple operations. In this case, NOpdsInterface<0> says that ConstantOp has zero operands, and OneResultInterface says that it has exactly one result.

And finally we have the verifier field, which specifies the verifier function for this operation. The verifier is responsible for enforcing invariants not captured by the interfaces that this Op implements. In this case, we can use the built-in succ verifier, which simply returns Ok(()) to indicate that the operation is always valid. For more complex invariants, you can write a custom verifier function by implementing the Verify trait for the Op.

Note: We have not defined IntegerAttr in this dialect. We are using the IntegerAttr defined in the builtin dialect. This is an important point: The IR is not restricted to using only the operations, types, and attributes defined in a single dialect. You can mix and match entities from different dialects as needed.

DeclOp: Variable Declarations

A DeclOp returns a pointer-typed result while storing source-level variable type as a TypeAttr. This represents local allocation of variables. (Analogous to LLVM’s AllocaInst) The PointerType is taken from pliron’s LLVM dialect.

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.decl",
    format = "attr($var_type, $TypeAttr) ` : ` type($0)",
    interfaces = [
        NOpdsInterface<0>,
        OneResultInterface,
        NResultsInterface<1>,
        ResultNOfType<0, PointerType>
    ],
    attributes = (var_type: TypeAttr),
    verifier = "succ",
)]
pub struct DeclOp;
}

BinOp: Binary Operations

BinOp has two operands (the left-hand side and right-hand side of the binary operation) and one result (the computed value). The specific binary operation (e.g., add, subtract, multiply, divide) is captured as an attribute (BinOpKind).

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.binop",
    format = "$0 ` `attr($kind, $BinOpKind) ` ` $1 ` : ` type($0)",
    interfaces = [
        AtLeastNOpdsInterface<1>,
        AtLeastNResultsInterface<1>,
        NOpdsInterface<2>,
        OneResultInterface,
        NResultsInterface<1>,
        SameOperandsType,
        SameResultsType,
        SameOperandsAndResultType
    ],
    attributes = (kind: BinOpKind),
    verifier = "succ"
)]
pub struct BinOp;
}

Here we show how one can define convenience methods on the typed wrapper (Op):

#![allow(unused)]
fn main() {
impl BinOp {
    /// Creates a new `BinOp` of the specified kind with the given operands.
    pub fn new(ctx: &mut Context, kind: BinOpKind, lhs: Value, rhs: Value) -> Self {
        let result_ty = lhs.get_type(ctx);
        let op = Operation::new(
            ctx,
            Self::get_concrete_op_info(),
            vec![result_ty],
            vec![lhs, rhs],
            vec![],
            0,
        );
        let op = BinOp { op };
        op.set_attr_kind(ctx, kind);
        op
    }

    /// Returns the `BinOpKind` of this `BinOp`.
    pub fn kind(&self, ctx: &Context) -> BinOpKind {
        *self
            .get_attr_kind(ctx)
            .expect("BinOp must carry kind attribute")
    }

    /// Returns the left-hand side operand of this `BinOp`.
    pub fn lhs(&self, ctx: &Context) -> Value {
        self.get_operation().deref(ctx).get_operand(0)
    }

    /// Returns the right-hand side operand of this `BinOp`.
    pub fn rhs(&self, ctx: &Context) -> Value {
        self.get_operation().deref(ctx).get_operand(1)
    }
}
}

CallOp

The CallOp represents a function call. It has a variable number of operands (the arguments to the function) and one result (the return value of the function). The callee function is captured as an attribute (an IdentifierAttr).

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.call",
    format = "`@`attr($callee, $IdentifierAttr) `(` operands(CharSpace(`,`)) `)` : type($0)",
    interfaces = [NResultsInterface<1>],
    attributes = (callee: IdentifierAttr),
    verifier = "succ",
)]
pub struct CallOp;
}

Regions and Blocks

Structured control flow is represented through regions and blocks:

IfOp

The IfOp has two regions: one for the “then” block and one for the “else” block. Each region here contains a single block (captured by the SingleBlockRegionInterface), which in turn contains a sequence of operations.

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.if",
    format = "$0 ` then ` region($0) ` else ` region($1)",
    interfaces = [
        NOpdsInterface<1>,
        NResultsInterface<0>,
        NRegionsInterface<2>,
        SingleBlockRegionInterface
    ],
    verifier = "succ",
)]
pub struct IfOp;
}

WhileOp

The WhileOp has a single region capturing the loop body. The loop condition is represented as an operand of the op. Here we define the semantics of the condition to be a pointer (to an integer value), captured by the OperandNOfType<0, PointerType> interface specification, where a non-zero value (of the pointee) is considered true and zero is false. The operand being a pointer allows the loop condition to be updated within the loop body. Similar to DeclOp, the pointer type is taken from pliron’s LLVM dialect.

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.while",
    format = "`*`$0 ` do ` region($0)",
    interfaces = [
        OperandNOfType<0, PointerType>,
        NResultsInterface<0>,
        NRegionsInterface<1>,
        SingleBlockRegionInterface
    ],
    verifier = "succ",
)]
pub struct WhileOp;
}

YieldOp

The YieldOp serves as a terminator for the body region of WhileOp and IfOp. It has no operands or results, and simply indicates the end of the structured region.

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.yield",
    format = "",
    interfaces = [IsTerminatorInterface, NResultsInterface<0>, NOpdsInterface<0>],
    verifier = "succ",
)]
pub struct YieldOp;
}

ReturnOp

The ReturnOp serves as a terminator from a function body region. It has one operand, which is the value being returned from the function.

To illustrate the use of a custom verifier, ReturnOp implements the Verify trait to enforce the invariant that it must have exactly one operand (this could also have been enforced declaratively using NOpdsInterface<1>).

#![allow(unused)]
fn main() {
#[pliron_op(
    name = "kaleidoscope.return",
    format = "$0",
    interfaces = [IsTerminatorInterface],
)]
pub struct ReturnOp;
}

The custom verifier:

#![allow(unused)]
fn main() {
impl Verify for ReturnOp {
    fn verify(&self, ctx: &Context) -> Result<()>
    where
        Self: Sized,
    {
        let n_operands = self.get_operation().deref(ctx).get_num_operands();
        if n_operands != 1 {
            return verify_err!(
                self.loc(ctx),
                "kaleidoscope.return expects exactly 1 operand, found {}",
                n_operands
            );
        }
        Ok(())
    }
}
}

Construction Example

In this section, we manually construct IR, using pliron APIs and utilities for a specific simple Fibonacci function. This is to illustrate how the IR is built up from the basic entities (operations, blocks, regions) and how the dialect ops are used in practice. The next chapter shows how to do this systematically by translating (lowering) the AST into this IR.

Pseudocode in Kaleidoscope for the function being generated:

#![allow(unused)]
fn main() {
// Kaleidoscope pseudocode for the generated function:
//
// def main() {
//   var a = 0;
//   var b = 1;
//   var i = 0;
//   var n = 10;
//
//   while i < n {
//     var tmp = a + b;
//     a = b;
//     b = tmp;
//     i = i + 1;
//   }
//
//   return b;
// }
}

Rather than reading the entire construction test as one block, it is easier to follow it in the same order as the IR is assembled.

1. Set up the context, module, and entry block

First we create the Context, define the function type, create a module and a main function, and position an inserter at the end of the entry block.

#![allow(unused)]
fn main() {
        let ctx = &mut Context::new();
        let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);

        let module = ModuleOp::new(ctx, "fib_test".try_into().expect("valid module name"));
        let main_ty = FunctionType::get(ctx, vec![], vec![i64_ty.into()]);
        let main_fn = FuncOp::new(
            ctx,
            "main".try_into().expect("valid function name"),
            main_ty,
        );
        module.append_operation(ctx, main_fn.get_operation(), 0);

        let entry = main_fn.get_entry_block(ctx);
        let mut ins = OpInserter::new_at_block_end(entry);
}

At this point we have the outer container structure in place, but the function body is still empty.

2. Allocate mutable slots for the variables

The Fibonacci implementation uses mutable local state (a, b, tmp, i, n, and the loop-condition slot), so the next step is to create DeclOps for each one.

#![allow(unused)]
fn main() {
        // Mutable slots: a, b, tmp, i, and the iteration limit n.
        let slot_a = DeclOp::new(ctx, i64_ty.into());
        set_operation_result_name(ctx, slot_a.get_operation(), 0, "a".try_into().ok());
        ins.append_op(ctx, &slot_a);
        let slot_b = DeclOp::new(ctx, i64_ty.into());
        set_operation_result_name(ctx, slot_b.get_operation(), 0, "b".try_into().ok());
        ins.append_op(ctx, &slot_b);
        let slot_tmp = DeclOp::new(ctx, i64_ty.into());
        set_operation_result_name(ctx, slot_tmp.get_operation(), 0, "tmp".try_into().ok());
        ins.append_op(ctx, &slot_tmp);
        let slot_i = DeclOp::new(ctx, i64_ty.into());
        set_operation_result_name(ctx, slot_i.get_operation(), 0, "i".try_into().ok());
        ins.append_op(ctx, &slot_i);
        let slot_n = DeclOp::new(ctx, i64_ty.into());
        set_operation_result_name(ctx, slot_n.get_operation(), 0, "n".try_into().ok());
        ins.append_op(ctx, &slot_n);
        // A mutable slot for the loop condition (while cond_ptr do ...).
        let slot_cond_ptr = DeclOp::new(ctx, i64_ty.into());
        set_operation_result_name(
            ctx,
            slot_cond_ptr.get_operation(),
            0,
            "cond_ptr".try_into().ok(),
        );
        ins.append_op(ctx, &slot_cond_ptr);
}

Notice that we also attach result names such as a and b. These names are not required for correctness, but they make the printed IR much easier to read.

3. Initialize the state and create the loop shell

Next we materialize the constants, store the initial values into the mutable slots, compute the initial loop condition i < n, and build the WhileOp itself.

#![allow(unused)]
fn main() {
        // Initialize: a=0, b=1, i=0, n=10.
        let c0 = ConstantOp::new_i64(ctx, 0);
        ins.append_op(ctx, &c0);
        let c1 = ConstantOp::new_i64(ctx, 1);
        ins.append_op(ctx, &c1);
        let c10 = ConstantOp::new_i64(ctx, 10);
        ins.append_op(ctx, &c10);

        let store_a0 = StoreOp::new(ctx, slot_a.get_result(ctx), c0.get_result(ctx));
        ins.append_op(ctx, &store_a0);
        let store_b1 = StoreOp::new(ctx, slot_b.get_result(ctx), c1.get_result(ctx));
        ins.append_op(ctx, &store_b1);
        let store_i0 = StoreOp::new(ctx, slot_i.get_result(ctx), c0.get_result(ctx));
        ins.append_op(ctx, &store_i0);
        let store_n10 = StoreOp::new(ctx, slot_n.get_result(ctx), c10.get_result(ctx));
        ins.append_op(ctx, &store_n10);

        // Loop condition i < n.
        let i_before = LoadOp::new(ctx, slot_i.get_result(ctx), i64_ty.into());
        ins.append_op(ctx, &i_before);
        let n_before = LoadOp::new(ctx, slot_n.get_result(ctx), i64_ty.into());
        ins.append_op(ctx, &n_before);
        let cond = BinOp::new(
            ctx,
            BinOpKind::Lt,
            i_before.get_result(ctx),
            n_before.get_result(ctx),
        );
        ins.append_op(ctx, &cond);
        let store_cond_ptr = StoreOp::new(ctx, slot_cond_ptr.get_result(ctx), cond.get_result(ctx));
        ins.append_op(ctx, &store_cond_ptr);

        let while_op = WhileOp::new(ctx, slot_cond_ptr.get_result(ctx));
        ins.append_op(ctx, &while_op);
}

The important detail here is that WhileOp takes a pointer to the condition slot, not the condition value directly. That lets the loop body recompute and update the condition on every iteration.

4. Fill in the loop body region

Once the WhileOp exists, we create its body block and populate it with the actual Fibonacci update logic.

#![allow(unused)]
fn main() {
        let while_region = while_op.body_region(ctx);
        let while_block = BasicBlock::new(
            ctx,
            Some("while_body".try_into().expect("valid block name")),
            vec![],
        );
        while_block.insert_at_front(while_region, ctx);
        let mut while_ins = OpInserter::new_at_block_end(while_block);

        // tmp = a + b; a = b; b = tmp; i = i + 1
        let a_val = LoadOp::new(ctx, slot_a.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &a_val);
        let b_val = LoadOp::new(ctx, slot_b.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &b_val);
        let sum = BinOp::new(
            ctx,
            BinOpKind::Add,
            a_val.get_result(ctx),
            b_val.get_result(ctx),
        );
        while_ins.append_op(ctx, &sum);
        let store_tmp = StoreOp::new(ctx, slot_tmp.get_result(ctx), sum.get_result(ctx));
        while_ins.append_op(ctx, &store_tmp);

        let b_for_a = LoadOp::new(ctx, slot_b.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &b_for_a);
        let store_a = StoreOp::new(ctx, slot_a.get_result(ctx), b_for_a.get_result(ctx));
        while_ins.append_op(ctx, &store_a);

        let tmp_for_b = LoadOp::new(ctx, slot_tmp.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &tmp_for_b);
        let store_b = StoreOp::new(ctx, slot_b.get_result(ctx), tmp_for_b.get_result(ctx));
        while_ins.append_op(ctx, &store_b);

        let i_val = LoadOp::new(ctx, slot_i.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &i_val);
        let one_step = ConstantOp::new_i64(ctx, 1);
        while_ins.append_op(ctx, &one_step);
        let i_next = BinOp::new(
            ctx,
            BinOpKind::Add,
            i_val.get_result(ctx),
            one_step.get_result(ctx),
        );
        while_ins.append_op(ctx, &i_next);
        let store_i = StoreOp::new(ctx, slot_i.get_result(ctx), i_next.get_result(ctx));
        while_ins.append_op(ctx, &store_i);

        // i is updated, now do the comparison again
        let i_inc = LoadOp::new(ctx, slot_i.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &i_inc);
        let n_for_cond = LoadOp::new(ctx, slot_n.get_result(ctx), i64_ty.into());
        while_ins.append_op(ctx, &n_for_cond);
        let cond_next = BinOp::new(
            ctx,
            BinOpKind::Lt,
            i_inc.get_result(ctx),
            n_for_cond.get_result(ctx),
        );
        while_ins.append_op(ctx, &cond_next);
        let store_cond = StoreOp::new(
            ctx,
            slot_cond_ptr.get_result(ctx),
            cond_next.get_result(ctx),
        );
        while_ins.append_op(ctx, &store_cond);

        let while_yield = YieldOp::new(ctx);
        while_ins.append_op(ctx, &while_yield);
}

This block mirrors the source program closely: compute tmp = a + b, rotate a and b, increment i, recompute the loop condition, then end the region with YieldOp.

5. Return the result and verify the IR

After the loop, the function loads the final value of b, returns it, and runs verification on the constructed module.

#![allow(unused)]
fn main() {
        let fib_result = LoadOp::new(ctx, slot_b.get_result(ctx), i64_ty.into());
        ins.append_op(ctx, &fib_result);
        let ret = ReturnOp::new(ctx, fib_result.get_result(ctx));
        ins.append_op(ctx, &ret);

        verify_op(&module, ctx).expect("constructed fibonacci IR should verify");
        println!("{}", module.get_operation().disp(ctx));
}

This last step is worth keeping in mind whenever you construct IR manually: verification is the cheapest way to catch structural mistakes early.

Try it out

cargo test --example kaleidoscope -- build_fib_example --show-output

This prints Kaleidoscope IR for the Fibonacci function shown above. We suggest studying the test and the printed IR together to understand how the dialect ops are used to construct the IR.

Exercise: Try adding a test to build the factorial function similarly and print its IR.

Next step

In this chapter we manually built the IR for a specific Kaleidoscope program. Chapter 3 shows how to lower the AST into this IR, which means we can parse any Kaleidoscope program into an AST and then lower it into IR.

Chapter 3: Lowering the AST to IR

In Chapter 2 we hand-built IR for a specific Fibonacci function. This chapter shows how to do that systematically for any Kaleidoscope program by lowering the AST produced in Chapter 1 into the dialect ops defined in Chapter 2.

The implementation for this chapter lives in examples/kaleidoscope/from_ast.rs

Design

Every Kaleidoscope value is a 64-bit signless integer (i64). The key design decisions are:

• All variables are memory-backed. Every local variable and every function parameter is backed by a DeclOp slot (analogous to LLVM’s alloca). Reads become LoadOps; writes become StoreOps. This avoids having to worry about SSA form.
• Control flow uses regions. IfOp owns two regions (then / else) and WhileOp owns one region (the loop body). Each region gets its own new BasicBlock.
• WhileOp holds a condition pointer. Rather than threading a boolean value as an argument, the condition is stored in a dedicated DeclOp slot in the outer block and updated at the end of each loop iteration.

Entry point

The public API is a single function. It takes an AST Function node and produces a FuncOp inside the provided Context:

#![allow(unused)]
fn main() {
pub fn lower_function(ctx: &mut Context, func: &Function) -> Result<FuncOp> {
    let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);

    // Build the function type: all params are i64, single i64 return.
    let param_tys: Vec<_> = func.params.iter().map(|_| i64_ty.into()).collect();
    let func_ty = FunctionType::get(ctx, param_tys, vec![i64_ty.into()]);

    let func_op = FuncOp::new(
        ctx,
        func.name
            .as_str()
            .try_into()
            .expect("invalid function name"),
        func_ty,
    );

    let entry = func_op.get_entry_block(ctx);
    let mut ins = OpInserter::new_at_block_end(entry);
    let mut var_map = VarMap::default();

    // Spill each function parameter (block argument) into a mutable DeclOp slot.
    for (idx, param_name) in func.params.iter().enumerate() {
        let param_val = entry.deref(ctx).get_argument(idx);
        let slot = DeclOp::new(ctx, i64_ty.into());
        let slot_val = slot.get_result(ctx);
        ins.append_op(ctx, &slot);
        let store = StoreOp::new(ctx, slot_val, param_val);
        ins.append_op(ctx, &store);
        var_map.insert(param_name.clone(), slot_val);
    }

    lower_stmts(ctx, &mut ins, &mut var_map, &func.body)?;

    // If no terminator was emitted (e.g., function ends with an `if` where both
    // branches return), add a fallback return of 0 to satisfy the verifier.
    if entry.deref(ctx).get_terminator(ctx).is_none() {
        let zero = ConstantOp::new_i64(ctx, 0);
        let zero_val = zero.get_result(ctx);
        ins.append_op(ctx, &zero);
        let ret = ReturnOp::new(ctx, zero_val);
        ins.append_op(ctx, &ret);
    }
    Ok(func_op)
}
}

Two type aliases keep the rest of the code concise:

#![allow(unused)]
fn main() {
/// Inserter type used throughout this module.
type OpInserter = IRInserter<DummyListener>;

/// Maps variable names to the slot-pointer [`Value`] produced by their [`DeclOp`].
type VarMap = FxHashMap<String, Value>;
}

OpInserter is an IRInserter with a no-op listener. It tracks a cursor position inside a block and appends ops there via append_op. VarMap maps source-level variable names to the Value (result of a DeclOp) that holds the variable’s storage slot.

Creating the FuncOp

lower_function first creates an empty FuncOp with the right type, then obtains the entry block and initialises the inserter at its end:

#![allow(unused)]
fn main() {
pub fn lower_function(ctx: &mut Context, func: &Function) -> Result<FuncOp> {
    let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);

    // Build the function type: all params are i64, single i64 return.
    let param_tys: Vec<_> = func.params.iter().map(|_| i64_ty.into()).collect();
    let func_ty = FunctionType::get(ctx, param_tys, vec![i64_ty.into()]);

    let func_op = FuncOp::new(
        ctx,
        func.name
            .as_str()
            .try_into()
            .expect("invalid function name"),
        func_ty,
    );

    let entry = func_op.get_entry_block(ctx);
    let mut ins = OpInserter::new_at_block_end(entry);
    let mut var_map = VarMap::default();

    // Spill each function parameter (block argument) into a mutable DeclOp slot.
    for (idx, param_name) in func.params.iter().enumerate() {
        let param_val = entry.deref(ctx).get_argument(idx);
        let slot = DeclOp::new(ctx, i64_ty.into());
        let slot_val = slot.get_result(ctx);
        ins.append_op(ctx, &slot);
        let store = StoreOp::new(ctx, slot_val, param_val);
        ins.append_op(ctx, &store);
        var_map.insert(param_name.clone(), slot_val);
    }

    lower_stmts(ctx, &mut ins, &mut var_map, &func.body)?;

    // If no terminator was emitted (e.g., function ends with an `if` where both
    // branches return), add a fallback return of 0 to satisfy the verifier.
    if entry.deref(ctx).get_terminator(ctx).is_none() {
        let zero = ConstantOp::new_i64(ctx, 0);
        let zero_val = zero.get_result(ctx);
        ins.append_op(ctx, &zero);
        let ret = ReturnOp::new(ctx, zero_val);
        ins.append_op(ctx, &ret);
    }
    Ok(func_op)
}
}

(Only the setup and fallback parts are discussed in detail below.)

Spilling parameters

Every function parameter arrives as a basic-block argument. To allow mutation later, each argument is immediately spilled into a DeclOp slot:

#![allow(unused)]
fn main() {
    // Spill each function parameter (block argument) into a mutable DeclOp slot.
    for (idx, param_name) in func.params.iter().enumerate() {
        let param_val = entry.deref(ctx).get_argument(idx);
        let slot = DeclOp::new(ctx, i64_ty.into());
        let slot_val = slot.get_result(ctx);
        ins.append_op(ctx, &slot);
        let store = StoreOp::new(ctx, slot_val, param_val);
        ins.append_op(ctx, &store);
        var_map.insert(param_name.clone(), slot_val);
    }
}

entry.deref(ctx).get_argument(idx) returns the Value of the idx-th block argument. DeclOp::new_with_type allocates a pointer-typed slot; StoreOp writes the initial value into it.

Fallback terminator

After lowering the body, the entry block might still lack a terminator. This can happen when the source function ends with an if statement where both branches contain a return. In that case a fallback return 0 is appended:

#![allow(unused)]
fn main() {
    // If no terminator was emitted (e.g., function ends with an `if` where both
    // branches return), add a fallback return of 0 to satisfy the verifier.
    if entry.deref(ctx).get_terminator(ctx).is_none() {
        let zero = ConstantOp::new_i64(ctx, 0);
        let zero_val = zero.get_result(ctx);
        ins.append_op(ctx, &zero);
        let ret = ReturnOp::new(ctx, zero_val);
        ins.append_op(ctx, &ret);
    }
}

Lowering statements

Statements are lowered by two helpers. lower_stmts iterates a slice and delegates each item to lower_stmt, short-circuiting on the first error:

#![allow(unused)]
fn main() {
fn lower_stmts(
    ctx: &mut Context,
    ins: &mut OpInserter,
    var_map: &mut VarMap,
    stmts: &[Stmt],
) -> Result<bool> {
    let mut terminated = false;
    for stmt in stmts {
        terminated = lower_stmt(ctx, ins, var_map, stmt)?;
    }
    Ok(terminated)
}
}

Both functions return Result<bool> where true means the last op emitted was a block terminator (ReturnOp). This signal is used to suppress redundant YieldOp terminators in if / while regions.

Variable declaration

var name; or var name = expr; allocates a slot, registers it in the VarMap, and optionally stores an initial value:

#![allow(unused)]
fn main() {
        Stmt::VarDecl { name, init } => {
            let slot = DeclOp::new(ctx, i64_ty.into());
            let slot_val = slot.get_result(ctx);
            ins.append_op(ctx, &slot);
            var_map.insert(name.clone(), slot_val);

            if let Some(init_expr) = init {
                let val = lower_expr(ctx, ins, var_map, init_expr)?;
                let store = StoreOp::new(ctx, slot_val, val);
                ins.append_op(ctx, &store);
            }
            Ok(false)
        }
}

Assignment

name = expr; looks up the existing slot in VarMap and emits a StoreOp. If the variable was never declared, input_error! returns a structured error instead of panicking:

#![allow(unused)]
fn main() {
        Stmt::Assign { name, value } => {
            let val = lower_expr(ctx, ins, var_map, value)?;
            let slot = *var_map.get(name.as_str()).ok_or_else(|| {
                input_error!(
                    Location::Unknown,
                    "assignment to undeclared variable: {name}"
                )
            })?;
            let store = StoreOp::new(ctx, slot, val);
            ins.append_op(ctx, &store);
            Ok(false)
        }
}

Return

return expr; lowers the expression, emits ReturnOp, and signals that the block is now terminated:

#![allow(unused)]
fn main() {
        Stmt::Return(expr) => {
            let val = lower_expr(ctx, ins, var_map, expr)?;
            let ret = ReturnOp::new(ctx, val);
            ins.append_op(ctx, &ret);
            Ok(true) // ReturnOp is a block terminator
        }
}

If statement

if cond { then } else { else } emits an IfOp, then builds two new blocks — one for each region. Each branch is lowered recursively. A YieldOp is appended only when the branch did not end with a return:

#![allow(unused)]
fn main() {
        Stmt::If {
            cond,
            then_body,
            else_body,
        } => {
            let cond_val = lower_expr(ctx, ins, var_map, cond)?;
            let if_op = IfOp::new(ctx, cond_val);
            ins.append_op(ctx, &if_op);

            // Then region: add YieldOp only if the branch didn't terminate.
            let then_block = BasicBlock::new(ctx, None, vec![]);
            then_block.insert_at_front(if_op.then_region(ctx), ctx);
            let mut then_ins = OpInserter::new_at_block_end(then_block);
            let mut then_vars = var_map.clone();
            let then_terminated = lower_stmts(ctx, &mut then_ins, &mut then_vars, then_body)?;
            if !then_terminated {
                let then_yield = YieldOp::new(ctx);
                then_ins.append_op(ctx, &then_yield);
            }

            // Else region: add YieldOp only if the branch didn't terminate.
            let else_block = BasicBlock::new(ctx, None, vec![]);
            else_block.insert_at_front(if_op.else_region(ctx), ctx);
            let mut else_ins = OpInserter::new_at_block_end(else_block);
            let mut else_vars = var_map.clone();
            let else_terminated = lower_stmts(ctx, &mut else_ins, &mut else_vars, else_body)?;
            if !else_terminated {
                let else_yield = YieldOp::new(ctx);
                else_ins.append_op(ctx, &else_yield);
            }

            Ok(false) // IfOp itself is not a terminator in the outer block
        }
}

Note that IfOp itself is not a block terminator in the outer block, so lower_stmt_if returns Ok(false).

While loop

while cond { body } uses the memory-backed condition pattern described in the design section above. Before entering the loop, the condition is evaluated and stored in a fresh DeclOp slot. At the end of each iteration, the condition is re-evaluated and the slot is updated. A YieldOp closes the body region (if it doesn’t already end with a return):

#![allow(unused)]
fn main() {
        Stmt::While { cond, body } => {
            // Allocate the condition slot in the outer block.
            let cond_slot = DeclOp::new(ctx, i64_ty.into());
            let cond_slot_val = cond_slot.get_result(ctx);
            ins.append_op(ctx, &cond_slot);

            // Compute the initial condition and store it.
            let init_cond = lower_expr(ctx, ins, var_map, cond)?;
            let init_store = StoreOp::new(ctx, cond_slot_val, init_cond);
            ins.append_op(ctx, &init_store);

            let while_op = WhileOp::new(ctx, cond_slot_val);
            ins.append_op(ctx, &while_op);

            // Build the loop body.
            let body_block = BasicBlock::new(ctx, None, vec![]);
            body_block.insert_at_front(while_op.body_region(ctx), ctx);
            let mut body_ins = OpInserter::new_at_block_end(body_block);
            let mut body_vars = var_map.clone();
            let body_terminated = lower_stmts(ctx, &mut body_ins, &mut body_vars, body)?;

            if !body_terminated {
                // Re-evaluate the condition at the end of the body and update the slot.
                let next_cond = lower_expr(ctx, &mut body_ins, &body_vars, cond)?;
                let next_store = StoreOp::new(ctx, cond_slot_val, next_cond);
                body_ins.append_op(ctx, &next_store);
                let body_yield = YieldOp::new(ctx);
                body_ins.append_op(ctx, &body_yield);
            }

            Ok(false) // WhileOp itself is not a terminator in the outer block
        }
}

Expression statement

A bare expr; lowers the expression for its side effects and discards the resulting value:

#![allow(unused)]
fn main() {
        Stmt::Expr(expr) => {
            lower_expr(ctx, ins, var_map, expr)?;
            Ok(false)
}

Lowering expressions

lower_expr matches on the Expr variant and returns the Value that holds the computed result:

#![allow(unused)]
fn main() {
fn lower_expr(
    ctx: &mut Context,
    ins: &mut OpInserter,
    var_map: &VarMap,
    expr: &Expr,
) -> Result<Value> {
    let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);

    match expr {
        // ── integer literal ───────────────────────────────────────────────
        Expr::Integer(n) => {
            let op = ConstantOp::new_i64(ctx, *n);
            let val = op.get_result(ctx);
            ins.append_op(ctx, &op);
            Ok(val)
        }

        // ── variable reference ────────────────────────────────────────────
        Expr::Variable(name) => {
            let slot = *var_map.get(name.as_str()).ok_or_else(|| {
                input_error!(
                    Location::Unknown,
                    "reference to undeclared variable: {name}"
                )
            })?;
            let load = LoadOp::new(ctx, slot, i64_ty.into());
            let val = load.get_result(ctx);
            ins.append_op(ctx, &load);
            Ok(val)
        }

        // ── binary operation ──────────────────────────────────────────────
        Expr::BinOp { op, lhs, rhs } => {
            let lhs_val = lower_expr(ctx, ins, var_map, lhs)?;
            let rhs_val = lower_expr(ctx, ins, var_map, rhs)?;
            let kind = ast_binop_to_kind(op);
            let bin_op = BinOp::new(ctx, kind, lhs_val, rhs_val);
            let val = bin_op.get_result(ctx);
            ins.append_op(ctx, &bin_op);
            Ok(val)
        }

        // ── function call ─────────────────────────────────────────────────
        Expr::Call { callee, args } => {
            let mut arg_vals = Vec::with_capacity(args.len());
            for a in args {
                arg_vals.push(lower_expr(ctx, ins, var_map, a)?);
            }
            let callee_id = callee.as_str().try_into().expect("valid callee identifier");
            let call_op = CallOp::new(ctx, IdentifierAttr::new(callee_id), arg_vals, i64_ty.into());
            let val = call_op.get_operation().deref(ctx).get_result(0);
            let val = { val }; // reborrow to release ctx ref before append
            ins.append_op(ctx, &call_op);
            Ok(val)
    }
}
}

Integer literal

A literal is wrapped in a ConstantOp. The result value is returned:

#![allow(unused)]
fn main() {
        Expr::Integer(n) => {
            let op = ConstantOp::new_i64(ctx, *n);
            let val = op.get_result(ctx);
            ins.append_op(ctx, &op);
            Ok(val)
        }
}

Variable reference

A variable reference looks up the slot in VarMap and emits a LoadOp to read its current value. An undeclared variable is reported as an InvalidInput error using the input_error! macro:

#![allow(unused)]
fn main() {
        Expr::Variable(name) => {
            let slot = *var_map.get(name.as_str()).ok_or_else(|| {
                input_error!(
                    Location::Unknown,
                    "reference to undeclared variable: {name}"
                )
            })?;
            let load = LoadOp::new(ctx, slot, i64_ty.into());
            let val = load.get_result(ctx);
            ins.append_op(ctx, &load);
            Ok(val)
        }
}

Binary operation

Both operands are lowered recursively, then a BinOp is created with the appropriate BinOpKind attribute:

#![allow(unused)]
fn main() {
        Expr::BinOp { op, lhs, rhs } => {
            let lhs_val = lower_expr(ctx, ins, var_map, lhs)?;
            let rhs_val = lower_expr(ctx, ins, var_map, rhs)?;
            let kind = ast_binop_to_kind(op);
            let bin_op = BinOp::new(ctx, kind, lhs_val, rhs_val);
            let val = bin_op.get_result(ctx);
            ins.append_op(ctx, &bin_op);
            Ok(val)
        }
}

Function call

Arguments are lowered in order and collected into a Vec. A CallOp is then created with the callee name as an IdentifierAttr:

#![allow(unused)]
fn main() {
        Expr::Call { callee, args } => {
            let mut arg_vals = Vec::with_capacity(args.len());
            for a in args {
                arg_vals.push(lower_expr(ctx, ins, var_map, a)?);
            }
            let callee_id = callee.as_str().try_into().expect("valid callee identifier");
            let call_op = CallOp::new(ctx, IdentifierAttr::new(callee_id), arg_vals, i64_ty.into());
            let val = call_op.get_operation().deref(ctx).get_result(0);
            let val = { val }; // reborrow to release ctx ref before append
            ins.append_op(ctx, &call_op);
            Ok(val)
}

Note the reborrow trick: call_op.get_operation().deref(ctx) borrows ctx immutably, so the result val must be captured before passing call_op to append_op, which borrows ctx mutably.

Note: The general guideline around calling deref or deref_mut on Ptr<T> is to keep the borrowed value (Ref<T> or RefMut<T>) around for as little time as possible, and to avoid passing it to any function that might call back into the context.

Error handling

All lowering functions return pliron::result::Result<T>. Errors are propagated with ?. The input_error! macro creates a pliron::result::Error with kind ErrorKind::InvalidInput and an optional source location. Because the Kaleidoscope AST does not carry source positions, Location::Unknown is used throughout.

Tests

The test module defines a helper that parses a source string, lowers every function into a fresh module, verifies the IR, and prints it:

#![allow(unused)]
fn main() {
    fn lower_program(src: &str) -> String {
        let funcs = parse_program(src).expect("parse error");
        let ctx = &mut Context::new();
        let module = ModuleOp::new(ctx, "test".try_into().expect("valid module name"));
        for func in &funcs {
            let func_op = lower_function(ctx, func).expect("lowering failed");
            module.append_operation(ctx, func_op.get_operation(), 0);
        }
        verify_op(&module, ctx).expect("IR verification failed");
        format!("{}", module.get_operation().disp(ctx))
    }
}

Try it out

cargo test --example kaleidoscope -- fibonacci_from_ast --show-output
cargo test --example kaleidoscope -- factorial_from_ast --show-output
cargo test --example kaleidoscope -- inline_fibonacci_from_ast --show-output

Each test prints the lowered IR so you can inspect how the AST maps to ops.

Next step

Chapter 4 lowers the Kaleidoscope dialect into a lower-level LLVM dialect.

Chapter 4: Lowering to the LLVM Dialect

In Chapter 3 we produced IR in the Kaleidoscope dialect — operations like kaleidoscope.if, kaleidoscope.binop, and kaleidoscope.while that still carry high-level, structured semantics. This chapter converts that IR into the LLVM dialect, where all control flow is flat (basic blocks + branches) and every op corresponds closely to an LLVM instruction.

The implementation for this chapter lives in examples/kaleidoscope/to_llvm.rs.

Design: Dialect Conversion

pliron ships a dialect conversion framework in pliron::irbuild::dialect_conversion. It is deliberately simpler than MLIR’s equivalent:

• No unrealized conversion casts. Types that do not need conversion are kept as-is.
• Definitions before uses. The framework guarantees that when an op’s rewrite callback fires, all operands have already been converted.
• Each op rewrites itself. Rather than a monolithic pattern-match switch, each op implements (in this case) the ToLLVMDialect interface from pliron_llvm.

The three moving parts are:

The DialectConversion trait

#![allow(unused)]
fn main() {
pub trait DialectConversion {
    fn can_convert_op(&self, ctx: &Context, op: Ptr<Operation>) -> bool;
    fn rewrite(
        &mut self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        op: Ptr<Operation>,
        operands_info: &OperandsInfo,
    ) -> Result<()>;
    // optional: can_convert_type, convert_type
}
}

can_convert_op is the filter. rewrite is called for every op that passes the filter, with the insertion point already positioned before the op.

OperandsInfo

The operands_info parameter gives each rewrite access to the history of type changes its operands went through during the conversion pass. For the Kaleidoscope lowering we do not convert types (everything stays i64), so this is left unused in most rewrites.

apply_dialect_conversion

#![allow(unused)]
fn main() {
pub fn apply_dialect_conversion<C: DialectConversion>(
    ctx: &mut Context,
    conversion: &mut C,
    op: Ptr<Operation>,
) -> Result<()>
}

The algorithm walks the IR tree rooted at op, collecting convertible ops into a worklist. It then repeatedly pops from the worklist, and ensures to process operand-defining ops first. After each rewrite, recorded mutations are inspected: erased ops are dropped from the worklist, newly inserted ops are added (if required), and block-argument types are updated if any successor references changed.

The conversion driver: KalToLLVM

Our driver is a zero-field struct that implements DialectConversion:

#![allow(unused)]
fn main() {
pub struct KalToLLVM;

impl DialectConversion for KalToLLVM {
    fn can_convert_op(&self, ctx: &Context, op: Ptr<Operation>) -> bool {
        op_impls::<dyn ToLLVMDialect>(&*Operation::get_op_dyn(op, ctx))
            || Operation::get_op::<builtin::ops::FuncOp>(op, ctx).is_some()
    }

    fn rewrite(
        &mut self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        op: Ptr<Operation>,
        operands_info: &OperandsInfo,
    ) -> Result<()> {
        if let Some(func_op) = Operation::get_op::<builtin::ops::FuncOp>(op, ctx) {
            // Convert from builtin.func to llvm.func by updating the function type and argument types.
            return lower_func_op_to_llvm(&func_op, ctx, rewriter);
        }
        let op_dyn = Operation::get_op_dyn(op, ctx);
        let to_llvm_op = op_cast::<dyn ToLLVMDialect>(&*op_dyn)
            .expect("Matched Op must implement ToLLVMDialect");
        to_llvm_op.rewrite(ctx, rewriter, operands_info)
    }
}
}

op_impls::<dyn ToLLVMDialect> checks whether the runtime type of the op object implements the ToLLVMDialect interface. Most conversions go through that path: op_cast downcasts dyn Op to dyn ToLLVMDialect and dispatches to the op’s own rewrite method.

There is one explicit special case: builtin.func is matched and rewritten to llvm.func in the driver itself. We do this because builtin.func is not a Kaleidoscope op and does not implement ToLLVMDialect, but we still need to convert function signatures and block-argument types before lowering function bodies.

Entry point

#![allow(unused)]
fn main() {
/// Lower a [`ModuleOp`] containing Kaleidoscope dialect ops in place.
///
/// Uses the [`DialectConversion`] infrastructure: each Kaleidoscope op
/// implements [`ToLLVMDialect`] and knows how to lower itself to LLVM ops.
pub fn lower_module(ctx: &mut Context, module: ModuleOp) -> Result<IRStatus> {
    apply_dialect_conversion(ctx, &mut KalToLLVM, module.get_operation())
}
}

The module is modified in place: builtin.module and builtin.func are kept as-is because they do not implement ToLLVMDialect. Only the Kaleidoscope ops inside the function bodies are converted.

Lowering simple ops

kaleidoscope.constant -> llvm.constant

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalConstantOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let val_attr = self.value_attr(ctx);
        let llvm_const = LlvmConstantOp::new(ctx, Box::new(val_attr));
        let new_result = llvm_const.get_result(ctx);
        rewriter.insert_op(ctx, &llvm_const);
        rewriter.replace_operation_with_values(ctx, self.get_operation(), vec![new_result]);
        Ok(())
    }
}
}

rewriter.insert_op inserts the new op at the current insertion point (before the op being replaced). replace_operation_with_values replaces every use of the original result with the new result and then erases the original op.

kaleidoscope.decl -> llvm.alloca

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalDeclOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let i32_ty = IntegerType::get(ctx, 32, Signedness::Signless);
        let elem_ty = self.variable_type(ctx);
        let size_attr = IntegerAttr::new(i32_ty, APInt::from_i32(1, bw(32)));
        let size_const = LlvmConstantOp::new(ctx, Box::new(size_attr));
        let size_val = size_const.get_result(ctx);
        rewriter.insert_op(ctx, &size_const);
        let alloca = AllocaOp::new(ctx, elem_ty, size_val);
        let alloca_ptr = alloca.get_result(ctx);
        rewriter.insert_op(ctx, &alloca);
        rewriter.replace_operation_with_values(ctx, self.get_operation(), vec![alloca_ptr]);
        Ok(())
    }
}
}

DeclOp allocates a variable slot. The LLVM equivalent is alloca elem_type, i32 1. The alloca instruction requires an i32 count, so a separate llvm.constant 1 : i32 is inserted first.

kaleidoscope.load -> llvm.load

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalLoadOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        operands_info: &OperandsInfo,
    ) -> Result<()> {
        let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);
        // `operands_info` carries the already-converted slot operand.
        let slot = operands_info
            .lookup_most_recent_type(self.slot(ctx))
            .map_or(self.slot(ctx), |_| self.slot(ctx));
        // Operand was already updated in-place by the framework.
        let load = LlvmLoadOp::new(ctx, slot, i64_ty.into());
        let result = load.get_result(ctx);
        rewriter.insert_op(ctx, &load);
        rewriter.replace_operation_with_values(ctx, self.get_operation(), vec![result]);
        Ok(())
    }
}
}

kaleidoscope.store -> llvm.store

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalStoreOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let slot = self.slot(ctx);
        let value = self.stored_value(ctx);
        let store = LlvmStoreOp::new(ctx, value, slot);
        rewriter.insert_op(ctx, &store);
        rewriter.erase_operation(ctx, self.get_operation());
        Ok(())
    }
}
}

StoreOp has no result, so we call erase_operation directly instead of replace_operation_with_values.

kaleidoscope.binop -> llvm.add / sub / mul / icmp + sext

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for BinOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);
        let lhs = self.lhs(ctx);
        let rhs = self.rhs(ctx);
        let kind = self.kind(ctx);

        let result = match kind {
            BinOpKind::Add => {
                let op = AddOp::new_with_overflow_flag(
                    ctx,
                    lhs,
                    rhs,
                    IntegerOverflowFlagsAttr::default(),
                );
                let r = op.get_result(ctx);
                rewriter.insert_op(ctx, &op);
                r
            }
            BinOpKind::Sub => {
                let op = SubOp::new_with_overflow_flag(
                    ctx,
                    lhs,
                    rhs,
                    IntegerOverflowFlagsAttr::default(),
                );
                let r = op.get_result(ctx);
                rewriter.insert_op(ctx, &op);
                r
            }
            BinOpKind::Mul => {
                let op = MulOp::new_with_overflow_flag(
                    ctx,
                    lhs,
                    rhs,
                    IntegerOverflowFlagsAttr::default(),
                );
                let r = op.get_result(ctx);
                rewriter.insert_op(ctx, &op);
                r
            }
            _ => {
                // Comparison: ICmpOp yields i1; sign-extend to i64.
                let pred = binop_kind_to_icmp_pred(kind);
                let icmp = ICmpOp::new(ctx, pred, lhs, rhs);
                let cmp_i1 = icmp.get_result(ctx);
                rewriter.insert_op(ctx, &icmp);
                let sext = SExtOp::new(ctx, cmp_i1, i64_ty.into());
                let r = sext.get_result(ctx);
                rewriter.insert_op(ctx, &sext);
                r
            }
        };
        rewriter.replace_operation_with_values(ctx, self.get_operation(), vec![result]);
        Ok(())
    }
}
}

Arithmetic ops are straightforward one-for-one translations. Comparison ops are two-step: llvm.icmp produces an i1 (1-bit boolean), which is then sign-extended to i64 by llvm.sext so the result type is consistent with the rest of the Kaleidoscope value universe.

kaleidoscope.call -> llvm.call

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalCallOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);
        let callee_attr = self
            .get_attr_callee(ctx)
            .expect("CallOp must have callee attribute")
            .clone();
        let callee_ident = pliron::identifier::Identifier::from(callee_attr);
        let n_args = self.get_operation().deref(ctx).get_num_operands();
        let args: Vec<Value> = (0..n_args)
            .map(|i| self.get_operation().deref(ctx).get_operand(i))
            .collect();
        let arg_types: Vec<Ptr<TypeObj>> = (0..n_args).map(|_| i64_ty.into()).collect();
        let llvm_func_ty = FuncType::get(ctx, i64_ty.into(), arg_types, false);
        let llvm_call = LlvmCallOp::new(
            ctx,
            CallOpCallable::Direct(callee_ident),
            llvm_func_ty,
            args,
        );
        let result = llvm_call.get_result(ctx);
        rewriter.insert_op(ctx, &llvm_call);
        rewriter.replace_operation_with_values(ctx, self.get_operation(), vec![result]);
        Ok(())
    }
}
}

llvm.call requires a FuncType at the call site. Because every Kaleidoscope function takes and returns i64, the callee type is always (i64, …) -> i64 regardless of which function is being called.

kaleidoscope.return -> llvm.return

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalReturnOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let val = self.value(ctx);
        let ret = LlvmReturnOp::new(ctx, Some(val));
        rewriter.insert_op(ctx, &ret);
        rewriter.erase_operation(ctx, self.get_operation());
        Ok(())
    }
}
}

Lowering control flow

Control flow ops are the most interesting because they carry nested regions that must be flattened into LLVM’s flat CFG. pliron’s DialectConversionRewriter provides the necessary primitives:

kaleidoscope.if -> conditional CFG

Before conversion:

^entry:
  ... (IfOp with then-region and else-region) ...
  ... (rest of the function) ...

After conversion:

^entry:          ; everything up to IfOp + icmp + cond_br
^then_block:     ; inlined from then-region, ends with br ^merge
^else_block:     ; inlined from else-region, ends with br ^merge
^merge:          ; rest of the function (from split_block)

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalIfOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);
        let cond = self.condition(ctx);
        let then_region = self.then_region(ctx);
        let else_region = self.else_region(ctx);

        // The entry block of each region is the single block in the region.
        let then_entry = then_region
            .deref(ctx)
            .get_head()
            .expect("IfOp then_region must have a block");
        let else_entry = else_region
            .deref(ctx)
            .get_head()
            .expect("IfOp else_region must have a block");

        let then_term = then_entry
            .deref(ctx)
            .get_terminator(ctx)
            .expect("then block must have a terminator");
        let else_term = else_entry
            .deref(ctx)
            .get_terminator(ctx)
            .expect("else block must have a terminator");

        // Convert the i64 condition to i1 via `icmp ne cond, 0`.
        let zero_attr = IntegerAttr::new(i64_ty, APInt::from_i64(0, bw(64)));
        let zero_const = LlvmConstantOp::new(ctx, Box::new(zero_attr));
        let zero_val = zero_const.get_result(ctx);
        rewriter.insert_op(ctx, &zero_const);
        let cmp = ICmpOp::new(ctx, ICmpPredicateAttr::NE, cond, zero_val);
        let cmp_i1 = cmp.get_result(ctx);
        rewriter.insert_op(ctx, &cmp);

        // Split the current block at the IfOp position to create the merge block.
        let pre_if_block = self
            .get_operation()
            .deref(ctx)
            .get_parent_block()
            .expect("IfOp must be in a block");
        let merge_block = rewriter.split_block(
            ctx,
            pre_if_block,
            OpInsertionPoint::BeforeOperation(self.get_operation()),
            Some("if_merge".try_into().unwrap()),
        );

        // Emit conditional branch in pre_if_block.
        rewriter.set_insertion_point(OpInsertionPoint::AtBlockEnd(pre_if_block));
        let cond_br = CondBrOp::new(ctx, cmp_i1, then_entry, vec![], else_entry, vec![]);
        rewriter.insert_op(ctx, &cond_br);

        // Replace YieldOp in then-branch with branch to merge.
        if Operation::is_op::<KalYieldOp>(then_term, ctx) {
            rewriter.set_insertion_point(OpInsertionPoint::BeforeOperation(then_term));
            let then_br = BrOp::new(ctx, merge_block, vec![]);
            rewriter.insert_op(ctx, &then_br);
            rewriter.erase_operation(ctx, then_term);
        }

        // Replace YieldOp in else-branch with branch to merge.
        if Operation::is_op::<KalYieldOp>(else_term, ctx) {
            rewriter.set_insertion_point(OpInsertionPoint::BeforeOperation(else_term));
            let else_br = BrOp::new(ctx, merge_block, vec![]);
            rewriter.insert_op(ctx, &else_br);
            rewriter.erase_operation(ctx, else_term);
        }

        // Inline both regions after the pre_if_block.
        rewriter.inline_region(
            ctx,
            then_region,
            BlockInsertionPoint::AfterBlock(pre_if_block),
        );
        rewriter.inline_region(
            ctx,
            else_region,
            BlockInsertionPoint::AfterBlock(then_entry),
        );

        // The IfOp itself has no results, so just erase it.
        rewriter.erase_operation(ctx, self.get_operation());
        Ok(())
    }
}
}

The key steps:

1. split_block cuts the current block at the IfOp, creating merge_block with everything that came after.
2. icmp ne cond, 0 converts the i64 condition to i1.
3. cond_br cmp_i1, then_entry, else_entry terminates pre_if_block.
4. The YieldOp terminators in both branches are replaced with br merge_block.
5. inline_region moves the then- and else-blocks into the enclosing function.
6. The IfOp shell (which now has empty regions) is erased.

kaleidoscope.while -> loop CFG

Before conversion:

^entry:
  ... (WhileOp with body-region containing cond updates) ...
  ... (rest of the function) ...

After conversion:

^entry:          ; everything up to WhileOp + br ^header
^while_header:   ; load cond, icmp ne cond, 0, cond_br ^body / ^exit
^body_block:     ; inlined from body-region, ends with br ^header (back-edge)
^exit:           ; rest of the function (from split_block)

#![allow(unused)]
fn main() {
#[op_interface_impl]
impl ToLLVMDialect for KalWhileOp {
    fn rewrite(
        &self,
        ctx: &mut Context,
        rewriter: &mut DialectConversionRewriter,
        _operands_info: &OperandsInfo,
    ) -> Result<()> {
        let i64_ty = IntegerType::get(ctx, 64, Signedness::Signless);
        let cond_ptr = self.cond_ptr(ctx);
        let body_region = self.body_region(ctx);
        let body_entry = body_region
            .deref(ctx)
            .get_head()
            .expect("WhileOp body_region must have a block");

        // Erase the YieldOp at the end of the body.
        let while_term = body_entry
            .deref(ctx)
            .get_terminator(ctx)
            .expect("body block must have a terminator");

        // The block containing the WhileOp is split to create the exit block.
        let pre_while_block = self
            .get_operation()
            .deref(ctx)
            .get_parent_block()
            .expect("WhileOp must be in a block");
        let exit_block = rewriter.split_block(
            ctx,
            pre_while_block,
            OpInsertionPoint::BeforeOperation(self.get_operation()),
            Some("while_exit".try_into().unwrap()),
        );

        // Create the header block.
        let header_block = rewriter.create_block(
            ctx,
            BlockInsertionPoint::AfterBlock(pre_while_block),
            Some("while_header".try_into().unwrap()),
            vec![],
        );

        // Emit an unconditional branch into the header from pre_while_block.
        rewriter.set_insertion_point(OpInsertionPoint::AtBlockEnd(pre_while_block));
        let br_to_header = BrOp::new(ctx, header_block, vec![]);
        rewriter.insert_op(ctx, &br_to_header);

        // Header: load condition, compare to zero, cond_br to body or exit.
        rewriter.set_insertion_point(OpInsertionPoint::AtBlockEnd(header_block));
        let cond_load = LlvmLoadOp::new(ctx, cond_ptr, i64_ty.into());
        let cond_i64 = cond_load.get_result(ctx);
        rewriter.insert_op(ctx, &cond_load);
        let zero_attr = IntegerAttr::new(i64_ty, APInt::from_i64(0, bw(64)));
        let zero_const = LlvmConstantOp::new(ctx, Box::new(zero_attr));
        let zero_val = zero_const.get_result(ctx);
        rewriter.insert_op(ctx, &zero_const);
        let cmp = ICmpOp::new(ctx, ICmpPredicateAttr::NE, cond_i64, zero_val);
        let cmp_i1 = cmp.get_result(ctx);
        rewriter.insert_op(ctx, &cmp);
        let cond_br = CondBrOp::new(ctx, cmp_i1, body_entry, vec![], exit_block, vec![]);
        rewriter.insert_op(ctx, &cond_br);

        // Replace YieldOp at end of body with back-edge to header.
        if Operation::is_op::<KalYieldOp>(while_term, ctx) {
            rewriter.set_insertion_point(OpInsertionPoint::BeforeOperation(while_term));
            let back_edge = BrOp::new(ctx, header_block, vec![]);
            rewriter.insert_op(ctx, &back_edge);
            rewriter.erase_operation(ctx, while_term);
        }

        // Inline the body region after the header block.
        rewriter.inline_region(
            ctx,
            body_region,
            BlockInsertionPoint::AfterBlock(header_block),
        );

        // Erase the WhileOp.
        rewriter.erase_operation(ctx, self.get_operation());
        Ok(())
    }
}
}

WhileOp uses the memory-backed condition pattern introduced in Chapter 3: the loop condition variable is a DeclOp slot in the outer block. The header loads that slot on each iteration and branches accordingly. The body region updates the slot at the end of every iteration, then its YieldOp is replaced with a back-edge branch to the header.

Tests

The test helper parses a Kaleidoscope source string, lowers it to the Kaleidoscope dialect, applies the LLVM lowering in place, then prints and returns the resulting IR:

#![allow(unused)]
fn main() {
    fn lower_to_llvm(src: &str) -> String {
        let funcs = parse_program(src).expect("parse error");
        let ctx = &mut Context::new();
        let module = ModuleOp::new(ctx, "test".try_into().expect("valid module name"));
        for func in &funcs {
            let func_op = lower_function(ctx, func).expect("kaleidoscope lowering failed");
            module.append_operation(ctx, func_op.get_operation(), 0);
        }
        let module_op_ptr = module.get_operation();
        lower_module(ctx, module).expect("LLVM lowering failed");
        verify_operation(module_op_ptr, ctx)
            .expect("module verification failed after LLVM lowering");
        format!("{}", module_op_ptr.disp(ctx))
    }
}

Try it out:

cargo test --example kaleidoscope -- --show-output fibonacci_to_llvm
cargo test --example kaleidoscope -- --show-output factorial_to_llvm
cargo test --example kaleidoscope -- --show-output if_else_to_llvm

Next step

Chapter 5 feeds the LLVM-dialect module into pliron-llvm’s JIT backend to compile and execute the Kaleidoscope program.

Chapter 5: JIT with LLVM

Chapter 4 lowered Kaleidoscope IR into the LLVM dialect. In this chapter we take the final step: convert that module to LLVM IR, JIT compile it, and invoke the generated machine code directly from Rust.

The implementation for this chapter lives in examples/kaleidoscope/jit.rs.

Design

The flow is intentionally small and linear:

1. Parse Kaleidoscope source into AST (parse_program).
2. Lower each AST function into Kaleidoscope dialect (lower_function).
3. Lower the module to LLVM dialect (lower_module).
4. Convert LLVM dialect to LLVM IR (to_llvm_ir::convert_module).
5. Build an LLVM ORC JIT instance, add the module, look up a symbol, execute.

The one extra safeguard in this implementation is a runtime signature check. Before JIT invocation, we verify that the target function really has signature fn(i64) -> i64. This limitation is intentionally set for simplicity.

Step 1-4: Lower source all the way to LLVM IR

lower_to_llvm_ir is a helper that runs the complete frontend and lowering pipeline and returns an LLVMModule:

#![allow(unused)]
fn main() {
fn lower_to_llvm_ir(src: &str, llvm_ctx: &LLVMContext) -> Result<LLVMModule> {
    let funcs =
        parse_program(src).map_err(|e| input_error_noloc!("Failed to parse program: {}", e))?;
    let ctx = &mut Context::new();
    let module = ModuleOp::new(ctx, "test".try_into().expect("valid module name"));
    for func in &funcs {
        let func_op = lower_function(ctx, func)?;
        module.append_operation(ctx, func_op.get_operation(), 0);
    }
    lower_module(ctx, module)?;
    verify_operation(module.get_operation(), ctx)?;
    // Convert from LLVM dialect to LLVM IR
    let llvm_module = to_llvm_ir::convert_module(ctx, llvm_ctx, module)?;
    llvm_module
        .verify()
        .map_err(|e| input_error_noloc!("Generated LLVM module is invalid: {}", e))?;
    Ok(llvm_module)
}
}

Notes:

• We build a fresh Context and ModuleOp per call.
• Every parsed function is lowered and appended to the module.
• lower_module mutates the module in place from Kaleidoscope dialect to LLVM dialect.
• to_llvm_ir::convert_module produces real LLVM IR (LLVMModule) consumable by JIT.

Step 5: JIT compile and execute

The public API for execution is exec_fn:

#![allow(unused)]
fn main() {
pub fn exec_fn(src: &str, name: &str, arg: i64) -> Result<i64> {
    initialize_native()
        .map_err(|e| input_error_noloc!("Failed to initialize native target: {}", e))?;
    let llvm_ctx = LLVMContext::default();
    let llvm_module = lower_to_llvm_ir(src, &llvm_ctx)?;

    let Some(f) = llvm_get_named_function(&llvm_module, name) else {
        return Err(input_error_noloc!(
            "Function '{}' not found in generated LLVM module",
            name
        ));
    };
    let f_ty = llvm_global_get_value_type(f);
    let param_types = llvm_get_param_types(f_ty);
    let ret_type = llvm_get_return_type(f_ty);
    let llvm_int64_ty = llvm_int_type_in_context(&llvm_ctx, 64);
    if param_types.len() != 1 || param_types[0] != llvm_int64_ty || ret_type != llvm_int64_ty {
        return Err(input_error_noloc!(
            "Expected function '{}' to have exactly one parameter of type i64 and return type i64, but found different signature",
            name
        ));
    }

    // println!("Generated LLVM IR:\n{}", llvm_module.to_string());

    // JIT compile and execute the main function
    let lljit = pliron_llvm::llvm_sys::lljit::LLVMLLJIT::new_with_default_builder()
        .map_err(|e| input_error_noloc!("Failed to create JIT execution engine: {}", e))?;
    lljit
        .add_module(llvm_module)
        .map_err(|e| input_error_noloc!("Failed to add module to JIT: {}", e))?;
    let main_fn = lljit
        .lookup_symbol(name)
        .map_err(|e| input_error_noloc!("Failed to find main function in JIT: {}", e))?;

    let main_fn: extern "C" fn(i64) -> i64 = unsafe { std::mem::transmute(main_fn) };
    Ok(main_fn(arg))
}
}

Key parts of exec_fn:

• initialize_native() sets up the host target backend once per process.
• llvm_get_named_function checks that the requested symbol exists in the generated module.
• llvm_get_param_types and llvm_get_return_type are used to validate the function ABI as exactly one i64 argument and an i64 return value.
• LLVMLLJIT::new_with_default_builder() creates an ORC JIT instance.
• add_module loads the generated LLVM module into JIT.
• lookup_symbol(name) resolves the function entry address.
• std::mem::transmute casts the raw symbol address to extern "C" fn(i64) -> i64, then calls it.

If the function is missing, or has a different signature, exec_fn returns a structured pliron::result::Error instead of panicking.

Tests

The file includes three focused tests that exercise the end-to-end JIT path.

Fibonacci from source file:

#![allow(unused)]
fn main() {
    #[test]
    fn fibonacci_jit() {
        let src = std::fs::read_to_string("examples/kaleidoscope/fibonacci.kal")
            .expect("failed to read fibonacci.kal");
        let result = exec_fn(&src, "main", 5).expect("failed to execute main function");
        assert_eq!(result, 5);
    }
}

Factorial from source file:

#![allow(unused)]
fn main() {
    #[test]
    fn factorial_jit() {
        let src = std::fs::read_to_string("examples/kaleidoscope/factorial.kal")
            .expect("failed to read factorial.kal");
        let result = exec_fn(&src, "main", 5).expect("failed to execute main function");
        assert_eq!(result, 120);
    }
}

Inline if/else program:

#![allow(unused)]
fn main() {
    #[test]
    fn if_else_jit() {
        let src = "
            def abs(x) {
                var result = 0;
                if x < 0 {
                    result = 0 - x;
                } else {
                    result = x;
                }
                return result;
            }
        ";
        let result = exec_fn(src, "abs", 42).expect("failed to execute main function");
        assert_eq!(result, 42);
        let result = exec_fn(src, "abs", -42).expect("failed to execute main function");
        assert_eq!(result, 42);
        let result = exec_fn(src, "abs", 0).expect("failed to execute main function");
        assert_eq!(result, 0);
    }
}

These tests verify that:

• file-backed programs run correctly through JIT,
• recursive calls work (fib, factorial),
• structured control flow (if/else) lowers and executes correctly.

Try it out

Run individual JIT tests:

cargo test --example kaleidoscope -- --show-output fibonacci_jit
cargo test --example kaleidoscope -- --show-output factorial_jit
cargo test --example kaleidoscope -- --show-output if_else_jit

You can also run the example binary in this workspace and execute a chosen function from a .kal source file.

Running via the example CLI

The example binary in examples/kaleidoscope/main.rs is a thin wrapper around jit::exec_fn: it reads source from --input, selects a function with --fn, passes an integer argument via --arg, and prints the result.

Run Fibonacci’s main(5):

cargo run --example kaleidoscope -- --input examples/kaleidoscope/fibonacci.kal --fn main --arg 5

Run Factorial’s main(5):

cargo run --example kaleidoscope -- --input examples/kaleidoscope/factorial.kal --fn main --arg 5

If the function name is missing from the module, or does not match the expected fn(i64) -> i64 signature, the CLI reports the error returned by exec_fn.

Recap

At this point, the tutorial pipeline is complete:

1. Parse source text into AST.
2. Lower AST to a custom high-level dialect.
3. Lower to LLVM dialect.
4. Convert to LLVM IR.
5. JIT and execute native code.

This is the minimal but complete compiler path from source language to running machine code using pliron + pliron-llvm.

Examples Index

This index maps tutorial chapters to runnable examples.

Chapter mapping

Running chapter tests

cargo test --example kaleidoscope -- --list
cargo test --example kaleidoscope -- --show-output

Run a single test by name:

cargo test --example kaleidoscope -- fibonacci_to_llvm --show-output

Run the end-to-end CLI example:

cargo run --example kaleidoscope -- --input examples/kaleidoscope/fibonacci.kal --fn main --arg 5

Testing strategy

As examples become implementation-heavy, mirror key behaviors in integration tests under tests/ so chapter claims remain verifiable in CI.

Suggested learning paths

• Parser-focused: Start at Chapter 1.
• IR design-focused: Start at Chapter 2, then Chapter 3 and Chapter 4.
• End-to-end pipeline: All chapters, in order.