If I understand it correctly, the current interval tracing evaluator will perform optimization and generate a new tape whenever something can be optimized. However, this optimization itself can be costly: it is linear in the length of the tape, while the optimization may only remove a few instructions in some (extreme) cases. For tapes that are long, the optimization pass may not be worth it.
I'm thinking if it would make sense to track the use count of values, essentially do a dead-code elimination at the end of an execution. We collect all the instructions that are marked dead, reduce the use count of its dependencies, and repeat. This will only be linear in the number of instructions that are being removed. When this count reaches a certain threshold (percentage of the length of the tape, say), we do the backward pass or continue this DCE and use it to copy things from the front to the back.
The issue with this reference counting approach is that we need to store the use count for each instruction in the tape, and this reference count management is overhead when optimization is beneficial. This is probably only beneficial when the tape is long, say over several hundred instructions, and dependencies are shallow.
If I understand it correctly, the current interval tracing evaluator will perform optimization and generate a new tape whenever something can be optimized. However, this optimization itself can be costly: it is linear in the length of the tape, while the optimization may only remove a few instructions in some (extreme) cases. For tapes that are long, the optimization pass may not be worth it.
I'm thinking if it would make sense to track the use count of values, essentially do a dead-code elimination at the end of an execution. We collect all the instructions that are marked dead, reduce the use count of its dependencies, and repeat. This will only be linear in the number of instructions that are being removed. When this count reaches a certain threshold (percentage of the length of the tape, say), we do the backward pass or continue this DCE and use it to copy things from the front to the back.
The issue with this reference counting approach is that we need to store the use count for each instruction in the tape, and this reference count management is overhead when optimization is beneficial. This is probably only beneficial when the tape is long, say over several hundred instructions, and dependencies are shallow.