nonbinary.computer
OR-1 dataflow CPU sketch
1"""Tests for the Resource allocation pass.
2
3Tests verify:
4- or1-asm.AC6.1: Dyadic instructions are assigned IRAM offsets starting at 0
5- or1-asm.AC6.2: Monadic/SM instructions are assigned IRAM offsets above dyadic range
6- or1-asm.AC6.3: Each function body on a PE gets a distinct context slot
7- or1-asm.AC6.4: All NameRef destinations resolve to ResolvedDest with correct Addr
8- or1-asm.AC6.5: Local edges (same PE) produce Addr with dest PE = source PE
9- or1-asm.AC6.6: Cross-PE edges produce Addr with dest PE = target PE
10- or1-asm.AC6.7: IRAM overflow produces error
11- or1-asm.AC6.8: Context slot overflow produces error
12"""
13
14from asm.allocate import allocate
15from asm.ir import (
16 IRGraph,
17 IRNode,
18 IREdge,
19 SystemConfig,
20 SourceLoc,
21 NameRef,
22 ResolvedDest,
23 CallSite,
24)
25from asm.errors import ErrorCategory, ErrorSeverity
26from cm_inst import ArithOp, MemOp, Port, RoutingOp
27
28
29class TestIRAMPacking:
30 """AC6.1, AC6.2: IRAM offset assignment (dyadic first, then monadic)."""
31
32 def test_mixed_dyadic_and_monadic(self):
33 """PE with 2 dyadic (ADD, SUB) and 2 monadic (INC, CONST)."""
34 nodes = {
35 "&add": IRNode(
36 name="&add",
37 opcode=ArithOp.ADD,
38 pe=0,
39 loc=SourceLoc(1, 1),
40 ),
41 "&sub": IRNode(
42 name="&sub",
43 opcode=ArithOp.SUB,
44 pe=0,
45 loc=SourceLoc(2, 1),
46 ),
47 "&inc": IRNode(
48 name="&inc",
49 opcode=ArithOp.INC,
50 pe=0,
51 loc=SourceLoc(3, 1),
52 ),
53 "&const_1": IRNode(
54 name="&const_1",
55 opcode=ArithOp.ADD, # Using const operand makes it monadic
56 pe=0,
57 const=1,
58 loc=SourceLoc(4, 1),
59 ),
60 }
61 system = SystemConfig(pe_count=1, sm_count=1)
62 graph = IRGraph(nodes, system=system)
63 result = allocate(graph)
64
65 assert len(result.errors) == 0
66
67 # Dyadic nodes should get offsets 0, 1
68 add_node = result.nodes["&add"]
69 sub_node = result.nodes["&sub"]
70 assert add_node.iram_offset == 0
71 assert sub_node.iram_offset == 1
72
73 # Monadic nodes should get offsets starting at 2
74 inc_node = result.nodes["&inc"]
75 const_node = result.nodes["&const_1"]
76 assert const_node.iram_offset == 2
77 assert inc_node.iram_offset == 3
78
79 def test_only_monadic(self):
80 """PE with only monadic instructions."""
81 nodes = {
82 "&inc": IRNode(
83 name="&inc",
84 opcode=ArithOp.INC,
85 pe=0,
86 loc=SourceLoc(1, 1),
87 ),
88 "&dec": IRNode(
89 name="&dec",
90 opcode=ArithOp.DEC,
91 pe=0,
92 loc=SourceLoc(2, 1),
93 ),
94 }
95 system = SystemConfig(pe_count=1, sm_count=1)
96 graph = IRGraph(nodes, system=system)
97 result = allocate(graph)
98
99 assert len(result.errors) == 0
100 inc_node = result.nodes["&inc"]
101 dec_node = result.nodes["&dec"]
102 assert inc_node.iram_offset == 0
103 assert dec_node.iram_offset == 1
104
105 def test_only_dyadic(self):
106 """PE with only dyadic instructions."""
107 nodes = {
108 "&add": IRNode(
109 name="&add",
110 opcode=ArithOp.ADD,
111 pe=0,
112 loc=SourceLoc(1, 1),
113 ),
114 "&sub": IRNode(
115 name="&sub",
116 opcode=ArithOp.SUB,
117 pe=0,
118 loc=SourceLoc(2, 1),
119 ),
120 }
121 system = SystemConfig(pe_count=1, sm_count=1)
122 graph = IRGraph(nodes, system=system)
123 result = allocate(graph)
124
125 assert len(result.errors) == 0
126 add_node = result.nodes["&add"]
127 sub_node = result.nodes["&sub"]
128 assert add_node.iram_offset == 0
129 assert sub_node.iram_offset == 1
130
131
132class TestActivationIDs:
133 """AC5.3: Activation ID assignment per function scope per PE."""
134
135 def test_single_function_scope(self):
136 """PE with nodes from only $main."""
137 nodes = {
138 "$main.&add": IRNode(
139 name="$main.&add",
140 opcode=ArithOp.ADD,
141 pe=0,
142 loc=SourceLoc(1, 1),
143 ),
144 "$main.&sub": IRNode(
145 name="$main.&sub",
146 opcode=ArithOp.SUB,
147 pe=0,
148 loc=SourceLoc(2, 1),
149 ),
150 }
151 system = SystemConfig(pe_count=1, sm_count=1)
152 graph = IRGraph(nodes, system=system)
153 result = allocate(graph)
154
155 assert len(result.errors) == 0
156 add_node = result.nodes["$main.&add"]
157 sub_node = result.nodes["$main.&sub"]
158 # Both should have act_id=0 (same function scope)
159 assert add_node.act_id == 0
160 assert sub_node.act_id == 0
161
162 def test_multiple_function_scopes(self):
163 """PE with nodes from $main and $helper."""
164 nodes = {
165 "$main.&add": IRNode(
166 name="$main.&add",
167 opcode=ArithOp.ADD,
168 pe=0,
169 loc=SourceLoc(1, 1),
170 ),
171 "$main.&sub": IRNode(
172 name="$main.&sub",
173 opcode=ArithOp.SUB,
174 pe=0,
175 loc=SourceLoc(2, 1),
176 ),
177 "$helper.&inc": IRNode(
178 name="$helper.&inc",
179 opcode=ArithOp.INC,
180 pe=0,
181 loc=SourceLoc(3, 1),
182 ),
183 }
184 system = SystemConfig(pe_count=1, sm_count=1)
185 graph = IRGraph(nodes, system=system)
186 result = allocate(graph)
187
188 assert len(result.errors) == 0
189 add_node = result.nodes["$main.&add"]
190 helper_node = result.nodes["$helper.&inc"]
191 # $main should get ctx=0, $helper should get ctx=1
192 assert add_node.act_id == 0
193 assert helper_node.act_id == 1
194
195 def test_toplevel_nodes(self):
196 """Top-level nodes (no function scope) get ctx=0."""
197 nodes = {
198 "&add": IRNode(
199 name="&add",
200 opcode=ArithOp.ADD,
201 pe=0,
202 loc=SourceLoc(1, 1),
203 ),
204 "&sub": IRNode(
205 name="&sub",
206 opcode=ArithOp.SUB,
207 pe=0,
208 loc=SourceLoc(2, 1),
209 ),
210 }
211 system = SystemConfig(pe_count=1, sm_count=1)
212 graph = IRGraph(nodes, system=system)
213 result = allocate(graph)
214
215 assert len(result.errors) == 0
216 add_node = result.nodes["&add"]
217 sub_node = result.nodes["&sub"]
218 assert add_node.act_id == 0
219 assert sub_node.act_id == 0
220
221 def test_multiple_functions_order_preserved(self):
222 """Context slots assigned in order of first appearance."""
223 nodes = {
224 "$fib.&a": IRNode(
225 name="$fib.&a",
226 opcode=ArithOp.ADD,
227 pe=0,
228 loc=SourceLoc(1, 1),
229 ),
230 "$main.&b": IRNode(
231 name="$main.&b",
232 opcode=ArithOp.SUB,
233 pe=0,
234 loc=SourceLoc(2, 1),
235 ),
236 "$helper.&c": IRNode(
237 name="$helper.&c",
238 opcode=ArithOp.INC,
239 pe=0,
240 loc=SourceLoc(3, 1),
241 ),
242 "$fib.&d": IRNode(
243 name="$fib.&d",
244 opcode=ArithOp.DEC,
245 pe=0,
246 loc=SourceLoc(4, 1),
247 ),
248 }
249 system = SystemConfig(pe_count=1, sm_count=1)
250 graph = IRGraph(nodes, system=system)
251 result = allocate(graph)
252
253 assert len(result.errors) == 0
254 a_node = result.nodes["$fib.&a"]
255 b_node = result.nodes["$main.&b"]
256 c_node = result.nodes["$helper.&c"]
257 d_node = result.nodes["$fib.&d"]
258 # First appearance order: $fib (ctx=0), $main (ctx=1), $helper (ctx=2)
259 assert a_node.act_id == 0
260 assert d_node.act_id == 0 # Same function as first
261 assert b_node.act_id == 1
262 assert c_node.act_id == 2
263
264
265class TestDestinationResolution:
266 """AC6.4, AC6.5, AC6.6: NameRef resolution to Addr with local/cross-PE edges."""
267
268 def test_single_dest_l_local_edge(self):
269 """Local edge: dest_l has FrameDest with target_pe matching source PE."""
270 nodes = {
271 "&add": IRNode(
272 name="&add",
273 opcode=ArithOp.ADD,
274 pe=0,
275 dest_l=NameRef(name="&sub", port=Port.L),
276 loc=SourceLoc(1, 1),
277 ),
278 "&sub": IRNode(
279 name="&sub",
280 opcode=ArithOp.SUB,
281 pe=0,
282 loc=SourceLoc(2, 1),
283 ),
284 }
285 edges = [
286 IREdge(source="&add", dest="&sub", port=Port.L, loc=SourceLoc(1, 5))
287 ]
288 system = SystemConfig(pe_count=1, sm_count=1)
289 graph = IRGraph(nodes, edges=edges, system=system)
290 result = allocate(graph)
291
292 assert len(result.errors) == 0
293 add_node = result.nodes["&add"]
294 sub_node = result.nodes["&sub"]
295
296 # dest_l should be resolved with FrameDest
297 assert isinstance(add_node.dest_l, ResolvedDest)
298 assert add_node.dest_l.frame_dest is not None
299 assert add_node.dest_l.frame_dest.offset == sub_node.iram_offset
300 assert add_node.dest_l.frame_dest.target_pe == 0 # Same PE
301 assert add_node.dest_l.frame_dest.act_id == sub_node.act_id
302
303 def test_cross_pe_edge(self):
304 """Cross-PE edge: FrameDest.target_pe = destination PE."""
305 nodes = {
306 "&add": IRNode(
307 name="&add",
308 opcode=ArithOp.ADD,
309 pe=0,
310 dest_l=NameRef(name="&sub", port=Port.L),
311 loc=SourceLoc(1, 1),
312 ),
313 "&sub": IRNode(
314 name="&sub",
315 opcode=ArithOp.SUB,
316 pe=1,
317 loc=SourceLoc(2, 1),
318 ),
319 }
320 edges = [
321 IREdge(source="&add", dest="&sub", port=Port.L, loc=SourceLoc(1, 5))
322 ]
323 system = SystemConfig(pe_count=2, sm_count=1)
324 graph = IRGraph(nodes, edges=edges, system=system)
325 result = allocate(graph)
326
327 assert len(result.errors) == 0
328 add_node = result.nodes["&add"]
329 sub_node = result.nodes["&sub"]
330
331 # dest_l should be resolved with FrameDest for destination PE
332 assert isinstance(add_node.dest_l, ResolvedDest)
333 assert add_node.dest_l.frame_dest is not None
334 assert add_node.dest_l.frame_dest.offset == sub_node.iram_offset
335 assert add_node.dest_l.frame_dest.target_pe == 1 # Destination PE
336
337 def test_dual_destinations_with_source_ports(self):
338 """Dual destinations with source port qualifiers (source_port L and R)."""
339 nodes = {
340 "&branch": IRNode(
341 name="&branch",
342 opcode=ArithOp.ADD,
343 pe=0,
344 dest_l=NameRef(name="&taken", port=Port.L),
345 dest_r=NameRef(name="¬_taken", port=Port.L),
346 loc=SourceLoc(1, 1),
347 ),
348 "&taken": IRNode(
349 name="&taken",
350 opcode=ArithOp.SUB,
351 pe=0,
352 loc=SourceLoc(2, 1),
353 ),
354 "¬_taken": IRNode(
355 name="¬_taken",
356 opcode=ArithOp.INC,
357 pe=0,
358 loc=SourceLoc(3, 1),
359 ),
360 }
361 edges = [
362 IREdge(
363 source="&branch",
364 dest="&taken",
365 port=Port.L,
366 source_port=Port.L,
367 loc=SourceLoc(1, 5),
368 ),
369 IREdge(
370 source="&branch",
371 dest="¬_taken",
372 port=Port.L,
373 source_port=Port.R,
374 loc=SourceLoc(1, 15),
375 ),
376 ]
377 system = SystemConfig(pe_count=1, sm_count=1)
378 graph = IRGraph(nodes, edges=edges, system=system)
379 result = allocate(graph)
380
381 assert len(result.errors) == 0
382 branch_node = result.nodes["&branch"]
383
384 # Both dest_l and dest_r should be resolved
385 assert isinstance(branch_node.dest_l, ResolvedDest)
386 assert isinstance(branch_node.dest_r, ResolvedDest)
387
388 def test_single_implicit_edge_maps_to_dest_l(self):
389 """Single edge without source_port → dest_l."""
390 nodes = {
391 "&a": IRNode(
392 name="&a",
393 opcode=ArithOp.ADD,
394 pe=0,
395 dest_l=NameRef(name="&b", port=Port.L),
396 loc=SourceLoc(1, 1),
397 ),
398 "&b": IRNode(
399 name="&b",
400 opcode=ArithOp.SUB,
401 pe=0,
402 loc=SourceLoc(2, 1),
403 ),
404 }
405 edges = [
406 IREdge(source="&a", dest="&b", port=Port.L, loc=SourceLoc(1, 5))
407 ]
408 system = SystemConfig(pe_count=1, sm_count=1)
409 graph = IRGraph(nodes, edges=edges, system=system)
410 result = allocate(graph)
411
412 assert len(result.errors) == 0
413 a_node = result.nodes["&a"]
414 assert isinstance(a_node.dest_l, ResolvedDest)
415
416
417class TestOverflow:
418 """AC6.7, AC6.8: IRAM and context slot overflow errors."""
419
420 def test_iram_overflow_default_capacity(self):
421 """PE with 65 nodes exceeds default 64 IRAM slots."""
422 nodes = {}
423 for i in range(65):
424 nodes[f"&node_{i}"] = IRNode(
425 name=f"&node_{i}",
426 opcode=ArithOp.ADD,
427 pe=0,
428 loc=SourceLoc(i + 1, 1),
429 )
430 system = SystemConfig(pe_count=1, sm_count=1, iram_capacity=64)
431 graph = IRGraph(nodes, system=system)
432 result = allocate(graph)
433
434 assert len(result.errors) > 0
435 error = result.errors[0]
436 assert error.category == ErrorCategory.RESOURCE
437 assert "IRAM" in error.message or "overflow" in error.message.lower()
438
439 def test_iram_overflow_custom_capacity(self):
440 """PE with 9 nodes exceeds custom IRAM limit of 8."""
441 nodes = {}
442 for i in range(9):
443 nodes[f"&node_{i}"] = IRNode(
444 name=f"&node_{i}",
445 opcode=ArithOp.ADD,
446 pe=0,
447 loc=SourceLoc(i + 1, 1),
448 )
449 system = SystemConfig(pe_count=1, sm_count=1, iram_capacity=8)
450 graph = IRGraph(nodes, system=system)
451 result = allocate(graph)
452
453 assert len(result.errors) > 0
454 error = result.errors[0]
455 assert error.category == ErrorCategory.RESOURCE
456
457 def test_act_id_overflow_default_capacity(self):
458 """PE with 5 function bodies exceeds default 8 frame_count (but uses custom 4)."""
459 nodes = {
460 "$main.&a": IRNode(
461 name="$main.&a",
462 opcode=ArithOp.ADD,
463 pe=0,
464 loc=SourceLoc(1, 1),
465 ),
466 "$fib.&b": IRNode(
467 name="$fib.&b",
468 opcode=ArithOp.SUB,
469 pe=0,
470 loc=SourceLoc(2, 1),
471 ),
472 "$helper.&c": IRNode(
473 name="$helper.&c",
474 opcode=ArithOp.INC,
475 pe=0,
476 loc=SourceLoc(3, 1),
477 ),
478 "$util.&d": IRNode(
479 name="$util.&d",
480 opcode=ArithOp.DEC,
481 pe=0,
482 loc=SourceLoc(4, 1),
483 ),
484 "$extra.&e": IRNode(
485 name="$extra.&e",
486 opcode=ArithOp.ADD,
487 pe=0,
488 loc=SourceLoc(5, 1),
489 ),
490 }
491 system = SystemConfig(pe_count=1, sm_count=1, frame_count=4)
492 graph = IRGraph(nodes, system=system)
493 result = allocate(graph)
494
495 assert len(result.errors) > 0
496 error = result.errors[0]
497 assert error.category == ErrorCategory.FRAME
498 assert "activation" in error.message.lower() or "frame" in error.message.lower()
499
500 def test_act_id_overflow_custom_capacity(self):
501 """PE with 3 function bodies exceeds custom frame_count of 2."""
502 nodes = {
503 "$main.&a": IRNode(
504 name="$main.&a",
505 opcode=ArithOp.ADD,
506 pe=0,
507 loc=SourceLoc(1, 1),
508 ),
509 "$helper.&b": IRNode(
510 name="$helper.&b",
511 opcode=ArithOp.SUB,
512 pe=0,
513 loc=SourceLoc(2, 1),
514 ),
515 "$util.&c": IRNode(
516 name="$util.&c",
517 opcode=ArithOp.INC,
518 pe=0,
519 loc=SourceLoc(3, 1),
520 ),
521 }
522 system = SystemConfig(pe_count=1, sm_count=1, frame_count=2)
523 graph = IRGraph(nodes, system=system)
524 result = allocate(graph)
525
526 assert len(result.errors) > 0
527 error = result.errors[0]
528 assert error.category == ErrorCategory.FRAME
529
530
531class TestMultiplePEs:
532 """Multiple PEs with independent allocation."""
533
534 def test_separate_pe_allocations(self):
535 """Different PEs get independent IRAM offsets."""
536 nodes = {
537 "&a0": IRNode(name="&a0", opcode=ArithOp.ADD, pe=0, loc=SourceLoc(1, 1)),
538 "&b0": IRNode(name="&b0", opcode=ArithOp.SUB, pe=0, loc=SourceLoc(2, 1)),
539 "&a1": IRNode(name="&a1", opcode=ArithOp.ADD, pe=1, loc=SourceLoc(3, 1)),
540 "&b1": IRNode(name="&b1", opcode=ArithOp.SUB, pe=1, loc=SourceLoc(4, 1)),
541 }
542 system = SystemConfig(pe_count=2, sm_count=1)
543 graph = IRGraph(nodes, system=system)
544 result = allocate(graph)
545
546 assert len(result.errors) == 0
547 # Each PE should have its own offset space
548 a0 = result.nodes["&a0"]
549 b0 = result.nodes["&b0"]
550 a1 = result.nodes["&a1"]
551 b1 = result.nodes["&b1"]
552
553 # PE0 nodes start at 0
554 assert a0.iram_offset == 0
555 assert b0.iram_offset == 1
556
557 # PE1 nodes also start at 0
558 assert a1.iram_offset == 0
559 assert b1.iram_offset == 1
560
561
562class TestMemoryOps:
563 """Memory operations (SM instructions) are monadic."""
564
565 def test_read_is_monadic(self):
566 """READ instruction is monadic."""
567 nodes = {
568 "&add": IRNode(
569 name="&add",
570 opcode=ArithOp.ADD,
571 pe=0,
572 loc=SourceLoc(1, 1),
573 ),
574 "&read": IRNode(
575 name="&read",
576 opcode=MemOp.READ,
577 pe=0,
578 loc=SourceLoc(2, 1),
579 ),
580 }
581 system = SystemConfig(pe_count=1, sm_count=1)
582 graph = IRGraph(nodes, system=system)
583 result = allocate(graph)
584
585 assert len(result.errors) == 0
586 add_node = result.nodes["&add"]
587 read_node = result.nodes["&read"]
588 # Dyadic ADD gets offset 0, monadic READ gets offset 1
589 assert add_node.iram_offset == 0
590 assert read_node.iram_offset == 1
591
592 def test_write_with_const_is_monadic(self):
593 """WRITE with const is monadic."""
594 nodes = {
595 "&add": IRNode(
596 name="&add",
597 opcode=ArithOp.ADD,
598 pe=0,
599 loc=SourceLoc(1, 1),
600 ),
601 "&write": IRNode(
602 name="&write",
603 opcode=MemOp.WRITE,
604 const=0x10,
605 pe=0,
606 loc=SourceLoc(2, 1),
607 ),
608 }
609 system = SystemConfig(pe_count=1, sm_count=1)
610 graph = IRGraph(nodes, system=system)
611 result = allocate(graph)
612
613 assert len(result.errors) == 0
614 add_node = result.nodes["&add"]
615 write_node = result.nodes["&write"]
616 # Dyadic ADD gets offset 0, monadic WRITE gets offset 1
617 assert add_node.iram_offset == 0
618 assert write_node.iram_offset == 1
619
620 def test_write_without_const_is_dyadic(self):
621 """WRITE without const is dyadic."""
622 nodes = {
623 "&add": IRNode(
624 name="&add",
625 opcode=ArithOp.ADD,
626 pe=0,
627 loc=SourceLoc(1, 1),
628 ),
629 "&write": IRNode(
630 name="&write",
631 opcode=MemOp.WRITE,
632 const=None,
633 pe=0,
634 loc=SourceLoc(2, 1),
635 ),
636 }
637 system = SystemConfig(pe_count=1, sm_count=1)
638 graph = IRGraph(nodes, system=system)
639 result = allocate(graph)
640
641 assert len(result.errors) == 0
642 add_node = result.nodes["&add"]
643 write_node = result.nodes["&write"]
644 # Both are dyadic, so ADD gets 0, WRITE gets 1
645 assert add_node.iram_offset == 0
646 assert write_node.iram_offset == 1
647
648
649class TestErrorValidation:
650 """Test edge-to-destination validation errors."""
651
652 def test_more_than_two_outgoing_edges(self):
653 """Node with 3+ outgoing edges produces error."""
654 nodes = {
655 "&a": IRNode(
656 name="&a",
657 opcode=ArithOp.ADD,
658 pe=0,
659 dest_l=NameRef(name="&b", port=Port.L),
660 dest_r=NameRef(name="&c", port=Port.L),
661 loc=SourceLoc(1, 1),
662 ),
663 "&b": IRNode(name="&b", opcode=ArithOp.SUB, pe=0, loc=SourceLoc(2, 1)),
664 "&c": IRNode(name="&c", opcode=ArithOp.INC, pe=0, loc=SourceLoc(3, 1)),
665 "&d": IRNode(name="&d", opcode=ArithOp.DEC, pe=0, loc=SourceLoc(4, 1)),
666 }
667 edges = [
668 IREdge(source="&a", dest="&b", port=Port.L, loc=SourceLoc(1, 5)),
669 IREdge(source="&a", dest="&c", port=Port.L, loc=SourceLoc(1, 10)),
670 IREdge(source="&a", dest="&d", port=Port.L, loc=SourceLoc(1, 15)),
671 ]
672 system = SystemConfig(pe_count=1, sm_count=1)
673 graph = IRGraph(nodes, edges=edges, system=system)
674 result = allocate(graph)
675
676 # Should have error about too many edges
677 assert len(result.errors) > 0
678
679 def test_conflicting_source_ports(self):
680 """Two edges with same source_port produces error."""
681 nodes = {
682 "&a": IRNode(
683 name="&a",
684 opcode=ArithOp.ADD,
685 pe=0,
686 dest_l=NameRef(name="&b", port=Port.L),
687 dest_r=NameRef(name="&c", port=Port.L),
688 loc=SourceLoc(1, 1),
689 ),
690 "&b": IRNode(name="&b", opcode=ArithOp.SUB, pe=0, loc=SourceLoc(2, 1)),
691 "&c": IRNode(name="&c", opcode=ArithOp.INC, pe=0, loc=SourceLoc(3, 1)),
692 }
693 edges = [
694 IREdge(source="&a", dest="&b", port=Port.L, source_port=Port.L),
695 IREdge(source="&a", dest="&c", port=Port.L, source_port=Port.L),
696 ]
697 system = SystemConfig(pe_count=1, sm_count=1)
698 graph = IRGraph(nodes, edges=edges, system=system)
699 result = allocate(graph)
700
701 # Should have error about conflicting ports
702 assert len(result.errors) > 0
703
704
705class TestSMReturnRoutes:
706 """SM read instructions use dest_l as return route."""
707
708 def test_read_with_return_address(self):
709 """READ instruction's dest_l is resolved as FrameDest return address."""
710 nodes = {
711 "&read": IRNode(
712 name="&read",
713 opcode=MemOp.READ,
714 pe=0,
715 dest_l=NameRef(name="&next", port=Port.L),
716 loc=SourceLoc(1, 1),
717 ),
718 "&next": IRNode(
719 name="&next",
720 opcode=ArithOp.ADD,
721 pe=0,
722 loc=SourceLoc(2, 1),
723 ),
724 }
725 edges = [
726 IREdge(source="&read", dest="&next", port=Port.L)
727 ]
728 system = SystemConfig(pe_count=1, sm_count=1)
729 graph = IRGraph(nodes, edges=edges, system=system)
730 result = allocate(graph)
731
732 assert len(result.errors) == 0
733 read_node = result.nodes["&read"]
734 next_node = result.nodes["&next"]
735
736 # dest_l should be resolved with FrameDest
737 assert isinstance(read_node.dest_l, ResolvedDest)
738 assert read_node.dest_l.frame_dest is not None
739 assert read_node.dest_l.frame_dest.offset == next_node.iram_offset
740
741
742class TestMacroScopeHandling:
743 """Task 1: Macro scope segments are ignored during context allocation."""
744
745 def test_extract_function_scope_with_macro_segment(self):
746 """Macro segment (#loop_0) is stripped from node name."""
747 from asm.allocate import _extract_function_scope
748
749 # Macro segment in middle of qualified name
750 assert _extract_function_scope("$main.#loop_0.&counter") == "$main"
751
752 def test_extract_function_scope_macro_at_root(self):
753 """Macro at root scope yields empty function scope."""
754 from asm.allocate import _extract_function_scope
755
756 assert _extract_function_scope("#loop_0.&counter") == ""
757
758 def test_extract_function_scope_multiple_macro_segments(self):
759 """Multiple macro segments are all stripped."""
760 from asm.allocate import _extract_function_scope
761
762 assert _extract_function_scope("$func.#outer_1.#inner_2.&label") == "$func"
763
764 def test_extract_function_scope_macro_only(self):
765 """Node with only macro segments yields root scope."""
766 from asm.allocate import _extract_function_scope
767
768 # All segments are macro segments
769 assert _extract_function_scope("#macro1.#macro2") == ""
770
771 def test_macro_scope_nodes_same_ctx_as_function(self):
772 """Nodes with macro scope segments get same ctx as function scope nodes."""
773 nodes = {
774 "$main.&add": IRNode(
775 name="$main.&add",
776 opcode=ArithOp.ADD,
777 pe=0,
778 loc=SourceLoc(1, 1),
779 ),
780 "$main.#loop_0.&counter": IRNode(
781 name="$main.#loop_0.&counter",
782 opcode=ArithOp.INC,
783 pe=0,
784 loc=SourceLoc(2, 1),
785 ),
786 }
787 system = SystemConfig(pe_count=1, sm_count=1)
788 graph = IRGraph(nodes, system=system)
789 result = allocate(graph)
790
791 assert len(result.errors) == 0
792 add_node = result.nodes["$main.&add"]
793 counter_node = result.nodes["$main.#loop_0.&counter"]
794 # Both should have ctx=0 (same function scope, macro segment ignored)
795 assert add_node.act_id == 0
796 assert counter_node.act_id == 0
797
798 def test_macro_scope_distinguishes_from_different_functions(self):
799 """Macro segments don't prevent distinguishing different functions."""
800 nodes = {
801 "$main.#loop_0.&counter": IRNode(
802 name="$main.#loop_0.&counter",
803 opcode=ArithOp.INC,
804 pe=0,
805 loc=SourceLoc(1, 1),
806 ),
807 "$helper.#loop_0.&counter": IRNode(
808 name="$helper.#loop_0.&counter",
809 opcode=ArithOp.DEC,
810 pe=0,
811 loc=SourceLoc(2, 1),
812 ),
813 }
814 system = SystemConfig(pe_count=1, sm_count=1)
815 graph = IRGraph(nodes, system=system)
816 result = allocate(graph)
817
818 assert len(result.errors) == 0
819 main_counter = result.nodes["$main.#loop_0.&counter"]
820 helper_counter = result.nodes["$helper.#loop_0.&counter"]
821 # Different functions get different ctx values
822 assert main_counter.act_id == 0
823 assert helper_counter.act_id == 1
824
825 def test_macro_scope_with_root_and_function(self):
826 """Macro scope at root and function scope get different ctx slots."""
827 nodes = {
828 "#loop_0.&counter": IRNode(
829 name="#loop_0.&counter",
830 opcode=ArithOp.ADD, # dyadic, like $main.&add
831 pe=0,
832 loc=SourceLoc(1, 1),
833 ),
834 "$main.&add": IRNode(
835 name="$main.&add",
836 opcode=ArithOp.SUB, # dyadic
837 pe=0,
838 loc=SourceLoc(2, 1),
839 ),
840 }
841 system = SystemConfig(pe_count=1, sm_count=1)
842 graph = IRGraph(nodes, system=system)
843 result = allocate(graph)
844
845 assert len(result.errors) == 0
846 macro_counter = result.nodes["#loop_0.&counter"]
847 main_add = result.nodes["$main.&add"]
848 # Macro scope at root extracts to "" (root scope)
849 # $main extracts to "$main" (function scope)
850 # First appearance gets ctx=0, next gets ctx=1
851 # macro_counter appears first in the PE's node list after IRAM packing
852 assert macro_counter.act_id == 0 # First scope seen
853 assert main_add.act_id == 1 # Second scope seen
854
855
856class TestPerCallSiteAllocation:
857 """Task 2: Per-call-site context allocation and budget warnings."""
858
859 def test_two_call_sites_to_same_function_get_different_ctx(self):
860 """Two call sites to same function get two distinct ctx values."""
861 nodes = {
862 "&trampoline_1": IRNode(
863 name="&trampoline_1",
864 opcode=RoutingOp.PASS,
865 pe=0,
866 loc=SourceLoc(1, 1),
867 ),
868 "&trampoline_2": IRNode(
869 name="&trampoline_2",
870 opcode=RoutingOp.PASS,
871 pe=0,
872 loc=SourceLoc(2, 1),
873 ),
874 "$func.&add": IRNode(
875 name="$func.&add",
876 opcode=ArithOp.ADD,
877 pe=1,
878 loc=SourceLoc(3, 1),
879 ),
880 "&free_ctx_1": IRNode(
881 name="&free_ctx_1",
882 opcode=RoutingOp.FREE_FRAME,
883 pe=0,
884 loc=SourceLoc(4, 1),
885 ),
886 "&free_ctx_2": IRNode(
887 name="&free_ctx_2",
888 opcode=RoutingOp.FREE_FRAME,
889 pe=0,
890 loc=SourceLoc(5, 1),
891 ),
892 }
893 call_sites = [
894 CallSite(
895 func_name="$func",
896 call_id=1,
897 trampoline_nodes=("&trampoline_1",),
898 free_frame_nodes=("&free_ctx_1",),
899 loc=SourceLoc(1, 1),
900 ),
901 CallSite(
902 func_name="$func",
903 call_id=2,
904 trampoline_nodes=("&trampoline_2",),
905 free_frame_nodes=("&free_ctx_2",),
906 loc=SourceLoc(2, 1),
907 ),
908 ]
909
910 system = SystemConfig(pe_count=2, sm_count=1)
911 graph = IRGraph(nodes, system=system, call_sites=call_sites)
912 result = allocate(graph)
913
914 assert len(result.errors) == 0
915 # Each call site gets its own ctx slot on PE1 (where $func lives)
916 # Trampoline and free_ctx on PE0 should also get the call site's ctx
917 trampoline_1 = result.nodes["&trampoline_1"]
918 trampoline_2 = result.nodes["&trampoline_2"]
919 free_ctx_1 = result.nodes["&free_ctx_1"]
920 free_ctx_2 = result.nodes["&free_ctx_2"]
921 func_node = result.nodes["$func.&add"]
922
923 # Both trampoline nodes should have ctx values assigned (per-call-site)
924 # They should be different
925 assert trampoline_1.act_id is not None
926 assert trampoline_2.act_id is not None
927 assert trampoline_1.act_id != trampoline_2.act_id
928
929 def test_context_overflow_produces_resource_error(self):
930 """Activation ID overflow produces FRAME error with per-PE breakdown."""
931 # Create 20 call sites on PE0 (8 frame_count available by default)
932 nodes = {}
933 call_sites = []
934
935 for i in range(20):
936 node_name = f"&trampoline_{i}"
937 nodes[node_name] = IRNode(
938 name=node_name,
939 opcode=RoutingOp.PASS,
940 pe=0,
941 loc=SourceLoc(i+1, 1),
942 )
943 call_sites.append(CallSite(
944 func_name=f"$func_{i}",
945 call_id=i,
946 trampoline_nodes=(node_name,),
947 free_frame_nodes=(),
948 loc=SourceLoc(i+1, 1),
949 ))
950
951 system = SystemConfig(pe_count=1, sm_count=1, frame_count=8)
952 graph = IRGraph(nodes, system=system, call_sites=call_sites)
953 result = allocate(graph)
954
955 # Should have FRAME errors for activation ID overflow
956 frame_errors = [e for e in result.errors if e.category == ErrorCategory.FRAME]
957 assert len(frame_errors) > 0
958 # Error should mention overflow or exhaustion
959 error_msg = " ".join(e.message for e in frame_errors)
960 assert "overflow" in error_msg.lower() or "exceed" in error_msg.lower() or "exhaustion" in error_msg.lower()
961
962 def test_budget_warning_at_75_percent(self):
963 """Budget warning emitted at 75% utilisation."""
964 # Create 13 call sites on PE0 (16 ctx slots, so 13/16 = 81% > 75%)
965 nodes = {}
966 call_sites = []
967
968 for i in range(13):
969 node_name = f"&trampoline_{i}"
970 nodes[node_name] = IRNode(
971 name=node_name,
972 opcode=RoutingOp.PASS,
973 pe=0,
974 loc=SourceLoc(i+1, 1),
975 )
976 call_sites.append(CallSite(
977 func_name=f"$func_{i}",
978 call_id=i,
979 trampoline_nodes=(node_name,),
980 free_frame_nodes=(),
981 loc=SourceLoc(i+1, 1),
982 ))
983
984 system = SystemConfig(pe_count=1, sm_count=1, frame_count=16)
985 graph = IRGraph(nodes, system=system, call_sites=call_sites)
986 result = allocate(graph)
987
988 # Should succeed but have WARNING errors for budget
989 assert len(result.errors) > 0
990 warnings = [e for e in result.errors if e.severity == ErrorSeverity.WARNING]
991 assert len(warnings) > 0
992 warning_msg = " ".join(w.message for w in warnings)
993 # Check for actual percentage (87% with 14 slots used out of 16)
994 # and "context slots used" pattern
995 assert ("87%" in warning_msg or "context slots used" in warning_msg.lower()) and \
996 ("PE0" in warning_msg or "context" in warning_msg.lower())