scale.backend
Class QDRA

java.lang.Object
  scale.backend.RegisterAllocator
      scale.backend.QDRA

public class QDRA
extends RegisterAllocator

This class implements a quick and dirty register allocator.

$Id: QDRA.java,v 1.75 2007-10-04 19:57:49 burrill Exp $

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

It's quick not because it runs quickly but because it was written quickly. It's dirty because it's not been proven to terminate in all cases.

Algorithm

   FOR trip = 1 to 30 DO
      compute the importance of each instruction (Note 1)
      FOR each instruction
        obtain the registers used by the instruction
        obtain the registers defined by the instruction
        obtain the registers clobbered by the instruction
      FOREND
      compute register liveness across instructions
      FOR each virtual register (VA)
        compute VA's importance (Note 2)
      FOREND
      sort virtual registers by importance 
      FOR each un-allocated virtual register (VA) in order of its importance
        FOR each real register (RA) (Note 3)
          IF the liveness of VA does not conflict with the liveness of RA THEN
            allocate VA to RA
            update RA's liveness
            BREAK
        FOREND
      FOREND
      IF no un-allocated virtual registers remain THEN
        RETURN allocation map
      spill
   FOREND
   ABORT(Allocation failure)
 

Notes

1. The importance of an instruction is basically its loop_depth * 10.
2. The importance of a register is a function of the sum of the importance of the instructions that use the register and the number of instructions over which the register is live.
3. Real registers are checked in the order specified by the register set definition.

Our "bin-packing" register allocator is based on the bin-packing register allocator as described in [Truab "Quality and Speed in Linear-scan Register Allocation"].

Spilling

We use two different methods to select virtual registers to be spilled. The method chosen is determined by a heuristic. The first spill method (meek) simply spills those virtual registers that were not allocated. The second spill method (aggressive) attempts to spill those virtual registers with the longest live sequence. Since that information is not readily available, it uses the number of instructions over which the register is live as an approximation. The number spilled by the second method is the number of virtual registers that were not allocated.

The heuristic for selecting the method is simply to choose the aggressive method if there are more un-allocated virtual registers than real registers or if the meek method has already been used in a previous attempt.

When spilling, register saves are inserted immediately after any code sequence that defines the virtual register. Code sequences basically consist of those instructions generated for one CFG node. Code sequences are defined by the backend code generator which marks the last instruction in a sequence.

The point at which a spilled virtual register is loaded is also determined by heuristic. If the virtual register is defined only once, it is reloaded immediately before every use. Otherwise, it is reloaded immediately before the first use in a basic block.

Field Summary

Fields inherited from class scale.backend.RegisterAllocator

classTrace, generator, regDef, regDefCnt, registers, regMod, regStrength, regUse, regUseCnt, spillLoadCount, spillStoreCount, trace

Constructor Summary

QDRA(Generator gen, boolean trace)
Setup a quick & dirty register allocation.

Method Summary

int[]	allocate(Instruction firstInstruction) Determine a mapping from virtual registers to real registers.
static int	maxVirtualRegs() Return the maximum number of virtual registers encountered.
static int	redo() Return the number of times register allocation was re-done.
static int	spills() Return the number of spills required.

Methods inherited from class scale.backend.RegisterAllocator

compress, computeLiveness, computePredecessors, defRegister, getStrength, linearize, modRegister, spill, spillLoads, spillStores, transpose, useRegister

Methods inherited from class java.lang.Object

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

Constructor Detail

QDRA

public QDRA(Generator gen,
            boolean trace)

Setup a quick & dirty register allocation.

Parameters:

gen - is the instruction generator in use

trace - is true if the register allocation should be traced

Method Detail

spills

public static int spills()

Return the number of spills required.

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(Instruction firstInstruction)

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.

Specified by:

allocate in class RegisterAllocator

Parameters:

firstInstruction - is the first instruction in the instruction sequence

Returns:

the mapping from virtual register to real register