Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize stack height check #420

Open
chfast opened this issue Jan 17, 2022 · 1 comment
Open

Optimize stack height check #420

chfast opened this issue Jan 17, 2022 · 1 comment
Labels
optimization Iproves performance without functional changes

Comments

@chfast
Copy link
Member

chfast commented Jan 17, 2022

Most of EVM instruction need to check EVM stack height before execution to report stack overflow/underflow errors.

In the current implementation the stack height value is computed by subtracting stack top and stack bottom pointers.

bool check1(uint256* top, const uint256* bottom)
{
    auto size = static_cast<int>(top - bottom);
    return size >= 2;
}
check1(uint256*, uint256 const*): # @check1(uint256*, uint256 const*)
  sub rdi, rsi
  shr rdi, 5
  cmp edi, 2
  setge al
  ret

It looks like only single subtraction is need, but this is not true. Pointers address bytes but uint256 type is 32 bytes in size. Therefore, additional division by 32 (shr rdi, 5) is needed to compute the stack height. Knowing this, we can request the stack height in bytes (stack size?). That eliminates the need for the division.

bool check2(uint256* top, const uint256* bottom)
{
    auto size = static_cast<int>((top - bottom) * sizeof(uint256));
    return size >= int(2 * sizeof(uint256));
}
check2(uint256*, uint256 const*): # @check2(uint256*, uint256 const*)
  sub edi, esi
  cmp edi, 64
  setge al
  ret

Obviously, we could track stack height with an integer because instruction implementations do not need to know the value (only stack requirement check does).

bool check3(uint256* bottom, int stack_height)
{
    return stack_height >= 2;
}
check3(uint256*, int): # @check3(uint256*, int)
  cmp esi, 2
  setge al
  ret

https://godbolt.org/z/qaE3zn3Ye

@chfast chfast added the optimization Iproves performance without functional changes label Jan 27, 2022
@chfast
Copy link
Member Author

chfast commented Oct 26, 2022

The #518 is doing

bool check4(uint256* top, const uint256* bottom)
{
    return top >= bottom + 2;
}

https://godbolt.org/z/ffWqMGTs3

We still may want to try tracking stack height as dedicated int (check3).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
optimization Iproves performance without functional changes
Projects
None yet
Development

No branches or pull requests

1 participant