Repository: calyxir/calyx (language: rust)

Issue:
Implement PIFO trees using binary-heap PIFOs
#2067 got us binary heaps, which is super cool. It also got us a small number of scheduling transactions, such that the binary heap plus a scheduling transaction over it obeys the same interface as our [simple round-robin PIFOs](https://docs.calyxir.org/frontends/queues.html#pifo). With our simple round-robin PIFOs, it was easy to build a PIFO tree. This will be a little trickier to do with binary heaps at nodes. This issue tracks the need to do that.

We will need to lay out a number of binary heaps that match some given tree shape. In binary heaps at leaves, we will need to store user-given values. In binary heaps at internal nodes, we will need to store integers. We will need to define the `push` operation with care, to ensure that an appropriate path of integers (plus one, final, user-given value) is pushed into the tree. Similarly we will need to have a `pop` operation. The `peek` operation will be easy after that. Anyway, the point is that we no longer get trees for free, as we did from our RR PIFOs. Let's actually build them, much like the _Formal Abstractions_ [artifact](https://github.com/cornell-netlab/pifo-trees-artifact/blob/main/lib/pifotree.ml) does.

Assigning to @KabirSamsi since he requested it, but I sincerely encourage folks to talk this out in a meeting or in a 1:1 with me before jumping in!


Discussion / hints:
@KabirSamsi just a quick request to please do a little documentation in this thread to capture our discussion from today! Don't spend too much time on it, but do get down the basic concrete plan so that we can look at it together. I think it'll really help you when you get back to this in a few days :)
Actually @KabirSamsi let's try and meet tomorrow morning if that's possible. Like, before you put in any energy towards a write-up. On further thinking I may have given you a bit of #fakenews during our chat today. The thing I'd like to revisit is your starting point. I told you you'd want to start with Calyx and create a Calyx-level tree, but I now think you may be able to start with OCaml and create a Calyx-level tree. @polybeandip feel free to join this chat, since it will involve a handshake with your work
Yes sounds good! To both :)

Fix patch:
diff --git a/frontends/queues/queues/binheap/round_robin.py b/frontends/queues/queues/binheap/round_robin.py
index 75584aca3c..10c6a1a16b 100644
--- a/frontends/queues/queues/binheap/round_robin.py
+++ b/frontends/queues/queues/binheap/round_robin.py
@@ -9,7 +9,7 @@
 def insert_binheap_rr(prog, name, n, flow_infer, queue_size_factor=FACTOR):
     comp = prog.component(name)
 
-    binheap = insert_stable_binheap(prog, "binheap", queue_size_factor)
+    binheap = insert_stable_binheap(prog, f"{name}_binheap", queue_size_factor)
     binheap = comp.cell("binheap", binheap)
 
     flow_infer = comp.cell("flow_infer", flow_infer)
diff --git a/frontends/queues/queues/binheap/stable_binheap.py b/frontends/queues/queues/binheap/stable_binheap.py
index 6864075b74..c090d417b7 100644
--- a/frontends/queues/queues/binheap/stable_binheap.py
+++ b/frontends/queues/queues/binheap/stable_binheap.py
@@ -33,7 +33,7 @@ def insert_stable_binheap(prog, name, queue_len_factor=FACTOR):
 
     comp = prog.component(name)
 
-    heap = insert_binheap(prog, "heap", queue_len_factor, 64, 32)
+    heap = insert_binheap(prog, f"{name}_heap", queue_len_factor, 64, 32)
     below = comp.cell("below", heap)
 
     cmd = comp.input("cmd", 1)
diff --git a/frontends/queues/queues/binheap/strict.py b/frontends/queues/queues/binheap/strict.py
index a1e288c7d4..613bdb5b49 100644
--- a/frontends/queues/queues/binheap/strict.py
+++ b/frontends/queues/queues/binheap/strict.py
@@ -10,7 +10,7 @@
 def insert_binheap_strict(prog, name, n, order, flow_infer, queue_size_factor=FACTOR):
     comp = prog.component(name)
 
