Examine MLIR's and melior's ability to add support for running generated programs under lldb with DWARF information.

Sierra implementation

• bool_to_felt252
• bool_and_impl
• bool_not_impl
• bool_xor_impl
• bool_or_impl

Sierra implementation

• enum_init
• enum_match

The enum_snapshot_match libfunc is covered by #93

• Compilation process walk-through
• Module documentation

Sierra implementation

• emit_event_syscall

It will eventually be necessary to call functions implemented in rust from the emitted programs.
Research which mechanism allows this, and lay down the framework needed.

Sierra implementation

The consts module in cairo-sierra-lang does not contain a particular libfunc but instead the ConstGenLibfunc trait, WrapConstGenLibfunc and SignatureAndConstConcreteLibfunc types. Explore how these are used in sierra and whether they need to be taken into account when translating sierra to MLIR.

it may lead to better optimizations since its higher level

todo: check how feasible this is

Include proptest as a dependency, examine the codebase for possible areas to property test and create separate issues for them.

Sierra implementation

• ec_point_zero
• ec_point_try_new_nz
• ec_point_from_x_nz
• ec_point_unwrap
• ec_neg
• ec_point_is_zero
• ec_state_init
• ec_state_add
• ec_state_try_finalize_nz
• ec_state_add_mul

Sierra implementation

• get_builtin_costs
• withdraw_gas_all

Sierra implementation

• store_temp
• store_local
• finalize_locals
• alloc_local
• rename

As the title says, methods with jumps and branching add a block that acts like the entry block, we should just use the entry block.

The purpose of this issue is to provide a way to implement MLIR stuff without the boilerplate associated with the C API, or melior in our case.

This macro will be especially useful when implementing large portions of code, as is the case with felt divison and the print implementations.

For starters, it only needs to parse the MLIR code and generate its representation, which can then be transferred into the appropiate module.

Usage example

impl<'ctx> Compiler<'ctx> {
    pub fn create_libfunc_print(
        &'ctx self,
        func_decl: &LibfuncDeclaration,
        parent_block: BlockRef<'ctx>,
        storage: &mut Storage<'ctx>,
    ) -> Result<()> {
        let module = mlir_asm! { &self.context =>
            func.func @print(%arg : llvm.struct<(i32, i32, !llvm.ptr)>) -> () {
                // ...
            }
        };

        // Transfer to our root module.
        {
            fn push_recursive(m: BlockRef, op: OperationRef) {
                m.append_operation();
                if let Some(next_op) = op.next_in_block() {
                    push_recursive(m, next_op);
                }
            }

            let module_body = module.body();
            push_recursive(parent_block, module_body.first_operation().unwrap());
        }

        storage.libfuncs.insert(
            func_decl.id.debug_name.as_deref().unwrap().to_string(),
            SierraLibFunc::create_function_all_args(vec![...], vec![]),
        );

        Ok(())
    }
}

• Compiler internals:
  • Gas global variable
  • Gas global variable manipulation (increase, decrease, get)
• Libfuncs:
  • withdraw_gas
  • withdraw_gas_all
  • get_available_gas
  • get_builtin_costs

Some documentation references:

• StarkWare Sessions 23 | Sierra - Enforcing Safety Using Typesystems | Shahar Papini
• StarkWare Sessions 23 | Not Stopping at the Halting Problem | Ori Ziv
• StarkNet Documentation: Fee Mechanism

Note: Cairo prevents us from running program with infinite loops by including a gas meter. The gas meter is a mechanism that limits the amount of computation that can be done in a program. By setting a value to the --available-gas flag, we can set the maximum amount of gas available to the program. Gas is a unit of measurementsthat expresses the computation cost of an instruction. When the gas meter runs out, the program will stop. In this case, the program panicked because it ran out of gas, as the stop condition was never reached. It is particularly important in the context of smart contracts deployed on Starknet, as it prevents from running infinite loops on the network. If you're writing a program that needs to run a loop, you will need to execute it with the --available-gas flag set to a value that is large enough to run the program.

• src
• withdraw gas example

As recursive functions can be a source of infinite loops if the stop condition is never met, the Cairo-to-Sierra compiler will inject a withdraw_gas method at the beginning of recursive functions. As this feature has not yet been implemented, developers are still expected to call withdraw_gas in recursive functions and handle the result themselves, although it should be included in a future release of the compiler.
This withdraw_gas function will deduct the amount of gas required to run the function from the total gas available for the transaction by evaluating the cost of running each instruction in the function. The cost is analyzed by determining how many steps each operation takes - which is known at compile time for most operations. During the execution of a Cairo program, if the withdraw_gas call returns a null or negative value, the current function execution will stop, all pending variables will be consumed by calling dict_squash on unsquashed dictionaries and calling drop on other variables, and the execution will be considered as failed. Because all transactions on Starknet have a limited amount of spendable gas to execute the transactions, infinite loops are avoided - and by ensuring that enough gas is still available to drop the variables and stop the execution, the sequencer will be able to collect the fees from the transaction failure.

• src

The branch_align libfunc is used to equalize gas costs and ap changes across merging paths of branching code.

• src

Code:

• Sierra extension module: gas
• Sierra gas computation crate
  -Sierra to casm gas invocation implementation

And add check to CI pipelines

Sierra implementation

• array_len
• array_new
• array_append
• array_pop_front
• array_get

The array_snapshot_pop_front libfunc is covered by #93

The dprintf call for u128 values most likely isn't working due to size constraints, possible fix: print the upper 64bits in hex and then the lower 64bits

The --print-fd flag works only when printing the return value of main (that is, when combined with --main-print). It should also work when using the print trait.

