feat(public-vm): call and return opcodes

[Maddiaa0]

Overview

Implement call and return opcodes in the avm

We will have a reserved memory space to use as the call stack, e.g. hypothetically 0x100 -> 0x200. The return pointer will begin at 0x100, then on each call we write the return destination to the stack pointer, increment the pointer, then preform the jump to the new location.
We can assume that JUMP has one operand, which is the dest. This operand MUST be present within intermediate register a.

On a return, we can load the return value by popping from the ret_stack, reading the pc to jump to then setting the next pc to have that value

Note: Not covered
The bytecode constraints will have to do some of the work here to ensure that the value in a is correct.

Spec

Relations

//===== JUMP_RETURN ========================================================
    // The program counter in the next row should be equal to the value loaded from the ia register
    // This implies that a load from memory must occur at the same time
    // Imply that we must load the jump selector into mema
    sel_jump * (ret_ptr' - (ret_ptr + 1)) = 0; // we increment our jump selector
    sel_jump * (ret_ptr - mem_idx_a) = 0;
    sel_jump * (rwa - 1) = 0; // it must be a write
    sel_jump * (mem_op_a - 1) = 0;
    sel_jump * (pc' - ia) = 0;
    
    // We must load the memory pointer to be the ret_ptr 
    sel_ret * (ret_ptr - (ret_ptr - 1)) = 0; // We decremenet out jump selector
    sel_ret * (ret_ptr - mem_idx_a) = 0;
    sel_ret * (pc' - ia) = 0;
    sel_ret * rwa = 0;
    sel_ret * (mem_op_a - 1) = 0;

Columns

• We have a selector for the jump sel_jump and return sel_ret
• We have a ret_ptr return pointer that keeps track of the head of the return stack in memory
• We have a program counter

On a Jump

• The return pointer MUST increment
• We must write the current program counter value into the current ret_ptr
• To do a write we must have the ret_ptr in our intermediate register a
• We must have the mem address in mem_ida_a

On a return:

• The return pointer MUST decrement
• We read the program counter from the ret_ptr memory location (-1) into intermediate reg a
• We set pc to the value in intermediate reg

Open questions:

We will need to initialise this return stack as a fixed and reserved part of memory, to do this we will need a way to ensure a boundary condition -> i.e. ret_ptr starts at this reserved location

[dbanks12]

@Maddiaa0 should this have been auto-closed by #3704 ?

[Maddiaa0]

@Maddiaa0 should this have been auto-closed by #3704 ?

Ye