bloqade.gemini.common.validation.recursion
recursion¶
bloqade.gemini.common.validation.recursion
Reject Gemini kernels whose call graph contains a cycle.
A Gemini kernel is lowered to a fixed sequence of physical atom moves, so a recursive call graph has no finite lowering and cannot be compiled. Rejecting it is therefore not a limitation we are working around but the correct answer.
Failing early matters for a second reason: every pass downstream diverges on a
cyclic call graph rather than erroring. AddressAnalysis re-analyses each
callee at every call site with no memoisation, so a branching cycle costs
phi ** max_depth interpreter calls — and because kirin’s depth guard returns
bottom instead of raising, the compile presents as an unkillable hang with no
diagnostic. See bloqade-lanes#921 and bloqade-circuit#852.
CallGraph below is deliberately self-contained rather than reusing
kirin.analysis.CallGraph, which recurses without a visited set and raises
RecursionError on precisely the inputs this module exists to diagnose
(kirin#703). It also differs in two ways worth keeping if this is upstreamed:
edges are keyed caller -> callee (matching how they read), and callees are found
through the ir.StaticCall trait rather than an isinstance check against
func.Invoke, so any dialect that declares the trait participates.