argotorg / argotorg/solidity

--via-ssa-cfg: O(N^4) compile-time blowup driven by number of simultaneously-live local variables in a single function

Open
#16,875 4 comments 0 reactions 1 assignee Claimed by @blishko View on GitHub
experimental high effort medium impact performance :racehorse:
Dominant language
C++
Stars
25.7k
Forks
6.2k
Avg merge
2d 19h
Merged PRs (30d)
29

Description

## Description

Compiling a function via **`--via-ssa-cfg`** scales as approximately O(N^3.87) (~**O(N^4)**) with N,
the number of local variables that stay simultaneously live until a single combining expression
(e.g. `return v1 + v2 + ... + vN;`). Measured via log-log regression across N=20..150
(R^2=0.9985): N=70 takes ~36s, N=150 takes ~700s (11m41s).

A syntactically ordinary contract with no unusual constructs -- just a function with ~100-150
local variables that are all summed in a single final expression -- can lock up the compiler for
minutes to hours.

I would expect compilation time to scale roughly linearly (or at worst as a low-degree
polynomial) with the number of local variables, not as O(N^4).

## Environment

- Compiler version: 0.8.37-develop (develop branch, commit b7d70971)
- Compilation pipeline (legacy, IR, SSA CFG): SSA CFG
- Target EVM version (as per compiler settings): default (not explicitly set in settings.evmVersion)
- Framework/IDE (e.g. Foundry, Hardhat, Remix): none -- solc invoked directly via --standard-json
- EVM execution environment / backend / blockchain client: N/A (compilation only, not executed)
- Operating system: Linux

## Steps to Reproduce

1. Save the following contract as `t.sol` (a function with 100 local variables, all summed in a
single final expression):

```solidity
pragma solidity ^0.8.0;

contract T {
function manyVars(uint a) public pure returns (uint) {
uint v1 = a + 1;
uint v2 = a + 2;
uint v3 = a + 3;
...
uint v100 = a + 100;
return v1 + v2 + v3 + ... + v100;
}
}
```

2. Compile it via standard-json with SSA CFG enabled:

```json
{
"language": "Solidity",
"sources": { "t.sol": { "content": "" } },
"settings": {
"viaIR": true,
"experimental": true,
"viaSSACFG": true,
"outputSelection": { "*": { "*": ["evm.bytecode.object"] } }
}
}
```

```
solc --standard-json request.json
```

3. Observe compile time scaling with N (number of local variables):
- N=20: 0.31s
- N=40: 3.37s
- N=60: 19.38s
- N=70: 36.30s
- N=150: 700.90s (11m41s)

Log-log regression across these points gives T(N) = C * N^k with k=3.87, R^2=0.9985 --
i.e. approximately O(N^4).

[request.json](https://github.com/user-attachments/files/30141392/request.json)
[timing_data.csv](https://github.com/user-attachments/files/30141393/timing_data.csv)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.