Design the Memory Representation (Initial)

[ktemkin]

Description

LLVM’s assumption of R/W memory and registers does not fit with the memory model used by the Cairo VM. We can either take the SSA form and treat the target as an infinite-register machine, or we can emulate R/W memory directly.

For this initial design phase we want to do the bare minimum to get mostly-correct semantics as far as the LLVM IR expects. This task includes designing the assignment model and the semantics of the operations on pointers.

[iamrecursion]

To add a bit more information to this:

• Cairo VM uses write-once memory.
• The conventional way to represent R/W memory cells on top of this is to use an array.
• Arrays nested in arrays could provide something more like a conventional "memory".
• On top of that, we also need to support explicit notions of:
  • Allocation
  • Deallocation
  • Pointer arithmetic
  • And so on (anything you can do with memory in C, really)
• We also need to contend with how wide our pointers are, and other things like that. Until we define our own target this should probably match our target.

[wzmuda]

LLVM Memory Model Meeting Notes

How to perform pointer operations without compromising performance while adhering to the read-only Cairo memory model.

Based on @Eagle941's notes taken live during today's meeting.

Problem breakdown

Allocator for Stack Memory

• Heap Memory is not a significant issue; need to implement the alloc method to return an address.
• CRT0 initializes data, const, bss using llvm_guest_pointer.
• Certain pointers, like those returning a flag, don't need support. In theory LLVM wouldn’t return a pointer, but it can be possible.

Virtual to Physical Allocation

• We need a mechanism that resembles a virtual address space in an operating system with an MMU table to track addresses.
• Unclear what wrappers are needed to implement the MMU.

Allocator

• Given no deallocation, it's feasible to use a linear allocator, moving the pointer forward as space is required.
• Variables allocated with malloc are not initialized automatically.
• Written variables can't be reused.
• If char array is being copied and possibly its usable data would fit a felt, it wouldn't because a single char already occupies the space of a felt.
• Are elements byte-addressable or felt-addressable? We're going to assume everything is aligned to a felt.
• Heap allocator is not managed by LLVM.
• We can be inspired by the Rust default allocator.

MMU

• 1st approach can be a simple dict as provided by Cairo. It's a naive solution with possible performance implications, probably good for the start.
  • For dict hashing we'd like to have a good hash function, but we can't for performance reasons. Simple hashing may lead to collisions. Solution: a list of indices search in case of a collision.
  • Cairo memory is immutable, so must be the dict. Writing an element involves a linear walk through the dict (and the list of indices added as collision prevention) to find the current value for the given key.
• Use read_addr and write_addr to interface with the LLVM model.
• Future Optimization: Use further indirection, possibly a page table storing arrays of arrays.

LLVM Instructions

- Wojtek's comment: are we sure about this? I don't see them in the langref.

• alloc, dealloc, alloc_zero, and realloc.
• Allocate gives a type instead of size. We need to trace back what the required space is for the given type. The consequence is that we first need to have a mapping between llvm types and size. To start with, we could say that each type less than felt, takes a whole felt. Otherwise they take multiple felts.

Allocation

• With Initialization: Write the element immediately.
• Without Initialization: Reserve the address but leave it unused for future writing (e.g., space for user input).
• Page table needs to have a flag for allocated, but not written.
• Load and store operations involve converting structs to felts.
• We may need to be able to support array of structs and to be able to access a specific set of bytes. We could also have structs of structs.
• All operations are effectively atomic.
• Added in a flo instead of a polyfill no-op. Initially unnecessary, but useful for future optimizations.

TODO

1. Develop our target descriptor and pass it to rustc.
2. Ensure the compiler checks against the target descriptor.
3. Write the expected memory interface for the compiler to use polyfills.
4. Write the memory model.
5. Handle overcommitting.

[iamrecursion]

Something that might be interesting is the cairo-riscv project's allocator, thanks to Ariel!