Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: m-labs/artiq
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 561d403dddde
Choose a base ref
...
head repository: m-labs/artiq
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 7c52910dc59d
Choose a head ref
  • 5 commits
  • 7 files changed
  • 1 contributor

Commits on Jul 3, 2015

  1. Unbreak return type inference.

    whitequark committed Jul 3, 2015
    Copy the full SHA
    4358c5c View commit details

Commits on Jul 4, 2015

  1. Implement escape analysis.

    whitequark committed Jul 4, 2015
    Copy the full SHA
    16432d2 View commit details
  2. Don't error out in inferencer if builtin arguments have polymorphic t…

    …ypes.
    whitequark committed Jul 4, 2015
    Copy the full SHA
    4785f0a View commit details
  3. Fix types.TFunction.fold.

    whitequark committed Jul 4, 2015
    Copy the full SHA
    549c110 View commit details

Commits on Jul 11, 2015

  1. Add a basic SSA IR.

    whitequark committed Jul 11, 2015
    7
    Copy the full SHA
    7c52910 View commit details
4 changes: 4 additions & 0 deletions artiq/compiler/builtins.py
Original file line number Diff line number Diff line change
@@ -132,3 +132,7 @@ def is_exn_constructor(typ, name=None):
typ.name == name
else:
return isinstance(typ, types.TExceptionConstructor)

def is_mutable(typ):
return typ.fold(False, lambda accum, typ:
is_list(typ) or types.is_function(typ))
319 changes: 319 additions & 0 deletions artiq/compiler/ir.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,319 @@
"""
The :mod:`ir` module contains the intermediate representation
of the ARTIQ compiler.
"""

from . import types, builtins

# Generic SSA IR classes

def escape_name(name):
if all([isalnum(x) or x == "." for x in name]):
return name
else:
return "\"{}\"".format(name.replace("\"", "\\\""))

class TSSABasicBlock(types.TMono):
def __init__(self):
super().__init__("ssa.basic_block")

class TSSAOption(types.TMono):
def __init__(self, inner):
super().__init__("ssa.option", {"inner": inner})

class Value:
"""
An SSA value that keeps track of its uses.
:ivar type: (:class:`.types.Type`) type of this value
:ivar uses: (list of :class:`Value`) values that use this value
"""

def __init__(self, typ=builtins.TNone()):
self.uses, self.type = set(), typ

def replace_all_uses_with(self, value):
for user in self.uses:
user.replace_uses_of(self, value)

class NamedValue(Value):
"""
An SSA value that has a name.
:ivar name: (string) name of this value
:ivar function: (:class:`Function`) function containing this value
"""

def __init__(self, typ=builtins.TNone(), name=""):
super().__init__(typ)
self.name, self.function = name, None

def set_name(self, new_name):
if self.function is not None:
self.function._remove_name(self.name)
self.name = self.function._add_name(new_name)
else:
self.name = new_name

def _set_function(self, new_function):
if self.function != new_function:
if self.function is not None:
self.function._remove_name(self.name)
self.function = new_function
if self.function is not None:
self.name = self.function._add_name(self.name)

def _detach(self):
self.function = None

def as_operand(self):
return "{} %{}".format(types.TypePrinter().name(self.type),
escape_name(self.name))

class User(NamedValue):
"""
An SSA value that has operands.
:ivar operands: (list of :class:`Value`) operands of this value
"""

def __init__(self, typ=builtins.TNone(), name="", operands=[]):
super().__init__(typ, name)
self.operands = []
self.set_operands(operands)

def set_operands(self, new_operands):
for operand in self.operands:
operand.uses.remove(self)
self.operands = new_operands
for operand in self.operands:
operand.uses.add(self)

def drop_references(self):
self.set_operands([])

def replace_uses_of(self, value, replacement):
assert value in operands

for index, operand in enumerate(operands):
if operand == value:
operands[index] = replacement

value.uses.remove(self)
replacement.uses.add(self)

class Instruction(User):
"""
An SSA instruction.
"""

def __init__(self, typ=builtins.TNone(), name="", operands=[]):
super().__init__(typ, name, operands)
self.basic_block = None

def set_basic_block(self, new_basic_block):
self.basic_block = new_basic_block
if self.basic_block is not None:
self._set_function(self.basic_block.function)
else:
self._set_function(None)

def opcode(self):
"""String representation of the opcode."""
return "???"

def _detach(self):
self.set_basic_block(None)

def remove_from_parent(self):
if self.basic_block is not None:
self.basic_block.remove(self)

def erase(self):
self.remove_from_parent()
self.drop_references()

def replace_with(self, value):
self.replace_all_uses_with(value)
if isinstance(value, Instruction):
self.basic_block.replace(self, value)
self.drop_references()
else:
self.erase()

def __str__(self):
if builtins.is_none(self.type):
prefix = ""
else:
prefix = "%{} = {} ".format(escape_name(self.name),
types.TypePrinter().name(self.type))

if any(self.operands):
return "{} {} {}".format(prefix, self.opcode(),
", ".join([operand.as_operand() for operand in self.operands]))
else:
return "{} {}".format(prefix, self.opcode())

class Phi(Instruction):
"""
An SSA instruction that joins data flow.
"""

def opcode(self):
return "phi"

