Skip to content

perf: use worklist algorithm for reaching definitions #164

@omsherikar

Description

@omsherikar

Summary

compute_reaching_definitions iterates all nodes until fixed point, even when only a subset changes between iterations. This can cause unnecessary passes on large graphs.

Suggested direction

  • Switch to predecessor/successor-driven worklist: initialize with all nodes, then enqueue successors only when OUT set changes.
  • Preserve current transfer functions (GEN/KILL semantics) and returned structure.

Acceptance

  • Same results as current implementation on existing fixtures.
  • Fewer transfer evaluations on sparse-change CFGs.
  • Add benchmark or instrumentation test demonstrating reduced iterations.

Code

  • refactron/analysis/data_flow.pycompute_reaching_definitions

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions