Skip to content

refactor[venom]: add dom walk property #4546

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
charles-cooper merged 4 commits into from
Mar 30, 2025
Merged

refactor[venom]: add dom walk property #4546

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
01d1d79
proper dom post order compute
harkal Mar 28, 2025
545686e
convert to iteratable property
harkal Mar 28, 2025
a1def95
refactor
harkal Mar 28, 2025
6c2b89d
Merge branch 'master' into fix/venom/dom_walk
harkal Mar 30, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
41 changes: 26 additions & 15 deletions vyper/venom/analysis/dominators.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
from functools import cached_property
from typing import Iterator

from vyper.exceptions import CompilerPanic
from vyper.utils import OrderedSet
Expand Down Expand Up @@ -33,6 +33,8 @@
self.dominator_frontiers = {}

self.cfg = self.analyses_cache.request_analysis(CFGAnalysis)
self.cfg_post_walk = list(self.cfg.dfs_post_walk)
self.cfg_post_order = {bb: idx for idx, bb in enumerate(self.cfg_post_walk)}

self._compute_dominators()
self._compute_idoms()
Expand All @@ -54,7 +56,7 @@
"""
Compute dominators
"""
basic_blocks = list(self.dfs_post_order.keys())
basic_blocks = self.cfg_post_walk
self.dominators = {bb: OrderedSet(basic_blocks) for bb in basic_blocks}
self.dominators[self.entry_block] = OrderedSet([self.entry_block])
changed = True
Expand All @@ -80,26 +82,26 @@
"""
Compute immediate dominators
"""
self.immediate_dominators = {bb: None for bb in self.dfs_post_order.keys()}
self.immediate_dominators = {bb: None for bb in self.cfg_post_walk}
self.immediate_dominators[self.entry_block] = self.entry_block
for bb in self.dfs_post_walk:
for bb in self.cfg_post_walk:
if bb == self.entry_block:
continue
doms = sorted(self.dominators[bb], key=lambda x: self.dfs_post_order[x])
doms = sorted(self.dominators[bb], key=lambda x: self.cfg_post_order[x])
self.immediate_dominators[bb] = doms[1]

self.dominated = {bb: OrderedSet() for bb in self.dfs_post_walk}
self.dominated = {bb: OrderedSet() for bb in self.cfg_post_walk}
for dom, target in self.immediate_dominators.items():
self.dominated[target].add(dom)

def _compute_df(self):
"""
Compute dominance frontier
"""
basic_blocks = self.dfs_post_walk
basic_blocks = self.cfg_post_walk
self.dominator_frontiers = {bb: OrderedSet() for bb in basic_blocks}

for bb in self.dfs_post_walk:
for bb in self.cfg_post_walk:
if len(bb.cfg_in) > 1:
for pred in bb.cfg_in:
runner = pred
Expand All @@ -120,21 +122,30 @@
"""
Find the nearest common dominator of two basic blocks.
"""
dfs_order = self.dfs_order
dfs_order = self.cfg_post_order

Check warning on line 125 in vyper/venom/analysis/dominators.py

View check run for this annotation

Codecov / codecov/patch

vyper/venom/analysis/dominators.py#L125 

Added line #L125 was not covered by tests
while bb1 != bb2:
while dfs_order[bb1] < dfs_order[bb2]:
bb1 = self.immediate_dominators[bb1]
while dfs_order[bb1] > dfs_order[bb2]:
bb2 = self.immediate_dominators[bb2]
return bb1

@cached_property
def dfs_post_walk(self) -> list[IRBasicBlock]:
return list(self.cfg.dfs_post_walk)
@property
def dom_post_order(self) -> Iterator[IRBasicBlock]:
"""
Compute post-order traversal of the dominator tree.
"""
visited = set()

def visit(bb: IRBasicBlock) -> Iterator[IRBasicBlock]:
if bb in visited:
return
visited.add(bb)
for dominated_bb in self.dominated.get(bb, OrderedSet()):
yield from visit(dominated_bb)
yield bb

@cached_property
def dfs_post_order(self) -> dict[IRBasicBlock, int]:
return {bb: idx for idx, bb in enumerate(self.dfs_post_walk)}
return visit(self.entry_block)

def as_graph(self) -> str:
"""
Expand Down
6 changes: 3 additions & 3 deletions vyper/venom/passes/make_ssa.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -35,8 +35,8 @@ def _add_phi_nodes(self):
Add phi nodes to the function.
"""
self._compute_defs()
work = {bb: 0 for bb in self.dom.dfs_post_walk}
has_already = {bb: 0 for bb in self.dom.dfs_post_walk}
work = {bb: 0 for bb in self.dom.dom_post_order}
has_already = {bb: 0 for bb in self.dom.dom_post_order}
i = 0

# Iterate over all variables
Expand Down Expand Up @@ -152,7 +152,7 @@ def _compute_defs(self):
Compute the definition points of variables in the function.
"""
self.defs = {}
for bb in self.dom.dfs_post_walk:
for bb in self.dom.dom_post_order:
assignments = bb.get_assignments()
for var in assignments:
if var not in self.defs:
Expand Down