The Yul optimizer causes mstore results to be inconsistent.

Subway2023 commented 2 weeks ago

Environment

Compiler version: 0.8.26
Target EVM version (as per compiler settings): None
Framework/IDE (e.g. Truffle or Remix): None
EVM execution environment / backend / blockchain client: None
Operating system: Linux

Steps to Reproduce

{
    function f(a, b) -> x { 
        x := add(b, a) 
    }
    function g() -> y { 
        y := mload(0) 
        mstore(0, 4) 
    }
    let i := 0
    for {} lt(i, 2) { i := add(i, 1) } 
    {
        let x := 1337
        if lt(i, 1) {
            x := 42
            continue
        }
        mstore(0, x)
    }
    let r := f(g(), mload(0))
    sstore(0, r)
}

Get Bin

normal

solc-0826  --strict-assembly --bin test.yul
5f5b60028110601a5760165f5160126037565b6033565b5f55005b600190610539828210602e575f525b016001565b506029565b0190565b5f519060045f5256

optimize

solc-0826  --strict-assembly --optimize --bin test.yul
5f5b600281106010575f5180015f55005b6001906105398282106024575f525b016001565b50601f56

Run in EVM

normal

go-ethereum/build/bin/evm --debug --json --code 5f5b60028110601a5760165f5160126037565b6033565b5f55005b600190610539828210602e575f525b016001565b506029565b0190565b5f519060045f5256 run

optimize

go-ethereum/build/bin/evm --debug --json --code 5f5b600281106010575f5180015f55005b6001906105398282106024575f525b016001565b50601f56 run

Execution result analysis

normal

output,storage,memory
{'output': '', 'gasUsed': '0x575c'},{'0': '2674'},{'0': '4'}

optimize

output,storage,memory
{'output': '', 'gasUsed': '0x571c'},{'0': '2674'},{'0': '1337'}

The data at position 0 is different. The suspected cause is that mstore(0, 4) was incorrectly optimized away.

ekpyron commented 2 weeks ago

The evaluation order in Yul is right-to-left (inherited from the argument order on stack on the EVM), so in f(g(), mload(0)), mload(0) is evaluated before g(). Hence also, as seen in the storage trace, the value of r in both cases is the same.

The Yul optimizer inlines both f and g, after which it can prove that memory offset 0 is never read after the mstore(0,4). Hence it can validly remove it - memory is local to the call frame, so if it is not read again, it's semantically unobservable and thus redundant. So yes, the mstore(0,4) is optimized away here, but that's valid.

Subway2023 commented 2 weeks ago

The evaluation order in Yul is right-to-left (inherited from the argument order on stack on the EVM), so in f(g(), mload(0)), mload(0) is evaluated before g(). Hence also, as seen in the storage trace, the value of r in both cases is the same.

The Yul optimizer inlines both f and g, after which it can prove that memory offset 0 is never read after the mstore(0,4). Hence it can validly remove it - memory is local to the call frame, so if it is not read again, it's semantically unobservable and thus redundant. So yes, the mstore(0,4) is optimized away here, but that's valid.

I don't think the bug is in f(g(), mload(0)) or mload(0), because I replaced it with let a := g(), and the inconsistency still persists.

{
    function g() -> y { 
        y := mload(0) 
        mstore(0, 4) 
    }
    let i := 0
    for {} lt(i, 2) { i := add(i, 1) } 
    {
        let x := 1337
        if lt(i, 1) {
            x := 42
            continue
        }
        mstore(0, x)
    }
    let a:=g()
    sstore(0, mload(0))
}

ekpyron commented 2 weeks ago

The evaluation order in Yul is right-to-left (inherited from the argument order on stack on the EVM), so in f(g(), mload(0)), mload(0) is evaluated before g(). Hence also, as seen in the storage trace, the value of r in both cases is the same. The Yul optimizer inlines both f and g, after which it can prove that memory offset 0 is never read after the mstore(0,4). Hence it can validly remove it - memory is local to the call frame, so if it is not read again, it's semantically unobservable and thus redundant. So yes, the mstore(0,4) is optimized away here, but that's valid.

I don't think the bug is in f(g(), mload(0)) or mload(0), because I replaced it with let a := g(), and the inconsistency still persists.
{
    function g() -> y { 
        y := mload(0) 
        mstore(0, 4) 
    }
    let i := 0
    for {} lt(i, 2) { i := add(i, 1) } 
    {
        let x := 1337
        if lt(i, 1) {
            x := 42
            continue
        }
        mstore(0, x)
    }
    let a:=g()
    sstore(0, mload(0))
}

In this new snippet, the optimizer will resolve the mload(0) to the value 4, since it knows that's necessarily what's stored at memory offset zero - with that the mload(0) within the sstore vanishes - which leaves an mstore(0, 4) that is no longer read from and thereby also redundant and can subsequently be removed. So it's still valid optimizations. The yul optimizer generally doesn't make any guarantees about the state of memory at the end of the call frame (since memory doesn't persist) - so memory writes are only preserved if they can possibly be read from by any subsequent instruction/code path.

ekpyron commented 2 weeks ago

If, for some reason like debugging, you don't want these memory writes to be removed, you can provide a custom Yul optimizer sequence not involving the UnusedStoreEliminator (in the sequence denoted as S). (For example https://soliditylang.org/blog/2024/05/21/solidity-0.8.26-release-announcement contains some explanation of the default optimizer sequence and how to change it.) But the cases so far appear to be valid optimizations and don't seem to constitute optimizer bugs.

ethereum / solidity