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

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):

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;
    }
}

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

{
    "language": "Solidity",
    "sources": { "t.sol": { "content": "<contract from step 1>" } },
    "settings": {
        "viaIR": true,
        "experimental": true,
        "viaSSACFG": true,
        "outputSelection": { "*": { "*": ["evm.bytecode.object"] } }
    }
}

solc --standard-json request.json

1. 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 timing_data.csv