diff options
| -rw-r--r-- | TODO.md | 2 | ||||
| -rw-r--r-- | src/compiler/analyzer.zc | 19 |
2 files changed, 20 insertions, 1 deletions
@@ -534,7 +534,7 @@ brief someone without re-reading the code. - fib is slightly slower under o3 than plain (0.86 against 0.78 ms), likely region entry and exit on every recursive call; related to direct o3-to-o3 calls. - a compiled o3 region that stores into its own code finishes the current activation on the old code; the change takes effect on the next entry. either document it or bail to the region interpreter when the hook drops the running region. - [ ] (in progress on work/exactsize) exact-size bounds checks: n is stored in p[-4] bits 32..62 and the check is 2 loads. -- [ ] (on work/checks) bounds checks out of loops and `--explain-checks`. done: a for loop's body is read ahead (`body_scan` in analyzer.zc) for the names it assigns, increments or takes the address of, closures, and anything that might free a block (calls, push/pop/resize/defer/asm/quote/new, stores to locals that can own); loop proofs now need a body that leaves the index, the bound and the array alone (before, a body that moved the index after a proved access was unchecked on the next iteration). `i < n` with an int n hoists the check to a flag computed at the loop entry (`hoist_guard`, `hoist_stub`): the check still runs, in place, when the flag says it can fail, so faults and side effects keep their order. a pointer set from `rt.new(n)` with a constant n is proved by `i < k` (k <= n) or hoisted, using the requested size (never the rounded block size), and only when the body cannot free or resize anything. `zy --explain-checks [file] < src` prints the kept checks as json lines from the same decisions (format v1 in docs/SPEC.md 4.15.4; consumers ignore unknown kinds, reasons and fields; `o3-candidate` is a possible future kind). later: hoisting for growable arrays with a variable bound, `while` loops, pointer sizes from `len()` once exact sizes land, mechanical `edit`s, tracking ownership precisely enough to hoist past calls that cannot free. +- [ ] (on work/checks) bounds checks out of loops and `--explain-checks`. done: a for loop's body is read ahead (`body_scan` in analyzer.zc) for the names it assigns, increments or takes the address of, closures, and anything that might free a block (calls, push/pop/resize/defer/asm/quote/new, stores to locals that can own); loop proofs now need a body that leaves the index, the bound and the array alone (before, a body that moved the index after a proved access was unchecked on the next iteration). `i < n` with an int n hoists the check to a flag computed at the loop entry (`hoist_guard`, `hoist_stub`): the check still runs, in place, when the flag says it can fail, so faults and side effects keep their order. a pointer set from `rt.new(n)` with a constant n is proved by `i < k` (k <= n) or hoisted, using the requested size (never the rounded block size), and only when the body cannot free or resize anything. `zy --explain-checks [file] < src` prints the kept checks as json lines from the same decisions (format v1 in docs/SPEC.md 4.15.4; consumers ignore unknown kinds, reasons and fields; `o3-candidate` is a possible future kind). later: hoisting for growable arrays with a variable bound, `while` loops, pointer sizes from `len()` once exact sizes land, mechanical `edit`s, tracking ownership precisely enough to hoist past calls that cannot free. cleanup: let the `bs_*` body scanner reuse capture_scan's token skipping instead of its own (about 0.5 to 1k genome words). the `--explain-checks` writer is `src/lib/explain.zc`, embedded and compiled only in that mode (a unit that defines its own `explain` namespace would clash with it). - [ ] (in progress on work/bench) `make bench`, `bench-check` and `bench-selftest`: baseline from ec49c6d, jit and llvm rows, interp rows only with `INTERP=1`. follow-up: fill the checks column from `--explain-checks` and re-save the baseline; the rule that fails when the check count rises is already in bench-check. - [ ] lsp and vscode bounds hints: diagnostics for kept checks with an all / loops / off setting, quick fixes, and a hot-checks command; the vscode extension supports all of it. later: `o3-candidate` hints for hot loops outside o3. - [ ] hoisting v2: use the u/m/d ownership tags to prove a loop can't free a pointer (v1 refuses to hoist when the loop body has any free, release or realloc, or any call that might free). diff --git a/src/compiler/analyzer.zc b/src/compiler/analyzer.zc index c2ea867..d1f6f3d 100644 --- a/src/compiler/analyzer.zc +++ b/src/compiler/analyzer.zc @@ -533,6 +533,7 @@ int proven_n(int ix, int n) { // 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]++; @@ -542,6 +543,7 @@ int body_name(word r, int nm) { // 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)); @@ -552,6 +554,7 @@ int body_mayfree(int nm, int pk2, int pv2) { // 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; } @@ -564,6 +567,7 @@ int bs_adv(word r) { return 0; } // a bracketed group from the current ( [ or {, through its closer + int bs_group(word r) { int depth = 0; while (1) { @@ -577,6 +581,7 @@ int bs_group(word r) { } // 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; } @@ -619,6 +624,7 @@ int body_scan(word r) { 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; @@ -627,6 +633,7 @@ int ldirty(word r, int nm) { } // 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; @@ -634,6 +641,7 @@ int lclean(int i) { 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; @@ -644,6 +652,7 @@ word linfo_new(int k) { 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; @@ -659,6 +668,7 @@ word linfo(int k) { // 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; @@ -682,6 +692,7 @@ int hoist_guard(int ix, int n, int arr) { } // 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); @@ -696,6 +707,7 @@ int hoist_stub(word r, int c0) { } // 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) { @@ -709,6 +721,7 @@ int proven_p(int ix, int n, int arr) { 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; @@ -718,6 +731,7 @@ word lafact_save() { } // 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; @@ -727,6 +741,7 @@ int lafact_keep(word r, word b) { } // 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; @@ -743,6 +758,7 @@ word entry_fact(int ix, int bl) { // 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; @@ -758,6 +774,7 @@ int ptr_elems(word f, word et, int bl) { // 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; @@ -774,6 +791,7 @@ int xc_reason(int ix, int arr) { } // the record of one kept check: kind 0 index, 1 pointer; the place of its [ // and, as the end, the token just read (its ]). src/lib/explain.zc writes it. + int xc_note(int kind, int why, int place) { int o1, o2, d = 0, k = loopbase, f; if (!xc_on || dry || cmode || incdepth > 0 || !xc_src || chbase != xc_src || !xc_hook) return 0; @@ -785,6 +803,7 @@ int xc_note(int kind, int why, int place) { } // is argument 1 --explain-checks? the file name for the records is argument 2. // then src/lib/explain.zc is compiled, and its note becomes the hook. + int xc_init() { int n = rt.syscall(rt.SYS_ARGC, 0, 0, 0), k, s, f; word b; if (n < 2) return 0; |