Register allocation pass implementation. More...

#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include "reg_alloc.h"
#include "target_info.h"
#include "errors.h"
#include "codegen.h"
#include "program.h"
#include "list.h"
#include "cfg.h"
#include "target_asm_print.h"

Data Structures
struct	t_liveInterval
	Structure describing a live interval of a register in a program. More...
struct	t_spillLocation
struct	t_regAllocator
	Structure encapsulating the state of the register allocator. More...
struct	t_spillInstrArgState
struct	t_spillRegState
	Structure representing the current state of a spill-reserved register. More...
struct	t_spillState
	Spill register slots state. More...

Macros
#define	MAX_INSTR_ARGS (CFG_MAX_DEFS + CFG_MAX_USES)
	Maximum amount of arguments to an instruction.
#define	RA_SPILL_REQUIRED ((t_regID)(-2))
	Fictitious register ID associated to registers to be spilled.
#define	RA_REGISTER_INVALID ((t_regID)(-1))
	Fictitious register ID marking currently unallocated temporaries.

Functions
t_regAllocator *	newRegAllocator (t_program *program)
void	deleteRegAllocator (t_regAllocator *RA)
void	regallocRun (t_regAllocator *regalloc)
void	dumpVariableBindings (t_regAllocator RA, FILE fout)
void	dumpLiveIntervals (t_listNode intervals, FILE fout)
void	regallocDump (t_regAllocator RA, FILE fout)

Detailed Description

Register allocation pass implementation.

Definition in file reg_alloc.c.

Data Structure Documentation

◆ t_liveInterval

struct t_liveInterval

Structure describing a live interval of a register in a program.

Definition at line 27 of file reg_alloc.c.

Data Fields
int	endPoint	Index of the last instruction that uses/defines this register.
t_listNode *	mcRegConstraints	List of all physical registers where this temporary register can be allocated.
int	startPoint	Index of the first instruction that uses/defines this register.
t_regID	tempRegID	Identifier of the register.

◆ t_spillLocation

struct t_spillLocation

Structure used for mapping a spilled temporary register to the label pointing to its physical storage location in memory.

Definition at line 41 of file reg_alloc.c.

Data Fields
t_label *	label	The label pointing to the spill area.
t_regID	tempRegID	The spilled temporary register ID.

◆ t_regAllocator

struct t_regAllocator

Structure encapsulating the state of the register allocator.

Opaque register allocator object.

Definition at line 49 of file reg_alloc.c.

Data Fields
t_regID *	bindings	Pointer to a dynamically allocated array which maps every temporary register to the corresponding physical register. Temporary registers allocated to a spill location are marked by the RA_SPILL_REQUIRED virtual register ID.
t_cfg *	graph	The temporary control flow graph produced from the program.
t_listNode *	liveIntervals	List of live intervals, ordered depending on their start index.
t_program *	program	The program where register allocation needs to be performed.
t_listNode *	spills	List of spill locations for temporary registers in the program.
int	tempRegNum	Number of temporary registers in the program.

◆ t_spillInstrArgState

struct t_spillInstrArgState

Structure representing the current state of an instruction argument during the spill load/store materialization process.

Definition at line 69 of file reg_alloc.c.

Data Fields
bool	isDestination	If the register is a destination register.
t_instrArg *	reg	The instruction argument structure.
int	spillSlot	The physical spill register index where the argument will be materialized, or -1 otherwise.

◆ t_spillRegState

struct t_spillRegState

Structure representing the current state of a spill-reserved register.

Definition at line 80 of file reg_alloc.c.

Data Fields
t_regID	assignedTempReg	Temporary register ID associated to this spill register.
bool	needsWB	Non-zero if at least one of the instructions wrote something new into the spill register, and the value has not been written to the spill memory location yet.

◆ t_spillState

struct t_spillState

Spill register slots state.

Definition at line 90 of file reg_alloc.c.

Data Fields
t_spillRegState	regs[NUM_SPILL_REGS]	each array element corresponds to one of the registers reserved for spilled variables, ordered by ascending register number.

Macro Definition Documentation

◆ MAX_INSTR_ARGS

#define MAX_INSTR_ARGS (CFG_MAX_DEFS + CFG_MAX_USES)

Maximum amount of arguments to an instruction.

Definition at line 18 of file reg_alloc.c.

◆ RA_REGISTER_INVALID

#define RA_REGISTER_INVALID ((t_regID)(-1))

Fictitious register ID marking currently unallocated temporaries.

Definition at line 23 of file reg_alloc.c.

◆ RA_SPILL_REQUIRED

#define RA_SPILL_REQUIRED ((t_regID)(-2))

Fictitious register ID associated to registers to be spilled.

Definition at line 21 of file reg_alloc.c.

Function Documentation

◆ dumpLiveIntervals()

void dumpLiveIntervals	(	t_listNode *	intervals,
		FILE *	fout )

Definition at line 900 of file reg_alloc.c.

◆ dumpVariableBindings()

void dumpVariableBindings	(	t_regAllocator *	RA,
		FILE *	fout )

Definition at line 858 of file reg_alloc.c.

Data Structures

Macros

Functions