More Efficient Scratch Slot Assignments in the ABI-Router

[tzaffi]

Problem

Consider this PyTEAL generated approval program with companion ABI contract. It came from this PyTEAL compiler test.

It specifies several methods. In particular, it defines methods sub(uint64,uint64)uint64 and add(uint64,uint64)uint64 that do not depend on each-other. However, PyTEAL generates TEAL code for these that enforce the usage of separate scratch slots.

For a contract with many methods, this could result in needlessly running out of slot space.

Solution

At compile time one could partition subroutine and bare app calls based on their interdependence and then assign slots starting from 0 for each partition component.

Dependencies

None

Urgency

Low-Medium - it seems like very large/complex contracts would be prone to running into this issue. For example, in the above link, a contract with 10 method required 68 slots, comprising more than 1/8 of the total slot space. So a program 8 times the size would be expected to run ouf of slots. It might also be too large in general, but I don't think we want to make the number of slots block large program creation when there is no inherent need.

[jasonpaulos]

FWIW I think it's likely the case a general solution for scratch slot sharing between subroutines & mutually exclusive branches of code captures this concern. We now have another compelling use case that would benefit from it.

[gidonkatten]

Is there any update on this? I am exceeding the scratch slot limit and it is mainly being caused by many abi methods with lots of arguments

EDIT: after some more testing, the subroutines is also having a significant impact

[tzaffi]

FWIW for ARC-4 compliant programs the theoretical solution seems fairly straight forward. But the devil's in the details.

Basically, one would:

1. decompose the subroutine call graph as an acyclic digraph of strongly connected components (SCC's) - call this G
2. compute the number of slots required in each SCC - this is similar to how it's currently done
3. traverse G starting from its leaves as follows:

• toVisit = min-heap of vertices of G with priority the out-degree of each vertex
• while toVisit is non-empty:
  • pop the next SCC v
  • assign required(v) slots starting from 0 but skipping over any already assigned to SCC's for which v is an ancestor
  • remove all edges in G ending at v so as to re-order toVisit

[tzaffi]

Closing since as of version 8 the majority of the scratch slot usage during subroutine calls has been eliminated. @gidonkatten - if you experience any issues, please re-open.