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