Skip to content

x87

This optimisation is basically a lot of analysis of x87 code, and hints for clang.

With these hints, based on my testing, clang is able to output code with equivalent performance to simply converting the x87 code to plain C doubles.

Where this happens

run in codegen/optimizations/x87/mod.rs.

Complex page.

My head burnssssssss. aaaaaaaaa A bunch of this probably needs a redo- it became 🍝 ; and overkill in parts. Sowwy 👉👈.

Code for this is really ass.

EXPERIMENTAL.

THIS CODE SUCKS.
THIS CODE SUCKS.
THIS CODE SUCKS.

I usually craft beautiful code people can learn from. This specific optimisation isn't that.
Do not use this as inspiration.

Approach is correct, docs are good.
But the code sux; and I'm really not happy with it.

This is a prototype chucked into production due to time constraints.
Because it was simply too much perf... forgive me.

Once again, 12h a day, for 3 months...

adbywuadgwyaudgywadwhu

Summary

x87 code works on a stack.

float mul_sums(float a, float b, float c, float d)
{
    return (a + b) * (c + d);
}
;                            #stack  st0          st1
fld   dword ptr [esp+4]    ; 1       a
fadd  dword ptr [esp+8]    ; 1       a+b
fld   dword ptr [esp+12]   ; 2       c            a+b
fadd  dword ptr [esp+16]   ; 2       c+d          a+b
fmulp st(1), st            ; 1       (a+b)*(c+d)
ret                        ;         <- returned in st0

Usually on cdecl & stdcall, we pass an empty x87 fpu stack to each function.
Parameters are loaded from stack parameters, and return values are returned by st(0).

You can play this to your advantage, if you play your cards ♠️♥️♦️♣️ right.

The Problem

clang doesn't know the x87 stack is empty on entry.

Normally, our recompiled code keeps the x87 stack in ctx.fpu:

struct X87FPU {
    double   st[8];   // st0 = st[top], st1 = st[top + 1]
                      // fld a: top = 7, st[7] = a
                      // fld b: top = 6, st[6] = b

    uint16_t top;     // counts down on push
    uint16_t cw;      // control word
    uint16_t sw;      // status word
    uint8_t  tag[8];  // per slot: 0 = full, 3 = empty
};

All of this state, such as the cw, sw, and tag array need updating if we do 'proper' x87 stack emulation. Hella expensive, hella slow.

Booooooring!

However, because the x87 fpu stack resets between most functions, we can exploit that.
And, with clever hinting- make clang skip a lot of the stack and flag work.

Example

We tell clang the stack is empty:

__builtin_assume(ctx.fpu.top == 0);
__builtin_assume(ctx.fpu.tag[0] == 3); // empty
// ... same for tag[1] to tag[7]

This is what X87_ASSUME_DEPTH(fpu, 0) expands to.

; fld dword ptr [esp+4]
mov    eax, dword ptr [rdi + 296]       ; read top
dec    eax
and    eax, 7                           ; slot = (top - 1) & 7
mov    word ptr [rdi + 296], ax         ; write top
; ...                                   ; build status word
cmp    byte ptr [rdi + rax + 302], 3    ; slot empty?
je     .ok
movsd  xmm0, qword ptr [.NaN]           ; no: overflow, push NaN
jmp    .done
.ok:
cvtss2sd xmm0, xmm0                     ; yes: push the value
.done:
mov    word ptr [rdi + 300], cx            ; write status word
movsd  qword ptr [rdi + 8*rax + 232], xmm0 ; st[slot] = value
mov    byte ptr [rdi + rax + 302], 0       ; tag slot full
; fld dword ptr [esp+4]
mov    word ptr [rdi + 296], 7          ; top = 7
or     byte ptr [rdi + 301], 56         ; status word
cvtss2sd xmm0, xmm0
movsd  qword ptr [rdi + 288], xmm0      ; st[7] = value
mov    byte ptr [rdi + 309], 0          ; tag st[7] full

And this is basically what we're cooking.
A suite of optimisations and hints just like this.

Make enough of them, and we equal plain C doubles in perf.

What we return

For each function, this optimisation pass decides two things:

  • Opt level: nothing/hints/local copy.
  • What to add at certain instructions: e.g. a reload right after a call.

Returned as an X87Plan:

struct X87Plan {
    level: X87Level,                                   // the whole function
    instructions: BTreeMap<GuestAddress32, X87Sync>,   // single instructions
}

