Further improve stack shuffling performance.

[ekpyron]

develop...stackShufflingPerformance has some preliminary work towards replacing the "muiltiplicity maps" during stack shuffling by simple vector lookups by assigning continuous indices to the stack slots before executing the tight stack shuffling loop in

solidity/libyul/backends/evm/StackHelpers.h

Line 113 in dc7cda1

static void shuffle(Args&&... args)

The stack shuffling is invoked in two places, one of them an adding additional PreviousSlot construction for symbolic stack shuffling on top of the regular stack slots (with uncommon comparison behaviour). That latter use is by far not as performance critical as the use in createStackLayout, but it needs to keep working nonetheless.

Tasks:

• reevaluate the via-IR-compilation performance gain of develop...stackShufflingPerformance (e.g. at the chains.sol benchmark)
• if the improvement is confirmed as significant, build a less-aggressively-templated index-based implementation of

  solidity/libyul/backends/evm/StackHelpers.h

  Line 105 in dc7cda1

  class Shuffler

  , in which the required operations on stack slots are defined in terms of indexed stack slots, while the caller will still provide the concrete implementations of the ShuffleOperations (since they differ in both places of use).

I have an additional improvement on top of the branch here https://gist.github.com/ekpyron/743c93f92bdaa9b61ff6019e72eab03e that improves the performance of assigning indices to stack slots - but it relies on boost::unordered_flat_map and we can't easily bump the boost version one that is recent enough to support that, but it'd also be interesting to at least locally evaluate the additional performance increase we can get from that to see if it's worthwhile to purse that further.

[ekpyron]

Note: there is no need to unit-test stack shuffling extensively.
We maintain a representation of the stack while shuffling, we need to make sure that we perform all operations on that properly. But based on that we validate that we in fact achieve the desired stack when performing the shuffling operations, which provides sufficient safety guarantees.

[CASABECI]

develop...stackShufflingPerformance has some preliminary work towards replacing the "muiltiplicity maps" during stack shuffling by simple vector lookups by assigning continuous indices to the stack slots before executing the tight stack shuffling loop in

solidity/libyul/backends/evm/StackHelpers.h

Line 113 in dc7cda1

static void shuffle(Args&&... args)

The stack shuffling is invoked in two places, one of them an adding additional PreviousSlot construction for symbolic stack shuffling on top of the regular stack slots (with uncommon comparison behaviour). That latter use is by far not as performance critical as the use in createStackLayout, but it needs to keep working nonetheless.

Tasks:

• reevaluate the via-IR-compilation performance gain of develop...stackShufflingPerformance (e.g. at the chains.sol benchmark)

• if the improvement is confirmed as significant, build a less-aggressively-templated index-based implementation of

  solidity/libyul/backends/evm/StackHelpers.h

  Line 105 in dc7cda1

  class Shuffler

  , in which the required operations on stack slots are defined in terms of indexed stack slots, while the caller will still provide the concrete implementations of the ShuffleOperations (since they differ in both places of use).

I have an additional improvement on top of the branch here https://gist.github.com/ekpyron/743c93f92bdaa9b61ff6019e72eab03e that improves the performance of assigning indices to stack slots - but it relies on boost::unordered_flat_map and we can't easily bump the boost version one that is recent enough to support that, but it'd also be interesting to at least locally evaluate the additional performance increase we can get from that to see if it's worthwhile to purse that further.