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