basis/compiler/cfg/linear-scan/linear-scan-tests.factor

   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
   4 cpu.architecture
   5 compiler.cfg
   6 compiler.cfg.optimizer
   7 compiler.cfg.instructions
   8 compiler.cfg.registers
   9 compiler.cfg.predecessors
  10 compiler.cfg.rpo
  11 compiler.cfg.debugger
  12 compiler.cfg.def-use
  13 compiler.cfg.comparisons
  14 compiler.cfg.linear-scan
  15 compiler.cfg.linear-scan.numbering
  16 compiler.cfg.linear-scan.live-intervals
  17 compiler.cfg.linear-scan.allocation
  18 compiler.cfg.linear-scan.allocation.state
  19 compiler.cfg.linear-scan.allocation.splitting
  20 compiler.cfg.linear-scan.allocation.spilling
  21 compiler.cfg.linear-scan.debugger ;
  22 FROM: namespaces => set ;
  23 IN: compiler.cfg.linear-scan.tests
  24
  25 check-allocation? on
  26 check-numbering? on
  27
  28 [
  29     { T{ live-range f 1 10 } T{ live-range f 15 15 } }
  30     { T{ live-range f 16 20 } }
  31 ] [
  32     {
  33         T{ live-range f 1 10 }
  34         T{ live-range f 15 20 }
  35     } 15 split-ranges
  36 ] unit-test
  37
  38 [
  39     { T{ live-range f 1 10 } T{ live-range f 15 16 } }
  40     { T{ live-range f 17 20 } }
  41 ] [
  42     {
  43         T{ live-range f 1 10 }
  44         T{ live-range f 15 20 }
  45     } 16 split-ranges
  46 ] unit-test
  47
  48 [
  49     { T{ live-range f 1 10 } }
  50     { T{ live-range f 15 20 } }
  51 ] [
  52     {
  53         T{ live-range f 1 10 }
  54         T{ live-range f 15 20 }
  55     } 12 split-ranges
  56 ] unit-test
  57
  58 [
  59     { T{ live-range f 1 10 } T{ live-range f 15 17 } }
  60     { T{ live-range f 18 20 } }
  61 ] [
  62     {
  63         T{ live-range f 1 10 }
  64         T{ live-range f 15 20 }
  65     } 17 split-ranges
  66 ] unit-test
  67
  68 [
  69     { T{ live-range f 1 10 } } 0 split-ranges
  70 ] must-fail
  71
  72 [
  73     { T{ live-range f 0 0 } }
  74     { T{ live-range f 1 5 } }
  75 ] [
  76     { T{ live-range f 0 5 } } 0 split-ranges
  77 ] unit-test
  78
  79 cfg new 0 >>spill-area-size cfg set
  80 H{ } spill-slots set
  81
  82 H{
  83     { 1 float-rep }
  84     { 2 float-rep }
  85     { 3 float-rep }
  86 } representations set
  87
  88 [
  89     T{ live-interval
  90        { vreg 1 }
  91        { reg-class float-regs }
  92        { start 0 }
  93        { end 2 }
  94        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
  95        { ranges V{ T{ live-range f 0 2 } } }
  96        { spill-to T{ spill-slot f 0 } }
  97        { spill-rep float-rep }
  98     }
  99     T{ live-interval
 100        { vreg 1 }
 101        { reg-class float-regs }
 102        { start 5 }
 103        { end 5 }
 104        { uses V{ T{ vreg-use f 5 f float-rep } } }
 105        { ranges V{ T{ live-range f 5 5 } } }
 106        { reload-from T{ spill-slot f 0 } }
 107        { reload-rep float-rep }
 108     }
 109 ] [
 110     T{ live-interval
 111        { vreg 1 }
 112        { reg-class float-regs }
 113        { start 0 }
 114        { end 5 }
 115        { 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 } } }
 116        { ranges V{ T{ live-range f 0 5 } } }
 117     } 2 split-for-spill
 118 ] unit-test
 119
 120 [
 121     f
 122     T{ live-interval
 123        { vreg 2 }
 124        { reg-class float-regs }
 125        { start 1 }
 126        { end 5 }
 127        { uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
 128        { ranges V{ T{ live-range f 1 5 } } }
 129        { reload-from T{ spill-slot f 4 } }
 130        { reload-rep float-rep }
 131     }
 132 ] [
 133     T{ live-interval
 134        { vreg 2 }
 135        { reg-class float-regs }
 136        { start 0 }
 137        { end 5 }
 138        { 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 } } }
 139        { ranges V{ T{ live-range f 0 5 } } }
 140     } 0 split-for-spill
 141 ] unit-test
 142
 143 [
 144     T{ live-interval
 145        { vreg 3 }
 146        { reg-class float-regs }
 147        { start 0 }
 148        { end 2 }
 149        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
 150        { ranges V{ T{ live-range f 0 2 } } }
 151        { spill-to T{ spill-slot f 8 } }
 152        { spill-rep float-rep }
 153     }
 154     f
 155 ] [
 156     T{ live-interval
 157        { vreg 3 }
 158        { reg-class float-regs }
 159        { start 0 }
 160        { end 5 }
 161        { 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 } } }
 162        { ranges V{ T{ live-range f 0 5 } } }
 163     } 5 split-for-spill
 164 ] unit-test
 165
 166 [
 167     T{ live-interval
 168        { vreg 4 }
 169        { reg-class float-regs }
 170        { start 0 }
 171        { end 1 }
 172        { uses V{ T{ vreg-use f 0 float-rep f } } }
 173        { ranges V{ T{ live-range f 0 1 } } }
 174        { spill-to T{ spill-slot f 12 } }
 175        { spill-rep float-rep }
 176     }
 177     T{ live-interval
 178        { vreg 4 }
 179        { reg-class float-regs }
 180        { start 20 }
 181        { end 30 }
 182        { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
 183        { ranges V{ T{ live-range f 20 30 } } }
 184        { reload-from T{ spill-slot f 12 } }
 185        { reload-rep float-rep }
 186     }
 187 ] [
 188     T{ live-interval
 189        { vreg 4 }
 190        { reg-class float-regs }
 191        { start 0 }
 192        { end 30 }
 193        { 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 } } }
 194        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
 195     } 10 split-for-spill
 196 ] unit-test
 197
 198 ! Don't insert reload if first usage is a def
 199 [
 200     T{ live-interval
 201        { vreg 5 }
 202        { reg-class float-regs }
 203        { start 0 }
 204        { end 1 }
 205        { uses V{ T{ vreg-use f 0 float-rep f } } }
 206        { ranges V{ T{ live-range f 0 1 } } }
 207        { spill-to T{ spill-slot f 16 } }
 208        { spill-rep float-rep }
 209     }
 210     T{ live-interval
 211        { vreg 5 }
 212        { reg-class float-regs }
 213        { start 20 }
 214        { end 30 }
 215        { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
 216        { ranges V{ T{ live-range f 20 30 } } }
 217     }
 218 ] [
 219     T{ live-interval
 220        { vreg 5 }
 221        { reg-class float-regs }
 222        { start 0 }
 223        { end 30 }
 224        { 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 } } }
 225        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
 226     } 10 split-for-spill
 227 ] unit-test
 228
 229 ! Multiple representations
 230 [
 231     T{ live-interval
 232        { vreg 6 }
 233        { reg-class float-regs }
 234        { start 0 }
 235        { end 11 }
 236        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
 237        { ranges V{ T{ live-range f 0 11 } } }
 238        { spill-to T{ spill-slot f 24 } }
 239        { spill-rep double-rep }
 240     }
 241     T{ live-interval
 242        { vreg 6 }
 243        { reg-class float-regs }
 244        { start 20 }
 245        { end 20 }
 246        { uses V{ T{ vreg-use f 20 f double-rep } } }
 247        { ranges V{ T{ live-range f 20 20 } } }
 248        { reload-from T{ spill-slot f 24 } }
 249        { reload-rep double-rep }
 250     }
 251 ] [
 252     T{ live-interval
 253        { vreg 6 }
 254        { reg-class float-regs }
 255        { start 0 }
 256        { end 20 }
 257        { 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 } } }
 258        { ranges V{ T{ live-range f 0 20 } } }
 259     } 15 split-for-spill
 260 ] unit-test
 261
 262 H{
 263     { 1 int-rep }
 264     { 2 int-rep }
 265     { 3 int-rep }
 266 } representations set
 267
 268 [
 269     {
 270         3
 271         10
 272     }
 273 ] [
 274     H{
 275         { int-regs
 276           V{
 277               T{ live-interval
 278                  { vreg 1 }
 279                  { reg-class int-regs }
 280                  { reg 1 }
 281                  { start 1 }
 282                  { end 15 }
 283                  { 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 } } }
 284               }
 285               T{ live-interval
 286                  { vreg 2 }
 287                  { reg-class int-regs }
 288                  { reg 2 }
 289                  { start 3 }
 290                  { end 8 }
 291                  { 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 } } }
 292               }
 293               T{ live-interval
 294                  { vreg 3 }
 295                  { reg-class int-regs }
 296                  { reg 3 }
 297                  { start 3 }
 298                  { end 10 }
 299                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
 300               }
 301           }
 302         }
 303     } active-intervals set
 304     H{ } inactive-intervals set
 305     T{ live-interval
 306         { vreg 1 }
 307         { reg-class int-regs }
 308         { start 5 }
 309         { end 5 }
 310         { uses V{ T{ vreg-use f 5 int-rep f } } }
 311     }
 312     spill-status
 313 ] unit-test
 314
 315 [
 316     {
 317         1
 318         1/0.
 319     }
 320 ] [
 321     H{
 322         { int-regs
 323           V{
 324               T{ live-interval
 325                  { vreg 1 }
 326                  { reg-class int-regs }
 327                  { reg 1 }
 328                  { start 1 }
 329                  { end 15 }
 330                  { uses V{ T{ vreg-use f 1 int-rep f } } }
 331               }
 332               T{ live-interval
 333                  { vreg 2 }
 334                  { reg-class int-regs }
 335                  { reg 2 }
 336                  { start 3 }
 337                  { end 8 }
 338                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
 339               }
 340           }
 341         }
 342     } active-intervals set
 343     H{ } inactive-intervals set
 344     T{ live-interval
 345         { vreg 3 }
 346         { reg-class int-regs }
 347         { start 5 }
 348         { end 5 }
 349         { uses V{ T{ vreg-use f 5 int-rep f } } }
 350     }
 351     spill-status
 352 ] unit-test
 353
 354 H{ { 1 int-rep } { 2 int-rep } } representations set
 355
 356 [ ] [
 357     {
 358         T{ live-interval
 359            { vreg 1 }
 360            { reg-class int-regs }
 361            { start 0 }
 362            { end 100 }
 363            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 364            { ranges V{ T{ live-range f 0 100 } } }
 365         }
 366     }
 367     H{ { int-regs { "A" } } }
 368     check-linear-scan
 369 ] unit-test
 370
 371 [ ] [
 372     {
 373         T{ live-interval
 374            { vreg 1 }
 375            { reg-class int-regs }
 376            { start 0 }
 377            { end 10 }
 378            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
 379            { ranges V{ T{ live-range f 0 10 } } }
 380         }
 381         T{ live-interval
 382            { vreg 2 }
 383            { reg-class int-regs }
 384            { start 11 }
 385            { end 20 }
 386            { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
 387            { ranges V{ T{ live-range f 11 20 } } }
 388         }
 389     }
 390     H{ { int-regs { "A" } } }
 391     check-linear-scan
 392 ] unit-test
 393
 394 [ ] [
 395     {
 396         T{ live-interval
 397            { vreg 1 }
 398            { reg-class int-regs }
 399            { start 0 }
 400            { end 100 }
 401            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 402            { ranges V{ T{ live-range f 0 100 } } }
 403         }
 404         T{ live-interval
 405            { vreg 2 }
 406            { reg-class int-regs }
 407            { start 30 }
 408            { end 60 }
 409            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
 410            { ranges V{ T{ live-range f 30 60 } } }
 411         }
 412     }
 413     H{ { int-regs { "A" } } }
 414     check-linear-scan
 415 ] unit-test
 416
 417 [ ] [
 418     {
 419         T{ live-interval
 420            { vreg 1 }
 421            { reg-class int-regs }
 422            { start 0 }
 423            { end 100 }
 424            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 425            { ranges V{ T{ live-range f 0 100 } } }
 426         }
 427         T{ live-interval
 428            { vreg 2 }
 429            { reg-class int-regs }
 430            { start 30 }
 431            { end 200 }
 432            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
 433            { ranges V{ T{ live-range f 30 200 } } }
 434         }
 435     }
 436     H{ { int-regs { "A" } } }
 437     check-linear-scan
 438 ] unit-test
 439
 440 [
 441     {
 442         T{ live-interval
 443            { vreg 1 }
 444            { reg-class int-regs }
 445            { start 0 }
 446            { end 100 }
 447            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 448            { ranges V{ T{ live-range f 0 100 } } }
 449         }
 450         T{ live-interval
 451            { vreg 2 }
 452            { reg-class int-regs }
 453            { start 30 }
 454            { end 100 }
 455            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
 456            { ranges V{ T{ live-range f 30 100 } } }
 457         }
 458     }
 459     H{ { int-regs { "A" } } }
 460     check-linear-scan
 461 ] must-fail
 462
 463 ! Problem with spilling intervals with no more usages after the spill location
 464 H{
 465     { 1 int-rep }
 466     { 2 int-rep }
 467     { 3 int-rep }
 468     { 4 int-rep }
 469     { 5 int-rep }
 470 } representations set
 471
 472 [ ] [
 473     {
 474         T{ live-interval
 475            { vreg 1 }
 476            { reg-class int-regs }
 477            { start 0 }
 478            { end 20 }
 479            { 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 } } }
 480            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 481         }
 482         T{ live-interval
 483            { vreg 2 }
 484            { reg-class int-regs }
 485            { start 0 }
 486            { end 20 }
 487            { 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 } } }
 488            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 489         }
 490         T{ live-interval
 491            { vreg 3 }
 492            { reg-class int-regs }
 493            { start 4 }
 494            { end 8 }
 495            { uses V{ T{ vreg-use f 6 int-rep f } } }
 496            { ranges V{ T{ live-range f 4 8 } } }
 497         }
 498         T{ live-interval
 499            { vreg 4 }
 500            { reg-class int-regs }
 501            { start 4 }
 502            { end 8 }
 503            { uses V{ T{ vreg-use f 8 int-rep f } } }
 504            { ranges V{ T{ live-range f 4 8 } } }
 505         }
 506
 507         ! This guy will invoke the 'spill partially available' code path
 508         T{ live-interval
 509            { vreg 5 }
 510            { reg-class int-regs }
 511            { start 4 }
 512            { end 8 }
 513            { uses V{ T{ vreg-use f 8 int-rep f } } }
 514            { ranges V{ T{ live-range f 4 8 } } }
 515         }
 516     }
 517     H{ { int-regs { "A" "B" } } }
 518     check-linear-scan
 519 ] unit-test
 520
 521 ! Test spill-new code path
 522
 523 [ ] [
 524     {
 525         T{ live-interval
 526            { vreg 1 }
 527            { reg-class int-regs }
 528            { start 0 }
 529            { end 10 }
 530            { 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 } } }
 531            { ranges V{ T{ live-range f 0 10 } } }
 532         }
 533
 534         ! This guy will invoke the 'spill new' code path
 535         T{ live-interval
 536            { vreg 5 }
 537            { reg-class int-regs }
 538            { start 2 }
 539            { end 8 }
 540            { uses V{ T{ vreg-use f 8 int-rep f } } }
 541            { ranges V{ T{ live-range f 2 8 } } }
 542         }
 543     }
 544     H{ { int-regs { "A" } } }
 545     check-linear-scan
 546 ] unit-test
 547
 548 [ f ] [
 549     T{ live-range f 0 10 }
 550     T{ live-range f 20 30 }
 551     intersect-live-range
 552 ] unit-test
 553
 554 [ 10 ] [
 555     T{ live-range f 0 10 }
 556     T{ live-range f 10 30 }
 557     intersect-live-range
 558 ] unit-test
 559
 560 [ 5 ] [
 561     T{ live-range f 0 10 }
 562     T{ live-range f 5 30 }
 563     intersect-live-range
 564 ] unit-test
 565
 566 [ 5 ] [
 567     T{ live-range f 5 30 }
 568     T{ live-range f 0 10 }
 569     intersect-live-range
 570 ] unit-test
 571
 572 [ 5 ] [
 573     T{ live-range f 5 10 }
 574     T{ live-range f 0 15 }
 575     intersect-live-range
 576 ] unit-test
 577
 578 [ 50 ] [
 579     {
 580         T{ live-range f 0 10 }
 581         T{ live-range f 20 30 }
 582         T{ live-range f 40 50 }
 583     }
 584     {
 585         T{ live-range f 11 15 }
 586         T{ live-range f 31 35 }
 587         T{ live-range f 50 55 }
 588     }
 589     intersect-live-ranges
 590 ] unit-test
 591
 592 [ f ] [
 593     {
 594         T{ live-range f 0 10 }
 595         T{ live-range f 20 30 }
 596         T{ live-range f 40 50 }
 597     }
 598     {
 599         T{ live-range f 11 15 }
 600         T{ live-range f 31 36 }
 601         T{ live-range f 51 55 }
 602     }
 603     intersect-live-ranges
 604 ] unit-test
 605
 606 [ 5 ] [
 607     T{ live-interval
 608        { start 0 }
 609        { reg-class int-regs }
 610        { end 10 }
 611        { uses { 0 10 } }
 612        { ranges V{ T{ live-range f 0 10 } } }
 613     }
 614     T{ live-interval
 615        { start 5 }
 616        { reg-class int-regs }
 617        { end 10 }
 618        { uses { 5 10 } }
 619        { ranges V{ T{ live-range f 5 10 } } }
 620     }
 621     relevant-ranges intersect-live-ranges
 622 ] unit-test
 623
 624 ! register-status had problems because it used map>assoc where the sequence
 625 ! had multiple keys
 626 H{
 627     { 1 int-rep }
 628     { 2 int-rep }
 629     { 3 int-rep }
 630     { 4 int-rep }
 631 } representations set
 632
 633 [ { 0 10 } ] [
 634     H{ { int-regs { 0 1 } } } registers set
 635     H{
 636         { int-regs
 637           {
 638               T{ live-interval
 639                  { vreg 1 }
 640                  { reg-class int-regs }
 641                  { start 0 }
 642                  { end 20 }
 643                  { reg 0 }
 644                  { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 645                  { uses V{ 0 2 10 20 } }
 646               }
 647
 648               T{ live-interval
 649                  { vreg 2 }
 650                  { reg-class int-regs }
 651                  { start 4 }
 652                  { end 40 }
 653                  { reg 0 }
 654                  { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
 655                  { uses V{ 4 6 30 40 } }
 656               }
 657           }
 658         }
 659     } inactive-intervals set
 660     H{
 661         { int-regs
 662           {
 663               T{ live-interval
 664                  { vreg 3 }
 665                  { reg-class int-regs }
 666                  { start 0 }
 667                  { end 40 }
 668                  { reg 1 }
 669                  { ranges V{ T{ live-range f 0 40 } } }
 670                  { uses V{ 0 40 } }
 671               }
 672           }
 673         }
 674     } active-intervals set
 675
 676     T{ live-interval
 677         { vreg 4 }
 678         { reg-class int-regs }
 679         { start 8 }
 680         { end 10 }
 681         { ranges V{ T{ live-range f 8 10 } } }
 682         { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
 683     }
 684     register-status
 685 ] unit-test