Getting started

Welcome to the documentation for the Miden compiler toolchain.

The documentation found here should provide a good starting point for the current capabilities of the toolchain, however if you find something that is not covered, but is not listed as unimplemented or a known limitation, please let us know by reporting an issue on the compiler issue tracker.

What is provided?

The compiler toolchain consists of the following primary components:

• An intermediate representation (IR), which can be lowered to by compiler backends wishing to support Miden as a target. The Miden IR is an SSA IR, much like Cranelift or LLVM, providing a much simpler path from any given source language (e.g. Rust), to Miden Assembly. It is used internally by the rest of the Miden compiler suite.
• A WebAssembly (Wasm) frontend for Miden IR. It can handle lowering both core Wasm modules, as well as basic components using the experimental WebAssembly Component Model. Currently, the Wasm frontend is known to work with Wasm modules produced by rustc, which is largely just what LLVM produces, but with the shadow stack placed at the start of linear memory rather than after read-only data. In the future we intend to support more variety in the structure of Wasm modules we accept, but for the time being we're primarily focused on using this as the path for lowering Rust to Miden.
• The compiler driver, in the form of the midenc executable, and a Rust crate, midenc-compiler to allow integrating the compiler into other tools. This plays the same role as rustc does in the Rust ecosystem.
• A Cargo extension, cargo-miden, that provides a convenient developer experience for creating and compiling Rust projects targeting Miden. It contains a project template for a basic Rust crate, and handles orchestrating rustc and midenc to compile the crate to WebAssembly, and then to Miden Assembly.
• A terminal-based interactive debugger, available via midenc debug, which provides a UI very similar to lldb or gdb when using the TUI mode. You can use this to run a program, or step through it cycle-by-cycle. You can set various types of breakpoints; see the source code, call stack, and contents of the operand stack at the current program point; as well as interatively read memory and format it in various ways for display.
• A Miden SDK for Rust, which provides types and bindings to functionality exported from the Miden standard library, as well as the Miden transaction kernel API. You can use this to access native Miden features which are not provided by Rust out-of-the-box. The project template generated by cargo miden new automatically adds this as a dependency.

What can I do with it?

That all sounds great, but what can you do with the compiler today? The answer depends a bit on what aspect of the compiler you are interested in:

Rust

The most practically useful, and interesting capability provided by the compiler currently, is the ability to compile arbitrary Rust programs to Miden Assembly. See the guides for more information on setting up and compiling a Rust crate for execution via Miden.

WebAssembly

More generally, the compiler frontend is capable of compiling WebAssembly modules, with some constraints, to Miden Assembly. As a result, it is possible to compile a wider variety of languages to Miden Assembly than just Rust, so long as the language can compile to WebAssembly. However, we do not currently provide any of the language-level support for languages other than Rust, and have limited ability to provide engineering support for languages other than Rust at this time.

Our Wasm frontend does not support all of the extensions to the WebAssembly MVP, most notably the reference types and GC proposals.

Miden IR

If you are interested in compiling to Miden from your own compiler, you can target Miden IR, and invoke the driver from your compiler to emit Miden artifacts. At this point in time, we don't have the resources to provide much in the way of engineering support for this use case, but if you find issues in your efforts to use the IR in your compiler, we would certainly like to know about them!

We do not currently perform any optimizations on the IR, since we are primarily working with the output of compiler backends which have already applied optimizations, at this time. This may change in the future, but for now it is expected that you implement your own optimization passes as needed.

Known bugs and limitations

For the latest information on known bugs and limitations, see the issue tracker.

Where to start?

Provided here are a set of guides which are focused on documenting a couple of supported workflows we expect will meet the needs of most users, within the constraints of the current feature set of the compiler. If you find that there is something you wish to do that is not covered, and is not one of our known limitations, please open an issue, and we will try to address the missing docs as soon as possible.

Installation

To get started, there are a few ways you might use the Miden compiler. Select the one that applies to you, and the corresponding guide will walk you through getting up and running:

1. Using the Cargo extension
2. Using the midenc executable

Getting started with midenc

The midenc executable is the command-line interface for the compiler driver, as well as other helpful tools, such as the interactive debugger.

While it is a lower-level tool compared to cargo-miden, just like the difference between rustc and cargo, it provides a lot of functionality for emitting diagnostic information, controlling the output of the compiler, and configuring the compilation pipeline. Most users will want to use cargo-miden, but understanding midenc is helpful for those times where you need to get your hands dirty.

Installation

rustup toolchain install nightly-2025-03-20

To install the midenc, clone the compiler repo first:

git clone https://github.com/0xMiden/compiler

Then, run the following in your shell in the cloned repo folder:

cargo install --path midenc --locked

Usage

Once installed, you should be able to invoke the compiler, you should see output similar to this:

midenc help compile
Usage: midenc compile [OPTIONS] [-- <INPUTS>...]

Arguments:
  [INPUTS]...
          Path(s) to the source file(s) to compile.

          You may also use `-` as a file name to read a file from stdin.

Options:
      --output-dir <DIR>
          Write all compiler artifacts to DIR

  -W <LEVEL>
          Modify how warnings are treated by the compiler

          [default: auto]

          Possible values:
          - none:  Disable all warnings
          - auto:  Enable all warnings
          - error: Promotes warnings to errors

  -v, --verbose
          When set, produces more verbose output during compilation

  -h, --help
          Print help (see a summary with '-h')

The actual help output covers quite a bit more than shown here, this is just for illustrative purposes.

The midenc executable supports two primary functions at this time:

• midenc compile to compile one of our supported input formats to Miden Assembly
• midenc debug to run a Miden program attached to an interactive debugger
• midenc run to run a Miden program non-interactively, equivalent to miden run

Compilation

See the help output for midenc compile for detailed information on its options and their behavior. However, the following is an example of how one might use midenc compile in practice:

midenc compile --target rollup \
    --entrypoint 'foo::main' \
    -lextra \
    -L ./masm \
    --emit=hir=-,masp \
    -o out.masp \
    target/wasm32-wasip1/release/foo.wasm

In this scenario, we are in the root of a Rust crate, named foo, which we have compiled for the wasm32-wasip1 target, which placed the resulting WebAssembly module in the target/wasm32-wasip1/release directory. This crate exports a function named main, which we want to use as the entrypoint of the program.

Additionally, our Rust code links against some hand-written Miden Assembly code, namespaced under extra, which can be found in ./masm/extra. We are telling midenc to link the extra library, and to add the ./masm directory to the library search path.

Lastly, we're configuring the output:

• We're using --emit to request midenc to dump Miden IR (hir) to stdout (specified via the - shorthand), in addition to the Miden package artifact (masp).
• We're telling midenc to write the compiled output to out.masp in the current directory, rather than the default path that would have been used (target/miden/foo.masp).

Debugging

See Debugging Programs for details on using midenc debug to debug Miden programs.

Next steps

We have put together two useful guides to walk through more detail on compiling Rust to WebAssembly:

1. To learn how to compile Rust to WebAssembly so that you can invoke midenc compile on the resulting Wasm module, see this guide.
2. If you already have a WebAssembly module, or know how to produce one, and want to learn how to compile it to Miden Assembly, see this guide.

You may also be interested in our basic account project template, as a starting point for your own Rust project.

Getting started with Cargo

As part of the Miden compiler toolchain, we provide a Cargo extension, cargo-miden, which provides a template to spin up a new Miden project in Rust, and takes care of orchestrating rustc and midenc to compile the Rust crate to a Miden package.

Installation

rustup toolchain install nightly-2025-03-20

To install the extension, clone the compiler repo first:

git clone https://github.com/0xMiden/compiler

Then, run the following in your shell in the cloned repo folder:

cargo install --path tools/cargo-miden --locked

This will take a minute to compile, but once complete, you can run cargo help miden or just cargo miden to see the set of available commands and options.

To get help for a specific command, use cargo miden help <command> or cargo miden <command> --help.

Creating a new project

Your first step will be to create a new Rust project set up for compiling to Miden:

cargo miden new foo

In this above example, this will create a new directory foo, containing a Cargo project for a crate named foo, generated from our Miden project template.

The template we use sets things up so that you can pretty much just build and run. Since the toolchain depends on Rust's native WebAssembly target, it is set up just like a minimal WebAssembly crate, with some additional tweaks for Miden specifically.

Out of the box, you will get a Rust crate that depends on the Miden SDK, and sets the global allocator to a simple bump allocator we provide as part of the SDK, and is well suited for most Miden use cases, avoiding the overhead of more complex allocators.

As there is no panic infrastructure, panic = "abort" is set, and the panic handler is configured to use the native WebAssembly unreachable intrinsic, so the compiler will strip out all of the usual panic formatting code.

Compiling to Miden package

Now that you've created your project, compiling it to Miden package is as easy as running the following command from the root of the project directory:

cargo miden build --release

This will emit the compiled artifacts to target/miden/release/foo.masp.

Running a compiled Miden VM program

The compiled Miden VM program can be run from the Miden package with the following:

midenc run target/miden/release/foo.masp --inputs some_inputs.toml

See midenc run --help for the inputs file format.

Examples

Check out the examples for some cargo-miden project examples.

Compiling Rust To WebAssembly

This chapter will walk you through compiling a Rust crate to a WebAssembly (Wasm) module in binary (i.e. .wasm) form. The Miden compiler has a frontend which can take such modules and compile them on to Miden Assembly, which will be covered in the next chapter.

Setup

First, let's set up a simple Rust project that contains an implementation of the Fibonacci function (I know, it's overdone, but we're trying to keep things as simple as possible to make it easier to show the results at each step, so bear with me):

Start by creating a new library crate:

cargo new --lib wasm-fib && cd wasm-fib

To compile to WebAssembly, you must have the appropriate Rust toolchain installed, so let's add a toolchain file to our project root so that rustup and cargo will know what we need, and use them by default:

cat <<EOF > rust-toolchain.toml
[toolchain]
channel = "stable"
targets = ["wasm32-wasip1"]
EOF

Next, edit the Cargo.toml file as follows:

[package]
name = "wasm-fib"
version = "0.1.0"
edition = "2021"

[lib]
# Build this crate as a self-contained, C-style dynamic library
# This is required to emit the proper Wasm module type
crate-type = ["cdylib"]

[dependencies]
# Use a tiny allocator in place of the default one, if we want
# to make use of types in the `alloc` crate, e.g. String. We
# don't need that now, but it's good information to have in hand.
#miden-sdk-alloc = "0.0.5"

# When we build for Wasm, we'll use the release profile
[profile.release]
# Explicitly disable panic infrastructure on Wasm, as
# there is no proper support for them anyway, and it
# ensures that panics do not pull in a bunch of standard
# library code unintentionally
panic = "abort"
# Enable debug information so that we get useful debugging output
debug = true
# Optimize the output for size
opt-level = "z"

Most of these things are done to keep the generated code size as small as possible. Miden is a target where the conventional wisdom about performance should be treated very carefully: we're almost always going to benefit from less code, even if conventionally that code would be less efficient, simply due to the difference in proving time accumulated due to extra instructions. That said, there are no hard and fast rules, but these defaults are good ones to start with.

Next, edit src/lib.rs as shown below:

#![allow(unused)]
fn main() {
// Do not link against libstd (i.e. anything defined in `std::`)
#![no_std]

// However, we could still use some standard library types while
// remaining no-std compatible, if we uncommented the following lines:
//
// extern crate alloc;
// use alloc::{string::String, vec::Vec};

// If we wanted to use the types mentioned above, it would also be
// a good idea to use the allocator we pulled in as a dependency
// in Cargo.toml, like so:
//#[global_allocator]
//static ALLOC: miden_sdk_alloc::BumpAlloc = miden_sdk_alloc::BumpAlloc::new();

// Required for no-std crates
#[panic_handler]
fn panic(_info: &core::panic::PanicInfo) -> ! {
    // Compiles to a trap instruction in WebAssembly
    core::arch::wasm32::unreachable()
}

// Marking the function no_mangle ensures that it is exported
// from the compiled binary as `fib`, otherwise it would have
// a mangled name that has no stable form.
//
// You can specify a different name from the library than the
// name in the source code using the `#[export_name = "foo"]`
// attribute, which will make the function callable as `foo`
// externally (in this example)
#[no_mangle]
pub fn fib(n: u32) -> u32 {
    let mut a = 0;
    let mut b = 1;
    for _ in 0..n {
        let c = a + b;
        a = b;
        b = c;
    }
    a
}
}

This exports our fib function from the library, making it callable from within a larger Miden program.

All that remains is to compile to WebAssembly:

cargo build --release --target=wasm32-wasip1

This places a wasm_fib.wasm file under the target/wasm32-wasip1/release/ directory, which we can then examine with wasm2wat to set the code we generated:

wasm2wat target/wasm32-wasip1/release/wasm_fib.wasm

Which dumps the following output (may differ slightly on your machine, depending on the specific compiler version):

(module $wasm_fib.wasm
  (type (;0;) (func (param i32) (result i32)))
  (func $fib (type 0) (param i32) (result i32)
    (local i32 i32 i32)
    i32.const 0
    local.set 1
    i32.const 1
    local.set 2
    loop (result i32)  ;; label = @1
      local.get 2
      local.set 3
      block  ;; label = @2
        local.get 0
        br_if 0 (;@2;)
        local.get 1
        return
      end
      local.get 0
      i32.const -1
      i32.add
      local.set 0
      local.get 1
      local.get 3
      i32.add
      local.set 2
      local.get 3
      local.set 1
      br 0 (;@1;)
    end)
  (memory (;0;) 16)
  (global $__stack_pointer (mut i32) (i32.const 1048576))
  (export "memory" (memory 0))
  (export "fib" (func $fib)))

Success!

Next steps

In Compiling WebAssembly to Miden Assembly, we walk through how to take the WebAssembly module we just compiled, and lower it to Miden Assembly using midenc!

Compiling WebAssembly to Miden Assembly

This guide will walk you through compiling a WebAssembly (Wasm) module, in binary form (i.e. a .wasm file), to Miden Assembly (Masm), both in its binary package form (a .masp file), and in textual Miden Assembly syntax form (i.e. a .masm file).

Setup

We will be making use of the example crate we created in Compiling Rust to WebAssembly, which produces a small Wasm module that is easy to examine in Wasm text format, and demonstrates a good set of default choices for a project compiling to Miden Assembly from Rust.

In this chapter, we will be compiling Wasm to Masm using the midenc executable, so ensure that you have followed the instructions in the Getting Started with midenc guide and then return here.

Compiling to Miden Assembly

In the last chapter, we compiled a Rust crate to WebAssembly that contains an implementation of the Fibonacci function called fib, that was emitted to target/wasm32-wasip1/release/wasm_fib.wasm. All that remains is to tell midenc to compile this module to Miden Assembly.

Currently, by default, the compiler will emit an experimental package format that the Miden VM does not yet support. We will instead use midenc run to execute the package using the VM for us, but once the package format is stabilized, this same approach will work with miden run as well.

We also want to examine the Miden Assembly generated by the compiler, so we're going to ask the compiler to emit both types of artifacts:

midenc compile --emit masm=wasm_fib.masm,masp  target/wasm32-wasip1/release/wasm_fib.wasm

This will compile our Wasm module to a Miden package with the .masp extension, and also emit the textual Masm to wasm_fib.masm so we can review it. The wasm_fib.masp file will be emitted in the default output directory, which is the current working directory by default.

If we dump the contents of wasm_fib.masm, we'll see the following generated code:

export.fib
  push.0
  push.1
  movup.2
  swap.1
  dup.1
  neq.0
  push.1
  while.true
    if.true
      push.4294967295
      movup.2
      swap.1
      u32wrapping_add
      dup.1
      swap.1
      swap.3
      swap.1
      u32wrapping_add
      movup.2
      swap.1
      dup.1
      neq.0
      push.1
    else
      drop
      drop
      push.0
    end
  end
end

If you compare this to the WebAssembly text format, you can see that this is a fairly faithful translation, but there may be areas where we generate sub-optimal Miden Assembly.

Testing with the Miden VM

We can test our compiled program like so:

$ midenc run --num-outputs 1 wasm_fib.masp -- 10
============================================================
Run program: wasm_fib.masp
============================================================
Executed program with hash 0xe5ba88695040ec2477821b26190e9addbb1c9571ae30c564f5bbfd6cabf6c535 in 19 milliseconds
Output: [55]
VM cycles: 295 extended to 512 steps (42% padding).
├── Stack rows: 295
├── Range checker rows: 67
└── Chiplets rows: 250
├── Hash chiplet rows: 248
├── Bitwise chiplet rows: 0
├── Memory chiplet rows: 1
└── Kernel ROM rows: 0

Success! We got the expected result of 55.

Next steps

This guide is not comprehensive, as we have not yet examined in detail the differences between compiling libraries vs programs, linking together multiple libraries, packages, or discussed some of the more esoteric compiler options. We will be updating this documentation with those details and more in the coming weeks and months, so bear with us while we flesh out our guides!

Developing Miden programs in Rust

This chapter will walk through how to develop Miden programs in Rust using the standard library provided by the miden-stdlib-sys crate (see the README.

Getting started

Import the standard library from the miden-stdlib-sys crate:

#![allow(unused)]
fn main() {
use miden_stdlib_sys::*;
}

Using Felt (field element) type

The Felt type is a field element type that is used to represent the field element values of the Miden VM.

To initialize a Felt value from an integer constant checking the range at compile time, use the felt! macro:

#![allow(unused)]
fn main() {
let a = felt!(42);
}

Otherwise, use the Felt::new constructor:

#![allow(unused)]
fn main() {
let a = Felt::new(some_integer_var).unwrap();
}

The constructor returns an error if the value is not a valid field element, e.g. if it is not in the range 0..=M where M is the modulus of the field (2^64 - 2^32 + 1).

The Felt type implements the standard arithmetic operations, e.g. addition, subtraction, multiplication, division, etc. which are accessible through the standard Rust operators +, -, *, /, etc. All arithmetic operations are wrapping, i.e. performed modulo M.

TODO: Add examples of using operations on Felt type and available functions (assert*, etc.).

Developing Miden rollup accounts and note scripts in Rust

This chapter walks you through how to develop Miden rollup accounts and note scripts in Rust using the Miden SDK crate.

Debugging programs

A very useful tool in the Miden compiler suite, is its TUI-based interactive debugger, accessible via the midenc debug command.

Getting started

The debugger is launched by executing midenc debug, and giving it a path to a program compiled by midenc compile. See Program Inputs for information on how to provide inputs to the program you wish to debug. Run midenc help debug for more detailed usage documentation.

The debugger may also be used as a library, but that is left as an exercise for the reader for now.

Example

# Compile a program to MAST from a rustc-generated Wasm module
midenc compile foo.wasm -o foo.masl

# Load that program into the debugger and start executing it
midenc debug foo.masl

Program inputs

To pass arguments to the program on the operand stack, or via the advice provider, you have two options, depending on the needs of the program:

1. Pass arguments to midenc debug in the same order you wish them to appear on the stack. That is, the first argument you specify will be on top of the stack, and so on.
2. Specify a configuration file from which to load inputs for the program, via the --inputs option.

Via command line

To specify the contents of the operand stack, you can do so following the raw arguments separator --. Each operand must be a valid field element value, in either decimal or hexadecimal format. For example:

midenc debug foo.masl -- 1 2 0xdeadbeef

If you pass arguments via the command line in conjunction with --inputs, then the command line arguments will be used instead of the contents of the inputs.stack option (if set). This lets you specify a baseline set of inputs, and then try out different arguments using the command line.

Via inputs config

While simply passing operands to the midenc debug command is useful, it only allows you to specify inputs to be passed via operand stack. To provide inputs via the advice provider, you will need to use the --inputs option. The configuration file expected by --inputs also lets you tweak the execution options for the VM, such as the maximum and expected cycle counts.

An example configuration file looks like so:

# This section is used for execution options
[options]
max_cycles = 5000
expected_cycles = 4000

# This section is the root table for all inputs
[inputs]
# Specify elements to place on the operand stack, leftmost element will be on top of the stack
stack = [1, 2, 0xdeadbeef]

# This section contains input options for the advice provider
[inputs.advice]
# Specify elements to place on the advice stack, leftmost element will be on top
stack = [1, 2, 3, 4]

# The `inputs.advice.map` section is a list of advice map entries that should be
# placed in the advice map before the program is executed. Entries with duplicate
# keys are handled on a last-write-wins basis.
[[inputs.advice.map]]
# The key for this entry in the advice map
digest = '0x3cff5b58a573dc9d25fd3c57130cc57e5b1b381dc58b5ae3594b390c59835e63'
# The values to be stored under this key
values = [1, 2, 3, 4]

[[inputs.advice.map]]
digest = '0x20234ee941e53a15886e733cc8e041198c6e90d2a16ea18ce1030e8c3596dd38''
values = [5, 6, 7, 8]

Usage

Once started, you will be dropped into the main debugger UI, stopped at the first cycle of the program. The UI is organized into pages and panes, with the main/home page being the one you get dropped into when the debugger starts. The home page contains the following panes:

• Source Code - displays source code for the current instruction, if available, with the relevant line and span highlighted, with syntax highlighting (when available)
• Disassembly - displays the 5 most recently executed VM instructions, and the current cycle count
• Stack Trace - displays a stack trace for the current instruction, if the program was compiled with tracing enabled. If frames are unavailable, this pane may be empty.
• Operand Stack - displays the contents of the operand stack and its current depth
• Breakpoints - displays the set of current breakpoints, along with how many were hit at the current instruction, when relevant

Keyboard shortcuts

On the home page, the following keyboard shortcuts are available:

When various panes have focus, additional keyboard shortcuts are available, in any pane with a list of items, or multiple lines (e.g. source code), j and k (or the up and down arrows) will select the next item up and down, respectively. As more features are added, I will document their keyboard shortcuts below.

Commands

From the home page, typing : will bring up the command prompt in the footer pane.

You will know the prompt is active because the keyboard shortcuts normally shown there will no longer appear, and instead you will see the prompt, starting with :. It supports any of the following commands:

Breakpoints

One of the most common things you will want to do with the debugger is set and manage breakpoints. Using the command prompt, you can create breakpoints by typing b (or break or breakpoint), followed by a space, and then the desired breakpoint expression to do any of the following:

• Break at an instruction which corresponds to a source file (or file and line) whose name/path matches a pattern
• Break at the first instruction which causes a call frame to be pushed for a procedure whose name matches a pattern
• Break any time a specific opcode is executed
• Break at the next instruction
• Break after N cycles
• Break at CYCLE

The syntax for each of these can be found below, in the same order (shown using b as the command):

When a breakpoint is hit, it will be highlighted, and the breakpoint window will display the number of hit breakpoints in the lower right.

After a breakpoint is hit, it expires if it is one of the following types:

• Break after N
• Break at CYCLE
• Break next

When a breakpoint expires, it is removed from the breakpoint list on the next cycle.

Reading memory

Another useful diagnostic task is examining the contents of linear memory, to verify that expected data has been written. You can do this via the command prompt, using r (or read), followed by a space, and then the desired memory address and options:

The format for read expressions is :r ADDR [OPTIONS..], where ADDR is a memory address in decimal or hexadecimal format (the latter requires the 0x prefix). The read command supports the following for OPTIONS:

Any invalid combination of options, or invalid syntax, will display an error in the status bar.

Types

Roadmap

The following are some features planned for the near future:

• Watchpoints, i.e. cause execution to break when a memory store touches a specific address
• Conditional breakpoints, i.e. only trigger a breakpoint when an expression attached to it evaluates to true
• More DYIM-style breakpoints, i.e. when breaking on first hitting a match for a file or procedure, we probably shouldn't continue to break for every instruction to which that breakpoint technically applies. Instead, it would make sense to break and then temporarily disable that breakpoint until something changes that would make breaking again useful. This will rely on the ability to disable breakpoints, not delete them, which we don't yet support.
• More robust type support in the read command
• Display procedure locals and their contents in a dedicated pane

Compiler architecture

This document provides an index of the various design documents for the compiler itself, and its toolchain components. If you see something missing or lacking, please let us know what improvements to these documents you'd like to see!

• Frontends
• Intermediate Representation (HIR)
• Data Layout
• Analyses
• Rewrites
• Code Generation
• Packaging

Supported front ends

WebAssembly (Wasm)

TODO

For the list of the unsupported Wasm core types, instructions and features, see the README.

High-Level Intermediate Representation (HIR)

This document describes the concepts, usage, and overall structure of the intermediate representation used by midenc and its various components.

• Core Concepts
  • Dialects
  • Operations
  • Regions
  • Blocks
  • Values
    • Operands
    • Immediates
  • Attributes
  • Traits
  • Interfaces
  • Symbols
  • Symbol Tables
  • Successors and Predecessors
• High-Level Structure
• Pass Infrastructure
  • Analysis
  • Pattern Rewrites
  • Canonicalization
    • Folding
• Implementation Details
  • Session
  • Context
  • Entity References
    • Entity Storage
      • StoreableEntity
      • ValueRange
    • Entity Lists
  • Traversal
  • Program Points
  • Defining Dialects
    • Dialect Registration
    • Dialect Hooks
    • Defining Operations
  • Builders
    • Validation
  • Effects

Core Concepts

HIR is directly based on the design and implementation of MLIR, in many cases, the documentation there can be a useful guide for HIR as well, in terms of concepts, etc. The actual implementation of HIR looks quite a bit different due to it being in Rust, rather than C++.

MLIR, and by extension, HIR, are compiler intermediate representations based on a concept called the Regionalized Value State Dependence Graph (commonly abbreviated as RVSDG), first introduced in this paper. The RVSDG representation, unlike other representations (e.g. LLVM IR), is oriented around data flow, rather than control flow, though it can represent both. Nodes in the data flow graph, which we call operations, represent computations; while edges, which we call values, represent dependencies between computations. Regions represent the hierarchical structure of a program, both at a high level (e.g. the relationship between modules and functions), as well as at a low level (e.g. structured control flow, such as an if-else operation, or while loop. This representation allows for representing programs at a much higher level of abstraction, makes many data flow analyses and optimizations simpler and more effective, and naturally exposes parallelism inherent in the programs it represents. It is well worth reading the RVSDG paper if you are interested in learning more!

More concretely, the above entities relate to each other as follows:

• Operations can contain regions, operands which represent input values, and results which represent output values.
• Regions can contain basic blocks
• Blocks can contain operations, and may introduce values in the form of block arguments. See the Basic Blocks section for more details.
• Values from the edges of the data flow graph, i.e. operation A depends on B, if B produces a result that A consumes as an operand.

As noted above, operations can represent both high-level and low-level concepts, e.g. both a function definition, and a function call. The semantics of an operation are encoded in the form of a wide variety of operation traits, e.g. whether it is commutative, or idempotent; as well as a core set of operation interfaces, e.g. there is an interface for side effects, unstructured/structured control flow operations, and more. This allows working with operations generically, i.e. you can write a control flow analysis without needing to handle every single control flow operation explicitly - instead, you can perform the analysis against a single interface (or set of interfaces that relate to each other), and any operation that implements the interface is automatically supported by the analysis.

Operations are organized into dialects. A dialect can be used to represent some set of operations that are used in a specific phase of compilation, but may not be legal in later phases, and vice versa. For example, we have both cf (unstructured control flow) and scf (structured control flow) dialects. When lowering to Miden Assembly, we require all control flow to be represented using the scf dialect, but early in the pipeline, we receive programs with control flow in the cf dialect, which is then "lifted" into scf before code generation.

See the following sections for more information on the concepts introduced above:

• Dialects
• Operations
• Regions
• Blocks
• Values
• Traits
• Interfaces

Dialects

A dialect is a logical grouping of operations, attributes, and associated analyses and transformations. It forms the basis on which the IR is modularized and extended.

There are currently a limited set of dialects, comprising the set of operations we currently have defined lowerings for, or can be converted to another dialect that does:

• builtin, which provides the World, Component, Module, Function, GlobalVariable, Segment, and Ret operations.
• test, used for testing within the compiler without external dependencies.
• ub, i.e. undefined behavior, which provides the Poison (and associated attribute type), and Unreachable operations.
• arith, i.e. arithmetic, which provides all of the mathematical operations we currently support lowerings for. This dialect also provides the Constant operation for all supported numeric types.
• cf, i.e. control flow, which provides all of the unstructured control flow or control flow-adjacent operations, i.e. Br, CondBr, Switch, and Select. The latter is not strictly speaking a control flow operation, but is semantically similar. This dialect is largely converted to the scf dialect before lowering, with the exception of Select, and limited support for CondBr (to handle a specific edge case of the control flow lifting transformation).
• scf, i.e. structured control flow, which provides structured equivalents of all the control flow we support, i.e. If, While (for both while/do and do/while loops), and IndexSwitch (essentially equivalent to cf.switch, but in structured form). The Yield and Condition operations are defined in this dialect to represent control flow within (or out of) a child region of one of the previous three ops.
• hir (likely to be renamed to masm or vm in the near future), which is currently used to represent the set of operations unique to the Miden VM, or correspond to compiler intrinsics implemented in Miden Assembly.

See defining dialects for more information on what dialects are responsible for in HIR.

Operations

An operation represents a computation. Inputs to that computation are in the form of operands, and outputs of the computation are in the form of results. In practice, an operation may also have effects, such as reading/writing from memory, which also represent input/output of the operation, but not explicitly represented in an operation's operands and results.

Operations can contain zero or more regions. An operation with no regions is also called a primitive operation; while an operation with one or more regions is called a structured operation. An example of the former is the hir.call operation, i.e. the function call instruction. An example of the latter is scf.if, which represents a structured conditional control flow operation, consisting of two regions, a "then" region, and an "else" region.

Operations can implement any number of traits and interfaces, so as to allow various pieces of IR infrastructure to operate over them generically based on those implementations. For example, the arith.add operation implements the BinaryOp and Commutative traits; the scf.if operation implements the HasRecursiveSideEffects trait, and the RegionBranchOpInterface interface.

Operations that represent unstructured control flow may also have successors, i.e. the set of blocks which they transfer control to. Edges in the control flow graph are formed by "block operands" that act as the value type of a successor. Block operands are tracked in the use list of their associated blocks, allowing one to traverse up the CFG from successors to predecessors.

Operations may also have associated attributes. Attributes represent metadata attached to an operation. Attributes are not guaranteed to be preserved during rewrites, except in certain specific cases.

Regions

A region encapsulates a control-flow graph (CFG) of one or more basic blocks. In HIR, the contents of a region are almost always in single-static assignment (SSA) form, meaning that values may only be defined once, definitions must dominate uses, and operations in the CFG described by the region are executed one-by-one, from the entry block of the region, until control exits the region (e.g. via builtin.ret or some other terminator instruction).

The order of operations in the region closely corresponds to their scheduling order, though the code generator may reschedule operations when it is safe - and more efficient - to do so.

Operations in a region may introduce nested regions. For example, the body of a function consists of a single region, and it might contain an scf.if operation that defines two nested regions, one for the true branch, and one for the false branch. Nested regions may access any values in an ancestor region, so long as those values dominate the operation that introduced the nested region. The exception to this are operations which are isolated from above. The regions of such an operation are not permitted to reference anything defined in an outer scope, except via symbols. For example, functions are an operation which is isolated from above.

The purpose of regions, is to allow for hierarchical/structured control flow operations. Without them, representing structured control flow in the IR is difficult and error-prone, due to the semantics of SSA CFGs, particularly with regards to analyses like dominance and loops. It is also an important part of what makes operations such a powerful abstraction, as it provides a way to generically represent the concept of something like a function body, without needing to special-case them.

A region must always consist of at least one block (the entry block), but not all regions allow multiple blocks. When multiple blocks are present, it implies the presence of unstructured control flow, as the only way to transfer control between blocks is by using unstructured control flow operations, such as cf.br, cf.cond_br, or cf.switch. Structured control flow operations such as scf.if, introduce nested regions consisting of only a single block, as all control flow within a structured control flow op, must itself be structured. The specific rules for a region depend on the semantics of the containing operation.

Blocks

A block, or basic block, is a set of one or more operations in which there is no control flow, except via the block terminator, i.e. the last operation in the block, which is responsible for transferring control to another block, exiting the current region (e.g. returning from a function body), or terminating program execution in some way (e.g. ub.unreachable).

Blocks belong to regions, and if a block has no parent region, it is considered orphaned.

A block may declare block arguments, the only other way to introduce values into the IR, aside from operation results. Predecessors of a block must ensure that they provide inputs for all block arguments when transfering control to the block.

Blocks which are reachable as successors of some control flow operation, are said to be used by that operation. These uses are represented in the form of the BlockOperand type, which specifies what block is used, what operation is the user, and the index of the successor in the operation's successor storage. The BlockOperand is linked into the use-list of the referenced Block, and a BlockOperandRef is stored as part of the successor information in the using operation's successor storage. This is the means by which the control flow graph is traversed - you can navigate to predecessors of a block by visiting all of its "users", and you navigate to successors of a block by visiting all successors of the block terminator operation.

Values

A value represents terms in a program, temporaries created to store data as it flows through the program. In HIR, which is in SSA form, values are immutable - once created they cannot be changed nor destroyed. This property of values allows them to be reused, rather than recomputed, when the operation that produced them contains no side-effects, i.e. invoking the operation with the same inputs must produce the same outputs. This forms the basis of one of the ways in which SSA IRs can optimize programs.

Value definitions (aka "defs") can be introduced in two ways:

1. Block argument lists, i.e. the BlockArgument value kind. In general, block arguments are used as a more intuitive and ergonomic representation of SSA phi nodes, joining multiple definitions of a single value together at control flow join points. Block arguments are also used to represent region arguments, which correspond to the set of values that will be forward to that region by the parent operation (or from a sibling region). These arguments are defined as block arguments of the region's entry block. A prime example of this, is the Function op. The parameters expressed by the function signature are reflected in the entry block argument list of the function body region.
2. Operation results, i.e. the OpResult value kind. This is the primary way in which values are introduced.

Both value kinds above implement the Value trait, which provides the set of metadata and behaviors that are common across all value kinds. In general, you will almost always be working with values in terms of this trait, rather than the concrete type.

Values have uses corresponding to usage as an operand of some operation. This is represented via the OpOperand type, which encodes the use of a specific value (i.e. its user, or owning operation; what value is used; its index in operand storage). The OpOperand is linked into the use list of the value, and the OpOperandRef is stored in the entity storage of the using operation. This allows navigating from an operation to all of the values it uses, as well from a value to all of its users. This makes replacing all uses of a value extremely efficient.

As always, all uses of a value must be dominated by its definition. The IR is invalid if this rule is ever violated.

Operands

An operand is a value used as an argument to an operation.

Beyond the semantics of any given operation, operand ordering is only significant in so far as it is used as the order in which those items are expected to appear on the operand stack once lowered to Miden Assembly. The earlier an operand appears in the list of operands for an operation, the closer to the top of the operand stack it will appear.

Similarly, the ordering of operand results also correlates to the operand stack order after lowering. Specifically, the earlier a result appears in the result list, the closer to the top of the operand stack it will appear after the operation executes.

Immediates

Immediates are a built-in attribute type, which we use to represent constants that are able to be used as "immediate" operands of machine instructions (e.g. a literal memory address, or integer value).

The Immediate type provides a number of useful APIs for interacting with an immediate value, such as bitcasts, conversions, and common queries, e.g. "is this a signed integer".

It should be noted, that this type is a convenience, it is entirely possible to represent the same information using other types, e.g. u32 rather than Immediate::U32, and the IR makes no assumptions about what type is used for constants in general. We do, however, assume this type is used for constants in specific dialects of the IR, e.g. hir.

Attributes

Attributes represent named metadata attached to an operation.

Attributes can be used in two primary ways:

• A name without a value, i.e. a "marker" attribute. In this case, the presence of the attribute is significant, e.g. #[inline].
• A name with a value, i.e. a "key-value" attribute. This is the more common usage, e.g. #[overflow = wrapping].

Any type that implements the AttributeValue trait can be used as the value of a key/value-style attribute. This trait is implemented by default for all integral types, as well as a handful of IR types which have been used as attributes. There are also a few generic built-in attribute types that you may be interested in:

• ArrayAttr, which can represent an array/vector-like collection of attribute values, e.g. #[indices = [1, 2, 3]].
• SetAttr, which represents a set-like collection of attribute values. The primary difference between this and ArrayAttr is that the values are guaranteed to be unique.
• DictAttr, which represents a map-like collection of attribute values.

It should be noted that there is no guarantee that attributes are preserved by transformations, i.e. if an operation is erased/replaced, attributes may be lost in the process. As such, you must not assume that they will be preserved, unless made an intrinsic part of the operation definition.

Traits

A trait defines some property of an operation. This allows operations to be operated over generically based on those properties, e.g. in an analysis or rewrite, without having to handle the concrete operation type explicitly.

Operations can always be cast to their implementing traits, as well as queried for if they implement a given trait. The set of traits attached to an operation can either be declared as part of the operation itself, or be attached to the operation at dialect registration time via dialect hooks.

There are a number of predefined traits, found in midenc_hir::traits, e.g.:

• IsolatedFromAbove, a marker trait that indicates that regions of the operation it is attached to cannot reference items from any parents, except via symbols.
• Terminator, a marker trait for operations which are valid block terminators
• ReturnLike, a trait that describes behavior shared by instructions that exit from an enclosing region, "returning" the results of executing that region. The most notable of these is builtin.ret, but scf.yield used by the structured control flow ops is also return-like in nature.
• ConstantLike, a marker trait for operations that produce a constant value
• Commutative, a marker trait for binary operations that exhibit commutativity, i.e. the order of the operands can be swapped without changing semantics.

Interfaces

An interface, in contrast to a trait, represents not only that an operation exhibits some property, but also provides a set of specialized APIs for working with them.

Some key examples:

• EffectOpInterface, operations whose side effects, or lack thereof, are well-specified. MemoryEffectOpInterface is a specialization of this interface specifically for operations with memory effects (e.g. read/write, alloc/free). This interface allows querying what effects an operation has, what resource the effect applies to (if known), or whether an operation affects a specific resource, and by what effect(s).
• CallableOpInterface, operations which are "callable", i.e. can be targets of a call-like operation. This allows querying information about the callable, such as its signature, whether it is a declaration or definition, etc.
• CallOpInterface, operations which can call a callable operation. This interface provides information about the call, and its callee.
• SelectOpInterface, operations which represent a selection between two values based on a boolean condition. This interface allows operating on all select-like operations without knowing what dialect they are from.
• BranchOpInterface, operations which implement an unstructured control flow branch from one block to one or more other blocks. This interface provides a generic means of accessing successors, successor operands, etc.
• RegionBranchOpInterface, operations which implement structured control flow from themselves (the parent), to one of their regions (the children). Much like BranchOpInterface, this interface provides a generic means of querying which regions are successors on entry, which regions are successors of their siblings, whether a region is "repetitive", i.e. loops, and more.
• RegionBranchTerminatorOpInterface, operations which represent control flow from some region of a RegionBranchOpInterface op, either to the parent op (e.g. returning/yielding), or to another region of that op (e.g. branching/yielding). Such operations are always children of a RegionBranchOpInterface, and conversely, the regions of a RegionBranchOpInterface must always terminate with an op that implements this interface.

Symbol Tables

A symbol table represents a namespace in which symbols may be defined and resolved.

Operations that represent a symbol table, must implement the SymbolTable trait.

Symbol tables may be nested, so long as child symbol table operations are also valid symbols, so that the hierarchy of namespaces can be encoded as a symbol path (see Symbols).

Symbols

A symbol is a named operation, e.g. the function foo names that function so that it can be referenced and called from other operations.

Symbols are only meaningful in the context of a symbol table, i.e. the namespace in which a symbol is registered. Symbols within a symbol table must be unique.

A symbol is reified as a symbol path, i.e. foo/bar represents a symbol path consisting of two path components, foo and bar. Resolving that symbol path requires first resolving foo in the current symbol table, to an operation that is itself a symbol table, and then resolving bar there.

Symbol paths can come in two forms: relative and absolute. Relative paths are resolved as described above, while absolute paths are resolved from the root symbol table, which is either the containing world, or the nearest symbol table which has no parent.

Symbols, like the various forms of values, track their uses and definitions, i.e. when you reference a symbol from another operation, that reference is recorded in the use list of the referenced symbol. This allows us to trivially determine if a symbol is used, and visit all of those uses.

Successors and Predecessors

The concept of predecessor and successor corresponds to a parent/child relationship between nodes in a control-flow graph (CFG), where edges in the graph are directed, and describe the order in which control flows through the program. If a node $A$ transfers control to a node $B$ after it is finished executing, then $A$ is a predecessor of $B$, and $B$ is a successor of $A$.

Successors and predecessors can be looked at from a few similar, but unique, perspectives:

Relating blocks

We're generally interested in successors/predecessors as they relate to blocks in the CFG. This is of primary interest in dominance and loop analyses, as the operations belonging to a block inherit the interesting properties of those analyses from their parent block.

In abstract, the predecessor of a block is the operation which transfers control to that block. When considering what blocks are predecessors of the current block, we're deriving that by mapping each predecessor operation to its parent block.

We are often interested in specific edges of the CFG, and because it is possible for a predecessor operation to have multiple edges to the same successor block, it is insufficient to refer to these edges by predecessor op and target block alone, instead we also need to know the successor index in the predecessor op.

Unique edges in the CFG are represented in the form of the BlockOperand type, which provides not only references to the predecessor operation and the successor block, but also the index of the successor in the predecessor's successor storage.

Relating operations

This perspective is less common, but useful to be aware of.

Operations in a basic block are, generally, assumed to execute in order, top to bottom. Thus, the predecessor/successor terminology can also refer to the relationship between two consecutive operations in a basic block, i.e. if $A$ immediately precedes $B$ in a block, then $A$ is the predecessor of $B$, and $B$ is the successor of $A$.

We do not generally refer to this relationship in the compiler, except in perhaps one or two places, so as to avoid confusion due to the overloaded terminology.

Relating regions

Another important place in which the predecessor/successor terminology applies, is in the relationship between a parent operation and its regions, specifically when the parent implements RegionBranchOpInterface.

In this dynamic, the relationship exists between two points, which we represent via the RegionBranchPoint type, where the two points can be either the parent op itself, or any of its child regions. In practice, this produces three types of edges:

1. From the parent op itself, to any of its child regions, i.e. "entering" the op and that specific region). In this case, the predecessor is the parent operation, and the successor is the child region (or more precisely, the entry block of that region).
2. From one of the child regions to one of its siblings, i.e. "yielding" to the sibling region. In this case, the predecessor is the terminator operation of the origin region, and the successor is the entry block of the sibling tregion.
3. From a child regions to the parent operation, i.e. "returning" from the op. In this case, the predecessor is the terminator operation of the child region, and the successor is the operation immediately succeeding the parent operation (not the parent operation itself).

This relationship is important to understand when working with RegionBranchOpInterface and RegionBranchTerminatorOpInterface operations.

Relating call and callable

The last place where the predecessor/successor terminology is used, is in regards to inter-procedural analysis of call operations and their callees.

In this situation, predecessors of a callable are the set of call sites which refer to it; while successors of a callable are the operations immediately succeeding the call site where control will resume when returning from the callable region.

We care about this when performing inter-procedural analyses, as it dictates how the data flow analysis state is propagated from caller to callee, and back to the caller again.

High-Level Structure

Beyond the core IR concepts introduced in the previous section, HIR also imposes some hierarchical structure to programs in form of builtin operations that are special-cased in certain respects:

• Worlds
• Components
• Modules
• Functions

In short, when compiling a program, the inputs (source program, dependencies, etc.) are represented in a single world (i.e. everything we know about that program and what is needed to compile it). The input program is then translated into a single top-level component of that world, and any of it's dependendencies are represented in the form of component declarations (in HIR, a declaration - as opposed to a definition - consists of just the metadata about a thing, not its implementation, e.g. a function signature).

A component can contain one or more modules, and optionally, one or more data segments. Each module can contain any number of functions and global variables.

The terminology and semantics of worlds and components, are based on the Web Assembly Component Model. In particular, the following properties are key to understanding the relationships between these entities:

• Worlds must encode everything needed by a component
• Components represent a shared-nothing boundary, i.e. nothing outside a component can access the resources of that component (e.g. memory). We rely on this property so that we can correctly represent the interaction between Miden contexts (each of which has its own memory, with no way to access the memory of other contexts).
• Component-level exports represent the "interface" of a component, and are required to adhere to the Canonical ABI.

The following is a rough visual representation of the hierarchy and relationships between these concepts in HIR:

          World
            |
            v
   ---- Component -----------
  |                          |
  v                          |
Function  (component export) |
                             |
             ----------------
            |           |
            v           v
          Module  Data Segment
            |
            |-----------
            v           v
         Function  Global Variable
            |
            v
   ----- Region (a function has a single region, it's "body")
  |         |   (the body region has a single block, it's "entry")
  |         v
  |       Block -> Block Argument (function parameters)
  |         |        |
  |         |        |
  |         |        v
  |         |      Operand
  |         v        |  ^
   ---> Operation <--   |
            |           |
            v           |
          Result -------

A few notes:

• Dependencies between components may only exist between component-level exported functions, i.e. it is not valid to depend on a function defined in a module of another component directly.
• Only component exports use the Canonical ABI, internally they handle lifting/lowering to the "core" ABI of the function which actually implements the behavior being exported.
• Data segments represent data that will be written into the shared memory of a component when the component is initialized. Thus, they must be specified at component level, and may not be shared between components.
• Global variables, representing some region of memory with a specified type, by definition cannot be shared between components, and are only visible within a component. We further restrict their definition to be within a module. Global variables can be shared between modules, however.
• Worlds, components, and modules are single-region, single-block operations, with graph-like region semantics (i.e. their block does not adhere to SSA dominance rules). They all implement the SymbolTable trait, and all but World implements the Symbol trait.
• Functions are single-region, but that region can contain multiple blocks, and the body region is an SSA CFG region, i.e. it's blocks and operations must adhere to SSA dominance rules. The interaction with a function is determined by its signature, which dictates the types of its parameters and results, but these are not represented as operation operands/results, instead the function parameters are encoded as block parameters of its entry block, and function results are materialized at call sites based on the function signature. A validation rule ensures that the return-like operations in the function body return values that match the signature of the containing function.

Worlds

A world represents all available information about a program and its dependencies, required for compilation. It is unnamed, and so it is not possible to interact between worlds.

Worlds may only contain components (possibly in the future we'll relax this to allow for non-component modules as well, but not today). Each world is a symbol table for the components it contains, facilitating inter-component dependencies.

A world is by definition the root symbol table for everything it contains, i.e. an absolute symbol path is always resolved from the nearest world, or failing that, the nearest operation without a parent.

Components

A component is a named entity with an interface comprised of it's exported functions. This implicit interface forms a signature that other components can use to provide for link-time virtualization of components, i.e. any component that can fulfill a given interface, can be used to satisfy that interface.

Components may contain modules, as well as data segment definitions which will be visible to all code running within the component boundary.

A component declaration, as opposed to a definition, consists strictly of its exported functions, all of which are declarations, not definitions.

A component instance refers to a component that has had all of its dependencies resolved concretely, and is thus fully-defined.

The modules of a component provide the implementation of its exported interface, i.e. top-level component functions typically only handle lifting module exports into the Canonical ABI.

Modules

A module is primarily two things:

1. A named container for one or more functions belonging to a common namespace.
2. A concrete implementation of the functionality exported from a component.

Functions within a module may be exported. Functions which are not exported, are only visible within that module.

A module defines a symbol table, whose entries are the functions and global variables defined in that module. Relative symbol paths used within the module are always resolved via this symbol table.

Functions

A function is the highest-level unit of computation represented in HIR, and differs from the other container types (e.g. component, module), in that its body region is an SSA CFG region, i.e. its blocks and operations must adhere to the SSA dominance property.

A function declaration is represented as a function operation whose body region is empty, i.e. has no blocks.

A function has a signature that encodes its parameters and results, as well as the calling convention it expects callers to use when calling it, and any special attributes that apply to it (i.e. whether it is inlineable, whether any of its parameters are special in some way, etc.).

Function parameters are materialized as values in the form of entry block arguments, and always correspond 1:1. Function results are materialized as values only at call sites, not as operation results of the function op.

Blocks in the function body must be terminated with one of two operations:

• builtin.ret, which returns from the function to its caller. The set of operands passed to this operation must match the arity and types specified in the containing function's signature.
• ub.unreachable, representing some control flow path that should never be reachable at runtime. This is translated to an abort/trap during code generation. This operation is defined in the ub dialect as it corresponds to undefined behavior in a program.

Global Variables

A global variable represents a named, typed region of memory, with a fixed address at runtime.

Global variables may specify an optional initializer, which is a region consisting of operations that will be executed in order to initialize the state of the global variable prior to program start. Typically, the initializer should only consist of operations that can be executed at compile-time, not runtime, but because of how Miden memory is initialized, we can actually relax this rule.

Pass Infrastructure

Compiler passes encode transformations of the IR from frontend to backend. In HIR, you define a pass over a concrete operation type, or over all operations and then filter on some criteria.

The execution of passes is configured and run via a pass manager, which you construct and then add passes to, and then run once finalized.

Passes typically make uses of analyses in order to perform their specific transformations. In order to share the computation of analyses between passes, and to correctly know when those analyses can be preserved or recomputed, the pass manager will construct an analysis manager, which is then provided to passes during execution, so that they can query it for a specific analysis of the current operation.

Passes can register statistics, which will then be tracked by the pass manager.

The primary way you interact with the pass infrastructure is by:

1. Construct a PassManager for whatever root operation type you plan to run the pass pipeline on.
2. Add one or more Pass implementations, nesting pass managers as needed in order to control which passes are applied at which level of the operation hierarchy.
3. Run the PassManager on the root operation you wish to transform.

In HIR, there are three primary types of passes:

• DIY, i.e. anything goes. What these do is completely up to the pass author.
• Pattern rewrites, which match against an operation by looking for some pattern, and then performing a rewrite of that operation based on that pattern. These are executed by the GreedyPatternRewriteDriver, and must adhere to a specific set of rules in order for the driver to be guaranteed to reach fixpoint.
• Canonicalizations, a special case of pattern rewrite which are orchestrated by the Canonicalizer rewrite pass.

Analyses

An analysis is responsible for computing some fact about the given IR entity it is given. Facts include things such as: the dominance tree for an SSA control flow graph; identifying loops and their various component parts such as the header, latches, and exits; reachability; liveness; identifying unused (i.e. dead) code, and much more.

Analyses in the IR can be defined in one of two ways (and sometimes both):

1. As an implementation of the Analysis trait. This is necessary for analyses which you wish to query from the AnalysisManager in a pass.
2. As an implementation of the DataFlowAnalysis trait, or one of its specializations, e.g. DenseBackwardDataFlowAnalysis. These are analyses which adhere to the classical data flow analysis rules, i.e. the analysis state represents a join/meet semi-lattice (depending on the type and direction of the analysis), and the transfer function ensures that the state always converges in a single direction.

Analysis implementations get the current AnalysisManager instance in their analyze callback, and can use this to query other analyses that they depend on. It is important that implementations also implement invalidate if they should be invalidated based on dependent analyses (and whether those have been invalidated can be accessed via the provided PreservedAnalyses state in that callback).

Analyses can be implemented for a specific concrete operation, or any operation.

Pattern Rewrites

See the Rewrites document for more information on rewrite passes in general, including the current set of transformation passes that build on the pattern rewrite infrastructure.

Pattern rewrites are essentially transformation passes which are scheduled on a specific operation type, or any operation that implements some trait or interface; recognizes some pattern about the operation which we desire to rewrite/transform in some way, and then attempts to perform that rewrite.

Pattern rewrites are applied using the GreedyPatternRewriteDriver, which coordinates the application of rewrites, reschedules operations affected by a rewrite to determine if the newly rewritten IR is now amenable to further rewrites, and attempts to fold operations and materialize constants, and if so configured, apply region simplification.

These are the core means by which transformation of the IR is performed.

Canonicalization

Canonicalization is a form of pattern rewrite that applies to a specific operation type that has a canonical form, recognizes whether the operation is in that form, and if not, transforms it so that it is.

What constitutes the canonical form of an operation, depends on the operation itself:

• In some cases, this might be ensuring that if an operation has a constant operand, that it is always in the same position - thus making pattern recognition at higher levels easier, as they only need to attempt to match a single pattern.
• In the case of control flow, the canonical form is often the simplest possible form that preserves the semantics.
• Some operations can be simplified based on known constant operands, or reduced to a constant themselves. This process is called constant folding, and is an implicit canonicalization of all operations which support folding, via the Foldable trait.

Folding

Constant-folding is the process by which an operation is simplified, replaced with a simpler/less-expensive operation, or reduced to a constant value - when some or all of its operands are known constant values.

The obvious example of this, is something like v3 = arith.add v1, v2, where both v1 and v2 are known to be constant values. This addition can be performed at compile-time, and the entire arith.add replaced with arith.constant, potentially enabling further folds of any operation using v3.

What about when only some of the operands are constant? That depends on the operation in question. For example, something like v4 = cf.select v1, v2, v3, where v1 is known to be the constant value true, would allow the entire cf.select to be erased, and all uses of v4 replaced with v2. However, if only v2 was constant, the attempt to fold the cf.select would fail, as no change can be made.

A fold has three outcomes:

• Success, i.e. the operation was able to be folded away; it can be erased and all uses of its results replaced with the fold outputs
• In-place, the operation was able to be simplified, but not folded away/replaced. In this case, there are no fold outputs, the original operation is simply updated.
• Failure, i.e. the operation could not be folded or simplified in any way

Operation folding can be done manually, but is largely handled via the canonicalization pass, which combines folding with other pattern rewrites, as well as region simplification.

Implementation Details

The following sections get into certain low-level implementation details of the IR, which are important to be aware of when working with it. They are not ordered in any particular way, but are here for future reference.

You should always refer to the documentation associated with the types mentioned here when working with them; however, this section is intended to provide an intro to the concepts and design decisions involved, so that you have the necessary context to understand how these things fit together and are used.

Session

The Session type, provided by the midenc-session crate, represents all of the configuration for the current compilation session, i.e. invocation.

A session begins by providing the compiler driver with some inputs, user-configurable flags/options, and intrumentation handler. A session ends when those inputs have been compiled to some output, and the driver exits.

Context

The Context type, provided by the midenc-hir crate, encapsulates the current session, and provides all of the IR-specific storage and state required during compilation.

In particular, a Context maintains the set of registered dialects, their hooks, the allocator for all IR entities produced with that context, and the uniquer for allocated value and block identifiers. All IR entities which are allocated using the Context, are referenced using entity references.

The Context itself is not commonly used directly, except in rare cases - primarily only when extending the context with dialect hooks, and when allocating values, operands, and blocks by hand.

Every operation has access to the context which created it, making it easy to always access the context when needed.

Entity References

All IR entities, e.g. values, operations, blocks, regions - are allocated via an arena allocator provided by the Context, along with any custom metadata relevant for the specific entity type. A custom smart pointer type, called RawEntityRef, is then used to reference those entities, while simultaneously providing access to the metadata, and enforcing Rust's aliasing rules via dynamic borrow checking.

This approach is used due to the graph-like structure of the IR itself - the ergonomics we can provide this way far outweigh the cost of dynamic borrow checking. However, it does place the burden on the programmer to carefully manage the lifetime of borrowed entities, so as to avoid aliasing conflicts. To make such issues easy to troubleshoot and fix, the RawEntityRef type will track both the source location of a borrow, and the location where a conflicting borrow occurs, and print this information as part of the runtime error that occurs (when compiled with the debug_refcell feature enabled).

There are two main "types" of RawEntityRef metadata:

• (), aliased as UnsafeEntityRef
• IntrusiveLink, aliased as UnsafeIntrusiveEntityRef.

In both cases, the type is aliased to reflect the underlying entity type being referenced, e.g. BlockRef is an UnsafeIntrusiveEntityRef<Block>, and ValueRef is an UnsafeEntityRef<dyn Value>.

The latter of the two is the most important, as it is used for all entity types which have a parent entity in which they are tracked by means of an intrusive doubly-linked list (called an entity list), e.g. operations, blocks, regions, operands, etc. The key thing that the UnsafeIntrusiveEntityRef type provides, is access to the parent entity, if linked to one, and access to the previous and next sibling of the containing entity list, if present - without needing to borrow the underlying entity. This is critical for traversing the IR without needing to borrow each entity being traversed, unless one wants to explicitly visit it. Entities allocated into an UnsafeIntrusiveEntityRef must also implement the EntityListItem trait, which provides various callbacks that are invoked when inserting/removing/transferring them between the entity list of the parent entity type.

The UnsafeEntityRef type, in contrast, is used for entities that are not tracked in an entity list, but in entity storage, i.e. a small, resizeable vector of references which are stored as part in the parent entity. Examples include block arguments, operation results, and operation successors. Entities allocated into an UnsafeEntityRef and stored in EntityStorage, must also implement the StoreableEntity trait, which provides a similar set of callbacks to EntityListItem for managing the lifecycle of an entity as it is inserted, removed, etc.

Entity Storage

This refers to the EntityStorage<T> type, which abstracts over the storage of IR entities in a small, resizeable vector attached to a parent entity.

The EntityStorage type provides the following:

• Lifecycle management of stored entities, via the StoreableEntity trait
• Grouping of entities within storage, with relative indexing, support for insertion, removal, iteration, etc. This is used, for example, to use a single EntityStorage for all operands of an operation, while grouping operands semantically (e.g. group 0 are operands of the op itself, group 1 through N are operand groups for each successor of the operation).
• Conveniences for indexing, slicing, iterating, etc.

StoreableEntity

The StoreableEntity trait is used to ensure that, as entities are inserted/removed/transferred between instances of EntityStorage, that metadata about the relationship between the stored entity, and the parent, is updated accordingly.

For example, this is used to ensure that when an OpOperand is inserted into the operand storage of an operation, that it is added to the use list of the referenced Value. Conversely, when that same operand is removed from the operand storage, the use of the referenced Value is removed.

ValueRange

The ValueRange type is intended to provide a uniform, efficient API over slices/ranges of value-like types, in the form of ValueRef. It can be directly constructed from any EntityRange or EntityStorage reference of BlockArgumentRef, OpOperandRef, or OpResultRef type; as well as raw slices of any of those types in addition to ValueRef.

It supports borrowed and owned variants, iteration, indexing, and conversions.

In general, you should prefer to use ValueRange when working with collections of value-like types, unless you have a specific reason otherwise.

Entity Lists

An entity list is simply a doubly-linked, intrusive list, owned by some entity, in which references to some specific child entity type are stored.

Examples include:

• The list of regions belonging to an operation
• The list of blocks belonging to a region
• The list of operations belonging to a block
• The list of operands using a block argument/op result
• The list of symbol users referencing a symbol

In conjunction with the list itself, there are a set of traits which facilitate automatically maintaining the relationship between parent and child entity as items are inserted, removed, or transferred between parent lists:

• EntityParent<Child>, implemented by any entity type which has some child entity of type Child. This provides us with the ability to map a parent/child relationship to the offset of the intrusive linked list in the parent entity, so that we can construct a reference to it. Entities can be the parent of multiple other entity types.
• EntityWithParent<Parent = T>, implemented by the child entity which has some parent type T, this provides the inverse of EntityParent, i.e. the ability for the entity list infrastructure to resolve the parent type of a child entity it stores, and given a reference to the parent entity, get the relevant intrusive list for that child. Entities with a parent may only have a single parent entity type at this time.
• EntityListItem, implemented by any entity type which can be stored in an entity list. This trait provides the set of callbacks that are invoked by the entity list infrastructure when modifying the list (inserting, removing, and transferring items). This trait is public, but the entity list infra actually uses a different trait, called EntityListTraits, which is specialized based on whether the list items implement just EntityListItem, or both EntityListItem and EntityWithParent. The specialization for the latter ensures that the parent/child relationship is updated appropriately by the entity list itself, rather than requiring EntityListItem implementations to do so.

We use intrusive linked lists for storing sets of entities that may be arbitrarily large, and where the O(1) insertion, removal, splicing and splitting makes up for the less cache-friendly iteration performance. Given a reference to an entity, we can always construct a cursor to that element of the list, and traverse the list from there, or modify the list there - this is a much more frequent operation than iterating these lists.

Traversal

Before we can discuss the various ways of traversing the IR, we need to clarify what aspect of the IR we're interested in traversing:

• The data flow graph, i.e. nodes are operations, edges are formed by operands referencing values.
• The control flow graph, i.e. nodes are either operations, blocks, or regions; and edges are formed by operations which transfer control (to the next op, to a specific set of successor blocks or regions).
• The call graph, i.e. nodes are symbols which implement CallableOpInterface, and edges are formed by operations which implement CallOpInterface.

There are also a few traversal primitives which are commonly used:

• Any UnsafeIntrusiveEntityRef for a type which implements EntityListItem, provides next and prev methods which allow navigating to the next/previous sibling item in the list, without borrowing the entity itself. In some cases, being siblings in an entity list does not mean that the items are near each other, e.g. the only thing shared in common between uses of a Symbol, is the symbol they refer to, but their order in the symbol use-list has no semantic meaning. In others, being siblings mean that the items are actually located next to each other in that order, e.g. operations in a block.
• Similarly, any UnsafeIntrusiveEntityRef for a type which implements EntityWithParent, provides a parent method which allow navigating to the parent entity from the child, without borrowing either of them.
• All child entities "owned" by a parent entity, are stored in either a entity list or entity storage attached to that entity.

These three primitives provide the core means by which one can navigate the relevant graph in any direction.

Another thing to be aware of, is that relationships between entities where there may be multiple edges between the same two entities, are typically represented using a special node type. For example:

• OpOperand represents a use of a Value by an operation. In order to maintain the use-def graph of values, each value type, e.g. BlockArgument, has its own entity list for OpOperands. What is stored in the relevant entity storage of the operation then, are OpOperandRefs. So while operands are intuitively something we think of as an intrinsic part of an operation, they are actually their own IR entity, which is then stored by reference both in the operation, and in the use-list of the value they reference.
• BlockOperand represents a "use" of a Block by an operation as a successor. This type is responsible for forming the edges of the CFG, and so much like OpOperand, the Block type has an entity list for BlockOperands, effectively the set of that block's predecessors; while the operation has entity storage for BlockOperandRefs (or more precisely, SuccessorInfo, of which BlockOperandRef is one part).
• SymbolUse represents a use of a Symbol by an operation. This underpins the maintenance of the call graph. Unlike operands, symbol usage is not tracked as a fundamental part of every operation, i.e. there is no dedicated symbols field of the Operation type which provides the entity storage for SymbolUseRefs, nor is there a field which defines the entity list. Instead, the symbol use list of an op that implements Symbol, must be defined as part of the concrete operation type. Similarly, any concrete operation type that can use/reference a Symbol op, must determine for itself how it will store that use. For this reason, symbol maintenance is a bit less ergonomic than other entity types.

We now can explore the different means by which the IR can be traversed:

1. Using the raw traversal primitives described above.
2. The Graph trait
3. The Walk and RawWalk traits
4. CallOpInterface and CallableOpInterface (specifically for traversing the call graph)

The Graph trait

The Graph trait is an abstraction for directed graphs, and is intended for use when writing generic graph algorithms which can be reused across multiple graph types. For example, the implementation of pre-order and post-order visitors is implemented over any Graph.

This trait is currently implemented for Region, Block/BlockRef, and DomTreeNode, as so far they are the only types we've needed to visit using this abstraction, primarily when performing pre-order/post-order visits of the CFG and/or dominance tree.

The Walk and RawWalk traits

The Walk trait defines how to walk all children of a given type, which are contained within the type for which Walk is being implemented. For example:

• Walk<Operation> for Region defines how to traverse a region to visit all of the operations it contains, recursively.
• Walk<Region> for Operation defines how to traverse an operation to visit all of the regions it contains, recursively.

The difference between Walk and RawWalk, is that Walk requires borrowed references to the types it is implemented for, while RawWalk relies on the traversal primitives we introduced at the start of this section, to avoid borrowing any of the entities being traversed, with the sole exception being to access child entity lists long enough to get a reference to the head of the list. If we are ever mutating the IR as we visit it, then we use RawWalk, otherwise Walk tends to be more ergonomic.

The Walk and RawWalk traits provide both pre- and post-order traversals, which dictates in what order the visit callback is invoked. You can further dictate the direction in which the children are visited, e.g. are operations of a block visited forward (top-down), or backward (bottom-up)? Lastly, if you wish to be able to break out of a traversal early, the traits provide variants of all functions which allow the visit callback to return a WalkResult that dictates whether to continue the traversal, skip the children of the current node, or abort the traversal with an error.

CallOpInterface and CallableOpInterface

These two interfaces provide the means for navigating the call graph, which is not explicitly maintained as its own data structure, but is rather implied by the connections between symbols and symbol uses which implement these interfaces, in a program.

One is generally interested in the call graph for one of a couple reasons:

1. Determine if a function/callable is used
2. Visit all callers of a function/callable
3. Visit the call graph reachable from a given call site as part of an analysis
4. Identify cycles in the call graph

For 1 and 2, one can simply use the Symbol use-list: an empty use-list means the symbol is unused. For non-empty use-lists, one can visit every use, determine if that use is by a CallOpInterface, and take some action based on that.

For 2 and 3, the mechanism is essentially identical:

1. Assume that you are starting from a call site, i.e. an operation that implements CallOpInterface. Your first step is generally going to be to determine if the callable is a SymbolPath, or a ValueRef (i.e. an indirect call), using the get_callable_for_callee interface method.
2. If the callable is a ValueRef, you can try to trace that value back to an operation that materialized it from a Symbol (if that was the case), so as to make your analysis more precise; but in general there can be situations in which it is not possible to do so. What this means for your analysis depends on what that analysis is.
3. If the callable is a SymbolPath, then we need to try and resolve it. This can be done using the resolve or resolve_in_symbol_table interface methods. If successful, you will get a SymbolRef which represents the callable Symbol. If the symbol could not be resolved, None is returned, and you can traverse that edge of the call graph no further.
4. Once you've obtained the SymbolRef of the callable, you can borrow it, and then cast the &dyn Symbol reference to a &dyn CallableOpInterface reference using symbol.as_symbol_operation().as_trait::<dyn CallableOpInterface>().
5. With that reference, you call the get_callable_region interface method. If it returns None, then the callable represents a declaration, and so it is not possible to traverse the call graph further. If it returns a RegionRef, then you proceed by traversing all of the operations in that region, looking for more call sites to visit.

Program Points

A program point essentially represents a cursor in the CFG of a program. Specifically, program points are defined as a position before, or after, a block or operation. The type that represents this in the IR is ProgramPoint, which can be constructed from just about any type of block or operation reference.

Program points are used in a few ways:

• To specify where a block or operation should be inserted
• To specify at what point a block should be split into two
• To specify at what point a block should be merged into another
• To anchor data flow analysis state, e.g. the state before and after an operation, or the state on entry and exit from a block.

Currently, we distinguish the points representing "before" a block (i.e. at the start of the block), and "after" a block (i.e. at the end of the block), from the first and last operations in the block, respectively. Thus, even though a point referring to the start of the block, and a point referring to "before" the first operation in that block, effectively refer to the same place, we currently treat them as distinct locations. This may change in the future, but for now, it is something to be aware of.

The ProgramPoint type can be reified as a literal cursor into the operation list of a block, and then used to perform some action relative to that cursor.

The key thing to understand about program points has to do with the relationship between before/after (or start/end) and what location that actually refers to. The gist, is that a program point, when materialized as a cursor into an operation list, will always have the cursor positioned such that if you inserted a new operation at that point, it would be placed where you expect it to be - i.e. if "before" an operation, the insertion will place the new item immediately preceding the operation referenced by the program point. This is of particular importance if inserting multiple operations using the same point, as the order in which operations will be inserted depends on whether the position is before or after the point. For example, inserting multiple items "before" an operation, will have them appear in that same order in the containing block. However, inserting multiple items "after" an operation, will have them appear in reverse order they were inserted (i.e. the last to be inserted will appear first in the block relative to the others).

Defining Dialects

Defining a new dialect is as simple as defining a struct type which implements the Dialect trait. For example:

#![allow(unused)]
fn main() {
use midenc_hir::{Dialect, DialectInfo};

#[derive(Debug)]
pub struct MyDialect {
    info: DialectInfo,
}

impl Dialect for MyDialect {
    fn info(&self) -> &DialectInfo {
        &self.info
    }
}
}

One last thing remains before the dialect is ready to be used, and that is dialect registration.

Dialect Registration

Dialect registration is the means by which a dialect and its operations are registered with the Context, such that operations of that dialect can be built.

First, you must define the DialectRegistration implementation. To extend our example from above:

#![allow(unused)]
fn main() {
impl DialectRegistration for MyDialect {
    const NAMESPACE: &'static str = "my";

    #[inline]
    fn init(info: DialectInfo) -> Self {
        Self { info }
    }

    fn register_operations(info: &mut DialectInfo) {
        info.register_operation::<FooOp>();
    }
}
}

This provides all of the information needed by the Context to register our dialect, i.e. what namespace the dialect uses, and what operations are registered with the dialect.

The next step is to actually register the dialect with a specific Context. In general, this is automatically handled for you, i.e. whenever an operation of your dialect is being built, a call to context.get_or_register_dialect::<MyDialect>() is made, so as to get a reference to the dialect. If the dialect has not yet been registered, a fresh instance will be constructed, all registered dialect hooks will be invoked, and the initialized dialect registered with the context, before returning a reference to the registered instance.

Dialect Hooks

In some cases, it is necessary/desirable to extend a dialect with types/behaviors that we do not want (or cannot make) dependencies of the dialect itself. For example, extending the set of traits/interfaces implemented by operations of some dialect.

The mechanism by which this is done, is in the form of dialect hooks, functions which are invoked when a dialect is being registered, before the main dialect registration callbacks (e.g. register_operations) are invoked. Hooks are provided a reference to the raw DialectInfo, which can be modified as if the hook is part of the DialectRegistration itself.

Of particular use, is the DialectInfo::register_operation_trait method, which can be used to register a trait (or interface) to an operation before it is registered by the dialect. These "late-bound" traits are then added to the set of traits/interfaces defined as part of the operation itself, when the operation is registered with DialectInfo::register_operation.

We currently use dialect hooks for:

• Attaching the midenc_codegen_masm::Lowering trait to all operations for which we have defined its lowering to Miden Assembly.
• Attaching the midenc_hir_eval::Eval trait to all operations for which we have defined evaluation semantics, for use with the HIR evaluator.

Defining Operations

Defining operations involves a non-trivial amount of boilerplate if done by hand, so we have defined the #[operation] proc-macro attribute which takes care of all the boilerplate associated with defining a new operation.

As a result, defining an operation looks like this (using an example from midenc_dialect_arith):

#![allow(unused)]
fn main() {
use midenc_hir::{derive::operation, effects::*, traits::*, *};

use crate::ArithDialect;

/// Two's complement sum
#[operation(
    dialect = ArithDialect,
    traits(BinaryOp, Commutative, SameTypeOperands, SameOperandsAndResultType),
    implements(InferTypeOpInterface, MemoryEffectOpInterface)
)]
pub struct Add {
    #[operand]
    lhs: AnyInteger,
    #[operand]
    rhs: AnyInteger,
    #[result]
    result: AnyInteger,
    #[attr]
    overflow: Overflow,
}

impl InferTypeOpInterface for Add {
    fn infer_return_types(&mut self, _context: &Context) -> Result<(), Report> {
        let lhs = self.lhs().ty().clone();
        self.result_mut().set_type(lhs);
        Ok(())
    }
}

// MemoryEffectOpInterface is an alias for EffectOpInterface<MemoryEffect>
impl EffectOpInterface<MemoryEffect> for Add {
    fn has_no_effect(&self) -> bool {
        true
    }

    fn effects(
        &self,
    ) -> EffectIterator<MemoryEffect> {
        EffectIterator::from_smallvec(smallvec![])
    }
}
}

To summarize:

• dialect specifies the dialect to which the operation will be registered
• traits specifies the set of derivable traits for this operation.
• implements specifies the set of traits/interfaces which will be manually implemented for this operation. If any of the listed traits/interfaces are not implemented, a compiler error will be emitted.
• The fields of the Add struct represent various properties of the operation. Their meaning depends on what (if any) attributes they are decorated with:
  • The #[operand] attribute represents an expected operand of this operation, and the field type represents the type constraint to apply to it.
  • The #[result] attribute represents a result produced by this operation, and the field type represents the type constraint to apply to it.
  • The #[attr] attribute represents a required attribute of this operation. If the #[default] attribute is present, it is treated as an optional attribute.
  • If a field has no attributes, or only #[default], it is defined as part of the concrete operation struct, and is considered an internal detail of the op.
  • All other fields are not actually stored as part of the concrete operation type, but as part of the underlying Operation struct, and methods will be generated in an impl Add block that provide access to those fields in all the ways you'd expect.
  • The #[operand], #[attr], and undecorated fields are all expected, in that order, as arguments to the op builder when constructing an instance of this op.

There are a variety of field attributes and options for them that are not shown here. For now, the best reference for these is looking at the set of current dialects for an operation that is similar to what you want to define. You can also look at the implementation of the #[operation] proc-macro in midenc_hir_macros as the authoritative source on what is supported and how it affects the output. In the future we will provide more comprehensive documentation for it.

Builders

Constructing the IR is generally done via implementations of the Builder trait, which includes implementations of the Rewriter trait, as the former is a super-trait of the latter. Typically, this means the OpBuilder type.

Aside from a variety of useful APIs e.g. creating blocks, setting the insertion point of the builder, etc., most commonly you will be constructing specific operations, which is done in one of two ways:

• The lowest level primitive, actually provided by the BuilderExt trait due to the need to keep Builder object-safe, is its create<T, Args> method. This method produces an implementation of BuildableOp for the specified operation type (i.e. the T type parameter), and signature (i.e. the Args type parameter, which must be a tuple type). The desired operation is then constructed by applying the necessary arguments to the BuildableOp as a function (because BuildableOp is an implementation of the FnOnce closure type).
• Much more commonly however, this boilerplate will be abstracted away for you by dialect-specific extensions of the Builder trait, e.g. the BuiltinOpBuilder trait extends all Builder implementations with methods for constructing any of the builtin dialect operations, such as the ret method, which constructs the builtin.return operation. All of the dialects used by the compiler define such a trait, all that is required is to bring it into scope in order to construct the specific operations you want.

If the builder has a valid insertion point set, then either of the above methods will also insert the constructed operation at that point.

The primary difference between Rewriter and Builder, is that the Rewriter API surface is comprised primarily of methods that modify the IR in some way, e.g. moving things around, splitting and merging blocks, erasing operations, replacing ops with values, values with values, etc. Because Builder is a super-trait, it can be used both to construct new IR, and to rewrite existing IR.

Validation

A key aspect of the IR design, is to enable as much boilerplate as possible to be generated from the description of an operation, especially when it comes to verifying the validity of an operation using the type constraints of it's operands and results, and the traits/interfaces it implements.

Operations are currently validated when constructed by the OperationBuilder that underpins the BuildableOp implementation generated by the #[operation] proc-macro attribute. There are some known issues with doing it here, so we are likely to revisit this at some point, but for now this is the first place where verification occurs. It may also be triggered manually at any point by calling the Operation::verify method.

There are two traits which underpin the verification infrastructure:

• Verify<Trait> which represents the verification of Trait against Self, which is an operation type. Typically, all traits with associated verification rules, implement this trait for all T: Op + Trait.
• Verifier<Trait> which is a trait used to facilitate the generation of verification boilerplate specialized against a specific concrete operation type, without having to be aware of what operation traits/interfaces have associated Verify implementations. Instead, no-op verifiers are elided by the Rust compiler using const { } blocks. The method by which this is done is highly reliant on Rust's specialization infrastructure and type-level trickery.

In the future, we will likely move verification out of the OperationBuilder, into a dedicated pass that is run as part of a pass pipeline, and invoked on each operation via Operation::verify. This will enable more robust verification than is currently possible (as operations are not yet inserted in the IR at the point verification is applied currently).

Effects

Side effects are an important consideration during analysis and transformation of operations in the IR, particularly when evaluating whether operations can be reordered, re-materialized, spilled and reloaded, etc.

The infrastructure underpinning the management and querying of effects is built on the following pieces:

• The Effect trait, which is a marker trait for types which represent an effect, e.g. MemoryEffect which represents effects on memory, such as reading and writing, allocation and freeing.
• The EffectOpInterface<T: Effect> interface, which is implemented for any operation for which the effect T is specified, and provides a number of useful methods for querying effects of a specific operation instance.
• The Resource trait, which represents a type of resource to which an effect can apply. In many cases, one will use DefaultResource, which is a catch-all resource that implies a global effect. However, it is also possible to scope effects to a specific resource, such as a specific address range in memory. This could permit operations with disjoint effects to be reordered relative to one another, when that would otherwise not be allowed if the effects were global.
• The EffectInstance type, which provides metadata about a specific effect, any attributes that apply to it, the resource affected, etc.

It should be noted that the choice to implement EffectOpInterface for an operation is not based on whether the operation has the effect; but rather, it is based on whether the behavior of the operation with respect to that effect is specified or not.

For example, most operations will have a known effect (or lack thereof) on memory, e.g. arith.add will never have a memory effect, while hir.load by definition will read from memory. In some cases, whether an operation will have such an effect is not a property of the operation itself, but rather operations that may be nested in one of its child regions, e.g. scf.if has no memory effects in and of itself, but one of its regions might contain an operation which does, such as an hir.store in the "then" region. In this case, it does not make sense for scf.if to implement EffectOpInterface<MemoryEffect>, because memory effects are not specified for scf.if, but are instead derived from its regions.

When EffectOpInterface is not implemented for some operation, then one must treat the operation as conservatively as possible in regards to the specific effect. For example, scf.call does not implement this interface for MemoryEffect, because whether the call has any memory effects depends on the function being called. As a result, one must assume that the scf.call could have any possible memory effect, unless you are able to prove otherwise using inter-procedural analysis.

Memory Effects

The infrastructure described above can be used to represent any manner of side effect. However, the compiler is currently only largely concerned with effects on memory. For this, there are a few more specific pieces:

• The MemoryEffectOpInterface trait alias, which is just an alias for EffectOpInterface<MemoryEffect>.
• The MemoryEffect type, which represents the set of memory effects we care about.
• The HasRecursiveMemoryEffects trait, which should be implemented on any operation whose regions may contain operations that have memory effects.
• The Operation::is_memory_effect_free method, which returns a boolean indicating whether the operation is known not to have any memory effects.

In most places, we're largely concerned with whether an operation is known to be memory effect free, thus allowing us to move that operation around freely. We have not started doing more sophisticated effect analysis and optimizations based on such analysis.

Data layout

This document describes how we map data/memory accesses from the byte-addressable address space asssumed by Rust and most (if not virtually all) other languages, to the element-addressable address space of the Miden VM.

The details of this are abstracted away by HIR - so if you are working with Miden from Rust, or some other language that lowers to Miden Assembly via the Miden compiler's intermediate representation (HIR), it is essentially transparent.

However, if you need to integrate handwritten Miden Assembly with, for example, Rust code that has been compiled by midenc, you will want to be aware of some of these details, as they are an intrinsic part of the Application Binary Interface (ABI) of the compiled code.

For most of this document, we'll be using Rust as the source language, and refer to specific details of how it is lowered into HIR via WebAssembly, and how data is laid out in memory from the perspective of Rust/Wasm, and then ultimately mapped to Miden. In general, these details are going to be very similar in other languages, particularly if going through the WebAssembly frontend, but once something is lowered into HIR, the way types are handled is shared across all languages.

Byte-addressable memory and type layout

TODO: Describe how Rust lays out common types in memory, and some of the constraints one needs to be aware of when writing low-level code to access/manipulate those types.

Element-addressable memory and type layout

TODO: Describe the specific methodology used to map the HIR type system to Miden's element-addressable memory.

WebAssembly

TODO: This section will describe details of the core Wasm type system that are relevant here, particularly our reliance on a hack that uses the float32 type to represent field elements efficiently in Rust/Wasm.

Canonical ABI

TODO: This section will describe relevant aspects of the Canonical ABI type system that developers using the Wasm frontend should be aware of.

Analyses

This document provides an overview of some of the current analysis passes the compiler uses when lowering from the frontend to Miden Assembly. This is not guaranteed to be comprehensive, but mostly meant as a high-level reference to what analyses exist and why they are being used.

All analysis passes, at the time of writing, are maintained in the midenc-hir-analysis crate, with the exception of two, which are part of the core midenc-hir crate.

• Dominance
• Loop Forest
• Dead Code
• Sparse Constant Propagation
• Liveness
• Spills

Dominance

Dominance analysis is responsible for computing three data structures commonly used in a compiler operating over a control flow graph in SSA form:

• Dominance tree
• Post-dominance tree
• Iterated dominance frontier

What does dominance refer to in this context? Quite simply, it refers to the relationship between program points in a control flow graph. If all paths to a specific program point $B$, flow through a preceding program point $A$, then it can be said that $A$ dominates $B$. Further, since any program point trivially dominates itself; when $A$ dominates $B$, and $A\ne B$, then $A$ is said to properly dominate $B$. This distinction is occasionally important in the use of the computed dominance analysis.

We're particularly interested in dominance as it pertains to uses and definitions of values of a program in SSA form. SSA, or single-static assignment form, requires that programs adhere to the following properties:

• Values, once defined, are immutable - hence "single-static assignment". To "reassign" a value, you must introduce a new definition representing the changed value. This doesn't account for mutating heap-allocated types where the "value" in SSA is the pointer to the data in memory, it is strictly in reference to what is encoded as an SSA value.
• Uses of a value must always be properly dominated by the definition of that value, i.e. there cannot be any path through the control flow graph that reaches a use of a value, not preceded by its definition.

Dominance analysis is critical for safe transformation of SSA-form programs.

Dominance tree

A dominance tree represents blocks of the CFG as a tree, where the root of the tree is the entry block, and each block in the tree has a single parent, its immediate dominator, and zero or more children for which it is the immediate dominator.

A reverse post-order traversal of the dominance tree is commonly used to visit nodes of the CFG such that each node is only seen once all of its predecessors have been seen, or if control must pass through the node before reaching a non-dominating predecessor (e.g. a loop header must always be passed through before any of its loopback edges).

A dominance tree tells us what blocks control will always pass through to reach any other given block in the CFG.

Post-dominance tree

A post-dominance tree is the inverse of a dominance tree, i.e. $B$ post-dominates $A$, if all paths to the exit node of the CFG starting at $A$, must go through $B$. Accordingly, the immediate post-dominator of $A$ is the post-dominator of $A$ that doesn't strictly post-dominate any other strict post-dominators of $A$.

A post-dominance tree tells us what blocks control will always pass through to reach the exit.

Iterated dominance frontier

The dominance frontier of some node $B$, is the set of all nodes $N$, such that $B$ dominates an immediate predecessor of $N$, but $B$ does not strictly dominate $N$. In other words, it is the set of nodes where $B$'s dominance stops.

The iterated dominance frontier of some node $B$, represents computing the dominance frontier $N$ of $B$, and then the dominance frontiers of all nodes in $N$, recursively.

Iterated dominance frontiers are especially useful when one needs to introduce new definitions of a value, and ensure that all uses of the original value reachable from the new definition, are rewritten to use the new definition. Because uses must be dominated by defs, and the new definition may not strictly dominate all uses, but nevertheless be defined along some path to a use, we may be required to introduce new phi nodes (in HIR, block arguments) that join two or more definitions of a value together at join points in the CFG. The iterated dominance frontier of the new definition tells us all of the blocks where we would need to introduce a new block argument, if there are uses of the value in, or dominated by, that block.

We currently use this in our spills analysis/transformation, in order to do the very thing described above for each reload of a spilled value (which represent new definitions of the spilled value). We want to ensure that uses of the original value reachable from the reload, use the reload instead, thus terminating the live range of the spilled value at the point it is spilled.

Loop Forest

The loop forest represents the set of loops identified in a given CFG, as well as their components:

• Entering blocks (loop predecessor blocks), i.e. non-loop nodes that are predecessors of the loop header. If only one such block exists, it is called the loop pre-header.
• Loop header, i.e. the block which dominates all other loop nodes.
• Latch nodes, i.e. a loop node that has an edge back to the loop header
• Exiting blocks, i.e. blocks which have a successor outside of the loop, but are inside the loop themselves.
• Exit blocks, i.e. a non-loop block which is the successor of an exiting block.

Each block may only be the header for a single loop, and thus you can identify a loop by the header block.

See LLVM Loop Terminology (and Canonical Forms) for a more comprehensive description of how loops are treated analyzed by the compiler, as we base our implementation on LLVM's.

The loop forest can be queried for info about a particular loop, whether a block is part of a loop, and if it is a loop header. The information for a particular loop lets you query what blocks are part of the loop, what their role(s) in the loop are, and the relationship to other loops (i.e. whether the loop is a child of another loop).

We currently do not make heavy use of this, except to attach some loop metadata to nodes during data flow analysis. Since we aim to lift unstructured control flow into structured control flow early during compilation, and this analysis is only defined for unstructured CFGs, it is only pertinent prior to control flow lifting.

Dead Code

The dead code analysis computes the following information about the IR:

• Whether a block is executable, or live.
• The set of known predecessors at certain program points (successors of a control flow op, entry points of a callable region, exit points of a call op), and whether those predecessors are executable.

This is a fundamental analysis in our data flow analysis framework, and it coordinates with the sparse constant propagation analysis to refine its results. We build on this to more precisely compute other analyses based on the liveness of a particular program point, or predecessors to that point.

We do not yet perform dead-code elimination based on this analysis, but likely will do so in the future.

Sparse Constant Propagation

This analysis takes all constant values in a program, and uses that information to attempt determining whether or not uses of those constants that produce new values, may themselves be reduced to constants.

This analysis does not transform the IR, that is done by the sparse conditional constant propagation (SCCP) transform. Instead, it attaches data flow facts to each value derived from an operation that uses a value for which we know a constant value.

This analysis feeds into the dead code analysis, by determining whether or not specific control flow paths are taken when operands to a control flow op have known constant values, e.g. if a scf.if selector is true, then the else region is statically dead.

The SCCP transform mentioned above will actually take the results of the two analyses and rewrite the IR to remove statically unreachable paths, and to fold operations which can be reduced to constants.

Liveness

This analysis computes the liveness, and live range, of every value in the program. This is of crucial importance during code generation, particularly as it relates to management of Miden's operand stack.

Our specific implementation is based on the ideas and algorithms described in Register Spilling and Live-Range Splitting for SSA-form Programs, by Matthias Braun and Sebastian Hack. Specifically, unlike many traditional liveness analysis implementations, we do not track liveness as a boolean state at each program point, but rather in terms of next-use distances. This seemingly small change has some significant benefits: we are able to reason more precisely about how important certain values are at each program point (e.g. should we keep a value in a register/on the operand stack, or can it be spilled to memory to make room for higher priority values); and we are able to quickly assess on entry to a loop, whether the next use of a value occurs within the loop, or after it. This choice of representation of liveness data plays a key role in our spills analysis.

Our liveness analysis also builds on top of the dead code and sparse constant propagation analyses, to avoid considering uses of values along code paths which are statically unreachable/dead. Like those two analyses, it is also implemented on top of our data flow analysis framework.

Spills

The purpose of the spills analysis is to identify programs where we can statically determine that the number of simultaneously-live values would overflow the addressable Miden operand stack, thus requiring us to spill values to memory in order to access values that are in the overflow table. By doing this ahead of time during compilation, we can make smarter choices about what to spill, and when, such that the operand stack never overflows, and potentially expensive spill/reload operations are not emitted in hot code paths, such as loops.

This analysis is tightly integrated with our liveness analysis implementation, particularly the fact that our liveness information is based on next-use distances. Like liveness, it also builds on top of the dead code and sparse constant propagation analyses to avoid considering statically unreachable/dead code paths.

The spills analysis also acts as a register allocator, in that part of how it determines what to spill and when, is by computing the live-in/live-out register sets at each block and operation, along with the set of values in those sets which have been spilled along code paths reaching each program point. We use this information to schedule operands at control flow join points, so that the state of the operand stack is kept consistent on exit from predecessors.

Rewrites

This document provides an overview of some of the current transformation/rewrite passes the compiler uses when lowering from the frontend to Miden Assembly. This is not guaranteed to be comprehensive, but mostly meant as a high-level reference to what rewrites exist and what they acheive.

Most rewrite passes, at the time of writing, are maintained in the midenc-hir-transform crate, with the exception of those which are either dialect-specific (i.e. canonicalization, or reliant on dialect-aware interfaces), or part of the core midenc-hir crate (i.e. region simplification, folding).

• Region Simplification
• Folding
• Canonicalization
• Sparse Conditional Constant Propagation
• Unstructured to Structured Control Flow Lifting
• Control Flow Sinking
• Spills

Region Simplification

Region simplification is a region-local transformation which:

• Removes redundant block arguments
• Merges identical blocks
• Removes unused/dead code

This transformation is exposed from the Region type, but is considered the responsibility of the GreedyPatternRewriteDriver to apply, based on the current compiler configuration.

Folding

Folding, or constant folding to be more precise, is the process by which an operation is simplified, or even reduced to a constant, when some or all of its operands have known constant values.

Operations which can be folded must implement the Foldable trait, and implement the folding logic there. Folds can produce three outcomes, represented via FoldResult:

• Ok, indicating that the operation was able to be reduced to a (possibly constant) value or set of values.
• InPlace, indicating that the operation was able to rewrite itself into a simpler form, but could not be completely folded. This is commonly the case when only a subset of the operands are known-constant.
• Failed, indicating that the operation could not be folded or simplified at all.

Folding can be done at any time, but similar to region simplification, is largely delegated to the GreedyPatternRewriteDriver to apply as part of canonicalization.

Canonicalization

Canonicalization refers to rewriting an operation such that it is in its canonical form. An operation can have several canonicalization patterns that can be applied, some even stack. It must be the case that these canonicalizations converge, i.e. you must never define two separate canonicalizations that could try to rewrite an operation in opposing ways, they must either not overlap, or converge to a fixpoint.

An operation that has at least one defined canonicalization pattern, must implement the Canonicalizable trait, and implement the register_canonicalization_patterns method to insert those rewrite patterns into the provided RewriteSet.

Canonicalization is performed using the Canonicalizer pass, provided by the midenc_hir_transform crate. Internally, this configures and runs the GreedyPatternRewriteDriver to not only apply all canonicalization patterns until fixpoint, but also constant folding and region simplification (depending on configuration).

This is the primary means by which the IR produced by a frontend is simplified and prepared for further transformation by the compiler.

Sparse Conditional Constant Propagation

This pass applies the results of the sparse constant propagation analysis described in Analyses, by rewriting the IR to materialize constant values, replace operations that were reduced to constants, and of particular note, prune unreachable blocks/regions from the IR based on control flow that was resolved to a specific target or set of targets based on constant operands.

Control Flow Lifting

This pass is responsible for converting unstructured control flow, represented via the cf dialect, into structured equivalents provided by the scf dialect.

Because some forms of unstructured control flow cannot be fully converted into structured equivalents, this process is called "lifting" rather than "conversion".

As an example, here's what it looks like to lift an unstructured conditional branch to a scf.if:

• Before:

^block0(v0: i1, v1: u32, v2: u32):
    cf.cond_br v0, ^block1(v1), ^block2(v2);

^block1(v3: u32):
    cf.br ^block3(v3);

^block2(v4: u32):
    v5 = arith.constant 1 : u32;
    v6 = arith.add v4, v5;
    cf.br ^block3(v6);

^block3(v7: u32):
    builtin.ret v7

• After:

v8 = scf.if v0 {
    scf.yield v1
} else {
    v5 = arith.constant 1 : u32;
    v6 = arith.add v2, v5;
    scf.yield v6
};
builtin.ret v8

The above transformation is the simplest possible example. In practice, the transformation is much more involved, as it must handle control flow that exits from arbitrarily deep nesting (e.g. a builtin.ret within the body of a loop, guarded by a conditional branch). The specific details of the transformation in general are described in detail in the module documentation of midenc_hir_transform::cfg_to_scf.

This transformation is a prerequisite for the generation of Miden Assembly, which provides only structured control flow primitives.

Control Flow Sinking

This actually refers to two separate passes, but both are duals of the same goal, which is to move operations closer to their uses, thus reducing the amount of computation that is performed on code paths where the result of that computation is not used.

The ControlFlowSink pass is generic, and will perform the transformation described above, so long as the operation has no side effects, is not a block terminator, and has no regions.

The SinkOperandDefs pass (which will be renamed in the near future), is designed specifically to move constant-like operations directly before their uses, and materialize copies if necessary so that each user gets its own copy. We do this to counter the effect of the control flow lifting transform and the canonicalizer, which both materialize constants in the entry block of a region. These constants then have overly broad live ranges that introduce a high likelihood of needing to spill values to memory. Furthermore, because the Miden VM is a stack machine, not a register machine, there is very little benefit to sharing constant definitions. Instead, by materializing constants immediately before they are used, we produce much more efficient code (as we do not need to shuffle the operand stack to access constants previously defined), and we significantly reduce the chances that we will need to spill values to memory.

Spills

The TransformSpills pass, implemented in midenc_dialect_hir, applies the results of the Spills analysis described in Analyses.

It inserts all of the computed spills and reloads, and fixes up the IR to ensure that all uses of a spilled value, use the closest dominating reload or definition of that value.

The resulting IR is guaranteed to keep the maximum operand stack pressure to 16 elements or less.

Code Generation

Coming soon..

Packaging

This document is coming soon!

Known limitations

The compiler is still in its early stages of development, so there are various features that are unimplemented, or only partially implemented, and the test suite is still limited in scope, so we are still finding bugs on a regular basis. We are rapidly improving this situation, but it is important to be aware of this when using the compiler.

The features discussed below are broken up into sections, to make them easier to navigate and reference.

Rust language support

Floating point types

• Status: Unsupported
• Tracking Issue: N/A
• Release Milestone: N/A

In order to represent Felt "natively" in Rust, we were forced to piggy-back on the f32 type, which is propagated through to WebAssembly, and allows us to handle those values specially.

As a result, floating-point types in Rust are not supported at all. Any attempt to use them will result in a compilation error. We considered this a fair design tradeoff, as floating point math is unused/rare in the context in which Miden is used, in comparison to fixed-point or field arithmetic. In addition, implementing floating-point operations in software on the Miden VM would be extraordinarily expensive, which generally works against the purpose for using floats in the first place.

At this point in time, we have no plans to support floats, but this may change if we are able to find a better/more natural representation for Felt in WebAssembly.

Function call indirection

• Status: Unimplemented
• Tracking Issue: #32
• Release Milestone: Beta 1

This feature corresponds to call_indirect in WebAssembly, and is associated with Rust features such as trait objects (which use indirection to call trait methods), and closures. Note that the Rust compiler is able to erase the indirection associated with certain abstractions statically in some cases, shown below. If Rust is unable to statically resolve all call targets, then midenc will raise an error when it encounters any use of call_indirect.

Iterator lowered to loop

#![allow(unused)]
fn main() {
pub fn is_zeroed(bytes: &[u8; 32]) -> bool {
    // Rust is able to convert this to a loop, erasing the closure completely
    bytes.iter().copied().all(|b| b == 0)
}
}

Monomorphization + inlining

pub fn call<F, T>(fun: F) -> T
where
    F: Fn() -> T,
{
    fun()
}

#[inline(never)]
pub fn foo() -> bool { true }

fn main() {
    // Rust is able to inline the body of `call` after monomorphization, which results in
    // the call to `foo` being resolved statically.
    call(foo)
}

Inlined trait impl

pub trait Foo {
    fn is_foo(&self) -> bool;
}

impl Foo for u32 {
    #[inline(never)]
    fn is_foo(&self) -> bool { true }
}

fn has_foo(items: &[dyn Foo]) -> bool {
    items.iter().any(|item| item.is_foo())
}

fn main() -> u32 {
    // Rust inlines `has_foo`, converts the iterator chain to a loop, and is able to realize
    // that the `dyn Foo` items are actually `u32`, and resolves the call to `is_foo` to
    // `<u32 as Foo>::is_foo`.
    let foo: &dyn Foo = &u32::MAX as &dyn Foo;
    has_foo(&[foo]) as u32
}

Miden SDK

• Status: Incomplete
• Tracking Issue: #159 and #158
• Release Milestone: Beta 1

The Miden SDK for Rust, is a Rust crate that provides the implementation of native Miden types, as well as bindings to the Miden standard library and transaction kernel APIs.

Currently, only a very limited subset of the API surface has had bindings implemented. This means that there is a fair amount of native Miden functionality that is not yet available from Rust. We will be expanding the SDK rapidly over the next few weeks and months, but for the time being, if you encounter a missing API that you need, let us know, so we can ensure it is prioritized above APIs which are lesser used.

Rust/Miden FFI (foreign function interface) and interop

• Status: Internal Use Only
• Tracking Issue: #304
• Release Milestone: TBD

While the compiler has functionality to link against native Miden Assembly libraries, binding against procedures exported from those libraries from Rust can require glue code to be emitted by the compiler in some cases, and the set of procedures for which this is done is currently restricted to a hardcoded whitelist of known Miden procedures.

This affects any procedure which returns a type larger than u32 (excluding Felt, which for this purpose has the same size). For example, returing a Miden Word from a procedure, a common return type, is not compatible with Rust's ABI - it will attempt to generate code which allocates stack space in the caller, which it expects the callee to write to, inserting a new parameter at the start of the parameter list, and expecting nothing to be returned by value. The compiler handles situations like these using a set of ABI "transformation strategies", which lift/lower differences between the Rust and Miden ABIs at call boundaries.

To expose the FFI machinery for use with any Miden procedure, we need type signatures for those procedures at a minimum, and in some cases we may require details of the calling convention/ABI. This metadata does not currently exist, but is on the roadmap for inclusion into Miden Assembly and Miden packaging. Once present, we can open up the FFI for general use.

Core Miden functionality

Dynamic procedure invocation

• Status: Unimplemented
• Tracking Issue: #32
• Release Milestone: Beta 1

This is a dependency of Function Call Indirection described above, and is the mechanism by which we can perform indirect calls in Miden. In order to implement support for indirect calls in the Wasm frontend, we need underlying support for dynexec, which is not yet implemented.

This feature adds support for lowering indirect calls to dynexec or dyncall instructions, depending on the ABI of the callee. dyncall has an additional dependency on support for Cross-Context Procedure Invocation.

A known issue with this feature is that dyn(exec|call) consumes a word on the operand stack for the hash of the callee being invoked, but this word remains on the stack when entering the callee, which has the effect of requiring procedures to have a different ABI depending on whether they expect to be dynamically-invoked or not.

Our solution to that issue is to generate stubs which are used as the target of dyn(exec|call), the body of which drop the callee hash, fix up the operand stack as necessary, and then uses a simple exec or call to invoke the "real" callee. We will emit a single stub for every function which has its "address" taken, and use the hash of the stub in place of the actual callee hash.

Cross-context procedure invocation

• Status: Unimplemented
• Tracking Issue: #303
• Release Milestone: Beta 2

This is required in order to support representing Miden accounts and note scripts in Rust, and compilation to Miden Assembly.

Currently, you can write code in Rust that is very close to how accounts and note scripts will look like in the language, but it is not possible to actually implement either of those in Rust today. The reasons for this are covered in depth in the tracking issue linked above, but to briefly summarize, the primary issue has to do with the fact that Rust programs are compiled for a "shared-everything" environment, i.e. you can pass references to memory from caller to callee, write to caller memory from the callee, etc. In Miden however, contexts are "shared-nothing" units of isolation, and thus cross-context operations, such as performing a call from a note script to a method on an account, are not compatible with the usual calling conventions used by Rust and LLVM.

The solution to this relies on compiling the Rust code for the wasm32-wasip2 target, which emits a new kind of WebAssembly module, known as a component. These components adhere to the rules of the WebAssembly Component Model. Of primary interest to us, is the fact that components in this model are "shared-nothing", and the ABI used to communicate across component boundaries, is specially designed to enforce shared-nothing semantics on caller and callee. In addition to compiling for a specific Wasm target, we also rely on some additional tooling for describing component interfaces, types, and to generate Rust bindings for those descriptions, to ensure that calls across the boundary remain opaque, even to the linker, which ensures that the assumptions of the caller and callee with regard to what address space they operate in are preserved (i.e. a callee can never be inlined into the caller, and thus end up executing in the caller's context rather than the expected callee context).

This is one of our top priorities, as it is critical to being able to use Rust to compile code for the Miden rollup, but it is also the most complex feature on our roadmap, hence why it is scheduled for our Beta 2 milestone, rather than Beta 1 (the next release), as it depends on multiple other subfeatures being implemented first.

Packaging

Package format

• Status: Experimental
• Tracking Issue: #121
• Release Milestone: Beta 1

This feature represents the ability to compile and distribute a single artifact that contains the compiled MAST, and all required and optional metadata to make linking against, and executing packages as convenient as a dynamic library or executable.

The compiler currently produces, by default, an experimental implementation of a package format that meets the minimum requirements to support libraries and programs compiled from Rust:

• Name and semantic version information
• Content digest
• The compiled MAST and metadata about the procedures exported from it
• Read-only data segments and their hashes (if needed by the program, used to load data into the advice provider when a program is loaded, and to write those segments into linear memory when the program starts)
• Dependency information (optional, specifies what libraries were linked against during compilation)
• Debug information (optional)

However, this package format is not yet understood by the Miden VM itself. This means you cannot, currently, compile a package and then run it using miden run directly. Instead, you can use midenc run to load and run code from a package, as the compiler ships with the VM embedded for use with the interactive debugger, and provides native support for packaging on top of it. You can also use midenc debug to execute your program interactively in the debugger, depending on your needs. See Debugging Programs for more information on how to use the debugger, and midenc help run for more information on executing programs with the midenc run command.

While it is possible to emit raw MAST from midenc, rather than the experimental package format, the resulting artifact cannot be run without some fragile and error-prone manual setup, in order to ensure that the advice provider is correctly initialized with any read-only data segments. For now, it is recommended that you use the midenc tooling for testing programs, until the format is stabilized.

Calling conventions

This document describes the various calling conventions recognized/handled by the compiler, including a specification for the interaction with the IR type system.

There are four calling conventions represented in the compiler:

• C aka SystemV, which corresponds to the C ABI commonly used for C foreign-function interfaces (FFI). We specifically use the System V ABI because it is well understood, documented, and straightforward.
• Fast, this convention allows the compiler to follow either the C calling convention, or modify it as it sees fit on a function-by-function basis. This convention provides no guarantees about how a callee will expect arguments to be passed, so should not be used for functions which are expected to have a stable, predictable interface. This is a good choice for local functions, or functions which are only used within an executable/library and are not part of the public interface.
• Kernel, this is a special calling convention that is used when defining kernel modules in the IR. Functions which are part of the kernel's public API are required to use this convention, and it is not possible to call a function via syscall if the callee is not defined with this convention. Because of the semantics of syscall, this convention is highly restrictive. In particular, it is not permitted to pass pointer arguments, or aggregates containing pointers, as syscall involves a context switch, and thus memory in the caller is not accessible to the callee, and vice versa.
• Contract, this is a special calling convention that is used when defining smart contract functions, i.e. functions that can be call'd. The compiler will not permit you to call a function if the callee is not defined with this convention, and functions with this convention cannot be called via exec. Like syscall, the call instruction involves a context switch, however, unlike the Kernel convention, the Contract convention is allowed to have types in its signature that are/contain pointers, with certain caveats around those pointers.

All four conventions above are based on the System V C ABI, tailored to the Miden VM. The only exception is Fast, which may modify the ABI arbitrarily as it sees fit, and makes no guarantees about what modifications, if any, it will make.

Data representation

The following is a description of how the IR type system is represented in the C calling convention. Later, a description of how the other conventions extend/restrict/modify this representation will be provided.

Scalars

The native scalar type for the Miden VM is a "field element", specifically a 64-bit value representing an integer in the "Goldilocks" field, i.e. 0..(2^64-2^32+1). A number of instructions in the VM operate on field elements directly. However, the native integral/pointer type, i.e. a "machine word", is actually u32. This is because a field element can fully represent 32-bit integers, but not the full 64-bit integer range. Values of u32 type are valid field element values, and can be used anywhere that a field element is expected (barring other constraints).

Miden also has the notion of a "word", not to be confused with a "machine word" (by which we mean the native integral type used to represent pointers), which corresponds to a set of 4 field elements. Words are commonly used in Miden, particularly to represent hashes, and a number of VM instructions operate on word-sized operands. As an aside, 128-bit integer values are represented using a word, or two 64-bit limbs (each limb consisting of two 32-bit limbs).

All integral types mentioned above, barring field elements, use two's complement encoding. Unsigned integral types make use of the sign bit to change the value range (i.e. 0..2^32-1, rather than -2^31..2^31-1), but the encoding follows two's complement rules.

The Miden VM only has native support for field elements, words, and u32; all other types are implemented in software using intrinsics.

Aggregates and unions

Structures and unions assume the alignment of their most strictly aligned component. Each member is assigned to the lowest available offset with the appropriate alignment. The size of any object is always a multiple of the object's alignment. An array uses the same alignment as its elements. Structure and union objects can require padding to meet size and alignment constraints. The contents of any padding is undefined.

Memory model

Interacting with memory in Miden is quite similar to WebAssembly in some ways:

• The address space is linear, with addresses starting at zero, and ranging up to 2^32-1
• There is no memory protection per se, you either have full read/write access, or no access to a specific memory context
• How memory is used is completely up to the program being executed

This is where it begins to differ though, and takes on qualities unique to Miden (in part, or whole):

• Certain regions of the address space are "reserved" for special uses, improper use of those regions may result in undefined behavior.
• Miden has different types of function call instructions: call vs syscall vs exec. The first two perform a context switch when transferring control to the callee, and the callee has no access to the caller's memory (and the caller has no access to the callee's memory). As a result, references to memory cannot be passed from caller to callee in arguments, nor can they be returned from the callee to the caller.
• Most significant of all though, is that Miden does not have byte-addressable memory, it is instead word-addressable, i.e. every address refers to a full word.
• It is not possible to load a specific field element from a word in memory, unless it happens to be the first element of the word. Instead, one must load the full word, and drop the elements you don't need.

This presents some complications, particularly:

• Most languages assume a byte-oriented memory model, which is not trivially mapped to a word-oriented model
• Simple things, such as taking the address of a field in a struct, and then dereferencing it, cannot be directly represented in Miden using native pointer arithmetic and load instruction. Operations like this must be translated into instruction sequences that load whole words from memory, extract the data needed, and discard the unused bits. This makes the choice of where in memory to store something much more important than byte-addressable memory, as loads of values which are not aligned to element or word boundaries can be quite inefficient in some cases.

The compiler solves this by providing a byte-addressable IR, and internally translating operations in the IR to the equivalent sequence of Miden instructions needed to emulate that operation. This translation is done during code generation, and uses the following semantics to determine how a particular operation gets lowered:

• A byte-addressable pointer can be emulated in Miden's word-addressable environment using three pieces of information:
  • The address of the word containing the first byte of the value, this is a "native" Miden address value
  • The index of the field element within that word containing the first byte of the value
  • The offset (in bytes) from the start of the 4 byte chunk represented by the selected element, corresponding to the first byte of the value. Since the chunk is represented as a u32 value, the offset is relative to the most-significant bit (i.e. the byte with the lowest address is found in bits 55-63, since Miden integers are little-endian)
• This relies on us treating Miden's linear memory as an array of 16-byte chunks of raw memory (each word is 4 field elements, each element represents a 4-byte chunk). In short, much like translating a virtual memory address to a physical one, we must translate byte-addressable "virtual" pointers to "real" Miden pointers with enough metadata to be able to extract the data we're trying to load (or encode the data we're trying to store).

Because we're essentially emulating byte-addressable memory on word-addressable memory, loads/stores can range from simple and straightforward, to expensive and complicated, depending on the size and alignment of the value type. The process goes as follows:

• If the value type is word-aligned, it can be loaded/stored in as little as a single instruction depending on the size of the type
• Likewise if the value type is element-aligned, and the address is word-aligned
• Element-aligned values require some extra instructions to load a full word and drop the unused elements (or in the case of stores, loading the full word and replacing the element being stored)
• Loads/stores of types with sub-element alignment depend on the alignment of the pointer itself. Element or word-aligned addresses are still quite efficient to load/store from, but if the first byte of the value occurs in the middle of an element, then the bytes of that value must be shifted into place (or unused bytes masked out). If the value crosses an element boundary, then the bytes in both elements must be isolated and shifted into position such that they can be bitwise-OR'd together to obtain the aligned value on the operand stack. If a value crosses a word boundary, then elements from both words must be loaded, irrelevant ones discarded, the relevant bytes isolated and shifted into position so that the resulting operand on the stack is aligned and laid out correctly.
• Stores are further complicated by the need to preserve memory that is not being explicitly written to, so values that do not overwrite a full word or element, require combining bytes from the operand being stored and what currently resides in memory.

The worst case scenario for an unaligned load or store involves a word-sized type starting somewhere in the last element of the first word. This will require loading elements from three consecutive words, plus a lot of shuffling bits around to get the final, aligned word-sized value on the operand stack. Luckily, such operations should be quite rare, as by default all word-sized scalar types are word-aligned or element-aligned, so an unaligned load or store would require either a packed struct, or a type such as an array of bytes starting at some arbitrary address. In practice, most loads/stores are likely to be element-aligned, so most overhead from emulation will come from values which cross an element or word boundary.

Function calls

This section describes the conventions followed when executing a function call via exec, including how arguments are passed on the operand stack, stack frames, etc. Later, we'll cover the differences when executing calls via call or syscall.

Locals and the stack frame

Miden does not have registers in the style of hardware architectures. Instead it has an operand stack, on which an arbitrary number of operands may be stored, and local variables. In both cases - an operand on the operand stack, or a single local variable - the value type is nominally a field element, but it is easier to reason about them as untyped element-sized values. The operand stack is used for function arguments, return values, temporary variables, and scratch space. Local variables are not always used, but are typically used to hold multiply-used values which you don't want to keep on the operand stack, function-scoped automatic allocations (i.e. alloca), and other such uses.

Miden does not have a stack frame per se. When you call a procedure in Miden Assembly, any local variables declared by that procedure are allocated space in a reserved region of linear memory in a single consecutive chunk. However, there is no stack or frame pointer, and because Miden is a Harvard architecture machine, there are no return addresses. Instead, languages (such as C) which have the concept of a stack frame with implications for the semantics of say, taking the address of a local variable, will need to emit code in function prologues and epilogues to maintain a shadow stack in Miden's linear memory. If all you need is local variables, you can get away with leaning on Miden's notion of local variables without implementing a shadow stack.

Because there are no registers, the notion of callee-saved or caller-saved registers does not have a direct equivalent in Miden. However, in its place, a somewhat equivalent set of rules defines the contract between caller and callee in terms of the state of the operand stack, those are described below in the section covering the operand stack.

The shadow stack

Miden is a Harvard architecture; as such, code and data are not in the same memory space. More precisely, in Miden, code is only addressable via the hash of the MAST root of that code, which must correspond to code that has been loaded into the VM. The hash of the MAST root of a function can be used to call that function both directly and indirectly, but that is the only action you can take with it. Code can not be generated and called on the fly, and it is not stored anywhere that is accessible to code that is currently executing.

One consequence of this is that there are no return addresses or instruction pointers visible to executing code. The runtime call stack is managed by the VM itself, and is not exposed to executing code in any way. This means that address-taken local C variables need to be on a separate stack in linear memory (which we refer to as a "shadow stack"). Not all functions necessarily require a frame in the shadow stack, as it cannot be used to perform unwinding, so only functions which have locals require a frame.

The Miden VM actually provides some built-in support for stack frames when using Miden Assembly. Procedures which are declared with some number of locals, will be automatically allocated sufficient space for those locals in a reserved region of linear memory when called. If you use the locaddr instruction to get the actual address of a local, that address can be passed as an argument to callees (within the constraints of the callee's calling convention).

Languages with more elaborate requirements with regard to the stack will need to implement their own shadow stack, and emit code in function prologues/epilogues to manage it.

The operand stack

The Miden virtual machine is a stack machine, not a register machine. Rather than having a fixed set of registers that are used to store and manipulate scalar values, the Miden VM has the operand stack, which can hold an arbitrary number of operands (where each operand is a single field element), of which the first 16 can be directly manipulated using special stack instructions. The operand stack is, as the name implies, a last-in/first-out data structure.

The following are basic rules all conventions are expected to follow with regard to the operand stack:

1. The state of the operand stack from the point of view of the caller should be preserved, with two exceptions:

• The callee is expected to consume all of its arguments, and the caller will expect those operands to be gone when control is returned to it
• If the callee signature declares a return value, the caller expects to see that on top of the stack when control is returned to it

2. No more than 16 elements of the operand stack may be used for passing arguments. If more than that is required to represent all of the arguments, then one of the following must happen:

• Spill to stack frame: in this scenario, up to 15 elements of the operand stack are used for arguments, and the remaining element is used to hold a pointer to a local variable in the caller's stack frame. That local variable is a struct whose fields are the spilled arguments, appearing in the same order as they would be passed. The callee must use the pointer it is given to compute the effective address for each spilled argument that it wishes to access.
• Spill to heap: this is basically identical to the approach above, except the memory is allocated from the global heap, rather than using memory associated with the caller's stack frame.
• Spill to the advice provider: in this scenario, 12 elements of the stack are used for arguments, and the remaining 4 are used to hold a hash which refers to the remaining arguments on the advice provider stack. The callee must arrange to fetch the spilled arguments from the advice provider using that hash.

Function signatures

Miden Abstract Syntax Trees (MASTs) do not have any notion of functions, and as such are not aware of parameters, return values, etc. For this document, that's not a useful level of abstraction to examine. Even a step higher, Miden Assembly (MASM) has functions (procedures in MASM parlance), but no function signature, i.e. given a MASM procedure, there is no way to know how many arguments it expects, how many values it returns, let alone the types of arguments/return values. Instead, we're going to specify calling conventions in terms of Miden IR, which has a fairly expressive type system more or less equivalent to that of LLVM, and how that translates to Miden primitives.

Functions in Miden IR always have a signature, which specify the following:

• The calling convention required to call the function
• The number and types of the function arguments
• The type of value, if any, returned by the function, and whether it is returned by value or reference

The following table relates IR types to how they are expected to be passed from the caller to the callee, and vice versa:

The compiler will automatically generate code that follows these rules, but if emitting MASM from your own backend, it is necessary to do so manually. For example, a function whose signature specifies that it returns a non-scalar struct by value, must actually be written such that it expects to receive a pointer to memory allocated by the caller sufficient to hold the return value, as the first parameter of the function (i.e. the parameter is prepended to the parameter list). When returning, the function must write the return value to that pointer, rather than returning it on the operand stack. In this example, the return value is returned indirectly (by reference).

A universal rule is that the arguments are passed in reverse order, i.e. the first argument in the parameter list of a function will be on top of the operand stack. This is different than many Miden instructions which seemingly use the opposite convention, e.g. add, which expects the right-hand operand on top of the stack, so a + b is represented like push a, push b, add. If we were to implement add as a function, it would instead be push b, push a, exec.add. The rationale behind this is that, in general, the more frequently used arguments appear earlier in the parameter list, and thus we want those closer to the top of the operand stack to reduce the amount of stack manipulation we need to do.

Arguments/return values are laid out on the operand stack just like they would be as if you had just loaded it from memory, so all arguments are aligned, but may span multiple operands on the operand stack as necessary based on the size of the type (i.e. a struct type that contains a u32 and a i1 field would require two operands to represent). If the maximum number of operands allowed for the call is reached, any remaining arguments must be spilled to the caller's stack frame, or to the advice provider. The former is used in the case of exec/dynexec, while the latter is used for call and syscall, as caller memory is not accessible to the callee with those instructions.

While ostensibly 16 elements is the maximum number of operands on the operand stack that can represent function arguments, due to the way dynexec/dyncall work, it is actually limited to 12 elements, because at least 4 must be free to hold the hash of the function being indirectly called.

1. i32 is not a native Miden type, but is implemented using compiler intrinsics on top of the native u32 type ↩ ↩2 ↩3 ↩4

2. An enum is i32 if all members of the enumeration can be represented by an int/unsigned int, otherwise it uses i64. ↩

3. i64 is not a native Miden type, but is implemented using compiler intrinsics on top of the stdlib u64 type ↩ ↩2

4. u64 is not a native Miden type, but is implemented in software using two 32-bit limbs (i.e. a pair of field elements) ↩

5. Miden's linear memory is word-addressable, not byte-addressable. The Ptr type has an AddressSpace parameter, that by default is set to the byte-addressable address space. The compiler translates values of Ptr type that are in this address space, into the Miden-native, word-addressable address space during codegen of load/store operations. See the section on the memory model below for more details. ↩

6. floating-point types are not currently supported, but will be implemented using compiler intrinsics ↩ ↩2

7. long double values correspond to 128-bit IEEE-754 quad-precision binary128 values. These are not currently supported, and we have no plans to support them in the near term. Should we ever provide such support, we will do so using compiler intrinsics. ↩

Canonical ABI vs Miden ABI incompatibility

Summary

The gist of the problem is that in Miden, the size and number of procedure results is only constrained by the maximum addressable operand stack depth. In most programming languages, particularly those in which interop is typically performed using some variant of the C ABI (commonly the one described in the System V specification), the number of results is almost always limited to a single result, and the size of the result type is almost always limited to the size of a single machine word, in some cases two. On these platforms, procedure results of greater arity or size are typically handled by reserving space in the caller's stack frame, and implicitly prepending the parameter list of the callee with an extra parameter: a pointer to the memory allocated for the return value. The callee will directly write the return value via this pointer, instead of returning a value in a register.

In the case of Rust, this means that attempting to represent a procedure that returns multiple values, or returns a larger-than-machine-word type, such as Word, will trigger the implicit transformation described above, as this is allowed by the standard Rust calling conventions. Since various Miden procedures that are part of the standard library and the transaction kernel are affected by this, the question becomes "how do we define bindings for these procedures in Rust?".

The solution is to have the compiler emit glue code that closes the gap between the two ABIs. It does so by generating adapter functions, which wrap functions that have an ABI unrepresentable in Rust, and orchestrate lifting/lowering arguments and results between the adapter and the "real" function.

When type signatures are available for all Miden Assembly procedures, we can completely automate this process. For now, we will require a manually curated list of known procedures, their signatures, and the strategy used to "adapt" those procedures for binding in Rust.

Background

After analyzing all of the functions in the transaction kernel API, the most common cause of a mismatch between Miden and Rust ABIs, is due to implicit "sret" parameters, i.e. the transformation mentioned above which inserts an implicit pointer to the caller's stack frame for the callee to write the return value to, rather than doing so in a register (or in our case, on the operand stack). This seems to happen for any type that is larger than 8 bytes (i64).

For most transaction kernel functions, the adapter function can be generated automatically using the pattern recognition and adapter functions described below.

Prerequisites

• The compiler must know the type signature for any function we wish to apply the adapter strategy to

Implementation

The compiler will analyze every component import to determine if that import requires an adapter, as determined by matching against a predefined set of patterns. The adapter generation will take place in the frontend, as it has access to all of the needed information, and ensures that we do not have any transformations or analyses that make decisions on the un-adapted procedure.

The following pseudo-code can be used to recognize the various Miden ABI patterns:

#![allow(unused)]
fn main() {
pub enum MidenAbiPattern {
    /// Calling this procedure will require an sret parameter on the Rust side, so
    /// we need to emit an adapter that will lift/lower calls according to that
    /// strategy.
    ReturnViaPointer,
    /// The underlying procedure is fully representable in Rust, and requires no adaptation.
    NoAdapterNeeded,
}

pub struct MidenAbiPatternRecognition {
    pattern: Option<MidenAbiPattern>,
    component_function: ComponentFunctionType,
    wasm_core_func: Signature,
    tx_kernel_function: Signature,
}

pub fn recognize_miden_abi_pattern(
    component_function: &ComponentFunctionType,
    wasm_core_func: &Signature,
    tx_kernel_func: &Signature) -> MidenAbiPatternRecognition {
    if wasm_core_func == tx_kernel_func {
        return MidenAbiPatternRecognition {
            pattern: Some(NoAdapterNeeded),
            component_function,
            wasm_core_function,
            tx_kernel_function,
        };
    } else if component_function.returns[0].byte_size > 8 && wasm_core_func.params.last() == I32 {
        return MidenAbiPatternRecognition {
            pattern: Some(ReturnViaPointer),
            component_function,
            wasm_core_function,
            tx_kernel_function,
        };
    } else {
        return MidenAbiPatternRecognition {
            pattern: None,
            component_function,
            wasm_core_function,
            tx_kernel_function,
        };
    }
}
}

The following pseudo-code can then be used to generate the adapter function:

#![allow(unused)]
fn main() {
pub fn generate_adapter(recognition: MidenAbiPatternRecognition) {
    match recognition.pattern {
        Some(pattern) => generate_adapter(
            pattern,
            recognition.component_function,
            recognition.wasm_core_function,
            recognition.tx_kernel_function
        ),
        None => use_manual_adapter(
            recognition.component_function,
            recognition.wasm_core_function,
            recognition.tx_kernel_function
        ),
    }
}

/// Escape hatch for the cases when the compiler can't generate an adapter function automatically
/// and we need to provide the adapter function manually.
pub fn use_manual_adapter(...) {
    // Find and use the manual adapter in the adapter library for the tx_kernel_function
}
}

The manual adapter library is a collection of adapter functions that are used when the compiler can't generate an adapter function automatically so its expected to be provided. The manual adapter library is a part of the Miden compiler. It is not anticipated that we will have many, or any, of these; however in the near term we are going to manually map procedures to their adapter strategies, as we have not yet automated the pattern recognition step.

Return-via-pointer adapter

The return value is expected to be returned by storing its flattened representation in a pointer passed as an argument.

Recognize this Miden ABI pattern by looking at the Wasm component function type. If the return value is bigger than 64 bits, expect the last argument in the Wasm core(HIR) signature to be i32 (a pointer).

The adapter function calls the tx kernel function and stores the result in the provided pointer (the last argument of the Wasm core function).

Here is the pseudo-code for generating the adapter function for the return-via-pointer Miden ABI pattern:

#![allow(unused)]
fn main() {
let ptr = wasm_core_function.params.last();
let adapter_function = FunctionBuilder::new(wasm_core_function.clone());
let tx_kernel_function_params = wasm_core_function.params.drop_last();
let tx_kernel_func_val = adapter_function.call(tx_kernel_function, tx_kernel_function_params);
adapter_function.store(tx_kernel_func_val, ptr);
adapter_function.build();
}

Here is how the adapter might look like in a pseudo-code for the add_asset function:

/// Takes an Asset as an argument and returns a new Asset
func wasm_core_add_asset(v0: f64, v1: f64, v2: f64, v3: f64, ptr: i32) {
    v4 = call tx_kernel_add_asset(v0, v1, v2, v3);
    // v4 is a tuple of 4 f64 values
    store v4 in ptr;
}

No-op adapter

No adapter is needed. The Wasm core function type is the same as the tx kernel ad-hoc signature.

This Miden ABI pattern is selected if no other Miden ABI pattern is applicable and the wasm core function signature is the same as the tx kernel ad-hoc signature.

For example, the get_id function falls under this Miden ABI pattern and its calls will be translated to the tx kernel function calls without any modifications.

Transaction kernel functions that require manual adapter functions

get_assets

get_assets:func() -> list<core-asset> in the note interface is the only function that requires attention. In Canonical ABI, any function that returns a dynamic list of items needs to allocate memory in the caller's module due to the shared-nothing nature of the Wasm component model. For this case, a realloc function is passed as a part of lift/lower Canonical ABI options for the caller to allocate memory in the caller's module.

Here are the signatures of the get_assets function in the WIT, core Wasm, and the tx kernel ad-hoc ABI: Comment from the miden-base

#! Writes the assets of the currently executing note into memory starting at the specified address.
#!
#! Inputs: [dest_ptr]
#! Outputs: [num_assets, dest_ptr]
#!
#! - dest_ptr is the memory address to write the assets.
#! - num_assets is the number of assets in the currently executing note.

Wasm component function type: get-assets: func() -> list<core-asset>;

Wasm core signature: wasm_core_get_assets(i32) -> ()

If we add a new get_assets_count: func() -> u32; function to the tx kernel and add the assets count parameter to the get_assets function (get_assets: func(assets_count: u32) -> list<core-asset>;) we should have everything we need to manually write the adapter function for the get_assets function.

The list is expected to be returned by storing the pointer to its first item in a ptr pointer passed as an argument and item count at ptr + 4 bytes address (ptr points to two pointers).

We could try to recognize this Miden ABI pattern by looking at the Wasm component function type. If the return value is a list, expect the last argument in the Wasm core(HIR) signature to be i32 (a pointer). The problem is recognizing the list count parameter in the Wasm core(HIR) signature.

The adapter function calls allocates asset_count * item_size memory via the realloc call and passes the pointer to the newly allocated memory to the tx kernel function.

Here is how the adapter function might look like in a pseudo-code for the get_assets function:

#![allow(unused)]
fn main() {
func wasm_core_get_assets(asset_count: u32, ptr_ptr: i32) {
    mem_size = asset_count * item_size;
    ptr = realloc(mem_size);
    (actual_asset_count, ptr) = call tx_kernel_get_assets(ptr);
    assert(actual_asset_count == asset_count);
    store ptr in ptr_ptr;
    store account_count in ptr_ptr + 4;
}
}

The example of some functions signatures

add_asset (return-via-pointer Miden ABI pattern)

Comment from the miden-base

#! Add the specified asset to the vault.
#!
#! Panics:
#! - If the asset is not valid.
#! - If the total value of two fungible assets is greater than or equal to 2^63.
#! - If the vault already contains the same non-fungible asset.
#!
#! Stack: [ASSET]
#! Output: [ASSET']
#!
#! - ASSET' final asset in the account vault is defined as follows:
#!   - If ASSET is a non-fungible asset, then ASSET' is the same as ASSET.
#!   - If ASSET is a fungible asset, then ASSET' is the total fungible asset in the account vault
#!     after ASSET was added to it.

Wasm component function type: add-asset(core-asset) -> core-asset

Wasm core signature: wasm_core_add_asset(f64, f64, f64, f64, i32) -> () The last i32 is a pointer to a returned value (word)

Tx kernel ad-hoc signature: tx_kernel_add_asset(felt, felt, felt, felt) -> (felt, felt, felt, felt)

get_id (no-adapter-needed Miden ABI pattern)

Comment from the miden-base

#! Returns the account id.
#!
#! Stack: []
#! Output: [acct_id]
#!
#! - acct_id is the account id.

Wasm component function type: get-id() -> account-id

Wasm core signature: wasm_core_get_id() -> f64

Tx kernel ad-hoc signature: tx_kernel_get_id() -> felt