TritonVM / triton-vm

Triton is a virtual machine that comes with Algebraic Execution Tables (AET) and Arithmetic Intermediate Representations (AIR) for use in combination with a STARK proof system.
https://triton-vm.org
Apache License 2.0
239 stars 36 forks source link

Method on `LabelledInstruction` showing if `OpStack` grows #227

Closed Sword-Smith closed 11 months ago

Sword-Smith commented 11 months ago

In the building of the tasm-lang compiler it would be nice to have a method on LabelledInstruction showing if the instruction grows the opstack by one. I guess it can't grow the opstack by 2, so maybe a grows_op_stack(&self) -> bool function would suffice?

Concretely it is for this, admittedly not so pretty, function that I could use this method. This function is trying to determine if a triplet of instructions are writing a memory-spilled value to memory. instr_1 would in this function have to grow the stack with 1 for that to be the case.

fn instrunction_triplet_looks_like_spill_writing(
                instr_0: &LabelledInstruction,
                instr_1: &LabelledInstruction,
                instr_2: &LabelledInstruction,
                static_allocations: &HashMap<ValueIdentifier, (usize, ast_types::DataType)>,
            ) -> Option<(ValueIdentifier, usize)> {
                if let Instruction(Push(n)) = instr_0 {
                    if *instr_2 == Instruction(WriteMem) {
                        let n = n.value() as usize;
                        return static_allocations
                            .into_iter()
                            .find(|(_val_id, (memory_spill_position, _))| {
                                *memory_spill_position == n
                            })
                            .map(|x| (x.0.to_owned(), x.1 .0.to_owned()));
                    }
                }

                None
            }
jan-ferdinand commented 11 months ago

PR #230 adds methods for checking growth and shrinkage of the op stack. Additionally, you will be able to write something like:

let sum_op_stack_size_influence = labelled_instructions
    .iter()
    .map(|instr| instr.op_stack_size_influence())
    .sum::<i32>();
jan-ferdinand commented 11 months ago

Let me know if the added methods grows_op_stack(), changes_op_stack_size(), shrinks_op_stack(), and op_stack_size_influence() are in your interest, or if there are any lacking or unintuitive ones.

Sword-Smith commented 11 months ago

Looks very reasonable to me. This solves my immediate problem and might even give me the ability to build in a really useful set of tests in the compiler, as I can now verify that the compiler's view of the stack matches the size that the instructions dictate.