-    binheap = insert_stable_binheap(prog, "binheap", queue_size_factor)
+    binheap = insert_stable_binheap(prog, f"{name}_binheap", queue_size_factor)
     binheap = comp.cell("binheap", binheap)
 
     flow_infer = comp.cell("flow_infer", flow_infer)
diff --git a/frontends/queues/queues/flow_inference.py b/frontends/queues/queues/flow_inference.py
index dc3ff07c25..7763df9fcd 100644
--- a/frontends/queues/queues/flow_inference.py
+++ b/frontends/queues/queues/flow_inference.py
@@ -4,16 +4,16 @@
 from calyx.tuple import insert_untuplify
 
 
-def insert_boundary_flow_inference(prog, name, boundaries):
-    n = len(boundaries)
+def insert_boundary_flow_inference(prog, name, boundaries, flow_bits=None):
+    flow_bits = flow_bits or bits_needed(len(boundaries) - 1)
 
     comp = prog.component(name)
 
     value = comp.input("value", 32)
-    flow = comp.reg(bits_needed(n - 1), "flow", is_ref=True)
+    flow = comp.reg(flow_bits, "flow", is_ref=True)
 
     bound_checks = []
-    for b in range(n):
+    for b in range(len(boundaries)):
         lt = comp.lt(32)
         le = comp.le(32)
         guard = comp.and_(1)
@@ -56,7 +56,31 @@ def insert_tuple_flow_inference(prog, name, num_flows):
 
     comp.control += [
         comp.reg_store(flow, untuplify.fst),
-        comp.reg_store(flow, flow.out, "nop"),  # temporary no-op to get it to run
+        comp.reg_store(flow, flow.out, "nop"),  # temporary no-op to compile
+        # question about this on Zulip:
+        # https://calyx.zulipchat.com/#narrow/channel/423433-general/topic/Circular.20Combinational.20Logic/near/479748231
+    ]
+
+    return comp
+
+
+def insert_value_flow_inference(prog, name, num_flows):
+    flow_bits = bits_needed(num_flows - 1)
+
+    comp = prog.component(name)
+
+    untuplify = insert_untuplify(prog, f"{name}_untuplify", 32 - flow_bits, flow_bits)
+    untuplify = comp.cell("untuplify", untuplify)
+
+    value = comp.input("value", 32)
+    flow = comp.reg(flow_bits, "flow", is_ref=True)
+
+    with comp.continuous:
+        untuplify.tup = value
+
+    comp.control += [
+        comp.reg_store(flow, untuplify.snd),
+        comp.reg_store(flow, flow.out, "nop"),  # temporary no-op to compile
         # question about this on Zulip:
         # https://calyx.zulipchat.com/#narrow/channel/423433-general/topic/Circular.20Combinational.20Logic/near/479748231
     ]
diff --git a/frontends/queues/queues/tree.py b/frontends/queues/queues/tree.py
new file mode 100644
index 0000000000..9627c316c7
--- /dev/null
+++ b/frontends/queues/queues/tree.py
@@ -0,0 +1,45 @@
+# pylint: disable=import-error
+import calyx.builder as cb
+from calyx.utils import bits_needed
+
+
+def insert_tree(prog, name, root, children, flow_infer):
+    comp = prog.component(name)
+
+    flow_infer = comp.cell("flow_infer", flow_infer)
+
+    root = comp.cell("root", root)
+    children = [comp.cell(f"child_{i}", child) for i, child in enumerate(children)]
+
+    cmd = comp.input("cmd", 1)
+    value = comp.input("value", 32)
+
+    ans = comp.reg(32, "ans", is_ref=True)
+
+    err = comp.reg(1, "err", is_ref=True)
+    err_eq_0 = comp.eq_use(err.out, 0)
+
+    flow = comp.reg(32, "flow")
+    infer_flow = cb.invoke(flow_infer, in_value=value, ref_flow=flow)
+
+    def invoke_child(child, cmd, value, ans, err):
+        return cb.invoke(child, in_cmd=cmd, in_value=value, ref_ans=ans, ref_err=err)
+
+    recurse = {
+        n: invoke_child(children[n], cmd, value, ans, err) for n in range(len(children))
+    }
+
+    push_logic = [
+        infer_flow,
+        cb.invoke(root, in_cmd=cmd, in_value=flow.out, ref_ans=ans, ref_err=err),
+        cb.if_with(err_eq_0, comp.case(flow.out, recurse)),
+    ]
+
+    pop_logic = [
+        cb.invoke(root, in_cmd=cmd, in_value=flow.out, ref_ans=ans, ref_err=err),
+        cb.if_with(err_eq_0, comp.case(ans.out, recurse)),
+    ]
+
+    comp.control += comp.case(cmd, {0: pop_logic, 1: push_logic})
+
+    return comp


