blob: e9f9ea8ec2ed8d73fbbb04589fe7668d6d68c551 [file]
"""Data-flow analyses."""
from __future__ import annotations
from abc import abstractmethod
from collections.abc import Collection, Iterable, Iterator, Set as AbstractSet
from typing import Any, Generic, TypeVar
from mypyc.ir.ops import (
ERR_NEVER,
Assign,
AssignMulti,
BasicBlock,
Box,
Branch,
Call,
CallC,
Cast,
ComparisonOp,
ControlOp,
DecRef,
Extend,
Float,
FloatComparisonOp,
FloatNeg,
FloatOp,
GetAttr,
GetElement,
GetElementPtr,
Goto,
IncRef,
InitStatic,
Integer,
IntOp,
KeepAlive,
LoadAddress,
LoadErrorValue,
LoadGlobal,
LoadLiteral,
LoadMem,
LoadStatic,
MethodCall,
Op,
OpVisitor,
PrimitiveOp,
RaiseStandardError,
Register,
RegisterOp,
Return,
SetAttr,
SetElement,
SetMem,
Truncate,
TupleGet,
TupleSet,
Unborrow,
Unbox,
Undef,
Unreachable,
Value,
)
class CFG:
"""Control-flow graph.
Node 0 is always assumed to be the entry point. There must be a
non-empty set of exits.
"""
def __init__(
self,
succ: dict[BasicBlock, list[BasicBlock]],
pred: dict[BasicBlock, list[BasicBlock]],
exits: set[BasicBlock],
) -> None:
assert exits
self.succ = succ
self.pred = pred
self.exits = exits
def __str__(self) -> str:
exits = sorted(self.exits, key=lambda e: int(e.label))
return f"exits: {exits}\nsucc: {self.succ}\npred: {self.pred}"
def get_cfg(blocks: list[BasicBlock], *, use_yields: bool = False) -> CFG:
"""Calculate basic block control-flow graph.
If use_yields is set, then we treat returns inserted by yields as gotos
instead of exits.
"""
succ_map = {}
pred_map: dict[BasicBlock, list[BasicBlock]] = {}
exits = set()
for block in blocks:
assert not any(
isinstance(op, ControlOp) for op in block.ops[:-1]
), "Control-flow ops must be at the end of blocks"
if use_yields and isinstance(block.terminator, Return) and block.terminator.yield_target:
succ = [block.terminator.yield_target]
else:
succ = list(block.terminator.targets())
if not succ:
exits.add(block)
# Errors can occur anywhere inside a block, which means that
# we can't assume that the entire block has executed before
# jumping to the error handler. In our CFG construction, we
# model this as saying that a block can jump to its error
# handler or the error handlers of any of its normal
# successors (to represent an error before that next block
# completes). This works well for analyses like "must
# defined", where it implies that registers assigned in a
# block may be undefined in its error handler, but is in
# general not a precise representation of reality; any
# analyses that require more fidelity must wait until after
# exception insertion.
for error_point in [block] + succ:
if error_point.error_handler:
succ.append(error_point.error_handler)
succ_map[block] = succ
pred_map[block] = []
for prev, nxt in succ_map.items():
for label in nxt:
pred_map[label].append(prev)
return CFG(succ_map, pred_map, exits)
def get_real_target(label: BasicBlock) -> BasicBlock:
if len(label.ops) == 1 and isinstance(label.ops[-1], Goto):
label = label.ops[-1].label
return label
def cleanup_cfg(blocks: list[BasicBlock]) -> None:
"""Cleanup the control flow graph.
This eliminates obviously dead basic blocks and eliminates blocks that contain
nothing but a single jump.
There is a lot more that could be done.
"""
changed = True
while changed:
# First collapse any jumps to basic block that only contain a goto
for block in blocks:
for i, tgt in enumerate(block.terminator.targets()):
block.terminator.set_target(i, get_real_target(tgt))
# Then delete any blocks that have no predecessors
changed = False
cfg = get_cfg(blocks)
orig_blocks = blocks.copy()
blocks.clear()
for i, block in enumerate(orig_blocks):
if i == 0 or cfg.pred[block]:
blocks.append(block)
else:
changed = True
T = TypeVar("T")
S = TypeVar("S")
class BitIndex(Generic[T]):
"""Assign bit positions to values, for use with BitSet."""
def __init__(self) -> None:
self.positions: dict[T, int] = {}
self.values: list[T] = []
def mask(self, values: Collection[T]) -> int:
"""Return a bit mask for values, assigning positions to new values."""
positions = self.positions
if len(values) > 8:
for value in values:
if value not in positions:
positions[value] = len(self.values)
self.values.append(value)
return self.known_mask(values)
# Gen and kill sets usually have only one or two items.
result = 0
for value in values:
pos = positions.get(value)
if pos is None:
pos = len(self.values)
positions[value] = pos
self.values.append(value)
result |= 1 << pos
return result
def known_mask(self, values: Iterable[object]) -> int:
"""Return a bit mask for those values that have a position (others are ignored)."""
positions: dict[Any, int] = self.positions
found = [pos for pos in map(positions.get, values) if pos is not None]
if len(found) <= 8:
result = 0
for pos in found:
result |= 1 << pos
return result
buf = bytearray((len(self.values) + 7) // 8)
for pos in found:
buf[pos >> 3] |= 1 << (pos & 7)
return int.from_bytes(buf, "little")
class BitSet(AbstractSet[T]):
"""Immutable set of values represented as a bit mask.
Bit i is set if index.values[i] is in the set. All the sets produced by a
single analysis share the same index, so set operations between them are
cheap integer operations. This uses much less memory than a set object:
one bit per value that the analysis knows about instead of a hash table
entry per element.
"""
def __init__(self, bits: int, index: BitIndex[T]) -> None:
self.bits = bits
self.index = index
def __contains__(self, value: object) -> bool:
positions: dict[Any, int] = self.index.positions
pos = positions.get(value)
return pos is not None and (self.bits >> pos) & 1 == 1
def positions(self) -> list[int]:
"""Return the positions of the set bits (in increasing order)."""
# Least significant bit first, so that index i is position i.
digits = bin(self.bits)[:1:-1]
result = []
pos = digits.find("1")
while pos >= 0:
result.append(pos)
pos = digits.find("1", pos + 1)
return result
def __iter__(self) -> Iterator[T]:
values = self.index.values
return iter([values[pos] for pos in self.positions()])
def __len__(self) -> int:
return self.bits.bit_count()
def __bool__(self) -> bool:
return self.bits != 0
def _mask_of(self, other: AbstractSet[Any]) -> int:
"""Return a mask of the values in both self and other."""
if isinstance(other, BitSet) and other.index is self.index:
return self.bits & other.bits
if len(self) <= len(other):
# Like set operations, iterate over the smaller operand.
values = self.index.values
return self.index.known_mask(
[values[pos] for pos in self.positions() if values[pos] in other]
)
return self.bits & self.index.known_mask(other)
def __sub__(self, other: AbstractSet[Any]) -> AbstractSet[T]:
return BitSet(self.bits & ~self._mask_of(other), self.index)
def __and__(self, other: AbstractSet[Any]) -> AbstractSet[T]:
return BitSet(self._mask_of(other), self.index)
def __or__(self, other: AbstractSet[S]) -> AbstractSet[T | S]:
if isinstance(other, BitSet) and other.index is self.index:
return BitSet(self.bits | other.bits, self.index)
result: set[T | S] = set(self)
result.update(other)
return result
# The reflected operations are used when the left operand is a set. They must
# return a set, since that's the type that the operation has with a set on the
# left according to typeshed, and compiled code checks this.
def __rand__(self, other: AbstractSet[S]) -> AbstractSet[S]:
return {value for value in other if value in self}
def __ror__(self, other: AbstractSet[S]) -> AbstractSet[T | S]:
result: set[T | S] = set(other)
result.update(self)
return result
def __rsub__(self, other: AbstractSet[S]) -> AbstractSet[S]:
return {value for value in other if value not in self}
def __repr__(self) -> str:
return repr(set(self))
AnalysisDict = dict[tuple[BasicBlock, int], AbstractSet[T]]
class AnalysisResult(Generic[T]):
def __init__(self, before: AnalysisDict[T], after: AnalysisDict[T]) -> None:
self.before = before
self.after = after
def __str__(self) -> str:
return f"before: {self.before}\nafter: {self.after}\n"
GenAndKill = tuple[AbstractSet[T], AbstractSet[T]]
_EMPTY: tuple[frozenset[Any], frozenset[Any]] = (frozenset(), frozenset())
class BaseAnalysisVisitor(OpVisitor[GenAndKill[T]]):
def visit_goto(self, op: Goto) -> GenAndKill[T]:
return _EMPTY
@abstractmethod
def visit_register_op(self, op: RegisterOp) -> GenAndKill[T]:
raise NotImplementedError
@abstractmethod
def visit_assign(self, op: Assign) -> GenAndKill[T]:
raise NotImplementedError
@abstractmethod
def visit_assign_multi(self, op: AssignMulti) -> GenAndKill[T]:
raise NotImplementedError
@abstractmethod
def visit_set_mem(self, op: SetMem) -> GenAndKill[T]:
raise NotImplementedError
def visit_inc_ref(self, op: IncRef) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_dec_ref(self, op: DecRef) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_call(self, op: Call) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_method_call(self, op: MethodCall) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_load_error_value(self, op: LoadErrorValue) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_load_literal(self, op: LoadLiteral) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_get_attr(self, op: GetAttr) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_set_attr(self, op: SetAttr) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_load_static(self, op: LoadStatic) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_init_static(self, op: InitStatic) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_tuple_get(self, op: TupleGet) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_tuple_set(self, op: TupleSet) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_box(self, op: Box) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_unbox(self, op: Unbox) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_cast(self, op: Cast) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_raise_standard_error(self, op: RaiseStandardError) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_call_c(self, op: CallC) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_primitive_op(self, op: PrimitiveOp) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_truncate(self, op: Truncate) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_extend(self, op: Extend) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_load_global(self, op: LoadGlobal) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_int_op(self, op: IntOp) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_float_op(self, op: FloatOp) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_float_neg(self, op: FloatNeg) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_comparison_op(self, op: ComparisonOp) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_float_comparison_op(self, op: FloatComparisonOp) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_load_mem(self, op: LoadMem) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_get_element(self, op: GetElement) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_get_element_ptr(self, op: GetElementPtr) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_set_element(self, op: SetElement) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_load_address(self, op: LoadAddress) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_keep_alive(self, op: KeepAlive) -> GenAndKill[T]:
return self.visit_register_op(op)
def visit_unborrow(self, op: Unborrow) -> GenAndKill[T]:
return self.visit_register_op(op)
class DefinedVisitor(BaseAnalysisVisitor[Value]):
"""Visitor for finding defined registers.
Note that this only deals with registers and not temporaries, on
the assumption that we never access temporaries when they might be
undefined.
If strict_errors is True, then we regard any use of LoadErrorValue
as making a register undefined. Otherwise we only do if
`undefines` is set on the error value.
This lets us only consider the things we care about during
uninitialized variable checking while capturing all possibly
undefined things for refcounting.
"""
def __init__(self, strict_errors: bool = False) -> None:
self.strict_errors = strict_errors
def visit_branch(self, op: Branch) -> GenAndKill[Value]:
return _EMPTY
def visit_return(self, op: Return) -> GenAndKill[Value]:
return _EMPTY
def visit_unreachable(self, op: Unreachable) -> GenAndKill[Value]:
return _EMPTY
def visit_register_op(self, op: RegisterOp) -> GenAndKill[Value]:
return _EMPTY
def visit_assign(self, op: Assign) -> GenAndKill[Value]:
# Loading an error value may undefine the register.
if isinstance(op.src, LoadErrorValue) and (op.src.undefines or self.strict_errors):
return set(), {op.dest}
else:
return {op.dest}, set()
def visit_assign_multi(self, op: AssignMulti) -> GenAndKill[Value]:
# Array registers are special and we don't track the definedness of them.
return _EMPTY
def visit_set_mem(self, op: SetMem) -> GenAndKill[Value]:
return _EMPTY
def analyze_maybe_defined_regs(
blocks: list[BasicBlock], cfg: CFG, initial_defined: set[Value]
) -> AnalysisResult[Value]:
"""Calculate potentially defined registers at each CFG location.
A register is defined if it has a value along some path from the initial location.
"""
return run_analysis(
blocks=blocks,
cfg=cfg,
gen_and_kill=DefinedVisitor(),
initial=initial_defined,
backward=False,
kind=MAYBE_ANALYSIS,
)
def analyze_must_defined_regs(
blocks: list[BasicBlock],
cfg: CFG,
initial_defined: set[Value],
regs: Iterable[Value],
strict_errors: bool = False,
index: BitIndex[Value] | None = None,
) -> AnalysisResult[Value]:
"""Calculate always defined registers at each CFG location.
This analysis can work before exception insertion, since it is a
sound assumption that registers defined in a block might not be
initialized in its error handler.
A register is defined if it has a value along all paths from the
initial location.
"""
return run_analysis(
blocks=blocks,
cfg=cfg,
index=index,
gen_and_kill=DefinedVisitor(strict_errors=strict_errors),
initial=initial_defined,
backward=False,
kind=MUST_ANALYSIS,
# Only registers can be undefined (temporaries are always defined before use),
# so leave everything else out of the universe to keep the sets small.
universe={r for r in regs if isinstance(r, Register)},
)
class BorrowedArgumentsVisitor(BaseAnalysisVisitor[Value]):
def __init__(self, args: set[Value]) -> None:
self.args = args
def visit_branch(self, op: Branch) -> GenAndKill[Value]:
return _EMPTY
def visit_return(self, op: Return) -> GenAndKill[Value]:
return _EMPTY
def visit_unreachable(self, op: Unreachable) -> GenAndKill[Value]:
return _EMPTY
def visit_register_op(self, op: RegisterOp) -> GenAndKill[Value]:
return _EMPTY
def visit_assign(self, op: Assign) -> GenAndKill[Value]:
if op.dest in self.args:
return set(), {op.dest}
return _EMPTY
def visit_assign_multi(self, op: AssignMulti) -> GenAndKill[Value]:
return _EMPTY
def visit_set_mem(self, op: SetMem) -> GenAndKill[Value]:
return _EMPTY
def analyze_borrowed_arguments(
blocks: list[BasicBlock], cfg: CFG, borrowed: set[Value], index: BitIndex[Value] | None = None
) -> AnalysisResult[Value]:
"""Calculate arguments that can use references borrowed from the caller.
When assigning to an argument, it no longer is borrowed.
"""
return run_analysis(
blocks=blocks,
cfg=cfg,
gen_and_kill=BorrowedArgumentsVisitor(borrowed),
initial=borrowed,
backward=False,
kind=MUST_ANALYSIS,
universe=borrowed,
index=index,
)
class UndefinedVisitor(BaseAnalysisVisitor[Value]):
def visit_branch(self, op: Branch) -> GenAndKill[Value]:
return _EMPTY
def visit_return(self, op: Return) -> GenAndKill[Value]:
return _EMPTY
def visit_unreachable(self, op: Unreachable) -> GenAndKill[Value]:
return _EMPTY
def visit_register_op(self, op: RegisterOp) -> GenAndKill[Value]:
return set(), {op} if not op.is_void else set()
def visit_assign(self, op: Assign) -> GenAndKill[Value]:
return set(), {op.dest}
def visit_assign_multi(self, op: AssignMulti) -> GenAndKill[Value]:
return set(), {op.dest}
def visit_set_mem(self, op: SetMem) -> GenAndKill[Value]:
return _EMPTY
def non_trivial_sources(op: Op) -> set[Value]:
result = set()
for source in op.sources():
if not isinstance(source, (Integer, Float, Undef)):
result.add(source)
return result
class LivenessVisitor(BaseAnalysisVisitor[Value]):
def visit_branch(self, op: Branch) -> GenAndKill[Value]:
return non_trivial_sources(op), set()
def visit_return(self, op: Return) -> GenAndKill[Value]:
if not isinstance(op.value, (Integer, Float)):
return {op.value}, set()
else:
return _EMPTY
def visit_unreachable(self, op: Unreachable) -> GenAndKill[Value]:
return _EMPTY
def visit_register_op(self, op: RegisterOp) -> GenAndKill[Value]:
gen = non_trivial_sources(op)
if not op.is_void:
return gen, {op}
else:
return gen, set()
def visit_assign(self, op: Assign) -> GenAndKill[Value]:
return non_trivial_sources(op), {op.dest}
def visit_assign_multi(self, op: AssignMulti) -> GenAndKill[Value]:
return non_trivial_sources(op), {op.dest}
def visit_set_mem(self, op: SetMem) -> GenAndKill[Value]:
return non_trivial_sources(op), set()
def visit_inc_ref(self, op: IncRef) -> GenAndKill[Value]:
return _EMPTY
def visit_dec_ref(self, op: DecRef) -> GenAndKill[Value]:
return _EMPTY
def analyze_live_regs(
blocks: list[BasicBlock], cfg: CFG, index: BitIndex[Value] | None = None
) -> AnalysisResult[Value]:
"""Calculate live registers at each CFG location.
A register is live at a location if it can be read along some CFG path starting
from the location.
"""
return run_analysis(
blocks=blocks,
cfg=cfg,
gen_and_kill=LivenessVisitor(),
initial=set(),
backward=True,
kind=MAYBE_ANALYSIS,
index=index,
)
def analyze_live_regs_with_exception_edges(
blocks: list[BasicBlock],
) -> dict[BasicBlock, set[Value]]:
"""Calculate block-entry liveness before exception handling is inserted.
Unlike get_cfg(), this models an error edge at each operation that can
raise. This matters when an assignment later in the same block overwrites a
value that the error handler can still read. Returns inserted for a yield
are treated as edges to their continuation blocks.
TODO: Unlike run_analysis(), this supports edges from the middle of basic
blocks, so we reimplement data flow analysis here. Figure out a way
to unify this with run_analysis().
"""
visitor = LivenessVisitor()
live_in: dict[BasicBlock, set[Value]] = {block: set() for block in blocks}
while True:
changed = False
for block in reversed(blocks):
terminator = block.terminator
if isinstance(terminator, Return) and terminator.yield_target is not None:
successors = (terminator.yield_target,)
else:
successors = terminator.targets()
live: set[Value] = set()
for successor in successors:
live.update(live_in[successor])
for op in reversed(block.ops):
if (
block.error_handler is not None
and isinstance(op, RegisterOp)
and op.error_kind != ERR_NEVER
):
live.update(live_in[block.error_handler])
gen, kill = op.accept(visitor)
live.difference_update(kill)
live.update(gen)
if live != live_in[block]:
live_in[block] = live
changed = True
if not changed:
return live_in
# Analysis kinds
MUST_ANALYSIS = 0
MAYBE_ANALYSIS = 1
def run_analysis(
blocks: list[BasicBlock],
cfg: CFG,
gen_and_kill: OpVisitor[GenAndKill[T]],
initial: set[T],
kind: int,
backward: bool,
universe: set[T] | None = None,
index: BitIndex[T] | None = None,
) -> AnalysisResult[T]:
"""Run a general set-based data flow analysis.
Args:
blocks: All basic blocks
cfg: Control-flow graph for the code
gen_and_kill: Implementation of gen and kill functions for each op
initial: Value of analysis for the entry points (for a forward analysis) or the
exit points (for a backward analysis)
kind: MUST_ANALYSIS or MAYBE_ANALYSIS
backward: If False, the analysis is a forward analysis; it's backward otherwise
universe: For a must analysis, the set of all possible values. This is the starting
value for the work list algorithm, which will narrow this down until reaching a
fixed point. For a maybe analysis the iteration always starts from an empty set
and this argument is ignored.
index: Bit positions to use for the result sets (see BitSet). Set operations
between results of analyses that share an index are fast.
Return analysis results: (before, after)
"""
# Sets are represented as bit masks (see BitSet), since a large function can
# have thousands of values and blocks, and we need a set for each of them.
if index is None:
index = BitIndex()
initial_bits = index.mask(initial)
universe_bits = index.mask(universe) if universe is not None else 0
# Calculate gen and kill masks for each op, and for entire basic blocks.
op_gen_and_kill: dict[BasicBlock, list[tuple[int, int]]] = {}
block_gen = {}
block_kill = {}
for block in blocks:
op_masks = []
gen = 0
kill = 0
ops = block.ops
if backward:
ops = list(reversed(ops))
for op in ops:
opgen_set, opkill_set = op.accept(gen_and_kill)
opgen = index.mask(opgen_set) if opgen_set else 0
opkill = index.mask(opkill_set) if opkill_set else 0
op_masks.append((opgen, opkill))
if opkill:
gen &= ~opkill
if opgen:
gen |= opgen
kill &= ~opgen
if opkill:
kill |= opkill
op_gen_and_kill[block] = op_masks
block_gen[block] = gen
block_kill[block] = kill
# Set up initial state for worklist algorithm.
worklist = list(blocks)
if not backward:
worklist.reverse() # Reverse for a small performance improvement
workset = set(worklist)
before: dict[BasicBlock, int] = {}
after: dict[BasicBlock, int] = {}
if kind == MAYBE_ANALYSIS:
start = 0
else:
assert universe is not None, "Universe must be defined for a must analysis"
start = universe_bits
for block in blocks:
before[block] = start
after[block] = start
if backward:
pred_map = cfg.succ
succ_map = cfg.pred
else:
pred_map = cfg.pred
succ_map = cfg.succ
# Run work list algorithm to generate in and out sets for each basic block.
while worklist:
label = worklist.pop()
workset.remove(label)
preds = pred_map[label]
if preds:
new_before = after[preds[0]]
for pred in preds[1:]:
if kind == MAYBE_ANALYSIS:
new_before |= after[pred]
else:
new_before &= after[pred]
else:
new_before = initial_bits
before[label] = new_before
new_after = (new_before & ~block_kill[label]) | block_gen[label]
if new_after != after[label]:
for succ in succ_map[label]:
if succ not in workset:
worklist.append(succ)
workset.add(succ)
after[label] = new_after
# Run algorithm for each basic block to generate opcode-level sets.
op_before: dict[tuple[BasicBlock, int], AbstractSet[T]] = {}
op_after: dict[tuple[BasicBlock, int], AbstractSet[T]] = {}
for block in blocks:
label = block
cur = before[label]
cur_set = BitSet(cur, index)
n = len(block.ops)
for i, (opgen, opkill) in enumerate(op_gen_and_kill[block]):
# The masks are in reverse op order for a backward analysis.
idx = n - 1 - i if backward else i
op_before[label, idx] = cur_set
if opkill or opgen:
cur = (cur & ~opkill) | opgen
cur_set = BitSet(cur, index)
op_after[label, idx] = cur_set
if backward:
op_after, op_before = op_before, op_after
return AnalysisResult(op_before, op_after)