def incoming(self):
operand_iter = iter(self.operands)
while True:
yield next(operand_iter), next(operand_iter)

def incoming_blocks(self):
(block for (block, value) in self.incoming())

def incoming_values(self):
(value for (block, value) in self.incoming())

def incoming_value_for_block(self, target_block):
for (block, value) in self.incoming():
if block == target_block:
return value
assert False

def add_incoming(self, value, block):
assert value.type == self.type
self.operands.append(value)
self.operands.append(block)

def __str__(self):
if builtins.is_none(self.type):
prefix = ""
else:
prefix = "%{} = {} ".format(escape_name(self.name),
types.TypePrinter().name(self.type))

if any(self.operands):
operand_list = ["%{} => %{}".format(escape_name(block.name), escape_name(value.name))
for operand in self.operands]
return "{} {} [{}]".format(prefix, self.opcode(), ", ".join(operand_list))

class Terminator(Instruction):
"""
An SSA instruction that performs control flow.
"""

def successors(self):
[operand for operand in self.operands if isinstance(operand, BasicBlock)]

class BasicBlock(NamedValue):
"""
A block of instructions with no control flow inside it.
:ivar instructions: (list of :)
"""

def __init__(self, name="", instructions=[]):
super().__init__(TSSABasicBlock(), name)
self.instructions = []
self.set_instructions(instructions)

def remove_from_parent(self):
if self.function is not None:
self.function.remove(self)

def prepend(self, insn):
insn.set_basic_block(self)
self.instructions.insert(0, insn)

def append(self, insn):
insn.set_basic_block(self)
self.instructions.append(insn)

def index(self, insn):
return self.instructions.index(insn)

def insert(self, before, insn):
insn.set_basic_block(self)
self.instructions.insert(self.index(before), insn)

def remove(self, insn):
insn._detach()
self.instructions.remove(insn)

def replace(self, insn, replacement):
self.insert(insn, replacement)
self.remove(insn)

def terminator(self):
assert isinstance(self.instructions[-1], Terminator)
return self.instructions[-1]

def successors(self):
return self.terminator().successors()

def predecessors(self):
assert self.function is not None
self.function.predecessors_of(self)

def __str__(self):
lines = ["{}:".format(escape_name(self.name))]
for insn in self.instructions:
lines.append(str(insn))
return "\n".join(lines)

class Argument(NamedValue):
"""
A function argument.
"""

def __str__(self):
return self.as_operand()

class Function(Value):
"""
A function containing SSA IR.
"""

def __init__(self, typ, name, arguments):
self.type, self.name, self.arguments = typ, name, []
self.set_arguments(arguments)
self.basic_blocks = set()
self.names = set()

def _remove_name(self, name):
self.names.remove(name)

def _add_name(self, base_name):
name, counter = base_name, 1
while name in self.names or name == "":
if base_name == "":
name = str(counter)
else:
name = "{}.{}".format(name, counter)
counter += 1

self.names.add(name)
return name

def set_arguments(self, new_arguments):
for argument in self.arguments:
argument._set_function(None)
self.arguments = new_arguments
for argument in self.arguments:
argument._set_function(self)

def add(self, basic_block):
basic_block._set_function(self)
self.basic_blocks.add(basic_blocks)

def remove(self, basic_block):
basic_block._detach()
self.basic_block.remove(basic_block)

def predecessors_of(self, successor):
set(block for block in self.basic_blocks if successor in block.successors())

def as_operand(self):
return "{} @{}".format(types.TypePrinter().name(self.type),
escape_name(self.name))

# Python-specific SSA IR classes
21 changes: 14 additions & 7 deletions artiq/compiler/transforms/asttyped_rewriter.py
Original file line number Diff line number Diff line change
@@ -28,32 +28,32 @@ def __init__(self, env_stack, engine):
# parameters can't be declared as global or nonlocal
self.params = set()

def visit_in_assign(self, node):
def visit_in_assign(self, node, in_assign):
try:
self.in_assign = True
old_in_assign, self.in_assign = self.in_assign, in_assign
return self.visit(node)
finally:
self.in_assign = False
self.in_assign = old_in_assign

def visit_Assign(self, node):
self.visit(node.value)
for target in node.targets:
self.visit_in_assign(target)
self.visit_in_assign(target, in_assign=True)

def visit_For(self, node):
self.visit(node.iter)
self.visit_in_assign(node.target)
self.visit_in_assign(node.target, in_assign=True)
self.visit(node.body)
self.visit(node.orelse)

def visit_withitem(self, node):
self.visit(node.context_expr)
if node.optional_vars is not None:
self.visit_in_assign(node.optional_vars)
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)
self.visit_in_assign(node.target, in_assign=True)
for if_ in node.ifs:
self.visit(node.ifs)

@@ -99,6 +99,13 @@ def visit_Name(self, node):
# creates a new binding for x in f's scope
self._assignable(node.id)

def visit_Attribute(self, node):
self.visit_in_assign(node.value, in_assign=False)

def visit_Subscript(self, node):
self.visit_in_assign(node.value, in_assign=False)
self.visit_in_assign(node.slice, in_assign=False)

def _check_not_in(self, name, names, curkind, newkind, loc):
if name in names:
diag = diagnostic.Diagnostic("error",
Loading