Skip to content

LIFTER_EFFICIENCY.md

Latest commit

 

History

History
261 lines (211 loc) · 13.4 KB

LIFTER_EFFICIENCY.md

File metadata and controls

261 lines (211 loc) · 13.4 KB
Raw

Efficiency of the code the lifter generates

Goal: measure the cost of the code the x86 → C static translation produces, find its source at the instruction level, and improve the lifter. Every step is generated in a separate directory and can be compared with diff; the step promoted to the main version becomes gen/all, and the previous version is moved under arsiv/vN/ (version number: VERSION at the repository root).

Versions: v1 = baseline (archive: arsiv/v1/). v2 = opt6, the main version since 2026-10-18 (gen/all, out/nfsu2_boot, out/nfsu2_hd_boot; generated by tools/gen_v2.sh).

The table below lists the steps up to that date. All the directories are now under arsiv/v1/gen/ and arsiv/v1/out/; opt6 = today's gen/all.

directory binary contents
gen/all (v1) out/nfsu2_boot baseline (as generated at the time)
gen/prof out/nfsu2_prof_boot baseline + every x86 instruction as a comment (COMMENTS=1), -gline-tables-only — profiling only
gen/opt out/nfsu2_opt_boot + FLAGABI
gen/opt2 out/nfsu2_opt2_boot + FLAGABI + X87OPT
gen/opt3 out/nfsu2_opt3_boot opt2 + INLINE=50 (negative result, for comparison)
gen/opt4 out/nfsu2_opt4_boot opt2 + RETEIP=0
gen/opt5 out/nfsu2_opt5_boot opt4 + FCMPBL=1 (branchless fcompare)
gen/opt6 → v2 out/nfsu2_opt6_boot opt4 + MEMARG=1, compiled with -fno-strict-aliasing
gen/cov out/nfsu2_cov_boot opt2 + call counter (COVERAGE=1) — measurement only
(same sources) out/nfsu2_{nsa,opt4nsa,opt5nsa}_boot gen/all/opt4/opt5 with -fno-strict-aliasing (the runtime too: out/obj_rtnsa)

Regeneration (from the repository root; the OVERRIDE list is the same as in PROJECT.md):

./.venv/bin/python tools/flagabi.py <SPEED2.EXE> out/flagabi.json      # ~30 s
OVERRIDE=... GENOUT=gen/opt2 FLAGABI=out/flagabi.json X87OPT=1 \
  ./.venv/bin/python tools/genall.py <SPEED2.EXE> 128
# gen/opt2 -> out/obj_opt2 (same flags as build.sh), runtime objects from out/obj

The switches are off by default: genall.py without switches produces v1. To produce v2 use tools/gen_v2.sh (four switches + the override list; reproduces gen/all exactly).

Measurement method

  • Metric: the ARM instructions and cycles executed by the game thread per frame (thread_selfcounts, the CPUWIN report). Much more stable than time: two runs of the same binary differ by 0.7% (instructions) / 3.6% (time).
  • Scenario: automatic Quick Race (AUTOSEQ), PACE60=1 CPUWIN=6200,8800, 3024x1964, 2 alternating runs per version.
  • Correctness: the differential fuzzer (tools/fuzzisa.py, real x86 = Rosetta; 3969 cases), image comparison at frame 8900 (compared against the difference between two runs of the same binary).
  • Instruction-level profile: PERFLOG samples (1 ms, guest thread) → atos -i → gen/prof line → the preceding /* address instruction */ comment (tools/lift_profile.py).

Starting point: where the time goes (race, inside lifted code)

kind share
line 0 + function entry (compiler: register saves, memory traffic of c-> fields) 20.2%
mov memory 14.9%
push/pop 11.2%
cmp/test (flags) 10.3%
x87 (load/store 8.7, arithmetic 8.5, compare 5.8) 23.0%
call + ret 6.8%

Targets of memory accesses in the hot lifted functions: c->esp 10.1%, flags ~12% (zf 4.4, sf 3.3, af 2.5, cf 1.9), general registers ~10%.

1. FLAGABI — cross-function flag liveness

Problem: the flag liveness analysis counted "all flags read" at call and "all flags live" at ret. All six flags of the last flag-producing instruction before a call (very often add esp,N, xor eax,eax; ret) were computed and written to memory.

Change (tools/lift.py: abi_cfg, abi_liveness, _flag_defuse_abi; tools/flagabi.py): MSVC code doesn't read flags returned from a call, and the callee doesn't read the caller's flags on entry. This assumption is proven over the whole program: at a fixed point, each function's entry-live flags and the call sites "where flags are read after the call" are computed; conservative behavior is kept only for those. A flag left undefined by x86 counts as defined (otherwise and/test never kill AF, and AF spread falsely everywhere: 3171 false "flag-returning" functions in the first attempt).

