bounds: body scan, loop-entry hoisting, pointer proofs from requested size, --explain-checks v1 (non-o3 code)

1 files changed, 328 insertions, 0 deletions

diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc
index 89713ff..1822fe5 100644
--- a/src/compiler/analyzer.zc
+++ b/src/compiler/analyzer.zc
@@ -512,6 +512,334 @@ int proven_n(int ix, int n) {
 	}
 	return 0;
 }
+// ---- loop bodies and hoisted checks ----
+
+// a loop proof only holds while the body leaves the index, the bound and the
+// array alone. the compiler reads the body once, in order, so before it
+// compiles one it reads its tokens ahead (as capture_scan does) and notes
+// every name the body assigns, increments, decrements or takes the address
+// of. the record is r = lpinfo + depth * LPI_W: r[0] is 1 when the scan could
+// not see the whole body (the source is stdin, it ran out) or found a closure
+// (which can change any captured local), and then every name counts; r[1]
+// names follow from r[2], at most 32. the body is read as one statement, the
+// way the parser will read it (bs_stmt).
+// r[40] the loop's index variable (or -1), r[41] its bound, r[42] the entry
+// jump to patch, r[43] how many hoisted checks, r[44..47] their element
+// counts, r[48..51] their flag slots, r[52] 1 when checks against the bound
+// can be hoisted, r[53] 1 when index and bound are left alone, r[54] 1 when
+// the record is in use, r[55] 1 when the body might free or resize a block
+// (any pointer, which may alias the one a proof is about): it calls a function,
+// uses push, pop, resize, defer, asm, quote or new, or stores to a local that
+// can own a block. then the size a pointer proof read can change. r[56] the
+// allocation facts of the locals at the loop entry (lafact_save), which the
+// loop top forgets.
+int body_name(word r, int nm) {
+	if (r[1] >= 32) { r[0] = 1; return 0; }
+	r[2 + r[1]] = nm; r[1]++;
+	return 0;
+}
+// can a store to the name nm free a block? a store to a pointer, a word or
+// an array local can (an owner frees what it held), and so can one to a name
+// the loop declares, unless a number type comes right before it (pk2, pv2: the
+// token before the name)
+int body_mayfree(int nm, int pk2, int pv2) {
+	int j = findloc(nm); word t;
+	if (j < 0) return !(pk2 == T_ID && (pv2 == sx_int || pv2 == sx_char || pv2 == sx_bool || pv2 == sx_float));
+	t = ltype[j];
+	if (!t || t == tword || isptr(t) || t[0] == TY_DYN || tracked(j)) return 1;
+	return 0;
+}
+// the scan's view of the token before the current one and the one before that
+int bs_pk, bs_pv, bs_pk2, bs_pv2;
+// note what the current token says about the body, then read the next one
+int bs_adv(word r) {
+	int j;
+	if (is_id(s_fn)) { peek(); if (pk_tk == T_OP && (pk_tv == s_lp || pk_tv == s_colon)) r[0] = 1; }
+	if (tk == T_OP && bs_pk == T_ID && (tv == s_eq || tv == s_inc || tv == s_dec || asgfind(tv) >= 0)) { body_name(r, bs_pv); if (body_mayfree(bs_pv, bs_pk2, bs_pv2)) r[55] = 1; }
+	if (tk == T_ID && bs_pk == T_OP && (bs_pv == s_inc || bs_pv == s_dec || bs_pv == s_amp)) body_name(r, tv);
+	if (tk == T_OP && tv == s_lp && bs_pk == T_ID) { j = lookup(bs_pv); if (j < 0 || skind[j] != K_KW) r[55] = 1; }
+	if (tk == T_ID && (tv == sx_push || tv == sx_pop || tv == sx_resize || tv == sx_defer || tv == sx_asm || tv == sx_quote || tv == sx_new)) r[55] = 1;
+	bs_pk2 = bs_pk; bs_pv2 = bs_pv; bs_pk = tk; bs_pv = tv;
+	next();
+	return 0;
+}
+// a bracketed group from the current ( [ or {, through its closer
+int bs_group(word r) {
+	int depth = 0;
+	while (1) {
+		if (tk == T_EOF) { r[0] = 1; return 0; }
+		if (tk == T_OP && (tv == s_lb || tv == s_lp || tv == s_lk)) depth++;
+		else if (tk == T_OP && (tv == s_rb || tv == s_rp || tv == s_rk)) depth--;
+		bs_adv(r);
+		if (depth <= 0) return 0;
+	}
+	return 0;
+}
+// one statement, read the way the parser will: a block, if/else, a loop or
+// switch with its body, do/while, or anything else up to its ; at depth 0
+int bs_stmt(word r) {
+	int depth = 0;
+	if (tk == T_EOF) { r[0] = 1; return 0; }
+	if (is_op(s_lb)) return bs_group(r);
+	if (is_id(sx_if)) {
+		bs_adv(r); if (is_op(s_lp)) bs_group(r);
+		bs_stmt(r);
+		if (is_id(sx_else)) { bs_adv(r); bs_stmt(r); }
+		return 0;
+	}
+	if (is_id(sx_while) || is_id(sx_for) || is_id(sx_switch)) {
+		bs_adv(r); if (is_op(s_lp)) bs_group(r);
+		return bs_stmt(r);
+	}
+	if (is_id(sx_do)) {
+		bs_adv(r); bs_stmt(r);
+		if (is_id(sx_while)) { bs_adv(r); if (is_op(s_lp)) bs_group(r); }
+		if (is_op(s_semi)) bs_adv(r);
+		return 0;
+	}
+	while (1) {
+		if (tk == T_EOF) { r[0] = 1; return 0; }
+		if (tk == T_OP && (tv == s_lb || tv == s_lp || tv == s_lk)) depth++;
+		else if (tk == T_OP && (tv == s_rb || tv == s_rp || tv == s_rk)) { depth--; if (depth < 0) return 0; }
+		if (depth == 0 && is_op(s_semi)) { bs_adv(r); return 0; }
+		bs_adv(r);
+	}
+	return 0;
+}
+int body_scan(word r) {
+	word old, f; int docs = docs_on, record = grec, sp = panic;
+	r[0] = 0; r[1] = 0; r[55] = 0;
+	if (isp < 0 || R_SRC[isp * 32] == 0) { r[0] = 1; return 0; }
+	src_push(1, capture_dummy, 0, 0); old = R_SRC + (isp - 1) * 32; f = R_SRC + isp * 32;
+	f[0] = old[0]; f[1] = old[1]; f[2] = old[2]; f[3] = old[3]; f[4] = 0; pq_n = f[14];
+	docs_on = 0; grec = 0; dry++;
+	bs_pk = 0; bs_pv = 0; bs_pk2 = 0; bs_pv2 = 0;
+	bs_stmt(r);
+	dry--; src_pop(); docs_on = docs; grec = record; panic = sp;
+	return 0;
+}
+// may the loop body behind r change the local named nm?
+int ldirty(word r, int nm) {
+	int k = 0;
+	if (!r || r[0]) return 1;
+	while (k < r[1]) { if (r[2 + k] == nm) return 1; k++; }
+	return 0;
+}
+// a local nothing outside the function's own code can change: no address
+// taken, not captured by a closure
+int lclean(int i) {
+	if (laaddr[i]) return 0;
+	if (local_cell && local_cell[i]) return 0;
+	if (local_captured && local_captured[i]) return 0;
+	return 1;
+}
+// a fresh record for the loop at depth k, or 0 past the first LPI_N depths
+word linfo_new(int k) {
+	word r;
+	if (k >= LPI_N) return 0;
+	if (!lpinfo) lpinfo = chk_resize(0, 0, LPI_N * LPI_W);
+	r = lpinfo + k * LPI_W;
+	rt.fill_w(r, 0, LPI_W);
+	r[54] = 1;
+	return r;
+}
+// the record of the live loop at depth k, or 0
+word linfo(int k) {
+	word r;
+	if (k >= LPI_N || !lpinfo) return 0;
+	r = lpinfo + k * LPI_W;
+	if (!r[54]) return 0;
+	return r;
+}
+// for a check of index ix against n elements of the array local arr (-1 for
+// a fixed array) inside a loop "for (...; ix < bound; ix++)" whose body leaves
+// ix and bound alone: the loop entry works out once whether ix < bound <= n
+// can fail (0 <= ix at the entry, bound <= n), and the check runs only when it
+// can. a plain early fault would move the fault before the side effects of the
+// iterations that come first; the flag keeps the check where it was. emits
+// the load of the flag and the jump over the check; returns the hole to patch
+// past it, or -1 when the check cannot be hoisted.
+int hoist_guard(int ix, int n, int arr) {
+	int k = lsp, j; word r;
+	if (ix < 0 || n <= 0) return 0 - 1;
+	while (k > loopbase) {
+		k--;
+		r = linfo(k);
+		if (!r || r[40] != ix) continue;
+		if (!r[52]) return 0 - 1;
+		if (arr >= 0 && (ldirty(r, lname[arr]) || !lclean(arr) || r[55])) return 0 - 1;
+		j = 0;
+		while (j < r[43] && r[44 + j] != n) j++;
+		if (j == r[43]) {
+			if (j >= 4) return 0 - 1;
+			r[44 + j] = n; r[48 + j] = fslots; fslots++; r[43]++;
+		}
+		laddr(r[48 + j]); op(O_LD);
+		j = hole(); op(O_JZ);
+		return j;
+	}
+	return 0 - 1;
+}
+// the loop entry of a loop with hoisted checks: each flag is 1 when ix < 0 or
+// bound > n, then on to the test at c0
+int hoist_stub(word r, int c0) {
+	int k = 0;
+	setlit(r[42], here);
+	while (k < r[43]) {
+		vaddr(r[40]); op(O_LD); lit(r[44 + k]); vaddr(r[41]); op(O_LD); op(O_SUB); op(17);
+		lit(0); op(O_LT);
+		laddr(r[48 + k]); op(O_ST);
+		k++;
+	}
+	jmp(c0);
+	return 0;
+}
+// i < n for a pointer local arr to a block of n words: a loop test against a
+// constant of at most n, in a loop whose body leaves arr alone
+int proven_p(int ix, int n, int arr) {
+	int k = lsp, w; word r;
+	while (k > loopbase) {
+		k--;
+		w = lpfact[k];
+		if (w >= 0 && p_iv(w) == ix && p_bd(w) == -1 && 0 - p_ar(w) - 2 <= n) {
+			r = linfo(k);
+			return r && !ldirty(r, lname[arr]) && lclean(arr) && !r[55];
+		}
+	}
+	return 0;
+}
+// the allocation facts of the function's locals, kept past the loop top that forgets them
+word lafact_save() {
+	word b; int i = lbase;
+	if (dry || nloc <= lbase) return 0;
+	b = chk_resize(0, 0, nloc - lbase + 2); b[0] = lbase; b[1] = nloc;
+	while (i < nloc) { b[2 + i - lbase] = lafact[i]; i++; }
+	return b;
+}
+// after a loop that frees nothing: the locals its body left alone get back the
+// allocation facts the loop forgot
+int lafact_keep(word r, word b) {
+	int i;
+	if (!b || dry || r[0] || r[55]) return 0;
+	i = b[0];
+	while (i < b[1] && i < nloc) { if (b[2 + i - b[0]] && !lafact[i] && !ldirty(r, lname[i]) && lclean(i)) lafact[i] = b[2 + i - b[0]]; i++; }
+	return 0;
+}
+// the allocation fact of the pointer local bl at the entry of the innermost
+// loop over ix, or 0
+word entry_fact(int ix, int bl) {
+	int k = lsp; word r, b;
+	if (ix < 0 || bl < 0) return 0;
+	while (k > loopbase) {
+		k--;
+		r = linfo(k);
+		if (!r || r[40] != ix) continue;
+		b = r[56];
+		if (!b || bl < b[0] || bl >= b[1]) return 0;
+		return b[2 + bl - b[0]];
+	}
+	return 0;
+}
+// the number of elements behind a pointer local: the requested size of the
+// block it was set from, when the analyzer knows it (never a rounded block
+// size), for one-word elements; -1 when unknown
+int ptr_elems(word f, word et, int bl) {
+	word base;
+	if (bl < 0 || !f || f[1] == 2 || f[0] < 0 || tbytes(et) || tsz(et) != 1) return 0 - 1;
+	if (f[6]) { base = af_base(f); if (base[1] == 0 || base[10] < 0) return 0 - 1; if (f[14] && f[13]) return 0 - 1; }	// as af_inrange: a live allocation, from its start
+	return f[0];
+}
+
+// ---- --explain-checks ----
+
+// zy --explain-checks [file] < source compiles the unit without running it and
+// prints, as json lines, every bounds check the compiler kept, from the same
+// decisions that drop the others. the first line is {"version":1}; the format
+// is in docs/SPEC.md. the reason codes:
+const int XC_NOT_LOOP = 1, XC_NOT_INVARIANT = 2, XC_NOT_LEN = 3, XC_SIZE = 4, XC_PACKED = 5, XC_HOISTED = 6, XC_MAYFREE = 7;
+// why a check of index ix (a local, or -1) into the array local arr stays
+int xc_reason(int ix, int arr) {
+	int k = lsp; word r;
+	if (ix < 0) return XC_NOT_LOOP;
+	while (k > loopbase) {
+		k--;
+		r = linfo(k);
+		if (!r || r[40] != ix) continue;
+		if (!r[53]) return XC_NOT_INVARIANT;
+		if (arr >= 0 && (ldirty(r, lname[arr]) || !lclean(arr))) return XC_NOT_INVARIANT;
+		if (arr >= 0 && r[55]) return XC_MAYFREE;
+		return XC_NOT_LEN;
+	}
+	return XC_NOT_LOOP;
+}
+// one character of the unit's source
+int xc_byte(int k) { return (xc_src[k >> 2] >> ((k & 3) * 8)) & 255; }
+// the column (from 1) of the source offset o
+int xc_col(int o) {
+	int k = o;
+	while (k > 0 && xc_byte(k - 1) != 10) k--;
+	return o - k + 1;
+}
+// a json string
+int xc_str(char* s) {
+	int i = 0, ch;
+	rt.put_c(34);
+	while (s[i]) {
+		ch = s[i] & 255;
+		if (ch == 34 || ch == 92) rt.put_c(92);
+		if (ch < 32) rt.put_c(32); else rt.put_c(ch);
+		i++;
+	}
+	rt.put_c(34);
+	return 0;
+}
+int xc_field(char* name) { rt.put_c(44); xc_str(name); rt.put_c(58); return 0; }
+// the record of one kept check: kind 0 index, 1 pointer; the place of its [
+// and, as the end, the token just read (its ])
+int xc_note(int kind, int why, int place) {
+	int o1, o2, d = 0, k = loopbase;
+	if (!xc_on || dry || cmode || incdepth > 0 || !xc_src || chbase != xc_src) return 0;
+	o1 = ((place >> 40) & 0x1FFFFF) - 1; o2 = tpend;
+	if (o1 < 0 || o2 < o1) return 0;
+	while (k < lsp) { if (R_LOOP[k * 8] != 0 - 1) d++; k++; }
+	rt.put_s("{\"file\":"); xc_str(xc_file);
+	xc_field("line"); rt.put_n(place & 0xFFFFFF);
+	xc_field("col"); rt.put_n(xc_col(o1));
+	xc_field("end_line"); rt.put_n(tpline);
+	xc_field("end_col"); rt.put_n(xc_col(o2));
+	xc_field("fn"); xc_str(xc_fn);
+	xc_field("kind"); if (kind) xc_str("pointer"); else xc_str("index");
+	xc_field("loop_depth"); rt.put_n(d);
+	xc_field("reason");
+	if (why == XC_NOT_LOOP) xc_str("index-not-loop-variable");
+	else if (why == XC_NOT_INVARIANT) xc_str("bound-not-invariant");
+	else if (why == XC_NOT_LEN) xc_str("index-not-len-derived");
+	else if (why == XC_SIZE) xc_str("size-unknown");
+	else if (why == XC_PACKED) xc_str("packed-elements");
+	else if (why == XC_MAYFREE) xc_str("pointer-may-be-freed");
+	else xc_str("hoisted-to-loop-entry");
+	xc_field("fix");
+	if (why == XC_NOT_LOOP) xc_str("index with the variable of a loop for (i = 0; i < bound; i++), or mark the code unbounded if the index is known to be in range");
+	else if (why == XC_NOT_INVARIANT) xc_str("the loop body changes the index, the bound or the array, takes an address or makes a closure; keep them fixed inside the loop");
+	else if (why == XC_NOT_LEN) xc_str("bound the loop with len() of the array, or with a constant no larger than its length");
+	else if (why == XC_SIZE) xc_str("the compiler does not know the size of the block; allocate it here with a constant size, or index a fixed array");
+	else if (why == XC_PACKED) xc_str("packed elements are checked by the runtime on every access");
+	else if (why == XC_MAYFREE) xc_str("the loop body calls something that might free or resize the block; move the call out of the loop");
+	else xc_str("checked once when the loop starts, and on every access only if that check fails; nothing to do");
+	rt.put_c(125); rt.put_c(10);
+	return 0;
+}
+// is argument 1 --explain-checks? the file name for the records is argument 2
+int xc_init() {
+	int n = rt.syscall(rt.SYS_ARGC, 0, 0, 0), k; word b;
+	if (n < 2) return 0;
+	b = chk_resize(0, 0, 32);
+	if (rt.syscall(rt.SYS_ARG, 1, b, 31) < 0 || !rt.eq_w(b, "--explain-checks")) return 0;
+	xc_on = 1;
+	if (n > 2) { k = rt.syscall(rt.SYS_ARG, 2, 0, 0); if (k >= 0) { b = chk_resize(0, 0, k + 1); rt.syscall(rt.SYS_ARG, 2, b, k + 1); xc_file = b; } }
+	rt.put_s("{\"version\":1}"); rt.put_c(10);
+	return 0;
+}
 // is the constant index xcval known to be inside the allocation f? the same
 // facts af_index warns from, so a possible failure is never called definite.
 int af_inrange(word f) {