1 USING: tools.test random sorting sequences hashtables assocs
2 kernel arrays splitting namespaces math accessors vectors
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.allocation
17 compiler.cfg.linear-scan.allocation.state
18 compiler.cfg.linear-scan.allocation.splitting
19 compiler.cfg.linear-scan.allocation.spilling
20 compiler.cfg.linear-scan.live-intervals
21 compiler.cfg.linear-scan.numbering
22 compiler.cfg.linear-scan.ranges
23 compiler.cfg.linear-scan.debugger
24 compiler.cfg.utilities ;
25 IN: compiler.cfg.linear-scan.tests
30 ! Live interval calculation
31 : test-live-intervals ( -- )
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" }
39 [ cfg set ] [ number-instructions ] [ compute-live-intervals ] tri
53 1 live-intervals get at ranges>> ranges-endpoints
56 ! Live interval splitting
57 { } insns>cfg [ stack-frame>> 4 >>spill-area-align drop ] keep cfg set
66 : clean-up-split ( a b -- a b )
67 [ [ [ >vector ] change-uses [ >vector ] change-ranges ] ?call ] bi@ ;
70 T{ live-interval-state
72 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
73 { ranges V{ { 0 2 } } }
74 { spill-to T{ spill-slot f 0 } }
75 { spill-rep float-rep }
77 T{ live-interval-state
79 { uses V{ T{ vreg-use f 5 f float-rep } } }
80 { ranges V{ { 5 5 } } }
81 { reload-from T{ spill-slot f 0 } }
82 { reload-rep float-rep }
85 T{ live-interval-state
89 T{ vreg-use f 0 float-rep f }
90 T{ vreg-use f 1 f float-rep }
91 T{ vreg-use f 5 f float-rep }
94 { ranges V{ { 0 5 } } }
101 T{ live-interval-state
103 { uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
104 { ranges V{ { 1 5 } } }
105 { reload-from T{ spill-slot f 4 } }
106 { reload-rep float-rep }
109 T{ live-interval-state
113 T{ vreg-use f 0 float-rep f }
114 T{ vreg-use f 1 f float-rep }
115 T{ vreg-use f 5 f float-rep }
118 { ranges V{ { 0 5 } } }
124 T{ live-interval-state
126 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
127 { ranges V{ { 0 2 } } }
128 { spill-to T{ spill-slot f 8 } }
129 { spill-rep float-rep }
133 T{ live-interval-state
137 T{ vreg-use f 0 float-rep f }
138 T{ vreg-use f 1 f float-rep }
139 T{ vreg-use f 5 f float-rep }
142 { ranges V{ { 0 5 } } }
148 T{ live-interval-state
150 { uses V{ T{ vreg-use f 0 float-rep f } } }
151 { ranges V{ { 0 1 } } }
152 { spill-to T{ spill-slot f 12 } }
153 { spill-rep float-rep }
155 T{ live-interval-state
157 { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
158 { ranges V{ { 20 30 } } }
159 { reload-from T{ spill-slot f 12 } }
160 { reload-rep float-rep }
163 T{ live-interval-state
167 T{ vreg-use f 0 float-rep f }
168 T{ vreg-use f 20 f float-rep }
169 T{ vreg-use f 30 f float-rep }
172 { ranges V{ { 0 8 } { 10 18 } { 20 30 } } }
177 ! Don't insert reload if first usage is a def
179 T{ live-interval-state
181 { uses V{ T{ vreg-use f 0 float-rep f } } }
182 { ranges V{ { 0 1 } } }
183 { spill-to T{ spill-slot f 16 } }
184 { spill-rep float-rep }
186 T{ live-interval-state
188 { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
189 { ranges V{ { 20 30 } } }
192 T{ live-interval-state
196 T{ vreg-use f 0 float-rep f }
197 T{ vreg-use f 20 float-rep f }
198 T{ vreg-use f 30 f float-rep }
201 { ranges V{ { 0 8 } { 10 18 } { 20 30 } } }
206 ! Multiple representations
208 T{ live-interval-state
210 { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
211 { ranges V{ { 0 11 } } }
212 { spill-to T{ spill-slot f 24 } }
213 { spill-rep double-rep }
215 T{ live-interval-state
217 { uses V{ T{ vreg-use f 20 f double-rep } } }
218 { ranges V{ { 20 20 } } }
219 { reload-from T{ spill-slot f 24 } }
220 { reload-rep double-rep }
223 T{ live-interval-state
227 T{ vreg-use f 0 float-rep f }
228 T{ vreg-use f 10 double-rep float-rep }
229 T{ vreg-use f 20 f double-rep }
232 { ranges V{ { 0 20 } } }
239 T{ live-interval-state
241 { ranges V{ { 8 8 } } }
242 { uses V{ T{ vreg-use f 8 int-rep } } }
245 T{ live-interval-state
247 { ranges V{ { 4 8 } } }
248 { uses V{ T{ vreg-use f 8 int-rep } } }
253 ! trim-before-ranges, trim-after-ranges
255 T{ live-interval-state
257 { ranges V{ { 0 3 } } }
258 { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
259 { spill-to T{ spill-slot f 32 } }
260 { spill-rep int-rep }
262 T{ live-interval-state
264 { ranges V{ { 14 16 } } }
265 { uses V{ T{ vreg-use f 14 f int-rep } } }
266 { reload-from T{ spill-slot f 32 } }
267 { reload-rep int-rep }
270 T{ live-interval-state
272 { ranges V{ { 0 4 } { 6 10 } { 12 16 } } }
275 T{ vreg-use f 0 f int-rep }
276 T{ vreg-use f 2 f int-rep }
277 T{ vreg-use f 14 f int-rep } }
287 } representations set
298 T{ live-interval-state
301 { ranges V{ { 1 15 } } }
304 T{ vreg-use f 1 int-rep f }
305 T{ vreg-use f 3 f int-rep }
306 T{ vreg-use f 7 f int-rep }
307 T{ vreg-use f 10 f int-rep }
308 T{ vreg-use f 15 f int-rep }
312 T{ live-interval-state
315 { ranges V{ { 3 8 } } }
318 T{ vreg-use f 3 int-rep f }
319 T{ vreg-use f 4 f int-rep }
320 T{ vreg-use f 8 f int-rep }
324 T{ live-interval-state
327 { ranges V{ { 3 10 } } }
328 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
332 } active-intervals set
333 H{ } inactive-intervals set
334 T{ live-interval-state
336 { ranges V{ { 5 5 } } }
337 { uses V{ T{ vreg-use f 5 int-rep f } } }
351 T{ live-interval-state
354 { ranges V{ { 1 15 } } }
355 { uses V{ T{ vreg-use f 1 int-rep f } } }
357 T{ live-interval-state
360 { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
364 } active-intervals set
365 H{ } inactive-intervals set
366 T{ live-interval-state
368 { ranges V{ { 5 5 } } }
369 { uses V{ T{ vreg-use f 5 int-rep f } } }
374 H{ { 1 int-rep } { 2 int-rep } } representations set
378 T{ live-interval-state
380 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
381 { ranges V{ { 0 100 } } }
384 H{ { int-regs { "A" } } }
390 T{ live-interval-state
392 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
393 { ranges V{ { 0 10 } } }
395 T{ live-interval-state
397 { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
398 { ranges V{ { 11 20 } } }
401 H{ { int-regs { "A" } } }
407 T{ live-interval-state
409 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
410 { ranges V{ { 0 100 } } }
412 T{ live-interval-state
414 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
415 { ranges V{ { 30 60 } } }
418 H{ { int-regs { "A" } } }
424 T{ live-interval-state
426 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
427 { ranges V{ { 0 100 } } }
429 T{ live-interval-state
431 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
432 { ranges V{ { 30 200 } } }
435 H{ { int-regs { "A" } } }
441 T{ live-interval-state
443 { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
444 { ranges V{ { 0 100 } } }
446 T{ live-interval-state
448 { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
449 { ranges V{ { 30 100 } } }
452 H{ { int-regs { "A" } } }
456 ! Problem with spilling intervals with no more usages after the spill location
463 } representations set
467 T{ live-interval-state
471 T{ vreg-use f 0 int-rep f }
472 T{ vreg-use f 10 f int-rep }
473 T{ vreg-use f 20 f int-rep }
476 { ranges V{ { 0 2 } { 10 20 } } }
478 T{ live-interval-state
482 T{ vreg-use f 0 int-rep f }
483 T{ vreg-use f 10 f int-rep }
484 T{ vreg-use f 20 f int-rep }
487 { ranges V{ { 0 2 } { 10 20 } } }
489 T{ live-interval-state
491 { uses V{ T{ vreg-use f 6 int-rep f } } }
492 { ranges V{ { 4 8 } } }
494 T{ live-interval-state
496 { uses V{ T{ vreg-use f 8 int-rep f } } }
497 { ranges V{ { 4 8 } } }
500 ! This guy will invoke the 'spill partially available' code path
501 T{ live-interval-state
503 { uses V{ T{ vreg-use f 8 int-rep f } } }
504 { ranges V{ { 4 8 } } }
507 H{ { int-regs { "A" "B" } } }
511 ! Test spill-new code path
515 T{ live-interval-state
517 { 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 } } }
518 { ranges V{ { 0 10 } } }
521 ! This guy will invoke the 'spill new' code path
522 T{ live-interval-state
524 { uses V{ T{ vreg-use f 8 int-rep f } } }
525 { ranges V{ { 2 8 } } }
528 H{ { int-regs { "A" } } }
532 ! register-status had problems because it used map>assoc where the sequence
539 } representations set
545 T{ live-interval-state
548 { ranges V{ { 0 2 } { 10 20 } } }
549 { uses V{ 0 2 10 20 } }
552 T{ live-interval-state
555 { ranges V{ { 4 6 } { 30 40 } } }
556 { uses V{ 4 6 30 40 } }
560 } inactive-intervals set
564 T{ live-interval-state
567 { ranges V{ { 0 40 } } }
572 } active-intervals set
574 T{ live-interval-state
576 { ranges V{ { 8 10 } } }
577 { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
579 H{ { int-regs { 0 1 } } } register-status
583 T{ cfg { frame-pointer? f } } admissible-registers machine-registers =
587 T{ cfg { frame-pointer? t } } admissible-registers
588 int-regs of frame-reg swap member?