Audit result: across 23274 functions, 14 "flag-returning", 210 entry-live, 12 sites reading flags after an indirect call; every indirect site examined is either a data byte decoded as code (retf 0x50ff, int3, a random adc) or a conservative outer edge.

2. X87OPT — x87 register allocation within a block

Problem: ST(n) = c->st[(c->top+n)&7] is indexed at run time; clang can never put x87 values in registers, and every operation is a top read + address

  • load/store.

Change (tools/lift.py: X87Region): within a basic block the stack depth is known at compile time. At the start of the region _T = c->top; ST(n) → _x[off+n+8] (constant index → ARM FP register); FPUSH/FPOP only change the static off. A slot read before being written is loaded once; at the end of the region (branch, call, ret, an instruction touching c->st/c->top, block end) only the modified slots still on the stack are written back, and c->top is updated once. fnstsw gets the static top via fsw_get_top.

Result

version instr/frame cycles/frame CPU ms/frame binary
baseline 43.22 M 16.50 M 5.97 46.1 MB
+ FLAGABI 40.24 M (−6.9%) 15.76 M (−4.5%) 5.86 40.3 MB
+ X87OPT 38.51 M (−10.9%) 14.83 M (−10.1%) 5.44 37.3 MB (−19%)

Fuzzer: 3969/3969 matched (X87OPT on and off). The image difference (mean 0.21) is at the same level as the difference between two runs of the same binary (0.16).

3. Call model

Measurement (gen/cov, COVREPORT + COVRESET_AT=6200, 2800 frames): in a race ~104 thousand lifted function calls per frame (~370 ARM instructions per call on average). 37% of the calls go to ≤50-instruction leaf functions that make no further calls (~38 thousand per frame); the most called is __ftol2 (sub_0075bed4, 39 instructions) at 10.5 thousand/frame. The call cost in the machine code of a small function: 3 stp + 3 ldp at entry/exit, reloading c->esp and g_mem after every call, writing the return address to c->eip at every ret.

3a. INLINE (negative). genall.py INLINE=50: the bodies of 4703 leaf functions are put into every shard as a static inline __attribute__((always_inline)) inl_X copy, and direct calls are redirected to it. Result (2 runs): instructions 37.82 → 38.20 M (+1%), cycles 14.44 → 14.93 M (+3.4%), binary 37.3 → 43.6 MB. The fixed cost per call is smaller than estimated; the inlined bodies increase register pressure in the already large goto functions. ThinLTO (−1.8%, within noise) had given the same result.

3b. RETEIP. ret → c->esp += 4(+n); return; instead of POP32(c->eip); return;. The only place reading c->eip after a lifted call was genexec.c; it now uses the return address it pushed (next) (the model already ignored modified return addresses). Result (opt2 → opt4, 2 runs): instructions 37.83 → 37.59 M (−0.7%), cycles 13.95 → 13.58 M (−2.7%), image the same.

4. Strict aliasing undefined behavior

Symptom. opt5 (FCMPBL=1, fcompare → branchless fcompare_bl) noticeably changed the race frame (Y 57.3 → 59.5, the same in two runs). The two functions produce the same bits for every pair of doubles (exhaustive test), and the generated C differs only in the function name.

Narrowing down (no guessing, every step measured):

  1. bisecting shards (mixing opt4/opt5 objects and checking frame 8900 brightness) → shard_0058;
  2. bisecting functions (fcompare_bl only in selected functions) → sub_005f0a40 (a quadtree search: compares the point against box midpoints and descends into a child);
  3. a function-level differential harness: runs the two builds side by side with random trees/points/boxes (±0, NaN, equality frequent) and compares the final state. opt5 -O3 diverges from its own -O0 (7854 in 100 thousand), opt4 doesn't; the difference is the sign of the midpoint on the stack (−0/+0);
  4. -mllvm -opt-bisect-limit → the breaking pass is GVNPass (pass 262 of 386);
  5. IR: an i32 is written to the same guest stack address and a float is read, with different TBAA tags.

Root cause. Lifted code accesses guest memory at the same address with different types (writing MR32 and reading MRF32, MR16/MR32 overlap). In C this is a strict aliasing violation; the compiler may assume that accesses of different types don't overlap and move the load ahead of the store. The build flags never had -fno-strict-aliasing — including the baseline gen/all and the runtime. With the flag opt5 = opt4 = baseline (image), difference 0. fcompare_bl is correct; the UB only became visible when the shape of the code changed.

