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

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