Prop

Bases: ForwardFrame[Result]

              flowchart TD
              kirin.analysis.const.prop.Frame[Frame]
              kirin.analysis.forward.ForwardFrame[ForwardFrame]
              kirin.interp.abstract.AbstractFrame[AbstractFrame]
              kirin.interp.frame.Frame[Frame]
              kirin.interp.frame.FrameABC[FrameABC]

                              kirin.analysis.forward.ForwardFrame --> kirin.analysis.const.prop.Frame
                                kirin.interp.abstract.AbstractFrame --> kirin.analysis.forward.ForwardFrame
                                kirin.interp.frame.Frame --> kirin.interp.abstract.AbstractFrame
                                kirin.interp.frame.FrameABC --> kirin.interp.frame.Frame
                





              click kirin.analysis.const.prop.Frame href "" "kirin.analysis.const.prop.Frame"
              click kirin.analysis.forward.ForwardFrame href "" "kirin.analysis.forward.ForwardFrame"
              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"
            

frame_is_not_pure: bool = False

should_be_pure: set[Statement] = field(default_factory=set)

Bases: ForwardExtra[Frame, Result]

              flowchart TD
              kirin.analysis.const.prop.Propagate[Propagate]
              kirin.analysis.forward.ForwardExtra[ForwardExtra]
              kirin.interp.abstract.AbstractInterpreter[AbstractInterpreter]
              kirin.interp.abc.InterpreterABC[InterpreterABC]

                              kirin.analysis.forward.ForwardExtra --> kirin.analysis.const.prop.Propagate
                                kirin.interp.abstract.AbstractInterpreter --> kirin.analysis.forward.ForwardExtra
                                kirin.interp.abc.InterpreterABC --> kirin.interp.abstract.AbstractInterpreter
                




              click kirin.analysis.const.prop.Propagate href "" "kirin.analysis.const.prop.Propagate"
              click kirin.analysis.forward.ForwardExtra href "" "kirin.analysis.forward.ForwardExtra"
              click kirin.interp.abstract.AbstractInterpreter href "" "kirin.interp.abstract.AbstractInterpreter"
              click kirin.interp.abc.InterpreterABC href "" "kirin.interp.abc.InterpreterABC"
            

Forward dataflow analysis for constant propagation.

This analysis is a forward dataflow analysis that propagates constant values through the program. It uses the Result lattice to track the constant values and purity of the values.

The analysis is implemented as a forward dataflow analysis, where the eval_stmt method is overridden to handle the different types of statements in the IR. The analysis uses the interp.Interpreter to evaluate the statements and propagate the constant values.

When a statement is registered under the "constprop" key in the method table, the analysis will call the method to evaluate the statement instead of using the interpreter. This allows for custom handling of statements.

With cache_calls set, within one run, a call with the same callee and the same argument facts as a call already analyzed reuses that call's result and frame instead of analyzing the callee again. A run starts whenever a frame is created without a caller; the IR may change between runs, so nothing is reused across them. Calls cut off at the depth limit, and calls whose frame holds a closure, are analyzed every time.

cache_calls: bool = field(default=False, kw_only=True)

keys = ('constprop',)

lattice = Result

call(
    node: Statement | Method,
    *args: Result,
    **kwargs: Result
) -> tuple[Frame, Result]

108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

def call(
    self, node: ir.Statement | ir.Method, *args: Result, **kwargs: Result
) -> tuple[Frame, Result]:
    # `ForwardExtra.call(self, ...)` rather than `super().call(...)`: CPython
    # gives a starred call to a bound method its own C frame, which would
    # lower the recursion depth that analyses survive.
    if not self.cache_calls or isinstance(node, ir.Method) or not self.state.depth:
        # A `Method` comes back as its code once its run is set up, and a
        # call without a caller is a whole run, whose frame its caller reads.
        return ForwardExtra.call(self, node, *args, **kwargs)

    key = (
        node,
        tuple(map(_fact_id, args)),
        tuple((name, _fact_id(value)) for name, value in kwargs.items()),
    )
    if (summary := self._call_summaries.get(key)) is not None:
        return summary.frame(node), summary.result

    cutoffs = self._cutoffs
    frame, result = ForwardExtra.call(self, node, *args, **kwargs)
    # Skip caching if the call hit the recursion limit (its result depends on
    # the call stack) or yields a closure (closures are told apart by
    # identity, so each call site needs its own).
    if self._cutoffs == cutoffs and not _holds_closure(
        (result, *frame.entries.values())
    ):
        self._call_summaries[key] = _CallSummary(
            (*args, *kwargs.values()),
            result,
            tuple(frame.entries.items()),
            frozenset(frame.should_be_pure),
            frame.frame_is_not_pure,
        )
    return frame, result

frame_eval(
    frame: Frame, node: Statement
) -> interp.StatementResult[Result]

160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

def frame_eval(
    self, frame: Frame, node: ir.Statement
) -> interp.StatementResult[Result]:
    method = self.lookup_registry(frame, node)
    if method is None:
        if node.has_trait(ir.ConstantLike):
            return self.try_eval_const_pure(frame, node, ())
        elif node.has_trait(ir.Pure):
            values = frame.get_values(node.args)
            if types.is_tuple_of(values, Value):
                return self.try_eval_const_pure(frame, node, values)

        if not node.has_trait(ir.Pure):
            # not pure, and no implementation, let's say it's not pure
            frame.frame_is_not_pure = True
        return tuple(Unknown() for _ in node._results)

    ret = method(self, frame, node)
    if node.has_trait(ir.IsTerminator) or node.has_trait(ir.Pure):
        return ret
    elif not node.has_trait(ir.MaybePure):  # cannot be pure at all
        frame.frame_is_not_pure = True
    elif (
        node not in frame.should_be_pure
    ):  # implementation cannot decide if it's pure
        frame.frame_is_not_pure = True
    return ret

initialize_frame(
    node: Statement, *, has_parent_access: bool = False
) -> Frame

148
149
150
151
152
153
154
155

def initialize_frame(
    self, node: ir.Statement, *, has_parent_access: bool = False
) -> Frame:
    state = getattr(self, "state", None)  # unset before `initialize`
    if state is None or not state.depth:
        # A frame without a caller starts a new run.
        self._call_summaries.clear()
    return Frame(node, has_parent_access=has_parent_access)

method_self(method: Method) -> Result

157
158

def method_self(self, method: ir.Method) -> Result:
    return Value(method)

recursion_limit_reached() -> Result

144
145
146

def recursion_limit_reached(self) -> Result:
    self._cutoffs += 1
    return super().recursion_limit_reached()