solidity
solidity copied to clipboard
ethereum
[OptimizedEVMCodeTransform] ICE due to "Could not create stack layout after 1000 iterations"
{
function f() -> o1, o2, o3, o4, o5, o6, o7, o8, o9, o10, o11, o12, o13, o14, o15, o16, o17, o18
{
for {} o13 { o18 := add(o1,0) } {
if eq(o4, 0) {
o7 := 0
{
for {o1 := 2} o13 {} { {leave} }
}
}
o9 := o6
}
}
}
throws
https://github.com/ethereum/solidity/blob/55467c1ccaffd5fcf6ea988d5e091d468a08f533/libyul/backends/evm/StackHelpers.h#L121
The fuzzer upstream reported this bug (see https://github.com/ethereum/solidity/blob/55467c1ccaffd5fcf6ea988d5e091d468a08f533/test/tools/ossfuzz/strictasm_assembly_ossfuzz.cpp#L49)
I could not reproduce via solc CLI.
Oh, "nice"! That's likely a real proper bug in the stack shuffling then :-)
Can be reproduced by the following as test/libyul/evmCodeTransform/ test:
function f() -> o1, o2, o3, o4, o5, o6, o7, o8, o9, o10, o11, o12, o13, o14, o15, o16, o17, o18
{
for {} o13 { o18 := add(o1,0) } {
if eq(o4, 0) {
o7 := 0
{
for {o1 := 2} o13 {} { {leave} }
}
}
o9 := o6
}
}
}
// ====
// stackOptimization: true
// ----
Out of curiosity: did you change the fuzzing in some way or is it pure coincidence that this only comes up now? The stack shuffling hasn't changed for quite a while... May very well be that it only occurs in very specific cases and that's why it took a long time, but not sure...
Anyways, I actually find it reassuring that the fuzzer is able to come up with this - when we started fuzzing this, I was actually surprised that this error never came up, but this report now seems to indicate that fuzzing works :-).
Ah, ok, interesting... This is also a "StackTooDeep" case... The stack shuffling algorithms wants to do a too-deep-swap, but tries to avoid it, since it's too-deep - and then hits a swapping cycle because of that...
Actually not sure if I should try to fix this in the shuffling algorithm or instead just have shuffling abort early on stack issues (either way this will ultimately report a stack too deep error, it's currently just disguised)
Might actually be nice to keep this open despite https://github.com/ethereum/solidity/pull/12572... While https://github.com/ethereum/solidity/pull/12572 "fixes" this to a regular stack-too-deep error, theoretically, it would be possible to generate code for this without a stack-too-deep, it'd just require some trickery that's beyond the current setup...
Out of curiosity: did you change the fuzzing in some way or is it pure coincidence that this only comes up now?
I would tend to think it is co-incidence but will take a closer look.
Anyways, I actually find it reassuring that the fuzzer is able to come up with this - when we started fuzzing this, I was actually surprised that this error never came up, but this report now seems to indicate that fuzzing works :-).
It is possible that the fuzzer that actually detected this issue took a long time because it is not semantics-aware (simply mutates raw bytes treating yul input as a binary stream). On the other hand, the semantics-aware fuzzer does not probe the new code transform if old code gen contains a stack too deep error. We are doing this so we can compare blockchain state (which requires a baseline i.e., old codegen).
https://github.com/ethereum/solidity/blob/3f401ebd42acae24c9bd6d800fa7f7dd3433b9f2/test/tools/ossfuzz/StackReuseCodegenFuzzer.cpp#L91
Another possibility is that this was undetected because the semantics-aware fuzzer only tests Yul optimizer + New code transform but the non semantics-aware fuzzer that found this issue only tested the new code transform i.e., assembling without optimization.
Closing this, since the concrete issue should have been fixed by https://github.com/ethereum/solidity/pull/12572
This is a big test that triggers the underlying ICE. Sorry for the bad formatting, if there is a tool I could use to auto-format yul files, I would do it.
https://gist.github.com/bshastry/a796b1c6f824b386750a9911160ab2e1
if there is a tool I could use to auto-format yul files, I would do it.
The compiler can do it. I wonder if it would be a good idea to expose it somehow.
if there is a tool I could use to auto-format yul files, I would do it.
The compiler can do it. I wonder if it would be a good idea to expose it somehow.
Thanks for the hint! Here's a much better formatted program albeit heavily indented and less readable due to it
{
let x
for { } calldataload(0) { }
{
{
{
{
{
{
for { } calldataload(0) { }
{
if callvalue() { break }
mstore(x, 0x42)
for { } calldataload(0) { }
{
{
x := 1
for { } calldataload(0) { }
{
{
{
if callvalue()
{
{
{
{
x := 2
for { } calldataload(0) { }
{
if callvalue()
{
{
{
{
{
{
if callvalue()
{
x := 2
{
{
sstore(4, exp(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe, 1))
sstore(6, exp(not(0), 1))
sstore(7, exp(0xffffafffffffffffffffffffffffffff, 2))
sstore(8, exp(0xffffffffffffffff, 2))
sstore(9, exp(0xf, 3))
sstore(13, exp(0xffffffffffffffff0000000000000000, 3))
sstore(14, exp(2, 6))
sstore(15, exp(2, 255))
{
{
if callvalue()
{
{
{
{
for { } calldataload(0) { }
{
if callvalue()
{
{
{
{
{
{
{
for { } calldataload(0) { }
{
if callvalue() { x := 2 }
mstore(x, 0x42)
}
if callvalue()
{
{
if callvalue()
{
x := 2
mstore(x, 0x42)
}
sstore(4, exp(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe, 1))
sstore(6, exp(not(0), 1))
sstore(7, exp(0xffffafffffffffffffffffffffffffff, 2))
sstore(8, exp(0xffffffffffffffff, 2))
sstore(9, exp(0xff, 3))
sstore(13, exp(0xffffffffffffffff0000000000000000, 3))
sstore(14, exp(2, 256))
sstore(15, exp(2, 255))
}
sstore(2, 3)
}
}
if callvalue() { x := 3 }
}
}
}
mstore(x, 0x42)
}
break
}
}
mstore(x, 0x42)
}
x := 3
}
}
}
}
}
}
}
}
}
}
}
}
}
break
}
}
}
}
mstore(x, 0x42)
}
}
break
}
}
if callvalue() { break }
}
mstore(x, 4)
}
}
}
mstore(x, 0)
}
}
break
}
}
}
}
}
}
I wouldn't say it's less readable. It's still hard to read of course but I think the unindented version was much worse because you could not see the structure at all.
I created #13550 for the formatter. Should be trivial to implement, but it's a very tangential thing so I think we should discuss on the call whether we want to add things like this to the compiler.
Same as https://github.com/ethereum/solidity/issues/13224 - it's just a different example case. (But we already established that they don't have exactly the same cause, just the same effect, so it's a separate issue.)