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 1 }
 149        { uses V{ T{ vreg-use f 0 float-rep f } } }
 150        { ranges V{ T{ live-range f 0 1 } } }
 151        { spill-to T{ spill-slot f 8 } }
 152        { spill-rep float-rep }
 153     }
 154     T{ live-interval
 155        { vreg 3 }
 156        { reg-class float-regs }
 157        { start 20 }
 158        { end 30 }
 159        { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
 160        { ranges V{ T{ live-range f 20 30 } } }
 161        { reload-from T{ spill-slot f 8 } }
 162        { reload-rep float-rep }
 163     }
 164 ] [
 165     T{ live-interval
 166        { vreg 3 }
 167        { reg-class float-regs }
 168        { start 0 }
 169        { end 30 }
 170        { 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 } } }
 171        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
 172     } 10 split-for-spill
 173 ] unit-test
 174
 175 ! Don't insert reload if first usage is a def
 176 [
 177     T{ live-interval
 178        { vreg 4 }
 179        { reg-class float-regs }
 180        { start 0 }
 181        { end 1 }
 182        { uses V{ T{ vreg-use f 0 float-rep f } } }
 183        { ranges V{ T{ live-range f 0 1 } } }
 184        { spill-to T{ spill-slot f 12 } }
 185        { spill-rep float-rep }
 186     }
 187     T{ live-interval
 188        { vreg 4 }
 189        { reg-class float-regs }
 190        { start 20 }
 191        { end 30 }
 192        { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
 193        { ranges V{ T{ live-range f 20 30 } } }
 194     }
 195 ] [
 196     T{ live-interval
 197        { vreg 4 }
 198        { reg-class float-regs }
 199        { start 0 }
 200        { end 30 }
 201        { 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 } } }
 202        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
 203     } 10 split-for-spill
 204 ] unit-test
 205
 206 ! Multiple representations
 207 [
 208     T{ live-interval
 209        { vreg 5 }
 210        { reg-class float-regs }
 211        { start 0 }
 212        { end 11 }
 213        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
 214        { ranges V{ T{ live-range f 0 11 } } }
 215        { spill-to T{ spill-slot f 16 } }
 216        { spill-rep double-rep }
 217     }
 218     T{ live-interval
 219        { vreg 5 }
 220        { reg-class float-regs }
 221        { start 20 }
 222        { end 20 }
 223        { uses V{ T{ vreg-use f 20 f double-rep } } }
 224        { ranges V{ T{ live-range f 20 20 } } }
 225        { reload-from T{ spill-slot f 16 } }
 226        { reload-rep double-rep }
 227     }
 228 ] [
 229     T{ live-interval
 230        { vreg 5 }
 231        { reg-class float-regs }
 232        { start 0 }
 233        { end 20 }
 234        { 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 } } }
 235        { ranges V{ T{ live-range f 0 20 } } }
 236     } 15 split-for-spill
 237 ] unit-test
 238
 239 H{
 240     { 1 int-rep }
 241     { 2 int-rep }
 242     { 3 int-rep }
 243 } representations set
 244
 245 [
 246     {
 247         3
 248         10
 249     }
 250 ] [
 251     H{
 252         { int-regs
 253           V{
 254               T{ live-interval
 255                  { vreg 1 }
 256                  { reg-class int-regs }
 257                  { reg 1 }
 258                  { start 1 }
 259                  { end 15 }
 260                  { 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 } } }
 261               }
 262               T{ live-interval
 263                  { vreg 2 }
 264                  { reg-class int-regs }
 265                  { reg 2 }
 266                  { start 3 }
 267                  { end 8 }
 268                  { 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 } } }
 269               }
 270               T{ live-interval
 271                  { vreg 3 }
 272                  { reg-class int-regs }
 273                  { reg 3 }
 274                  { start 3 }
 275                  { end 10 }
 276                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
 277               }
 278           }
 279         }
 280     } active-intervals set
 281     H{ } inactive-intervals set
 282     T{ live-interval
 283         { vreg 1 }
 284         { reg-class int-regs }
 285         { start 5 }
 286         { end 5 }
 287         { uses V{ T{ vreg-use f 5 int-rep f } } }
 288     }
 289     spill-status
 290 ] unit-test
 291
 292 [
 293     {
 294         1
 295         1/0.
 296     }
 297 ] [
 298     H{
 299         { int-regs
 300           V{
 301               T{ live-interval
 302                  { vreg 1 }
 303                  { reg-class int-regs }
 304                  { reg 1 }
 305                  { start 1 }
 306                  { end 15 }
 307                  { uses V{ T{ vreg-use f 1 int-rep f } } }
 308               }
 309               T{ live-interval
 310                  { vreg 2 }
 311                  { reg-class int-regs }
 312                  { reg 2 }
 313                  { start 3 }
 314                  { end 8 }
 315                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
 316               }
 317           }
 318         }
 319     } active-intervals set
 320     H{ } inactive-intervals set
 321     T{ live-interval
 322         { vreg 3 }
 323         { reg-class int-regs }
 324         { start 5 }
 325         { end 5 }
 326         { uses V{ T{ vreg-use f 5 int-rep f } } }
 327     }
 328     spill-status
 329 ] unit-test
 330
 331 H{ { 1 int-rep } { 2 int-rep } } representations set
 332
 333 [ ] [
 334     {
 335         T{ live-interval
 336            { vreg 1 }
 337            { reg-class int-regs }
 338            { start 0 }
 339            { end 100 }
 340            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 341            { ranges V{ T{ live-range f 0 100 } } }
 342         }
 343     }
 344     H{ { int-regs { "A" } } }
 345     check-linear-scan
 346 ] unit-test
 347
 348 [ ] [
 349     {
 350         T{ live-interval
 351            { vreg 1 }
 352            { reg-class int-regs }
 353            { start 0 }
 354            { end 10 }
 355            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
 356            { ranges V{ T{ live-range f 0 10 } } }
 357         }
 358         T{ live-interval
 359            { vreg 2 }
 360            { reg-class int-regs }
 361            { start 11 }
 362            { end 20 }
 363            { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
 364            { ranges V{ T{ live-range f 11 20 } } }
 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 100 }
 378            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 379            { ranges V{ T{ live-range f 0 100 } } }
 380         }
 381         T{ live-interval
 382            { vreg 2 }
 383            { reg-class int-regs }
 384            { start 30 }
 385            { end 60 }
 386            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
 387            { ranges V{ T{ live-range f 30 60 } } }
 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 200 }
 409            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
 410            { ranges V{ T{ live-range f 30 200 } } }
 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 100 }
 432            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
 433            { ranges V{ T{ live-range f 30 100 } } }
 434         }
 435     }
 436     H{ { int-regs { "A" } } }
 437     check-linear-scan
 438 ] must-fail
 439
 440 ! Problem with spilling intervals with no more usages after the spill location
 441 H{
 442     { 1 int-rep }
 443     { 2 int-rep }
 444     { 3 int-rep }
 445     { 4 int-rep }
 446     { 5 int-rep }
 447 } representations set
 448
 449 [ ] [
 450     {
 451         T{ live-interval
 452            { vreg 1 }
 453            { reg-class int-regs }
 454            { start 0 }
 455            { end 20 }
 456            { 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 } } }
 457            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 458         }
 459         T{ live-interval
 460            { vreg 2 }
 461            { reg-class int-regs }
 462            { start 0 }
 463            { end 20 }
 464            { 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 } } }
 465            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 466         }
 467         T{ live-interval
 468            { vreg 3 }
 469            { reg-class int-regs }
 470            { start 4 }
 471            { end 8 }
 472            { uses V{ T{ vreg-use f 6 int-rep f } } }
 473            { ranges V{ T{ live-range f 4 8 } } }
 474         }
 475         T{ live-interval
 476            { vreg 4 }
 477            { reg-class int-regs }
 478            { start 4 }
 479            { end 8 }
 480            { uses V{ T{ vreg-use f 8 int-rep f } } }
 481            { ranges V{ T{ live-range f 4 8 } } }
 482         }
 483
 484         ! This guy will invoke the 'spill partially available' code path
 485         T{ live-interval
 486            { vreg 5 }
 487            { reg-class int-regs }
 488            { start 4 }
 489            { end 8 }
 490            { uses V{ T{ vreg-use f 8 int-rep f } } }
 491            { ranges V{ T{ live-range f 4 8 } } }
 492         }
 493     }
 494     H{ { int-regs { "A" "B" } } }
 495     check-linear-scan
 496 ] unit-test
 497
 498 ! Test spill-new code path
 499
 500 [ ] [
 501     {
 502         T{ live-interval
 503            { vreg 1 }
 504            { reg-class int-regs }
 505            { start 0 }
 506            { end 10 }
 507            { 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 } } }
 508            { ranges V{ T{ live-range f 0 10 } } }
 509         }
 510
 511         ! This guy will invoke the 'spill new' code path
 512         T{ live-interval
 513            { vreg 5 }
 514            { reg-class int-regs }
 515            { start 2 }
 516            { end 8 }
 517            { uses V{ T{ vreg-use f 8 int-rep f } } }
 518            { ranges V{ T{ live-range f 2 8 } } }
 519         }
 520     }
 521     H{ { int-regs { "A" } } }
 522     check-linear-scan
 523 ] unit-test
 524
 525 [ f ] [
 526     T{ live-range f 0 10 }
 527     T{ live-range f 20 30 }
 528     intersect-live-range
 529 ] unit-test
 530
 531 [ 10 ] [
 532     T{ live-range f 0 10 }
 533     T{ live-range f 10 30 }
 534     intersect-live-range
 535 ] unit-test
 536
 537 [ 5 ] [
 538     T{ live-range f 0 10 }
 539     T{ live-range f 5 30 }
 540     intersect-live-range
 541 ] unit-test
 542
 543 [ 5 ] [
 544     T{ live-range f 5 30 }
 545     T{ live-range f 0 10 }
 546     intersect-live-range
 547 ] unit-test
 548
 549 [ 5 ] [
 550     T{ live-range f 5 10 }
 551     T{ live-range f 0 15 }
 552     intersect-live-range
 553 ] unit-test
 554
 555 [ 50 ] [
 556     {
 557         T{ live-range f 0 10 }
 558         T{ live-range f 20 30 }
 559         T{ live-range f 40 50 }
 560     }
 561     {
 562         T{ live-range f 11 15 }
 563         T{ live-range f 31 35 }
 564         T{ live-range f 50 55 }
 565     }
 566     intersect-live-ranges
 567 ] unit-test
 568
 569 [ f ] [
 570     {
 571         T{ live-range f 0 10 }
 572         T{ live-range f 20 30 }
 573         T{ live-range f 40 50 }
 574     }
 575     {
 576         T{ live-range f 11 15 }
 577         T{ live-range f 31 36 }
 578         T{ live-range f 51 55 }
 579     }
 580     intersect-live-ranges
 581 ] unit-test
 582
 583 [ 5 ] [
 584     T{ live-interval
 585        { start 0 }
 586        { reg-class int-regs }
 587        { end 10 }
 588        { uses { 0 10 } }
 589        { ranges V{ T{ live-range f 0 10 } } }
 590     }
 591     T{ live-interval
 592        { start 5 }
 593        { reg-class int-regs }
 594        { end 10 }
 595        { uses { 5 10 } }
 596        { ranges V{ T{ live-range f 5 10 } } }
 597     }
 598     relevant-ranges intersect-live-ranges
 599 ] unit-test
 600
 601 ! register-status had problems because it used map>assoc where the sequence
 602 ! had multiple keys
 603 H{
 604     { 1 int-rep }
 605     { 2 int-rep }
 606     { 3 int-rep }
 607     { 4 int-rep }
 608 } representations set
 609
 610 [ { 0 10 } ] [
 611     H{ { int-regs { 0 1 } } } registers set
 612     H{
 613         { int-regs
 614           {
 615               T{ live-interval
 616                  { vreg 1 }
 617                  { reg-class int-regs }
 618                  { start 0 }
 619                  { end 20 }
 620                  { reg 0 }
 621                  { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 622                  { uses V{ 0 2 10 20 } }
 623               }
 624
 625               T{ live-interval
 626                  { vreg 2 }
 627                  { reg-class int-regs }
 628                  { start 4 }
 629                  { end 40 }
 630                  { reg 0 }
 631                  { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
 632                  { uses V{ 4 6 30 40 } }
 633               }
 634           }
 635         }
 636     } inactive-intervals set
 637     H{
 638         { int-regs
 639           {
 640               T{ live-interval
 641                  { vreg 3 }
 642                  { reg-class int-regs }
 643                  { start 0 }
 644                  { end 40 }
 645                  { reg 1 }
 646                  { ranges V{ T{ live-range f 0 40 } } }
 647                  { uses V{ 0 40 } }
 648               }
 649           }
 650         }
 651     } active-intervals set
 652
 653     T{ live-interval
 654         { vreg 4 }
 655         { reg-class int-regs }
 656         { start 8 }
 657         { end 10 }
 658         { ranges V{ T{ live-range f 8 10 } } }
 659         { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
 660     }
 661     register-status
 662 ] unit-test