enum X87Level {
    // Left as it is.
    Original,

    // Runs on `ctx.fpu`.
    // Starts with `X87_ASSUME_DEPTH(ctx.fpu, 0)`: the stack is empty.
    Hints,

    // Runs on a local copy of `ctx.fpu`.
    // Starts with `X87FPU fpu = x87_copy(ctx.fpu);` and `X87_ASSUME_DEPTH(fpu, 0)`.
    LocalCopy,
}

// Extra code for one instruction. Each number is `#stack` at that point.
struct X87Sync {
    // Before the instruction
    assume: Option<u8>,       // tell clang: "the stack holds N values"
    local_to_ctx: Option<u8>, // leaving the function: copy N values -> ctx.fpu

    // Instead of the instruction
    ffree_pops: bool,         // write this `ffree` as a pop

    // After the instruction
    ctx_to_local: Option<u8>, // once the call returns: ctx.fpu -> copy, N values

    // Around its mid-assembly hook
    hook: Option<HookSync>,   // copy -> ctx.fpu, hook runs, ctx.fpu -> copy
}

e.g.

  • assume: Some(2) writes X87_ASSUME_DEPTH(fpu, 2) before instructions

Counting the stack

X87Analysis::build in codegen/optimizations/x87/stack_depth/.

These aren't 'steps' per-se, i.e. 1 & 2 happen together. Step 3 just says 'repeat'.

But it's easier (for me) to reason about it as 'steps'.

We'll use mul_sums as an example

1. Count the stack in each function

We follow each function's control flow, and track #stack at every instruction:

mul_sums:                     ; #stack
    fld   dword ptr [esp+4]   ; 0 -> 1
    fadd  dword ptr [esp+8]   ; 1
    fld   dword ptr [esp+12]  ; 1 -> 2
    fadd  dword ptr [esp+16]  ; 2
    fmulp st(1), st           ; 2 -> 1
    ret                       ; exits with 1

So calling mul_sums pushes 1 value.
We save what calling each function does to the stack as an X87Effect:

struct X87Effect {
    stack_at_entry: u8, // #stack at function entry: its x87 arguments
    stack_at_exit: u8,  // #stack at function exit: 1 if returns float in st(0), else 0
}

mul_sums gets { stack_at_entry: 0, stack_at_exit: 1 }.

Change Instructions, for example
+1 fld, fild, fld1, fldz, fldpi, fptan
−1 fstp, fistp, faddp, fmulp, fcomip, fpatan
−2 fcompp, fucompp
to 0 fninit, fnsave, emms

Rare functions take arguments on the x87 stack.

_CIpow:
    fadd  st0, st1   ; reads 2 values it never loaded

If an instruction reads values we never loaded, we restart the count with a bigger stack_at_entry. So _CIpow starts at 2.

Just have to be careful to account for those. nya~ 🐱

2. At each call, use the called function's count

When we know the called function, we use its count from step 1:

caller:                       ; #stack
    call  mul_sums            ; 0 -> 1   <- returns 1 value in st(0)
    fstp  dword ptr [esi]     ; 1 -> 0
    ret                       ; exits with 0

Calls to unknown targets

For virtual calls, we don't always know the target at compile time.

So we look at the instructions after it:

                      ; 0        <- based on previous instructions
call  [eax+0x10]      ; 0 -> 1   <- unknown target
mov   esi, [ebp+8]    ;          <- skipped: not x87
fstp  dword ptr [esi] ; 1 -> 0   <- reads 1 value

The logic is fairly simple, if we read a value, then a value has to exist. So if #stack was 0 before the call, it now has to be 1.

There's also some edge cases

                  ; 0   <- based on previous instructions
call   [edx+0x18] ;     <- unknown target
fld    [ebp-0x10] ;     <- we push 1
fcomip st0, st1   ;     <- compares 2 values

In this case, the call must have returned a value, otherwise we wouldn't have 2 values to read from.

When branches disagree

This guess part relies on how MSVC compiles code.

From my experience of modding games, MSVC will always pop the x87 stack (fstp st(0)), even if the return value is unused.

Wouldn't break on non-MSVC targets, but just FYI.

   ┌── jz    .error     ; 0
   │   fld   [ecx]      ; 0 -> 1
┌──┼── jmp   .done
│  └─> .error:
│           call  [0x57C708] ; 0 -> ?   <- unknown, nothing reads the stack after it
└────> .done:                ;          <- stop: label
            ret              ; 1 from `fld`, ? from the call

