Skip to content

Abstract

AbstractFrame dataclass 

AbstractFrame(
    code: Statement,
    worklist: WorkList[Successor[ResultType]] = WorkList(),
    visited: dict[
        Block, set[tuple[Successor[ResultType], int]]
    ] = dict(),
    *,
    parent: FrameABC | None = None,
    has_parent_access: bool = False,
    lineno_offset: int = 0,
    entries: dict[SSAValue, ValueType] = dict()
)

Bases: Frame[ResultType]


              flowchart TD
              kirin.interp.abstract.AbstractFrame[AbstractFrame]
              kirin.interp.frame.Frame[Frame]
              kirin.interp.frame.FrameABC[FrameABC]

                              kirin.interp.frame.Frame --> kirin.interp.abstract.AbstractFrame
                                kirin.interp.frame.FrameABC --> kirin.interp.frame.Frame
                



              click kirin.interp.abstract.AbstractFrame href "" "kirin.interp.abstract.AbstractFrame"
              click kirin.interp.frame.Frame href "" "kirin.interp.frame.Frame"
              click kirin.interp.frame.FrameABC href "" "kirin.interp.frame.FrameABC"

Store abstract SSA values and worklist state for an analysis call.

In addition to the SSA-value entries inherited from :class:Frame, an abstract frame owns the pending control-flow successors and the visitation identities already evaluated for each block. A visitation identity combines a path-sensitive successor with the dependency generation maintained by the SSACFG solver. This lets an unchanged control-flow edge run again after an SSA value used by its destination changes.

Assignments record values whose lattice meaning changed in _changes. The SSACFG solver drains that set after evaluating a block and requeues any reached blocks that depend on those values. Multiple pending invalidations at the same latest generation therefore share one visitation identity.

set 

set(key: SSAValue, value: ResultType) -> None

Set the value for the given key. See also set_values.

Parameters:

Name Type Description Default
key KeyType

The key to set the value for.

 required
value ValueType

The value.

 required
Source code in src/kirin/interp/abstract.py 
48
49
50
51
52
53
54
def set(self, key: ir.SSAValue, value: ResultType) -> None:
    previous = self.entries.get(key)
    self.entries[key] = value
    if previous is None or not (
        previous.is_subseteq(value) and value.is_subseteq(previous)
    ):
        self._changes.add(key)

AbstractInterpreter dataclass 

AbstractInterpreter(
    dialects: DialectGroup,
    *,
    max_depth: int = 800,
    max_python_recursion_depth: int = 131072,
    debug: bool = False
)

Bases: InterpreterABC[AbstractFrameType, ResultType], ABC


              flowchart TD
              kirin.interp.abstract.AbstractInterpreter[AbstractInterpreter]
              kirin.interp.abc.InterpreterABC[InterpreterABC]

                              kirin.interp.abc.InterpreterABC --> kirin.interp.abstract.AbstractInterpreter
                


              click kirin.interp.abstract.AbstractInterpreter href "" "kirin.interp.abstract.AbstractInterpreter"
              click kirin.interp.abc.InterpreterABC href "" "kirin.interp.abc.InterpreterABC"

Abstract interpreter for the IR.

This is a base class for implementing abstract interpreters for the IR. It provides a framework for implementing abstract interpreters given a bounded lattice type.

The abstract interpreter is a forward dataflow analysis that computes the abstract values for each SSA value in the IR. The abstract values are computed by evaluating the statements in the IR using the abstract lattice operations.

The abstract interpreter is implemented as a worklist algorithm. The worklist contains the successors of the current block to be processed. The abstract interpreter processes each successor by evaluating the statements in the block and updating the abstract values in the frame.

The abstract interpreter provides hooks for customizing the behavior of the interpreter. The [prehook_succ][kirin.interp.abstract.AbstractInterpreter.prehook_succ] and [posthook_succ][kirin.interp.abstract.AbstractInterpreter.posthook_succ] methods can be used to perform custom actions before and after processing a successor.

lattice class-attribute instance-attribute 

lattice: type[BoundedLattice[ResultType]] = field(
    init=False
)

lattice type for the abstract interpreter.

expect_const classmethod 

expect_const(value: SSAValue, type_: type[T])

Expect a constant value of a given type.

If the value is not a constant or the constant is not of the given type, raise an InterpreterError.

Source code in src/kirin/interp/abstract.py 
173
174
175
176
177
178
179
180
181
182
183
@classmethod
def expect_const(cls, value: ir.SSAValue, type_: type[T]):
    """Expect a constant value of a given type.

    If the value is not a constant or the constant is not of the given type, raise
    an `InterpreterError`.
    """
    hint = cls.maybe_const(value, type_)
    if hint is None:
        raise InterpreterError(f"expected {type_}, got {hint}")
    return hint

maybe_const classmethod 

maybe_const(value: SSAValue, type_: type[T]) -> T | None

Get a constant value of a given type.

If the value is not a constant or the constant is not of the given type, return None.

Source code in src/kirin/interp/abstract.py 
160
161
162
163
164
165
166
167
168
169
170
171
@classmethod
def maybe_const(cls, value: ir.SSAValue, type_: type[T]) -> T | None:
    """Get a constant value of a given type.

    If the value is not a constant or the constant is not of the given type, return
    `None`.
    """
    from kirin.analysis.const.lattice import Value

    hint = value.hints.get("const")
    if isinstance(hint, Value) and isinstance(hint.data, type_):
        return hint.data

recursion_limit_reached 

recursion_limit_reached() -> ResultType

Handle the recursion limit reached.

This method is called when the maximum depth of the interpreter stack when calling a callable node is reached. By default a StackOverflowError is raised. Overload this method to provide a custom behavior, e.g. in the case of abstract interpreter, the recursion limit returns a bottom value.

Source code in src/kirin/interp/abstract.py 
106
107
def recursion_limit_reached(self) -> ResultType:
    return self.lattice.bottom()