solidity

solidity copied to clipboard

• [ ] Check if the call to SyntacticallyEqual::operator() can be made more efficienty
• [ ] Check yul::valueOfNumberLiteral (cache it)
• [ ] In DataFlowAnalyzer, don't always use m_memory (check whether the derived class needs it). CSE might be fine without it - implemented in https://github.com/ethereum/solidity/pull/13261

Taken from a 0.8.15 profiling:

Perhaps also https://github.com/ethereum/solidity/blob/70ca05fd739b2423636d510e3e7dca5a59ffbefd/libyul/optimiser/CommonSubexpressionEliminator.cpp#L108

Yep, that's exactly it. So it looks like for CSE we should disable m_memory and m_storage in DataFlowAnalyzer and we should use a more efficient data structure for the search inline 108.

@leonardoalt do you still have the original input for the profiler run here?

@leonardoalt could you provide a repro for the profiler run? I'd love to take a jab at this.

A few questions:

1. Why aren't nested function call expressions unnested -- design choice, or legacy? It could've enabled more CSE for nested expressions, e.g.,

        let expr_9 := checked_add_int256(convert_rational_by_to_int256(expr_7), var_a_2)
        // ...
        let expr_15 := checked_add_int256(expr_9, convert_rational_by_to_int256(expr_7))

Regardless, it might be worth to support such nested CSE (by looking up such nested/unnamed values & replacing them with newly inserted variable definitions). I uncovered this pattern from a very simple program:

contract C {
    function foo(int a) pure public {
        int a = 2 + a;
        int b = a + 2;
        int c = a * b;
        int d = a * b;
    }
}

2. For the commented inefficient search, any thoughts on using value numbering (simple hash) to look up variable by syntactic value? We could potentially also cache valueOfNumberLiteral in the SyntacticallyEqual object, and reuse this object in the comparator for the unordered_map.

3. For the same program from (1), any thoughts on supporting CSE for commutative algebraic ops? Should be pretty easy to implement with (2).

4. Is it really worth looking up values for literals (Number, Boolean, String)? Is it to avoid redundant string alloc? I can't seem to make a program that shows this.

Why aren't nested function call expressions unnested -- design choice, or legacy? It could've enabled more CSE for nested expressions, e.g.,

@StrongerXi They will get "unnested" by the ExpressionSplitter. The ExpressionJoiner would invert the operation. But it's a good question on how often this should be applied. You can look at https://github.com/ethereum/solidity/blob/d5a78b18b3fd9e54b2839e9685127c6cdbddf614/libyul/optimiser/Suite.cpp#L254 and https://github.com/ethereum/solidity/blob/d5a78b18b3fd9e54b2839e9685127c6cdbddf614/libsolidity/interface/OptimiserSettings.h#L44 on how it's being used.

For the commented inefficient search, any thoughts on using value numbering (simple hash) to look up variable by syntactic value?

Sounds good. Would be nice to benchmark this change, and we'd accept this if it can improve the performance.

For the same program from (1), any thoughts on supporting CSE for commutative algebraic ops? Should be pretty easy to implement with (2).

Again, sounds good. For commutativity, we have mostly been relying on https://github.com/ethereum/solidity/blob/develop/libevmasm/RuleList.h. If your proposal improves the performance of the optimizer or optimizes more code, we'd be happy to merge it.

Is it really worth looking up values for literals (Number, Boolean, String)? Is it to avoid redundant string alloc? I can't seem to make a program that shows this.

Also sounds good. I also found all the string manipulation a bit awkward. Maybe you can have a Yul dialect that only has number literals (u256) and perform all operations there.

Thanks for your suggestions, they all sound good! I'm not sure if we are currently doing CSE for calls to user-defined functions. We did some work on extending the side-effects structure also to user-defined functions, so it might already be there, but could also be in an "almost finished" open pull request :)

After https://github.com/ethereum/solidity/pull/13682 I think the only item left that can improve the performance for the profile run in the screenshot is to improve the knowledge base.

@leonardoalt do you happen to have the original solidity source code for the profile run?

The last task is being tracked in https://github.com/ethereum/solidity/issues/13700