compiler: maintain both the IR and iodelay forms of delay expressions.

After this commit, the delay instruction (again) does not generate any LLVM IR: all heavy lifting is relegated to the delay and delay_mu intrinsics. When the interleave transform needs to adjust the global timeline, it synthesizes a delay_mu intrinsnic. This way, the interleave transformation becomes composable, as the input and the output IR invariants are the same. Also, code generation is adjusted so that a basic block is split off not only after a delay call, but also before one; otherwise, e.g., code immediately at the beginning of a `with parallel:` branch would have no choice but to execute after another branch has already advanced the timeline. This takes care of issue #1 described in 50e7b44 and is a step to solving issue #2.
m-labs · Nov 20, 2015 · cb3b811 · cb3b811
1 parent 50e7b44
commit cb3b811
Showing 7 changed files with 142 additions and 108 deletions.
diff --git a/artiq/compiler/builtins.py b/artiq/compiler/builtins.py
@@ -38,6 +38,12 @@ def zero():
     def one():
         return 1
 
+def TInt32():
+    return TInt(types.TValue(32))
+
+def TInt64():
+    return TInt(types.TValue(64))
+
 class TFloat(types.TMono):
     def __init__(self):
         super().__init__("float")

diff --git a/artiq/compiler/ir.py b/artiq/compiler/ir.py
@@ -72,6 +72,16 @@ def as_entity(self, type_printer):
         return "{} {}".format(type_printer.name(self.type),
                               repr(self.value))
 
+    def __hash__(self):
+        return hash(self.value)
+
+    def __eq__(self, other):
+        return isinstance(other, Constant) and \
+            other.type == self.type and other.value == self.value
+
+    def __ne__(self, other):
+        return not (self == other)
+
 class NamedValue(Value):
     """
     An SSA value that has a name.
@@ -190,7 +200,7 @@ def _operands_as_string(self, type_printer):
         return ", ".join([operand.as_operand(type_printer) for operand in self.operands])
 
     def as_entity(self, type_printer):
-        if builtins.is_none(self.type):
+        if builtins.is_none(self.type) and len(self.uses) == 0:
             prefix = ""
         else:
             prefix = "%{} = {} ".format(escape_name(self.name),
@@ -1198,35 +1208,46 @@ class Delay(Terminator):
 
     :ivar expr: (:class:`iodelay.Expr`) expression
     :ivar var_names: (list of string)
-        iodelay expression names corresponding to operands
+        iodelay variable names corresponding to operands
     """
 
     """
     :param expr: (:class:`iodelay.Expr`) expression
     :param substs: (dict of str to :class:`Value`)
+        SSA values corresponding to iodelay variable names
+    :param call: (:class:`Call` or ``Constant(None, builtins.TNone())``)
+        the call instruction that caused this delay, if any
     :param target: (:class:`BasicBlock`) branch target
     """
-    def __init__(self, expr, substs, target, name=""):
+    def __init__(self, expr, substs, decomposition, target, name=""):
         for var_name in substs: assert isinstance(var_name, str)
+        assert isinstance(decomposition, Call) or \
+            isinstance(decomposition, Builtin) and decomposition.op in ("delay", "delay_mu")
         assert isinstance(target, BasicBlock)
-        super().__init__([target, *substs.values()], builtins.TNone(), name)
+        super().__init__([decomposition, target, *substs.values()], builtins.TNone(), name)
         self.expr = expr
         self.var_names = list(substs.keys())
 
-    def target(self):
+    def decomposition(self):
         return self.operands[0]
 
+    def target(self):
+        return self.operands[1]
+
     def set_target(self, new_target):
-        self.operands[0] = new_target
+        self.operands[1] = new_target
 
     def substs(self):
-        return zip(self.var_names, self.operands[1:])
+        return zip(self.var_names, self.operands[2:])
 
     def _operands_as_string(self, type_printer):
         substs = []
         for var_name, operand in self.substs():
             substs.append("{}={}".format(var_name, operand))
-        return "[{}], {}".format(", ".join(substs), self.target().as_operand(type_printer))
+        result = "[{}]".format(", ".join(substs))
+        result += ", decomp {}, to {}".format(self.decomposition().as_operand(type_printer),
+                                              self.target().as_operand(type_printer))
+        return result
 
     def opcode(self):
         return "delay({})".format(self.expr)

