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

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