feat: Introduce instruction `recurse_or_return`

[jan-ferdinand]

Instruction recurse_or_return behaves – surprise! – either like instruction recurse or like instruction return. The (deterministic) decision which behavior to exhibit is made at runtime and depends on the current stack as well as the instruction's immediate argument i.

Argument i indicates one of the stack's top 16 elements. Let the value of the indicated stack element be a, and the value of its successor element b. In the slightly special case of i == 15, the indicated element's successor is taken to be stack element with index 0. If a != b, then recurse_or_return acts like instruction recurse, else like return.

[Sword-Smith]

I'm seeing an 11 % increase in the number of base columns which takes away what I estimate is 30-50 % of the gain that this new instruction yields. How would that number (the increase in the number of base columns) look if you remove the immediate argument to the instruction and only look at stack element 5 and 6 which is what we need for a faster TASM-verifier?

[jan-ferdinand]

While I was aware that the additional cost of the new instruction in its current design is quite high, the hope was that raising the degree the constraints are lowered to, which would be possible cheaply with an upcoming update, would remove that additional cost again. However, some quick experiments indicate that this is not so; with a target degree of 8, the new instruction would contribute more than a quarter of the total degree-lowering columns. This is an even higher relative impact: at target degree 4, the current design would be responsible for around 15% of the degree lowering columns.

How would [the increase in the number of base columns] look if you remove the immediate argument to the instruction and only look at stack element 5 and 6 […]?

Probably a lot better. To find out the actual numbers, I need to write the corresponding code.

[jan-ferdinand]

How would [the increase in the number of base columns] look if you remove the immediate argument to the instruction and only look at stack element 5 and 6 […]?

The new instruction recurse_or_return without immediate argument introduces an additional 3 base columns in the degree lowering table.

[jan-ferdinand]

When targeting a degree of 12, which might be possible through a future upgrade, the additional cost of instruction recurse_or_return with immediate argument becomes negligible: it introduces only 2 additional degree-lowering columns.

Instruction recurse_or_return without immediate argument introduces 1 additional degree-lowering column:

Summarizing, with target degree 12, we have:	branch	degree-lowering columns
master	66
recurse_or_return	67
recurse_or_return + i	68

Should the target degree be 12 at some point in the future, re-introducing the instruction's immediate argument could be considered.