1 IN: compiler.cfg.linear-scan.tests
2 USING: tools.test random sorting sequences sets hashtables assocs
3 kernel fry arrays splitting namespaces math accessors vectors locals
4 math.order grouping strings strings.private classes layouts
8 compiler.cfg.instructions
10 compiler.cfg.predecessors
12 compiler.cfg.linearization
15 compiler.cfg.comparisons
16 compiler.cfg.linear-scan
17 compiler.cfg.linear-scan.numbering
18 compiler.cfg.linear-scan.live-intervals
19 compiler.cfg.linear-scan.allocation
20 compiler.cfg.linear-scan.allocation.state
21 compiler.cfg.linear-scan.allocation.splitting
22 compiler.cfg.linear-scan.allocation.spilling
23 compiler.cfg.linear-scan.debugger ;
29 { T{ live-range f 1 10 } T{ live-range f 15 15 } }
30 { T{ live-range f 16 20 } }
33 T{ live-range f 1 10 }
34 T{ live-range f 15 20 }
39 { T{ live-range f 1 10 } T{ live-range f 15 16 } }
40 { T{ live-range f 17 20 } }
43 T{ live-range f 1 10 }
44 T{ live-range f 15 20 }
49 { T{ live-range f 1 10 } }
50 { T{ live-range f 15 20 } }
53 T{ live-range f 1 10 }
54 T{ live-range f 15 20 }
59 { T{ live-range f 1 10 } T{ live-range f 15 17 } }
60 { T{ live-range f 18 20 } }
63 T{ live-range f 1 10 }
64 T{ live-range f 15 20 }
69 { T{ live-range f 1 10 } } 0 split-ranges
73 { T{ live-range f 0 0 } }
74 { T{ live-range f 1 5 } }
76 { T{ live-range f 0 5 } } 0 split-ranges
79 cfg new 0 >>spill-area-size cfg set
83 { 1 single-float-rep }
84 { 2 single-float-rep }
85 { 3 single-float-rep }
94 { ranges V{ T{ live-range f 0 2 } } }
102 { ranges V{ T{ live-range f 5 5 } } }
111 { ranges V{ T{ live-range f 0 5 } } }
121 { ranges V{ T{ live-range f 0 1 } } }
129 { ranges V{ T{ live-range f 1 5 } } }
138 { ranges V{ T{ live-range f 0 5 } } }
148 { ranges V{ T{ live-range f 0 1 } } }
156 { ranges V{ T{ live-range f 20 30 } } }
164 { uses V{ 0 20 30 } }
165 { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
173 } representations set
189 { uses V{ 1 3 7 10 15 } }
207 } active-intervals set
208 H{ } inactive-intervals set
243 } active-intervals set
244 H{ } inactive-intervals set
254 H{ { 1 int-rep } { 2 int-rep } } representations set
263 { ranges V{ T{ live-range f 0 100 } } }
266 H{ { int-regs { "A" } } }
277 { ranges V{ T{ live-range f 0 10 } } }
284 { ranges V{ T{ live-range f 11 20 } } }
287 H{ { int-regs { "A" } } }
298 { ranges V{ T{ live-range f 0 100 } } }
305 { ranges V{ T{ live-range f 30 60 } } }
308 H{ { int-regs { "A" } } }
319 { ranges V{ T{ live-range f 0 100 } } }
326 { ranges V{ T{ live-range f 30 200 } } }
329 H{ { int-regs { "A" } } }
340 { ranges V{ T{ live-range f 0 100 } } }
347 { ranges V{ T{ live-range f 30 100 } } }
350 H{ { int-regs { "A" } } }
354 ! Problem with spilling intervals with no more usages after the spill location
361 } representations set
369 { uses V{ 0 10 20 } }
370 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
376 { uses V{ 0 10 20 } }
377 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
384 { ranges V{ T{ live-range f 4 8 } } }
391 { ranges V{ T{ live-range f 4 8 } } }
394 ! This guy will invoke the 'spill partially available' code path
400 { ranges V{ T{ live-range f 4 8 } } }
403 H{ { int-regs { "A" "B" } } }
407 ! Test spill-new code path
416 { ranges V{ T{ live-range f 0 10 } } }
419 ! This guy will invoke the 'spill new' code path
425 { ranges V{ T{ live-range f 2 8 } } }
428 H{ { int-regs { "A" } } }
433 T{ live-range f 0 10 }
434 T{ live-range f 20 30 }
439 T{ live-range f 0 10 }
440 T{ live-range f 10 30 }
445 T{ live-range f 0 10 }
446 T{ live-range f 5 30 }
451 T{ live-range f 5 30 }
452 T{ live-range f 0 10 }
457 T{ live-range f 5 10 }
458 T{ live-range f 0 15 }
464 T{ live-range f 0 10 }
465 T{ live-range f 20 30 }
466 T{ live-range f 40 50 }
469 T{ live-range f 11 15 }
470 T{ live-range f 31 35 }
471 T{ live-range f 50 55 }
473 intersect-live-ranges
478 T{ live-range f 0 10 }
479 T{ live-range f 20 30 }
480 T{ live-range f 40 50 }
483 T{ live-range f 11 15 }
484 T{ live-range f 31 36 }
485 T{ live-range f 51 55 }
487 intersect-live-ranges
495 { ranges V{ T{ live-range f 0 10 } } }
501 { ranges V{ T{ live-range f 5 10 } } }
503 relevant-ranges intersect-live-ranges
506 ! register-status had problems because it used map>assoc where the sequence
513 } representations set
516 H{ { int-regs { 0 1 } } } registers set
525 { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
526 { uses V{ 0 2 10 20 } }
534 { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
535 { uses V{ 4 6 30 40 } }
539 } inactive-intervals set
548 { ranges V{ T{ live-range f 0 40 } } }
553 } active-intervals set
559 { ranges V{ T{ live-range f 8 10 } } }
565 :: test-linear-scan-on-cfg ( regs -- )
567 cfg new 0 get >>entry
569 dup fake-representations
570 dup { { int-regs regs } } (linear-scan)
571 flatten-cfg 1array mr.
574 ! Bug in live spill slots calculation
576 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
595 T{ ##compare-imm-branch
631 ! Bug in inactive interval handling
632 ! [ rot dup [ -rot ] when ]
633 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
648 T{ ##compare-imm-branch
712 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
714 ! Similar to the above
715 ! [ swap dup [ rot ] when ]
720 { instructions V{ T{ ##prologue } T{ ##branch } } }
732 T{ ##compare-imm-branch
803 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
805 ! compute-live-registers was inaccurate since it didn't take
806 ! lifetime holes into account
808 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
815 T{ ##compare-imm-branch
858 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
860 ! Inactive interval handling: splitting active interval
861 ! if it fits in lifetime hole only partially
863 V{ T{ ##peek f 3 R 1 } T{ ##branch } } 0 test-bb
867 T{ ##compare-imm-branch f 2 5 cc= }
879 T{ ##replace f 1 D 2 }
884 T{ ##replace f 3 R 2 }
885 T{ ##replace f 0 D 0 }
891 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
893 ! Not until splitting is finished
894 ! [ _copy ] [ 3 get instructions>> second class ] unit-test
896 ! Resolve pass; make sure the spilling is done correctly
897 V{ T{ ##peek f 3 R 1 } T{ ##branch } } 0 test-bb
901 T{ ##compare-imm-branch f 2 5 cc= }
909 T{ ##replace f 3 R 1 }
912 T{ ##replace f 1 D 2 }
913 T{ ##replace f 0 D 2 }
918 T{ ##replace f 3 R 2 }
924 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
926 [ _spill ] [ 2 get successors>> first instructions>> first class ] unit-test
928 [ _spill ] [ 3 get instructions>> second class ] unit-test
930 [ f ] [ 3 get instructions>> [ _reload? ] any? ] unit-test
932 [ _reload ] [ 4 get instructions>> first class ] unit-test
941 T{ ##compare-imm-branch f 0 5 cc= }
945 T{ ##replace f 0 D 0 }
948 T{ ##replace f 1 D 0 }
949 T{ ##replace f 2 D 0 }
959 T{ ##compare-imm-branch f 1 5 cc= }
963 T{ ##replace f 0 D 0 }
968 T{ ##replace f 0 D 0 }
978 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
980 [ t ] [ 2 get instructions>> [ _spill? ] any? ] unit-test
982 [ t ] [ 3 get predecessors>> first instructions>> [ _spill? ] any? ] unit-test
984 [ t ] [ 5 get instructions>> [ _reload? ] any? ] unit-test
986 ! A more complicated failure case with resolve that came up after the above
988 V{ T{ ##branch } } 0 test-bb
997 V{ T{ ##branch } } 2 test-bb
998 V{ T{ ##branch } } 3 test-bb
1001 T{ ##replace f 1 D 1 }
1002 T{ ##replace f 2 D 2 }
1003 T{ ##replace f 3 D 3 }
1004 T{ ##replace f 4 D 4 }
1005 T{ ##replace f 0 D 0 }
1008 V{ T{ ##replace f 0 D 0 } T{ ##branch } } 5 test-bb
1009 V{ T{ ##return } } 6 test-bb
1010 V{ T{ ##branch } } 7 test-bb
1012 T{ ##replace f 1 D 1 }
1013 T{ ##replace f 2 D 2 }
1014 T{ ##replace f 3 D 3 }
1019 T{ ##replace f 5 D 1 }
1020 T{ ##replace f 6 D 2 }
1021 T{ ##replace f 7 D 3 }
1022 T{ ##replace f 8 D 4 }
1026 T{ ##replace f 1 D 1 }
1027 T{ ##replace f 2 D 2 }
1028 T{ ##replace f 3 D 3 }
1041 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
1043 [ _spill ] [ 1 get instructions>> second class ] unit-test
1044 [ _reload ] [ 4 get instructions>> 4 swap nth class ] unit-test
1045 [ V{ 3 2 1 } ] [ 8 get instructions>> [ _spill? ] filter [ n>> cell / ] map ] unit-test
1046 [ V{ 3 2 1 } ] [ 9 get instructions>> [ _reload? ] filter [ n>> cell / ] map ] unit-test
1048 ! Resolve pass should insert this
1049 [ _reload ] [ 5 get predecessors>> first instructions>> first class ] unit-test
1055 T{ ##replace f 1 D 1 }
1056 T{ ##replace f 2 D 2 }
1062 V{ T{ ##branch } } 1 test-bb
1067 T{ ##replace f 3 D 3 }
1068 T{ ##replace f 1 D 1 }
1069 T{ ##replace f 2 D 2 }
1070 T{ ##replace f 0 D 3 }
1074 V{ T{ ##branch } } 3 test-bb
1082 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1084 ! Spilling an interval immediately after its activated;
1085 ! and the interval does not have a use at the activation point
1089 T{ ##replace f 1 D 1 }
1090 T{ ##replace f 2 D 2 }
1095 V{ T{ ##branch } } 1 test-bb
1103 T{ ##replace f 1 D 1 }
1105 T{ ##replace f 2 D 2 }
1109 V{ T{ ##branch } } 4 test-bb
1112 T{ ##replace f 0 D 0 }
1122 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1124 ! Reduction of push-all regression, x86-32
1125 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
1128 T{ ##load-immediate { dst 61 } }
1129 T{ ##peek { dst 62 } { loc D 0 } }
1130 T{ ##peek { dst 64 } { loc D 1 } }
1137 T{ ##copy { dst 79 } { src 69 } { rep int-rep } }
1158 T{ ##replace { src 79 } { loc D 3 } }
1159 T{ ##replace { src 62 } { loc D 4 } }
1160 T{ ##replace { src 79 } { loc D 1 } }
1161 T{ ##replace { src 62 } { loc D 2 } }
1162 T{ ##replace { src 61 } { loc D 5 } }
1163 T{ ##replace { src 62 } { loc R 0 } }
1164 T{ ##replace { src 69 } { loc R 1 } }
1165 T{ ##replace { src 97 } { loc D 0 } }
1166 T{ ##call { word resize-array } }
1171 T{ ##peek { dst 98 } { loc R 0 } }
1172 T{ ##peek { dst 100 } { loc D 0 } }
1179 T{ ##peek { dst 108 } { loc D 2 } }
1180 T{ ##peek { dst 110 } { loc D 3 } }
1181 T{ ##peek { dst 112 } { loc D 0 } }
1182 T{ ##peek { dst 114 } { loc D 1 } }
1183 T{ ##peek { dst 116 } { loc D 4 } }
1184 T{ ##peek { dst 119 } { loc R 0 } }
1185 T{ ##copy { dst 109 } { src 108 } { rep int-rep } }
1186 T{ ##copy { dst 111 } { src 110 } { rep int-rep } }
1187 T{ ##copy { dst 113 } { src 112 } { rep int-rep } }
1188 T{ ##copy { dst 115 } { src 114 } { rep int-rep } }
1189 T{ ##copy { dst 117 } { src 116 } { rep int-rep } }
1190 T{ ##copy { dst 120 } { src 119 } { rep int-rep } }
1195 T{ ##copy { dst 109 } { src 62 } { rep int-rep } }
1196 T{ ##copy { dst 111 } { src 61 } { rep int-rep } }
1197 T{ ##copy { dst 113 } { src 62 } { rep int-rep } }
1198 T{ ##copy { dst 115 } { src 79 } { rep int-rep } }
1199 T{ ##copy { dst 117 } { src 64 } { rep int-rep } }
1200 T{ ##copy { dst 120 } { src 69 } { rep int-rep } }
1205 T{ ##replace { src 120 } { loc D 0 } }
1206 T{ ##replace { src 109 } { loc D 3 } }
1207 T{ ##replace { src 111 } { loc D 4 } }
1208 T{ ##replace { src 113 } { loc D 1 } }
1209 T{ ##replace { src 115 } { loc D 2 } }
1210 T{ ##replace { src 117 } { loc D 5 } }
1221 [ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
1223 ! Another reduction of push-all
1224 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
1227 T{ ##peek { dst 85 } { loc D 0 } }
1234 T{ ##peek { dst 91 } { loc D 1 } }
1271 T{ ##load-immediate { dst 129 } { val 24 } }
1272 T{ ##inc-d { n 4 } }
1273 T{ ##inc-r { n 1 } }
1274 T{ ##replace { src 109 } { loc D 2 } }
1275 T{ ##replace { src 85 } { loc D 3 } }
1276 T{ ##replace { src 128 } { loc D 0 } }
1277 T{ ##replace { src 85 } { loc D 1 } }
1278 T{ ##replace { src 89 } { loc D 4 } }
1279 T{ ##replace { src 96 } { loc R 0 } }
1280 T{ ##replace { src 129 } { loc R 0 } }
1285 T{ ##peek { dst 134 } { loc D 1 } }
1292 T{ ##inc-d { n 1 } }
1293 T{ ##inc-r { n 1 } }
1294 T{ ##replace { src 140 } { loc D 0 } }
1295 T{ ##replace { src 134 } { loc R 0 } }
1296 T{ ##call { word resize-array } }
1301 T{ ##peek { dst 141 } { loc R 0 } }
1302 T{ ##peek { dst 143 } { loc D 0 } }
1314 T{ ##inc-d { n -1 } }
1315 T{ ##inc-r { n -1 } }
1316 T{ ##peek { dst 156 } { loc D 2 } }
1317 T{ ##peek { dst 158 } { loc D 3 } }
1318 T{ ##peek { dst 160 } { loc D 0 } }
1319 T{ ##peek { dst 162 } { loc D 1 } }
1320 T{ ##peek { dst 164 } { loc D 4 } }
1321 T{ ##peek { dst 167 } { loc R 0 } }
1322 T{ ##copy { dst 157 } { src 156 } { rep int-rep } }
1323 T{ ##copy { dst 159 } { src 158 } { rep int-rep } }
1324 T{ ##copy { dst 161 } { src 160 } { rep int-rep } }
1325 T{ ##copy { dst 163 } { src 162 } { rep int-rep } }
1326 T{ ##copy { dst 165 } { src 164 } { rep int-rep } }
1327 T{ ##copy { dst 168 } { src 167 } { rep int-rep } }
1332 T{ ##inc-d { n 3 } }
1333 T{ ##inc-r { n 1 } }
1334 T{ ##copy { dst 157 } { src 85 } }
1335 T{ ##copy { dst 159 } { src 89 } }
1336 T{ ##copy { dst 161 } { src 85 } }
1337 T{ ##copy { dst 163 } { src 109 } }
1338 T{ ##copy { dst 165 } { src 91 } }
1339 T{ ##copy { dst 168 } { src 96 } }
1350 T{ ##inc-d { n 1 } }
1351 T{ ##inc-r { n -1 } }
1352 T{ ##replace { src 168 } { loc D 0 } }
1353 T{ ##replace { src 157 } { loc D 3 } }
1354 T{ ##replace { src 159 } { loc D 4 } }
1355 T{ ##replace { src 161 } { loc D 1 } }
1356 T{ ##replace { src 163 } { loc D 2 } }
1357 T{ ##replace { src 165 } { loc D 5 } }
1369 [ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
1371 ! Fencepost error in assignment pass
1372 V{ T{ ##branch } } 0 test-bb
1376 T{ ##compare-imm-branch f 0 5 cc= }
1379 V{ T{ ##branch } } 2 test-bb
1384 T{ ##replace f 1 D 0 }
1385 T{ ##replace f 2 D 0 }
1390 T{ ##replace f 0 D 0 }
1396 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1398 [ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
1400 [ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
1402 [ 1 ] [ 3 get predecessors>> first instructions>> [ _spill? ] count ] unit-test
1404 [ 1 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
1406 ! Another test case for fencepost error in assignment pass
1407 V{ T{ ##branch } } 0 test-bb
1411 T{ ##compare-imm-branch f 0 5 cc= }
1417 T{ ##replace f 1 D 0 }
1418 T{ ##replace f 2 D 0 }
1419 T{ ##replace f 0 D 0 }
1428 T{ ##replace f 0 D 0 }
1434 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1436 [ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
1438 [ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
1440 [ 1 ] [ 2 get instructions>> [ _reload? ] count ] unit-test
1442 [ 0 ] [ 3 get instructions>> [ _spill? ] count ] unit-test
1444 [ 0 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
1449 T{ ##replace f 1 D 1 }
1459 T{ ##replace f 0 D 0 }
1466 [ ] [ { 1 2 3 } test-linear-scan-on-cfg ] unit-test
1468 [ { 3 } ] [ 1 get instructions>> first tagged-values>> ] unit-test
1473 T{ ##compare-imm-branch f 1 5 cc= }
1478 T{ ##replace f 0 D 0 }
1488 [ ] [ { 1 2 3 } test-linear-scan-on-cfg ] unit-test
1490 [ { 3 } ] [ 1 get instructions>> first tagged-values>> ] unit-test