scale.backend
Class RegisterAllocator

java.lang.Object
  scale.backend.RegisterAllocator

Direct Known Subclasses:

QDRA

public abstract class RegisterAllocator
extends java.lang.Object

This is the base class for all register allocators.

$Id: RegisterAllocator.java,v 1.55 2007-04-12 20:09:29 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

Field Summary

static boolean	classTrace True if traces are to be performed.
protected Generator	generator The backend in use for code generation.
protected BitVect[]	regDef regDef[instruction,register] is true if instruction sets the register.
protected int[]	regDefCnt A count of the number of times the register was set - indexed by register number.
protected RegisterSet	registers The register set definition in use for allocation.
protected BitVect[]	regMod regMod[instruction,register] is true if instruction destroys the value in the register.
protected long[]	regStrength The register strength - indexed by register number.
protected BitVect[]	regUse regUse[instruction,register] is true if instruction uses the register.
protected int[]	regUseCnt A count of the number of times the register was referenced - indexed by register number.
static int	spillLoadCount
static int	spillStoreCount
protected boolean	trace True if tracing requested.

Constructor Summary

RegisterAllocator(Generator generator, boolean trace)

Method Summary

abstract int[]	allocate(Instruction first) Determine a mapping from virtual registers to real registers.
protected BitVect[]	compress(BitVect[] in) Remove un-needed bit vectors from the liveness array.
protected BitVect[]	computeLiveness(Instruction[] insts) Compute the liveness for every register at every instruction.
protected void	computePredecessors(Instruction first) The predecessors of labels are determined.
void	defRegister(int inst, int reg) Specify that instruction inst defines the value of register reg.
long	getStrength(int register) Return the importance of the register.
protected Instruction[]	linearize(Instruction first) Linearize the instructions so that an index can be used to access an instruction.
void	modRegister(int inst, int reg) Specify that instruction inst destroys the value in register reg.
protected void	spill(int reg, Instruction first, boolean aggressive) Insert loads and stores to shorten the liveness ranges of a virtual register.
static int	spillLoads() Return the number of spill loads inserted.
static int	spillStores() Return the number of spill stores inserted.
protected BitVect[]	transpose(BitVect[] in, int n) Convert a m by n bit array to an n by m bit array.
void	useRegister(int inst, int reg, int strength) Specify that instruction inst uses the value of register reg.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

spillLoadCount

public static int spillLoadCount

spillStoreCount

public static int spillStoreCount

classTrace

public static boolean classTrace

True if traces are to be performed.

registers

protected RegisterSet registers

The register set definition in use for allocation.

generator

protected Generator generator

The backend in use for code generation.

regUse

protected BitVect[] regUse

regUse[instruction,register] is true if instruction uses the register.

regDef

protected BitVect[] regDef

regDef[instruction,register] is true if instruction sets the register.

regMod

protected BitVect[] regMod

regMod[instruction,register] is true if instruction destroys the value in the register.

regStrength

protected long[] regStrength

The register strength - indexed by register number.

regDefCnt

protected int[] regDefCnt

A count of the number of times the register was set - indexed by register number.

regUseCnt

protected int[] regUseCnt

A count of the number of times the register was referenced - indexed by register number.

trace

protected boolean trace

True if tracing requested.

Constructor Detail

RegisterAllocator

public RegisterAllocator(Generator generator,
                         boolean trace)

Method Detail

spillLoads

public static int spillLoads()

Return the number of spill loads inserted.

spillStores

public static int spillStores()

Return the number of spill stores inserted.

useRegister

public void useRegister(int inst,
                        int reg,
                        int strength)

Specify that instruction inst uses the value of register reg. Uses must be specified before definitions.

Parameters:

inst - is the instruction index

reg - is the register

strength - is the importance of the instruction

See Also:

defRegister(int,int), Instruction.specifyRegisterUsage(scale.backend.RegisterAllocator, int, int)

defRegister

public void defRegister(int inst,
                        int reg)

Specify that instruction inst defines the value of register reg. Uses must be specified before definitions.

Parameters:

inst - is the instruction index

reg - is the register

See Also:

useRegister(int,int,int), Instruction.specifyRegisterUsage(scale.backend.RegisterAllocator, int, int)

modRegister

public void modRegister(int inst,
                        int reg)

Specify that instruction inst destroys the value in register reg.

Parameters:

inst - is the instruction index

reg - is the register

See Also:

useRegister(int,int,int), Instruction.specifyRegisterUsage(scale.backend.RegisterAllocator, int, int)

getStrength

public long getStrength(int register)

Return the importance of the register. This information must be specified.

See Also:

useRegister(int,int,int)

allocate

public abstract int[] allocate(Instruction first)

Determine a mapping from virtual registers to real registers. This may involve the insertion of instructions to load and store the value of a virtual register.

Parameters:

first - is the first instruction in the instruction sequence

Returns:

the mapping from virtual register to real register

linearize

protected Instruction[] linearize(Instruction first)

Linearize the instructions so that an index can be used to access an instruction. The instruction's index is set as the instruction's tag value. Obtain the register usage by instruction along with the importance of each instruction.

Parameters:

first - is the first instruction

computeLiveness

protected BitVect[] computeLiveness(Instruction[] insts)

Compute the liveness for every register at every instruction.

compress

protected BitVect[] compress(BitVect[] in)

Remove un-needed bit vectors from the liveness array. If two consecutive bit vectors are equivalent, the second one is removed. This method modifies the argument.

transpose

protected BitVect[] transpose(BitVect[] in,
                              int n)

Convert a m by n bit array to an n by m bit array. The bit array is represented by an array of bit vectors.

Parameters:

n - is the max in columns

computePredecessors

protected void computePredecessors(Instruction first)

The predecessors of labels are determined.

Parameters:

first - is the first instruction

spill

protected void spill(int reg,
                     Instruction first,
                     boolean aggressive)

Insert loads and stores to shorten the liveness ranges of a virtual register.

Parameters:

reg - is the register to spill

first - is the first instruction of the program

aggressive - is true if aggressive spilling should be used