Straightforward cases where memory mover fails to move enough variables to memory

[cameel]

Solidity

This relatively regular example results in a "Stack Too Deep" error even though memory mover should be able to deal with it simply by moving more variables:

function sum(
    uint x01, uint x02, uint x03, uint x04,
    uint x05, uint x06, uint x07, uint x08,
    uint x09, uint x10, uint x11, uint x12,
    uint x13, uint x14, uint x15, uint x16,
    uint x17, uint x18
) returns (uint)
{
    return
        x01 + x02 + x03 + x04 +
        x05 + x06 + x07 + x08 +
        x09 + x10 + x11 + x12 +
        x13 + x14 + x15 + x16 +
        x17 + x18;
}

function arg(uint i) returns (uint) {
    return i * i + i * i;
}

function f(
    uint a01, uint a02, uint a03, uint a04,
    uint a05, uint a06, uint a07, uint a08,
    uint a09, uint a10, uint a11, uint a12,
    uint a13, uint a14, uint a15, uint a16,
    uint a17, uint a18
) returns (uint) {
    uint u01 = arg(a01); uint u02 = arg(a02); uint u03 = arg(a03); uint u04 = arg(a04);
    uint u05 = arg(a05); uint u06 = arg(a06); uint u07 = arg(a07); uint u08 = arg(a08);
    uint u09 = arg(a09); uint u10 = arg(a10); uint u11 = arg(a11); uint u12 = arg(a12);
    uint u13 = arg(a13); uint u14 = arg(a14); uint u15 = arg(a15); uint u16 = arg(a16);
    uint u17 = arg(a17); uint u18 = arg(a18);
    return sum(
        u18, u17,
        u16, u15, u14, u13,
        u12, u11, u10, u09,
        u08, u07, u06, u05,
        u04, u03, u02, u01
    );
}

contract C {
    function run() public {
        f(
             1,  2,  3,  4,
             5,  6,  7,  8,
             9, 10, 11, 12,
            13, 14, 15, 16,
            17, 18
        );
    }
}

solc test.sol --via-ir --optimize --asm

Error: Variable sum_14 is 1 too deep in the stack [ sum_12 sum_14 sum_13 sum sum_1 sum_2 sum_3 sum_4 sum_5 sum_6 sum_7 sum_8 sum_9 sum_10 sum_11 product_10 product_2 product_34 ]
memoryguard was present.

Looking at the IR output, only 3 variables get actually moved to memory, which might indicate that the memory mover tries but for some reason gives up without reporting an error:

pop(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(checked_add_uint256(sum_14, sum_13), sum_12), sum_11), sum_10), sum_9), sum_8), sum_7), sum_6), sum_5), sum_4), sum_3), sum_2), sum_1), sum), mload(0x80)), mload(0xa0)), mload(0xc0)))

Unoptimized compilation results in "Stack Too Deep" as well:

solc test.sol --via-ir --asm

Error: Cannot swap Variable _1 with Slot TMP[mload, 0]: too deep in the stack by 1 slots in [ RET _1 TMP[mload, 0] _16 _15 _14 _13 _12 _11 _10 _9 _8 _7 _6 _5 _4 _3 _2 TMP[mload, 0] ]
memoryguard was present.
  --> test.sol:44:9:
   |
44 |         f(
   |         ^ (Relevant source part starts here and spans across multiple lines).

Yul

I tried to come up with a similar example in Yul, which should be easier to debug. I only partially succeeded, because it produces "Stack Too Deep" only in unoptimized compilation. That still involves memory mover though, so it should be useful anyway:

{
    function sum(
        a01, a02, a03, a04, a05,
        a06, a07, a08, a09, a10,
        a11, a12, a13, a14, a15,
        a16, a17, a18, a19, a20
    ) -> output
    {
        let x := 0
        x := add(x, a01) x := add(x, a02) x := add(x, a03) x := add(x, a04) x := add(x, a05)
        x := add(x, a06) x := add(x, a07) x := add(x, a08) x := add(x, a09) x := add(x, a10)
        x := add(x, a11) x := add(x, a12) x := add(x, a13) x := add(x, a14) x := add(x, a15)
        x := add(x, a16) x := add(x, a17) x := add(x, a18) x := add(x, a19) x := add(x, a20)
        output := x
    }

    function arg(i) -> x {
        let s := mul(i, i)
        x := add(s, s)
    }

    sstore(0, memoryguard(0))

    let x01 := calldataload(1)  let x02 := calldataload(2)  let x03 := calldataload(3)  let x04 := calldataload(4)  let x05 := calldataload(5)
    let x06 := calldataload(6)  let x07 := calldataload(7)  let x08 := calldataload(8)  let x09 := calldataload(9)  let x10 := calldataload(10)
    let x11 := calldataload(11) let x12 := calldataload(12) let x13 := calldataload(13) let x14 := calldataload(14) let x15 := calldataload(15)
    let x16 := calldataload(16) let x17 := calldataload(17) let x18 := calldataload(18) let x19 := calldataload(19) let x20 := calldataload(20)

    let u01 := arg(x01) let u02 := arg(x02) let u03 := arg(x03) let u04 := arg(x04) let u05 := arg(x05)
    let u06 := arg(x06) let u07 := arg(x07) let u08 := arg(x08) let u09 := arg(x09) let u10 := arg(x10)
    let u11 := arg(x11) let u12 := arg(x12) let u13 := arg(x13) let u14 := arg(x14) let u15 := arg(x15)
    let u16 := arg(x16) let u17 := arg(x17) let u18 := arg(x18) let u19 := arg(x19) let u20 := arg(x20)
    sstore(42, sum(u20, u19, u18, u17, u16, u15, u14, u13, u12, u11, u10, u09, u08, u07, u06, u05, u04, u03, u02, u01))
}

solc --strict-assembly test.yul --asm

Uncaught exception:
/usr/src/debug/solidity/solidity_0.8.30/libyul/backends/evm/EVMObjectCompiler.cpp(111): Throw in function void solidity::yul::EVMObjectCompiler::run(const solidity::yul::Object&, bool)
Dynamic exception type: boost::wrapexcept<solidity::yul::StackTooDeepError>
std::exception::what: Cannot swap Variable u17 with Slot TMP[mload, 0]: too deep in the stack by 1 slots in [ u17 TMP[mload, 0] TMP[mload, 0] TMP[mload, 0] u04 u05 u06 u07 u08 u09 u10 u11 u12 u13 u14 u15 u16 TMP[mload, 0] ]
memoryguard was present.
[solidity::util::tag_comment*] = Cannot swap Variable u17 with Slot TMP[mload, 0]: too deep in the stack by 1 slots in [ u17 TMP[mload, 0] TMP[mload, 0] TMP[mload, 0] u04 u05 u06 u07 u08 u09 u10 u11 u12 u13 u14 u15 u16 TMP[mload, 0] ]
memoryguard was present.
[solidity::langutil::tag_sourceLocation*] = test.yul[1472,1483]

[algonomad571]

Hi! I’d like to work on this issue.

I’ve gone through the contributing guidelines and set up the Solidity build environment locally. I’ve also reviewed how the memory mover pass operates in the optimizer and can reproduce the described behavior.

I plan to start by analyzing why the current heuristic stops moving additional variables to memory and then propose a minimal fix with regression tests.

Please assign this issue to me if that’s okay.