Negative --print-fd values should disable printing, however right now dprintf() is called with the negative file descriptor, which causes it to fail. The effect is the same, but the implementation is incorrect and should be fixed.

Sierra implementation

Some of the following libfuncs may warrant their own issue:

• Sierra implementation
  • contract_address_const
  • contract_address_to_felt252
  • contract_address_try_from_felt252
  • class_hash_const
  • class_hash_to_felt252
  • class_hash_try_from_felt252
  • call_contract_syscall
  • deploy_syscall
  • library_call_syscall
  • send_message_to_l1_syscall

Sierra implementation

• Sierra implementation
  • felt252_add_const
  • felt252_div_const
  • felt252_mul_const
  • felt252_sub_const

The cairo compiler does not seem to generate these currently.

Sierra implementation

• storage_base_address_const
• storage_address_to_felt252
• storage_address_from_base
• storage_address_from_base_and_offset
• storage_address_try_from_felt252
• storage_base_address_from_felt252
• storage_read_syscall
• storage_write_syscall

• Add a Makefile pattern rule to build the examples.
• Remove and exclude examples/*.sierra, examples/*.mlir and examples/*.ll from git.

• Sierra implementation
  • felt252_const
  • felt252_add
  • felt252_div
  • felt252_is_zero
  • felt252_mul
  • felt252_sub

Current benchmarks are run either with external scripts, or with criterion for microbenchmarks.
We should research incorporaring Iai into the benchmarks run as part of our CI pipeline so that they can be used not as proper performance regression tests.

Sierra implementation

Sierra implementation

• upcast
• downcast

Sierra implementation

The sqrt libfunc is marked experimental and does not seem to be very used.

Sierra implementation

• set_block_number
• set_block_timestamp
• set_caller_address
• set_contract_address
• set_sequencer_address

• Sierra extension module

  • secp256k1_ec_add_syscall
  • secp256k1_ec_get_point_from_x_syscall
  • secp256k1_ec_mul_syscall
  • secp256k1_ec_new_syscall

• PR adding the secp256k1 syscall

• Add a rust-toolchain file setting. cf cairo-rs
• Copy rustfmt.toml & clippy.toml from https://github.com/starkware-libs/cairo
• Add code coverage, cf cairo-rs codecov.yml
• Rename test.yml to ci.yml
• Try to standarize with cairo's main worlflow

• snapshot
  • snapshot_take (done in #79)
• structure
  • struct_snapshot_deconstruct #369
• array
  • array_snapshot_pop_front
• enm
  • enum_snapshot_match #366

Sierra implementation

• snapshot_take

Looks like its a way to "duplicate" non-duplicatable values.

Sierra implementation

• replace_class_syscall

• Sierra implementation for 8,16,32 and 64 bit widths
• Sierra implementation for 128 bit width
• Libfuncs for a given width:
  • uN_const
  • uN_eq uN_eq(T, T) -> [branch, branch] (fallthrough 0)
  • uN_is_zero uN_is_zero(T) -> [branch, branch] (fallthrough 0)
  • uN_le uN_le(RangeCheckPtr, T, T) -> [branch, branch] (fallthrough 0)
  • uN_lt uN_lt(RangeCheckPtr, T, T) -> [branch, branch] (fallthrough 0)
  • uN_overflowing_add _overflowing_add(RangeCheckPtr, T, T) -> [branch(RangeCheckPtr, T), branch(RangeCheckPtr, T)]
  • uN_overflowing_sub _overflowing_sub(RangeCheckPtr, T, T) -> [branch(RangeCheckPtr, T), branch(RangeCheckPtr, T)]
  • uN_safe_divmod
  • uN_to_felt252
  • uN_try_from_felt252
  • uN_wide_mul

Sierra implementation

• pedersen

Implement functionality to be able to print Felt252's in the emitted programs, for debugging aid.
This is distinct from the print libfunc which supports the print facility in cairo.
Additionally, see how the debugging tips can be applied from a rust context

Sierra implementation

• print

Use the programs from the cairo examples folder to drive a test battery.

When there are 2 paths, and the point where they join uses a variable computed within those paths, it currently errors because it doesn't dominate it's use. To fix this we need to pass the variables through the block arguments.

Sierra implementation

• get_execution_info_syscall
• get_execution_info_v2_syscall

Cairo 1 also supports dictionaries in the core library. A dictionary is a data structure that stores key-value pairs. The key is used to look up a specific value, much like looking up a word in a print dictionary. It is currently possible to create dictionaries that map felts to u128, felt, u8, u64 and Nullable::.

Because short strings are actually felts, it is possible to create string keys in a dictionary.

example:

use dict::Felt252DictTrait;

fn main() -> u32 {
    let mut dict: Felt252Dict<u32> = Felt252DictTrait::new();
    dict.insert('hello', 2_u32);
    let value = dict.get('hello');
    value
}

let mut d = DictFeltToTrait::new();
d.insert(1, 1); // Write.
d.get(1); // Read.
d.squash(); // Destroy the dictionary.

• Cairo 1 corelib dict
• Sierra extension module
  • felt252_dict_entry_finalize
  • felt252_dict_entry_get
  • felt252_dict_new
  • felt252_dict_squash
  • Felt252Dict type
  • SquashedFelt252Dict type
  • Felt252DictEntry type
  • redeposit_gas
• Sierra squashed_felt252_dict extension module
• Sierra to casm dict implementation
• Caito lang runner dict manager implementation

Sierra implementation

• null
• nullable_from_box
• match_nullable

Sierra implementation

• poseidon