angr.analyses.decompiler.pattern_match.dedup

PatternDeduplicator: outline discovered patterns and merge the sound ones.

Extraction happens in two steps.

Outlining lifts every selected region into its own function via Outliner. This always applies and is what removes the duplicated bulk from the parent.

Merging then folds several outlined callees into a single shared function. This is only sound when the callees are identical modulo constants, so each group is re-verified at unlimited canonicalization depth (the shapes used for discovery are depth-limited and would not prove it), the argument lists are put into a canonical order, and the constants that actually differ are lifted into extra parameters passed by each call site. Anything that fails a check is left outlined but unmerged and reported, never merged approximately.

granularity selects what gets outlined:

"occurrence"

Each fuzzy occurrence becomes its own function. Maximum bulk removal from the parent; merging usually finds nothing, because near-duplicates that align at 90% are not identical.

"core"

Only the exactly-shared cores are outlined. Every member of a core group is identical modulo constants by construction, so these always merge.

class angr.analyses.decompiler.pattern_match.dedup.OutlinedRegion

Bases: object

One region that was successfully lifted into its own function.

group_key: tuple
interval: Interval
src_loc: tuple[int, int]
call_loc: tuple[int, int]
child_func: Function
child_graph: networkx.DiGraph[Block]
child_args: list[VirtualVariable]
consts: list[int]
const_bits: list[int]
jump_target_consts: set[int]

indices into consts that are block addresses, meaningless across copies

call_target_consts: set[int]

indices into consts that name a callee, which copies must agree on

shape: tuple[str, ...] = ()
auto_frontier: bool = False
property statements: int

Statements actually moved into the callee.

With a derived frontier this is not the interval length: the Outliner picks its own boundary, so the region it lifts can be smaller (or larger) than the interval that pointed at it.

__init__(group_key, interval, src_loc, call_loc, child_func, child_graph, child_args, consts=<factory>, const_bits=<factory>, jump_target_consts=<factory>, call_target_consts=<factory>, shape=(), auto_frontier=False)
Parameters:
Return type:

None

class angr.analyses.decompiler.pattern_match.dedup.MergeGroup

Bases: object

Several outlined regions folded into one shared function.

name: str
members: list[OutlinedRegion]
lifted_const_indices: list[int]
property size: int
__init__(name, members, lifted_const_indices=<factory>)
Parameters:
Return type:

None

class angr.analyses.decompiler.pattern_match.dedup.DedupResult

Bases: object

What PatternDeduplicator did.

graph: networkx.DiGraph[Block]
outlined: list[OutlinedRegion]
groups: list[MergeGroup]
skipped: list[tuple[Interval, str]]
property statements_removed: int

Statements actually moved out of the parent.

__init__(graph, outlined=<factory>, groups=<factory>, skipped=<factory>)
Parameters:
Return type:

None

angr.analyses.decompiler.pattern_match.dedup.graph_problems(graph, func_addr=None)

Structural invariants the decompiler relies on, checked after an outline.

Three things go wrong in practice, and all three surface far downstream as an unrelated crash, so they are caught here instead:

  • A phi keeps sourcing a block that is gone. The Outliner keeps the source block’s phis in the caller, moves every block the region reaches into the callee, and rewrites frontier phis to the call or dispatcher block; materialize splits a head’s phis off so a loop back to it exits the region. What is left is a frontier phi reached through several new predecessors at once, which _update_phi_stmts leaves alone.

  • Two blocks end up sharing (addr, idx). GraphDephicationVVarMapping keys blocks by that pair in a plain dict, so one silently shadows the other and statement-index lookups land in the wrong block.

  • A vvar gains a second definition. Definition locations are keyed by varid in a plain dict too, so the second write wins and the recorded index then points at an unrelated statement.

Outlines that introduce any of these are rolled back rather than handed on.

Return type:

list[str]

Parameters:

  • graph (networkx.DiGraph[Block])

  • func_addr (int | None)

angr.analyses.decompiler.pattern_match.dedup.normalize_call_width(graph, call_loc)

Rebuild a synthesized call at the width of the variable it is assigned to.

The Outliner mints the callsite at return-register width, then overwrites the destination with the region’s live-out variable, which is often narrower. Variable recovery later evaluates the assignment and dies on the width mismatch (“args’ length must all be equal”), so fix it at the source.

Return type:

bool

Parameters:

  • graph (networkx.DiGraph[Block])

  • call_loc (Address)

angr.analyses.decompiler.pattern_match.dedup.callee_shape(graph)

Full-depth canonical shape of a callee body, for merge verification.

Discovery uses depth-limited shapes, which cannot prove two bodies equal: anything below the depth cut renders as ?. Merging re-derives the shape with no depth limit so equality really means identical modulo constants.

Return type:

tuple[str, ...]

Parameters:

graph (networkx.DiGraph[Block])

angr.analyses.decompiler.pattern_match.dedup.callee_consts(graph)

Const values and widths of a callee body, ordered as in callee_shape(), with the indices that are jump targets and those that are call targets.

Return type:

tuple[list[int], list[int], set[int], set[int]]

Parameters:

graph (networkx.DiGraph[Block])

angr.analyses.decompiler.pattern_match.dedup.canonical_arg_order(graph, args)

Order args by first use in the callee body.

The Outliner derives its interface from a dict of definitions, so two structurally identical callees can end up with their parameters in different orders. Sorting by first use makes the k-th parameter mean the same thing in every member of a merge group.

Return type:

list[VirtualVariable]

Parameters:
class angr.analyses.decompiler.pattern_match.dedup.PatternDeduplicator

Bases: Analysis

Outline fuzzy patterns out of a function and merge the provably equal ones.

Parameters:

  • func (Function) – The function being rewritten.

  • ail_graph (networkx.DiGraph[Block]) – Its AIL graph. Not mutated; a copy is rewritten.

  • patterns (list[FuzzyPattern]) – Patterns from FuzzyPatternFinder.

  • granularity (str) – "core" (default, always mergeable) or "occurrence" (maximum bulk removal).

  • merge (bool) – Fold provably identical callees into one function.

  • frontier_mode (str) – "region" outlines exactly the discovered interval; "fallback" (default) additionally retries regions that are not single-entry by letting the Outliner derive its own frontier.

  • max_auto_blocks (int) – Bound, as a multiple of the region’s block count, on how large a derived frontier may grow.

  • min_auto_ratio (float) – Smallest fraction of the region a derived frontier may cover before the outline is judged unrelated to the pattern and rolled back.

  • name_prefix (str) – Prefix for synthesized function names.

__init__(func, ail_graph, patterns, stream, *, granularity='core', merge=True, name_prefix='fuzzy', vvar_id_start=53248, block_addr_start=2882338816, const_param_stack_base=-65536, min_group_size=2, validate=True, frontier_mode='fallback', max_auto_blocks=3, min_auto_ratio=0.5)
Parameters:
summary()
Return type:

str