-
Notifications
You must be signed in to change notification settings - Fork 201
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Showing
236 changed files
with
15,353 additions
and
3,913 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -1,4 +1,4 @@ | ||
[submodule "artiq/runtime/lwip"] | ||
path = artiq/runtime/lwip | ||
url = git://git.savannah.nongnu.org/lwip.git | ||
ignore = untracked | ||
ignore = untracked |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -1,6 +1,9 @@ | ||
language: python | ||
python: | ||
- '3.5' | ||
branches: | ||
only: | ||
- master | ||
sudo: false | ||
env: | ||
global: | ||
|
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,2 @@ | ||
from .module import Module, Source | ||
from .embedding import Stitcher |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1 @@ | ||
from .inline import inline |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,2 @@ | ||
from .domination import DominatorTree | ||
from .devirtualization import Devirtualization |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -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 |
Oops, something went wrong.