diff --git a/artiq/compiler/transforms/artiq_ir_generator.py b/artiq/compiler/transforms/artiq_ir_generator.py
@@ -1418,15 +1418,6 @@ def alloc_exn(self, typ, message=None, param0=None, param1=None, param2=None):
 
         return self.append(ir.Alloc(attributes, typ))
 
-    def _make_delay(self, delay):
-        if not iodelay.is_const(delay, 0):
-            after_delay = self.add_block()
-            self.append(ir.Delay(delay,
-                                 {var_name: self.current_args[var_name]
-                                  for var_name in delay.free_vars()},
-                                 after_delay))
-            self.current_block = after_delay
-
     def visit_builtin_call(self, node):
         # A builtin by any other name... Ignore node.func, just use the type.
         typ = node.func.type
@@ -1529,15 +1520,16 @@ def body_gen(index):
                 return self.append(ir.Arith(ast.Mult(loc=None), now_mu_float, self.ref_period))
             else:
                 assert False
-        elif types.is_builtin(typ, "at"):
+        elif types.is_builtin(typ, "delay") or types.is_builtin(typ, "at"):
             if len(node.args) == 1 and len(node.keywords) == 0:
                 arg = self.visit(node.args[0])
                 arg_mu_float = self.append(ir.Arith(ast.Div(loc=None), arg, self.ref_period))
                 arg_mu = self.append(ir.Coerce(arg_mu_float, builtins.TInt(types.TValue(64))))
                 self.append(ir.Builtin(typ.name + "_mu", [arg_mu], builtins.TNone()))
             else:
                 assert False
-        elif types.is_builtin(typ, "now_mu") or types.is_builtin(typ, "at_mu"):
+        elif types.is_builtin(typ, "now_mu") or types.is_builtin(typ, "delay_mu") \
+                or types.is_builtin(typ, "at_mu"):
             return self.append(ir.Builtin(typ.name,
                                           [self.visit(arg) for arg in node.args], node.type))
         elif types.is_builtin(typ, "mu_to_seconds"):
@@ -1554,9 +1546,6 @@ def body_gen(index):
                 return self.append(ir.Coerce(arg_mu, builtins.TInt(types.TValue(64))))
             else:
                 assert False
-        elif types.is_builtin(typ, "delay") or types.is_builtin(typ, "delay_mu"):
-            assert node.iodelay is not None
-            self._make_delay(node.iodelay)
         elif types.is_exn_constructor(typ):
             return self.alloc_exn(node.type, *[self.visit(arg_node) for arg_node in node.args])
         elif types.is_constructor(typ):
@@ -1567,77 +1556,82 @@ def body_gen(index):
     def visit_CallT(self, node):
         typ = node.func.type.find()
 
+        if node.iodelay is not None and not iodelay.is_const(node.iodelay, 0):
+            before_delay = self.current_block
+            during_delay = self.add_block()
+            before_delay.append(ir.Branch(during_delay))
+            self.current_block = during_delay
+
         if types.is_builtin(typ):
-            return self.visit_builtin_call(node)
-
-        if types.is_function(typ):
-            func     = self.visit(node.func)
-            self_arg = None
-            fn_typ   = typ
-            offset   = 0
-        elif types.is_method(typ):
-            method   = self.visit(node.func)
-            func     = self.append(ir.GetAttr(method, "__func__"))
-            self_arg = self.append(ir.GetAttr(method, "__self__"))
-            fn_typ   = types.get_method_function(typ)
-            offset   = 1
+            insn = self.visit_builtin_call(node)
         else:
-            assert False
+            if types.is_function(typ):
+                func     = self.visit(node.func)
+                self_arg = None
+                fn_typ   = typ
+                offset   = 0
+            elif types.is_method(typ):
+                method   = self.visit(node.func)
+                func     = self.append(ir.GetAttr(method, "__func__"))
+                self_arg = self.append(ir.GetAttr(method, "__self__"))
+                fn_typ   = types.get_method_function(typ)
+                offset   = 1
+            else:
+                assert False
 
-        args = [None] * (len(fn_typ.args) + len(fn_typ.optargs))
+            args = [None] * (len(fn_typ.args) + len(fn_typ.optargs))
 
