git » blacktide.git » commit 786d596

Keep private loop and join bindings out of parent state

Keep private loop and join bindings out of parent state

Make invariant-parameter pruning respect the lexical boundaries introduced
by structured loop recovery. It previously counted all definitions inside
an inner loop or join value as assignments in the parent loop. Inner slots
are initialized by self-copy, so immutable captures were incorrectly marked
as changed and retained as redundant parent loop/recur parameters.

The Joined language already provides the boundary needed to fix this:

- An inner :loop's bindings and recurrence are private. The changed values
  that return to its parent are exactly the enclosing :join's :targets.
  Therefore assigned returns the empty set for the inner loop itself.
- A :join exports its targets into its body. Its value subtree has private
  bindings, so assigned combines the targets with assignments in the body
  and does not descend into the value subtree.

This depends on the existing structure and region checks: nested recur
cannot target an active ancestor, and a bounded join value must reach its
follow or throw. A tail loop has no returning parent continuation. The
analysis is of changes to parent lexical bindings, not all side effects;
initializers, calls, throws and their evaluation order remain in place.
No new traversal framework, fixed point or code-motion pass is needed.

The regression initializes an immutable bias outside nested dotimes loops:

  (loophole [sum 0 n 0]
    (let [bias (long (first events))]
      (dotimes [i 2]
        (dotimes [j 3]
          (setq sum (+ sum bias) n (inc n)))))
    [sum n])

With events [7], all three backends return [42 6]. The structural assertion
requires both recovered loops to carry exactly three slots: sum, n and
their own index. Bias and the invariant bound remain lexical captures.
Checking the representation is essential: result-only tests cannot detect
the redundant carried state.

The design follows explicit region arguments/results as used by MLIR SCF,
and the exported-value boundary illustrated by LLVM loop-closed SSA. It
uses those scoping principles in Blacktide's existing Joined language,
rather than importing either IR or claiming a general SSA transformation:

  https://mlir.llvm.org/docs/Dialects/SCFDialect/
  https://llvm.org/docs/LoopTerminology.html#loop-closed-ssa-lcssa

Keeping this correction in the existing invariant pass also preserves the
Nanopass separation between control recovery, lexical binding simplification
and representation selection:

  https://andykeep.com/pubs/np-preprint.pdf

Validation after the change:

- clojure -M:test on JDK 17, 21, 25 and 27: 150 tests, 7,362 assertions,
  zero failures/errors on each JVM.
- clojure -M:check on JDK 25 and 27: 16 tests, 166 assertions, zero
  failures/errors on each. Both commands used
  -Sdeps '{:mvn/local-repo "/tmp/loophole-typed-m2"}' and JAVA_CMD per JVM.
- Repeated 51 independent adversarial observations and 12,060 bounded
  differential comparisons (seed 724091), covering all three backends.
- Fresh AOT output is byte-for-byte identical to the preceding commit for
  all 20 measured Datalevin function classes per configuration and all four
  Riemann comparison classes. Its kernel measurements therefore still
  apply; this scope refinement has a structural regression, not a separate
  claimed benchmark speedup.

diff --git a/src/com/tailrecursion/blacktide/compiler/passes/invariants.clj b/src/com/tailrecursion/blacktide/compiler/passes/invariants.clj
index da4900d..eb7a5b4 100644
--- a/src/com/tailrecursion/blacktide/compiler/passes/invariants.clj
+++ b/src/com/tailrecursion/blacktide/compiler/passes/invariants.clj
@@ -9,10 +9,11 @@
 (np/defpass assigned {:from [l/Joined Expr] :to (t/Set t/Sym)}
   [node]
   :bind (conj (assigned (:body node)) (:target (:binding node)))
-  :join (into (set/union (assigned (:value node)) (assigned (:body node))) (:targets node))
+  :join (into (assigned (:body node)) (:targets node))
   :branch (set/union (assigned (:yes node)) (assigned (:no node)))
   :switch (into #{} (mapcat assigned) (:arms node))
-  :loop (into (assigned (:body node)) (:slots node))
+  ;; Inner bindings are private; only enclosing join targets export changes.
+  :loop #{}
   :recur #{} :return #{} :throw #{})
 
 (np/defpass expression {:from [l/Joined Expr] :to [l/Joined Expr] :args [(t/Set t/Sym)]}
diff --git a/test/com/tailrecursion/blacktide/backend_test.clj b/test/com/tailrecursion/blacktide/backend_test.clj
index 25885d5..a430055 100644
--- a/test/com/tailrecursion/blacktide/backend_test.clj
+++ b/test/com/tailrecursion/blacktide/backend_test.clj
@@ -293,7 +293,14 @@
             {:throw clojure.lang.ExceptionInfo
              :trace [[0 0 1 1] [0 1 2 3] [0 2 3 6] [1 0 4 10] :construct]}]]]
     (is (= :structured (:op (capture #'structure/recover form))))
-    (doseq [mode [:default :generic :dispatcher]] (is (= expected (execution form mode))))))
+    (doseq [mode [:default :generic :dispatcher]] (is (= expected (execution form mode)))))
+  (let [form '(loophole [sum 0 n 0]
+                (let [bias (long (first events))]
+                  (dotimes [i 2] (dotimes [j 3] (setq sum (+ sum bias) n (inc n))))) [sum n])
+        program (capture #'storage/select-storage form)
+        loops (filter #(and (map? %) (= :loop (:op %))) (tree-seq coll? seq (:body program)))]
+    (is (= [3 3] (mapv #(count (:slots %)) loops)) "Only sum, n and each loop's index need carrying")
+    (doseq [mode [:default :generic :dispatcher]] (is (= [42 6] ((compile-program form mode) [7]))))))
 
 (defn primitive-target ^long [^long n] (+ n 1))
 (defn primitive-replacement ^long [^long n] (+ n 100))