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{ T{ live-range f 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{ T{ live-range f 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 V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
  98        { ranges V{ T{ live-range f 0 5 } } }
  99     } 2 split-for-spill
 100     clean-up-split
 101 ] unit-test
 102
 103 {
 104     f
 105     T{ live-interval-state
 106        { vreg 2 }
 107        { start 1 }
 108        { end 5 }
 109        { uses V{ T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
 110        { ranges V{ T{ live-range f 1 5 } } }
 111        { reload-from T{ spill-slot f 4 } }
 112        { reload-rep float-rep }
 113     }
 114 } [
 115     T{ live-interval-state
 116        { vreg 2 }
 117        { start 0 }
 118        { end 5 }
 119        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
 120        { ranges V{ T{ live-range f 0 5 } } }
 121     } 0 split-for-spill
 122     clean-up-split
 123 ] unit-test
 124
 125 {
 126     T{ live-interval-state
 127        { vreg 3 }
 128        { start 0 }
 129        { end 2 }
 130        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } } }
 131        { ranges V{ T{ live-range f 0 2 } } }
 132        { spill-to T{ spill-slot f 8 } }
 133        { spill-rep float-rep }
 134     }
 135     f
 136 } [
 137     T{ live-interval-state
 138        { vreg 3 }
 139        { start 0 }
 140        { end 5 }
 141        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 1 f float-rep } T{ vreg-use f 5 f float-rep } } }
 142        { ranges V{ T{ live-range f 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        { start 0 }
 151        { end 1 }
 152        { uses V{ T{ vreg-use f 0 float-rep f } } }
 153        { ranges V{ T{ live-range f 0 1 } } }
 154        { spill-to T{ spill-slot f 12 } }
 155        { spill-rep float-rep }
 156     }
 157     T{ live-interval-state
 158        { vreg 4 }
 159        { start 20 }
 160        { end 30 }
 161        { uses V{ T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
 162        { ranges V{ T{ live-range f 20 30 } } }
 163        { reload-from T{ spill-slot f 12 } }
 164        { reload-rep float-rep }
 165     }
 166 } [
 167     T{ live-interval-state
 168        { vreg 4 }
 169        { start 0 }
 170        { end 30 }
 171        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 20 f float-rep } T{ vreg-use f 30 f float-rep } } }
 172        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 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        { start 0 }
 182        { end 1 }
 183        { uses V{ T{ vreg-use f 0 float-rep f } } }
 184        { ranges V{ T{ live-range f 0 1 } } }
 185        { spill-to T{ spill-slot f 16 } }
 186        { spill-rep float-rep }
 187     }
 188     T{ live-interval-state
 189        { vreg 5 }
 190        { start 20 }
 191        { end 30 }
 192        { uses V{ T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
 193        { ranges V{ T{ live-range f 20 30 } } }
 194     }
 195 } [
 196     T{ live-interval-state
 197        { vreg 5 }
 198        { start 0 }
 199        { end 30 }
 200        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 20 float-rep f } T{ vreg-use f 30 f float-rep } } }
 201        { ranges V{ T{ live-range f 0 8 } T{ live-range f 10 18 } T{ live-range f 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        { start 0 }
 211        { end 11 }
 212        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } } }
 213        { ranges V{ T{ live-range f 0 11 } } }
 214        { spill-to T{ spill-slot f 24 } }
 215        { spill-rep double-rep }
 216     }
 217     T{ live-interval-state
 218        { vreg 6 }
 219        { start 20 }
 220        { end 20 }
 221        { uses V{ T{ vreg-use f 20 f double-rep } } }
 222        { ranges V{ T{ live-range f 20 20 } } }
 223        { reload-from T{ spill-slot f 24 } }
 224        { reload-rep double-rep }
 225     }
 226 } [
 227     T{ live-interval-state
 228        { vreg 6 }
 229        { start 0 }
 230        { end 20 }
 231        { uses V{ T{ vreg-use f 0 float-rep f } T{ vreg-use f 10 double-rep float-rep } T{ vreg-use f 20 f double-rep } } }
 232        { ranges V{ T{ live-range f 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         { start 8 }
 242         { end 8 }
 243         { ranges V{ T{ live-range f 8 8 } } }
 244         { uses V{ T{ vreg-use f 8 int-rep } } }
 245     }
 246 } [
 247     T{ live-interval-state
 248         { vreg 7 }
 249         { start 4 }
 250         { end 8 }
 251         { ranges V{ T{ live-range f 4 8 } } }
 252         { uses V{ T{ vreg-use f 8 int-rep } } }
 253     } 4 split-for-spill
 254     clean-up-split
 255 ] unit-test
 256
 257 ! trim-before-ranges, trim-after-ranges
 258 {
 259     T{ live-interval-state
 260         { vreg 8 }
 261         { start 0 }
 262         { end 3 }
 263         { ranges V{ T{ live-range f 0 3 } } }
 264         { uses V{ T{ vreg-use f 0 f int-rep } T{ vreg-use f 2 f int-rep } } }
 265         { spill-to T{ spill-slot f 32 } }
 266         { spill-rep int-rep }
 267     }
 268     T{ live-interval-state
 269         { vreg 8 }
 270         { start 14 }
 271         { end 16 }
 272         { ranges V{ T{ live-range f 14 16 } } }
 273         { uses V{ T{ vreg-use f 14 f int-rep } } }
 274         { reload-from T{ spill-slot f 32 } }
 275         { reload-rep int-rep }
 276     }
 277 } [
 278     T{ live-interval-state
 279         { vreg 8 }
 280         { start 0 }
 281         { end 16 }
 282         { ranges V{ T{ live-range f 0 4 } T{ live-range f 6 10 } T{ live-range f 12 16 } } }
 283         { uses
 284           V{
 285               T{ vreg-use f 0 f int-rep }
 286               T{ vreg-use f 2 f int-rep }
 287               T{ vreg-use f 14 f int-rep } }
 288         }
 289     } 8 split-for-spill
 290     clean-up-split
 291 ] unit-test
 292
 293 H{
 294     { 1 int-rep }
 295     { 2 int-rep }
 296     { 3 int-rep }
 297 } representations set
 298
 299 {
 300     {
 301         3
 302         10
 303     }
 304 } [
 305     H{
 306         { int-regs
 307           V{
 308               T{ live-interval-state
 309                  { vreg 1 }
 310                  { reg 1 }
 311                  { start 1 }
 312                  { end 15 }
 313                  { uses V{ T{ vreg-use f 1 int-rep f } T{ vreg-use f 3 f int-rep } T{ vreg-use f 7 f int-rep } T{ vreg-use f 10 f int-rep } T{ vreg-use f 15 f int-rep } } }
 314               }
 315               T{ live-interval-state
 316                  { vreg 2 }
 317                  { reg 2 }
 318                  { start 3 }
 319                  { end 8 }
 320                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 4 f int-rep } T{ vreg-use f 8 f int-rep } } }
 321               }
 322               T{ live-interval-state
 323                  { vreg 3 }
 324                  { reg 3 }
 325                  { start 3 }
 326                  { end 10 }
 327                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 10 f int-rep } } }
 328               }
 329           }
 330         }
 331     } active-intervals set
 332     H{ } inactive-intervals set
 333     T{ live-interval-state
 334         { vreg 1 }
 335         { start 5 }
 336         { end 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                  { start 1 }
 355                  { end 15 }
 356                  { uses V{ T{ vreg-use f 1 int-rep f } } }
 357               }
 358               T{ live-interval-state
 359                  { vreg 2 }
 360                  { reg 2 }
 361                  { start 3 }
 362                  { end 8 }
 363                  { uses V{ T{ vreg-use f 3 int-rep f } T{ vreg-use f 8 f int-rep } } }
 364               }
 365           }
 366         }
 367     } active-intervals set
 368     H{ } inactive-intervals set
 369     T{ live-interval-state
 370         { vreg 3 }
 371         { start 5 }
 372         { end 5 }
 373         { uses V{ T{ vreg-use f 5 int-rep f } } }
 374     }
 375     spill-status
 376 ] unit-test
 377
 378 H{ { 1 int-rep } { 2 int-rep } } representations set
 379
 380 { } [
 381     {
 382         T{ live-interval-state
 383            { vreg 1 }
 384            { start 0 }
 385            { end 100 }
 386            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 387            { ranges V{ T{ live-range f 0 100 } } }
 388         }
 389     }
 390     H{ { int-regs { "A" } } }
 391     check-linear-scan
 392 ] unit-test
 393
 394 { } [
 395     {
 396         T{ live-interval-state
 397            { vreg 1 }
 398            { start 0 }
 399            { end 10 }
 400            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } } }
 401            { ranges V{ T{ live-range f 0 10 } } }
 402         }
 403         T{ live-interval-state
 404            { vreg 2 }
 405            { start 11 }
 406            { end 20 }
 407            { uses V{ T{ vreg-use f 11 int-rep f } T{ vreg-use f 20 f int-rep } } }
 408            { ranges V{ T{ live-range f 11 20 } } }
 409         }
 410     }
 411     H{ { int-regs { "A" } } }
 412     check-linear-scan
 413 ] unit-test
 414
 415 { } [
 416     {
 417         T{ live-interval-state
 418            { vreg 1 }
 419            { start 0 }
 420            { end 100 }
 421            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 422            { ranges V{ T{ live-range f 0 100 } } }
 423         }
 424         T{ live-interval-state
 425            { vreg 2 }
 426            { start 30 }
 427            { end 60 }
 428            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 60 f int-rep } } }
 429            { ranges V{ T{ live-range f 30 60 } } }
 430         }
 431     }
 432     H{ { int-regs { "A" } } }
 433     check-linear-scan
 434 ] unit-test
 435
 436 { } [
 437     {
 438         T{ live-interval-state
 439            { vreg 1 }
 440            { start 0 }
 441            { end 100 }
 442            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 443            { ranges V{ T{ live-range f 0 100 } } }
 444         }
 445         T{ live-interval-state
 446            { vreg 2 }
 447            { start 30 }
 448            { end 200 }
 449            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 200 f int-rep } } }
 450            { ranges V{ T{ live-range f 30 200 } } }
 451         }
 452     }
 453     H{ { int-regs { "A" } } }
 454     check-linear-scan
 455 ] unit-test
 456
 457 [
 458     {
 459         T{ live-interval-state
 460            { vreg 1 }
 461            { start 0 }
 462            { end 100 }
 463            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 100 f int-rep } } }
 464            { ranges V{ T{ live-range f 0 100 } } }
 465         }
 466         T{ live-interval-state
 467            { vreg 2 }
 468            { start 30 }
 469            { end 100 }
 470            { uses V{ T{ vreg-use f 30 int-rep f } T{ vreg-use f 100 f int-rep } } }
 471            { ranges V{ T{ live-range f 30 100 } } }
 472         }
 473     }
 474     H{ { int-regs { "A" } } }
 475     check-linear-scan
 476 ] must-fail
 477
 478 ! Problem with spilling intervals with no more usages after the spill location
 479 H{
 480     { 1 int-rep }
 481     { 2 int-rep }
 482     { 3 int-rep }
 483     { 4 int-rep }
 484     { 5 int-rep }
 485 } representations set
 486
 487 { } [
 488     {
 489         T{ live-interval-state
 490            { vreg 1 }
 491            { start 0 }
 492            { end 20 }
 493            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } T{ vreg-use f 20 f int-rep } } }
 494            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 495         }
 496         T{ live-interval-state
 497            { vreg 2 }
 498            { start 0 }
 499            { end 20 }
 500            { uses V{ T{ vreg-use f 0 int-rep f } T{ vreg-use f 10 f int-rep } T{ vreg-use f 20 f int-rep } } }
 501            { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 502         }
 503         T{ live-interval-state
 504            { vreg 3 }
 505            { start 4 }
 506            { end 8 }
 507            { uses V{ T{ vreg-use f 6 int-rep f } } }
 508            { ranges V{ T{ live-range f 4 8 } } }
 509         }
 510         T{ live-interval-state
 511            { vreg 4 }
 512            { start 4 }
 513            { end 8 }
 514            { uses V{ T{ vreg-use f 8 int-rep f } } }
 515            { ranges V{ T{ live-range f 4 8 } } }
 516         }
 517
 518         ! This guy will invoke the 'spill partially available' code path
 519         T{ live-interval-state
 520            { vreg 5 }
 521            { start 4 }
 522            { end 8 }
 523            { uses V{ T{ vreg-use f 8 int-rep f } } }
 524            { ranges V{ T{ live-range f 4 8 } } }
 525         }
 526     }
 527     H{ { int-regs { "A" "B" } } }
 528     check-linear-scan
 529 ] unit-test
 530
 531 ! Test spill-new code path
 532
 533 { } [
 534     {
 535         T{ live-interval-state
 536            { vreg 1 }
 537            { start 0 }
 538            { end 10 }
 539            { 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 } } }
 540            { ranges V{ T{ live-range f 0 10 } } }
 541         }
 542
 543         ! This guy will invoke the 'spill new' code path
 544         T{ live-interval-state
 545            { vreg 5 }
 546            { start 2 }
 547            { end 8 }
 548            { uses V{ T{ vreg-use f 8 int-rep f } } }
 549            { ranges V{ T{ live-range f 2 8 } } }
 550         }
 551     }
 552     H{ { int-regs { "A" } } }
 553     check-linear-scan
 554 ] unit-test
 555
 556 ! register-status had problems because it used map>assoc where the sequence
 557 ! had multiple keys
 558 H{
 559     { 1 int-rep }
 560     { 2 int-rep }
 561     { 3 int-rep }
 562     { 4 int-rep }
 563 } representations set
 564
 565 { { 0 10 } } [
 566     H{
 567         { int-regs
 568           {
 569               T{ live-interval-state
 570                  { vreg 1 }
 571                  { start 0 }
 572                  { end 20 }
 573                  { reg 0 }
 574                  { ranges V{ T{ live-range f 0 2 } T{ live-range f 10 20 } } }
 575                  { uses V{ 0 2 10 20 } }
 576               }
 577
 578               T{ live-interval-state
 579                  { vreg 2 }
 580                  { start 4 }
 581                  { end 40 }
 582                  { reg 0 }
 583                  { ranges V{ T{ live-range f 4 6 } T{ live-range f 30 40 } } }
 584                  { uses V{ 4 6 30 40 } }
 585               }
 586           }
 587         }
 588     } inactive-intervals set
 589     H{
 590         { int-regs
 591           {
 592               T{ live-interval-state
 593                  { vreg 3 }
 594                  { start 0 }
 595                  { end 40 }
 596                  { reg 1 }
 597                  { ranges V{ T{ live-range f 0 40 } } }
 598                  { uses V{ 0 40 } }
 599               }
 600           }
 601         }
 602     } active-intervals set
 603
 604     T{ live-interval-state
 605         { vreg 4 }
 606         { start 8 }
 607         { end 10 }
 608         { ranges V{ T{ live-range f 8 10 } } }
 609         { uses V{ T{ vreg-use f 8 int-rep f } T{ vreg-use f 10 f int-rep } } }
 610     }
 611     H{ { int-regs { 0 1 } } } register-status
 612 ] unit-test
 613
 614 { t } [
 615     T{ cfg { frame-pointer? f } } admissible-registers machine-registers =
 616 ] unit-test
 617
 618 { f } [
 619     T{ cfg { frame-pointer? t } } admissible-registers
 620     int-regs of frame-reg swap member?
 621 ] unit-test