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

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