The new IR pipeline introduces stack-to-deep errors

[pcaversaccio]

Description

Running my Solidity tests here (commit 2d8b8d1238e7534cef8a4fb1640068cc34259ea8) using the --via-ir option will throw with a stack-too-deep error even though compiling it "normally", i.e using the old bytecode optimiser pipeline, will complete successfully.

Failure Case

~$ forge test --via-ir
[⠒] Compiling...
[⠃] Compiling 102 files with 0.8.20
[⠘] Solc 0.8.20 finished in 566.03s
Error: 
Compiler run failed:
Error: Yul exception:Variable var_assets is 1 too deep in the stack [ RET var_assets _3 expr_2 _5 _2 expr_1 _6 expr _8 cleaned var_caller _7 _16 _12 var_receiver _20 _21 ]
memoryguard was present.
memoryguard was present.

Success Case

~$ forge test
[⠰] Compiling...
[⠢] Compiling 102 files with 0.8.20
[⠰] Solc 0.8.20 finished in 175.13s
Compiler run successful!

Environment

• Compiler version: 0.8.20
• Target EVM version (as per compiler settings): shanghai
• Framework/IDE (e.g. Truffle or Remix): forge
• EVM execution environment / backend / blockchain client: foundry (i.e. hevm under the hood)
• Operating system: WSL using Ubuntu

Steps to Reproduce

Install Foundry:

curl -L https://foundry.paradigm.xyz | bash

Clone my repo and run forge with the --via-ir option (caveat: it's time-consuming since the new IR pipeline is very slow):

git clone git@github.com:pcaversaccio/snekmate.git
cd snekmate
git submodule update --init --recursive
forge test --via-ir

[aathan]

Possibly related. If --optimizer-runs is omitted, this error is not produced. Does the "memoryguard" indicate there is some arbitrary limit on the size of certain data structures? Can I increase it? I plan to try 0.8.20 soon.

$ forge build --force --via-ir --optimizer-runs 1
[⠊] Compiling...
[⠃] Compiling 71 files with 0.8.19
[⠢] Solc 0.8.19 finished in 75.88s
Error:
Compiler run failed:
Error: Yul exception:Variable var_quantum is 2 too deep in the stack [ var_mult var_normToV _1 var_quantum var_name_mpos var_div var_quantize var_mm_slot RET RET[increment_uint256] var_i RET[checked_add_uint256] 0x06 RET[fun_log_23831] expr_1 _2 RET[string_concat_stringliteral_703d_string_stringliteral_681a_string_storage_stringliteral] var_name_mpos RET[fun_log_23831] _10 _8 ]
memoryguard was present.
memoryguard was present.

[cameel]

See memoryguard in the Yul docs. In this particular case the fact that memoryguard was present simply indicates that your code did not contain anything that would make the compiler assume your code is not memory-safe (like assembly blocks that access memory and are not marked memory-safe), and it was able to use memoryguard. Which means that the compiler was not prevented from using the mechanism for moving variables to memory, which is the most common cause of "Stack too deep" errors nowadays.

It does not impose any size limits.

[pcaversaccio]

See memoryguard in the Yul docs. In this particular case the fact that memoryguard was present simply indicates that your code did not contain anything that would make the compiler assume your code is not memory-safe (like assembly blocks that access memory and are not marked memory-safe), and it was able to use memoryguard. Which means that the compiler was not prevented from using the mechanism for moving variables to memory, which is the most common cause of "Stack too deep" errors nowadays.

Right, so it's an optimizer bug in the end, correct?

[ekpyron]

Technically it's a bug in what we call "Yul-EVM-code-transform" :-) - but it's a bug in any case.

[mds1]

Adding the Optimism codebase as another data point here, where it compiles with the default pipeline but not with the via-ir pipeline. Steps to reproduce:

1. Clone the repo: https://github.com/ethereum-optimism/optimism/
2. Checkout commit fff6563c5, the latest commit on the develop branch at the time of writing
3. cd packages/contracts-bedrock && forge install
4. Find and replace pragma solidity 0.8.15 with pragma solidity ^0.8.15 if you want to compile with the latest solidity version (foundry will auto-detect)
5. forge build: This builds with the regular optimization pipeline (not via-ir), and it builds successfully
6. In foundry.toml, under [profile.default], add via_ir = true to enable via-ir
7. Run forge clean for good measure, and run forge build. This errors with:

Error: Yul exception:Cannot swap Variable var_operation with Variable _1: too deep in the stack by 4 slots in [ var_operation RET var_operation var_data_57693_length var_signatures_mpos var_signatures_mpos var_to var_refundReceiver var_gasToken var_gasPrice var_baseGas var_safeTxGas var_value var_data_57693_offset var_refundReceiver var_to var_data_57693_length var_value var_gasToken var_gasPrice var_baseGas var_safeTxGas _1 ]
No memoryguard was present. Consider using memory-safe assembly only and annotating it via 'assembly ("memory-safe") { ... }'.
YulException: Cannot swap Variable var_operation with Variable _1: too deep in the stack by 4 slots in [ var_operation RET var_operation var_data_57693_length var_signatures_mpos var_signatures_mpos var_to var_refundReceiver var_gasToken var_gasPrice var_baseGas var_safeTxGas var_value var_data_57693_offset var_refundReceiver var_to var_data_57693_length var_value var_gasToken var_gasPrice var_baseGas var_safeTxGas _1 ]
No memoryguard was present. Consider using memory-safe assembly only and annotating it via 'assembly ("memory-safe") { ... }'.

Nearly all assembly blocks in the codebase are not annotated as memory-safe, but I'd expect that this shouldn't be an issue for via-ir given that it does compile without via-ir.

[cameel]

Nearly all assembly blocks in the codebase are not annotated as memory-safe, but I'd expect that this shouldn't be an issue for via-ir given that it does compile without via-ir.

Well, this actually is a big issue for the IR codegen, because one of the main mechanisms to avoid StackTooDeep is moving variables to memory when we can't put them all in reachable stack slots - and that mechanism has to be disabled in presence of memory-unsafe assembly blocks.

We're working on improving the algorithms used by the Yul->EVM transform to make moving variables to memory necessary less often and if we could get EIP-663 it would solve the issue too, but for the time being we have to rely heavily on the stack-to-memory mover to solve the hard cases.

[mds1]

That all makes sense, but why is the regular pipeline able to handle this, and not the IR pipeline? Presumably the regular pipeline is not just incorrectly assuming all assembly blocks are memory safe :)