Verification and cost (against the Windows reference, frames 1300–8900, port NFSRES=1280x960 VCLOCK=fixed): with the flag, baseline/opt4/opt5 give the same image; no visible effect of this UB was measured in the baseline build. Raw cost (mean of 2 runs):

instr/frame cycles/frame
baseline 42.61 M 14.34 M
baseline + -fno-strict-aliasing 45.24 M (+6.2%) 15.14 M (+5.6%)
opt4 38.54 M 12.81 M
opt4 + -fno-strict-aliasing 39.61 M (+2.8%) 12.95 M (+1.1%)

Source of the cost (disassembly): without type information the value of the global g_mem is re-read after every guest write (sub_005f0a40: 2 → 10 ldr x, [&g_mem]).

5. MEMARG — the guest memory base as a parameter

Observation. With or without the flag, CPU fields like c->eax are re-read after every write to guest memory: even though c is restrict, g_mem is a pointer read from memory, and since c is passed to calls it has "escaped"; LLVM can't prove that a guest write doesn't touch *c.

Change (tools/genall.py, MEMARG=1, a post-generation transform): every function becomes void sub_X_m(CPU *restrict c, uint8_t *restrict _mb); the shard has #define g_mem _mb; lifted code calls each other with sub_Y_m(c, _mb). The externally visible void sub_X(CPU*) stays as a thin wrapper (fntab, indirect calls, runtime → lifted calls and overrides don't change; the _m bridge for overrides and missing functions is in stubs.c). Two separate noalias parameters never alias in LLVM, with certainty — no escape analysis needed. On ARM64 _mb arrives in x1.

In a single function (sub_005f0a40, -fno-strict-aliasing): CPU field reads 25 → 4, guest reads 18 → 8; an int write followed by a float read is now forwarded directly (str w12 → fmov s0, w12).

Result (opt4 + -fno-strict-aliasing ↔ opt6, alternating; instructions 2+2, cycles excluding the noisy p4 run (IPC 2.72)): instructions 39.33 → 35.50 M (−9.7%), cycles 12.94 → 11.51 M (−11%), binary 38.1 → 34.8 MB. Image: all 16 frames under Windows conditions identical to opt4+flag. MEMARG doesn't just win back the cost of the correctness fix, it goes beyond it.

Total (with a correct build)

version instr/frame cycles/frame binary
baseline (gen/all, strict aliasing UB present) 42.61 M 14.34 M 46.1 MB
opt6 (FLAGABI + X87OPT + RETEIP + MEMARG, -fno-strict-aliasing) 35.50 M (−16.7%) 11.51 M (−19.7%) 34.8 MB (−25%)

6. v2: opt6 as the main version (2026-10-18)

opt6 was first played as a separate build with the current runtime. Once the user approved it, it became the main version (v2): gen/opt6 → gen/all, v1 was moved under arsiv/v1/.

tools/gen_v2.sh <SPEED2.EXE>         # gen/all (131 files, 0 differences from gen/opt6)
./build.sh && ./link.sh              # everything with -fno-strict-aliasing
./pack.sh --embed [--hd]             # out/personal/NFSU2[ HD].app, version "2.0"
  • The tools/gen_v2.sh recipe reproduced gen/opt6 exactly; the 130 objects compiled with build.sh are byte-for-byte identical to the opt6 objects. impargs.c is the same as in v1.
  • Tests on v2: 439/439 ISA, 15/15 function verification.

Verification, image (Windows NFSRef conditions, 16 frames): difference from the Windows reference in the menu 0.18–0.55. This is at the same level as the v1 build's 0.18–0.70, and the difference comes from the animation phase. Sharpness and edge profile identical. HD v2 vs HD v1: 0.07–0.64. Command buffer errors 0, unresolved indirect calls 0.

Verification, CPU (same runtime, PACE60 CPUWIN=6200,8800, 3024x1964, alternating 3+3 runs):

CPU ms/frame instr/frame cycles/frame
v1 5.71 41.99 M 15.49 M
v2 (opt6) 4.44 (−22.3%) 34.17 M (−18.6%) 11.19 M (−27.7%)

Since the game is at its 120 fps limit, the gain doesn't show in fps. Where it shows is the time the game thread spends asleep, and watts (see tools/session.sh, powermetrics).

Next candidates

  • Call model: c->esp and the general registers are written to memory and read back at every call (~20% of memory accesses in hot code).
  • Fusing fcom → fnstsw → test → jcc: reducing it to a single C comparison.
  • Extending the x87 region across blocks (merge points with consistent depth).