Cairo Compiler Learning Notes

Excerpts from How Cairo Works

Introduction to Cairo

Registers

ap: allocation pointer
fp: frame pointer
pc: program counter

Basic instructions

[fp - 1] = [ap - 2] + [fp + 4]
[ap - 1] = [fp + 10] * [ap]; ap++
[ap - 1] = [fp + 10] + 12345; ap++  # See (a) below.
[fp + 2] = [ap + 5]
[fp + 2] = 12345
[ap + 2] = [[ap + 5]]  # See (b) below.
[ap] = [fp - 3] - [ap + 4]  # See (c) below.
[ap] = [fp - 3] / [ap + 4]  # See (c) below.

The program counter (pc)

The program is stored in memory, where each instruction takes 1 or 2 field elements.

Conditional jumps

jmp rel 17 if [ap - 1] != 0)

Consts and references

Consts

const value = 1234
[ap] = value

is equivalent to

[ap] = 1234

Short string literals

[ap] = 'hello'

References

# Set value of x.
let x = ap
[x] = 3; ap++

[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++
[ap] = [ap - 1] * [ap - 1]; ap++

[ap] = [ap - 1] + [x]; ap++

the compiler replaces the first occurrence of by [ap] and the second by [ap - 5].

The assert statement and compound expressions

let x = [ap - 1]
let y = [ap - 2]
assert x * x = x + 5 * y

One should avoid using ap and fp directly in such expressions.

Revoked references

If there is a label or a call instruction between the definition of a reference that depends on ap and its usage, the reference may be revoked.

It is the same that using reference depending on fp outside of the scope of the function may result in an undefined behavior.

Typed references

struct MyStruct:
    member x : felt
    member y : felt
    member z : felt
end

let ptr : MyStruct* = cast([fp], MyStruct*)
assert ptr.y = 10

Temporary variables

tempvar var_name = <expr>

For simple expressions, with at most one operation, this is equivalent to:

[ap] = <expr>; ap++
let var_name = [ap - 1]

If <expr> is a compound expressions, more than one Cairo instruction will be compiled.

Local variables

Local variables are based on fp.

func main():
    ap += SIZEOF_LOCALS
    local x  # x will be a reference to [fp + 0].
    local y  # y will be a reference to [fp + 1].

    x = 5
    y = 7
    ret
end

Typed local variables

local x : T* = <expr>
local y : T = <expr>

x.a is equivalent to [[fp + 0] + T.a].

y.a is equivalent to [fp + 1 + T.a].

Tuples

assert (x, y) = (1, 2)

is equivalent to

assert x = 1
assert y = 2

Functions

call and ret

call addr is roughly equivalent to:

# Stores the value of the current fp, which will be
# restored once the called function ends using ret.
[ap] <-- fp

# Stores the address of the next instruction, to run
# once the called function ends. This will be
# assigned to pc when ret is invoked.
[ap + 1] <-- return_pc

# Increase ap by 2, to account for the last two writes.
ap += 2

# Updates fp to be the new ap, so it points to the start
# of the new frame within the called function's scope.
fp <-- ap

jmp addr

ret is roughly equivalent to:

# Jumps to return_pc (stored on the stack).
jmp [fp - 1]

# Restores the value of the previous fp.
fp <-- [fp - 2]

Bouns Exercise

Write a piece of code that when executed puts the current values of ap, fp and pc in memory (say, write ap into [ap], fp into [ap + 1] and pc into [ap + 2]).

func main():
    tempvar qaq = 1000
    ap += 3
    call f1
    [ap - 7] = [ap - 2] - 5
    [ap - 6] = [ap - 4]
    [ap - 5] = [ap - 3] - 4
    ret 
end
func f1():
    call f2
    ret
end
func f2():
    ret
end

Accessing the values of the registers

Using library functions:

from starkware.cairo.common.registers import get_ap
from starkware.cairo.common.registers import get_fp_and_pc

let get_ap_res = get_ap()
tempvar my_ap = get_ap_res.ap_val

let fp_and_pc = get_fp_and_pc()
tempvar my_fp = fp_and_pc.fp_val
tempvar my_pc = fp_and_pc.pc_val

Cairo compiler will replace fp in a compound expression with __fp__. For example, line B requires line A in order to compile.

local __fp__ = fp_and_pc.fp_val  # A.
tempvar x = fp  # B.
tempvar y = [fp]  # C.

Function arguments and return values

Arguments

Any usage of the reference argname is replaced by [fp - (2 + n_args) + Args.argname].

For example, to call foo(4, 5) you should write:

[ap] = 4; ap++  # x.
[ap] = 5; ap++  # y.
call foo

Return values

foo(x=4, y=5)
[ap] = [ap - 1] + [ap - 2]; ap++  # Compute z + w.

Return values unpacking:

let (z, w) = foo(x=4, y=5)
[ap] = z + w; ap++

Unpack as local variable:

let (local z, local w) = foo(x=4, y=5)
[ap] = z + w; ap++

Named arguments

let args = cast(ap, foo.Args*)
args.x = 4; ap++
args.y = 5; ap++
# Check that ap was advanced the correct number of times
# (this will ensure arguments were not forgotten).
static_assert args + foo.Args.SIZE == ap
let foo_ret = call foo

Return tuple

func foo() -> (a, b):
    return (<expr0>, b=<expr1>)
end

is equivalent to

func foo() -> (a, b):
    [ap] = <expr0>; ap++
    [ap] = <expr1>; ap++
    ret
end

Types

Used-defined type aliases

using Point = (x : felt, y : felt)

Object allocation

The alloc() function allocates a new memory segment.

let (struct_array : MyStruct*) = alloc()

The new operator creates the object in the execution segment.

tempvar ptr : MyStruct* = new MyStruct(a=1, b=2)

Scope attributes

with_attr attribute_name("Attribute value"):
    # Code block.
end

At present, only one attribute is supported by the Cairo runner: error_message.

Hints

A hint is a block of Python code, that will be executed by the prover right before the next instruction.

[ap] = 25; ap++
%{
    import math
    memory[ap] = int(math.sqrt(memory[ap - 1]))
%}
[ap - 1] = [ap] * [ap]; ap++

Note that a hint is attached to the next instruction and executed before each execution of the corresponding instruction.

Program input & output

A Cairo program may have a secret input (called “program input”) and a public output (called “program output”).

Segments

During the run of the Cairo VM, it’s useful to treat the memory as a list of continuous segments, which are concatenated to form one continuous chunk at the end of the run, when their final sizes can be calculated.

• program segment
• execution segment

Nondeterministic jumps

Nondeterminisitic jumps is a code pattern that combines conditional jumps and hints.

%{
    memory[ap] = 1 if x > 10 else 0
%}
jmp label if [ap] != 0; ap++

Builtins and implicit arguments

%builtins pedersen

from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2


func f3(hash_ptr : HashBuiltin*, x, y, z) -> (
    hash_ptr : HashBuiltin*, res
):
    alloc_locals
    let hash = hash_ptr
    hash.x = x
    hash.y = y 
    local tmp = hash.result

    let hash_ptr = hash_ptr + HashBuiltin.SIZE
    let hash = hash_ptr
    hash.x = tmp
    hash.y = z
    let hash_ptr = hash_ptr + HashBuiltin.SIZE
    return (hash_ptr = hash_ptr, res = hash.result)
end

# func f3_{hash_ptr : HashBuiltin*}(x, y, z) -> (res):
#     let (tmp) = hash2(x, y)
#     let (res) = hash2(tmp, z)
#     return (res = res)
# end

func main{pedersen_ptr : HashBuiltin*}():
    # let (res) = f3_{hash_ptr=pedersen_ptr}(1, 2, 3)
    let (pedersen_ptr, res) = f3(pedersen_ptr, 1, 2, 3)
    return ()
end