Stack Shift
Moves every stack access above some point by a fixed number of bytes.
Where this happens
StackShift::find and StackShift::apply in codegen/optimizations/helpers/stack_shift.rs.
Rationale
Some optimizations add or remove stack space
This means we need to adjust all instructions.
Say we remove the return address, like Return Slot Elimination does.
So everything from entry ESP + 4 (argument 0) moves down by 4. That +4 is the boundary.
One function, top to bottom:
sub esp, 4 ; make room for a local
mov ecx, [esp] ; the local
mov eax, [esp+8] ; argument 0
lea edx, [esp+12] ; points at argument 1
mov eax, [edx] ; reads argument 1
mov edx, 0 ; drops the pointer
add esp, 4
ret 8
sub esp, 4
mov ecx, [esp] ; below the boundary: stays put
mov eax, [esp+4] ; moved down 4
lea edx, [esp+8] ; moved down 4
mov eax, [edx] ; follows the pointer: no change needed
mov edx, 0
add esp, 4
ret 8 ; count unchanged, see below
How we shift
We use Stack Tracking to first get ESP and EBP before each instruction.
Afterwards, we use that information to shift every instruction.
| Entry ESP offset | Holds | Shifted? |
|---|---|---|
| -4 | a local | no |
| +0 | return address | no |
| +4 | argument 0 | yes |
| +8 | argument 1 | yes |
The original esp+0 acts as the boundary. Anything above shifted, below not shifted.
Works with (almost) any instruction, e.g.
add [esp+4], eaxorfld qword [esp+8]
Some instructions aren't supported
A few can reach memory past the address they name.
Like bt [esp], ecx, which reads [esp+4] when ECX is 32.
Moving lea
lea can be moved too, but we need to be careful with it.
That address could go anywhere, like into another function. So we follow the register that receives its result, and give up if we lose track of it.
lea eax, [esp+4] ; moves to [esp+8]
mov ecx, [eax+4] ; reads argument 1, still correct
mov eax, 0 ; pointer gone: safe
Particulatly, we look for this 👆. Where the register is overwritten entirely.
An extra rule applies. As per above, all uses must stay on same side of the [esp+0] boundary, per rule above.
lea eax, [esp+0] ; unsafe!
mov ecx, [eax+4] ; unsafe because above is unsafe!
Copies, like mov edx, eax or lea edx, [eax+4], and changes, like add eax, 4, aren't supported.
Giving up
We change nothing if we see:
- ESP, or EBP while it points into the stack, used:
- As a value, like
mov eax, esp. - As an index, like
[esp+ecx*4].
- As a value, like
- An access we can't shift safely:
- One crossing the boundary, like a 4-byte read at
+2. - An unsupported instruction, like
bt [esp], ecx. - A
leapointer we lose track of.
- One crossing the boundary, like a 4-byte read at
push,pop,leaveorrettouching the shifted area.- A
call. - When shifting down, anything but
retusing the space we move into.
Applying the shift
Call find, then apply with the same model.
ret N is unchanged. So an optimization changing the stack size will need to do it manually.