DESCRIPTION

This file contains functions implementing a somewhat modified version of the linear scan register allocation algorithm. This algorithm assumes there's a fixed number of registers, which is not the case for Parrot. Therefore, the algorithm is modified in some places.

SYNOPSIS

  // create a new lsr allocator
  lsr_allocator *lsr = new_linear_scan_register_allocator(lexer);

  for ( ... ) {
      pir_type type = ... ;

      // create a new live interval, specifying location/ID of first statement
      live_interval *interval = new_live_interval(lsr, firstlocation, type);
  }

  // update live interval with more usage information about a variable
  interval->endpoint = ... ;

  // perform a linear scan
  linear_scan_register_allocation(lsr);

  // clean up
  destroy_linear_scan_register_allocator(lsr);

FUNCTIONS

static void reset_register_count(lsr_allocator *const lsr)

Reset the register counters; there's one counter for each register type (string, num, int, pmc).

lsr_allocator *new_linear_scan_register_allocator(struct lexer_state *lexer)

Constructor for a linear scan register allocator. Initializates the allocator, and returns it.

void destroy_linear_scan_register_allocator(lsr_allocator *lsr)

Destructor for linear scan register allocator. All live_interval objects are destroyed as well.

static void add_live_interval(lsr_allocator *const lsr, live_interval *const i, pir_type type)

Add live_interval i to the list; this list is sorted on increasing start point.

live_interval *new_live_interval(lsr_allocator *const lsr, unsigned firstuse_location, pir_type type)

Constructor for a live_interval struct object. After creating the new interval object, its startpoint and endpoint are initialized to the value in firstuse_location. Note that an interval has a type; the register allocator keeps a list of interval for each type, because obviously you can't mix different types of registers.The newly created interval is added to the list of intervals.

static void add_interval_to_active(lsr_allocator *lsr, live_interval *i, pir_type type)

Add interval i to the list of active intervals; the list is sorted on increasing endpoint.

static unsigned get_free_reg(lsr_allocator *const lsr, pir_type type)

Allocate a new register; if there's any old registers to be reused, return such a second-hand register; otherwise, allocate a brand new one.

static void add_free_reg(lsr_allocator *const lsr, unsigned regno, pir_type type)

Add register regno to the list of free regs that can be reuse.

static void remove_from_active(live_interval *i)

Remove interval i from the list of active intervals.

static void expire_old_intervals(lsr_allocator *const lsr, live_interval *i, pir_type type)

Go over all active intervals; if the endpoint of one of them is >= than i's start point, the action is aborted. This is why the active list must be sorted on increasing endpoint. Otherwise j is 'removed' from active, as it has expired. (the variable is no longer needed).

static void cache_interval_objects(lsr_allocator *const lsr, live_interval *interval)

Store the interval interval on a caching list; whenever a new live_interval object is requested, these interval objects can be re-used, instead of malloc()ing a new one.

void linear_scan_register_allocation(lsr_allocator *const lsr)

Go over all live intervals; before handling any interval, expire all old ones; they might have expired (see expire_old_intervals()). Then, allocate a new register; this can be one that was just expired.