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.linearization
  12 compiler.cfg.debugger
  13 compiler.cfg.def-use
  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
  25
  26 check-allocation? on
  27 check-numbering? on
  28
  29 [
  30     { T{ live-range f 1 10 } T{ live-range f 15 15 } }
  31     { T{ live-range f 16 20 } }
  32 ] [
  33     {
  34         T{ live-range f 1 10 }
  35         T{ live-range f 15 20 }
  36     } 15 split-ranges
  37 ] unit-test
  38
  39 [
  40     { T{ live-range f 1 10 } T{ live-range f 15 16 } }
  41     { T{ live-range f 17 20 } }
  42 ] [
  43     {
  44         T{ live-range f 1 10 }
  45         T{ live-range f 15 20 }
  46     } 16 split-ranges
  47 ] unit-test
  48
  49 [
  50     { T{ live-range f 1 10 } }
  51     { T{ live-range f 15 20 } }
  52 ] [
  53     {
  54         T{ live-range f 1 10 }
  55         T{ live-range f 15 20 }
  56     } 12 split-ranges
  57 ] unit-test
  58
  59 [
  60     { T{ live-range f 1 10 } T{ live-range f 15 17 } }
  61     { T{ live-range f 18 20 } }
  62 ] [
  63     {
  64         T{ live-range f 1 10 }
  65         T{ live-range f 15 20 }
  66     } 17 split-ranges
  67 ] unit-test
  68
  69 [
  70     { T{ live-range f 1 10 } } 0 split-ranges
  71 ] must-fail
  72
  73 [
  74     { T{ live-range f 0 0 } }
  75     { T{ live-range f 1 5 } }
  76 ] [
  77     { T{ live-range f 0 5 } } 0 split-ranges
  78 ] unit-test
  79
  80 cfg new 0 >>spill-area-size cfg set
  81 H{ } spill-slots set
  82
  83 H{
  84     { 1 float-rep }
  85     { 2 float-rep }
  86     { 3 float-rep }
  87 } representations set
  88
  89 [
  90     T{ live-interval
  91        { vreg 1 }
  92        { start 0 }
  93        { end 2 }
  94        { uses V{ 0 1 } }
  95        { ranges V{ T{ live-range f 0 2 } } }
  96        { spill-to T{ spill-slot f 0 } }
  97     }
  98     T{ live-interval
  99        { vreg 1 }
 100        { start 5 }
 101        { end 5 }
 102        { uses V{ 5 } }
 103        { ranges V{ T{ live-range f 5 5 } } }
 104        { reload-from T{ spill-slot f 0 } }
 105     }
 106 ] [
 107     T{ live-interval
 108        { vreg 1 }
 109        { start 0 }
 110        { end 5 }
 111        { uses V{ 0 1 5 } }
 112        { ranges V{ T{ live-range f 0 5 } } }
 113     } 2 split-for-spill
 114 ] unit-test
 115
 116 [
 117     T{ live-interval
 118        { vreg 2 }
 119        { start 0 }
 120        { end 1 }
 121        { uses V{ 0 } }
 122        { ranges V{ T{ live-range f 0 1 } } }
 123        { spill-to T{ spill-slot f 4 } }
 124     }
 125     T{ live-interval
 126        { vreg 2 }
 127        { start 1 }
 128        { end 5 }
 129        { uses V{ 1 5 } }
 130        { ranges V{ T{ live-range f 1 5 } } }
 131        { reload-from T{ spill-slot f 4 } }
 132     }
 133 ] [
 134     T{ live-interval
 135        { vreg 2 }
 136        { start 0 }
 137        { end 5 }
 138        { uses V{ 0 1 5 } }
 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        { start 0 }
 147        { end 1 }
 148        { uses V{ 0 } }
 149        { ranges V{ T{ live-range f 0 1 } } }
 150        { spill-to T{ spill-slot f 8 } }
 151     }
 152     T{ live-interval
 153        { vreg 3 }
 154        { start 20 }
 155        { end 30 }
 156        { uses V{ 20 30 } }
 157        { ranges V{ T{ live-range f 20 30 } } }
 158        { reload-from T{ spill-slot f 8 } }
 159     }
 160 ] [
 161     T{ live-interval
 162        { vreg 3 }
 163        { start 0 }
 164        { end 30 }
 165        { uses V{ 0 20 30 } }
 166        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 20 30 } } }
 167     } 10 split-for-spill
 168 ] unit-test
 169
 170 H{
 171     { 1 int-rep }
 172     { 2 int-rep }
 173     { 3 int-rep }
 174 } representations set
 175
 176 [
 177     {
 178         3
 179         10
 180     }
 181 ] [
 182     H{
 183         { int-regs
 184           V{
 185               T{ live-interval
 186                  { vreg 1 }
 187                  { reg 1 }
 188                  { start 1 }
 189                  { end 15 }
 190                  { uses V{ 1 3 7 10 15 } }
 191               }
 192               T{ live-interval
 193                  { vreg 2 }
 194                  { reg 2 }
 195                  { start 3 }
 196                  { end 8 }
 197                  { uses V{ 3 4 8 } }
 198               }
 199               T{ live-interval
 200                  { vreg 3 }
 201                  { reg 3 }
 202                  { start 3 }
 203                  { end 10 }
 204                  { uses V{ 3 10 } }
 205               }
 206           }
 207         }
 208     } active-intervals set
 209     H{ } inactive-intervals set
 210     T{ live-interval
 211         { vreg 1 }
 212         { start 5 }
 213         { end 5 }
 214         { uses V{ 5 } }
 215     }
 216     spill-status
 217 ] unit-test
 218
 219 [
 220     {
 221         1
 222         1/0.
 223     }
 224 ] [
 225     H{
 226         { int-regs
 227           V{
 228               T{ live-interval
 229                  { vreg 1 }
 230                  { reg 1 }
 231                  { start 1 }
 232                  { end 15 }
 233                  { uses V{ 1 } }
 234               }
 235               T{ live-interval
 236                  { vreg 2 }
 237                  { reg 2 }
 238                  { start 3 }
 239                  { end 8 }
 240                  { uses V{ 3 8 } }
 241               }
 242           }
 243         }
 244     } active-intervals set
 245     H{ } inactive-intervals set
 246     T{ live-interval
 247         { vreg 3 }
 248         { start 5 }
 249         { end 5 }
 250         { uses V{ 5 } }
 251     }
 252     spill-status
 253 ] unit-test
 254
 255 H{ { 1 int-rep } { 2 int-rep } } representations set
 256
 257 [ ] [
 258     {
 259         T{ live-interval
 260            { vreg 1 }
 261            { start 0 }
 262            { end 100 }
 263            { uses V{ 0 100 } }
 264            { ranges V{ T{ live-range f 0 100 } } }
 265         }
 266     }
 267     H{ { int-regs { "A" } } }
 268     check-linear-scan
 269 ] unit-test
 270
 271 [ ] [
 272     {
 273         T{ live-interval
 274            { vreg 1 }
 275            { start 0 }
 276            { end 10 }
 277            { uses V{ 0 10 } }
 278            { ranges V{ T{ live-range f 0 10 } } }
 279         }
 280         T{ live-interval
 281            { vreg 2 }
 282            { start 11 }
 283            { end 20 }
 284            { uses V{ 11 20 } }
 285            { ranges V{ T{ live-range f 11 20 } } }
 286         }
 287     }
 288     H{ { int-regs { "A" } } }
 289     check-linear-scan
 290 ] unit-test
 291
 292 [ ] [
 293     {
 294         T{ live-interval
 295            { vreg 1 }
 296            { start 0 }
 297            { end 100 }
 298            { uses V{ 0 100 } }
 299            { ranges V{ T{ live-range f 0 100 } } }
 300         }
 301         T{ live-interval
 302            { vreg 2 }
 303            { start 30 }
 304            { end 60 }
 305            { uses V{ 30 60 } }
 306            { ranges V{ T{ live-range f 30 60 } } }
 307         }
 308     }
 309     H{ { int-regs { "A" } } }
 310     check-linear-scan
 311 ] unit-test
 312
 313 [ ] [
 314     {
 315         T{ live-interval
 316            { vreg 1 }
 317            { start 0 }
 318            { end 100 }
 319            { uses V{ 0 100 } }
 320            { ranges V{ T{ live-range f 0 100 } } }
 321         }
 322         T{ live-interval
 323            { vreg 2 }
 324            { start 30 }
 325            { end 200 }
 326            { uses V{ 30 200 } }
 327            { ranges V{ T{ live-range f 30 200 } } }
 328         }
 329     }
 330     H{ { int-regs { "A" } } }
 331     check-linear-scan
 332 ] unit-test
 333
 334 [
 335     {
 336         T{ live-interval
 337            { vreg 1 }
 338            { start 0 }
 339            { end 100 }
 340            { uses V{ 0 100 } }
 341            { ranges V{ T{ live-range f 0 100 } } }
 342         }
 343         T{ live-interval
 344            { vreg 2 }
 345            { start 30 }
 346            { end 100 }
 347            { uses V{ 30 100 } }
 348            { ranges V{ T{ live-range f 30 100 } } }
 349         }
 350     }
 351     H{ { int-regs { "A" } } }
 352     check-linear-scan
 353 ] must-fail
 354
 355 ! Problem with spilling intervals with no more usages after the spill location
 356 H{
 357     { 1 int-rep }
 358     { 2 int-rep }
 359     { 3 int-rep }
 360     { 4 int-rep }
 361     { 5 int-rep }
 362 } representations set
 363
 364 [ ] [
 365     {
 366         T{ live-interval
 367            { vreg 1 }
 368            { start 0 }
 369            { end 20 }
 370            { uses V{ 0 10 20 } }
 371            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 372         }
 373         T{ live-interval
 374            { vreg 2 }
 375            { start 0 }
 376            { end 20 }
 377            { uses V{ 0 10 20 } }
 378            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 379         }
 380         T{ live-interval
 381            { vreg 3 }
 382            { start 4 }
 383            { end 8 }
 384            { uses V{ 6 } }
 385            { ranges V{ T{ live-range f 4 8 } } }
 386         }
 387         T{ live-interval
 388            { vreg 4 }
 389            { start 4 }
 390            { end 8 }
 391            { uses V{ 8 } }
 392            { ranges V{ T{ live-range f 4 8 } } }
 393         }
 394
 395         ! This guy will invoke the 'spill partially available' code path
 396         T{ live-interval
 397            { vreg 5 }
 398            { start 4 }
 399            { end 8 }
 400            { uses V{ 8 } }
 401            { ranges V{ T{ live-range f 4 8 } } }
 402         }
 403     }
 404     H{ { int-regs { "A" "B" } } }
 405     check-linear-scan
 406 ] unit-test
 407
 408 ! Test spill-new code path
 409
 410 [ ] [
 411     {
 412         T{ live-interval
 413            { vreg 1 }
 414            { start 0 }
 415            { end 10 }
 416            { uses V{ 0 6 10 } }
 417            { ranges V{ T{ live-range f 0 10 } } }
 418         }
 419
 420         ! This guy will invoke the 'spill new' code path
 421         T{ live-interval
 422            { vreg 5 }
 423            { start 2 }
 424            { end 8 }
 425            { uses V{ 8 } }
 426            { ranges V{ T{ live-range f 2 8 } } }
 427         }
 428     }
 429     H{ { int-regs { "A" } } }
 430     check-linear-scan
 431 ] unit-test
 432
 433 [ f ] [
 434     T{ live-range f 0 10 }
 435     T{ live-range f 20 30 }
 436     intersect-live-range
 437 ] unit-test
 438
 439 [ 10 ] [
 440     T{ live-range f 0 10 }
 441     T{ live-range f 10 30 }
 442     intersect-live-range
 443 ] unit-test
 444
 445 [ 5 ] [
 446     T{ live-range f 0 10 }
 447     T{ live-range f 5 30 }
 448     intersect-live-range
 449 ] unit-test
 450
 451 [ 5 ] [
 452     T{ live-range f 5 30 }
 453     T{ live-range f 0 10 }
 454     intersect-live-range
 455 ] unit-test
 456
 457 [ 5 ] [
 458     T{ live-range f 5 10 }
 459     T{ live-range f 0 15 }
 460     intersect-live-range
 461 ] unit-test
 462
 463 [ 50 ] [
 464     {
 465         T{ live-range f 0 10 }
 466         T{ live-range f 20 30 }
 467         T{ live-range f 40 50 }
 468     }
 469     {
 470         T{ live-range f 11 15 }
 471         T{ live-range f 31 35 }
 472         T{ live-range f 50 55 }
 473     }
 474     intersect-live-ranges
 475 ] unit-test
 476
 477 [ f ] [
 478     {
 479         T{ live-range f 0 10 }
 480         T{ live-range f 20 30 }
 481         T{ live-range f 40 50 }
 482     }
 483     {
 484         T{ live-range f 11 15 }
 485         T{ live-range f 31 36 }
 486         T{ live-range f 51 55 }
 487     }
 488     intersect-live-ranges
 489 ] unit-test
 490
 491 [ 5 ] [
 492     T{ live-interval
 493        { start 0 }
 494        { end 10 }
 495        { uses { 0 10 } }
 496        { ranges V{ T{ live-range f 0 10 } } }
 497     }
 498     T{ live-interval
 499        { start 5 }
 500        { end 10 }
 501        { uses { 5 10 } }
 502        { ranges V{ T{ live-range f 5 10 } } }
 503     }
 504     relevant-ranges intersect-live-ranges
 505 ] unit-test
 506
 507 ! register-status had problems because it used map>assoc where the sequence
 508 ! had multiple keys
 509 H{
 510     { 1 int-rep }
 511     { 2 int-rep }
 512     { 3 int-rep }
 513     { 4 int-rep }
 514 } representations set
 515
 516 [ { 0 10 } ] [
 517     H{ { int-regs { 0 1 } } } registers set
 518     H{
 519         { int-regs
 520           {
 521               T{ live-interval
 522                  { vreg 1 }
 523                  { start 0 }
 524                  { end 20 }
 525                  { reg 0 }
 526                  { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 527                  { uses V{ 0 2 10 20 } }
 528               }
 529
 530               T{ live-interval
 531                  { vreg 2 }
 532                  { start 4 }
 533                  { end 40 }
 534                  { reg 0 }
 535                  { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
 536                  { uses V{ 4 6 30 40 } }
 537               }
 538           }
 539         }
 540     } inactive-intervals set
 541     H{
 542         { int-regs
 543           {
 544               T{ live-interval
 545                  { vreg 3 }
 546                  { start 0 }
 547                  { end 40 }
 548                  { reg 1 }
 549                  { ranges V{ T{ live-range f 0 40 } } }
 550                  { uses V{ 0 40 } }
 551               }
 552           }
 553         }
 554     } active-intervals set
 555
 556     T{ live-interval
 557        { vreg 4 }
 558         { start 8 }
 559         { end 10 }
 560         { ranges V{ T{ live-range f 8 10 } } }
 561         { uses V{ 8 10 } }
 562     }
 563     register-status
 564 ] unit-test
 565
 566 :: test-linear-scan-on-cfg ( regs -- )
 567     [
 568         cfg new 0 get >>entry
 569         dup cfg set
 570         dup fake-representations
 571         dup { { int-regs regs } } (linear-scan)
 572         flatten-cfg 1array mr.
 573     ] with-scope ;
 574
 575 ! Bug in live spill slots calculation
 576
 577 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
 578
 579 V{
 580     T{ ##peek
 581        { dst 703128 }
 582        { loc D 1 }
 583     }
 584     T{ ##peek
 585        { dst 703129 }
 586        { loc D 0 }
 587     }
 588     T{ ##copy
 589        { dst 703134 }
 590        { src 703128 }
 591     }
 592     T{ ##copy
 593        { dst 703135 }
 594        { src 703129 }
 595     }
 596     T{ ##compare-imm-branch
 597        { src1 703128 }
 598        { src2 5 }
 599        { cc cc/= }
 600     }
 601 } 1 test-bb
 602
 603 V{
 604     T{ ##copy
 605        { dst 703134 }
 606        { src 703129 }
 607     }
 608     T{ ##copy
 609        { dst 703135 }
 610        { src 703128 }
 611     }
 612     T{ ##branch }
 613 } 2 test-bb
 614
 615 V{
 616     T{ ##replace
 617        { src 703134 }
 618        { loc D 0 }
 619     }
 620     T{ ##replace
 621        { src 703135 }
 622        { loc D 1 }
 623     }
 624     T{ ##epilogue }
 625     T{ ##return }
 626 } 3 test-bb
 627
 628 0 1 edge
 629 1 { 2 3 } edges
 630 2 3 edge
 631
 632 ! Bug in inactive interval handling
 633 ! [ rot dup [ -rot ] when ]
 634 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
 635
 636 V{
 637     T{ ##peek
 638        { dst 689473 }
 639        { loc D 2 }
 640     }
 641     T{ ##peek
 642        { dst 689474 }
 643        { loc D 1 }
 644     }
 645     T{ ##peek
 646        { dst 689475 }
 647        { loc D 0 }
 648     }
 649     T{ ##compare-imm-branch
 650        { src1 689473 }
 651        { src2 5 }
 652        { cc cc/= }
 653     }
 654 } 1 test-bb
 655
 656 V{
 657     T{ ##copy
 658        { dst 689481 }
 659        { src 689475 }
 660        { rep int-rep }
 661     }
 662     T{ ##copy
 663        { dst 689482 }
 664        { src 689474 }
 665        { rep int-rep }
 666     }
 667     T{ ##copy
 668        { dst 689483 }
 669        { src 689473 }
 670        { rep int-rep }
 671     }
 672     T{ ##branch }
 673 } 2 test-bb
 674
 675 V{
 676     T{ ##copy
 677        { dst 689481 }
 678        { src 689473 }
 679        { rep int-rep }
 680     }
 681     T{ ##copy
 682        { dst 689482 }
 683        { src 689475 }
 684        { rep int-rep }
 685     }
 686     T{ ##copy
 687        { dst 689483 }
 688        { src 689474 }
 689        { rep int-rep }
 690     }
 691     T{ ##branch }
 692 } 3 test-bb
 693
 694 V{
 695     T{ ##replace
 696        { src 689481 }
 697        { loc D 0 }
 698     }
 699     T{ ##replace
 700        { src 689482 }
 701        { loc D 1 }
 702     }
 703     T{ ##replace
 704        { src 689483 }
 705        { loc D 2 }
 706     }
 707     T{ ##epilogue }
 708     T{ ##return }
 709 } 4 test-bb
 710
 711 test-diamond
 712
 713 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
 714
 715 ! Similar to the above
 716 ! [ swap dup [ rot ] when ]
 717
 718 T{ basic-block
 719    { id 201537 }
 720    { number 0 }
 721    { instructions V{ T{ ##prologue } T{ ##branch } } }
 722 } 0 set
 723
 724 V{
 725     T{ ##peek
 726        { dst 689600 }
 727        { loc D 1 }
 728     }
 729     T{ ##peek
 730        { dst 689601 }
 731        { loc D 0 }
 732     }
 733     T{ ##compare-imm-branch
 734        { src1 689600 }
 735        { src2 5 }
 736        { cc cc/= }
 737     }
 738 } 1 test-bb
 739
 740 V{
 741     T{ ##peek
 742        { dst 689604 }
 743        { loc D 2 }
 744     }
 745     T{ ##copy
 746        { dst 689607 }
 747        { src 689604 }
 748     }
 749     T{ ##copy
 750        { dst 689608 }
 751        { src 689600 }
 752        { rep int-rep }
 753     }
 754     T{ ##copy
 755        { dst 689610 }
 756        { src 689601 }
 757        { rep int-rep }
 758     }
 759     T{ ##branch }
 760 } 2 test-bb
 761
 762 V{
 763     T{ ##peek
 764        { dst 689609 }
 765        { loc D 2 }
 766     }
 767     T{ ##copy
 768        { dst 689607 }
 769        { src 689600 }
 770        { rep int-rep }
 771     }
 772     T{ ##copy
 773        { dst 689608 }
 774        { src 689601 }
 775        { rep int-rep }
 776     }
 777     T{ ##copy
 778        { dst 689610 }
 779        { src 689609 }
 780        { rep int-rep }
 781     }
 782     T{ ##branch }
 783 } 3 test-bb
 784
 785 V{
 786     T{ ##replace
 787        { src 689607 }
 788        { loc D 0 }
 789     }
 790     T{ ##replace
 791        { src 689608 }
 792        { loc D 1 }
 793     }
 794     T{ ##replace
 795        { src 689610 }
 796        { loc D 2 }
 797     }
 798     T{ ##epilogue }
 799     T{ ##return }
 800 } 4 test-bb
 801
 802 test-diamond
 803
 804 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
 805
 806 ! compute-live-registers was inaccurate since it didn't take
 807 ! lifetime holes into account
 808
 809 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
 810
 811 V{
 812     T{ ##peek
 813        { dst 0 }
 814        { loc D 0 }
 815     }
 816     T{ ##compare-imm-branch
 817        { src1 0 }
 818        { src2 5 }
 819        { cc cc/= }
 820     }
 821 } 1 test-bb
 822
 823 V{
 824     T{ ##peek
 825        { dst 1 }
 826        { loc D 1 }
 827     }
 828     T{ ##copy
 829        { dst 2 }
 830        { src 1 }
 831        { rep int-rep }
 832     }
 833     T{ ##branch }
 834 } 2 test-bb
 835
 836 V{
 837     T{ ##peek
 838        { dst 3 }
 839        { loc D 2 }
 840     }
 841     T{ ##copy
 842        { dst 2 }
 843        { src 3 }
 844        { rep int-rep }
 845     }
 846     T{ ##branch }
 847 } 3 test-bb
 848
 849 V{
 850     T{ ##replace
 851        { src 2 }
 852        { loc D 0 }
 853     }
 854     T{ ##return }
 855 } 4 test-bb
 856
 857 test-diamond
 858
 859 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
 860
 861 ! Inactive interval handling: splitting active interval
 862 ! if it fits in lifetime hole only partially
 863
 864 V{ T{ ##peek f 3 R 1 } T{ ##branch } } 0 test-bb
 865
 866 V{
 867     T{ ##peek f 2 R 0 }
 868     T{ ##compare-imm-branch f 2 5 cc= }
 869 } 1 test-bb
 870
 871 V{
 872     T{ ##peek f 0 D 0 }
 873     T{ ##branch }
 874 } 2 test-bb
 875
 876
 877 V{
 878     T{ ##peek f 1 D 1 }
 879     T{ ##peek f 0 D 0 }
 880     T{ ##replace f 1 D 2 }
 881     T{ ##branch }
 882 } 3 test-bb
 883
 884 V{
 885     T{ ##replace f 3 R 2 }
 886     T{ ##replace f 0 D 0 }
 887     T{ ##return }
 888 } 4 test-bb
 889
 890 test-diamond
 891
 892 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
 893
 894 ! Not until splitting is finished
 895 ! [ _copy ] [ 3 get instructions>> second class ] unit-test
 896
 897 ! Resolve pass; make sure the spilling is done correctly
 898 V{ T{ ##peek f 3 R 1 } T{ ##branch } } 0 test-bb
 899
 900 V{
 901     T{ ##peek f 2 R 0 }
 902     T{ ##compare-imm-branch f 2 5 cc= }
 903 } 1 test-bb
 904
 905 V{
 906     T{ ##branch }
 907 } 2 test-bb
 908
 909 V{
 910     T{ ##replace f 3 R 1 }
 911     T{ ##peek f 1 D 1 }
 912     T{ ##peek f 0 D 0 }
 913     T{ ##replace f 1 D 2 }
 914     T{ ##replace f 0 D 2 }
 915     T{ ##branch }
 916 } 3 test-bb
 917
 918 V{
 919     T{ ##replace f 3 R 2 }
 920     T{ ##return }
 921 } 4 test-bb
 922
 923 test-diamond
 924
 925 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
 926
 927 [ _spill ] [ 2 get successors>> first instructions>> first class ] unit-test
 928
 929 [ _spill ] [ 3 get instructions>> second class ] unit-test
 930
 931 [ f ] [ 3 get instructions>> [ _reload? ] any? ] unit-test
 932
 933 [ _reload ] [ 4 get instructions>> first class ] unit-test
 934
 935 ! Resolve pass
 936 V{
 937     T{ ##branch }
 938 } 0 test-bb
 939
 940 V{
 941     T{ ##peek f 0 D 0 }
 942     T{ ##compare-imm-branch f 0 5 cc= }
 943 } 1 test-bb
 944
 945 V{
 946     T{ ##replace f 0 D 0 }
 947     T{ ##peek f 1 D 0 }
 948     T{ ##peek f 2 D 0 }
 949     T{ ##replace f 1 D 0 }
 950     T{ ##replace f 2 D 0 }
 951     T{ ##branch }
 952 } 2 test-bb
 953
 954 V{
 955     T{ ##branch }
 956 } 3 test-bb
 957
 958 V{
 959     T{ ##peek f 1 D 0 }
 960     T{ ##compare-imm-branch f 1 5 cc= }
 961 } 4 test-bb
 962
 963 V{
 964     T{ ##replace f 0 D 0 }
 965     T{ ##return }
 966 } 5 test-bb
 967
 968 V{
 969     T{ ##replace f 0 D 0 }
 970     T{ ##return }
 971 } 6 test-bb
 972
 973 0 1 edge
 974 1 { 2 3 } edges
 975 2 4 edge
 976 3 4 edge
 977 4 { 5 6 } edges
 978
 979 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
 980
 981 [ t ] [ 2 get instructions>> [ _spill? ] any? ] unit-test
 982
 983 [ t ] [ 3 get predecessors>> first instructions>> [ _spill? ] any? ] unit-test
 984
 985 [ t ] [ 5 get instructions>> [ _reload? ] any? ] unit-test
 986
 987 ! A more complicated failure case with resolve that came up after the above
 988 ! got fixed
 989 V{ T{ ##branch } } 0 test-bb
 990 V{
 991     T{ ##peek f 0 D 0 }
 992     T{ ##peek f 1 D 1 }
 993     T{ ##peek f 2 D 2 }
 994     T{ ##peek f 3 D 3 }
 995     T{ ##peek f 4 D 0 }
 996     T{ ##branch }
 997 } 1 test-bb
 998 V{ T{ ##branch } } 2 test-bb
 999 V{ T{ ##branch } } 3 test-bb
1000 V{
1001
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 }
1007     T{ ##branch }
1008 } 4 test-bb
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
1012 V{
1013     T{ ##replace f 1 D 1 }
1014     T{ ##replace f 2 D 2 }
1015     T{ ##replace f 3 D 3 }
1016     T{ ##peek f 5 D 1 }
1017     T{ ##peek f 6 D 2 }
1018     T{ ##peek f 7 D 3 }
1019     T{ ##peek f 8 D 4 }
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 }
1024     T{ ##branch }
1025 } 8 test-bb
1026 V{
1027     T{ ##replace f 1 D 1 }
1028     T{ ##replace f 2 D 2 }
1029     T{ ##replace f 3 D 3 }
1030     T{ ##return }
1031 } 9 test-bb
1032
1033 0 1 edge
1034 1 { 2 7 } edges
1035 7 8 edge
1036 8 9 edge
1037 2 { 3 5 } edges
1038 3 4 edge
1039 4 9 edge
1040 5 6 edge
1041
1042 [ ] [ { 1 2 3 4 } test-linear-scan-on-cfg ] unit-test
1043
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
1048
1049 ! Resolve pass should insert this
1050 [ _reload ] [ 5 get predecessors>> first instructions>> first class ] unit-test
1051
1052 ! Some random bug
1053 V{
1054     T{ ##peek f 1 D 1 }
1055     T{ ##peek f 2 D 2 }
1056     T{ ##replace f 1 D 1 }
1057     T{ ##replace f 2 D 2 }
1058     T{ ##peek f 3 D 0 }
1059     T{ ##peek f 0 D 0 }
1060     T{ ##branch }
1061 } 0 test-bb
1062
1063 V{ T{ ##branch } } 1 test-bb
1064
1065 V{
1066     T{ ##peek f 1 D 1 }
1067     T{ ##peek f 2 D 2 }
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 }
1072     T{ ##branch }
1073 } 2 test-bb
1074
1075 V{ T{ ##branch } } 3 test-bb
1076
1077 V{
1078     T{ ##return }
1079 } 4 test-bb
1080
1081 test-diamond
1082
1083 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1084
1085 ! Spilling an interval immediately after its activated;
1086 ! and the interval does not have a use at the activation point
1087 V{
1088     T{ ##peek f 1 D 1 }
1089     T{ ##peek f 2 D 2 }
1090     T{ ##replace f 1 D 1 }
1091     T{ ##replace f 2 D 2 }
1092     T{ ##peek f 0 D 0 }
1093     T{ ##branch }
1094 } 0 test-bb
1095
1096 V{ T{ ##branch } } 1 test-bb
1097
1098 V{
1099     T{ ##peek f 1 D 1 }
1100     T{ ##branch }
1101 } 2 test-bb
1102
1103 V{
1104     T{ ##replace f 1 D 1 }
1105     T{ ##peek f 2 D 2 }
1106     T{ ##replace f 2 D 2 }
1107     T{ ##branch }
1108 } 3 test-bb
1109
1110 V{ T{ ##branch } } 4 test-bb
1111
1112 V{
1113     T{ ##replace f 0 D 0 }
1114     T{ ##return }
1115 } 5 test-bb
1116
1117 0 1 edge
1118 1 { 2 4 } edges
1119 4 5 edge
1120 2 3 edge
1121 3 5 edge
1122
1123 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1124
1125 ! Reduction of push-all regression, x86-32
1126 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
1127
1128 V{
1129     T{ ##load-immediate { dst 61 } }
1130     T{ ##peek { dst 62 } { loc D 0 } }
1131     T{ ##peek { dst 64 } { loc D 1 } }
1132     T{ ##slot-imm
1133         { dst 69 }
1134         { obj 64 }
1135         { slot 1 }
1136         { tag 2 }
1137     }
1138     T{ ##copy { dst 79 } { src 69 } { rep int-rep } }
1139     T{ ##slot-imm
1140         { dst 85 }
1141         { obj 62 }
1142         { slot 2 }
1143         { tag 7 }
1144     }
1145     T{ ##compare-branch
1146         { src1 69 }
1147         { src2 85 }
1148         { cc cc> }
1149     }
1150 } 1 test-bb
1151
1152 V{
1153     T{ ##slot-imm
1154         { dst 97 }
1155         { obj 62 }
1156         { slot 2 }
1157         { tag 7 }
1158     }
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 } }
1168     T{ ##branch }
1169 } 2 test-bb
1170
1171 V{
1172     T{ ##peek { dst 98 } { loc R 0 } }
1173     T{ ##peek { dst 100 } { loc D 0 } }
1174     T{ ##set-slot-imm
1175         { src 100 }
1176         { obj 98 }
1177         { slot 2 }
1178         { tag 7 }
1179     }
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 } }
1192     T{ ##branch }
1193 } 3 test-bb
1194
1195 V{
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 } }
1202     T{ ##branch }
1203 } 4 test-bb
1204
1205 V{
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 } }
1212     T{ ##epilogue }
1213     T{ ##return }
1214 } 5 test-bb
1215
1216 0 1 edge
1217 1 { 2 4 } edges
1218 2 3 edge
1219 3 5 edge
1220 4 5 edge
1221
1222 [ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
1223
1224 ! Another reduction of push-all
1225 V{ T{ ##prologue } T{ ##branch } } 0 test-bb
1226
1227 V{
1228     T{ ##peek { dst 85 } { loc D 0 } }
1229     T{ ##slot-imm
1230         { dst 89 }
1231         { obj 85 }
1232         { slot 3 }
1233         { tag 7 }
1234     }
1235     T{ ##peek { dst 91 } { loc D 1 } }
1236     T{ ##slot-imm
1237         { dst 96 }
1238         { obj 91 }
1239         { slot 1 }
1240         { tag 2 }
1241     }
1242     T{ ##add
1243         { dst 109 }
1244         { src1 89 }
1245         { src2 96 }
1246     }
1247     T{ ##slot-imm
1248         { dst 115 }
1249         { obj 85 }
1250         { slot 2 }
1251         { tag 7 }
1252     }
1253     T{ ##slot-imm
1254         { dst 118 }
1255         { obj 115 }
1256         { slot 1 }
1257         { tag 2 }
1258     }
1259     T{ ##compare-branch
1260         { src1 109 }
1261         { src2 118 }
1262         { cc cc> }
1263     }
1264 } 1 test-bb
1265
1266 V{
1267     T{ ##add-imm
1268         { dst 128 }
1269         { src1 109 }
1270         { src2 8 }
1271     }
1272     T{ ##load-immediate { 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 } }
1282     T{ ##branch }
1283 } 2 test-bb
1284
1285 V{
1286     T{ ##peek { dst 134 } { loc D 1 } }
1287     T{ ##slot-imm
1288         { dst 140 }
1289         { obj 134 }
1290         { slot 2 }
1291         { tag 7 }
1292     }
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 } }
1298     T{ ##branch }
1299 } 3 test-bb
1300
1301 V{
1302     T{ ##peek { dst 141 } { loc R 0 } }
1303     T{ ##peek { dst 143 } { loc D 0 } }
1304     T{ ##set-slot-imm
1305         { src 143 }
1306         { obj 141 }
1307         { slot 2 }
1308         { tag 7 }
1309     }
1310     T{ ##write-barrier-imm
1311         { src 141 }
1312         { slot 2 }
1313         { temp1 145 }
1314         { temp2 146 }
1315     }
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 } }
1330     T{ ##branch }
1331 } 4 test-bb
1332
1333 V{
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 } }
1342     T{ ##branch }
1343 } 5 test-bb
1344
1345 V{
1346     T{ ##set-slot-imm
1347         { src 163 }
1348         { obj 161 }
1349         { slot 3 }
1350         { tag 7 }
1351     }
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 } }
1360     T{ ##epilogue }
1361     T{ ##return }
1362 } 6 test-bb
1363
1364 0 1 edge
1365 1 { 2 5 } edges
1366 2 3 edge
1367 3 4 edge
1368 4 6 edge
1369 5 6 edge
1370
1371 [ ] [ { 1 2 3 4 5 } test-linear-scan-on-cfg ] unit-test
1372
1373 ! Fencepost error in assignment pass
1374 V{ T{ ##branch } } 0 test-bb
1375
1376 V{
1377     T{ ##peek f 0 D 0 }
1378     T{ ##compare-imm-branch f 0 5 cc= }
1379 } 1 test-bb
1380
1381 V{ T{ ##branch } } 2 test-bb
1382
1383 V{
1384     T{ ##peek f 1 D 0 }
1385     T{ ##peek f 2 D 0 }
1386     T{ ##replace f 1 D 0 }
1387     T{ ##replace f 2 D 0 }
1388     T{ ##branch }
1389 } 3 test-bb
1390
1391 V{
1392     T{ ##replace f 0 D 0 }
1393     T{ ##return }
1394 } 4 test-bb
1395
1396 test-diamond
1397
1398 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1399
1400 [ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
1401
1402 [ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
1403
1404 [ 1 ] [ 3 get predecessors>> first instructions>> [ _spill? ] count ] unit-test
1405
1406 [ 1 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
1407
1408 ! Another test case for fencepost error in assignment pass
1409 V{ T{ ##branch } } 0 test-bb
1410
1411 V{
1412     T{ ##peek f 0 D 0 }
1413     T{ ##compare-imm-branch f 0 5 cc= }
1414 } 1 test-bb
1415
1416 V{
1417     T{ ##peek f 1 D 0 }
1418     T{ ##peek f 2 D 0 }
1419     T{ ##replace f 1 D 0 }
1420     T{ ##replace f 2 D 0 }
1421     T{ ##replace f 0 D 0 }
1422     T{ ##branch }
1423 } 2 test-bb
1424
1425 V{
1426     T{ ##branch }
1427 } 3 test-bb
1428
1429 V{
1430     T{ ##replace f 0 D 0 }
1431     T{ ##return }
1432 } 4 test-bb
1433
1434 test-diamond
1435
1436 [ ] [ { 1 2 } test-linear-scan-on-cfg ] unit-test
1437
1438 [ 0 ] [ 1 get instructions>> [ _spill? ] count ] unit-test
1439
1440 [ 1 ] [ 2 get instructions>> [ _spill? ] count ] unit-test
1441
1442 [ 1 ] [ 2 get instructions>> [ _reload? ] count ] unit-test
1443
1444 [ 0 ] [ 3 get instructions>> [ _spill? ] count ] unit-test
1445
1446 [ 0 ] [ 4 get instructions>> [ _reload? ] count ] unit-test
1447
1448 V{
1449     T{ ##peek f 0 D 0 }
1450     T{ ##peek f 1 D 1 }
1451     T{ ##replace f 1 D 1 }
1452     T{ ##branch }
1453 } 0 test-bb
1454
1455 V{
1456     T{ ##gc f 2 3 }
1457     T{ ##branch }
1458 } 1 test-bb
1459
1460 V{
1461     T{ ##replace f 0 D 0 }
1462     T{ ##return }
1463 } 2 test-bb
1464
1465 0 1 edge
1466 1 2 edge
1467
1468 [ ] [ { 1 2 3 } test-linear-scan-on-cfg ] unit-test
1469
1470 [ { { 0 1 } } ] [ 1 get instructions>> first tagged-values>> ] unit-test
1471
1472 V{
1473     T{ ##peek f 0 D 0 }
1474     T{ ##peek f 1 D 1 }
1475     T{ ##compare-imm-branch f 1 5 cc= }
1476 } 0 test-bb
1477
1478 V{
1479     T{ ##gc f 2 3 }
1480     T{ ##replace f 0 D 0 }
1481     T{ ##return }
1482 } 1 test-bb
1483
1484 V{
1485     T{ ##return }
1486 } 2 test-bb
1487
1488 0 { 1 2 } edges
1489
1490 [ ] [ { 1 2 3 } test-linear-scan-on-cfg ] unit-test
1491
1492 [ { { 0 1 } } ] [ 1 get instructions>> first tagged-values>> ] unit-test