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 FROM: namespaces => set ;
24 IN: compiler.cfg.linear-scan.tests
29 ! Live interval calculation
31 ! A value is defined and never used; make sure it has the right
34 T{ ##load-integer f 1 0 }
35 T{ ##replace-imm f D 0 "hi" }
39 : test-live-intervals ( -- )
41 [ cfg set ] [ number-instructions ] [ compute-live-intervals ] tri
55 1 live-intervals get at [ start>> ] [ end>> ] bi
58 ! Live range and interval splitting
60 { T{ live-range f 1 10 } T{ live-range f 15 15 } }
61 { T{ live-range f 16 20 } }
64 T{ live-range f 1 10 }
65 T{ live-range f 15 20 }
70 { T{ live-range f 1 10 } T{ live-range f 15 16 } }
71 { T{ live-range f 17 20 } }
74 T{ live-range f 1 10 }
75 T{ live-range f 15 20 }
80 { T{ live-range f 1 10 } }
81 { T{ live-range f 15 20 } }
84 T{ live-range f 1 10 }
85 T{ live-range f 15 20 }
90 { T{ live-range f 1 10 } T{ live-range f 15 17 } }
91 { T{ live-range f 18 20 } }
94 T{ live-range f 1 10 }
95 T{ live-range f 15 20 }
100 { T{ live-range f 1 10 } } 0 split-ranges
104 { T{ live-range f 0 0 } }
105 { T{ live-range f 1 5 } }
107 { T{ live-range f 0 5 } } 0 split-ranges
110 cfg new 0 >>spill-area-size 4 >>spill-area-align cfg set
117 } representations set
119 : clean-up-split ( a b -- a b )
120 [ dup [ [ >vector ] change-uses [ >vector ] change-ranges ] when ] bi@ ;
125 { reg-class float-regs }
128 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
129 { ranges V{ T{ live-range f 0 2 } } }
130 { spill-to T{ spill-slot f 0 } }
131 { spill-rep float-rep }
135 { reg-class float-regs }
138 { uses V{ T{ vreg-use f 5 f float-rep } } }
139 { ranges V{ T{ live-range f 5 5 } } }
140 { reload-from T{ spill-slot f 0 } }
141 { reload-rep float-rep }
146 { reg-class float-regs }
149 { 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 } } }
150 { ranges V{ T{ live-range f 0 5 } } }
159 { reg-class float-regs }
162 { uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
163 { ranges V{ T{ live-range f 1 5 } } }
164 { reload-from T{ spill-slot f 4 } }
165 { reload-rep float-rep }
170 { reg-class float-regs }
173 { 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 } } }
174 { ranges V{ T{ live-range f 0 5 } } }
182 { reg-class float-regs }
185 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
186 { ranges V{ T{ live-range f 0 2 } } }
187 { spill-to T{ spill-slot f 8 } }
188 { spill-rep float-rep }
194 { reg-class float-regs }
197 { 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 } } }
198 { ranges V{ T{ live-range f 0 5 } } }
206 { reg-class float-regs }
209 { uses V{ T{ vreg-use f 0 float-rep f } } }
210 { ranges V{ T{ live-range f 0 1 } } }
211 { spill-to T{ spill-slot f 12 } }
212 { spill-rep float-rep }
216 { reg-class float-regs }
219 { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
220 { ranges V{ T{ live-range f 20 30 } } }
221 { reload-from T{ spill-slot f 12 } }
222 { reload-rep float-rep }
227 { reg-class float-regs }
230 { 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 } } }
231 { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
236 ! Don't insert reload if first usage is a def
240 { reg-class float-regs }
243 { uses V{ T{ vreg-use f 0 float-rep f } } }
244 { ranges V{ T{ live-range f 0 1 } } }
245 { spill-to T{ spill-slot f 16 } }
246 { spill-rep float-rep }
250 { reg-class float-regs }
253 { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
254 { ranges V{ T{ live-range f 20 30 } } }
259 { reg-class float-regs }
262 { 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 } } }
263 { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
268 ! Multiple representations
272 { reg-class float-regs }
275 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
276 { ranges V{ T{ live-range f 0 11 } } }
277 { spill-to T{ spill-slot f 24 } }
278 { spill-rep double-rep }
282 { reg-class float-regs }
285 { uses V{ T{ vreg-use f 20 f double-rep } } }
286 { ranges V{ T{ live-range f 20 20 } } }
287 { reload-from T{ spill-slot f 24 } }
288 { reload-rep double-rep }
293 { reg-class float-regs }
296 { 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 } } }
297 { ranges V{ T{ live-range f 0 20 } } }
308 { ranges V{ T{ live-range f 8 8 } } }
309 { uses V{ T{ vreg-use f 8 int-rep } } }
310 { reg-class int-regs }
317 { ranges V{ T{ live-range f 4 8 } } }
318 { uses V{ T{ vreg-use f 8 int-rep } } }
319 { reg-class int-regs }
324 ! trim-before-ranges, trim-after-ranges
330 { ranges V{ T{ live-range f 0 3 } } }
331 { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
332 { reg-class int-regs }
333 { spill-to T{ spill-slot f 32 } }
334 { spill-rep int-rep }
340 { ranges V{ T{ live-range f 14 16 } } }
341 { uses V{ T{ vreg-use f 14 f int-rep } } }
342 { reg-class int-regs }
343 { reload-from T{ spill-slot f 32 } }
344 { reload-rep int-rep }
351 { ranges V{ T{ live-range f 0 4 } T{ live-range f 6 10 } T{ live-range f 12 16 } } }
352 { 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 } } }
353 { reg-class int-regs }
362 } representations set
375 { reg-class int-regs }
379 { 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 } } }
383 { reg-class int-regs }
387 { 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 } } }
391 { reg-class int-regs }
395 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
399 } active-intervals set
400 H{ } inactive-intervals set
403 { reg-class int-regs }
406 { uses V{ T{ vreg-use f 5 int-rep f } } }
422 { reg-class int-regs }
426 { uses V{ T{ vreg-use f 1 int-rep f } } }
430 { reg-class int-regs }
434 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
438 } active-intervals set
439 H{ } inactive-intervals set
442 { reg-class int-regs }
445 { uses V{ T{ vreg-use f 5 int-rep f } } }
450 H{ { 1 int-rep } { 2 int-rep } } representations set
456 { reg-class int-regs }
459 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
460 { ranges V{ T{ live-range f 0 100 } } }
463 H{ { int-regs { "A" } } }
471 { reg-class int-regs }
474 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
475 { ranges V{ T{ live-range f 0 10 } } }
479 { reg-class int-regs }
482 { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
483 { ranges V{ T{ live-range f 11 20 } } }
486 H{ { int-regs { "A" } } }
494 { reg-class int-regs }
497 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
498 { ranges V{ T{ live-range f 0 100 } } }
502 { reg-class int-regs }
505 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
506 { ranges V{ T{ live-range f 30 60 } } }
509 H{ { int-regs { "A" } } }
517 { reg-class int-regs }
520 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
521 { ranges V{ T{ live-range f 0 100 } } }
525 { reg-class int-regs }
528 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
529 { ranges V{ T{ live-range f 30 200 } } }
532 H{ { int-regs { "A" } } }
540 { reg-class int-regs }
543 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
544 { ranges V{ T{ live-range f 0 100 } } }
548 { reg-class int-regs }
551 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
552 { ranges V{ T{ live-range f 30 100 } } }
555 H{ { int-regs { "A" } } }
559 ! Problem with spilling intervals with no more usages after the spill location
566 } representations set
572 { reg-class int-regs }
575 { 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 } } }
576 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
580 { reg-class int-regs }
583 { 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 } } }
584 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
588 { reg-class int-regs }
591 { uses V{ T{ vreg-use f 6 int-rep f } } }
592 { ranges V{ T{ live-range f 4 8 } } }
596 { reg-class int-regs }
599 { uses V{ T{ vreg-use f 8 int-rep f } } }
600 { ranges V{ T{ live-range f 4 8 } } }
603 ! This guy will invoke the 'spill partially available' code path
606 { reg-class int-regs }
609 { uses V{ T{ vreg-use f 8 int-rep f } } }
610 { ranges V{ T{ live-range f 4 8 } } }
613 H{ { int-regs { "A" "B" } } }
617 ! Test spill-new code path
623 { reg-class int-regs }
626 { 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 } } }
627 { ranges V{ T{ live-range f 0 10 } } }
630 ! This guy will invoke the 'spill new' code path
633 { reg-class int-regs }
636 { uses V{ T{ vreg-use f 8 int-rep f } } }
637 { ranges V{ T{ live-range f 2 8 } } }
640 H{ { int-regs { "A" } } }
645 T{ live-range f 0 10 }
646 T{ live-range f 20 30 }
651 T{ live-range f 0 10 }
652 T{ live-range f 10 30 }
657 T{ live-range f 0 10 }
658 T{ live-range f 5 30 }
663 T{ live-range f 5 30 }
664 T{ live-range f 0 10 }
669 T{ live-range f 5 10 }
670 T{ live-range f 0 15 }
676 T{ live-range f 0 10 }
677 T{ live-range f 20 30 }
678 T{ live-range f 40 50 }
681 T{ live-range f 11 15 }
682 T{ live-range f 31 35 }
683 T{ live-range f 50 55 }
685 intersect-live-ranges
690 T{ live-range f 0 10 }
691 T{ live-range f 20 30 }
692 T{ live-range f 40 50 }
695 T{ live-range f 11 15 }
696 T{ live-range f 31 36 }
697 T{ live-range f 51 55 }
699 intersect-live-ranges
705 { reg-class int-regs }
708 { ranges V{ T{ live-range f 0 10 } } }
712 { reg-class int-regs }
715 { ranges V{ T{ live-range f 5 10 } } }
717 relevant-ranges intersect-live-ranges
720 ! register-status had problems because it used map>assoc where the sequence
727 } representations set
730 H{ { int-regs { 0 1 } } } registers set
736 { reg-class int-regs }
740 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
741 { uses V{ 0 2 10 20 } }
746 { reg-class int-regs }
750 { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
751 { uses V{ 4 6 30 40 } }
755 } inactive-intervals set
761 { reg-class int-regs }
765 { ranges V{ T{ live-range f 0 40 } } }
770 } active-intervals set
774 { reg-class int-regs }
777 { ranges V{ T{ live-range f 8 10 } } }
778 { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }