← Tutorials / docs

MIR Documentation

The MIR is a "classical" Control Flow Graph (CFG) in Static Single Assignment (SSA) form. The main purpose of the MIR is to reduce copies and ensure heap allocations don't not leak memory. To achieve those objectives the MIR has a Borrowing System.

The MIR Borrowing System

  • There are 3 memory types in the MIR: Vectors, Closures and Tuples. Each SSA definition that is of memory type is either Owned or Borrowed.

  • Many operations in the MIR can consume some of their inputs. In many places where operations can consume their inputs an implicit copy of the input is created if the input is not consumed (for example vecwrite).

  • An input can only be consumed if it is Owned and has no (live) Borrowers.

  • Owned values need to be consumed or dropped (within a function).

SSA Definitions and Uses

  • SSA Values use integers as identifiers. These integers are unique within each function (SSA...).
  • Both definitions and uses are written like: %n where n is the integer identifier.
  • Definitions of memory type have a o for owned or b for borrowed appended ie. %0o or %1b.
  • Uses of memory type have a ! appended if they are consumed ie. %2!
  • Uses of memory type have a c appended if they are copied ie. %3c

Types

The following types exist:

  • unit is the unit type
  • i32 is a 32 bit wide integer
  • i8 is a 8 bit wide integer
  • a*b*... is a tuple type with elements of type a, type b, ...
  • clos(a,b,...->x) is the closure type of a function taking arguments of type a, type b, ... and returning type x
  • vec<d,it> is the vector type for a d dimensional vector with inner type it, where it can be i32 or i8

Globals

global @g<globalid>: <globaltype>

Where

  • <globalid> is a unique integer identifier
  • <globaltype> is the type of the global

Functions

Functions have the following format

fn <rettyp> @<funcid> "<funcname>" (<argtyp> <ssadef> "<argname>", ...) { ... }

Where:

  • <rettyp> is the return type of the function
  • <funcid> is the unique integer identifying the function
  • <funcname> is the function name used for readability only
  • <argtyp> is the type of the following argument
  • <ssadef> is the SSA definition of a function argument
  • <argname> is an optional argument name used for readability only
  • The ... after first argument should signify that other arguments can follow (comma separated)
  • { ... } contains the function body

Basic Blocks

The function body contains a list of basic blocks (bb). The first bb in this list is the entry (where the function starts executing). A bb has the following format

bb<bbid> "<bbname>" (<ssadef>, ...):
    <oplist>
    <term>

Where:

  • <bbid> is a unique integer identifying the bb
  • <bbname> is a bb name used for readability only
  • <ssadef> is the SSA definition of a bb argument
  • The ... after first argument should signify that other arguments can follow (comma separated)
  • <oplist> is a list of operations executed from top to bottom
  • <term> is a terminator

The MIR uses bb arguments rather than Phi-nodes. bb arguments are conceptually similar to placing phi nodes at the top of a bb.

Terminators

There are 3 terminators:

  • ret <ssause> returns the value of <ssause>. If the return value is of memory type ret must consume it.
  • br bb<targetbbid>(<ssauselist>) branches to bb <targetbbid> passing the bb arguments in <ssauselist> (space separated). bb arguments of memory type that are defined as owned must be consumed by br.
  • cbr <condssause> bb<truebbid> bb<falsebbid> branches to bb <truebbid> if <condssause> (must be i32) does evaluate to non zero and to bb <falsebbid> otherwise.

Operations

  • %res = func @funcid @allownedfuncid creates closure.
  • %res = pack %oldclos %arg0 %arg1 ... adds an input/argument to a closure.
  • %res = callclosure %clos calls the closure. If %clos is consumed a version of the function with all memory type arguments as owned is called otherwise one with all borrowed.
  • %res = calldirect @funcid %arg0 %arg1 ... calls a function. If an argument of memory type is consumed it need to be passed/considered as owned in the callee otherwise as borrowed.
  • %res = copy %val creates a new ssa value that is identical (a copy...) but owned.
  • drop %mem0 %mem1 ... drops all supplied ssa values.
  • storeglobal @gid %val stores %val in global @gid. Consumes or copies %val.
  • %res = loadglobal @gid load from global @gid. If the global is of memory type, %res is borrowed.
  • dropglobal @gid drops the value stored in global @gid.
  • %res = immi32 1234 immediate for i32 type
  • %res = immi8 123 immediate for i8 type
  • %res = immunit immediate for unit type
  • %res = uopi32 arg %a uop for i32
  • %res = uopi8 arg %a uop for i8
  • %res = bopi32 arg %a %b bop for i32
  • %res = bopi8 arg %a %b bop for i8
  • %res = tupwrp %elm0 %elm1 ... create a tuple form %elm0 %elm1 .... %res is owned and %elm0 %elm1 ... are consumed or copied (if they are of memory type)
  • %elm0, ... = tupborr %tup borrow elements %elm0, ... from tuple %tup. Elements %elm0, ... are borrowed.
  • %elm0, ... = tupuwrp %tup extract elements %elm0, ... from tuple %tup. Elements %elm0, ... are owned.
  • %res = veclit %elm0 %elm1 ... create a vector with the literals %elm0 %elm1 ....
    • %elm0 %elm1 ... are consumed or copied if they are of memory type.
    • %res is owned
  • %res = vecinit %lit <dimsizelst> initialize a vector.
    • <dimsizelst> needs to be a non empty list of i32 ssa values.
    • The 1-D case with a single element %dim in <dimsizelst> creates a vector of length %dim with %lit stored at every index.
    • The N-D case with a leftmost element %dim and rest <dimsizetail> of <dimsizelst> is recursively defined as a vector of length %dim with the result vecinit %lit <dimsizetail> stored at every index ((N-1)-D case).
    • If %lit has memory type it is copied (produce of <dimsizelst> times)
  • %res = veclen %vec get the length of a vector
    • %res has type i32
  • %res = vecread %vec <idxlst> reads form a vector.
    • <idxlst> needs to be a list of i32 ssa values.
    • The n-th index in <idxlst> is used to index the n-th dimension of %vec.
    • <idxlst> can be empty but it can't have more elements than %vec has dimensions.
    • If %res is a memory type (must be a vector if so) it borrows from %vec.
  • %res = vecwrite %vec %val <idxlst> create new vector based on %vec by changing the value of one "inner" element (i32 or i8).
    • <idxlst> needs to be a list of i32 ssa values with one element for each dimension of %vec.
    • The n-th index in <idxlst> is used to index the n-th dimension of %vec. %val needs to be a i32 or i8 depending on %vec's "inner" type.
    • %vec is copied or consumed.
    • %res is owned.
  • %res = vecinsert %vec %vecins <idxlst> create new vector based on %vec by inserting %vecins.
    • <idxlst> needs to be a list of i32 ssa values with less elements that %vec has dimensions.
    • The n-th index in <idxlst> is used to index the n-th dimension of %vec.
    • %vecins needs to be a vector with the same "inner type" as %vec.
    • The sum of %vecins's dimensionality plus the number of indexes in <idxlst> must equal %vec's dimensionality.
    • %vec and %vecins are each copied or consumed.
    • %res is owned.
  • %res = vecslice %vec %start %len slice vector %vec
    • %start %len need to have type i32.
    • %res starts at offset %start into %vec.
    • %res has length %len.
    • %res borrows from %vec.
  • %res = vecextend %vec %lit %off create extended vector based on %vec.
    • %vec %lit %off need to have type i32.
    • If off is positive, %lit is appended %off times.
    • If off is negative, %lit is prepended minus %off times.
    • Copies %vec.
    • %res is owned.

Notes and Edge Cases

Note the MIR has logical memory types. For example a tuple consisting of two i32 values does not actually have a heap allocation, but because tuples can have elements that are heap allocated they do count as logical memory types.

Intlang playground — write, compile, and run in the browser