﻿ Cairo Compiler Learning Notes – DOFY's Blog

# 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



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


DOFY's Blog

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 +…

2022-06-02