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.

FUNCTIONS

lsr_allocator *new_linear_scan_register_allocator(void)

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

void destroy_linear_scan_regiser_allocator(lsr_allocator *lsr)

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

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.

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.

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).

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.