m-labs · Jul 18, 2015 · Jul 18, 2015
Showing with 60 additions and 5 deletions.

+1 −0 artiq/compiler/analyses/__init__.py

+48 −0 artiq/compiler/analyses/domination.py

+11 −5 artiq/compiler/ir.py
diff --git a/artiq/compiler/analyses/__init__.py b/artiq/compiler/analyses/__init__.py
@@ -0,0 +1 @@
+from .domination import DominatorTree
diff --git a/artiq/compiler/analyses/domination.py b/artiq/compiler/analyses/domination.py
@@ -0,0 +1,48 @@
+"""
+:class:`DominatorTree` computes the dominance relation over
+control flow graphs.
+
+See http://www.cs.colostate.edu/~mstrout/CS553/slides/lecture04.pdf.
+"""
+
+from functools import reduce, cmp_to_key
+
+# Key Idea
+#   If a node dominates all
+#   predecessors of node n, then it
+#   also dominates node n
+class DominatorTree:
+    def __init__(self, func):
+        entry = func.get_entry()
+
+        self.dominated_by = { entry: {entry} }
+        for block in func.basic_blocks:
+            if block != entry:
+                self.dominated_by[block] = set(func.basic_blocks)
+
+        predecessors = {block: block.predecessors() for block in func.basic_blocks}
+        while True:
+            changed = False
+
+            for block in func.basic_blocks:
+                if block == entry:
+                    continue
+
+                if not any(predecessors[block]):
+                    # Unreachable blocks are dominated by everything
+                    continue
+
+                new_dominated_by = {block}.union(
+                    reduce(lambda a, b: a.intersection(b),
+                           (self.dominated_by[pred] for pred in predecessors[block])))
+                if new_dominated_by != self.dominated_by[block]:
+                    self.dominated_by[block] = new_dominated_by
+                    changed = True
+
+            if not changed:
+                break
+
+    def in_domination_order(self):
+        blocks = list(self.dominated_by.keys())
+        blocks.sort(key=cmp_to_key(lambda a, b: a in self.dominated_by[b]))
+        return blocks
diff --git a/artiq/compiler/ir.py b/artiq/compiler/ir.py
@@ -303,8 +303,7 @@ def successors(self):
         return self.terminator().successors()
 
     def predecessors(self):
-        assert self.function is not None
-        return self.function.predecessors_of(self)
+        return [use.basic_block for use in self.uses if isinstance(use, Terminator)]
 
     def __str__(self):
         # Header
@@ -336,6 +335,9 @@ def __str__(self):
 
         return "\n".join(lines)
 
+    def __repr__(self):
+        return "<BasicBlock '{}'>".format(self.name)
+
 class Argument(NamedValue):
     """
     A function argument.
@@ -384,9 +386,13 @@ def remove(self, basic_block):
         basic_block._detach()
         self.basic_blocks.remove(basic_block)
 
-    def predecessors_of(self, successor):
-        return [block for block in self.basic_blocks
-                       if block.is_terminated() and successor in block.successors()]
+    def get_entry(self):
+        assert any(self.basic_blocks)
+        return self.basic_blocks[0]
+
+    def instructions(self):
+        for basic_block in self.basic_blocks:
+            yield from iter(basic_block.instructions)
 
     def __str__(self):
         printer = types.TypePrinter()