Extend DUP1-16 / SWAP1-16 With DUPN / SWAPN

[mattdf]

Motivation

The fixed limit on stack referencing through the current DUP and SWAP operations limits the usability of the stack when writing compilers that target the EVM, as at most you can only access memory 17 levels deep. A solution that makes efficient use of the stack and allows for a higher number of local variables becomes needlessly complicated as beyond 17 levels the implementation needs to start storing things in memory instead.

Specification

Introduce two new opcodes, DUPN and SWAPN that take one integral argument, N, where DUPN duplicates the N'th stack item to the top of the stack, and SWAPN swaps the first stack item with the N'th stack item.

An argument N > the number of items on the stack should cause the program to terminate with a stack underflow, as it does currently for the SWAP#/DUP# set of instructions.

The gas cost for these operations should remain Wverylow, seeing as there is no real difference as the stack for a contract needs to be held in memory while executing either way, and the gas limit would likely be hit before the stack size would become a problem.

[gcolvin]

Agreed.  Is a dynamic value on the stack needed, or would two
  bytes of immediate data do the trick?  Dynamic operations can be
  much harder to analyze.

On 11/8/16 7:09 AM, Matthew Di Ferrante
  wrote:


  Motivation
  The fixed limit on stack referencing through the current DUP
    and SWAP operations limits the usability of the stack when
    writing compilers that target the EVM, as at most you can only
    access memory 17 levels deep. A solution that makes efficient
    use of the stack and allows for a higher number of local
    variables becomes needlessly complicated as beyond 17 levels the
    implementation needs to start storing things in memory instead.
  Specification
  Introduce two new opcodes, DUPN and SWAPN
    that take one integral argument, N, where DUPN
    duplicates the N'th stack item to the top of the stack, and SWAPN
    swaps the first stack item with the N'th stack item.
  An argument N > the number of items on the stack should
    cause the program to terminate with a stack underflow, as it
    does currently for the SWAP#/DUP# set
    of instructions.
  The gas cost for these operations should remain Wverylow,
    seeing as there is no real difference as the stack for a
    contract needs to be held in memory while executing either way,
    and the gas limit would likely be hit before the stack size
    would become a problem.
  —
    You are receiving this because you are subscribed to this
    thread.
    Reply to this email directly, view it on
      GitHub, or mute
      the thread.







  {"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/ethereum/EIPs","title":"ethereum/EIPs","subtitle":"GitHub repository","main_image_url":"https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/ethereum/EIPs"}},"updates":{"snippets":[{"icon":"DESCRIPTION","message":"Replace DUP1-17 / SWAP1-17 With DUPN / SWAPN (#174)"}],"action":{"name":"View Issue","url":"https://github.com/ethereum/EIPs/issues/174"}}}

[mattdf]

@gcolvin Two bytes of immediate data would be preferable and easier to implement from a compiler perspective as well. If function calls / frame compilation are implemented properly there should be no stack additions in terms of new variable declarations in the middle of a call frame hence all stack references should be able to be addressed with static offsets.

[vbuterin]

I would also strongly prefer two bytes of immediate data. I support that version.

[mattdf]

If possible, it would be great if this could be rolled out with Metropolis, as it would make writing compilers / optimizations much easier.

In terms of implementation complexity, the major clients I looked at (parity, geth) already use functions which can swap/dup at arbitrary places, so it would in essence just be a matter of registering a new opcode in the instruction dispatch that takes the fixed size argument.

[chriseth]

Please correct me if I'm wrong but I think this proposal severely limits the abilities for static analysis and just in time compilation. If the following snippet is present anywhere in the code and there is at least one dynamic jump, you can basically make no assumptions about stack content:

JUMPDEST
SWAP500

If we want to have an efficient EVM, we have to limit the access to the stack. Stack is as cheap as it currently is because we can more or less assume that it is always in cache or even in registers. If we allow constant access to the full stack, this is not the case anymore. There is a proposal to add "subroutine jumps" which have to make promises about how much of the stack they can modify and I don't think these two proposals are compatible.

[mattdf]

I disagree. I don't see why this would make it difficult. It would just make the implementation different. The JVM and pretty much all other instruction set architectures support arbitrary stack access, and JIT is still possible there. You can limit the total stack size to some power of 2 and use that in your JIT / analysis if needed.

There are many other cases where the stack content can be made unpredictable by loading on-chain data right after jumps, or loading in current block metadata.

The arbitrary limitation is yet another barrier to writing efficient compilers that target the EVM, and that is a far more important, because for the ecosystem to grow there needs to be more than one or two high level languages that can target it.

If you want to make promises for how much stack "subroutine jumps" can access, set the limitation in the jump? I don't see why these two proposals are mutually exclusive. You can set it such that any subroutine jump marks a page of 1KB (or whatever) as accessible and access beyond that becomes a page violation.

[chriseth]

