AddressAnalysis has no call memoization: φ^max_depth cost on recursive call graphs

[weinbe58]

Summary

AddressAnalysis re-analyzes each callee's body at every call site with no memoization, so on a call graph containing a cycle the cost grows as φ^max_depth (golden ratio) rather than reaching a fixpoint. With kirin's default max_depth=800 this is ~10^167 interpreter calls — effectively an unkillable hang.

Versions: bloqade-circuit 0.15.0, kirin-toolchain 0.22.11.

Reproducer (no downstream deps)

import time
from bloqade import squin
from bloqade.analysis.address import AddressAnalysis

@squin.kernel(fold=False)
def B(main):
    B(main)
    main()

@squin.kernel(fold=False)
def main():
    q = squin.qalloc(2)
    B(main)

for d in (10, 14, 18, 22):
    t0 = time.monotonic()
    AddressAnalysis(main.dialects, max_depth=d).run(main)
    print(d, f"{time.monotonic()-t0:.3f}s")

Counting AddressAnalysis.frame_call invocations:

max_depth	frame_calls	seconds	growth per unit depth
10	219	0.006	1.624
14	1,507	0.028	1.619
18	10,335	0.245	1.618
22	70,843	1.353	1.618

The growth factor converges to exactly φ = 1.618: main → B and B → {B, main} is a Fibonacci recurrence, and every path through it is re-walked from scratch.

Root cause

Both call implementations recurse unconditionally into the callee:

• bloqade/analysis/address/impls.py:178-191 — func.Invoke → interp_.call(stmt.callee.code, ...)
• bloqade/analysis/address/impls.py:211-225 — func.Call → interp_.run_lattice(...) → analysis.py:104 → self.call(...)

Neither consults a cache keyed on the callee, so a diamond or cycle in the call graph multiplies work instead of being joined. Both impls carry # TODO comments (# TODO: look for abstract method table for func., # TODO: replace with the generic implementation) suggesting this was always known to be a stopgap.

kirin's depth guard does fire at max_depth, but AbstractInterpreter.recursion_limit_reached() returns bottom rather than raising, so the explosion is silent — it looks like a hang, not an error.

Suggested fix

Memoize call on (callee, input lattice tuple) and join on repeat visits, so recursive call graphs reach a fixpoint (returning bottom for the in-progress entry is the standard treatment). This would also make the diamond-shaped non-recursive case linear instead of exponential.

Found while debugging a hang in bloqade-lanes (gemini.logical.kernel on a recursive kernel).