Advanced compiler optimisation

[rkalis]

In #18 I listed several potential compiler optimisations of which the lowest hanging fruit was implemented in 0.2.0. The remaining optimisations are documented below, although this list might be updated in the future.

• Improved stack ordering. By looking at the script we know when values are needed by certain opcodes. If we are able to order the initial stack correctly, there is no need to OP_PICK or OP_ROLL these values when they're needed, as they are already available at the top of the stack.
• Simplification. If a contract contains e.g. 2 + 2 == 4, we already know beforehand that this is going to evaluate to true, so this whole expression can be simplified to just true. However, most well-implemented contracts will likely not have many of these instances, as the implementer can manually do a lot of this simplification themselves. So the benefit of implementing this optimisation is questionable.
• Improved deep replacement. When a variable is reassigned inside a conditional block, we replace the variable at its original position in the stack. This uses an algorithm that sort of digs into the stack with OP_SWAP OP_TOALTSTACK, and then puts all other values back where they belong with OP_FROMALTSTACK. This can be improvedby using more specific stack operations for specific depths rather than OP_SWAP.
• Inlining of single-use variables. Some variables are assigned and then only used once in the remaining code. Right now they are pushed to the stack when they are assigned and then retrieved from the stack when they are used. This could be changed to pushing these values to the stack when they are used instead. This would save the opcodes required to retrieve the value (e.g. OP_6 OP_ROLL).

[rkalis]

Currently multifunction contracts are compiled as follows:

<selector> <function1> OP_NUMEQUAL OP_IF
    <body1>
OP_ELSE <selector> <function2> OP_NUMEQUAL OP_IF
    <body2>
OP_ELSE <selector> <function3> OP_NUMEQUAL OP_IF
    <body3>
OP_ELSE
    OP_0
OP_ENDIF OP_ENDIF OP_ENDIF

We have the final OP_ELSE OP_0 to make sure there's no malleability through the function selector.

This can also be achieved by compiling to:

<selector> <function1> OP_NUMEQUAL OP_IF
    <body1>
OP_ELSE <selector> <function2> OP_NUMEQUAL OP_IF
    <body2>
OP_ELSE <selector> <function3> OP_NUMEQUALVERIFY
<body3>
OP_ENDIF OP_ENDIF

This saves us one extra if-else-endif as well as the extra OP_0.

[rkalis]

In #18 I implemented using OP_ROLL over OP_PICK for the final occurrence of variables. This optimisation was skipped if the final occurrence is inside an if-block because we need to be sure that the resulting stack is exactly the same regardless of the taken execution path. There are some special cases where this optimisation can still be applied though:

• The final occurrence of a local variable, as it is dropped from the stack at the end of the block any way.
• If the variable has a final occurrence inside both of the execution paths

[rkalis]

I implemented the NUMEQUALVERIFY optimisation. I also implemented an optimisation that only drops the final OP_VERIFY if the remaining stack depth is < 5, because 2DROP 2DROP 1 < NIP NIP NIP NIP. Finally I also optimised the OutputNullData for HexLiterals. This will be further improved after Simplification is implemented.

[rkalis]

I've been working on simplification. Most simplifications have been implemented in vacuum, but still need to be integrated.

There is one edge case that makes me think though:

• Casting int to sized bytes (NUM2BIN) might result in a much larger bytecode (OP_0 OP_16 OP_NUM2BIN is much smaller in bytes than 0x00000000000000000000000000000000). But it does result in a lower opcount. So it could make sense to skip these optimisations, but then some mor eimpactful simplifications might be skipped as well due to the cascading nature of simplifications.
  • Should we have two optimisation targets (opcount and bytesize)?
  • Should we evaluate the result of an optimisation, and then decide whether to actually apply it? How deep do we go in terms of cascading optimisations?

I'll have to think about this more.

[rkalis]

Simplification and other advanced optimisation will stay on indefinite hold. The already implemented optimisations will be included in the next release.

[rkalis]

The implemented optimisations have been released in v0.4.0.

[mr-zwets]

It makes sense to revisit some of these possible optimizations as the op_code count limit will be removed as part of the May 2025 BCH network upgrade

the only relevant optimization target is bytesize (except for the outlier edge cases where a person would run into the VM opcost budget limits and needs to 'buy extra budget')