EIP-663: Unlimited SWAP and DUP instructions

Pushed this as “Option A+” to the EIP to make discussion clearer: https://github.com/ethereum/EIPs/pull/2235

I think we can agree that “Option A” should not be accepted.

Question about “Option A+”: if this option is considered, do we want to introduce a validation stage?

Also because it ruins one of the good things about stack machines:

http://troubles.md/posts/wasm-is-not-a-stack-machine/

There were some earlier discussions on the same topic here: https://github.com/ethereum/EIPs/issues/174

Probably nothing was mentioned there what didn’t came up on this thread, but still good to have a reference.

Thing have been quiet here for too long. With EIP-615 on indefinite hold I’d like to see this one get into the clients fairly soon, @axic.

There was no progress made here beyond me updating the draft to reflect all the discussions.

Any reason not to put it on the core dev’s agenda?

What is the point putting it on agenda if no progress has been made? There are some open questions.

OK. Guess we need to close the questions. With the EIP-2315 subroutine proposal (rather than EIP-615) they look a lot more useful.

Updated this EIP to be dependent on EIP-3540 and thus able to use immediates. This simplified the proposal significantly.

The current version is set to use an 8-bit immediate, allowing access to the top 256 items out of the total 1024 depth.


Since some old historical sections (i.e. References) have been removed according to current guidelines, here’s a copy of it:

A similar proposal was made with EIP-174. Read the thread for some detailed discussion.

Rootstock RSKIP26 also introduced SWAPN and DUPN with Option A described above.

2 Likes

One question in the proposal:

We introduce the variable n which equals to imm + 1 .

Should n equals to imm + 17? Since n = 1…16 cases are already covered by existing opcodes.

One way to ease the verification issue is to introduce a stack counter variable (sc), and the following opcodes:

ADD_SC16
ADD_SC32
ADD_SC64
ADD_SC128
which will accumulate sc variable with the corresponding value.

When calling the existing DUPx/SWAPx , x in 1…16, opcodes, it will actually do DUPx/SWAPx with the stack variable at position x + sc. After calling DUPx/SWAPx, sc will be reset to 0.

Examples:

Two opcodes

ADD_SC16 DUP1 = DUP17

ADD_SC16 DUP16 = DUP32
ADD_SC32 DUP1 = DUP33

ADD_SC32 DUP16 = DUP48

Three opcodes

ADD_SC32 ADD_SC16 DUP1 = DUP49

ADD_SC32 ADD_SC16 DUP16 = DUP64
ADD_SC64 DUP1 = DUP65

ADD_SC64 ADD_SC32 DUP16 = DUP112

Four opcodes

ADD_SC64 ADD_SC32 ADD_SC16 DUP1 = DUP113

ADD_SC128 ADD_SC64 ADD_SC32 DUP16 = DUP240

where

  • using 2 opcodes (the same amount as DUPn + 1 byte of n), we could address up to 48th stack variables
  • using 3 opcodes (the same amount as PUSH1 + 1 byte of n + DUPn), we could address up to 112th stack variables
  • using four opcodes, we could address up to 240th stack variables.

In most cases, I think even addressing up to 48th stack variables should solve most of stack too deep issues as developers frequently experience.

Note that we may impose the restriction that an ADD_SCx opcode must follow with another AD_SCx or DUP/SWAP opcode for better static analysis.

For the record, I’d love to see this picked up again and be considered for inclusion for the initial EOF version :-). For us in Solidity, resp. actually for Yul, this would simplify things a lot and make it much easier to generate simpler and more optimal code. If there’s interest and it helps, I could look into producing some stats about this, let me know.

1 Like

That’s actually a pretty nice proposal. Originally the idea was that one could just keep using SWAPN/DUPN` only, but since it has immediates, they are fixed just like the existing ones. I think it would make sense following your suggestion.

@ekpyron @chfast wdyt?

2 Likes

For the record (we also discussed this offline): We could work with it either way, but starting from 17 for the immediate argument opcodes and thus avoiding to have multiple opcodes with the same behaviour, also seems reasonable to me.

Probably more useful than SWAP_N would be SWAP_N_M, which takes two immediates and swaps the n’th and m’th stack items. This is important for stack scheduling as right now swapping the nth and mth items takes three instructions.

1 Like

IMO there is no problem with having redundant instructions. Starting from 17 (i.e., SWAP_N 1 actually meaning SWAP17) would be a source of confusion and footguns, forever. The fact that the SWAP and DUP instructions were originally designed without immediates should not lead to a confusing design for the new instructions. Having the redundant instructions also provides a forward path for phasing out the old instructions, if that becomes attractive in the future.

The EIP was updated to reflect this and the wording was improved to be overall more clear: Clarifications to EIP-663 by axic · Pull Request #6055 · ethereum/EIPs · GitHub

I think this would be a worthy idea to explore.

Since most of us weren’t too decided (mostly just slightly in favour) about this and there was already a more concerned voice before yours, I think we are leaning towards not taking the +17 offset.

The rationale read like:

The offset 17 was chosen to avoid these new instructions overlapping with the existing DUP? and SWAP? instructions, which are cheaper to deploy because they take a single byte. Having the overlap provides little benefit, and likely would see very little use.

We did consider “deprecating” the old opcodes, but that could realistically only happen within EOF, and it felt like a harsh change due to the increased code size limit it would cause.

Well, I did not really mean that the old opcodes should be deprecated immediately. But at some point code size constraints may be less important. In any case, in the meantime, I don’t see the conceptual complexity that will stem from N starting from 17 to justify having an extra 16 possible addressable items.

Maybe more fun than taking two immediate bytes would be taking 1 byte immediate. The high nibble represents N and the low nibble represents M.