Cranelift and suboptimal instruction scheduling

I did a bit of work recently to get a build of [XNNPACK](https://github.com/google/XNNPACK) working with Wasmtime. My original motivation for doing this was that XNNPACK has been used as a benchmark to evaluate a number of changes to the simd proposal to WebAssembly (and relaxed-simd), so it seemed like a great candidate to test as baselines between WebAssembly engines and native performance. The `master` branch of that repository itself doesn't support WASI as a target, so I [hacked up a bunch of commits](https://github.com/alexcrichton/XNNPACK/tree/wasi) and updated the intrinsics to the LLVM 16 versions. Using that I was able to produce a WebAssembly file with:

```
./bazelisk-linux-arm64 build -c opt --config wasi --features wasm_relaxed_simd :end2end_bench
```

The output file is [end2end.simd.relaxed.wasm.gz](https://github.com/bytecodealliance/wasmtime/files/11161966/end2end.simd.relaxed.wasm.gz).

I'll be honest in that there's a ton of benchmarks listed in the `BUILD.bazel` file for that repository and I don't know if "end2end" is the "main" one or if there even is a "main" one. Nevertheless it sounded right and I figured it was at least one good starting point.

Using this script:

run.sh

```sh
set -e
wasmtime="../wasmtime/target/release/wasmtime run --disable-cache \
--wasm-features threads,relaxed-simd \
--wasi-modules experimental-wasi-threads \
--"
wasmtime2="../wasmtime/target/release/wasmtime run --disable-cache \
--wasm-features threads,relaxed-simd \
--wasi-modules experimental-wasi-threads \
--cranelift-set use_egraphs=false \
--"
node="node \
--experimental-wasm-relaxed-simd \
--experimental-wasi-unstable-preview1 \
../meshoptimizer/run.mjs"
spidermonkey="../gecko-dev/obj-opt-aarch64-unknown-linux-gnu/dist/bin/js \
../wasmtime/spidermonkey.js"
v8="../v8/out/arm64.release/d8 \
--experimental-wasm-relaxed-simd \
../wasmtime/v8.js --"

for t in `$wasmtime ./end2end.simd.relaxed.wasm --benchmark_list_tests | rg -v FP16`; do
# echo ====================================================================

for file in end2end.simd.relaxed.wasm; do
# echo == $file ==
echo -n "wasmtime "
$wasmtime ./$file --benchmark_filter=$t 2>&1 | rg $t
echo -n "wasmtime2 "
$wasmtime2 ./$file --benchmark_filter=$t 2>&1 | rg $t
echo -n "node "
$node ./$file --benchmark_filter=$t 2>&1 | rg $t
echo -n "spidermonkey "
$spidermonkey ./$file --benchmark_filter=$t 2>&1 | rg $t
echo -n "v8 "
$v8 ./$file --benchmark_filter=$t 2>&1 | rg $t
echo -n "native "
./end2end_bench --benchmark_filter=$t 2>&1 | rg $t

done
echo

done
```

run.mjs

```js
import { readFile } from 'node:fs/promises';
import { WASI } from 'wasi';
import { argv } from 'node:process';

const wasi = new WASI({
version: 'preview1',
args: argv.slice(2),
});

const m = process.argv[2];
const wasm = await WebAssembly.compile(await readFile(m));
const obj = wasi.getImportObject();
obj.env = {
memory: new WebAssembly.Memory({shared: true, initial: 8000, maximum: 16000}),
};
obj.wasi = {
'thread-spawn': function() {
throw new Error('wasi thread spawn');
},
};
const instance = await WebAssembly.instantiate(wasm, obj);
wasi.start(instance);

```

spidermonkey.js

```js
const ITERS = 1;

////////////////////////////////////////////////////////////////////////////////

class TextEncoder {
constructor(enc) {
if (enc != "utf-8") {
throw new Error("FITZGEN: unsupported encoding: " + enc);
}
}
encode(s, n) {
let buf = new Uint8Array(s.length);
for (let i = 0; i < Math.min(s.length, n); i++) {
buf[i] = s.charCodeAt(i); // lol
}
return buf;
}
};

class TextDecoder {
constructor(enc) {
if (enc != "utf-8") {
throw new Error("FITZGEN: unsupported encoding: " + enc);
}
}
decode(buf) {
let buf8 = new Uint8Array(buf);
let s = "";
for (let i = 0; i < buf8.length; i++) {
s += String.fromCharCode(buf8[i]); // lol
}
return s;
}
};

////////////////////////////////////////////////////////////////////////////////

async function ionCompile(wasm) {
let module = await WebAssembly.compile(wasm);
while (!wasmHasTier2CompilationCompleted(module)) {
sleep(1);
}
// wasmDis(module);
return module;
}

function unimplemented(name) {
return function (...args) {
throw new Error(name + " is unimplemented! args = " + args);
}
}

class ProcExitError extends Error {
constructor(code) {
this.code = code;
this.message = "Program exited with code " + code;
}
toString() {
return "ProcExitError: " + this.message
}
}

function trace(obj) {
let proxy = {};
for (let key of Object.keys(obj)) {
if (typeof obj[key] != "function") {
proxy[key] = obj[key];
continue;
}
proxy[key] = function (...args) {
print("TRACE: " + key + "(" + args + ")");
let ret = obj[key](...args);
print("TRACE: -> " + ret);
return ret;
};
}
return proxy;
}

////////////////////////////////////////////////////////////////////////////////

async function main() {
let smWasm = os.file.readFile(scriptArgs[0], "binary");
let smModule = await ionCompile(smWasm);

for (let i = 0; i < ITERS; i++) {
let args = scriptArgs;
let mem = null;
let start = null;
let unread = true;

let smInstance = await WebAssembly.instantiate(smModule, trace({
env: {
memory: new WebAssembly.Memory({
shared: true,
minimum: 8000,
maximum: 16000,
}),
},
bench: {
start: function () {
start = monotonicNow()
},
end: function () {
let end = monotonicNow();
print("ITER: " + (end - start));
}
},
wasi: {
'thread-spawn': function() {
throw new Error('thread-spawn');
},
},
wasi_snapshot_preview1: {
fd_pread: function() { throw new Error('fd_pread'); },
poll_oneoff: function(in_, out, n) {
console.log(n);
// throw new Error('poll_oneoff');
return 0;
},
random_get: function(a, b) {
while (b > 0) {
(new DataView(mem.buffer)).setInt8(a, 1, true);
b -= 1;
a += 1;
}
return 0;
},
args_get: function(a, b) {
for (let arg of args) {
(new DataView(mem.buffer)).setInt32(a, b, true);
a += 4;
for (let c in arg) {
(new DataView(mem.buffer)).setInt8(b, arg.charCodeAt(c), true);
b += 1;
}
(new DataView(mem.buffer)).setInt8(b, 0, true);
b += 1;
}
return 0;
},
args_sizes_get: function(a, b) {
let len = 0;
for (let arg of args) {
len += arg.length + 1;
}
(new DataView(mem.buffer)).setInt32(a, args.length, true);
(new DataView(mem.buffer)).setInt32(b, len, true);
return 0;
},
clock_res_get: function () { return 1; },
clock_time_get: function(a, b, c) {
const now = Math.round(performance.now() * 1000000);
(new DataView(mem.buffer)).setBigInt64(c, BigInt(now), true);
return 0;
},
fd_filestat_get: function() { throw new Error('fd_filestat_get'); },
fd_read: function(fd, iovecs_ptr, iovecs_len, out_ptr) {
let mem8 = new Uint8Array(mem.buffer);
switch (fd) {
case 4:
let data = os.file.readFile("/home/nick/sightglass/benchmarks/spidermonkey/default.input.md");
let k = 0;
for (let i = 0; i < iovecs_len && k < data.length && unread; i++) {
let ptr = (new DataView(mem.buffer)).getUint32(iovecs_ptr + i * 8, true);
let len = (new DataView(mem.buffer)).getUint32(iovecs_ptr + i * 8 + 4, true);
for (let j = 0; j < len && k < data.length; j++) {
mem8[ptr + j] = data.charCodeAt(k++);
}
}
unread = false;
(new DataView(mem.buffer)).setUint32(out_ptr, k, true);
return 0;
default:
return 8;
}
},
fd_seek: function(fd, offset, whence, out_ptr) {
switch (fd) {
case 4:
let len = os.file.readFile("/home/nick/sightglass/benchmarks/spidermonkey/default.input.md").length;
(new DataView(mem.buffer)).setBigUint64(out_ptr, BigInt(len), true);
return 0;
default:
return 8;
}
},
fd_write: function(a, b, c, d) {
let s = '';
let total = 0;
while (c > 0) {
let base = (new DataView(mem.buffer)).getInt32(b, true);
let len = (new DataView(mem.buffer)).getInt32(b + 4, true);
b += 8;
c -= 1;

while (len > 0) {
let c = new Uint8Array(mem.buffer)[base]
s += String.fromCharCode(c);
len -= 1;
base += 1;
total += 1;
}
}
//print("fd_write(" + a + "): " + s.trimEnd());
print(s.trimEnd());
(new DataView(mem.buffer)).setInt32(d, total, true);
return 0;
},
fd_fdstat_set_flags: function() { throw new Error('fd_fdstat_set_flags'); },
path_filestat_get: function() { throw new Error('path_filestat_get'); },
path_open: function(fd, dirflags, path_ptr, path_len, oflags, fs_rights_base, fs_rights_inheriting, fdflags, out_ptr) {
let buf = new Uint8Array(path_len);
let mem8 = new Uint8Array(mem.buffer);
for (let i = 0; i < path_len; i++) {
buf[i] = mem8[path_ptr + i];
}
let path = (new TextDecoder('utf-8')).decode(buf);
switch (path) {
case "default.input.md":
(new DataView(mem.buffer)).setInt32(out_ptr, 4, true);
return 0;
default:
print('denying path_open(' + path + ')');
return 2;
}
},
path_remove_directory: function() { throw new Error('path_remove_directory'); },
path_unlink_file: function() { throw new Error('path_unlink_file'); },
sched_yield: function() { throw new Error('sched_yield'); },
environ_get: function() { return 0; },
environ_sizes_get: function(a, b) {
(new DataView(mem.buffer)).setInt32(a, 0, true);
(new DataView(mem.buffer)).setInt32(b, 0, true);
return 0;
},
fd_close: function(fd) {
return 0;
},
fd_fdstat_get: function(fd, out_ptr) {
(new DataView(mem.buffer)).setInt32(out_ptr, 0);
// type
switch (fd) {
case 3:
(new DataView(mem.buffer)).setInt32(out_ptr + 4, 3, true);
break;
case 4:
(new DataView(mem.buffer)).setInt32(out_ptr + 4, 4, true);
break;
default:
(new DataView(mem.buffer)).setInt32(out_ptr + 4, 0, true);
break;
}
(new DataView(mem.buffer)).setInt32(out_ptr + 8, 0, true);
(new DataView(mem.buffer)).setInt32(out_ptr + 12, 0, true);
(new DataView(mem.buffer)).setInt32(out_ptr + 16, 0, true);
(new DataView(mem.buffer)).setInt32(out_ptr + 20, 0, true);
return 0;
},
fd_prestat_get: function(a, b) {
// case for preopened "."
if (a == 3) {
// discriminant for directory
(new DataView(mem.buffer)).setInt32(b, 0, true);
// one entry in directory
(new DataView(mem.buffer)).setInt32(b + 4, 1, true);
return 0;
}
return 8;
},
fd_prestat_dir_name: function(fd, ptr, len) {
let buf = (new TextEncoder('utf-8')).encode(".", 1);
let mem8 = new Uint8Array(mem.buffer);
for (let i = 0; i < Math.min(buf.length, len); i++) {
mem8[ptr + i] = buf[i];
}
mem8[Math.min(buf.length, len)] = 0;
return 0;
},
proc_exit: function(code) { throw new ProcExitError(code); },
},
}));

mem = smInstance.exports.memory;

try {
smInstance.exports._start();
} catch (e) {
if ((e instanceof ProcExitError) && e.code == 0) {
continue;
}
throw e;
}
}
}

main().catch(function (e) {
print("====== ERROR!!! ======");
print(e);
print(e.stack);
});

```

v8.js

```js
const ITERS = 1;

////////////////////////////////////////////////////////////////////////////////

class TextEncoder {
constructor(enc) {
if (enc != "utf-8") {
throw new Error("FITZGEN: unsupported encoding: " + enc);
}
}
encode(s, n) {
let buf = new Uint8Array(s.length);
for (let i = 0; i < Math.min(s.length, n); i++) {
buf[i] = s.charCodeAt(i); // lol
}
return buf;
}
};

class TextDecoder {
constructor(enc) {
if (enc != "utf-8") {
throw new Error("FITZGEN: unsupported encoding: " + enc);
}
}
decode(buf) {
let buf8 = new Uint8Array(buf);
let s = "";
for (let i = 0; i < buf8.length; i++) {
s += String.fromCharCode(buf8[i]); // lol
}
return s;
}
};

////////////////////////////////////////////////////////////////////////////////

async function ionCompile(wasm) {
let module = new WebAssembly.Module(wasm);
// while (!wasmHasTier2CompilationCompleted(module)) {
// sleep(1);
// }
// wasmDis(module);
return module;
}

function unimplemented(name) {
return function (...args) {
throw new Error(name + " is unimplemented! args = " + args);
}
}

class ProcExitError extends Error {
constructor(code) {
this.code = code;
this.message = "Program exited with code " + code;
}
toString() {
return "ProcExitError: " + this.message
}
}

function trace(obj) {
let proxy = {};
for (let key of Object.keys(obj)) {
if (typeof obj[key] != "function") {
proxy[key] = obj[key];
continue;
}
proxy[key] = function (...args) {
print("TRACE: " + key + "(" + args + ")");
let ret = obj[key](...args);
print("TRACE: -> " + ret);
return ret;
};
}
return proxy;
}

////////////////////////////////////////////////////////////////////////////////

async function main(args) {
console.log(args[0]);
let smWasm = readbuffer(args[0]);
console.log(smWasm.byteLength, smWasm);
let smModule = await ionCompile(smWasm);

for (let i = 0; i < ITERS; i++) {
let mem = null;
let start = null;
let unread = true;

let smInstance = await WebAssembly.instantiate(smModule, trace({
env: {
memory: new WebAssembly.Memory({
shared: true,
initial: 8000,
maximum: 16000,
}),
},
bench: {
start: function () {
start = monotonicNow()
},
end: function () {
let end = monotonicNow();
print("ITER: " + (end - start));
}
},
wasi: {
'thread-spawn': function() {
throw new Error('thread-spawn');
},
},
wasi_snapshot_preview1: {
fd_pread: function() { throw new Error('fd_pread'); },
poll_oneoff: function(in_, out, n) {
console.log(n);
// throw new Error('poll_oneoff');
return 0;
},
random_get: function(a, b) {
while (b > 0) {
(new DataView(mem.buffer)).setInt8(a, 1, true);
b -= 1;
a += 1;
}
return 0;
},
args_get: function(a, b) {
for (let arg of args) {
(new DataView(mem.buffer)).setInt32(a, b, true);
a += 4;
for (let c in arg) {
(new DataView(mem.buffer)).setInt8(b, arg.charCodeAt(c), true);
b += 1;
}
(new DataView(mem.buffer)).setInt8(b, 0, true);
b += 1;
}
return 0;
},
args_sizes_get: function(a, b) {
let len = 0;
for (let arg of args) {
len += arg.length + 1;
}
(new DataView(mem.buffer)).setInt32(a, args.length, true);
(new DataView(mem.buffer)).setInt32(b, len, true);
return 0;
},
clock_res_get: function () { return 1; },
clock_time_get: function(a, b, c) {
const now = Math.round(performance.now() * 1000000);
(new DataView(mem.buffer)).setBigInt64(c, BigInt(now), true);
return 0;
},
fd_filestat_get: function() { throw new Error('fd_filestat_get'); },
fd_read: function(fd, iovecs_ptr, iovecs_len, out_ptr) {
let mem8 = new Uint8Array(mem.buffer);
switch (fd) {
case 4:
let data = os.file.readFile("/home/nick/sightglass/benchmarks/spidermonkey/default.input.md");
let k = 0;
for (let i = 0; i < iovecs_len && k < data.length && unread; i++) {
let ptr = (new DataView(mem.buffer)).getUint32(iovecs_ptr + i * 8, true);
let len = (new DataView(mem.buffer)).getUint32(iovecs_ptr + i * 8 + 4, true);
for (let j = 0; j < len && k < data.length; j++) {
mem8[ptr + j] = data.charCodeAt(k++);
}
}
unread = false;
(new DataView(mem.buffer)).setUint32(out_ptr, k, true);
return 0;
default:
return 8;
}
},
fd_seek: function(fd, offset, whence, out_ptr) {
switch (fd) {
case 4:
let len = os.file.readFile("/home/nick/sightglass/benchmarks/spidermonkey/default.input.md").length;
(new DataView(mem.buffer)).setBigUint64(out_ptr, BigInt(len), true);
return 0;
default:
return 8;
}
},
fd_write: function(a, b, c, d) {
let s = '';
let total = 0;
while (c > 0) {
let base = (new DataView(mem.buffer)).getInt32(b, true);
let len = (new DataView(mem.buffer)).getInt32(b + 4, true);
b += 8;
c -= 1;

while (len > 0) {
let c = new Uint8Array(mem.buffer)[base]
s += String.fromCharCode(c);
len -= 1;
base += 1;
total += 1;
}
}
//print("fd_write(" + a + "): " + s.trimEnd());
print(s.trimEnd());
(new DataView(mem.buffer)).setInt32(d, total, true);
return 0;
},
fd_fdstat_set_flags: function() { throw new Error('fd_fdstat_set_flags'); },
path_filestat_get: function() { throw new Error('path_filestat_get'); },
path_open: function(fd, dirflags, path_ptr, path_len, oflags, fs_rights_base, fs_rights_inheriting, fdflags, out_ptr) {
let buf = new Uint8Array(path_len);
let mem8 = new Uint8Array(mem.buffer);
for (let i = 0; i < path_len; i++) {
buf[i] = mem8[path_ptr + i];
}
let path = (new TextDecoder('utf-8')).decode(buf);
switch (path) {
case "default.input.md":
(new DataView(mem.buffer)).setInt32(out_ptr, 4, true);
return 0;
default:
print('denying path_open(' + path + ')');
return 2;
}
},
path_remove_directory: function() { throw new Error('path_remove_directory'); },
path_unlink_file: function() { throw new Error('path_unlink_file'); },
sched_yield: function() { throw new Error('sched_yield'); },
environ_get: function() { return 0; },
environ_sizes_get: function(a, b) {
(new DataView(mem.buffer)).setInt32(a, 0, true);
(new DataView(mem.buffer)).setInt32(b, 0, true);
return 0;
},
fd_close: function(fd) {
return 0;
},
fd_fdstat_get: function(fd, out_ptr) {
(new DataView(mem.buffer)).setInt32(out_ptr, 0);
// type
switch (fd) {
case 3:
(new DataView(mem.buffer)).setInt32(out_ptr + 4, 3, true);
break;
case 4:
(new DataView(mem.buffer)).setInt32(out_ptr + 4, 4, true);
break;
default:
(new DataView(mem.buffer)).setInt32(out_ptr + 4, 0, true);
break;
}
(new DataView(mem.buffer)).setInt32(out_ptr + 8, 0, true);
(new DataView(mem.buffer)).setInt32(out_ptr + 12, 0, true);
(new DataView(mem.buffer)).setInt32(out_ptr + 16, 0, true);
(new DataView(mem.buffer)).setInt32(out_ptr + 20, 0, true);
return 0;
},
fd_prestat_get: function(a, b) {
// case for preopened "."
if (a == 3) {
// discriminant for directory
(new DataView(mem.buffer)).setInt32(b, 0, true);
// one entry in directory
(new DataView(mem.buffer)).setInt32(b + 4, 1, true);
return 0;
}
return 8;
},
fd_prestat_dir_name: function(fd, ptr, len) {
let buf = (new TextEncoder('utf-8')).encode(".", 1);
let mem8 = new Uint8Array(mem.buffer);
for (let i = 0; i < Math.min(buf.length, len); i++) {
mem8[ptr + i] = buf[i];
}
mem8[Math.min(buf.length, len)] = 0;
return 0;
},
proc_exit: function(code) { throw new ProcExitError(code); },
},
}));

mem = smInstance.exports.memory;

try {
smInstance.exports._start();
} catch (e) {
if ((e instanceof ProcExitError) && e.code == 0) {
continue;
}
throw e;
}
}
}

main(arguments)
// .catch(function (e) {
// print("====== ERROR!!! ======");
// print(e);
// print(e.stack);
// });

```

I was able to compare a variety of executions of this wasm file:

| Engine | aarch64 | x86_64 |
|----------|---------|---------|
| Wasmtime | 52e90532e0050bbb271813321727588e6a1c25ab | 52e90532e0050bbb271813321727588e6a1c25ab |
| Wasmtime2 | 52e90532e0050bbb271813321727588e6a1c25ab plus `--cranelift-set use_egraphs=false` | 52e90532e0050bbb271813321727588e6a1c25ab plus `--cranelift-set use_egraphs=false` |
| Node.js | 19.8.1 | *N/A since it crashes with breakpoint trap* |
| Spidermonkey | dbc0cd5615f9cd | dbc0cd5615f9cd |
| v8 | 1664d8a3e546d | 11.4.62 (from jsvu) |

These are the results for engine-to-engine comparisons within the same benchmark. Everything is normalized to the fastest engine and other engines are expressed as a factor of the fastest engine's performance. Lower is better.

(sorry for the different colors here)

I probably compiled v8 the wrong way for aarch64 or something like that because node is often substantially faster than v8. Some things from this are:

* On AArch64 egraphs surprisingly slow down all benchmarks, an average of 3.3%.
* On AArch64 Wasmtime is a good 10-20% slower than node. It's difficult for me to profile node but when profiling v8 for the `Q*8*` benchmarks at the end v8 and Cranelift have very similar instructions selected, mostly just in different orders
* On x86_64 egraphs aren't always a slowdown but are still an average slowdown of 3.3% with up to a 10% slowdown on `FP32MobileNetV3Small/T:1/real_time`, for example

On many benchmarks we're trailing significantly behind v8/node and it's not obvious what the reasons are looking at perf profiles. Overall one major thing I feel like I see from the perf profiles, though, is that the diassembly of functions often drastically differs in ordering of instructions between v8 and Cranelift. On one hand v8 tends to match the original wasm pretty closely, keeping grouped instructions together. For Cranelift, however, everything looks more "data driven" where one value is computed, then the next value is computed, etc. This seems like it may hurt processor pipelines where each instruction may stall on the prior as opposed to what's in the wasm which is to have things be slightly more parallel.

I'll be honest though in that I haven't spent a huge amount of time digging into this yet. There's quite a few benchmarks here and quite a few configurations, and any number of them could provide avenues through which things may be optimized. Flipping `--cranelift-set use_egraphs=false` was an easy way to see the impact and led to me opening this issue, but there could very well be more specific issues unrelated entirely to instruction scheduling to dig into here.