merge work/jit2: x86-64 jit inline enhancements

5 files changed, 215 insertions, 0 deletions

diff --git a/tests/parity.known b/tests/parity.known
index 6892499..5ddbdf2 100644
--- a/tests/parity.known
+++ b/tests/parity.known
@@ -16,3 +16,4 @@ tests/programs/bench_strings.zc # reads the repeat count from stdin; with none,
 # zc0 reads unbounded and ignores it, and emits no index checks at all
 tests/programs/bounds_fixed.zc # bounds checks: only the self-hosted compiler checks a fixed array index
 tests/programs/bounds_heap.zc # bounds checks: only the self-hosted compiler checks a pointer into a heap block
+tests/programs/bounds_proof.zc # bounds checks: zc0 emits none, so the variable-bound loop is as short as the unbounded one
diff --git a/tests/programs/bounds_proof.zc b/tests/programs/bounds_proof.zc
new file mode 100644
index 0000000..a678fb3
--- /dev/null
+++ b/tests/programs/bounds_proof.zc
@@ -0,0 +1,21 @@
+namespace;
+include rt;
+
+// a loop test i < K with a constant K proves the index of a fixed array of at
+// least K elements, so the bounds check is dropped: the checked loop compiles
+// to exactly as many words as the unbounded one. a variable bound proves
+// nothing and keeps the check. sizes come from the functions' line blocks.
+int[8] t;
+int konst() { int i, s = 0; for (i = 0; i < 8; i++) s = s + t[i]; return s; }
+unbounded int bare() { int i, s = 0; for (i = 0; i < 8; i++) s = s + t[i]; return s; }
+int vary(int n) { int i, s = 0; for (i = 0; i < n; i++) s = s + t[i]; return s; }
+unbounded int vbare(int n) { int i, s = 0; for (i = 0; i < n; i++) s = s + t[i]; return s; }
+
+int size(word f) { word b = rt.line_block_of(f); return b[2] - b[1]; }
+
+int main() {
+	rt.put_n(konst() + bare() + vary(8) + vbare(8)); rt.put_c(10);
+	rt.put_n(size(konst) == size(bare)); rt.put_c(10);
+	rt.put_n(size(vary) > size(vbare)); rt.put_c(10);
+	return 0;
+}
diff --git a/tests/programs/enh_ops.expected b/tests/programs/enh_ops.expected
new file mode 100644
index 0000000..6549235
--- /dev/null
+++ b/tests/programs/enh_ops.expected
@@ -0,0 +1,34 @@
+add 882028350189717406
+sub 6655513972688108814
+mul 8202745059402640650
+sdiv -7272167455729189346
+udiv 2339759234614203099
+srem -1116402929106219647
+urem 9047360979782569854
+and 6728770653513201046
+or -5846742303323483640
+xor 5871231116872866930
+shl -343427929681503244
+shr -5759255359902579034
+sar -6075979569754238740
+lt -8494581876920277443
+ltu 5806102239654568498
+eq -7243535849964624607
+ne 2622739368221699999
+min 2867643923396239862
+max -1985615573206522456
+minu -7534928991011776213
+maxu 8416957341201493619
+mulhs -4206753455779030529
+mulhu -2870129158516768804
+rotl -6540633553243608262
+rotr -7155384646341566258
+neg -5182646291052210387
+not 5851949150302311436
+clz -7956734789639098207
+ctz 4862650619482391916
+abs 6757983799103834145
+bswap 5143948399074944670
+sel -578455337847416602
+ld st 71455
+mix -2049273682776724457
diff --git a/tests/programs/enh_ops.zc b/tests/programs/enh_ops.zc
new file mode 100644
index 0000000..da3cc09
--- /dev/null
+++ b/tests/programs/enh_ops.zc
@@ -0,0 +1,148 @@
+namespace;
+include rt;
+
+// every micro-op the x86-64 jit lowers inline, on edge values (0, -1, the
+// minimum, shift counts past 63, out-of-range loads), called with variables
+// and with literals (which specialize the enhancement on them). the output must
+// be the same on every backend; tests/drivers/jit_x64_test.sh compares it
+// against the interpreter.
+enhance e_add(a, b) micro "r0 = add a b";
+enhance e_sub(a, b) micro "r0 = sub a b";
+enhance e_mul(a, b) micro "r0 = mul a b";
+enhance e_sdiv(a, b) micro "r0 = sdiv a b";
+enhance e_udiv(a, b) micro "r0 = udiv a b";
+enhance e_srem(a, b) micro "r0 = srem a b";
+enhance e_urem(a, b) micro "r0 = urem a b";
+enhance e_and(a, b) micro "r0 = and a b";
+enhance e_or(a, b) micro "r0 = or a b";
+enhance e_xor(a, b) micro "r0 = xor a b";
+enhance e_shl(a, b) micro "r0 = shl a b";
+enhance e_shr(a, b) micro "r0 = shr a b";
+enhance e_sar(a, b) micro "r0 = sar a b";
+enhance e_lt(a, b) micro "r0 = lt a b";
+enhance e_ltu(a, b) micro "r0 = ltu a b";
+enhance e_eq(a, b) micro "r0 = eq a b";
+enhance e_ne(a, b) micro "r0 = ne a b";
+enhance e_min(a, b) micro "r0 = min a b";
+enhance e_max(a, b) micro "r0 = max a b";
+enhance e_minu(a, b) micro "r0 = minu a b";
+enhance e_maxu(a, b) micro "r0 = maxu a b";
+enhance e_mulhs(a, b) micro "r0 = mulhs a b";
+enhance e_mulhu(a, b) micro "r0 = mulhu a b";
+enhance e_rotl(a, b) micro "r0 = rotl a b";
+enhance e_rotr(a, b) micro "r0 = rotr a b";
+enhance u_neg(a) micro "r0 = neg a";
+enhance u_not(a) micro "r0 = not a";
+enhance u_clz(a) micro "r0 = clz a";
+enhance u_ctz(a) micro "r0 = ctz a";
+enhance u_abs(a) micro "r0 = abs a";
+enhance u_bswap(a) micro "r0 = bswap a";
+enhance e_sel(a, b, c) micro "r0 = sel a b c";
+enhance e_ld(a) micro "r0 = ld a";
+enhance e_st(a, b) micro "st a b; r0 = ld a";
+enhance e_mix(a, b) micro "r2 = mul a 3; r3 = add r2 b; r4 = sdiv r3 7; r5 = minu r4 b; r0 = xor r5 r2";
+
+int[12] v;
+int h;
+int mix(int r) { h = h * 31 + r; return 0; }
+int show(char* name) { rt.put_s(name); rt.put_c(32); rt.put_n(h); rt.put_c(10); h = 0; return 0; }
+
+unchecked int main() {
+	int i, j, a, b; word g = rt.new(4);
+	v[0] = 0; v[1] = 1; v[2] = 0 - 1; v[3] = 1 << 63; v[4] = (1 << 63) - 1; v[5] = 7; v[6] = 0 - 7; v[7] = 63; v[8] = 64; v[9] = 65; v[10] = 100; v[11] = 0x123456789;
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_add(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_add(a, 0)); mix(e_add(a, 0 - 1)); mix(e_add(a, 3)); mix(e_add(a, 64)); mix(e_add(a, 0x7fffffff)); }
+	show("add");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_sub(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_sub(a, 0)); mix(e_sub(a, 0 - 1)); mix(e_sub(a, 3)); mix(e_sub(a, 64)); mix(e_sub(a, 0x7fffffff)); }
+	show("sub");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_mul(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_mul(a, 0)); mix(e_mul(a, 0 - 1)); mix(e_mul(a, 3)); mix(e_mul(a, 64)); mix(e_mul(a, 0x7fffffff)); }
+	show("mul");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_sdiv(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_sdiv(a, 0)); mix(e_sdiv(a, 0 - 1)); mix(e_sdiv(a, 3)); mix(e_sdiv(a, 64)); mix(e_sdiv(a, 0x7fffffff)); }
+	show("sdiv");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_udiv(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_udiv(a, 0)); mix(e_udiv(a, 0 - 1)); mix(e_udiv(a, 3)); mix(e_udiv(a, 64)); mix(e_udiv(a, 0x7fffffff)); }
+	show("udiv");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_srem(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_srem(a, 0)); mix(e_srem(a, 0 - 1)); mix(e_srem(a, 3)); mix(e_srem(a, 64)); mix(e_srem(a, 0x7fffffff)); }
+	show("srem");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_urem(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_urem(a, 0)); mix(e_urem(a, 0 - 1)); mix(e_urem(a, 3)); mix(e_urem(a, 64)); mix(e_urem(a, 0x7fffffff)); }
+	show("urem");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_and(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_and(a, 0)); mix(e_and(a, 0 - 1)); mix(e_and(a, 3)); mix(e_and(a, 64)); mix(e_and(a, 0x7fffffff)); }
+	show("and");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_or(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_or(a, 0)); mix(e_or(a, 0 - 1)); mix(e_or(a, 3)); mix(e_or(a, 64)); mix(e_or(a, 0x7fffffff)); }
+	show("or");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_xor(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_xor(a, 0)); mix(e_xor(a, 0 - 1)); mix(e_xor(a, 3)); mix(e_xor(a, 64)); mix(e_xor(a, 0x7fffffff)); }
+	show("xor");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_shl(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_shl(a, 0)); mix(e_shl(a, 0 - 1)); mix(e_shl(a, 3)); mix(e_shl(a, 64)); mix(e_shl(a, 0x7fffffff)); }
+	show("shl");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_shr(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_shr(a, 0)); mix(e_shr(a, 0 - 1)); mix(e_shr(a, 3)); mix(e_shr(a, 64)); mix(e_shr(a, 0x7fffffff)); }
+	show("shr");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_sar(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_sar(a, 0)); mix(e_sar(a, 0 - 1)); mix(e_sar(a, 3)); mix(e_sar(a, 64)); mix(e_sar(a, 0x7fffffff)); }
+	show("sar");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_lt(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_lt(a, 0)); mix(e_lt(a, 0 - 1)); mix(e_lt(a, 3)); mix(e_lt(a, 64)); mix(e_lt(a, 0x7fffffff)); }
+	show("lt");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_ltu(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_ltu(a, 0)); mix(e_ltu(a, 0 - 1)); mix(e_ltu(a, 3)); mix(e_ltu(a, 64)); mix(e_ltu(a, 0x7fffffff)); }
+	show("ltu");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_eq(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_eq(a, 0)); mix(e_eq(a, 0 - 1)); mix(e_eq(a, 3)); mix(e_eq(a, 64)); mix(e_eq(a, 0x7fffffff)); }
+	show("eq");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_ne(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_ne(a, 0)); mix(e_ne(a, 0 - 1)); mix(e_ne(a, 3)); mix(e_ne(a, 64)); mix(e_ne(a, 0x7fffffff)); }
+	show("ne");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_min(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_min(a, 0)); mix(e_min(a, 0 - 1)); mix(e_min(a, 3)); mix(e_min(a, 64)); mix(e_min(a, 0x7fffffff)); }
+	show("min");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_max(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_max(a, 0)); mix(e_max(a, 0 - 1)); mix(e_max(a, 3)); mix(e_max(a, 64)); mix(e_max(a, 0x7fffffff)); }
+	show("max");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_minu(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_minu(a, 0)); mix(e_minu(a, 0 - 1)); mix(e_minu(a, 3)); mix(e_minu(a, 64)); mix(e_minu(a, 0x7fffffff)); }
+	show("minu");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_maxu(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_maxu(a, 0)); mix(e_maxu(a, 0 - 1)); mix(e_maxu(a, 3)); mix(e_maxu(a, 64)); mix(e_maxu(a, 0x7fffffff)); }
+	show("maxu");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_mulhs(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_mulhs(a, 0)); mix(e_mulhs(a, 0 - 1)); mix(e_mulhs(a, 3)); mix(e_mulhs(a, 64)); mix(e_mulhs(a, 0x7fffffff)); }
+	show("mulhs");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_mulhu(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_mulhu(a, 0)); mix(e_mulhu(a, 0 - 1)); mix(e_mulhu(a, 3)); mix(e_mulhu(a, 64)); mix(e_mulhu(a, 0x7fffffff)); }
+	show("mulhu");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_rotl(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_rotl(a, 0)); mix(e_rotl(a, 0 - 1)); mix(e_rotl(a, 3)); mix(e_rotl(a, 64)); mix(e_rotl(a, 0x7fffffff)); }
+	show("rotl");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_rotr(a, b)); }
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_rotr(a, 0)); mix(e_rotr(a, 0 - 1)); mix(e_rotr(a, 3)); mix(e_rotr(a, 64)); mix(e_rotr(a, 0x7fffffff)); }
+	show("rotr");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(u_neg(a)); } mix(u_neg(0)); mix(u_neg(0 - 1)); mix(u_neg(8));
+	show("neg");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(u_not(a)); } mix(u_not(0)); mix(u_not(0 - 1)); mix(u_not(8));
+	show("not");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(u_clz(a)); } mix(u_clz(0)); mix(u_clz(0 - 1)); mix(u_clz(8));
+	show("clz");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(u_ctz(a)); } mix(u_ctz(0)); mix(u_ctz(0 - 1)); mix(u_ctz(8));
+	show("ctz");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(u_abs(a)); } mix(u_abs(0)); mix(u_abs(0 - 1)); mix(u_abs(8));
+	show("abs");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(u_bswap(a)); } mix(u_bswap(0)); mix(u_bswap(0 - 1)); mix(u_bswap(8));
+	show("bswap");
+	for (i = 0; i < 12; i++) { a = v[i]; mix(e_sel(a, 5, 9)); mix(e_sel(a, a, 0 - a)); mix(e_sel(0, a, 2)); }
+	show("sel");
+	mix(e_ld(0 - 1)); mix(e_ld(1 << 62)); a = g; mix(e_ld(a) == g[0]); mix(e_st(a, 42)); mix(g[0]); mix(e_st(0 - 5, 1));
+	show("ld st");
+	for (i = 0; i < 12; i++) for (j = 0; j < 12; j++) { a = v[i]; b = v[j]; mix(e_mix(a, b)); mix(e_mix(a, 5)); }
+	show("mix");
+	rt.free(g);
+	return 0;
+}
diff --git a/tests/test.sh b/tests/test.sh
index 7a80c3c..cdce083 100755
--- a/tests/test.sh
+++ b/tests/test.sh
@@ -227,6 +227,8 @@ ABC" "$l o3 lifts byte loads and stores"
 	chk "$($vm < tests/programs/boundsrules.zc 2>&1 | head -3)" $'5\n7\nzy: index 5 out of range (length 4)' "$l unbounded as prefix, block and statement, o3 implies it; checked code reports"
 	chk "$($vm < tests/programs/bounds_fixed.zc 2>&1 | head -3)" $'55\n29\nzy: index 6 out of range (length 6)' "$l a fixed array with a variable index is checked against its length"
 	chk "$($vm < tests/programs/bounds_heap.zc 2>&1 | head -4)" $'3\n0\nx\nzy: index 11 out of range (length 11)' "$l a pointer to a heap block is checked against its payload"
