Skip to content

Commit

Permalink
Merge branch 'new-py2llvm'
Browse files Browse the repository at this point in the history
whitequark committed Nov 23, 2015
2 parents de30a4b + 66b1388 commit c14299d
Showing 236 changed files with 15,353 additions and 3,913 deletions.
8 changes: 8 additions & 0 deletions .gitignore
Original file line number Diff line number Diff line change
@@ -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
2 changes: 1 addition & 1 deletion .gitmodules
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
3 changes: 3 additions & 0 deletions .travis.yml
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:
2 changes: 2 additions & 0 deletions artiq/compiler/__init__.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,2 @@
from .module import Module, Source
from .embedding import Stitcher
1 change: 1 addition & 0 deletions artiq/compiler/algorithms/__init__.py
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
from .inline import inline
80 changes: 80 additions & 0 deletions artiq/compiler/algorithms/inline.py
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()
2 changes: 2 additions & 0 deletions artiq/compiler/analyses/__init__.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,2 @@
from .domination import DominatorTree
from .devirtualization import Devirtualization
119 changes: 119 additions & 0 deletions artiq/compiler/analyses/devirtualization.py
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)
137 changes: 137 additions & 0 deletions artiq/compiler/analyses/domination.py
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
Loading

0 comments on commit c14299d

Please sign in to comment.