compilers/pirc/src/pirregalloc.c

   1 /*
   2  * $Id$
   3  * Copyright (C) 2008-2009, Parrot Foundation.
   4  */
   5 #include <stdio.h>
   6 #include "pircompiler.h"
   7 #include "pirregalloc.h"
   8 #include "parrot/parrot.h"
   9
  10 /*
  11
  12 =head1 DESCRIPTION
  13
  14 This file contains functions implementing a somewhat modified version of the
  15 linear scan register allocation algorithm. This algorithm assumes there's a
  16 fixed number of registers, which is not the case for Parrot. Therefore,
  17 the algorithm is modified in some places.
  18
  19 =head1 SYNOPSIS
  20
  21   // create a new lsr allocator
  22   lsr_allocator *lsr = new_linear_scan_register_allocator(lexer);
  23
  24   for ( ... ) {
  25       pir_type type = ... ;
  26
  27       // create a new live interval, specifying location/ID of first statement
  28       live_interval *interval = new_live_interval(lsr, firstlocation, type);
  29   }
  30
  31   // update live interval with more usage information about a variable
  32   interval->endpoint = ... ;
  33
  34   // perform a linear scan
  35   linear_scan_register_allocation(lsr);
  36
  37   // clean up
  38   destroy_linear_scan_register_allocator(lsr);
  39
  40 =head1 FUNCTIONS
  41
  42 =over 4
  43
  44 =cut
  45
  46 */
  47
  48 /*
  49
  50 =item C<static void reset_register_count(lsr_allocator * const lsr)>
  51
  52 Reset the register counters; there's one counter for each register
  53 type (string, num, int, pmc).
  54
  55 =cut
  56
  57 */
  58 static void
  59 reset_register_count(ARGIN(lsr_allocator * const lsr))
  60 {
  61     ASSERT_ARGS(reset_register_count)
  62     int i;
  63     /* the "r" field keeps track of the number of registers that must be allocated by
  64      * parrot. In the original implementation, "r" is constant, and indicates the number
  65      * of available registers. In parrot, this is flexible, so we increment it only
  66      * if necessary. However, the minimum value for "r" must be 1, in order for the
  67      * algorithm to work properly. After all, having 0 registers doesn't make sense.
  68      * Initialize r for each type to 1 here:
  69      */
  70     for (i = 0; i < 4; ++i)
  71         lsr->r[i] = 1;
  72 }
  73
  74 /* HEADERIZER HFILE: compilers/pirc/src/pirregalloc.h */
  75
  76 /* HEADERIZER BEGIN: static */
  77 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END.  Your changes will be lost. */
  78
  79 static void add_free_reg(
  80     ARGIN(lsr_allocator * const lsr),
  81     unsigned regno,
  82     pir_type type)
  83         __attribute__nonnull__(1);
  84
  85 static void add_interval_to_active(
  86     ARGIN(lsr_allocator *lsr),
  87     ARGIN(live_interval * const i),
  88     pir_type type)
  89         __attribute__nonnull__(1)
  90         __attribute__nonnull__(2);
  91
  92 static void add_live_interval(
  93     ARGIN(lsr_allocator * const lsr),
  94     ARGIN(live_interval * const i),
  95     pir_type type)
  96         __attribute__nonnull__(1)
  97         __attribute__nonnull__(2);
  98
  99 static void cache_interval_object(
 100     ARGIN(lsr_allocator * const lsr),
 101     ARGIN(live_interval * interval))
 102         __attribute__nonnull__(1)
 103         __attribute__nonnull__(2);
 104
 105 static void expire_old_intervals(
 106     ARGIN(lsr_allocator * const lsr),
 107     ARGIN(live_interval * const i),
 108     pir_type type)
 109         __attribute__nonnull__(1)
 110         __attribute__nonnull__(2);
 111
 112 static unsigned get_free_reg(
 113     ARGIN(lsr_allocator * const lsr),
 114     pir_type type)
 115         __attribute__nonnull__(1);
 116
 117 static unsigned lengthi(ARGIN_NULLOK(live_interval *list));
 118 static void remove_from_active(ARGMOD(live_interval *i))
 119         __attribute__nonnull__(1)
 120         FUNC_MODIFIES(*i);
 121
 122 static void reset_register_count(ARGIN(lsr_allocator * const lsr))
 123         __attribute__nonnull__(1);
 124
 125 #define ASSERT_ARGS_add_free_reg __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 126        PARROT_ASSERT_ARG(lsr))
 127 #define ASSERT_ARGS_add_interval_to_active __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 128        PARROT_ASSERT_ARG(lsr) \
 129     , PARROT_ASSERT_ARG(i))
 130 #define ASSERT_ARGS_add_live_interval __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 131        PARROT_ASSERT_ARG(lsr) \
 132     , PARROT_ASSERT_ARG(i))
 133 #define ASSERT_ARGS_cache_interval_object __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 134        PARROT_ASSERT_ARG(lsr) \
 135     , PARROT_ASSERT_ARG(interval))
 136 #define ASSERT_ARGS_expire_old_intervals __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 137        PARROT_ASSERT_ARG(lsr) \
 138     , PARROT_ASSERT_ARG(i))
 139 #define ASSERT_ARGS_get_free_reg __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 140        PARROT_ASSERT_ARG(lsr))
 141 #define ASSERT_ARGS_lengthi __attribute__unused__ int _ASSERT_ARGS_CHECK = (0)
 142 #define ASSERT_ARGS_remove_from_active __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 143        PARROT_ASSERT_ARG(i))
 144 #define ASSERT_ARGS_reset_register_count __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 145        PARROT_ASSERT_ARG(lsr))
 146 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END.  Your changes will be lost. */
 147 /* HEADERIZER END: static */
 148
 149 /*
 150
 151 =item C<lsr_allocator * new_linear_scan_register_allocator(struct lexer_state
 152 *lexer)>
 153
 154 Constructor for a linear scan register allocator.
 155 Initializes the allocator, and returns it.
 156
 157 =cut
 158
 159 */
 160 PARROT_CAN_RETURN_NULL
 161 lsr_allocator *
 162 new_linear_scan_register_allocator(ARGIN_NULLOK(struct lexer_state *lexer))
 163 {
 164     ASSERT_ARGS(new_linear_scan_register_allocator)
 165     lsr_allocator *lsr = (lsr_allocator *)mem_sys_allocate_zeroed(sizeof (lsr_allocator));
 166
 167     lsr->lexer = lexer;
 168
 169     return lsr;
 170 }
 171
 172 /*
 173
 174 XXX debug function only
 175
 176 */
 177 void print_list(char *msg, live_interval *i);
 178 void
 179 print_list(ARGIN(char *msg), ARGIN(live_interval *i))
 180 {
 181     fprintf(stderr, "%s: ", msg);
 182     while (i) {
 183         fprintf(stderr, "[%d] ", i->endpoint);
 184         i = i->nexta;
 185     }
 186     fprintf(stderr, "\n");
 187 }
 188
 189 /*
 190
 191 =item C<void destroy_linear_scan_register_allocator(lsr_allocator *lsr)>
 192
 193 Destructor for linear scan register allocator. All live_interval
 194 objects are destroyed as well.
 195
 196 =cut
 197
 198 */
 199 void
 200 destroy_linear_scan_register_allocator(ARGMOD(lsr_allocator *lsr))
 201 {
 202     ASSERT_ARGS(destroy_linear_scan_register_allocator)
 203     pir_type type;
 204     live_interval *i;
 205
 206     for (type = 0; type < 4; ++type) {
 207         live_interval *iter = lsr->intervals[type];
 208         while (iter) {
 209             iter = iter->nexti;
 210             mem_sys_free(iter->previ);
 211         }
 212     }
 213
 214     /* free all cached interval objects */
 215     i = lsr->cached_intervals;
 216     while (i != NULL) {
 217         live_interval *tmp = i;
 218         i = i->nextc;
 219         mem_sys_free(tmp);
 220     }
 221
 222     mem_sys_free(lsr);
 223 }
 224
 225 /*
 226
 227 =item C<static unsigned lengthi(live_interval *list)>
 228
 229 XXX debug function only.
 230 Return length of list C<list>
 231
 232 =cut
 233
 234 */
 235 static unsigned
 236 lengthi(ARGIN_NULLOK(live_interval *list))
 237 {
 238     ASSERT_ARGS(lengthi)
 239     unsigned len = 0;
 240
 241     while (list) {
 242         ++len;
 243         list = list->nexti;
 244     }
 245     return len;
 246 }
 247
 248 /*
 249
 250 =item C<static void add_live_interval(lsr_allocator * const lsr, live_interval *
 251 const i, pir_type type)>
 252
 253 Add live_interval C<i> to the list; this list is sorted on increasing
 254 start point.
 255
 256 =cut
 257
 258 */
 259 static void
 260 add_live_interval(ARGIN(lsr_allocator * const lsr),
 261     ARGIN(live_interval * const i), pir_type type)
 262 {
 263     ASSERT_ARGS(add_live_interval)
 264     live_interval *iter = lsr->intervals[type];
 265
 266     /* if there's no interval for the specified type, insert i as the first one and return */
 267     if (iter == NULL) {
 268         lsr->intervals[type] = i;
 269         /* print_list("intervals (1): ", lsr->intervals[type]); */
 270         return;
 271     }
 272
 273     /* search for the right point to insert */
 274
 275     while (iter->nexti && iter->startpoint < i->startpoint) {
 276         iter = iter->nexti;
 277     }
 278
 279     /* at this point iter->startpoint >= i->startpoint, or iter->nexti is NULL */
 280
 281     if (iter->nexti) {
 282         PARROT_ASSERT(iter->startpoint >= i->startpoint);
 283         /* iter->startpoint >= i->startpoint */
 284         /* insert i before iter */
 285         i->nexti = iter;
 286         if (iter->previ) {
 287             i->previ = iter->previ;
 288             i->previ->nexti = i;
 289         }
 290         else {
 291             lsr->intervals[type] = i;
 292         }
 293         iter->previ = i;
 294
 295         /* print_list("intervals (2): ", lsr->intervals[type]); */
 296     }
 297     else {
 298         /* iter->nexti is NULL */
 299         if (iter->startpoint < i->startpoint) { /* add i after iter */
 300             iter->nexti = i;
 301             i->previ = iter;
 302         }
 303         else { /* iter->startpoint >= i->startpoint */
 304             /* insert i before iter */
 305             i->nexti = iter;
 306             if (iter->previ) {
 307                 i->previ = iter->previ;
 308                 i->previ->nexti = i;
 309             }
 310             else {
 311                 lsr->intervals[type] = i;
 312             }
 313             iter->previ = i;
 314         }
 315
 316         /* print_list("intervals (3): ", lsr->intervals[type]);*/
 317     }
 318
 319     /* fprintf(stderr, "live intervals: #%d\n", lengthi(lsr->intervals[type])); */
 320
 321 }
 322
 323
 324
 325 /*
 326
 327 =item C<live_interval * new_live_interval(lsr_allocator * const lsr, unsigned
 328 firstuse_location, pir_type type)>
 329
 330 Constructor for a live_interval struct object. After creating the new interval object,
 331 its startpoint and endpoint are initialized to the value in C<firstuse_location>. Note
 332 that an interval has a type; the register allocator keeps a list of interval for each
 333 type, because obviously you can't mix different types of registers.
 334
 335 The newly created interval is added to the list of intervals.
 336
 337 =cut
 338
 339 */
 340 PARROT_CAN_RETURN_NULL
 341 PARROT_MALLOC
 342 PARROT_WARN_UNUSED_RESULT
 343 live_interval *
 344 new_live_interval(ARGIN(lsr_allocator * const lsr),
 345         unsigned firstuse_location, pir_type type)
 346 {
 347     ASSERT_ARGS(new_live_interval)
 348     live_interval *i;
 349     /* check whether there's an interval object that we can re-use, to prevent
 350      * memory malloc() and free()s.
 351      */
 352     if (lsr->cached_intervals) {
 353
 354         i = lsr->cached_intervals;
 355         lsr->cached_intervals = i->nextc;
 356
 357         /* clear fields */
 358         i->nexti = i->previ   = NULL;
 359         i->nexta = i->preva   = NULL;
 360         i->nextc = NULL;
 361     }
 362     else {
 363         /* there's no interval object to be re-used (none allocated yet, or all are used). */
 364         i = (live_interval *)mem_sys_allocate_zeroed(sizeof (live_interval));
 365     }
 366
 367     /* this is the first usage of the register, and up to now also the last */
 368     i->startpoint = i->endpoint = firstuse_location;
 369
 370     add_live_interval(lsr, i, type);
 371     return i;
 372
 373 }
 374
 375
 376
 377
 378 /*
 379
 380 =item C<static void add_interval_to_active(lsr_allocator *lsr, live_interval *
 381 const i, pir_type type)>
 382
 383 Add interval C<i> to the list of active intervals; the list is sorted
 384 on increasing endpoint.
 385
 386 =cut
 387
 388 */
 389 static void
 390 add_interval_to_active(ARGIN(lsr_allocator *lsr),
 391         ARGIN(live_interval * const i), pir_type type)
 392 {
 393     ASSERT_ARGS(add_interval_to_active)
 394     live_interval *iter = lsr->active[type];
 395
 396     /* if there's no active intervals, set i as first */
 397     if (iter == NULL) {
 398         lsr->active[type] = i;
 399         /* print_list("(1)", lsr->active[type]); */
 400         return;
 401     }
 402
 403     /* look for the right place to insert; sort on increasing end point */
 404     while (iter->nexta && iter->endpoint < i->endpoint) {
 405         iter = iter->nexta;
 406     }
 407
 408     /* at this point iter->endpoint >= i->endpoint, or, iter->next is NULL, or both */
 409
 410     if (iter->nexta) {
 411
 412         PARROT_ASSERT(iter->endpoint >= i->endpoint);
 413
 414         i->nexta = iter;
 415         if (iter->preva) {
 416             i->preva = iter->preva;
 417             i->preva->nexta = i;
 418         }
 419         else {
 420             lsr->active[type] = i;
 421         }
 422         iter->preva = i;
 423
 424         /* print_list("(2)", lsr->active[type]); */
 425     }
 426     else { /* iter->next is NULL */
 427
 428         if (iter->endpoint > i->endpoint) { /* iter > i, so insert before iter */
 429             i->nexta = iter;
 430             if (iter->preva) {
 431                 i->preva = iter->preva;
 432                 i->preva->nexta = i;
 433             }
 434             else { /* if a node has no prev pointer, then it's the first */
 435                 lsr->active[type] = i;
 436             }
 437             iter->preva = i;
 438
 439         }
 440         else { /* i->endpoint >= iter->endpoint */
 441             /* add i after iter; i->next is NULL, so it's the last item */
 442             i->preva    = iter;
 443             iter->nexta = i;
 444         }
 445         /* print_list("(3)", lsr->active[type]); */
 446     }
 447 }
 448
 449 /*
 450
 451 =item C<static unsigned get_free_reg(lsr_allocator * const lsr, pir_type type)>
 452
 453 Allocate a new register; if there's any old registers to be reused, return
 454 such a second-hand register; otherwise, allocate a brand new one.
 455
 456 =cut
 457
 458 */
 459 static unsigned
 460 get_free_reg(ARGIN(lsr_allocator * const lsr), pir_type type)
 461 {
 462     ASSERT_ARGS(get_free_reg)
 463     /* if there's any second hand register for the requested type, return that. */
 464     if (lsr->free_regs[type]) {
 465         free_reg *available  = lsr->free_regs[type];
 466         lsr->free_regs[type] = available->next;
 467
 468         /* store the free_reg object for later re-use */
 469         available->next      = lsr->cached_regs;
 470         lsr->cached_regs     = available;
 471
 472         fprintf(stderr, "get_free_reg(): cached: %d\n", available->regno);
 473         return available->regno;
 474     }
 475     else {
 476         /* no free regs, allocate a new one. Note that as r is initialized to 1,
 477          * and parrot register numbering starts at 0, substract 1 here.
 478          * (initializing r to 0 will make the algorithm stop working properly.)
 479          */
 480         unsigned reg = lsr->r[type] - 1;
 481         lsr->r[type]++;
 482         fprintf(stderr, "get_free_reg(): non-cached: %d\n", reg);
 483         return reg;
 484     }
 485 }
 486
 487 /*
 488
 489 =item C<static void add_free_reg(lsr_allocator * const lsr, unsigned regno,
 490 pir_type type)>
 491
 492 Add register C<regno> to the list of free regs that can be reuse.
 493
 494 =cut
 495
 496 */
 497 static void
 498 add_free_reg(ARGIN(lsr_allocator * const lsr), unsigned regno, pir_type type)
 499 {
 500     ASSERT_ARGS(add_free_reg)
 501
 502     free_reg *reg;
 503
 504     /* fprintf(stderr, "add_free_reg(): %u\n", regno); */
 505
 506     /* if we still had some free_reg object lying around, re-use that one;
 507      * if not, then allocate a new one.
 508      */
 509     if (lsr->cached_regs) {
 510         reg = lsr->cached_regs;
 511         lsr->cached_regs = reg->next;
 512     }
 513     else
 514         reg = (free_reg *)mem_sys_allocate_zeroed(sizeof (free_reg));
 515
 516     /* store the register number for re-use. */
 517     reg->regno = regno;
 518
 519     /* link the free_reg object in list of available registers */
 520     reg->next = lsr->free_regs[type];
 521     lsr->free_regs[type] = reg;
 522 }
 523
 524 /*
 525
 526 =item C<static void remove_from_active(live_interval *i)>
 527
 528 Remove interval C<i> from the list of active intervals.
 529
 530 =cut
 531
 532 */
 533 static void
 534 remove_from_active(ARGMOD(live_interval *i))
 535 {
 536     ASSERT_ARGS(remove_from_active)
 537     /* if it has a previous node, that previous node's next is set
 538      * to i's next.
 539      */
 540     if (i->preva)
 541         i->preva->nexta = i->nexta;
 542     /* if it has a next node, that next node's previous is set to
 543      * i's previous.
 544      */
 545     if (i->nexta)
 546         i->nexta->preva = i->preva;
 547 }
 548
 549
 550
 551 /*
 552
 553 =item C<static void expire_old_intervals(lsr_allocator * const lsr,
 554 live_interval * const i, pir_type type)>
 555
 556 Go over all active intervals; if the endpoint of one of them is >= than
 557 C<i>'s start point, the action is aborted. This is why the C<active> list must be
 558 sorted on increasing endpoint. Otherwise C<j> is 'removed' from
 559 active, as it has expired. (the variable is no longer needed).
 560
 561 =cut
 562
 563 */
 564 static void
 565 expire_old_intervals(ARGIN(lsr_allocator * const lsr),
 566         ARGIN(live_interval * const i), pir_type type)
 567 {
 568     ASSERT_ARGS(expire_old_intervals)
 569
 570     live_interval *j;
 571
 572     for (j = lsr->active[type]; j != NULL; j = j->nexta) {
 573         if (j->endpoint >= i->startpoint) {
 574             return;
 575         }
 576
 577         /* don't remove from active if a :unique_reg flag was set */
 578         if (!TEST_FLAG(j->flags, INTERVAL_FLAG_UNIQUE_REG)) {
 579             remove_from_active(j);
 580             add_free_reg(lsr, j->realreg, type);
 581         }
 582     }
 583
 584 }
 585
 586 /*
 587
 588 =item C<static void cache_interval_object(lsr_allocator * const lsr,
 589 live_interval * interval)>
 590
 591 Store the interval C<interval> on a caching list; whenever a new C<live_interval>
 592 object is requested, these interval objects can be re-used, instead of malloc()ing
 593 a new one.
 594
 595 =cut
 596
 597 */
 598 static void
 599 cache_interval_object(ARGIN(lsr_allocator * const lsr),
 600         ARGIN(live_interval * interval))
 601 {
 602     ASSERT_ARGS(cache_interval_object)
 603     interval->nextc = lsr->cached_intervals;
 604     lsr->cached_intervals = interval;
 605 }
 606
 607 /*
 608
 609 =item C<void linear_scan_register_allocation(lsr_allocator * const lsr)>
 610
 611 Go over all live intervals; before handling any interval, expire all old ones;
 612 they might have expired (see expire_old_intervals()). Then, allocate a new
 613 register; this can be one that was just expired.
 614
 615 =cut
 616
 617 */
 618 void
 619 linear_scan_register_allocation(ARGIN(lsr_allocator * const lsr))
 620 {
 621     ASSERT_ARGS(linear_scan_register_allocation)
 622     live_interval * i;
 623     pir_type type = 0; /* types run from 0 to 4; see pircompunit.h */
 624
 625     reset_register_count(lsr);
 626
 627     for (type = 0; type < 4; ++type) { /* handle each of the 4 parrot types separately. */
 628
 629         /* cache the objects on the active list for reuse */
 630         for (i = lsr->active[type]; i != NULL; i = i->nexta)
 631             cache_interval_object(lsr, i);
 632
 633         /* initialize active intervals list to NULL */
 634         lsr->active[type] = NULL;
 635
 636         /* fprintf(stderr, "Lin.scan.reg.alloc.: %u variables to be mapped\n",
 637            lengthi(lsr->intervals[type]));
 638         */
 639         for (i = lsr->intervals[type]; i != NULL; i = i->nexti) {
 640
 641             /* expire all intervals whose endpoint is smaller than i's start
 642              * point; that means that i can be mapped to a register that was
 643              * previously assigned to one of the expired intervals; that one
 644              * is no longer needed (hence it expired).
 645              */
 646             expire_old_intervals(lsr, i, type);
 647
 648             /* get a free register */
 649             i->realreg = get_free_reg(lsr, type);
 650
 651
 652             /* update the symbol/pir_reg with this newly allocated reg */
 653             *i->color = i->realreg;
 654
 655             /* add this variable to the list of active ones */
 656             add_interval_to_active(lsr, i, type);
 657         }
 658
 659          /* cache the objects on the list for reuse */
 660         for (i = lsr->intervals[type]; i != NULL; i = i->nexti)
 661             cache_interval_object(lsr, i);
 662
 663         /* clear list of intervals */
 664         lsr->intervals[type] = NULL;
 665
 666         /* lsr->r is 1 too high w.r.t. the actual register usage, subtract now,
 667          * this is safe, because lsr->r[type] will no longer be used, as type will
 668          * be incremented.
 669          */
 670         --lsr->r[type];
 671     }
 672
 673
 674     /* update the register usage in the current subroutine structure. */
 675     update_sub_register_usage(lsr->lexer, lsr->r);
 676
 677 }
 678
 679
 680 /*
 681
 682 =back
 683
 684 =cut
 685
 686 */
 687
 688 /*
 689  * Local variables:
 690  *   c-file-style: "parrot"
 691  * End:
 692  * vim: expandtab shiftwidth=4:
 693  */
 694
 695