-        for index, arg_node in enumerate(node.args):
-            arg = self.visit(arg_node)
-            if index < len(fn_typ.args):
-                args[index + offset] = arg
+            for index, arg_node in enumerate(node.args):
+                arg = self.visit(arg_node)
+                if index < len(fn_typ.args):
+                    args[index + offset] = arg
+                else:
+                    args[index + offset] = self.append(ir.Alloc([arg], ir.TOption(arg.type)))
+
+            for keyword in node.keywords:
+                arg = self.visit(keyword.value)
+                if keyword.arg in fn_typ.args:
+                    for index, arg_name in enumerate(fn_typ.args):
+                        if keyword.arg == arg_name:
+                            assert args[index] is None
+                            args[index] = arg
+                            break
+                elif keyword.arg in fn_typ.optargs:
+                    for index, optarg_name in enumerate(fn_typ.optargs):
+                        if keyword.arg == optarg_name:
+                            assert args[len(fn_typ.args) + index] is None
+                            args[len(fn_typ.args) + index] = \
+                                    self.append(ir.Alloc([arg], ir.TOption(arg.type)))
+                            break
+
+            for index, optarg_name in enumerate(fn_typ.optargs):
+                if args[len(fn_typ.args) + index] is None:
+                    args[len(fn_typ.args) + index] = \
+                            self.append(ir.Alloc([], ir.TOption(fn_typ.optargs[optarg_name])))
+
+            if self_arg is not None:
+                assert args[0] is None
+                args[0] = self_arg
+
+            assert None not in args
+
+            if self.unwind_target is None:
+                insn = self.append(ir.Call(func, args))
             else:
-                args[index + offset] = self.append(ir.Alloc([arg], ir.TOption(arg.type)))
-
-        for keyword in node.keywords:
-            arg = self.visit(keyword.value)
-            if keyword.arg in fn_typ.args:
-                for index, arg_name in enumerate(fn_typ.args):
-                    if keyword.arg == arg_name:
-                        assert args[index] is None
-                        args[index] = arg
-                        break
-            elif keyword.arg in fn_typ.optargs:
-                for index, optarg_name in enumerate(fn_typ.optargs):
-                    if keyword.arg == optarg_name:
-                        assert args[len(fn_typ.args) + index] is None
-                        args[len(fn_typ.args) + index] = \
-                                self.append(ir.Alloc([arg], ir.TOption(arg.type)))
-                        break
-
-        for index, optarg_name in enumerate(fn_typ.optargs):
-            if args[len(fn_typ.args) + index] is None:
-                args[len(fn_typ.args) + index] = \
-                        self.append(ir.Alloc([], ir.TOption(fn_typ.optargs[optarg_name])))
-
-        if self_arg is not None:
-            assert args[0] is None
-            args[0] = self_arg
-
-        assert None not in args
-
-        if self.unwind_target is None:
-            insn = self.append(ir.Call(func, args))
-        else:
-            after_invoke = self.add_block()
-            insn = self.append(ir.Invoke(func, args, after_invoke, self.unwind_target))
-            self.current_block = after_invoke
+                after_invoke = self.add_block()
+                insn = self.append(ir.Invoke(func, args, after_invoke, self.unwind_target))
+                self.current_block = after_invoke
 
-        method_key = None
-        if isinstance(node.func, asttyped.AttributeT):
-            attr_node = node.func
-            self.method_map[(attr_node.value.type, attr_node.attr)].append(insn)
+            method_key = None
+            if isinstance(node.func, asttyped.AttributeT):
+                attr_node = node.func
+                self.method_map[(attr_node.value.type, attr_node.attr)].append(insn)
 
         if node.iodelay is not None and not iodelay.is_const(node.iodelay, 0):
             after_delay = self.add_block()
-            self.append(ir.Delay(node.iodelay,
-                                 {var_name: self.current_args[var_name]
-                                  for var_name in node.iodelay.free_vars()},
-                                 after_delay))
+            substs = {var_name: self.current_args[var_name]
+                      for var_name in node.iodelay.free_vars()}
+            self.append(ir.Delay(node.iodelay, substs, insn, after_delay))
             self.current_block = after_delay
 
         return insn

