Reuse optimized IR/bytecode for bytecode dependencies

[cameel]

Abstract

While the IR code generator does reuse the IR that the current contract depends on (via new, .runtimeCode or .creationCode) it's only the unoptimized IR that is reused. There is no reuse of optimized IR, which means that we're reoptimizing dependencies (and their dependencies, recursively) from scratch every time.

Motivation

This is likely a significant slowdown for contracts that contain a lot of bytecode dependencies.

Benchmarking is needed to determine how much of an effect it has on compilation times in practice, but we have already established that some popular projects do have a lot of bytecode dependencies (especially when using Foundry test framework) so some attempt at code reuse here is expected to be beneficial.

Details

As can be seen in CompilerStack, the compiler takes unoptimized IR of all contracts and later passes it into IRGenerator:

solidity/libsolidity/interface/CompilerStack.cpp

Lines 1519 to 1520 in 8a97fa7

	for (auto const& pair: m_contracts)
	otherYulSources.emplace(pair.second.contract, pair.second.yulIR);

IRGenerator selects sources of contract's bytecode dependencies and embeds their unoptimized IR as subobjects of the contract being compiled:

solidity/libsolidity/codegen/ir/IRGenerator.cpp

Line 150 in 8a97fa7

<subObjects>

Then that object is optimized as a whole, without an attempt at reusing the already optimized IR of other contracts:

solidity/libsolidity/interface/CompilerStack.cpp

Line 1573 in 8a97fa7

stack.optimize();

Possible solutions

A quick and easy way to address this at Yul IR level would be to modify YulStack::optimize() to receive optimized IR of other contracts and substitute it whenever it encounters a corresponding subobject.

The downside of this, however, is that it would only address IR reuse. We'd still be doing Yul->EVM transform separately for each subobject. It also breaks encapsulation by having YulStack assume that the unoptimized subobject really comes from the bytecode dependency and has not been modified between code generation and optimization.

A better approach might be to defer subobject embedding and introduce a linking stage. We could have IRGenerator generate code only for the current contract and insert the code dependency later. The optimizer already works on each assembly separately, and knowledge about assemblies is abstracted away using builtins like datasize()/dataoffset()/datacopy() so this should be feasible.

The upside of this solution is that linking could be done even at the bytecode level, reusing the results of EVM->Yul transform and maybe even EVM asm optimization. The downside is that the change is more invasive and we also have to prepare compiler for dealing with unlinked (i.e. incomplete) bytecode in most of the pipeline. To avoid showing such incomplete artifacts to the user we'd also need to be prepared to do some rudimentary linking at any stage where output can be requested.

Backwards Compatibility

This should be completely transparent to the users, unless we decide to cut corners, e.g. by outputting unlinked artifacts at intermediate stages.

[cameel]

The upside of this solution is that linking could be done even at the bytecode level, reusing the results of EVM->Yul transform and maybe even EVM asm optimization.

Last week I did some profiling to find out whether this would actually be worthwhile. Turns out that probably not. The Yul->EVM takes only ~15% of the overall compilation time while Yul optimizer takes ~70% (10-15% of which are stack optimizations). This would explain why I wasn't seeing much effect of caching the EVM artifacts in my caching experiments.

Results

Here are the results from callgrind for IR compilation of chains.sol on recent develop:

I think this gives a good picture of relative proportions. Numbers on real projects like Uniswap or OZ are a little different, but still consistent with the Yul optimizer being the slowest part:

Input	solc	Yul Optimizer	Stack optimizations	Yul->EVM Transform	Profiler
chains.sol	develop	78.5%	8.2%	6.9%	callgrind
Uniswap v4	0.8.26	55%	0%?	13.7%	gperftools
OpenZeppelin v5.0.2	0.8.26	54.9%	12.9%	15.4%	gperftools

Assuming that roughly:

• Yul Optimizer = OptimizerSuite::runSequence()
• Stack optimizations = StackLimitEvader + StackCompressor
• Yul->EVM Transform = CompilerStack::generateEVMFromIR()

Note also that these results are on 0.8.26, so without #15267.

EDIT: Here's how it looks on develop, with #15267:

Input	solc	Yul Optimizer	Stack optimizations	Yul->EVM Transform	Profiler
Uniswap v4	develop	39.3%	0%?	24.7%	gperftools
OpenZeppelin v5.0.2	develop	50.7%	0%?	13.9%	gperftools

callgrind vs gperftools

callgrind gives pretty clean graphs, but is also unmanageably slow (it took over 24h for Uniswap and I had to kill it in the end) so I had to switch to gperftools.

For comparison, here's what I get for chains.sol in various runs. In particular the 50% vs 70% difference seems to be coming from the input, not from changing the profiler or from switching from develop to 0.8.26.

Input	solc	Yul Optimizer	Stack optimizations	Yul->EVM Transform	Profiler
chains.sol	develop	78.5%	8.2%	6.9%	callgrind
chains.sol	develop	74.4%	13.8%	7.4%	gperftools
chains.sol	0.8.26	75.9%	9.8%	6.6%	gperftools

Curiously, the callgrind results do not show StackLimitEvader. I'm a bit suspicious as to the reliability of those numbers, but they are generally in the same ballpark between both tools so they're probably good enough as long as we don't require too much precision.

Reproducing the results

gperftools

For completeness, here's how to run it on chains.sol (assuming gperftools is installed) in case anyone wants to play with it more:

LD_PRELOAD=/usr/lib/libprofiler.so \
CPUPROFILE="${test_name}.prof" \
    "$solc_path" chains.sol --via-ir --optimize --bin
pprof --svg "$solc_path" "${test_name}.prof" > "${test_name}.svg"

This method does not require building anything extra into the binary but to actually see function names on the graph you need a binary built with debug symbols, so an official release binary won't do. Also, pprof needs the exact same path to the binary that we used to generate the .prof file.

callgrind

valgrind --tool=callgrind \
    "$solc_path" chains.sol --via-ir --optimize --bin
kcachegrind callgrind.out.*

kcachegrind is a separate tool I used to analyze the results.

[clonker]

What optimization flag configuration did you use to benchmark?

[cameel]

For Uniswap and OpenZeppelin? I used the same input that we use in test/benchmarks/external.sh. I.e. the Standard JSON that Foundry generates for those projects when you run forge build --optimize --offline --no-cache --via-ir.

Uniswap:

"optimizer": {"enabled": true, "runs": 44444444},
"evmVersion": "cancun",
"viaIR": true,

OpenZeppelin:

"optimizer": {"enabled": true, "runs": 200},
"evmVersion": "cancun",
"viaIR": true,