m-labs · Oct 7, 2015 · Oct 7, 2015 · Oct 7, 2015
Showing with 125 additions and 6 deletions.

+4 −0 artiq/compiler/module.py

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

+3 −6 artiq/compiler/transforms/asttyped_rewriter.py

+117 −0 artiq/compiler/transforms/devirtualizer.py
diff --git a/artiq/compiler/module.py b/artiq/compiler/module.py
@@ -57,6 +57,7 @@ def __init__(self, src, ref_period=1e-6):
                                                          ref_period=ref_period)
         dead_code_eliminator = transforms.DeadCodeEliminator(engine=self.engine)
         local_access_validator = validators.LocalAccessValidator(engine=self.engine)
+        devirtualizer = transforms.Devirtualizer()
 
         self.name = src.name
         self.globals = src.globals
@@ -65,9 +66,12 @@ def __init__(self, src, ref_period=1e-6):
         monomorphism_validator.visit(src.typedtree)
         escape_validator.visit(src.typedtree)
         iodelay_estimator.visit_fixpoint(src.typedtree)
+        devirtualizer.visit(src.typedtree)
         self.artiq_ir = artiq_ir_generator.visit(src.typedtree)
         dead_code_eliminator.process(self.artiq_ir)
         local_access_validator.process(self.artiq_ir)
+        # for f in self.artiq_ir:
+        #     print(f)
 
     def build_llvm_ir(self, target):
         """Compile the module to LLVM IR for the specified target."""

diff --git a/artiq/compiler/transforms/__init__.py b/artiq/compiler/transforms/__init__.py
@@ -3,5 +3,6 @@
 from .int_monomorphizer import IntMonomorphizer
 from .iodelay_estimator import IODelayEstimator
 from .artiq_ir_generator import ARTIQIRGenerator
+from .devirtualizer import Devirtualizer
 from .dead_code_eliminator import DeadCodeEliminator
 from .llvm_ir_generator import LLVMIRGenerator
diff --git a/artiq/compiler/transforms/asttyped_rewriter.py b/artiq/compiler/transforms/asttyped_rewriter.py
@@ -38,8 +38,7 @@ def visit_in_assign(self, node, in_assign):
 
     def visit_Assign(self, node):
         self.visit(node.value)
-        for target in node.targets:
-            self.visit_in_assign(target, in_assign=True)
+        self.visit_in_assign(node.targets, in_assign=True)
 
     def visit_For(self, node):
         self.visit(node.iter)
@@ -49,14 +48,12 @@ def visit_For(self, node):
 
     def visit_withitem(self, node):
         self.visit(node.context_expr)
-        if node.optional_vars is not None:
-            self.visit_in_assign(node.optional_vars, in_assign=True)
+        self.visit_in_assign(node.optional_vars, in_assign=True)
 
     def visit_comprehension(self, node):
         self.visit(node.iter)
         self.visit_in_assign(node.target, in_assign=True)
-        for if_ in node.ifs:
-            self.visit(node.ifs)
+        self.visit(node.ifs)
 
     def visit_generator(self, node):
         if self.in_root:

diff --git a/artiq/compiler/transforms/devirtualizer.py b/artiq/compiler/transforms/devirtualizer.py
@@ -0,0 +1,117 @@
+"""
+:class:`Devirtualizer` performs method resolution at
+compile time.
+
+Devirtualization is implemented using a lattice
+with three states: unknown → assigned once → diverges.
+The lattice is computed individually for every
+variable in scope as well as every
+(instance type, field name) pair.
+"""
+
+from pythonparser import algorithm
+from .. import asttyped, ir, types
+
+def _advance(target_map, key, value):
+    if key not in target_map:
+        target_map[key] = value # unknown → assigned once
+    else:
+        target_map[key] = None  # assigned once → diverges
+
+class FunctionResolver(algorithm.Visitor):
+    def __init__(self, variable_map):
+        self.variable_map = variable_map
+
+        self.in_assign = False
+        self.scope_map = dict()
+        self.scope = None
+        self.queue = []
+
+    def finalize(self):
+        for thunk in self.queue:
+            thunk()
+
+    def visit_scope(self, node):
+        old_scope, self.scope = self.scope, node
+        self.generic_visit(node)
+        self.scope = old_scope
+
+    def visit_in_assign(self, node):
+        self.in_assign = True
+        self.visit(node)
+        self.in_assign = False
+
+    def visit_Assign(self, node):
+        self.visit(node.value)
+        self.visit_in_assign(node.targets)
+
+    def visit_For(self, node):
+        self.visit(node.iter)
+        self.visit_in_assign(node.target)
+        self.visit(node.body)
+        self.visit(node.orelse)
+
+    def visit_withitem(self, node):
+        self.visit(node.context_expr)
+        self.visit_in_assign(node.optional_vars)
+
+    def visit_comprehension(self, node):
+        self.visit(node.iter)
+        self.visit_in_assign(node.target)
+        self.visit(node.ifs)
+
+    def visit_ModuleT(self, node):
+        self.visit_scope(node)
+
+    def visit_FunctionDefT(self, node):
+        _advance(self.scope_map, (self.scope, node.name), node)
+        self.visit_scope(node)
+
+    def visit_NameT(self, node):
+        if self.in_assign:
+            # Just give up if we assign anything at all to a variable, and
+            # assume it diverges.
+            _advance(self.scope_map, (self.scope, node.id), None)
+        else:
+            # Copy the final value in scope_map into variable_map.
+            key = (self.scope, node.id)
+            def thunk():
+                if key in self.scope_map:
+                    self.variable_map[node] = self.scope_map[key]
+            self.queue.append(thunk)
+
+class MethodResolver(algorithm.Visitor):
+    def __init__(self, variable_map, method_map):
+        self.variable_map = variable_map
+        self.method_map = method_map
+
+    # embedding.Stitcher.finalize generates initialization statements
+    # of form "constructor.meth = meth_body".
+    def visit_Assign(self, node):
+        if node.value not in self.variable_map:
+            return
+
+        value = self.variable_map[node.value]
+        for target in node.targets:
+            if isinstance(target, asttyped.AttributeT):
+                if types.is_constructor(target.value.type):
+                    instance_type = target.value.type.instance
+                elif types.is_instance(target.value.type):
+                    instance_type = target.value.type
+                else:
+                    continue
+                _advance(self.method_map, (instance_type, target.attr), value)
+
+class Devirtualizer:
+    def __init__(self):
+        self.variable_map = dict()
+        self.method_map = dict()
+
+    def visit(self, node):
+        function_resolver = FunctionResolver(self.variable_map)
+        function_resolver.visit(node)
+        function_resolver.finalize()
+
+        method_resolver = MethodResolver(self.variable_map, self.method_map)
+        method_resolver.visit(node)
+        print(self.method_map)