Merge branch 'new-py2llvm'

m-labs · Nov 23, 2015 · c14299d · c14299d
2 parents de30a4b + 66b1388
commit c14299d
Showing 236 changed files with 15,353 additions and 3,913 deletions.
diff --git a/.gitignore b/.gitignore
@@ -5,6 +5,7 @@ __pycache__
 *.bin
 *.elf
 *.fbi
+*.pyc
 doc/manual/_build
 /build
 /dist
@@ -15,3 +16,10 @@ artiq/test/h5types.h5
 examples/master/results
 examples/master/dataset_db.pyon
 examples/sim/dataset_db.pyon
+Output/
+/lit-test/libartiq_support/libartiq_support.so
+
+# for developer convenience
+/test*.py
+/device_db.pyon
+/dataset_db.pyon
diff --git a/.gitmodules b/.gitmodules
@@ -1,4 +1,4 @@
 [submodule "artiq/runtime/lwip"]
 	path = artiq/runtime/lwip
 	url = git://git.savannah.nongnu.org/lwip.git
-    ignore = untracked
+	ignore = untracked
diff --git a/.travis.yml b/.travis.yml
@@ -1,6 +1,9 @@
 language: python
 python:
   - '3.5'
+branches:
+  only:
+    - master
 sudo: false
 env:
   global:

diff --git a/artiq/compiler/__init__.py b/artiq/compiler/__init__.py
@@ -0,0 +1,2 @@
+from .module import Module, Source
+from .embedding import Stitcher
diff --git a/artiq/compiler/algorithms/__init__.py b/artiq/compiler/algorithms/__init__.py
@@ -0,0 +1 @@
+from .inline import inline
diff --git a/artiq/compiler/algorithms/inline.py b/artiq/compiler/algorithms/inline.py
@@ -0,0 +1,80 @@
+"""
+:func:`inline` inlines a call instruction in ARTIQ IR.
+The call instruction must have a statically known callee,
+it must be second to last in the basic block, and the basic
+block must have exactly one successor.
+"""
+
+from .. import types, builtins, iodelay, ir
+
+def inline(call_insn):
+    assert isinstance(call_insn, ir.Call)
+    assert call_insn.static_target_function is not None
+    assert len(call_insn.basic_block.successors()) == 1
+    assert call_insn.basic_block.index(call_insn) == \
+                len(call_insn.basic_block.instructions) - 2
+
+    value_map          = {}
+    source_function    = call_insn.static_target_function
+    target_function    = call_insn.basic_block.function
+    target_predecessor = call_insn.basic_block
+    target_successor   = call_insn.basic_block.successors()[0]
+
+    if builtins.is_none(source_function.type.ret):
+        target_return_phi = None
+    else:
+        target_return_phi = target_successor.prepend(ir.Phi(source_function.type.ret))
+
+    closure = target_predecessor.insert(ir.GetAttr(call_insn.target_function(), '__closure__'),
+                                        before=call_insn)
+    for actual_arg, formal_arg in zip([closure] + call_insn.arguments(),
+                                      source_function.arguments):
+        value_map[formal_arg] = actual_arg
+
+    for source_block in source_function.basic_blocks:
+        target_block = ir.BasicBlock([], "i." + source_block.name)
+        target_function.add(target_block)
+        value_map[source_block] = target_block
+
+    def mapper(value):
+        if isinstance(value, ir.Constant):
+            return value
+        else:
+            return value_map[value]
+
+    for source_insn in source_function.instructions():
+        target_block = value_map[source_insn.basic_block]
+        if isinstance(source_insn, ir.Return):
+            if target_return_phi is not None:
+                target_return_phi.add_incoming(mapper(source_insn.value()), target_block)
+            target_insn = ir.Branch(target_successor)
+        elif isinstance(source_insn, ir.Phi):
+            target_insn = ir.Phi()
+        elif isinstance(source_insn, ir.Delay):
+            substs        = source_insn.substs()
+            mapped_substs = {var: value_map[substs[var]] for var in substs}
+            const_substs  = {var: iodelay.Const(mapped_substs[var].value)
+                             for var in mapped_substs
+                              if isinstance(mapped_substs[var], ir.Constant)}
+            other_substs  = {var: mapped_substs[var]
+                             for var in mapped_substs
+                              if not isinstance(mapped_substs[var], ir.Constant)}
+            target_insn  = ir.Delay(source_insn.expr.fold(const_substs), other_substs,
+                                    value_map[source_insn.decomposition()],
+                                    value_map[source_insn.target()])
+        else:
+            target_insn = source_insn.copy(mapper)
+            target_insn.name = "i." + source_insn.name
+        value_map[source_insn] = target_insn
+        target_block.append(target_insn)
+
+    for source_insn in source_function.instructions():
+        if isinstance(source_insn, ir.Phi):
+            target_insn = value_map[source_insn]
+            for block, value in source_insn.incoming():
+                target_insn.add_incoming(value_map[value], value_map[block])
+
+    target_predecessor.terminator().replace_with(ir.Branch(value_map[source_function.entry()]))
+    if target_return_phi is not None:
+        call_insn.replace_all_uses_with(target_return_phi)
+    call_insn.erase()
diff --git a/artiq/compiler/analyses/__init__.py b/artiq/compiler/analyses/__init__.py
@@ -0,0 +1,2 @@
+from .domination import DominatorTree
+from .devirtualization import Devirtualization
diff --git a/artiq/compiler/analyses/devirtualization.py b/artiq/compiler/analyses/devirtualization.py
@@ -0,0 +1,119 @@
+"""
+: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.scope_map = dict()
+        self.queue = []
+
+        self.in_assign = False
+        self.current_scopes = []
+
+    def finalize(self):
+        for thunk in self.queue:
+            thunk()
+
+    def visit_scope(self, node):
+        self.current_scopes.append(node)
+        self.generic_visit(node)
+        self.current_scopes.pop()
+
+    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.current_scopes[-1], 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.current_scopes[-1], node.id), None)
+        else:
+            # Look up the final value in scope_map and copy it into variable_map.
+            keys = [(scope, node.id) for scope in reversed(self.current_scopes)]
+            def thunk():
+                for key in keys:
+                    if key in self.scope_map:
+                        self.variable_map[node] = self.scope_map[key]
+                        return
+            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 Devirtualization:
+    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)
diff --git a/artiq/compiler/analyses/domination.py b/artiq/compiler/analyses/domination.py
@@ -0,0 +1,137 @@
+"""
+:class:`DominatorTree` computes the dominance relation over
+control flow graphs.
+
+See http://www.cs.rice.edu/~keith/EMBED/dom.pdf.
+"""
+
+class GenericDominatorTree:
+    def __init__(self):
+        self._assign_names()
+        self._compute()
+
+    def _traverse_in_postorder(self):
+        raise NotImplementedError
+
+    def _prev_block_names(self, block):
+        raise NotImplementedError
+
+    def _assign_names(self):
+        postorder = self._traverse_in_postorder()
+
+        self._start_name    = len(postorder) - 1
+        self._block_of_name = postorder
+        self._name_of_block = {}
+        for block_name, block in enumerate(postorder):
+            self._name_of_block[block] = block_name
+
+    def _intersect(self, block_name_1, block_name_2):
+        finger_1, finger_2 = block_name_1, block_name_2
+        while finger_1 != finger_2:
+            while finger_1 < finger_2:
+                finger_1 = self._doms[finger_1]
+            while finger_2 < finger_1:
+                finger_2 = self._doms[finger_2]
+        return finger_1
+
+    def _compute(self):
+        self._doms = {}
+
+        # Start block dominates itself.
+        self._doms[self._start_name] = self._start_name
+
+        # We don't yet know what blocks dominate all other blocks.
+        for block_name in range(self._start_name):
+            self._doms[block_name] = None
+
+        changed = True
+        while changed:
+            changed = False
+
+            # For all blocks except start block, in reverse postorder...
+            for block_name in reversed(range(self._start_name)):
+                # Select a new immediate dominator from the blocks we have
+                # already processed, and remember all others.
+                # We've already processed at least one previous block because
+                # of the graph traverse order.
+                new_idom, prev_block_names = None, []
+                for prev_block_name in self._prev_block_names(block_name):
+                    if new_idom is None and self._doms[prev_block_name] is not None:
+                        new_idom = prev_block_name
+                    else:
+                        prev_block_names.append(prev_block_name)
+
+                # Find a common previous block
+                for prev_block_name in prev_block_names:
+                    if self._doms[prev_block_name] is not None:
+                        new_idom = self._intersect(prev_block_name, new_idom)
+
+                if self._doms[block_name] != new_idom:
+                    self._doms[block_name] = new_idom
+                    changed = True
+
+    def immediate_dominator(self, block):
+        return self._block_of_name[self._doms[self._name_of_block[block]]]
+
+    def dominators(self, block):
+        yield block
+
+        block_name = self._name_of_block[block]
+        while block_name != self._doms[block_name]:
+            block_name = self._doms[block_name]
+            yield self._block_of_name[block_name]
+
+class DominatorTree(GenericDominatorTree):
+    def __init__(self, function):
+        self.function = function
+        super().__init__()
+
+    def _traverse_in_postorder(self):
+        postorder = []
+
+        visited = set()
+        def visit(block):
+            visited.add(block)
+            for next_block in block.successors():
+                if next_block not in visited:
+                    visit(next_block)
+            postorder.append(block)
+
+        visit(self.function.entry())
+
+        return postorder
+
+    def _prev_block_names(self, block_name):
+        for block in self._block_of_name[block_name].predecessors():
+            yield self._name_of_block[block]
+
+class PostDominatorTree(GenericDominatorTree):
+    def __init__(self, function):
+        self.function = function
+        super().__init__()
+
+    def _traverse_in_postorder(self):
+        postorder = []
+
+        visited = set()
+        def visit(block):
+            visited.add(block)
+            for next_block in block.predecessors():
+                if next_block not in visited:
+                    visit(next_block)
+            postorder.append(block)
+
+        for block in self.function.basic_blocks:
+            if not any(block.successors()):
+                visit(block)
+
+        postorder.append(None) # virtual exit block
+        return postorder
+
+    def _prev_block_names(self, block_name):
+        succ_blocks = self._block_of_name[block_name].successors()
+        if len(succ_blocks) > 0:
+            for block in succ_blocks:
+                yield self._name_of_block[block]
+        else:
+            yield self._start_name
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		from .module import Module, Source
		from .embedding import Stitcher
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		from .domination import DominatorTree
		from .devirtualization import Devirtualization