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

   1 USING: tools.test random sorting sequences hashtables assocs
   2 kernel arrays splitting namespaces math accessors vectors
   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 ranges>> ranges-endpoints
  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     [ [ [ >vector ] change-uses [ >vector ] change-ranges ] ?call ] bi@ ;
  68
  69 {
  70     T{ live-interval-state
  71        { vreg 1 }
  72        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
  73        { ranges V{ { 0 2 } } }
  74        { spill-to T{ spill-slot f 0 } }
  75        { spill-rep float-rep }
  76     }
  77     T{ live-interval-state
  78        { vreg 1 }
  79        { uses V{ T{ vreg-use f 5 f float-rep } } }
  80        { ranges V{ { 5 5 } } }
  81        { reload-from T{ spill-slot f 0 } }
  82        { reload-rep float-rep }
  83     }
  84 } [
  85     T{ live-interval-state
  86        { vreg 1 }
  87        { uses
  88          V{
  89              T{ vreg-use f 0 float-rep f }
  90              T{ vreg-use f 1 f float-rep }
  91              T{ vreg-use f 5 f float-rep }
  92          }
  93        }
  94        { ranges V{ { 0 5 } } }
  95     } 2 split-for-spill
  96     clean-up-split
  97 ] unit-test
  98
  99 {
 100     f
 101     T{ live-interval-state
 102        { vreg 2 }
 103        { uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
 104        { ranges V{ { 1 5 } } }
 105        { reload-from T{ spill-slot f 4 } }
 106        { reload-rep float-rep }
 107     }
 108 } [
 109     T{ live-interval-state
 110        { vreg 2 }
 111        { uses
 112          V{
 113              T{ vreg-use f 0 float-rep f }
 114              T{ vreg-use f 1 f float-rep }
 115              T{ vreg-use f 5 f float-rep }
 116          }
 117        }
 118        { ranges V{ { 0 5 } } }
 119     } 0 split-for-spill
 120     clean-up-split
 121 ] unit-test
 122
 123 {
 124     T{ live-interval-state
 125        { vreg 3 }
 126        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
 127        { ranges V{ { 0 2 } } }
 128        { spill-to T{ spill-slot f 8 } }
 129        { spill-rep float-rep }
 130     }
 131     f
 132 } [
 133     T{ live-interval-state
 134        { vreg 3 }
 135        { uses
 136          V{
 137              T{ vreg-use f 0 float-rep f }
 138              T{ vreg-use f 1 f float-rep }
 139              T{ vreg-use f 5 f float-rep }
 140          }
 141        }
 142        { ranges V{ { 0 5 } } }
 143     } 5 split-for-spill
 144     clean-up-split
 145 ] unit-test
 146
 147 {
 148     T{ live-interval-state
 149        { vreg 4 }
 150        { uses V{ T{ vreg-use f 0 float-rep f } } }
 151        { ranges V{ { 0 1 } } }
 152        { spill-to T{ spill-slot f 12 } }
 153        { spill-rep float-rep }
 154     }
 155     T{ live-interval-state
 156        { vreg 4 }
 157        { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
 158        { ranges V{ { 20 30 } } }
 159        { reload-from T{ spill-slot f 12 } }
 160        { reload-rep float-rep }
 161     }
 162 } [
 163     T{ live-interval-state
 164        { vreg 4 }
 165        { uses
 166          V{
 167              T{ vreg-use f 0 float-rep f }
 168              T{ vreg-use f 20 f float-rep }
 169              T{ vreg-use f 30 f float-rep }
 170          }
 171        }
 172        { ranges V{ { 0 8 } { 10 18 } { 20 30 } } }
 173     } 10 split-for-spill
 174     clean-up-split
 175 ] unit-test
 176
 177 ! Don't insert reload if first usage is a def
 178 {
 179     T{ live-interval-state
 180        { vreg 5 }
 181        { uses V{ T{ vreg-use f 0 float-rep f } } }
 182        { ranges V{ { 0 1 } } }
 183        { spill-to T{ spill-slot f 16 } }
 184        { spill-rep float-rep }
 185     }
 186     T{ live-interval-state
 187        { vreg 5 }
 188        { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
 189        { ranges V{ { 20 30 } } }
 190     }
 191 } [
 192     T{ live-interval-state
 193        { vreg 5 }
 194        { uses
 195          V{
 196              T{ vreg-use f 0 float-rep f }
 197              T{ vreg-use f 20 float-rep f }
 198              T{ vreg-use f 30 f float-rep }
 199          }
 200        }
 201        { ranges V{ { 0 8 } { 10 18 } { 20 30 } } }
 202     } 10 split-for-spill
 203     clean-up-split
 204 ] unit-test
 205
 206 ! Multiple representations
 207 {
 208     T{ live-interval-state
 209        { vreg 6 }
 210        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
 211        { ranges V{ { 0 11 } } }
 212        { spill-to T{ spill-slot f 24 } }
 213        { spill-rep double-rep }
 214     }
 215     T{ live-interval-state
 216        { vreg 6 }
 217        { uses V{ T{ vreg-use f 20 f double-rep } } }
 218        { ranges V{ { 20 20 } } }
 219        { reload-from T{ spill-slot f 24 } }
 220        { reload-rep double-rep }
 221     }
 222 } [
 223     T{ live-interval-state
 224        { vreg 6 }
 225        { uses
 226          V{
 227              T{ vreg-use f 0 float-rep f }
 228              T{ vreg-use f 10 double-rep float-rep }
 229              T{ vreg-use f 20 f double-rep }
 230          }
 231        }
 232        { ranges V{ { 0 20 } } }
 233     } 15 split-for-spill
 234     clean-up-split
 235 ] unit-test
 236
 237 {
 238     f
 239     T{ live-interval-state
 240         { vreg 7 }
 241         { ranges V{ { 8 8 } } }
 242         { uses V{ T{ vreg-use f 8 int-rep } } }
 243     }
 244 } [
 245     T{ live-interval-state
 246         { vreg 7 }
 247         { ranges V{ { 4 8 } } }
 248         { uses V{ T{ vreg-use f 8 int-rep } } }
 249     } 4 split-for-spill
 250     clean-up-split
 251 ] unit-test
 252
 253 ! trim-before-ranges, trim-after-ranges
 254 {
 255     T{ live-interval-state
 256         { vreg 8 }
 257         { ranges V{ { 0 3 } } }
 258         { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
 259         { spill-to T{ spill-slot f 32 } }
 260         { spill-rep int-rep }
 261     }
 262     T{ live-interval-state
 263         { vreg 8 }
 264         { ranges V{ { 14 16 } } }
 265         { uses V{ T{ vreg-use f 14 f int-rep } } }
 266         { reload-from T{ spill-slot f 32 } }
 267         { reload-rep int-rep }
 268     }
 269 } [
 270     T{ live-interval-state
 271         { vreg 8 }
 272         { ranges V{ { 0 4 } { 6 10 } { 12 16 } } }
 273         { uses
 274           V{
 275               T{ vreg-use f 0 f int-rep }
 276               T{ vreg-use f 2 f int-rep }
 277               T{ vreg-use f 14 f int-rep } }
 278         }
 279     } 8 split-for-spill
 280     clean-up-split
 281 ] unit-test
 282
 283 H{
 284     { 1 int-rep }
 285     { 2 int-rep }
 286     { 3 int-rep }
 287 } representations set
 288
 289 {
 290     {
 291         3
 292         10
 293     }
 294 } [
 295     H{
 296         { int-regs
 297           V{
 298               T{ live-interval-state
 299                  { vreg 1 }
 300                  { reg 1 }
 301                  { ranges V{ { 1 15 } } }
 302                  { uses
 303                    V{
 304                        T{ vreg-use f 1 int-rep f }
 305                        T{ vreg-use f 3 f int-rep }
 306                        T{ vreg-use f 7 f int-rep }
 307                        T{ vreg-use f 10 f int-rep }
 308                        T{ vreg-use f 15 f int-rep }
 309                    }
 310                  }
 311               }
 312               T{ live-interval-state
 313                  { vreg 2 }
 314                  { reg 2 }
 315                  { ranges V{ { 3 8 } } }
 316                  { uses
 317                    V{
 318                        T{ vreg-use f 3 int-rep f }
 319                        T{ vreg-use f 4 f int-rep }
 320                        T{ vreg-use f 8 f int-rep }
 321                    }
 322                  }
 323               }
 324               T{ live-interval-state
 325                  { vreg 3 }
 326                  { reg 3 }
 327                  { ranges V{ { 3 10 } } }
 328                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
 329               }
 330           }
 331         }
 332     } active-intervals set
 333     H{ } inactive-intervals set
 334     T{ live-interval-state
 335        { vreg 1 }
 336        { ranges V{ { 5 5 } } }
 337        { uses V{ T{ vreg-use f 5 int-rep f } } }
 338     }
 339     spill-status
 340 ] unit-test
 341
 342 {
 343     {
 344         1
 345         1/0.
 346     }
 347 } [
 348     H{
 349         { int-regs
 350           V{
 351               T{ live-interval-state
 352                  { vreg 1 }
 353                  { reg 1 }
 354                  { ranges V{ { 1 15 } } }
 355                  { uses V{ T{ vreg-use f 1 int-rep f } } }
 356               }
 357               T{ live-interval-state
 358                  { vreg 2 }
 359                  { reg 2 }
 360                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
 361               }
 362           }
 363         }
 364     } active-intervals set
 365     H{ } inactive-intervals set
 366     T{ live-interval-state
 367        { vreg 3 }
 368        { ranges V{ { 5 5 } } }
 369        { uses V{ T{ vreg-use f 5 int-rep f } } }
 370     }
 371     spill-status
 372 ] unit-test
 373
 374 H{ { 1 int-rep } { 2 int-rep } } representations set
 375
 376 { } [
 377     {
 378         T{ live-interval-state
 379            { vreg 1 }
 380            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 381            { ranges V{ { 0 100 } } }
 382         }
 383     }
 384     H{ { int-regs { "A" } } }
 385     check-linear-scan
 386 ] unit-test
 387
 388 { } [
 389     {
 390         T{ live-interval-state
 391            { vreg 1 }
 392            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
 393            { ranges V{ { 0 10 } } }
 394         }
 395         T{ live-interval-state
 396            { vreg 2 }
 397            { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
 398            { ranges V{ { 11 20 } } }
 399         }
 400     }
 401     H{ { int-regs { "A" } } }
 402     check-linear-scan
 403 ] unit-test
 404
 405 { } [
 406     {
 407         T{ live-interval-state
 408            { vreg 1 }
 409            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 410            { ranges V{ { 0 100 } } }
 411         }
 412         T{ live-interval-state
 413            { vreg 2 }
 414            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
 415            { ranges V{ { 30 60 } } }
 416         }
 417     }
 418     H{ { int-regs { "A" } } }
 419     check-linear-scan
 420 ] unit-test
 421
 422 { } [
 423     {
 424         T{ live-interval-state
 425            { vreg 1 }
 426            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 427            { ranges V{ { 0 100 } } }
 428         }
 429         T{ live-interval-state
 430            { vreg 2 }
 431            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
 432            { ranges V{ { 30 200 } } }
 433         }
 434     }
 435     H{ { int-regs { "A" } } }
 436     check-linear-scan
 437 ] unit-test
 438
 439 [
 440     {
 441         T{ live-interval-state
 442            { vreg 1 }
 443            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 444            { ranges V{ { 0 100 } } }
 445         }
 446         T{ live-interval-state
 447            { vreg 2 }
 448            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
 449            { ranges V{ { 30 100 } } }
 450         }
 451     }
 452     H{ { int-regs { "A" } } }
 453     check-linear-scan
 454 ] must-fail
 455
 456 ! Problem with spilling intervals with no more usages after the spill location
 457 H{
 458     { 1 int-rep }
 459     { 2 int-rep }
 460     { 3 int-rep }
 461     { 4 int-rep }
 462     { 5 int-rep }
 463 } representations set
 464
 465 { } [
 466     {
 467         T{ live-interval-state
 468            { vreg 1 }
 469            { uses
 470              V{
 471                  T{ vreg-use f 0 int-rep f }
 472                  T{ vreg-use f 10 f int-rep }
 473                  T{ vreg-use f 20 f int-rep }
 474              }
 475            }
 476            { ranges V{ { 0 2 } { 10 20 } } }
 477         }
 478         T{ live-interval-state
 479            { vreg 2 }
 480            { uses
 481              V{
 482                  T{ vreg-use f 0 int-rep f }
 483                  T{ vreg-use f 10 f int-rep }
 484                  T{ vreg-use f 20 f int-rep }
 485              }
 486            }
 487            { ranges V{ { 0 2 } { 10 20 } } }
 488         }
 489         T{ live-interval-state
 490            { vreg 3 }
 491            { uses V{ T{ vreg-use f 6 int-rep f } } }
 492            { ranges V{ { 4 8 } } }
 493         }
 494         T{ live-interval-state
 495            { vreg 4 }
 496            { uses V{ T{ vreg-use f 8 int-rep f } } }
 497            { ranges V{ { 4 8 } } }
 498         }
 499
 500         ! This guy will invoke the 'spill partially available' code path
 501         T{ live-interval-state
 502            { vreg 5 }
 503            { uses V{ T{ vreg-use f 8 int-rep f } } }
 504            { ranges V{ { 4 8 } } }
 505         }
 506     }
 507     H{ { int-regs { "A" "B" } } }
 508     check-linear-scan
 509 ] unit-test
 510
 511 ! Test spill-new code path
 512
 513 { } [
 514     {
 515         T{ live-interval-state
 516            { vreg 1 }
 517            { 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 } } }
 518            { ranges V{ { 0 10 } } }
 519         }
 520
 521         ! This guy will invoke the 'spill new' code path
 522         T{ live-interval-state
 523            { vreg 5 }
 524            { uses V{ T{ vreg-use f 8 int-rep f } } }
 525            { ranges V{ { 2 8 } } }
 526         }
 527     }
 528     H{ { int-regs { "A" } } }
 529     check-linear-scan
 530 ] unit-test
 531
 532 ! register-status had problems because it used map>assoc where the sequence
 533 ! had multiple keys
 534 H{
 535     { 1 int-rep }
 536     { 2 int-rep }
 537     { 3 int-rep }
 538     { 4 int-rep }
 539 } representations set
 540
 541 { { 0 10 } } [
 542     H{
 543         { int-regs
 544           {
 545               T{ live-interval-state
 546                  { vreg 1 }
 547                  { reg 0 }
 548                  { ranges V{ { 0 2 } { 10 20 } } }
 549                  { uses V{ 0 2 10 20 } }
 550               }
 551
 552               T{ live-interval-state
 553                  { vreg 2 }
 554                  { reg 0 }
 555                  { ranges V{ { 4 6 } { 30 40 } } }
 556                  { uses V{ 4 6 30 40 } }
 557               }
 558           }
 559         }
 560     } inactive-intervals set
 561     H{
 562         { int-regs
 563           {
 564               T{ live-interval-state
 565                  { vreg 3 }
 566                  { reg 1 }
 567                  { ranges V{ { 0 40 } } }
 568                  { uses V{ 0 40 } }
 569               }
 570           }
 571         }
 572     } active-intervals set
 573
 574     T{ live-interval-state
 575         { vreg 4 }
 576         { ranges V{ { 8 10 } } }
 577         { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
 578     }
 579     H{ { int-regs { 0 1 } } } register-status
 580 ] unit-test
 581
 582 { t } [
 583     T{ cfg { frame-pointer? f } } admissible-registers machine-registers =
 584 ] unit-test
 585
 586 { f } [
 587     T{ cfg { frame-pointer? t } } admissible-registers
 588     int-regs of frame-reg swap member?
 589 ] unit-test