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
11 compiler.cfg.linearization
14 compiler.cfg.comparisons
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
30 { T{ live-range f 1 10 } T{ live-range f 15 15 } }
31 { T{ live-range f 16 20 } }
34 T{ live-range f 1 10 }
35 T{ live-range f 15 20 }
40 { T{ live-range f 1 10 } T{ live-range f 15 16 } }
41 { T{ live-range f 17 20 } }
44 T{ live-range f 1 10 }
45 T{ live-range f 15 20 }
50 { T{ live-range f 1 10 } }
51 { T{ live-range f 15 20 } }
54 T{ live-range f 1 10 }
55 T{ live-range f 15 20 }
60 { T{ live-range f 1 10 } T{ live-range f 15 17 } }
61 { T{ live-range f 18 20 } }
64 T{ live-range f 1 10 }
65 T{ live-range f 15 20 }
70 { T{ live-range f 1 10 } } 0 split-ranges
74 { T{ live-range f 0 0 } }
75 { T{ live-range f 1 5 } }
77 { T{ live-range f 0 5 } } 0 split-ranges
80 cfg new 0 >>spill-area-size cfg set
94 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } } }
95 { ranges V{ T{ live-range f 0 2 } } }
96 { spill-to T{ spill-slot f 0 } }
102 { uses V{ T{ vreg-use f 5 } } }
103 { ranges V{ T{ live-range f 5 5 } } }
104 { reload-from T{ spill-slot f 0 } }
111 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } T{ vreg-use f 5 } } }
112 { ranges V{ T{ live-range f 0 5 } } }
121 { uses V{ T{ vreg-use f 0 } } }
122 { ranges V{ T{ live-range f 0 1 } } }
123 { spill-to T{ spill-slot f 4 } }
129 { uses V{ T{ vreg-use f 1 } T{ vreg-use f 5 } } }
130 { ranges V{ T{ live-range f 1 5 } } }
131 { reload-from T{ spill-slot f 4 } }
138 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 1 } T{ vreg-use f 5 } } }
139 { ranges V{ T{ live-range f 0 5 } } }
148 { uses V{ T{ vreg-use f 0 } } }
149 { ranges V{ T{ live-range f 0 1 } } }
150 { spill-to T{ spill-slot f 8 } }
156 { uses V{ T{ vreg-use f 20 } T{ vreg-use f 30 } } }
157 { ranges V{ T{ live-range f 20 30 } } }
158 { reload-from T{ spill-slot f 8 } }
165 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 20 } T{ vreg-use f 30 } } }
166 { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
174 } representations set
190 { uses V{ T{ vreg-use f 1 } T{ vreg-use f 3 } T{ vreg-use f 7 } T{ vreg-use f 10 } T{ vreg-use f 15 } } }
197 { uses V{ T{ vreg-use f 3 } T{ vreg-use f 4 } T{ vreg-use f 8 } } }
204 { uses V{ T{ vreg-use f 3 } T{ vreg-use f 10 } } }
208 } active-intervals set
209 H{ } inactive-intervals set
214 { uses V{ T{ vreg-use f 5 } } }
233 { uses V{ T{ vreg-use f 1 } } }
240 { uses V{ T{ vreg-use f 3 } T{ vreg-use f 8 } } }
244 } active-intervals set
245 H{ } inactive-intervals set
250 { uses V{ T{ vreg-use f 5 } } }
255 H{ { 1 int-rep } { 2 int-rep } } representations set
263 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
264 { ranges V{ T{ live-range f 0 100 } } }
267 H{ { int-regs { "A" } } }
277 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } } }
278 { ranges V{ T{ live-range f 0 10 } } }
284 { uses V{ T{ vreg-use f 11 } T{ vreg-use f 20 } } }
285 { ranges V{ T{ live-range f 11 20 } } }
288 H{ { int-regs { "A" } } }
298 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
299 { ranges V{ T{ live-range f 0 100 } } }
305 { uses V{ T{ vreg-use f 30 } T{ vreg-use f 60 } } }
306 { ranges V{ T{ live-range f 30 60 } } }
309 H{ { int-regs { "A" } } }
319 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
320 { ranges V{ T{ live-range f 0 100 } } }
326 { uses V{ T{ vreg-use f 30 } T{ vreg-use f 200 } } }
327 { ranges V{ T{ live-range f 30 200 } } }
330 H{ { int-regs { "A" } } }
340 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 100 } } }
341 { ranges V{ T{ live-range f 0 100 } } }
347 { uses V{ T{ vreg-use f 30 } T{ vreg-use f 100 } } }
348 { ranges V{ T{ live-range f 30 100 } } }
351 H{ { int-regs { "A" } } }
355 ! Problem with spilling intervals with no more usages after the spill location
362 } representations set
370 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } T{ vreg-use f 20 } } }
371 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
377 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 10 } T{ vreg-use f 20 } } }
378 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
384 { uses V{ T{ vreg-use f 6 } } }
385 { ranges V{ T{ live-range f 4 8 } } }
391 { uses V{ T{ vreg-use f 8 } } }
392 { ranges V{ T{ live-range f 4 8 } } }
395 ! This guy will invoke the 'spill partially available' code path
400 { uses V{ T{ vreg-use f 8 } } }
401 { ranges V{ T{ live-range f 4 8 } } }
404 H{ { int-regs { "A" "B" } } }
408 ! Test spill-new code path
416 { uses V{ T{ vreg-use f 0 } T{ vreg-use f 6 } T{ vreg-use f 10 } } }
417 { ranges V{ T{ live-range f 0 10 } } }
420 ! This guy will invoke the 'spill new' code path
425 { uses V{ T{ vreg-use f 8 } } }
426 { ranges V{ T{ live-range f 2 8 } } }
429 H{ { int-regs { "A" } } }
434 T{ live-range f 0 10 }
435 T{ live-range f 20 30 }
440 T{ live-range f 0 10 }
441 T{ live-range f 10 30 }
446 T{ live-range f 0 10 }
447 T{ live-range f 5 30 }
452 T{ live-range f 5 30 }
453 T{ live-range f 0 10 }
458 T{ live-range f 5 10 }
459 T{ live-range f 0 15 }
465 T{ live-range f 0 10 }
466 T{ live-range f 20 30 }
467 T{ live-range f 40 50 }
470 T{ live-range f 11 15 }
471 T{ live-range f 31 35 }
472 T{ live-range f 50 55 }
474 intersect-live-ranges
479 T{ live-range f 0 10 }
480 T{ live-range f 20 30 }
481 T{ live-range f 40 50 }
484 T{ live-range f 11 15 }
485 T{ live-range f 31 36 }
486 T{ live-range f 51 55 }
488 intersect-live-ranges
496 { ranges V{ T{ live-range f 0 10 } } }
502 { ranges V{ T{ live-range f 5 10 } } }
504 relevant-ranges intersect-live-ranges
507 ! register-status had problems because it used map>assoc where the sequence
514 } representations set
517 H{ { int-regs { 0 1 } } } registers set
526 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
527 { uses V{ 0 2 10 20 } }
535 { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
536 { uses V{ 4 6 30 40 } }
540 } inactive-intervals set
549 { ranges V{ T{ live-range f 0 40 } } }
554 } active-intervals set
560 { ranges V{ T{ live-range f 8 10 } } }
561 { uses V{ T{ vreg-use f 8 } T{ vreg-use f 10 } } }
566 :: test-linear-scan-on-cfg ( regs -- )
568 cfg new 0 get >>entry
570 dup fake-representations
571 dup { { int-regs regs } } (linear-scan)
572 flatten-cfg 1array mr.
575 ! Bug in live spill slots calculation
577 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
596 T{ ##compare-imm-branch
632 ! Bug in inactive interval handling
633 ! [ rot dup [ -rot ] when ]
634 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
649 T{ ##compare-imm-branch
713 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
715 ! Similar to the above
716 ! [ swap dup [ rot ] when ]
721 { instructions V{ T{ ##prologue } T{ ##branch } } }
733 T{ ##compare-imm-branch
804 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
806 ! compute-live-registers was inaccurate since it didn't take
807 ! lifetime holes into account
809 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
816 T{ ##compare-imm-branch
859 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
861 ! Inactive interval handling: splitting active interval
862 ! if it fits in lifetime hole only partially
864 V{ T{ ##peek f 3 R 1 } T{ ##branch } } 0 test-bb
868 T{ ##compare-imm-branch f 2 5 cc= }
880 T{ ##replace f 1 D 2 }
885 T{ ##replace f 3 R 2 }
886 T{ ##replace f 0 D 0 }
892 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
894 ! Not until splitting is finished
895 ! [ _copy ] [ 3 get instructions>> second class ] unit-test
897 ! Resolve pass; make sure the spilling is done correctly
898 V{ T{ ##peek f 3 R 1 } T{ ##branch } } 0 test-bb
902 T{ ##compare-imm-branch f 2 5 cc= }
910 T{ ##replace f 3 R 1 }
913 T{ ##replace f 1 D 2 }
914 T{ ##replace f 0 D 2 }
919 T{ ##replace f 3 R 2 }
925 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
927 [ _spill ] [ 2 get successors>> first instructions>> first class ] unit-test
929 [ _spill ] [ 3 get instructions>> second class ] unit-test
931 [ f ] [ 3 get instructions>> [ _reload? ] any? ] unit-test
933 [ _reload ] [ 4 get instructions>> first class ] unit-test
942 T{ ##compare-imm-branch f 0 5 cc= }
946 T{ ##replace f 0 D 0 }
949 T{ ##replace f 1 D 0 }
950 T{ ##replace f 2 D 0 }
960 T{ ##compare-imm-branch f 1 5 cc= }
964 T{ ##replace f 0 D 0 }
969 T{ ##replace f 0 D 0 }
979 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
981 [ t ] [ 2 get instructions>> [ _spill? ] any? ] unit-test
983 [ t ] [ 3 get predecessors>> first instructions>> [ _spill? ] any? ] unit-test
985 [ t ] [ 5 get instructions>> [ _reload? ] any? ] unit-test
987 ! A more complicated failure case with resolve that came up after the above
989 V{ T{ ##branch } } 0 test-bb
998 V{ T{ ##branch } } 2 test-bb
999 V{ T{ ##branch } } 3 test-bb
1002 T{ ##replace f 1 D 1 }
1003 T{ ##replace f 2 D 2 }
1004 T{ ##replace f 3 D 3 }
1005 T{ ##replace f 4 D 4 }
1006 T{ ##replace f 0 D 0 }
1009 V{ T{ ##replace f 0 D 0 } T{ ##branch } } 5 test-bb
1010 V{ T{ ##return } } 6 test-bb
1011 V{ T{ ##branch } } 7 test-bb
1013 T{ ##replace f 1 D 1 }
1014 T{ ##replace f 2 D 2 }
1015 T{ ##replace f 3 D 3 }
1020 T{ ##replace f 5 D 1 }
1021 T{ ##replace f 6 D 2 }
1022 T{ ##replace f 7 D 3 }
1023 T{ ##replace f 8 D 4 }
1027 T{ ##replace f 1 D 1 }
1028 T{ ##replace f 2 D 2 }
1029 T{ ##replace f 3 D 3 }
1042 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
1044 [ _spill ] [ 1 get instructions>> second class ] unit-test
1045 [ _reload ] [ 4 get instructions>> 4 swap nth class ] unit-test
1046 [ V{ 3 2 1 } ] [ 8 get instructions>> [ _spill? ] filter [ dst>> n>> cell / ] map ] unit-test
1047 [ V{ 3 2 1 } ] [ 9 get instructions>> [ _reload? ] filter [ src>> n>> cell / ] map ] unit-test
1049 ! Resolve pass should insert this
1050 [ _reload ] [ 5 get predecessors>> first instructions>> first class ] unit-test
1056 T{ ##replace f 1 D 1 }
1057 T{ ##replace f 2 D 2 }
1063 V{ T{ ##branch } } 1 test-bb
1068 T{ ##replace f 3 D 3 }
1069 T{ ##replace f 1 D 1 }
1070 T{ ##replace f 2 D 2 }
1071 T{ ##replace f 0 D 3 }
1075 V{ T{ ##branch } } 3 test-bb
1083 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1085 ! Spilling an interval immediately after its activated;
1086 ! and the interval does not have a use at the activation point
1090 T{ ##replace f 1 D 1 }
1091 T{ ##replace f 2 D 2 }
1096 V{ T{ ##branch } } 1 test-bb
1104 T{ ##replace f 1 D 1 }
1106 T{ ##replace f 2 D 2 }
1110 V{ T{ ##branch } } 4 test-bb
1113 T{ ##replace f 0 D 0 }
1123 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1125 ! Reduction of push-all regression, x86-32
1126 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
1129 T{ ##load-integer { dst 61 } }
1130 T{ ##peek { dst 62 } { loc D 0 } }
1131 T{ ##peek { dst 64 } { loc D 1 } }
1138 T{ ##copy { dst 79 } { src 69 } { rep int-rep } }
1159 T{ ##replace { src 79 } { loc D 3 } }
1160 T{ ##replace { src 62 } { loc D 4 } }
1161 T{ ##replace { src 79 } { loc D 1 } }
1162 T{ ##replace { src 62 } { loc D 2 } }
1163 T{ ##replace { src 61 } { loc D 5 } }
1164 T{ ##replace { src 62 } { loc R 0 } }
1165 T{ ##replace { src 69 } { loc R 1 } }
1166 T{ ##replace { src 97 } { loc D 0 } }
1167 T{ ##call { word resize-array } }
1172 T{ ##peek { dst 98 } { loc R 0 } }
1173 T{ ##peek { dst 100 } { loc D 0 } }
1180 T{ ##peek { dst 108 } { loc D 2 } }
1181 T{ ##peek { dst 110 } { loc D 3 } }
1182 T{ ##peek { dst 112 } { loc D 0 } }
1183 T{ ##peek { dst 114 } { loc D 1 } }
1184 T{ ##peek { dst 116 } { loc D 4 } }
1185 T{ ##peek { dst 119 } { loc R 0 } }
1186 T{ ##copy { dst 109 } { src 108 } { rep int-rep } }
1187 T{ ##copy { dst 111 } { src 110 } { rep int-rep } }
1188 T{ ##copy { dst 113 } { src 112 } { rep int-rep } }
1189 T{ ##copy { dst 115 } { src 114 } { rep int-rep } }
1190 T{ ##copy { dst 117 } { src 116 } { rep int-rep } }
1191 T{ ##copy { dst 120 } { src 119 } { rep int-rep } }
1196 T{ ##copy { dst 109 } { src 62 } { rep int-rep } }
1197 T{ ##copy { dst 111 } { src 61 } { rep int-rep } }
1198 T{ ##copy { dst 113 } { src 62 } { rep int-rep } }
1199 T{ ##copy { dst 115 } { src 79 } { rep int-rep } }
1200 T{ ##copy { dst 117 } { src 64 } { rep int-rep } }
1201 T{ ##copy { dst 120 } { src 69 } { rep int-rep } }
1206 T{ ##replace { src 120 } { loc D 0 } }
1207 T{ ##replace { src 109 } { loc D 3 } }
1208 T{ ##replace { src 111 } { loc D 4 } }
1209 T{ ##replace { src 113 } { loc D 1 } }
1210 T{ ##replace { src 115 } { loc D 2 } }
1211 T{ ##replace { src 117 } { loc D 5 } }
1222 [ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
1224 ! Another reduction of push-all
1225 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
1228 T{ ##peek { dst 85 } { loc D 0 } }
1235 T{ ##peek { dst 91 } { loc D 1 } }
1272 T{ ##load-integer { dst 129 } { val 24 } }
1273 T{ ##inc-d { n 4 } }
1274 T{ ##inc-r { n 1 } }
1275 T{ ##replace { src 109 } { loc D 2 } }
1276 T{ ##replace { src 85 } { loc D 3 } }
1277 T{ ##replace { src 128 } { loc D 0 } }
1278 T{ ##replace { src 85 } { loc D 1 } }
1279 T{ ##replace { src 89 } { loc D 4 } }
1280 T{ ##replace { src 96 } { loc R 0 } }
1281 T{ ##replace { src 129 } { loc R 0 } }
1286 T{ ##peek { dst 134 } { loc D 1 } }
1293 T{ ##inc-d { n 1 } }
1294 T{ ##inc-r { n 1 } }
1295 T{ ##replace { src 140 } { loc D 0 } }
1296 T{ ##replace { src 134 } { loc R 0 } }
1297 T{ ##call { word resize-array } }
1302 T{ ##peek { dst 141 } { loc R 0 } }
1303 T{ ##peek { dst 143 } { loc D 0 } }
1310 T{ ##write-barrier-imm
1316 T{ ##inc-d { n -1 } }
1317 T{ ##inc-r { n -1 } }
1318 T{ ##peek { dst 156 } { loc D 2 } }
1319 T{ ##peek { dst 158 } { loc D 3 } }
1320 T{ ##peek { dst 160 } { loc D 0 } }
1321 T{ ##peek { dst 162 } { loc D 1 } }
1322 T{ ##peek { dst 164 } { loc D 4 } }
1323 T{ ##peek { dst 167 } { loc R 0 } }
1324 T{ ##copy { dst 157 } { src 156 } { rep int-rep } }
1325 T{ ##copy { dst 159 } { src 158 } { rep int-rep } }
1326 T{ ##copy { dst 161 } { src 160 } { rep int-rep } }
1327 T{ ##copy { dst 163 } { src 162 } { rep int-rep } }
1328 T{ ##copy { dst 165 } { src 164 } { rep int-rep } }
1329 T{ ##copy { dst 168 } { src 167 } { rep int-rep } }
1334 T{ ##inc-d { n 3 } }
1335 T{ ##inc-r { n 1 } }
1336 T{ ##copy { dst 157 } { src 85 } }
1337 T{ ##copy { dst 159 } { src 89 } }
1338 T{ ##copy { dst 161 } { src 85 } }
1339 T{ ##copy { dst 163 } { src 109 } }
1340 T{ ##copy { dst 165 } { src 91 } }
1341 T{ ##copy { dst 168 } { src 96 } }
1352 T{ ##inc-d { n 1 } }
1353 T{ ##inc-r { n -1 } }
1354 T{ ##replace { src 168 } { loc D 0 } }
1355 T{ ##replace { src 157 } { loc D 3 } }
1356 T{ ##replace { src 159 } { loc D 4 } }
1357 T{ ##replace { src 161 } { loc D 1 } }
1358 T{ ##replace { src 163 } { loc D 2 } }
1359 T{ ##replace { src 165 } { loc D 5 } }
1371 [ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
1373 ! Fencepost error in assignment pass
1374 V{ T{ ##branch } } 0 test-bb
1378 T{ ##compare-imm-branch f 0 5 cc= }
1381 V{ T{ ##branch } } 2 test-bb
1386 T{ ##replace f 1 D 0 }
1387 T{ ##replace f 2 D 0 }
1392 T{ ##replace f 0 D 0 }
1398 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1400 [ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
1402 [ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
1404 [ 1 ] [ 3 get predecessors>> first instructions>> [ _spill? ] count ] unit-test
1406 [ 1 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
1408 ! Another test case for fencepost error in assignment pass
1409 V{ T{ ##branch } } 0 test-bb
1413 T{ ##compare-imm-branch f 0 5 cc= }
1419 T{ ##replace f 1 D 0 }
1420 T{ ##replace f 2 D 0 }
1421 T{ ##replace f 0 D 0 }
1430 T{ ##replace f 0 D 0 }
1436 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1438 [ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
1440 [ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
1442 [ 1 ] [ 2 get instructions>> [ _reload? ] count ] unit-test
1444 [ 0 ] [ 3 get instructions>> [ _spill? ] count ] unit-test
1446 [ 0 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
1451 T{ ##replace f 1 D 1 }
1461 T{ ##replace f 0 D 0 }
1468 [ ] [ { 1 2 3 } test-linear-scan-on-cfg ] unit-test
1470 [ { { 0 1 } } ] [ 1 get instructions>> first tagged-values>> ] unit-test
1475 T{ ##compare-imm-branch f 1 5 cc= }
1480 T{ ##replace f 0 D 0 }
1490 [ ] [ { 1 2 3 } test-linear-scan-on-cfg ] unit-test
1492 [ { { 0 1 } } ] [ 1 get instructions>> first tagged-values>> ] unit-test