+	chk "$($vm < tests/programs/enh_ops.zc | md5sum)" "$(md5sum < tests/programs/enh_ops.expected)" "$l enhancement micro-ops on edge values, with variables and with literals"
+	chk "$($vm < tests/programs/bounds_proof.zc)" $'0\n1\n1' "$l a loop test against a constant drops the fixed-array check; a variable bound keeps it"
 	chk "$($vm < tests/programs/zc0unbounded.zc)" "42" "$l unbounded in the unit, a prefix and a statement"
 	local r; r=$(bash tests/runerr.sh "$vm" tests/errors | tail -1)
 	chk "$r" "rejected: $(ls tests/errors/*.zc | wc -l | tr -d ' ') passed, 0 failed" "$l analyzer rejects every bad program"
@@ -500,6 +502,15 @@ s_jit() {
 			chk "$(cd $T && qemu-aarch64 -L /usr/aarch64-linux-gnu $T/zyjd < $R/tests/programs/structret.zc)" "3 4 3.500000 4.000000 24 8 1.000000 3.500000" "jit structs returned from a c function (aapcs64 results)"
 		fi
 	else echo "skip jit (no aarch64 toolchain or qemu)"; fi
+	# the x86-64 jit against the interpreter, every program (about a minute; not in the quick path)
+	if [ "$(uname -s)-$(uname -m)" = Linux-x86_64 ] && [ $QUICK = 0 ]; then
+		$CC -pthread -O2 -w -fwrapv -DJTYPE=int -DZYINTERP src/core/core.c src/core/io_linux.c $GI -o $T/zyi || exit 1
+		$CC -pthread -O2 -w -fwrapv -DJTYPE=int src/core/core.c src/core/io_linux.c $GI -o $T/zyx || exit 1
+		bash tests/drivers/jit_x64_test.sh $T/zyi $T/zyx > $T/jit_x64.out 2>&1; r=$?
+		grep '^DIFF' $T/jit_x64.out
+		chk $r 0 "x86-64 jit agrees with the interpreter: $(tail -n 1 $T/jit_x64.out)"
+		chk "$(ZYNOENH=1 $T/zyx < tests/programs/enh_ops.zc | md5sum)" "$(md5sum < tests/programs/enh_ops.expected)" "x86-64 jit with enhancements called through xrun (ZYNOENH=1)"
+	fi
 }
 
 s_llvm() {