bloqade.gemini.common.validation.recursion.CallGraph

← Module overview

classCallGraph¶source

bloqade.gemini.common.validation.recursion.CallGraph

Static call graph rooted at ``entry``, keyed caller -> callees.

class CallGraph(mt: ir.Method)

Public import paths

• from bloqade.gemini.common.validation.call_site import CallGraph

Construction is an iterative worklist, so a recursive kernel produces a graph containing a cycle instead of exhausting the Python stack.

Only statically resolved edges are followed. A dynamic func.Call through an SSA value is invisible here: resolving one needs the same constant propagation that diverges on cyclic input, so it cannot be used by a guard whose job is to run first.

ir.Method.backedges looks like it should make this class unnecessary, but cannot be used for any of the three things needed here:

• It is empty when this runs. update_backedges is called from Method.__init__, which completes only after run_pass returns, so at guard time every method’s backedges is still an empty set.
• It goes stale. It is populated once at construction and never invalidated, so after the inliner has spliced a callee away the edge is still recorded. That matters for the post-fold re-check, which would then see cycles that no longer exist.
• It points the wrong way. It records callers, but validating a kernel asks what that kernel reaches, rooted at the kernel itself.

It also derives from the same ir.StaticCall trait, so it would miss the unresolved self call for the same reason a plain forward walk does.

Parameters

Name	Type	Description
mt	ir.Method

Attributes

Name	Type	Default	Description
entry	ir.Method	mt
edges	dict[ir.Method, set[ir.Method]]	{}

methodcallees¶source

bloqade.gemini.common.validation.recursion.CallGraph.callees

def callees(method: ir.Method) -> list[ir.Method]

Callees of method, in a deterministic order.

Parameters

Name	Type	Description
method	ir.Method

Returns

list[ir.Method]

source

methodfind_cycles¶source

bloqade.gemini.common.validation.recursion.CallGraph.find_cycles

def find_cycles() -> list[Cycle]

Return one representative cycle per distinct set of mutual callers.

An empty list means the call graph is acyclic. The traversal is an explicit-stack DFS so that deeply nested (but acyclic) call graphs stay safe too.

Returns

list[Cycle]

source