ScEpTIC.AST.register_allocation.linear_scan package

Submodules

ScEpTIC.AST.register_allocation.linear_scan.linear_scan module

class ScEpTIC.AST.register_allocation.linear_scan.linear_scan.LinearScanRegisterAllocator(function, regs_number, reg_prefix='R', spill_prefix='%spill_', spill_type='i32')

Bases: object

Implementation of linear scan register allocation. It must be done for each function and this class refers to a single function body. Implementation details can be found here: https://www2.seas.gwu.edu/~hchoi/teaching/cs160d/linearscan.pdf

append_alloca_operation(alloca_type)

Appends an alloca operation in the code at the end of the alloca section. It returns the virtual registers contining the alloca address.

append_load_operation(position, element, load_type, is_arg_of_function_call, metadata)

Appends a load operation at the required position. It returns the virtual register containing the loaded value.

append_store_operation(position, target, value, target_type, label, metadata)

Appends a store operation at the required position.

do_call_post_processing()
Applies function call post-processing, which consists in:
  • Insertion of SaveRegistersOperation and RestoreRegistersOperation respectively before and after

    a function call

  • Updating the labels mappings (if code is appended, a label is mapped with a line which won’t be exact)

do_call_pre_processing()
Applies call pre-processing, consisting in:

  • marking load of arguments as is_arg_of_function_call

  • creating alloca-store-load for immediate

  • creating alloca-store-load for conversion and other operation s.t. their

    results are passed as arguments of the function call.

do_liveness_analysis()

This method performs the liveness analysis, which finds the live interval for each register. NB: LLVM IR is in Static Single Assignment (SSA) foarm, so for obtaining the liveness intervals is sufficient to map the definition with its last use.

do_register_allocation()

Performs the linear scan register allocation over the given function.

expire_old(instant)

Updates the active registers by removing expired ones.

run_register_allocation()

Runs the actual register allocation.

spill_at(instant)

Selects a register to be spilled in the given instant and spills it.

property spill_type

Returns an instance of the spill type, to be used in the operations.

ScEpTIC.AST.register_allocation.linear_scan.register_operations module

class ScEpTIC.AST.register_allocation.linear_scan.register_operations.RestoreRegistersOperation(save_registers_operation)

Bases: ScEpTIC.AST.elements.instruction.Instruction

Represents an operation that emulates the restoring of registers after a called function returns. It is setup by proiding the corresponding SaveRegistersOperation, from which takes the tick_count and the registers values to be restored.

get_val()
class ScEpTIC.AST.register_allocation.linear_scan.register_operations.SaveRegistersOperation(tick_count, target_reg, register_pool)

Bases: ScEpTIC.AST.elements.instruction.Instruction

Operation that emulates the saving of registers before a function call. All the register savings are done as caller-save, since saving register in the callee function will lead to multiple SaveRegistersOperation (one before each return). The instruction is set up with:

  • tick_count: consists in the number of registers used by the called function.

    In a real scenario, 1 store operation (Rx -> stack) will be inserted for each register that needs to be saved. Once this instruction is executed, the global clock will be incremented by this value ( = number of store operations that should be present)

  • target_reg: is the name of the register that will contain the return value of the call. It won’t be restored, nor saved.

NB: all registers are saved from R0 to R_n, so it is sufficient to provide the number of registers to be saved to save the first n registers.

get_val()

Save all registers, except for the target one. They will be restored by RestoreRegistersOperation. Since saving all registers or a sub-group of them won’t change anything, this function saves all of them in order to remove a control of which register needs to be saved. The overall result is the same as it only some registers are saved, since registers computed inside a function won’t have any value needed by the caller, except from the return register.

ScEpTIC.AST.register_allocation.linear_scan.register_pool module

class ScEpTIC.AST.register_allocation.linear_scan.register_pool.RegisterPool(regs_number, reg_prefix)

Bases: object

Pool of registers used by register allocation to get available registers.

free_reg(reg_name)

Marks a given register as free.

get_reg()

Returns a free register. If no register is available, it raises a RegAllocException The returned register is marked as busy.

Module contents

ScEpTIC.AST.register_allocation.linear_scan.allocate_registers(functions, registers_number, reg_prefix='R', spill_prefix='%spill_', spill_type='i32')

This functions performs the register allocation on the whole code (analysis, pre-processing, register allocation, and post-processing)

ScEpTIC.AST.register_allocation.linear_scan.compute_registers_usage(functions, registers_number)

This function estimates the maximum register usage of each code’s function and is used to estimate the actual number of operation performed for saving and restoring registers before a function call. Register allocation must be performed before running this function, so to have the number of registers used.

A good partitioned register allocation will make registers from frequent functions call to not overlap, so to minimize the register saving operations before a function call.

To estimate this scenario, is sufficient to find the number of registers used by each function (including the ones from the calls present in such function).

The number of registers needed by a function is computed as:

max(registers_used_by_internal_calls) + registers_used_by_function NB: recursive calls are ignored, since they will save the number of registers used by the current function.

If this number is lower than the number of available registers, no saving is needed before the call.

The overall number of register usage is calculated iteratively, since cycles can be possible (a calls b; b calls a;) If the number of needed registers exceed the number of available ones, a cycle-dependecy is found and thus all registers should be saved before such call.

Initial setup: each function uses reg_count as max_reg_usage, calls is initialized with the functions called

Iterate:

find the max_reg_usage among the functions in calls set max_reg_usage = max_reg_usage of function calls + reg_count if max_reg_usage > max_available_registers -> max_reg_usage = max_available_registers

until a fixed point is reached

Once the max_reg_usage is found, call post-processing can be done (addition of registers saving/restoring routines)