Implement CSE optimisation for Indigo programs
Clarification and motivation
After exploration of generated code in morley#128 (closed) I figured out that a lot of extra code generated when some expressions reused, I mean, they are not stored into Indigo variables but stored in a variables created in let
.
This "let creation expressions" seem to be only a peak of iceberg and obvious case, but there are a lot of more implicit cases, like storage.field.innerField1
and storage.field.innerField2
and more (and actually having them in let is kinda convenient). So we need to implement this algorithm https://en.wikipedia.org/wiki/Common_subexpression_elimination
(there is another one https://en.wikipedia.org/wiki/Value_numbering but it requires code to be in form of https://en.wikipedia.org/wiki/Static_single_assignment_form, I think one day we will prohibit variable modification), which basically solves this old known task.
This algorithm is two pass, so first we need to go through contract code and analyse which expressions are reused in several places, but with current IndigoM
it's not possible because we just generate Lorentz code on the fly, losing initial Indigo statements (like assignment, if, case, while, etc).
So, the idea is to introduce something like freer monad or even better operational monad (I don't think we can use standard ones because of exposed inp
and out
) over IndigoM
with all possible statements which require expressions, and then when compilation happen, analyse this program tree, performing CSE algorithm which tracks all subexpressions and gather some additional information for compilation, and then, using this information to compile allocating some temporary variables on stack, which would allow to just reuse value of an expression instead of computing it from scratch, and generate more optimal in sense of gas and byte size code.
Acceptance criteria
The functionality is implemented, checked that it improves managed ledger contract and some tests are written.