Better handling of decorator operations

[bobbinth]

Currently, we have a single Operation type which encodes all operations which can be executed on the VM. These operations fall into two main categories:

1. Regular operations (e.g., ADD, MUL etc.)
2. Decorators (e.g., DEBUG, ADVICE). As opposed to regular operations, decorators do not advance the clock cycle of the VM, and do not affect the state of the deterministic VM components (e.g., stack, memory).

The idea behind decorators is that we can use this mechanism to provide "hints" to the VM for debugging and other purposes. However, the way the decorators are implemented currently, leads to a couple of undesired consequences.

First undesired consequence is that decorators are relatively "heavy". For example, the current size of an Operation is 48 bytes (ideally, it would be just one byte, though this ideal might be difficult to achieve).

Second undesired consequence is that decorators can affect program hash. Specifically, decorators are placed into span blocks and as long as there is at least one regular operation in the same block, all is fine. But if there are no regular operations, we basically have a block which consists of noops, and there is no way to eliminate it. This should happen relatively rarely - but this edge case is possible, and thus we need to handle it.

To sum up: we want to support decorators, but we want to maintain the following properties:

1. They should not affect the size of Operation type.
2. Presence of decorators should not affect program hash.

One way to achieve this is to introduce a separate Decorator type, and have a separate data structure which specifies which decorator is to be executed at a given clock cycles (this would be somewhat similar to how we handle this in v0.1). There might be performance implications to this. Specifically, on each cycle we'd need to check if there are decorators to be executed before executing a regular operation. My hope is that these performance implications would be close to negligible.

However, this still doesn't address the second issue. Consider the following example:

while.true
  <instructions>
end
debug
while.true
  <instructions>
end

The debug decorator here would have to be located in an empty span block, and this would mean that the hash of the program would be different from exactly the same program but without the debug decorator.

One potential solution to this is to also put decorators into other blocks (not just span blocks). But this may add a considerable amount of complexity.

[tohrnii]

Would love to take a stab at this issue.

[bobbinth]

That would be awesome! It is a fairly complicated one. Maybe as the first step it would be good to write up a short description of the general approach?

btw, I'm thinking we can probably remove debug decorators entirely since using execute_iter() gives us a better way to get all the same info (unless others thing they are useful).

[grjte]

I agree about removing debug decorators. That will reduce a lot of the extra weight and avoid having so much complexity introduced here by something that isn't required for normal execution of the program

[bobbinth]

One other thing to mention is that I'd like to come up with a way to tie assembly instructions to the actual operations executed by the VM. Right now a single assembly instruction can be translated into a sequence of one or more operations and for someone who doesn't know all details of this translation debugging a program would be confusing.

It would be cool if in the new decorator structure we could specify these relationships (e.g., these 3 operations are actually just one assembly instruction). This structure would probably introduce some overhead - so, it should be optional. For example, when we execute a program using execute() we don't necessarily need all this info. But when we do it via execute_iter() - this info may be very useful.

[grjte]

One other thing to mention is that I'd like to come up with a way to tie assembly instructions to the actual operations executed by the VM.

I think this could be useful in the future for program analysis of potential optimizations as well. It could help us recognize patterns that could be improved on when compiling higher-level languages to miden assembly or make it easier to highlight sections to be manually reviewed for optimization, such as when the assembly calls pop instead of store (as a simple example)

[tohrnii]

Based on @bobbinth's suggestions, a new decorator structure is being implemented in PR #265. First of all, debug decorator operation has been removed entirely since exec_iter() gives us all the same debug info. A new decorator type can be introduced called AsmOp(String) which maps an assembly instruction to the start of corresponding series of operations. These decorators can be stored as a DecoratorMap which is a BTreeMap<op_idx, Vec<Decorator>> in a span block. Similarly, advice injection can also be moved out of operations into the new decorator type. We can also use the new decorator to mark start and end of inlined procedures using ProcStart and ProcEnd variants. Since populating this map will be an expensive operation, and debug related decorators (AsmOp, ProcStart, ProcEnd, etc) are not required for regular functioning, a new boolean flag can be introduced to the assembler so that debug related decorators are only populated in debug mode. After execution of these span blocks, the decoratorMap can be stored in the decoder struct as BTreeMap<clk, Vec<Decorator>> for easy mapping between assembly instruction and corresponding series of operations. Please let me know if the above structure makes sense. Required changes can be made as part of PR #265. cc: @grjte

Edit: This is being broken down into several sub-tasks based on @bobbinth's suggestions and PR 265 has been closed in favor of those.

[bobbinth]

I think the above makes sense - but I think we should do this in stages. You already did the first part (removing the debug operation). I think the next step would be to introduce the DecoratorMap structure and to make it work for Advice decorators - so that we can remove them from Operation enum. I suspect this would take some effort as we'll need to make sure SPAN blocks are merged together correctly (though, maybe it won't be as complicated as I think).

Once the above structure is working, we can move to other decorator types.

[bobbinth]

Closing this as it was largely addressed in #282.