diff --git a/artiq/compiler/transforms/interleaver.py b/artiq/compiler/transforms/interleaver.py
@@ -3,7 +3,7 @@
 the timestamp would always monotonically nondecrease.
 """
 
-from .. import ir, iodelay
+from .. import types, builtins, ir, iodelay
 from ..analyses import domination
 
 def delay_free_subgraph(root, limit):
@@ -81,20 +81,39 @@ def time_after_block(pair):
                 target_time_delta = new_target_time - target_time
 
                 target_terminator = target_block.terminator()
-                if isinstance(target_terminator, (ir.Delay, ir.Branch)):
-                    target_terminator.set_target(source_block)
-                elif isinstance(target_terminator, ir.Parallel):
+                if isinstance(target_terminator, ir.Parallel):
                     target_terminator.replace_with(ir.Branch(source_block))
                 else:
-                    assert False
+                    assert isinstance(target_terminator, (ir.Delay, ir.Branch))
+                    target_terminator.set_target(source_block)
 
                 source_terminator = source_block.terminator()
+
+                if isinstance(source_terminator, ir.Delay):
+                    old_decomp = source_terminator.decomposition()
+                else:
+                    old_decomp = None
+
                 if target_time_delta > 0:
                     assert isinstance(source_terminator, ir.Delay)
-                    source_terminator.expr = iodelay.Const(target_time_delta)
+
+                    if isinstance(old_decomp, ir.Builtin) and \
+                            old_decomp.op in ("delay", "delay_mu"):
+                        new_decomp_expr = ir.Constant(target_time_delta, builtins.TInt64())
+                        new_decomp = ir.Builtin("delay_mu", [new_decomp_expr], builtins.TNone())
+                        new_decomp.loc = old_decomp.loc
+                        source_terminator.basic_block.insert(source_terminator, new_decomp)
+                    else:
+                        assert False # TODO
+
+                    source_terminator.replace_with(ir.Delay(iodelay.Const(target_time_delta), {},
+                                                            new_decomp, source_terminator.target()))
                 else:
                     source_terminator.replace_with(ir.Branch(source_terminator.target()))
 
+                if old_decomp is not None:
+                    old_decomp.erase()
+
                 target_block = source_block
                 target_time  = new_target_time
 

diff --git a/artiq/compiler/transforms/llvm_ir_generator.py b/artiq/compiler/transforms/llvm_ir_generator.py
@@ -7,7 +7,7 @@
 from pythonparser import ast, diagnostic
 from llvmlite_artiq import ir as ll
 from ...language import core as language_core
-from .. import types, builtins, ir, iodelay
+from .. import types, builtins, ir
 
 
 llvoid     = ll.VoidType()
@@ -787,6 +787,12 @@ def get_outer(llenv, env_ty):
         elif insn.op == "at_mu":
             time, = insn.operands
             return self.llbuilder.store(self.map(time), self.llbuiltin("now"))
+        elif insn.op == "delay_mu":
+            interval, = insn.operands
+            llnowptr = self.llbuiltin("now")
+            llnow = self.llbuilder.load(llnowptr)
+            lladjusted = self.llbuilder.add(llnow, self.map(interval))
+            return self.llbuilder.store(lladjusted, llnowptr)
         else:
             assert False
 
@@ -1062,6 +1068,8 @@ def process_Select(self, insn):
     def process_Branch(self, insn):
         return self.llbuilder.branch(self.map(insn.target()))
 
+    process_Delay = process_Branch
+
     def process_BranchIf(self, insn):
         return self.llbuilder.cbranch(self.map(insn.condition()),
                                       self.map(insn.if_true()), self.map(insn.if_false()))
@@ -1141,17 +1149,3 @@ def process_LandingPad(self, insn):
             self.llbuilder.branch(self.map(insn.cleanup()))
 
         return llexn
-
-    def process_Delay(self, insn):
-        def map_delay(expr):
-            if isinstance(expr, iodelay.Const):
-                return ll.Constant(lli64, int(expr.value))
-            else:
-                assert False
-
-        llnowptr = self.llbuiltin("now")
-        llnow = self.llbuilder.load(llnowptr)
-        lladjusted = self.llbuilder.add(llnow, map_delay(insn.expr))
-        self.llbuilder.store(lladjusted, llnowptr)
-
-        return self.llbuilder.branch(self.map(insn.target()))
diff --git a/lit-test/test/interleaving/nonoverlapping.py b/lit-test/test/interleaving/nonoverlapping.py
@@ -18,8 +18,8 @@ def g():
             print("E", now_mu())
 
 # CHECK-L: A 0
+# CHECK-L: C 0
 # CHECK-L: B 2
-# CHECK-L: C 2
 # CHECK-L: D 2
 # CHECK-L: E 4
 g()
diff --git a/lit-test/test/interleaving/overlapping.py b/lit-test/test/interleaving/overlapping.py
@@ -17,9 +17,9 @@ def g():
             #
             print("E", now_mu())
 
+# CHECK-L: A 0
 # CHECK-L: C 0
-# CHECK-L: A 2
+# CHECK-L: D 2
 # CHECK-L: B 3
-# CHECK-L: D 3
 # CHECK-L: E 4
 g()