[cameel]

Well, if the legacy pipeline is compiling this without StackTooDeep, the IR should theoretically be able to arrive at such a solution too. Still, it's not really possible to "fix it" by making it do the same things, because they're designed completely differently. Legacy has much more complex code generator, which uses a lot of tricks to avoid overloading the stack, while IR purposely generates inefficient but very simple Yul and offloads dealing with the problem to the optimizer and the Yul->EVM transform. Looks like, unfortunately, in this case the legacy approach is still more effective. It will not stay like this forever though. Problems in the transform are being heavily researched now.

In the meantime, IR can use stack-to-memory-mover as a fallback. This actually gives it an edge in other cases, where the code would not compile at all without moving variables to memory. Legacy would be stuck and the IR pipeline can power through it.

[karmacoma-eth]

Adding another datapoint here with the a16z/cicada codebase:

git clone https://github.com/a16z/cicada

cd cicada

# works
forge build --use 0.8.25

# does not work
forge build --use 0.8.26

Error: 
Compiler run failed:
Error: Yul exception:Cannot swap Variable usr$a3 with Variable usr$updatedCarry: too deep in the stack by 1 slots in [ var_result_28726_mpos RET usr$p usr$a3 var_modulus_mpos usr$r6_2 usr$c5_1 usr$h_3 var_b_28717_mpos usr$c3_2 usr$r4_3 usr$a0 usr$c5_1 usr$a1 usr$a2 usr$r3_2 usr$r5_3 usr$c4_2 var_b_28717_mpos usr$c2_1 usr$updatedCarry ]
No memoryguard was present. Consider using memory-safe assembly only and annotating it via 'assembly ("memory-safe") { ... }'.
YulException: Cannot swap Variable usr$a3 with Variable usr$updatedCarry: too deep in the stack by 1 slots in [ var_result_28726_mpos RET usr$p usr$a3 var_modulus_mpos usr$r6_2 usr$c5_1 usr$h_3 var_b_28717_mpos usr$c3_2 usr$r4_3 usr$a0 usr$c5_1 usr$a1 usr$a2 usr$r3_2 usr$r5_3 usr$c4_2 var_b_28717_mpos usr$c2_1 usr$updatedCarry ]
No memoryguard was present. Consider using memory-safe assembly only and annotating it via 'assembly ("memory-safe") { ... }'.

[cameel]

Interestingly this one compiled on 0.8.25. So it's more of a data point for the new sequence.

No memoryguard was present.

Have you tried making it memory-safe?

[karmacoma-eth]

@cameel not yet, there are dozens of assembly blocks and I need to check with the original author. We're going to pin back to 0.8.25 while we investigate