###### tags: `Technical Notes` # memIR This is a work in progress. An IR to improve memory handling of Solidity. ## Goals - Reuse memory. - Remove redundant memory use. - Use identity precompile for copies. - Minimize msize. - Avoid free memory pointer whenever possible. - Use code for storing static data and copy them to memory. ## Design - No direct memory access opcodes. ## Example ```solidity interface ERC20 { function transferFrom(address from, address to, uint amount) external returns (uint); } contract C { ERC20 immutable token; address immutable from; function do_transfer(address to, uint amount) external returns (uint) { // need some authorization. return token.transferFrom(from, to, amount); } } ``` Would be translated to ``` // A builtin let freeMemPtr := allocateFreeMemoryPtr() // encode high level call "token.transferFrom(...)" // staticallyAllocate is a builtin let x := staticallyAllocate(100) staticStore(x, 0, 4, selector) staticStore(x, 4, 32, from) staticStore(x, 36, 32, to) staticStore(x, 68, 32, amount) let y := staticallyAllocate(32) // Q: should we include length offsets of x and y here? let success := call(gas(), token, x, y) if lt(returndatasize(), 32) { panic() } calldatacopy(y, 0) ``` ## Translation - `staticallyAllocate(len)` would be replaced by a literal `offset` during the translation to pure Yul. - There needs to be zeroing `calldatacopy(offset, calldatasize(), len)`. Ultimately need to figure out when zeroing can be avoided. - Understand when two variables can have conflicts. In the above example, x and y can have the same offsets. Can be smart about when to avoid cleanup v/s pay the price of memory expansion. In the above example, both x and y can have value 0. Better syntax for conflict management? ``` let success := call(gas(), token, x) let y := staticallyallocate(32) // But the translation can be smart about rewriting the call to use // y and 32. calldatacopy(y, 0) ``` ## Implementation - Can gradually move from Yul to mem-IR. Any solidity contract that has a direct memory access is "unimplemented feature". - Similar to how Yul was implemented, gradually move features. # Yul with types and borrow checker by @chriseth this proposal looks good, but I would at least consider going some steps further: Add proper memory types and references to Yul and add a borrow checker like in rust. Of course this high level yul would be translated to low level yul after the optimization. Storage is still handled as before because we do not need clever allocation and we do not expect it to be used as much as memory (because it is expensive). It might be easy to do this for storage as well. This is a very early draft. We migt want to think about making the type system compatible with sonatina. ``` // The types are: // bool, uint, mem&, memmut&, memmut&mut&, ... // (anything matching the regex mem((mut)?&)+ // // There is one allocation function per nesting depth. // The borrow checker performs lifetime tracking and ensures // the same or similar properties as the rust borrow checker // and thus we can ensure that there is no aliasing for memory writes. let x:memmut& := allocate_memmut&(100) // We can create memory slices, but we could also directly use // memory write opcodes with offsets and lengths. let sel:memmut& := mslice(x, 0, 4) // Here, sel is a mutable reference to a part of x. // This means as long as sel is alive, it "blocks" any access to x. // Not sure yet what happens if we write to a slice that is shorter // than 32 bytes mstore(sel, selector) // At this point sel goes out of scope, so we can access x again. // mslice performs bounds checking. mstore(mslice(x, 4, 32), from) mstore(mslice(x, 4, 32), to) mstore(mslice(x, 4, 32), amount) let y: memmut& := allocate_memmut&(32) let success := call(gas(), token, x, y) if lt(returndatasize(), 32) { panic() } calldatacopy(y, 0) ``` Ideas: Maybe we can avoid the use of "unbounded allocation" altogether. This is mainly a problem in the abi encoder. We should check if iterative allocations and memory moves could be optimized by the compiler to a single allocation. The other way would be to first determine the length and then do the encoding. Problem: If the type only models the depth, we might get a problem with structs - do we use the deepest type by members? We could use types of the form ``(v[],v)`` for a ``struct S { uint[] a, uint b }`` ## Tasks of the Borrow Checker: - references are not used before they are assigned - moved-from variables are not used after they were moved from - For all references to a varialbe, at any time, at most one of them can be mutable. - If there is at least one active reference to a variable, it cannot be mutated. ## Random notes: A non-value type is always owned by exactly one variable. If the variable goes out of scope and still owns something (it was not moved out of it), that something can be deallocated. Question: Do array objects store their length and do we do bounds checking or are they more or less just pointers? - It is probably easier to do no bounds checking by the builtins and instead just treat objects as pointers. - If we include the length implicitly and introduce slicing functions, the signature of most builtin functions gets much shorter. In the worst case, we could store the length on the stack. - We cannot store the length in memory because slices would not work then. - This means length actually cannot be implicit because implicit length does not work for multi-dimensional arrays. So maybe: Use pointers as basic types and use slices (pointer plus length) as convenience types on top? The borrow checker probably does not perform offset analysis anyway. When calling functions, do we need to actively create references using a ref keyword or function or is it automatic? - return variables cannot be assigned at declaration. Also it is weird to declare them as mut (because it is irrelevant in the signature), so maybe always make them non-mut (we can declare a local mut variable in the worst case) We allow references to all types and do not specify if data is stored on the stack or in memory. On the implementation side, passing a mutable reference to a value type to a function means that the value needs to be copied to memory. ## Very Open Question: How compatible are the existing optimizer rules (ssa transform, etc) with the borrow checker? Maybe it's not such a big deal because non-ssa variables are 'mut' anyway? Need to check! Most other steps should actually be fine! Note that mutable references (and actually all non-value types) cannot be copied, but only moved. How does this relate to lifetimes/lifetime annotations? ## Open Question: Yoshi asks if we can have struct members of reference types. Chris thinks this is probably not needed, but maybe we need them if we use tuples to pass around data / for variadic functions. - This would change the semantics of multi-dimensional arrays in Solidity a lot. Can we move data easily like in `x[i] = y`, where `y` is an array? - Is "mutable" part of the type or the variable? - Can we do `copy_byte[](slice_mut(x, 0, 10), slice(x, 10, 10))`? - Somehow it would be nice to be able to define named structs - can we do that? - Is it possible to mix reference-checked-and-typed yul and current yul? What can the optimizer still do? -> [mixed-yul]](#Mixed-Yul) - How are fixed-size arrays modeled? Do we need them? Can we reason that the length is never accessed and the allocator optimizes it away? - Dereferencing is actually more complicated. We need it both on the LHS and on the RHS. - It turns out that in rust, reading from a deref always copies, so deref can be a simple function that returns a copy by value (and only works on non-complex types). On the LHS we can use a generic `assign` function. ## Spec Types: `bool`, `byte`, `word`, `(T, ...)`, `T[]`, `T&`, `T.mut&` We do not specify if data is stored in memory or on the stack. We probably need a syntax for lifetime annotations like in rust. In contrast to rust, there is no dereferencing operation to use as lvalue, we need a builtin function for that. Assignments are always move-assignments, except for value types. Builtin functions: ```yul // for all T - even value types? function ref(x: T'a) -> T&'a function mutref(x: T'a) -> T.mut&'a // for all value types T - maybe this could be automatic? function deref(x: T&) -> T // for all T - if T is an array itself, its size is zero function new_T[](size: uint) -> result: T[] // Is this needed or can we just declare a variable of this type? function new_T1_..._Tn() -> result: (T1, ..., Tn) function index(x: T[]&'a, i: uint) -> result: T&'a function index_mut(x: T[].mut&'a, i: uint) -> result: T.mut&'a function slice_uint(x: byte[].mut&'a) -> result: uint.mut&'a // TODO we should be able to abstract away if x is on stack or in memory function mstore_uint(x: uint.mut&, v: uint) function mstore_word(x: word.mut&, v: word) function mstore_byte(x: byte.mut&, v: byte) // TODO do we want a new type for slices? function slice(x: T[]&'a, start: uint, length: uint) -> T[]&'a function slice_mut(x: T[].mut&'a, start: uint, length: uint) -> T[].mut&'a // TODO might be better with slices function copy_byte[](dest: byte[].mut&, offset: uint, from: byte[]&, length: uint) // Slice version function copy_byte[](dest: byte[].mut&, from: byte[]&) // for all i up to size of the struct // TODO the lifetime does not need to be bound to the full struct... function member_i(x: (T1, ..., Tn)&'a) -> result: Ti&'a function member_mut_i(x: (T1, ..., Tn).mut&'a) -> result: Ti.mut&'a // Whether or not length() reads from memory or if the length is // stored on the stack is opaque to this version of yul. function length_T[](x: T[]&) -> r: uint function datacopy_new(start: uint, length: uint) -> result: byte[] function datacopy(target: byte[].mut&, offset: uint, length: uint) function calldatacopy(target: byte[].mut&, offset: uint, length: uint) function return(data: byte[]&) function revert(data: byte[]&) // TODO can we do this with memory references, i.e. // slice_uint(buffer: byte[] mut&'a, offset: uint) -> result: uint.mut& // and // assign(uint.mut& x, uint y)? function mstore_uint(buffer: byte[] mut&, offset: uint, value: uint) function log0(data: byte[]&) function log1(data: byte[]&, topic0: uint) function log2(data: byte[]&, topic0: uint, topic1: uint) function log3(data: byte[]&, topic0: uint, topic1: uint, topic2: uint) function keccak256(data: byte[]&) -> word ... ``` ## Benchmarks In the following code, the creation code is first copied to memory and then copied again for `encodePacked`. Can we avoid the second copy with the new mechanism? Does it also work if the arguments to `encodePacked` are reversed? ``` uint arg = ...; bytes32 digest = keccak256( abi.encodePacked( type(ERC20).creationCode, abi.encode(arg) ) ); ``` Could be translated to: ```rust let arg: uint := ... let code: byte[] := new_byte[](original_len) codecopy(mutref(code), 0, original_len) let args_encoded: byte[] := abi_encode_uint(arg) let buf: byte[] := concatenate(ref(code), ref(args_encoded)) let digest: word := keccak256(ref(buf)) function abi_encode_uint(x: uint) -> r: byte[] { // TODO is r mutable? // General: Are return variables mutable? Or do they support // only one assignment? In the worst case, we can move // from a mutable local variable. r := new_byte[](32) let s: uint[].mut& := slice_uint(ref(r), 0) mstore_uint(s, x) } function concatenate(a: byte[]&, b: byte[]&) -> r: byte[] { let len: uint := add(length(a), length(b)) r := new_byte[](len) copy_byte[](slice_mut(mutref(r), 0, length(a)), a) copy_byte[](slice_mut(mutref(r), length(a), length(b)), b) } ``` After inlining, we get: ```rust let arg: uint := ... let code: byte[] := new_byte[](original_len) codecopy(mutref(code), 0, original_len) // abi_encode() let args_encoded: byte[] := new_byte[](32) let s: uint[].mut& := slice_uint(ref(args_encoded), 0) mstore_uint(s, arg) // concatenate() let len: uint := add(length(ref(code)), length(ref(args_encoded))) let buf: byte[] := new_byte[](len) copy_byte[](slice_mut(mutref(buf), 0, length(code)), ref(code)) copy_byte[]( slice_mut(mutref(buf), length(code), length(ref(args_encoded))), ref(args_encoded) ) let digest: word := keccak256(ref(buf)) ``` Extracting all the lengths and introducing temporary variables for slices: ```rust let arg: uint := ... let code_len: uint := original_len let code: byte[] := new_byte[](code_len) codecopy(mutref(code), 0, code_len) // abi_encode() let args_encoded: byte[] := new_byte[](32) let args_len: uint := 32 let s: uint[].mut& := slice_uint(ref(args_encoded), 0) mstore_uint(s, arg) // concatenate() let len: uint := add(code_len, args_len) let buf: byte[] := new_byte[](len) let first_slice: byte[].mut& := slice_mut(mutref(buf), 0, code_len) copy_byte[](first_slice, ref(code)) let second_slice: byte[].mut& := slice_mut(mutref(buf), code_len, args_len) copy_byte[](second_slice, ref(args_encoded)) let digest: word := keccak256(ref(buf)) ``` Now it's obvious that the only use of `code` is in the first copy of `concatenate`. This mean we can replace `copy_byte[](first_slice, ref(code))` by `codecopy(first_slice, 0, code_len)` This can actually always be done because it is not more expensive! Now, `code` is unused and can be removed, which removes the allocation and the copy. ## Some Examples ERC20: https://gist.github.com/chriseth/df0f4c1220abe7c653a242b0a9beb67f The example above: ``` // Allocate a 100 byte memory object. The function returns // "by value" and not a "real" reference, // the resulting value is moved. In reality, // arrays are of course implemented using pointers and what // is moved is ownership, it does not actually move the data. let x: byte[] := allocate_byte[](100) // mstore_word stores a full word and takes a mutable reference // to the object. While this function is executing, // access to x is blocked, but access is possible again after it returns. mstore_word(x, 0, shl(selector, 28)) // We can create a slice (not really required, but good for illustration) let dataPart: byte[].mut& := slice(x, 4) // Now we have an active mutable reference to x. // The fact that is in an active mutable reference to x // (and not just something else) is apparent from the lifetime // annotations of the function slice: // function slice(in: bytes[].mut&'a, offset: uint) -> bytes[].mut&'a // - it returns something whose lifetimes is bound to the lifetime // of the first parameter (because of the identical strings "a") mstore_word(dataPart, 0, from) // Question: Can we create a new slice of dataPart here and write to it? // Should these be two active mutable references to the same object? // Or is it OK because now we have a mutable reference to dataPart // instead of x? mstore_word(slice(dataPart, 0x20), 0, to) mstore_word(dataPart, 0x60, amount) // The lifetime of dataPart ends here, so we can write to x again directly. let y: byte[] := allocate_byte[](32) // Call takes x by non-mutable reference and y by mutable reference. let success := call(gas(), token, x, y) if lt(returndatasize(), 32) { panic() } calldatacopy(y, 0) ``` ## Sonatina Types essentially exactly the llvm types i8, ..., i256 bool tuples of types: (i64, i64) arrays of types pointers of types ## How are lengths of arrays handled? Problem: We want dynamically-sized arrays. For code simplicity, it would be nice to allow dynamically-sized arrays and slices, so that we don't need "offset" and "length" parameters all the time. What is the most basic type we need to define that we can then build on top? It looks like rust essentially only has "unsafe pointer" to build dynamically-sized arrays on top. I fear that this means that the allocator needs to be implemented, which would not work well with our optimizer. We want the allocator to be a language feature/compile-time feature so that the optimizer can work with it. How does rust solve ownership for raw pointers? -> not clear how... We could work with "raw arrays" that have a structure, but not a length. You can allocate them with `new_T[](size)`, which allocates and initializes, but the length is not accessible after that. If we want to store the length, we need to define a new struct - this would be nice to be generic (but does not have to be, it can be pseudo-generic / generated). `type array_T = (length: uint, data: T[])` Because of move semantics, the length would not be stored with the data (as in solidity), but `data` would be a pointer and we have another indirection. This is good because length could be stored on the stack for temporary data, but it is bad for nested arrays. The other option would be to have two types: An array that has the length stored and a slice. Maybe making slices a language feature would not be such a bad idea, because they appear everywhere. Arrays are `T[]` and store the length together with the data. Slices are `T[:]`, are invalid as a non-borrowed type and thus only store a pointer and a length. Since they are invalid as a non-borrowed type, they currently cannot be members in structs or elements of an array. ## Spec Types: - `Elementary: bool, byte, word` - `Complex: (T1, ..., Tn), T[], T` for `T, T1, ..., Tn Elementary or Complex` - `Slices: T[:]&, T[:].mut&` for `T Elementary or Complex` - `References: T&, T.mut&` for `T Elementary or Complex` We do not specify if data is stored in memory or on the stack. We probably need a syntax for lifetime annotations like in rust. In contrast to rust, there is no dereferencing operation to use as lvalue, we need a builtin function for that. Assignments are always move-assignments, except for value types. Arrays store their length somewhere and cannot be resized. Slices only exist as references. References cannot be used inside complex types. For now we require all ref/mutref/deref calls to be explicit. In the future, some of them could be omitted. Builtin functions (in progress): ```yul // for all complex T function ref(x: T'a) -> T&'a function mutref(x: T'a) -> T.mut&'a // for all value types T - maybe this could be automatic? function deref(x: T&) -> T // This can be used to move from struct members / assign to struct members // and array elements. It swaps the contents of the references, not the // pointers themselves. If the pointers point at a pointer, the pointers // pointed to are swapped. Because of that, lifetimes do not need // to be specially considered (the ownership of the pointers do not change). // In C++ it would be `swap(*x, *y)`. function swap(x: T.mut&, y: T.mut&) // for all elementary and complex T - if T is an array itself, its size is zero function new_T[](size: uint) -> result: T[] // Is this needed or can we just declare a variable of this type? function new_T1_..._Tn() -> result: (T1, ..., Tn) function index(x: T[]&'a, i: uint) -> result: T&'a function index_mut(x: T[].mut&'a, i: uint) -> result: T.mut&'a function slice_uint(x: byte[].mut&'a) -> result: uint.mut&'a // For all elementary or complex T // TOOD still need to find out if swap or assign is more elementary. function assign_T(x: T.mut&, v: T) function slice(x: T[]&'a, start: uint, length: uint) -> T[:]&'a function slice_mut(x: T[].mut&'a, start: uint, length: uint) -> T[:].mut&'a function copy_T(dest: T[:].mut&, from: T[:]&) // for all i up to size of the struct // TODO the lifetime does not need to be bound to the full struct... function member_i(x: (T1, ..., Tn)&'a) -> result: Ti&'a function member_mut_i(x: (T1, ..., Tn).mut&'a) -> result: Ti.mut&'a // Whether or not length() reads from memory or if the length is // stored on the stack is opaque to this version of yul. function length_T[](x: T[]&) -> r: uint function length_T[:](x: T[:]&) -> r: uint function datacopy_new(start: uint, length: uint) -> result: byte[] function datacopy(target: byte[:].mut&, offset: uint, length: uint) function calldatacopy(target: byte[:].mut&, offset: uint, length: uint) function return(data: byte[:]&) function revert(data: byte[:]&) function log0(data: byte[:]&) function log1(data: byte[:]&, topic0: uint) function log2(data: byte[:]&, topic0: uint, topic1: uint) function log3(data: byte[:]&, topic0: uint, topic1: uint, topic2: uint) function keccak256(data: byte[:]&) -> word ... ``` ### Helper functions ```yul function assign_T(x: T.mut&, y: T) { // TODO this does not work if T is a value type // because we cannot take mut refs of value types swap(x, mutref(y)) } ``` ### Example translations Daniel: I think the comment below is actually an issue, especially if the second reference is supposed to become impossible both on solidity *and* even on Yul level. It's not like we're targetting a normal system in which memory is abundant and copies are cheap. I think we have to assume that we need to cater to the ability for any kind of "weird" manual memory compression. I don't think life-time tracking has a hard dependency on this either, even though it would need some other carefully defined restrictions then. ```solidity uint[][] memory x = new uint[][](20); x[0] = new uint[](3); x[0][1] = 7; // It was possible to assign a second reference // in the past, now we need to copy. x[1] = copy x[0]; ``` Translation: ```yul let x: uint[][] := new_uint[][](20) let x_0: uint[].mut& := index_mut_uint[][](mutref(x), 0) assign(x_0, new_uint[](3)) let x_0_1: uint.mut& := index_mut_uint[](x_0, 1) assign(x_0_1, 7) let x_1: uint[].mut& := index_mut_uint[][](mutref(x), 1) // TODO this won't really work, we need to evaluate the RHS // before the LHS assign(x_1, array_copy(new_uint[](3)) ``` If we change the above to not have a copy (and evaluate the RHS before the LHS), we get: ```yul ... let x_0: uint[]& := index_uint[][](ref(x), 0) let x_1: uint[].mut& := index_mut_uint[][](mutref(x), 1) assign(x_1, x_0) ``` ### Code for copies from storage/calldata to memory and vice-versa for struct with array `struct X { uint[10] a; uint[] b; uint c; }` #### Copy from storage to memory Will model fixed-size arrays using dynamic arrays for now. It wastes one word in memory, but apart from that is compatible with Solidity's memory layout. ```rust function copy_struct_S_from_storage(ptr: word) -> r: (uint[],uint[],uint) { // maybe need to find a better syntax for complex types // in function names. // could even maybe introduce named types. r := new_uint[],uint[],uint() let a: uint[].mut& := member_mut_0(mutref(r)) // TODO mstore_uint[](x, f()) is the equivalent of `*x = f()` in rust/C++. // maybe we DO want to have a syntax for assigning to a dereferenced // reference? // `a := ...` is something else, it just changes the pointer // on the stack. mstore_uint[](a, copy_uint_array_from_storage(ptr, 10)) // a is not used below this line, so the mut ref to r is released. ptr := add(ptr, 10) let b: uint[].mut& := member_mut_1(mutref(r)) mstore_uint[](b, read_uint[]_storage(ptr)) ptr := add(ptr, 1) let c: uint.mut& := member_mut_2(mutref(r)) mstore_uint(c, read_uint_storage(ptr)) } // Copy a dynamically-sized uint array from storage to memory function read_uint[]_storage(sptr: word) -> r: uint[] { let len: uint := read_uint_storage(sptr) let dataArea: word := wordHash(sptr) r := copy_uint_array_from_storage(dataArea, len) } function copy_uint_array_from_storage(data_area: word, len: uint) -> arr: uint[] { arr := new_uint[](len) for { let i: uint := 0 } lt(i, len) { i := add(i, 1) } { let item: uint := read_uint_storage(add(data_area, i)) mstore_uint(index_mut(mutref(arr), i), item) } } function read_uint_storage(ptr: word) r: uint { r := word_to_uint(sload(word)) } function wordHash(x: word) -> r: word { // buffer can be moved to the scratch area, // but it doesn't even need to, we can just allocate // and de-allocate again. byte[] buffer := new_byte[](32) mstore_word(slice_word(mutref(buffer), 0, 0), x) r := keccak256(slice(ref(buffer), 0, 0)) } ``` ## Mixed-Yul Is it possible to mix lifetime-tracked yul and yul where you have full memory access? The idea would be that there is a direct access to `mload` and `mstore` opcodes and there are `allocate_uint[](...)` functions, but there is no way to get access to the memory pointer inside a `uint[]` variable. Is this "safe enough"? What can the optimizer/allocator still reason about? Which instructios would break such reasoning? Of course the usual assumptions about the free memory pointer hold: You promise to only access memory that you "allocated" before via incrementing the free memor pointer.