Skip to content

Commit

Permalink
analyses.domination: add PostDominatorTree.
Browse files Browse the repository at this point in the history
whitequark committed Nov 1, 2015
1 parent f70f7fb commit 3a1b77a
Showing 1 changed file with 27 additions and 0 deletions.
27 changes: 27 additions & 0 deletions artiq/compiler/analyses/domination.py
Original file line number Diff line number Diff line change
@@ -37,3 +37,30 @@ def __init__(self, func):

if not changed:
break

class PostDominatorTree:
def __init__(self, func):
exits = [block for block in func.basic_blocks if none(block.successors())]

self.dominated_by = { exit: {exit} for exit in exits }
for block in func.basic_blocks:
if block != entry:
self.dominated_by[block] = set(func.basic_blocks)

successors = {block: block.successors() for block in func.basic_blocks}
while True:
changed = False

for block in func.basic_blocks:
if block in exits:
continue

new_dominated_by = {block}.union(
reduce(lambda a, b: a.intersection(b),
(self.dominated_by[pred] for pred in successors[block])))
if new_dominated_by != self.dominated_by[block]:
self.dominated_by[block] = new_dominated_by
changed = True

if not changed:
break

0 comments on commit 3a1b77a

Please sign in to comment.