The JVM does explicitly not allow arbitrary stack access. I am pretty sure that efficient JITing of methods in the JVM relies on the fact that local variables in the caller cannot be modified by the callee.

The current EVM does not have this promise.

I'm not saying we should not have arbitrary stack access, we should just be careful about what exactly we allow.

[mattdf]

Then would amending the proposal to allow enforcement similar to the JVM in terms of not modifying variables outside the callee's frame address your concerns? The total stack size could be a default EVM limit like it is on the default stack page in modern OS, or it could be set by an additional instruction for which the gas cost scales with the page size, either way you would have an explicit limit that can be used in analysis.

From the perspective of supporting as many constructs as possible I would make the case that the EVM should at least allow access to the entire stack (up to a certain page size), even if it doesn't allow the callee to modify caller variables, so you can at least implement constructs like closures.

Do you see any issues with it working as described above?

[chriseth]

I think it is really hard to come up with the correct gas costs for such things.

Concerning how to implement closures: Static access from the stack top also will not help you there, because the stack depth will change in calls. Furthermore, you might also want those variables to live on beyond the point where the function returns. So the only nice way I see to implement closures is by moving some stack variables to memory. This is a feature that is convenient anyway for a compiler to implement and as soon as you have this feature, you don't need arbitrary stack access anymore...

[mattdf]

To be fair, it's a hassle to manage when all opcodes return onto the stack and load from the stack, since the EVM doesn't have the ability to have opcode arguments be loaded directly from memory.

It's definitely possible but it's extra work that could be remedied by changing the ISA - and if it wasn't significant extra work, I'm sure Solidity would have support for more than 16 variables inside functions - which it doesn't now.

[chriseth]

No need to tell me :-)

[gcolvin]

The proposal to replace dynamic jumps with static jumps and subroutines should eliminate any problems with static analysis and compiling; if it doesn't, that's a problem with the proposal. But we are still working on it. And I doubt this will cause significant performance problems. EVM stack items are too big and EVM arithmetic and interpretation too expensive for even one or two stack items to stay in registers for long, but the whole stack will easily live in the megabytes of cache on a typical CPU, so mostly we are looking at which level of cache which part of the stack is in when needed. All of cache is a lot better than RAM, so I think at worst DUPN and SWAPN would make it a little easier to write programs that perform a bit worse. But the intended use of the feature would probably bounce between the top of the stack where computation is happening and lower down where variables are stored, keeping both parts of the stack "hot" and in the faster levels of cache.

[axic]

Sorry I haven't seen this issue when creating #663.

[gcolvin]

I still think that if #615 is accepted this will be unnecessary.

[SergioDemianLerner]

You could adopt the RSK standard for DUPN and SWAPN, which receives arguments in the stack.
You can check this code here:
https://github.com/rsksmart/rskj/blob/master/rskj-core/src/main/java/org/ethereum/vm/VM.java#L953

This way we could keep in sync ETH with RSK.

[mattdf]

I'm going to revive this because this limit in the EVM (and solidity by extension) is honestly such a pain when you're trying to do anything non-trivial, especially when feeding in things like signatures for EC operations...

@gcolvin why does #615 make this EIP unnecessary?

[gcolvin]

@mattdf #615 divides up the stack into subroutines and provides opcodes to get at all the variables in a subroutine. So does #48. This is of course a smaller change.

[mattdf]

What's the timeline for something like #615 making it into the protocol?

[gcolvin]

@mattdf I'd say #48 is more likely, but there is no real process for deciding these things, so I can't guess at a timeline. If you want #174 to go through you need to write up a proper EIP and make a PR.

[axic]

Please note there is a "proper EIP" written under #663 (I didn't notice this one when I wrote it), though that proposes to take the last stack item as index.

Benefit of that is that tools wouldn't need to be upgraded to support another immediate opcode (which for some reason seems to be the preferred way), downside is it goes against static analysis. I am actually in favour of having it as immediate.

[mattdf]

It doesn't make much difference to me whether N is inline or a stack arg, so I'd support the construction #663 for immediate merge as well. When using complex bn/crypto related functions this limit becomes a nightmare.

[gcolvin]

#663 could pretty easily be changed to specify an immediate, which I also prefer.

[HarryR]

So basically this is getting shelved until WASM comes along, at which point it will become a non-issue?

Makes sense, and the ABIv2 encoder is making things workable in the meantime.

[axic]

@mattdf #663 was merged as a draft quite a while ago and it proposes the same (my earlier comment here when I've realised the duplicate work)

There's a discussion URL for 663 here: https://ethereum-magicians.org/t/eip-663-unlimited-swap-and-dup-instructions/3346/20

Added references to this issue in the merged EIP. What do you think about closing this?

[axic]

Since https://eips.ethereum.org/EIPS/eip-663 is discussed during Istanbul/Berlin, I think this thread here should be closed to avoid confusion.

@mattdf please let me know if you think otherwise and this issue can be reopened.