1 USING: tools.test random sorting sequences sets hashtables assocs
2 kernel fry arrays splitting namespaces math accessors vectors locals
3 math.order grouping strings strings.private classes layouts
7 compiler.cfg.instructions
9 compiler.cfg.predecessors
13 compiler.cfg.comparisons
14 compiler.cfg.ssa.destruction.leaders
15 compiler.cfg.linear-scan
16 compiler.cfg.linear-scan.numbering
17 compiler.cfg.linear-scan.live-intervals
18 compiler.cfg.linear-scan.allocation
19 compiler.cfg.linear-scan.allocation.state
20 compiler.cfg.linear-scan.allocation.splitting
21 compiler.cfg.linear-scan.allocation.spilling
22 compiler.cfg.linear-scan.debugger
23 compiler.cfg.utilities ;
24 FROM: namespaces => set ;
25 IN: compiler.cfg.linear-scan.tests
30 ! Live interval calculation
32 ! A value is defined and never used; make sure it has the right
35 T{ ##load-integer f 1 0 }
36 T{ ##replace-imm f D 0 "hi" }
40 : test-live-intervals ( -- )
42 [ cfg set ] [ number-instructions ] [ compute-live-intervals ] tri
56 1 live-intervals get at [ start>> ] [ end>> ] bi
59 ! Live range and interval splitting
61 { T{ live-range f 1 10 } T{ live-range f 15 15 } }
62 { T{ live-range f 16 20 } }
65 T{ live-range f 1 10 }
66 T{ live-range f 15 20 }
71 { T{ live-range f 1 10 } T{ live-range f 15 16 } }
72 { T{ live-range f 17 20 } }
75 T{ live-range f 1 10 }
76 T{ live-range f 15 20 }
81 { T{ live-range f 1 10 } }
82 { T{ live-range f 15 20 } }
85 T{ live-range f 1 10 }
86 T{ live-range f 15 20 }
91 { T{ live-range f 1 10 } T{ live-range f 15 17 } }
92 { T{ live-range f 18 20 } }
95 T{ live-range f 1 10 }
96 T{ live-range f 15 20 }
101 { T{ live-range f 1 10 } } 0 split-ranges
105 { T{ live-range f 0 0 } }
106 { T{ live-range f 1 5 } }
108 { T{ live-range f 0 5 } } 0 split-ranges
111 cfg new 0 >>spill-area-size 4 >>spill-area-align cfg set
118 } representations set
120 : clean-up-split ( a b -- a b )
121 [ dup [ [ >vector ] change-uses [ >vector ] change-ranges ] when ] bi@ ;
124 T{ live-interval-state
126 { reg-class float-regs }
129 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
130 { ranges V{ T{ live-range f 0 2 } } }
131 { spill-to T{ spill-slot f 0 } }
132 { spill-rep float-rep }
134 T{ live-interval-state
136 { reg-class float-regs }
139 { uses V{ T{ vreg-use f 5 f float-rep } } }
140 { ranges V{ T{ live-range f 5 5 } } }
141 { reload-from T{ spill-slot f 0 } }
142 { reload-rep float-rep }
145 T{ live-interval-state
147 { reg-class float-regs }
150 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
151 { ranges V{ T{ live-range f 0 5 } } }
158 T{ live-interval-state
160 { reg-class float-regs }
163 { uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
164 { ranges V{ T{ live-range f 1 5 } } }
165 { reload-from T{ spill-slot f 4 } }
166 { reload-rep float-rep }
169 T{ live-interval-state
171 { reg-class float-regs }
174 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
175 { ranges V{ T{ live-range f 0 5 } } }
181 T{ live-interval-state
183 { reg-class float-regs }
186 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
187 { ranges V{ T{ live-range f 0 2 } } }
188 { spill-to T{ spill-slot f 8 } }
189 { spill-rep float-rep }
193 T{ live-interval-state
195 { reg-class float-regs }
198 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
199 { ranges V{ T{ live-range f 0 5 } } }
205 T{ live-interval-state
207 { reg-class float-regs }
210 { uses V{ T{ vreg-use f 0 float-rep f } } }
211 { ranges V{ T{ live-range f 0 1 } } }
212 { spill-to T{ spill-slot f 12 } }
213 { spill-rep float-rep }
215 T{ live-interval-state
217 { reg-class float-regs }
220 { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
221 { ranges V{ T{ live-range f 20 30 } } }
222 { reload-from T{ spill-slot f 12 } }
223 { reload-rep float-rep }
226 T{ live-interval-state
228 { reg-class float-regs }
231 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
232 { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
237 ! Don't insert reload if first usage is a def
239 T{ live-interval-state
241 { reg-class float-regs }
244 { uses V{ T{ vreg-use f 0 float-rep f } } }
245 { ranges V{ T{ live-range f 0 1 } } }
246 { spill-to T{ spill-slot f 16 } }
247 { spill-rep float-rep }
249 T{ live-interval-state
251 { reg-class float-regs }
254 { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
255 { ranges V{ T{ live-range f 20 30 } } }
258 T{ live-interval-state
260 { reg-class float-regs }
263 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
264 { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
269 ! Multiple representations
271 T{ live-interval-state
273 { reg-class float-regs }
276 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
277 { ranges V{ T{ live-range f 0 11 } } }
278 { spill-to T{ spill-slot f 24 } }
279 { spill-rep double-rep }
281 T{ live-interval-state
283 { reg-class float-regs }
286 { uses V{ T{ vreg-use f 20 f double-rep } } }
287 { ranges V{ T{ live-range f 20 20 } } }
288 { reload-from T{ spill-slot f 24 } }
289 { reload-rep double-rep }
292 T{ live-interval-state
294 { reg-class float-regs }
297 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } T{ vreg-use f 20 f double-rep } } }
298 { ranges V{ T{ live-range f 0 20 } } }
305 T{ live-interval-state
309 { ranges V{ T{ live-range f 8 8 } } }
310 { uses V{ T{ vreg-use f 8 int-rep } } }
311 { reg-class int-regs }
314 T{ live-interval-state
318 { ranges V{ T{ live-range f 4 8 } } }
319 { uses V{ T{ vreg-use f 8 int-rep } } }
320 { reg-class int-regs }
325 ! trim-before-ranges, trim-after-ranges
327 T{ live-interval-state
331 { ranges V{ T{ live-range f 0 3 } } }
332 { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
333 { reg-class int-regs }
334 { spill-to T{ spill-slot f 32 } }
335 { spill-rep int-rep }
337 T{ live-interval-state
341 { ranges V{ T{ live-range f 14 16 } } }
342 { uses V{ T{ vreg-use f 14 f int-rep } } }
343 { reg-class int-regs }
344 { reload-from T{ spill-slot f 32 } }
345 { reload-rep int-rep }
348 T{ live-interval-state
352 { ranges V{ T{ live-range f 0 4 } T{ live-range f 6 10 } T{ live-range f 12 16 } } }
353 { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } T{ vreg-use f 14 f int-rep } } }
354 { reg-class int-regs }
363 } representations set
374 T{ live-interval-state
376 { reg-class int-regs }
380 { uses V{ T{ vreg-use f 1 int-rep f } T{ vreg-use f 3 f int-rep } T{ vreg-use f 7 f int-rep } T{ vreg-use f 10 f int-rep } T{ vreg-use f 15 f int-rep } } }
382 T{ live-interval-state
384 { reg-class int-regs }
388 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 4 f int-rep } T{ vreg-use f 8 f int-rep } } }
390 T{ live-interval-state
392 { reg-class int-regs }
396 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
400 } active-intervals set
401 H{ } inactive-intervals set
402 T{ live-interval-state
404 { reg-class int-regs }
407 { uses V{ T{ vreg-use f 5 int-rep f } } }
421 T{ live-interval-state
423 { reg-class int-regs }
427 { uses V{ T{ vreg-use f 1 int-rep f } } }
429 T{ live-interval-state
431 { reg-class int-regs }
435 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
439 } active-intervals set
440 H{ } inactive-intervals set
441 T{ live-interval-state
443 { reg-class int-regs }
446 { uses V{ T{ vreg-use f 5 int-rep f } } }
451 H{ { 1 int-rep } { 2 int-rep } } representations set
455 T{ live-interval-state
457 { reg-class int-regs }
460 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
461 { ranges V{ T{ live-range f 0 100 } } }
464 H{ { int-regs { "A" } } }
470 T{ live-interval-state
472 { reg-class int-regs }
475 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
476 { ranges V{ T{ live-range f 0 10 } } }
478 T{ live-interval-state
480 { reg-class int-regs }
483 { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
484 { ranges V{ T{ live-range f 11 20 } } }
487 H{ { int-regs { "A" } } }
493 T{ live-interval-state
495 { reg-class int-regs }
498 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
499 { ranges V{ T{ live-range f 0 100 } } }
501 T{ live-interval-state
503 { reg-class int-regs }
506 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
507 { ranges V{ T{ live-range f 30 60 } } }
510 H{ { int-regs { "A" } } }
516 T{ live-interval-state
518 { reg-class int-regs }
521 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
522 { ranges V{ T{ live-range f 0 100 } } }
524 T{ live-interval-state
526 { reg-class int-regs }
529 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
530 { ranges V{ T{ live-range f 30 200 } } }
533 H{ { int-regs { "A" } } }
539 T{ live-interval-state
541 { reg-class int-regs }
544 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
545 { ranges V{ T{ live-range f 0 100 } } }
547 T{ live-interval-state
549 { reg-class int-regs }
552 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
553 { ranges V{ T{ live-range f 30 100 } } }
556 H{ { int-regs { "A" } } }
560 ! Problem with spilling intervals with no more usages after the spill location
567 } representations set
571 T{ live-interval-state
573 { reg-class int-regs }
576 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } T{ vreg-use f 20 f int-rep } } }
577 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
579 T{ live-interval-state
581 { reg-class int-regs }
584 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } T{ vreg-use f 20 f int-rep } } }
585 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
587 T{ live-interval-state
589 { reg-class int-regs }
592 { uses V{ T{ vreg-use f 6 int-rep f } } }
593 { ranges V{ T{ live-range f 4 8 } } }
595 T{ live-interval-state
597 { reg-class int-regs }
600 { uses V{ T{ vreg-use f 8 int-rep f } } }
601 { ranges V{ T{ live-range f 4 8 } } }
604 ! This guy will invoke the 'spill partially available' code path
605 T{ live-interval-state
607 { reg-class int-regs }
610 { uses V{ T{ vreg-use f 8 int-rep f } } }
611 { ranges V{ T{ live-range f 4 8 } } }
614 H{ { int-regs { "A" "B" } } }
618 ! Test spill-new code path
622 T{ live-interval-state
624 { reg-class int-regs }
627 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 6 f int-rep } T{ vreg-use f 10 f int-rep } } }
628 { ranges V{ T{ live-range f 0 10 } } }
631 ! This guy will invoke the 'spill new' code path
632 T{ live-interval-state
634 { reg-class int-regs }
637 { uses V{ T{ vreg-use f 8 int-rep f } } }
638 { ranges V{ T{ live-range f 2 8 } } }
641 H{ { int-regs { "A" } } }
646 T{ live-range f 0 10 }
647 T{ live-range f 20 30 }
652 T{ live-range f 0 10 }
653 T{ live-range f 10 30 }
658 T{ live-range f 0 10 }
659 T{ live-range f 5 30 }
664 T{ live-range f 5 30 }
665 T{ live-range f 0 10 }
670 T{ live-range f 5 10 }
671 T{ live-range f 0 15 }
677 T{ live-range f 0 10 }
678 T{ live-range f 20 30 }
679 T{ live-range f 40 50 }
682 T{ live-range f 11 15 }
683 T{ live-range f 31 35 }
684 T{ live-range f 50 55 }
686 intersect-live-ranges
691 T{ live-range f 0 10 }
692 T{ live-range f 20 30 }
693 T{ live-range f 40 50 }
696 T{ live-range f 11 15 }
697 T{ live-range f 31 36 }
698 T{ live-range f 51 55 }
700 intersect-live-ranges
704 T{ live-interval-state
706 { reg-class int-regs }
709 { ranges V{ T{ live-range f 0 10 } } }
711 T{ live-interval-state
713 { reg-class int-regs }
716 { ranges V{ T{ live-range f 5 10 } } }
718 relevant-ranges intersect-live-ranges
721 ! register-status had problems because it used map>assoc where the sequence
728 } representations set
731 H{ { int-regs { 0 1 } } } registers set
735 T{ live-interval-state
737 { reg-class int-regs }
741 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
742 { uses V{ 0 2 10 20 } }
745 T{ live-interval-state
747 { reg-class int-regs }
751 { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
752 { uses V{ 4 6 30 40 } }
756 } inactive-intervals set
760 T{ live-interval-state
762 { reg-class int-regs }
766 { ranges V{ T{ live-range f 0 40 } } }
771 } active-intervals set
773 T{ live-interval-state
775 { reg-class int-regs }
778 { ranges V{ T{ live-range f 8 10 } } }
779 { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
785 T{ cfg { frame-pointer? f } } admissible-registers machine-registers =
789 T{ cfg { frame-pointer? t } } admissible-registers
790 int-regs of frame-reg swap member?