scale.backend.trips2
Class Trips2Allocator

java.lang.Object
  scale.backend.trips2.Trips2Allocator

Direct Known Subclasses:

Trips2AllocatorHybrid

public class Trips2Allocator
extends java.lang.Object

This class implements a quick and dirty register allocator for the Trips TIL.

$Id: Trips2Allocator.java,v 1.76 2007-10-23 17:18:56 beroy Exp $

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

This allocator is based upon QDRA. It is different in that it only allocates registers for the virtual registers that are alive across basic block boundaries. The virtual registers that are used only within a single basic block are not allocated.

Field Summary

protected BitVect[]	blocksDefdIn
protected BitVect[]	blocksUsedIn
protected static int	finalSpillCount
protected static int	finalSpillLdCnt
protected static int	finalSpillStCnt
protected Hyperblock[]	hbs
static boolean	LBSA2 Try to avoid spilling in a hyperblock if the spills would cause the hyperblock to violate a block constraint.
protected int[]	map
protected static int	maxVRCount
protected static int	redoCount
protected int[]	sorted
protected int	spillCount
protected boolean[]	spilled
protected double[]	strengths
protected BitVect[]	tLiveIn
protected BitVect[]	tLiveOut
protected BitVect[]	tLiveUse
protected boolean	trace
protected int[]	unallocated

Constructor Summary

Trips2Allocator(Generator gen, Hyperblock hbStart, boolean trace)
Setup a quick & dirty register allocation.

Method Summary

int[]	allocate() Determine a mapping from virtual registers to real registers.
protected int	allocateRealRegisters(BitVect allocReg) Generate a virtual register to real register mapping.
protected BitVect	computeLiveness() Compute liveness.
protected void	computeStats(java.lang.String msg, int retries) Compute the statistics after register allocation.
protected void	computeStrength(int numVirtual, int numReal) Determine the importance of each register.
protected double	computeStrengthBlockSize(int vr) Compute the strength of a virtual register based on the size of the hyperblocks the virtual register spans.
protected void	initialize() Initialize the register allocator.
static int	maxVirtualRegs() Return the maximum number of virtual registers encountered.
protected void	meekSpill(int numNotAllocated) Spill the registers that were not allocated.
static int	redo() Return the number of times register allocation was re-done.
static int	spillLoads() Return the number of loads inserted by spilling.
static int	spills() Return the number of spills required.
static int	spillStores() Return the number of stores inserted by spilling.

Methods inherited from class java.lang.Object

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

Field Detail

redoCount

protected static int redoCount

maxVRCount

protected static int maxVRCount

finalSpillCount

protected static int finalSpillCount

finalSpillStCnt

protected static int finalSpillStCnt

finalSpillLdCnt

protected static int finalSpillLdCnt

LBSA2

public static boolean LBSA2

Try to avoid spilling in a hyperblock if the spills would cause the hyperblock to violate a block constraint.

spillCount

protected int spillCount

unallocated

protected int[] unallocated

sorted

protected int[] sorted

strengths

protected double[] strengths

spilled

protected boolean[] spilled

map

protected int[] map

hbs

protected Hyperblock[] hbs

tLiveUse

protected BitVect[] tLiveUse

tLiveIn

protected BitVect[] tLiveIn

tLiveOut

protected BitVect[] tLiveOut

blocksUsedIn

protected BitVect[] blocksUsedIn

blocksDefdIn

protected BitVect[] blocksDefdIn

trace

protected boolean trace

Constructor Detail

Trips2Allocator

public Trips2Allocator(Generator gen,
                       Hyperblock hbStart,
                       boolean trace)

Setup a quick & dirty register allocation.

Parameters:

gen - is the instruction generator in use

hbStart - is the entry to the hyperblock flow graph

trace - is true if the register allocation should be traced

Method Detail

spills

public static int spills()

Return the number of spills required.

spillLoads

public static int spillLoads()

Return the number of loads inserted by spilling.

spillStores

public static int spillStores()

Return the number of stores inserted by spilling.

redo

public static int redo()

Return the number of times register allocation was re-done.

maxVirtualRegs

public static int maxVirtualRegs()

Return the maximum number of virtual registers encountered.

allocate

public int[] allocate()

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

Returns:

the mapping from virtual register to real register.

computeStats

protected void computeStats(java.lang.String msg,
                            int retries)

Compute the statistics after register allocation.

initialize

protected void initialize()

Initialize the register allocator.

computeLiveness

protected BitVect computeLiveness()

Compute liveness.

meekSpill

protected void meekSpill(int numNotAllocated)

Spill the registers that were not allocated. If the register to be spilled is used in the hyperblock, a load is inserted at the beginning of the block. Likewise if the register is defined in the hyperblock, a store is inserted at the end of the block.

Parameters:

numNotAllocated - is the number of un-allocated virtual registers

computeStrengthBlockSize

protected double computeStrengthBlockSize(int vr)

Compute the strength of a virtual register based on the size of the hyperblocks the virtual register spans. The strength will be higher for virtual registers that span "full" hyperblocks so the allocator will assign those first in an attempt to avoid spilling into full hyperblocks to minimize block splits.

computeStrength

protected void computeStrength(int numVirtual,
                               int numReal)

Determine the importance of each register. Importance is the measure of how important it is to allocate it before other registers.

allocateRealRegisters

protected int allocateRealRegisters(BitVect allocReg)

Generate a virtual register to real register mapping.

Parameters:

allocReg - is true if the register should be allocated

Returns:

the number of virtual registers that were not allocated.