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