Test patch:
diff --git a/frontends/queues/test_data_gen/gen_test_data.sh b/frontends/queues/test_data_gen/gen_test_data.sh
index 3d01159b3f..284d91510f 100755
--- a/frontends/queues/test_data_gen/gen_test_data.sh
+++ b/frontends/queues/test_data_gen/gen_test_data.sh
@@ -95,6 +95,11 @@ mv $tests_dir/pifo_test.data $tests_dir/binheap/
 mv $tests_dir/pifo_test.expect $tests_dir/binheap/
 [[ $? -eq 0 ]] && echo "Generated binheap/pifo_test.expect"
 
+cp $tests_dir/complex_tree_test.data $tests_dir/binheap/
+[[ $? -eq 0 ]] && echo "Generated binheap/complex_tree_test.data"
+cp $tests_dir/complex_tree_test.expect $tests_dir/binheap/
+[[ $? -eq 0 ]] && echo "Generated binheap/complex_tree_test.expect"
+
 for i in $tests_dir/round_robin/*.data; do
     file="$(basename $i)"
     cp $i $tests_dir/binheap/round_robin/$file
diff --git a/frontends/queues/tests/binheap/complex_tree_test.py b/frontends/queues/tests/binheap/complex_tree_test.py
new file mode 100644
index 0000000000..73d7babb50
--- /dev/null
+++ b/frontends/queues/tests/binheap/complex_tree_test.py
@@ -0,0 +1,45 @@
+# pylint: disable=import-error
+import sys
+import calyx.builder as cb
+import queues.queue_call as qc
+import queues.binheap.round_robin as rr
+import queues.binheap.strict as st
+import queues.tree as tr
+import queues.flow_inference as fi
+
+# This complex tree has the shape rr(strict(A, B, C), rr(D, E, F), strict(G, H))
+
+
+def build():
+    """Top-level function to build the program."""
+    num_cmds = int(sys.argv[1])
+    keepgoing = "--keepgoing" in sys.argv
+    prog = cb.Builder()
+
+    fi_strict1 = fi.insert_boundary_flow_inference(prog, "fi_strict1", [44, 88, 133])
+    pifo_strict1 = st.insert_binheap_strict(
+        prog, "pifo_strict1", 3, [0, 1, 2], fi_strict1
+    )
+
+    fi_rr = fi.insert_boundary_flow_inference(prog, "fi_rr", [177, 221, 266])
+    pifo_rr = rr.insert_binheap_rr(prog, "pifo_rr", 3, fi_rr)
+
+    fi_strict2 = fi.insert_boundary_flow_inference(prog, "fi_strict2", [333, 400])
+    pifo_strict2 = st.insert_binheap_strict(prog, "pifo_strict2", 2, [0, 1], fi_strict2)
+
+    fi_root = fi.insert_value_flow_inference(prog, "fi_root", 3)
+    pifo_root = rr.insert_binheap_rr(prog, "pifo_root", 3, fi_root)
+
+    fi_tree = fi.insert_boundary_flow_inference(
+        prog, "fi_tree", [133, 266, 400], flow_bits=32
+    )
+    pifo_tree = tr.insert_tree(
+        prog, "pifo_tree", pifo_root, [pifo_strict1, pifo_rr, pifo_strict2], fi_tree
+    )
+
+    qc.insert_main(prog, pifo_tree, num_cmds, keepgoing=keepgoing)
+    return prog.program
+
+
+if __name__ == "__main__":
+    build().emit()