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