Compilation time much longer without optimizations enabled than with them enabled

[Jack-Clark]

Description

The program below takes a long time to compile without optimizations enabled, but is very quick with optimizations enabled. This seems like odd behaviour and may suggest something weird going on in the compiler.

uint160 constant v0 = (((0 % ((uint96(0 < 0 ? (0) : ((57896044618658097711785492504343953926634992332820282019728792003956564819967)))) - 0))));
uint160 constant v1 = (((v0 ** (((((int256(((((65535) )) )) < 0 ? (((((((65535) ))) ))) : uint256(int256((((((65535) - ((65535)) ))) ))))))) == 0 ? v0 : uint16(((((((((6553565535) ))) )) < 0 ? (((((((6553565535) ))) ))) : ((((((65535))) ))))))))) == 0 ? ((uint8((((((((255255) )) )) < 0 ? uint256((((((255255) )) ))) : uint256(int256(((((((255)) ))) )))))) ** v0) & (uint120((uint120(((((((1329227995784915872903807060280344575) ))) )) < 0 ? uint256(((((((1329227995784915872903807060280344575) ))) ))) : (((((((1329227995784915872903807060280344575) - (1329227995784915872903807060280344575) ))) )))))))) : ((((uint8(int256((((( - (255) ))) )) < 0 ? uint256((((((  (255) ))) ))) : uint256(((((((255) - (255) ))) )))))) *   uint120((uint120(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((633622243003627655816303902590537618024298437763948046000 % 1329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))) / (uint96(v0) ** ((uint16((uint16(int256((0 % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(0)) : uint256(int256((((- (((63333589844528659455904546595419459198716447290645670587 )) ))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))))))) == 0 ? v0 : v0 % uint16((uint16(int256((((- (((63333589844528659455904546595419459198716447290645670587 % 65535)) % 1))) )) < 0 ? uint256(((((- (((63333589844528659455904546595419459198716447290645670587 % 65535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((63333589844528659455904546595419459198716447290645670587 % 65535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))));
uint160 constant v2 = ((uint96(v1) << (v0 >> uint216((uint216(int256((((- (((1212546125244198100003483652170244291651820393 % 105312291668557186697918027683670432318895095400549111254310977535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((1212546125244198100003483652170244291651820393 % 105312291668557186697918027683670432318895095400549111254310977535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((1))) )))))))) - ((v1 & uint96((uint96(int256((57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(((57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((((602744 % 79228162514264337593543950335)) ))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))));
uint160 constant v3 = (((v2 * ((uint112(int256((((- (((37131 % 5192296858534827628530496329220095)) ))) )) < 0 ? uint256(-int256((((- (((37131 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((37131 % 5192296858534827628530496329220095)) % 1))) )))))) >> v2)) & ((uint80((uint80(int256(((((((1208925819614629174706175))) - (((1208925819614629174706175)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((((30355150732171146360656859781356 % 120892581961462917470617530355150732171146360656859781356 % 1208925819614629174706175)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((((30355150732171146360656859781356 % 12089258196146291747061751208925819614629174706175)) ))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))) ** v0) << ((uint8((uint8(int256((((- (((11504625071530220116791815411563636715055106176383590791724100624698481300350 % 255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((11504625071530220116791815411563636715055106176383590791724100624698481300350 % 255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))))))) == 0 ? v0 : v0 / uint8((uint8(int256(((((((11504625071530220116791815411563636715055106176383590791724100624698481300350 % 25511504625071530220116791815411563636715055106176383590791724100624698481300350 % 255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((((255))) - (((255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))));
uint192 constant v4 = (((uint40((uint40(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))) ** v3) >= (v3 ** uint16((uint16(int256(((((((9.80 % 9.80 % 65535)) % 1))) )) < 0 ? uint256((((((((9.80 % 65535))) - (((9.80 % 65535)) ))) ))) : uint256(int256(((((((9.80 % 65535))) - (((9.80 % 65535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))) ? ((v3 + uint192((uint192(int256(((((((419667436760 % 6277101735386680763835789423207666416102355444464034512895419667436760 % 6277101735386680763835789423207666416102355444464034512895)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((419667436760 % 6277101735386680763835789423207666416102355444464034512895)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((419667436760 % 6277101735386680763835789423207666416102355444464034512895)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))))))) | (v2 - uint112((uint112(int256((((- (((22501639574477468342322750253400633278227133977546808687 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((22501639574477468342322750253400633278227133977546808687 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((22501639574477468342322750253400633278227133977546808687 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))) : ((uint136((uint136(int256((((- (((1594235690288794038468860480509258594591250747359972 % 87112285931760246646623899502532662132735)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256((((((((8711228593176024664662389950253266213273587112285931760246646623899502532662132735)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((1594235690288794038468860480509258594591250747359972 % 87112285931760246646623899502532662132735)) ))) )))))) >> v1) - (uint120((uint120(int256(((((((3394355531188923 % 13292279957849158729038070602803445753394355531188923 % 1329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((((3394355531188923 % 13292279957849158729038070602803445753394355531188923 % 1329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((((3394355531188923 % 13292279957849158729038070602803445751329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))) * v3)));
uint160 constant v5 = uint160(v4) + uint160(v3) + uint160(v2) + uint160(v1) + uint160(v0);
uint160 constant v6 = v5 + v3;
uint160 constant v7 = v6 + v2;
uint160 constant v8 = v7 + v0;
uint160 constant v9 = v8 + v1;

contract Test {
	function test() public returns (uint160) {
		// It seems like having a statically detectable infinite loop is necessary in order to 
		// trigger a long compilation time.
		for(;;) {}
		uint160 v10;
		unchecked {
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
			v10 += v9;
		}
		return v10;
	}
}

$ time solc --bin very_slow_compilation_modified.sol
real	5m19.718s
user	4m21.302s
sys	0m57.960s

$ time solc --bin --optimize very_slow_compilation_modified.sol
real	0m26.746s
user	0m26.630s
sys	0m0.100s

$ time solc --bin --optimize --via-ir very_slow_compilation_modified.sol
real	0m0.170s
user	0m0.165s
sys	0m0.004s

As the comments in the program suggest, this seems to require a statically detectable infinite loop. Furthermore, the expressions that impact the compilation time must come after this infinite loop. The requirement for a statically detectable infinite loop potentially limits the scope of the impact, however, it does seem like odd behaviour.

Environment

• Compiler version: Version: 0.8.18+commit.87f61d96.Linux.g++
• Operating system: Ubuntu 20.04

[cameel]

This is an interesting case. Thanks for the report! It's not specifically infinite loops. Looks like is triggered by any dead code. A simple revert() or return; will cause this too. The optimizer removes dead code, so I'm not surprised that it's fast with optimization. But looking at --bin output, the unused code actually still gets removed even with optimizer disabled. Apparently something between the point where the optimizer normally runs and the point where this dead code is removed (EVM code generation?) is pretty slow.

The earliest version where I was able to reproduce this problem is 0.4.17 (with small adjustments - file level constants were not allowed back then). The one thing that stands out to me in the changelog for that version is this:

• Optimizer: Add new optimization step to remove unused JUMPDESTs.

The fact is, on the CLI the optimizer is never truly disabled. We always run the peephole optimizer and jumpdest removal steps. It's only possible to disable it completely via Standard JSON. This step probably has something to do with the slowdown. It would be interesting to run this via Standard JSON with the whole optimizer disabled and see if this is the source of the problem.

Also, could you check if this affects --via-ir as well? If it does, it gives the problem a bit more impact (though in either case I'd still say the impact is low given that it affects only contracts with huge bits of dead code). It can't really be verified on the CLI because --via-ir without optimization results in "Stack too deep" but you can set minimal optimizations the way described in #12533 (comment) to get only enough optimization to prevent "stack too deep" errors.

Overall, I'm not sure if we should classify this as a bug. I'm inclined to say so, but if it's jumpdest remover, it could just have been designed with the assumption that such pathological dead code is already removed when it runs. @chriseth, what do you think about all this?

By the way, the Test contract can be reduced quite a bit and still give a measurable difference between versions with and without dead code:

contract Test {
    function test() public {
        return;
        v5;
    }
}

On my machine this still takes ~2s with dead code, but finishes almost instantly (~100 ms), with return commented out.

[Jack-Clark]

Thanks for taking a look at this @cameel. I can produce a measurable difference in execution time using your version of the code and standard json input with the following settings:

"optimizer": {
    "enabled": false,
    "details": {
        "peephole": true,
        "inliner": false,
        "jumpdestRemover": true,
        "orderLiterals": false,
        "deduplicate": false,
        "cse": false,
        "constantOptimizer": false,
        "yul": false
    }
},
"evmVersion": "paris",
"viaIR": false,

It seems like both the peephole and jumpdest optimizations need to be enabled to cause the issue. One thing I didn't mention in the initial report is that it seems like the compile time is increasing non-linearly with the amount of dead code. Very roughly, doubling the amount of dead code increases the compile time by 3x-4x. For example, adding another v5 increases the compile time from 0.8s to 2.6s and adding a further two v5s increases the compile time to 10s. I don't know if this helps pin down the issue. It also doesn't look like this affects --via-ir. Using the following settings, I get a "normal" compilation time:

        "optimizer": {
            "enabled": false,
            "details": {
                "peephole": true,
                "inliner": false,
                "jumpdestRemover": true,
                "orderLiterals": false,
                "deduplicate": false,
                "cse": false,
                "constantOptimizer": false,
                "yul": true,
                "yulDetails": {
                    "stackAllocation": true,
                    "optimizerSteps": ""
                }
            }
        },
        "evmVersion": "paris",
        "viaIR": true,

I set stackAllocation to true to avoid the stack too deep errors. For completeness, here's the full standard json that is causing issues:

{
    "language": "Solidity",
    "sources":
    {
      "destructible":
      {
        "content": "uint160 constant v0 = (((0 % ((uint96(0 < 0 ? (0) : ((57896044618658097711785492504343953926634992332820282019728792003956564819967)))) - 0))));uint160 constant v1 = (((v0 ** (((((int256(((((65535) )) )) < 0 ? (((((((65535) ))) ))) : uint256(int256((((((65535) - ((65535)) ))) ))))))) == 0 ? v0 : uint16(((((((((6553565535) ))) )) < 0 ? (((((((6553565535) ))) ))) : ((((((65535))) ))))))))) == 0 ? ((uint8((((((((255255) )) )) < 0 ? uint256((((((255255) )) ))) : uint256(int256(((((((255)) ))) )))))) ** v0) & (uint120((uint120(((((((1329227995784915872903807060280344575) ))) )) < 0 ? uint256(((((((1329227995784915872903807060280344575) ))) ))) : (((((((1329227995784915872903807060280344575) - (1329227995784915872903807060280344575) ))) )))))))) : ((((uint8(int256((((( - (255) ))) )) < 0 ? uint256((((((  (255) ))) ))) : uint256(((((((255) - (255) ))) )))))) *   uint120((uint120(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((633622243003627655816303902590537618024298437763948046000 % 1329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))) / (uint96(v0) ** ((uint16((uint16(int256((0 % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(0)) : uint256(int256((((- (((63333589844528659455904546595419459198716447290645670587 )) ))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))))))) == 0 ? v0 : v0 % uint16((uint16(int256((((- (((63333589844528659455904546595419459198716447290645670587 % 65535)) % 1))) )) < 0 ? uint256(((((- (((63333589844528659455904546595419459198716447290645670587 % 65535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((63333589844528659455904546595419459198716447290645670587 % 65535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))));uint160 constant v2 = ((uint96(v1) << (v0 >> uint216((uint216(int256((((- (((1212546125244198100003483652170244291651820393 % 105312291668557186697918027683670432318895095400549111254310977535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((1212546125244198100003483652170244291651820393 % 105312291668557186697918027683670432318895095400549111254310977535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((1))) )))))))) - ((v1 & uint96((uint96(int256((57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(((57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((((602744 % 79228162514264337593543950335)) ))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))));uint160 constant v3 = (((v2 * ((uint112(int256((((- (((37131 % 5192296858534827628530496329220095)) ))) )) < 0 ? uint256(-int256((((- (((37131 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((37131 % 5192296858534827628530496329220095)) % 1))) )))))) >> v2)) & ((uint80((uint80(int256(((((((1208925819614629174706175))) - (((1208925819614629174706175)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((((30355150732171146360656859781356 % 120892581961462917470617530355150732171146360656859781356 % 1208925819614629174706175)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((((30355150732171146360656859781356 % 12089258196146291747061751208925819614629174706175)) ))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))) ** v0) << ((uint8((uint8(int256((((- (((11504625071530220116791815411563636715055106176383590791724100624698481300350 % 255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((11504625071530220116791815411563636715055106176383590791724100624698481300350 % 255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))))))) == 0 ? v0 : v0 / uint8((uint8(int256(((((((11504625071530220116791815411563636715055106176383590791724100624698481300350 % 25511504625071530220116791815411563636715055106176383590791724100624698481300350 % 255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((((255))) - (((255)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))));uint192 constant v4 = (((uint40((uint40(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))) ** v3) >= (v3 ** uint16((uint16(int256(((((((9.80 % 9.80 % 65535)) % 1))) )) < 0 ? uint256((((((((9.80 % 65535))) - (((9.80 % 65535)) ))) ))) : uint256(int256(((((((9.80 % 65535))) - (((9.80 % 65535)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))) ? ((v3 + uint192((uint192(int256(((((((419667436760 % 6277101735386680763835789423207666416102355444464034512895419667436760 % 6277101735386680763835789423207666416102355444464034512895)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((419667436760 % 6277101735386680763835789423207666416102355444464034512895)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((419667436760 % 6277101735386680763835789423207666416102355444464034512895)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))))))) | (v2 - uint112((uint112(int256((((- (((22501639574477468342322750253400633278227133977546808687 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256((((- (((22501639574477468342322750253400633278227133977546808687 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((22501639574477468342322750253400633278227133977546808687 % 5192296858534827628530496329220095)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))))) : ((uint136((uint136(int256((((- (((1594235690288794038468860480509258594591250747359972 % 87112285931760246646623899502532662132735)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256((((((((8711228593176024664662389950253266213273587112285931760246646623899502532662132735)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256((((- (((1594235690288794038468860480509258594591250747359972 % 87112285931760246646623899502532662132735)) ))) )))))) >> v1) - (uint120((uint120(int256(((((((3394355531188923 % 13292279957849158729038070602803445753394355531188923 % 1329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)) < 0 ? uint256(-int256(((((((3394355531188923 % 13292279957849158729038070602803445753394355531188923 % 1329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967))) : uint256(int256(((((((3394355531188923 % 13292279957849158729038070602803445751329227995784915872903807060280344575)) % 1))) % 57896044618658097711785492504343953926634992332820282019728792003956564819967)))))) * v3)));uint160 constant v5 = uint160(v4) + v3 + v2 + v1 + v0;contract Test {function test() public {return;v5;}}"
      }
    },
    "settings": 
    {
        "optimizer": {
            "enabled": false,
            "details": {
                "peephole": true,
                "inliner": false,
                "jumpdestRemover": true,
                "orderLiterals": false,
                "deduplicate": false,
                "cse": false,
                "constantOptimizer": false,
                "yul": false
            }
        },
        "evmVersion": "paris",
        "viaIR": false,
        "outputSelection": {
            "*": {
                "*": [
                "metadata", "evm.bytecode", "evm.deployedBytecode"
                ]
            }
        }
    }
}

[github-actions]

This issue has been marked as stale due to inactivity for the last 90 days.
It will be automatically closed in 7 days.

[github-actions]

Hi everyone! This issue has been automatically closed due to inactivity.
If you think this issue is still relevant in the latest Solidity version and you have something to contribute, feel free to reopen.
However, unless the issue is a concrete proposal that can be implemented, we recommend starting a language discussion on the forum instead.