CallGraph analysis misses ilist.map (and other higher-order) calls; needs a call-discovery trait

[weinbe58]

Summary

kirin.analysis.callgraph.CallGraph does not treat ilist.map (and the other higher-order ilist statements) as calls, even though the function they apply is logically part of the call graph. As a result, any analysis or rewrite that walks the call graph silently skips the function body referenced by an ilist.map's fn operand.

Current behavior

CallGraph.__build only recognizes func.Invoke and hardcodes the isinstance check:

# kirin/analysis/callgraph.py
def __build(self, mt: ir.Method):
    for stmt in mt.callable_region.walk():
        if isinstance(stmt, func.Invoke):          # <-- only func.Invoke
            edges = self.edges.setdefault(stmt.callee, set())
            edges.add(mt)
            self.__build(stmt.callee)

So a statement like ilist.Map (kirin/dialects/ilist/stmts.py), which references the applied function through an SSA operand:

class Map(ir.Statement):
    traits = frozenset({ir.MaybePure(), lowering.FromPythonCall()})
    fn: ir.SSAValue = info.argument(types.MethodType[[ElemT], OutElemT])
    ...

is never added as an edge. The same applies to Foldl, Foldr, Scan, and ForEach, all of which take a fn: ir.SSAValue of MethodType.

Why it matters

Anything built on the call graph (e.g. CallGraphPass, and more generally rewrites that expect to descend into every reachable method) does not reach code that only runs inside an ilist.map closure. This forces awkward workarounds downstream — for example, a dialect statement that must be resolved at compile time cannot be marked ir.Pure if it might appear inside an ilist.map, because constant folding hoists the pure closure into an opaque constant Method and the call graph never descends into it, so the statement is never resolved.

(Concrete downstream impact: QuEraComputing/bloqade-circuit#830.)

Proposed direction

Make CallGraph trait-driven instead of isinstance(func.Invoke)-driven.

kirin already has the StaticCall trait (kirin/ir/traits/callable.py):

class StaticCall(StmtTrait, ABC, Generic[StmtType]):
    @classmethod
    @abstractmethod
    def get_callee(cls, stmt: StmtType) -> "Method": ...

and func.Invoke carries InvokeCall(ir.StaticCall["Invoke"]). The call graph should query this trait rather than the concrete type:

for stmt in mt.callable_region.walk():
    if (trait := stmt.get_trait(ir.StaticCall)) is not None:
        callee = trait.get_callee(stmt)
        ...

That alone fixes the trait-vs-isinstance coupling, but ilist.map's callee is not a static attribute — it comes from an SSA fn operand whose value may be a constant Method (or need const-prop / resolution to find one). StaticCall.get_callee returning a single Method may not be sufficient for these higher-order statements.

So the proposal is to introduce a trait dedicated to "this statement invokes a function as part of its semantics, and here is how to find the callee(s)" that higher-order statements like ilist.map can implement — e.g. by pointing at the operand that holds the Method, and tolerating the case where the callee is only known after constant propagation. CallGraph would then enumerate edges via this trait, covering both func.Invoke and the ilist higher-order ops uniformly.

Acceptance criteria

• CallGraph discovers calls via a trait, not isinstance(func.Invoke).
• A method that applies a function via ilist.map (and Foldl/Foldr/Scan/ForEach) has an edge to that function in the call graph.
• Existing func.Invoke behavior is unchanged.
• Regression test covering an ilist.map over a method that itself invokes another method (transitive reachability through the closure).

[weinbe58]

Implementation note: resolving the callee via SSAValue.hints

For the higher-order ops (ilist.map et al.) the callee isn't a static attribute — it's the fn: ir.SSAValue operand. The trait can recover a static callee by inspecting that operand's const hint, and return None when it isn't a statically-known Method (i.e. not a static call, so no call-graph edge).

There's an exact precedent in Call2Invoke (kirin/rewrite/call2invoke.py), which lowers a dynamic func.Call to a static func.Invoke by reading the callee's "const" hint:

if (mt := node.callee.hints.get("const")) is None:
    return RewriteResult()
if not isinstance(mt, const.Value):
    return RewriteResult()
if not isinstance(mt.data, ir.Method):
    return RewriteResult()
method = mt.data

So the trait impl for ilist.Map (and Foldl/Foldr/Scan/ForEach) would be roughly:

@classmethod
def get_callee(cls, stmt) -> ir.Method | None:
    hint = stmt.fn.hints.get("const")
    if isinstance(hint, const.Value) and isinstance(hint.data, ir.Method):
        return hint.data
    return None  # not a static call -> no call-graph edge

i.e. the call-discovery trait returns an Optional[Method]: a statically-known callee when fn has a const hint pointing at a Method, otherwise None. CallGraph only adds an edge when it's non-None. (Note: this presumes constant propagation has run so the hint is populated — worth calling out as a precondition for the call graph to see these edges.)