Unsound Spill In Mutual Recursion Bug

What it is

A Solidity compiler bug in the Yul optimizer's call graph analysis, disclosed by the Solidity team (found by clonker on May 11, 2026). Mutually recursive functions were sometimes misclassified as non-recursive, allowing the stack-to-memory mover to relocate their local variables to fixed memory offsets — an operation that is only sound for non-recursive functions. The result is silent memory corruption and wrong return values, with no compiler warning and no runtime revert. Rated medium severity. Affects Solidity 0.7.2 through 0.8.35; fixed in 0.8.36.

How it works

The stack-to-memory mover ("stack limit evader") relocates locals to fixed memory offsets to dodge the EVM's 16-slot stack limit. A fixed offset is shared across every activation of a function, so if a relocated function re-enters itself (directly or through a cycle), the inner call overwrites the slot and the outer call reads corrupted data. The mover must therefore never touch functions in a recursive cycle.

The old CallGraphGenerator detected cycles with a path-based DFS that marked nodes visited once fully explored and short-circuited on revisit. This is unsound with intersecting cycles: if a function's cycle can only close through a node already finished as part of an earlier cycle, the traversal stops before the second cycle closes, and the function is wrongly reported non-recursive. Whether this triggers depends on traversal order, which is determined by the hashes of the functions' internal Yul names.

Preconditions / Affected

All of these must coincide:

flowchart TD
    A[Compiled with --via-ir] --> B[Contains mutually recursive internal functions]
    B --> C[Two+ intersecting cycles sharing a function]
    C --> D[Yul-name-hash traversal order triggers misclassification]
    D --> E[Misclassified function complex enough to spill locals to memory]
    E --> F[Corrupted variable influences an observable result]
    F --> G[Miscompilation]

• --via-ir is not default; projects that never opted in are unaffected.
• On 0.8.21+, the bug is independent of --optimize (the mover runs regardless). On 0.7.2–0.8.20, reaching it requires both --via-ir and --optimize.
• The IR pipeline was experimental (required opt-in) before 0.8.13. A working reproducer was only achievable from 0.8.8 onward; the 0.7.2 floor is conservative.
• A Sourcify scan of ~207,000 --via-ir contracts found 272 (~0.1%) with a misclassified function, but none relocate variables inside it — no deployed contract is known affected.

What to do

• Upgrade to Solidity 0.8.36 or later before deploying IR-compiled contracts, particularly those using mutual recursion.
• If a previously-compiling contract now reports "Stack too deep" after upgrading, the recursive function involved was being miscompiled — this is correct behavior, not a regression. That recursion cannot be safely spilled to fixed memory; the fix surfaces the real problem instead of emitting silent wrong code.

The fix replaces the DFS with Tarjan's algorithm, which partitions the graph into strongly connected components in one order-independent pass. A function is now recursive iff it is in an SCC of more than one function, or calls itself directly.

Caveats

• Real-world likelihood is very low — all conditions above must align. No known affected deployment.
• The Solidity team could not build a reproducer below 0.8.8 but cannot prove unreachability, hence the conservative range.
• Unlike many past compiler bugs, this one triggers without inline assembly. Projects running their test suite under --via-ir before deployment are likely to observe the wrong result, though the root cause may not be obvious.