edu.ustc.cs.compile.arch.x86.regalloc
类 RegAllocator

java.lang.Object
  edu.ustc.cs.compile.arch.x86.regalloc.RegAllocator

public class RegAllocator
extends java.lang.Object

This class implements a simple X86 register allocator.we use a greedy-like local algorithm to allocate registers. There are no basic block breaking down, no data flow analysis. Given a String as an variable name, this allocator returns an available register. Meanwhile it may spill registers.
This register allocator asserts that:
1. at one time there is no more than one value stored in a register:
for example: a = b; in some register allocator, variable a and b shares the same register. However, to keep the allocator simple, in this allocate we do not put them together.
2. we do not increment esp pointer so that in this version of regAllocator it is very simple.

The following are some of the register allocator's usage:
1. To get a free register, use getReg(java.lang.String) .
2. if getReg(java.lang.String) returns null, it implies that all the registers in the register pool are occupied. We have to spill out a register so that we can use the present one by asking selectReg() to select one for us, let's say it is %eax.
3. Now we have to spill %eax: call spill(edu.ustc.cs.compile.arch.x86.X86Register) with argument X86Register.EAX, and we can get a sequence of spilling code. After we add the spilling code to our assembly statement sequence, %eax is now free.

字段摘要

private java.util.LinkedList<java.lang.Integer>	availableMemSlot
private java.util.LinkedList<X86Register>	lruList
private java.util.HashMap<java.lang.String,java.lang.Integer>	name2place
private int	numOfMemAlloc
private java.util.HashMap<X86Register,java.lang.String>	reg2name

构造函数摘要

RegAllocator()

方法摘要

X86Register	getAFreeRegister() Uses LRU to determine a free register and returns it.
AssemblySequence	getMem2Reg(java.lang.String valName, X86Register reg) Generates a chain of instructions the fetches a variable from the memory to a register. if in stack we do not have the record of the variable, it returns null.
Instruct.Operand	getPositionInMem(java.lang.String name) Returns the stack address corresponding to a variable register.
Instruct.Operand	getPositionInMem(X86Register reg) Returns the stack address corresponding to a variable or a register.
X86Register	getReg(java.lang.String valName) Returns a register that is free to store the variable, or null if there are no available allocator.
boolean	hasFreeReg() Returns a free register that is free or null if there are no available register.
boolean	isFree(X86Register reg) Tests if a register is free for use.
X86Register	selectReg() Selects a register by LRU algorithm.
AssemblySequence	spill(X86Register reg) Spills a register to memory.
private void	useReg(X86Register reg_)

从类 java.lang.Object 继承的方法

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

字段详细信息

name2place

private java.util.HashMap<java.lang.String,java.lang.Integer> name2place

reg2name

private java.util.HashMap<X86Register,java.lang.String> reg2name

lruList

private java.util.LinkedList<X86Register> lruList

availableMemSlot

private java.util.LinkedList<java.lang.Integer> availableMemSlot

numOfMemAlloc

private int numOfMemAlloc

构造函数详细信息

RegAllocator

public RegAllocator()

方法详细信息

getReg

public X86Register getReg(java.lang.String valName)

Returns a register that is free to store the variable, or null if there are no available allocator. In this case user should use spill(X86Register) to spill out an occupied register.

参数：

valName - The name of the variable which needs a register to allocate.

返回：

the register that can allocate valName, or null if all register is occupied.

另请参见：

X86Register

hasFreeReg

public boolean hasFreeReg()

Returns a free register that is free or null if there are no available register.

返回：

true if there is at least a free register, or false vice versa.

spill

public AssemblySequence spill(X86Register reg)

Spills a register to memory. The method will automatically generate spilling assembly codes; if the register contains nothing, return null.

参数：

reg - The register name that shall be spilled out.

返回：

The spilling-to-stack operation sequence

getMem2Reg

public AssemblySequence getMem2Reg(java.lang.String valName,
                                   X86Register reg)

Generates a chain of instructions the fetches a variable from the memory to a register. if in stack we do not have the record of the variable, it returns null.

参数：

valName - the variable name that shall be restored to a register.

reg - the to-be-used register's name.

返回：

a list of instructions that fetches the variable from memory to address. If the process is not possible, return null.

isFree

public boolean isFree(X86Register reg)

Tests if a register is free for use.

参数：

reg - the register's name.

返回：

true if the register is free, false vice versa.

getAFreeRegister

public X86Register getAFreeRegister()

Uses LRU to determine a free register and returns it.

返回：

the name of the register, or null if there are no available registers.

getPositionInMem

public Instruct.Operand getPositionInMem(java.lang.String name)

Returns the stack address corresponding to a variable register. The stack address is represented as an Instruct.Operand

参数：

name - name of the variable

返回：

the memory address of the variable as an operand.

getPositionInMem

public Instruct.Operand getPositionInMem(X86Register reg)

Returns the stack address corresponding to a variable or a register. The stack address is represented as an Instruct.Operand

参数：

reg - name of the register

返回：

the memory address of the variable as an operand.

selectReg

public X86Register selectReg()

Selects a register by LRU algorithm. It is used to select an register to spill out.

返回：

the register that has not been used or referenced for the longest time.

useReg

private void useReg(X86Register reg_)