When reading, we stop looking at the first label, jump, call or ret.
If nothing read the stack by then, we guess the call returned nothing (0).

If the paths then disagree (here, 1 and 0 at .done), we guess 1 for (all) calls; such as call [0x57C708].
Should paths still disagree, we give up on the function.

3. Repeat until no X87Effect changes

To count past call mul_sums, caller needs the X87Effect of mul_sums.

So we loop the analysis until we reach an answer:

  1. Start every X87Effect at:
    • stack_at_entry: the x87 arguments found in step 1. Usually 0.
    • stack_at_exit: 0.
    • Or the stated effect from the config, if there is one. It never changes.
  2. Follow every function with the current X87Effects.
  3. Update each X87Effect with what we found.
  4. Repeat until nothing changes.

We repeat this for 50 rounds. Shadow The Hedgehog, finishes in 5; so this number is rather arbitrary.

4. Give up on what we can't follow

We refer to each function we can't fully analyse as 'opaque' functions.

A function is opaque (unoptimisable) if:

  • Paths disagree: they meet, or reach ret, with different #stack.
  • It returns more than 1 value.
  • The count breaks: it reads more values than are left after a call, or #stack goes above 8.
  • An instruction moves the stack in a way we can't count: ffree, fincstp, frstor and similar. Exceptions:
    • ffree st(n-1) down to ffree st0, back to back, with the fast_x87_ffree speed hack: counted as pops.
    • frstor matched to its fnsave.
  • It passes extra values to a function with a virtual call: the virtual call could read them where we can't see.
  • We can't read the code: a decode failure, or a jump or call we can't follow.

A function that calls an opaque function is untrusted, and so are its callers. A stated effect on the opaque function stops this.

fnsave and frstor

fnsave saves the x87 stack to memory and empties it. frstor loads it back.

Some error handling stuff like _CIpow from MSVC tend to do this:

mov    ecx, esp
push   ecx
fnsave [ecx+0x08]    ; #stack -> 0
call   0x3826A5
pop    ecx
frstor [ecx+0x08]    ; #stack -> as before `fnsave`

Usually we make fnsave and frstor turn functions into opaque.
However, if we can match a 'save' and 'restore' pair, we allow it.

5. Find #stack at entry

find_stack_at_entry in codegen/optimizations/x87/stack_depth/entry.rs

Callers can leave extra values on the stack, under the arguments.

_ftol takes 1 value, but often starts with 2:

fld   [ecx]   ; 0 -> 1   <- left over (unrelated code)
fld   [edx]   ; 1 -> 2   <- the argument
call  _ftol   ; starts at 2

So we check #stack at every call to each function:

  • Same at every call: we count _ftol again, starting with 2 values.
    • Unless _ftol makes a virtual call, or calls something that does; too much guesswork.
  • Different: we don't optimise the function.

Writing the code

Where this lives

  • plan_function in codegen/optimizations/x87/plan.rs
  • place_syncs in the same file.

6. Pick a level

We check each function in this order:

If the function It gets
uses MMX Original
is opaque or untrusted Original
has no known #stack at entry Original
changes state the copy can't carry Hints
has no x87 code, but calls something that changes #stack Hints
anything else LocalCopy

For MMX see MMX Locals. Handled there instead.

7. Write the hints and syncs

With the local copy, caller becomes (simplified):

X87FPU fpu = x87_copy(ctx.fpu); // <- local copy
X87_ASSUME_DEPTH(fpu, 0);       // <- #stack is 0
// call mul_sums
mul_sums(ctx, base);
x87_in<1>(fpu, ctx.fpu);        // <- reload, with 1 value
// fstp dword ptr [esi]
X86_STORE_F32(ctx.esi.u32, fpu.st0());
fpu.pop();
// ret
x87_out<0>(ctx.fpu, fpu);       // <- sync to ctx.fpu, with 0 values

Stated effects

Sometimes you need to set a function's X87Effect by hand...
When the steps above can't analyse it.

[optimization_hints]
x87_stack_effects = [
  { address = 0x37E1A5, stack_at_entry = 0, stack_at_exit = 0 }, # __security_check_cookie
]

In Shadow the Hedgehog, this entry brings back 18 functions.

A wrong X87Effect makes callers assume the wrong #stack.

And Sanic sez- that's no good!