		===================
		Register Allocation
		===================


1. Introduction
===============

Purpose: This file contains implementation information about register 
	 allocation.
Author : Ruchira Sasanka
Date   : Dec 8, 2001


2. Entry Point
==============
class PhyRegAlloc (PhyRegAlloc.h) is the main class for the register 
allocation. PhyRegAlloc::allocateRegisters() starts the register allocation
and contains the major steps for register allocation.

2. Usage
========
Register allocation must be done  as:	

   MethodLiveVarInfo LVI(*MethodI );           // compute LV info
   LVI.analyze();

   TargetMachine &target = ....	               // target description     


   PhyRegAlloc PRA(*MethodI, target, &LVI);    // allocate regs
   PRA.allocateRegisters();


4. Input and Preconditions
==========================
Register allocation is done using machine instructions. The constructor
to the class takes a pointer to a method, a target machine description and
a live variable information for the method.

The preconditions are:

1. Instruction selection is complete (i.e., machine instructions are 
   generated) for the method before the live variable analysis

2. Phi elimination is complete. 


5. Assumptions
==============

   All variables (llvm Values) are defined before they are used. However, a 
   constant may not be defined in the machine instruction stream if it can be
   used as an immediate value within a machine instruction. However, register
   allocation does not have to worry about immediate constants since they
   do not require registers.

   Since an llvm Value has a list of uses associated, it is sufficient to
   record only the defs in a Live Range.


6. Overall Design
=================
There are sperate reigster classes - e.g., Int, Float, 
IntConditionCode, FloatConditionCode register classes for Sparc.

Registerallocation consists of the following main steps:

  1. Construct Live-ranges & Suggest colors (machine specific) if required
  2. Create Interference graphs
  3. Coalescing live ranges
  4. Color all live ranges in each RegClass using graph coloring algo
  5. Insert additional (machine specific) code for calls/returns/incoming args
  6. Update instruction stream and insert spill code

All the above methods are called from  PhyRegAlloc::allocateRegisters().

All steps above except step 5 and suggesting colors in step 1 are indepenedent
of a particular target architecture. Targer independent code is availble in
../lib/CodeGen/RegAlloc. Target specific code for Sparc is available in
../lib/Target/Sparc. 


6.1. Construct Live-ranges & Suggest colors (machine specific) if required
--------------------------------------------------------------------------
Live range construction is done using machine instructions. Since there must
be at least one definition for each variable in the machine instruction, we
consider only definitions in creating live ranges. After live range
construction is complete, there is a live range for all variables defined in
the instruction stream. Note however that, live ranges are not constructed for
constants which are not defined in the instruction stream. 

A LiveRange is a set of Values (only defs) in that live range. Live range
construction is done in combination for all register classes. All the live
ranges for a method are entered to a LiveRangeMap which can be accessed using 
any Value in the LiveRange.

After live ranges have been constructed, we call machine specific code to 
suggest colors for speical live ranges. For instance, incoming args, call args,
return values must be placed in special registers for most architectures. By
suggesting colors for such special live ranges before we do the actual register
allocation using graph coloring, the graph coloring can try its best to assign
the required color for such special live ranges. This will reduce unnecessary
copy instructions needed to move values to special registers. However, there
is no guarantee that a live range will receive its suggested color. If the
live range does not receive the suggested color, we have to insert explicit 
copy instructions to move the value into requred registers and its done in
step 5 above.

See LiveRange.h, LiveRangeInfo.h (and  LiveRange.cpp, LiveRangeInfo.cpp) for
algorithms and details. See SparcRegInfo.cpp for suggesting colors for 
incoming/call arguments and return values.


6.2. Create Interference graphs
-------------------------------
Once live ranges are constructed, we can build interference graphs for each
register class. Though each register class must have a separate interference
graph, building all interference graphs is performed in one pass. Also, the
adjacency list for each live range is built in this phase. Consequently, each
register class has an interference graph (which is a bit matrix) and each
LiveRange has an adjacency list to record its neighbors. Live variable info
is used for finding the interferences.

See IGNode.h, InterferenceGraph.h (and IGNode.h, InterferenceGraph.h) for 
data structures and PhyRegAlloc::createIGNodeListsAndIGs() for the starting
point for interference graph construction.


6.3. Coalescing live ranges
---------------------------
We coalesce live ranges to reduce the number of live ranges. 

See  LiveRangeInfo.h (and LiveRangeInfo.cpp). The entire algorithm for
coalesing is given in LiveRangeInfo::coalesceLRs().


6.4. Color all live ranges in each RegClass using graph coloring algo
---------------------------------------------------------------------
Each register class is colored separately using the graph coloring algo. When
assigning colors, preference is given to live ranges with suggested colors
so that if such a live range receives a color (i.e., not spilled), then
we try to assign the color suggested for that live range. When this phase
is complete it is possible that some live ranges do not have colors (i.e., 
those that must be spilled).


6.5. Insert additional (machine specific) code for calls/returns/incoming args
------------------------------------------------------------------------------
This code is machine specific. Currently, the code for Sparc is implemented
in SparcRegInfo.cpp. This code is more complex because of the complex 
requirements of assigning some values to special registers. When a special
value as an incoming argument receives a color through the graph coloring
alogorithm, we have to make sure that it received the correct color (for 
instance the first incoming int argument must be colored to %i0 on Sparc). If
it didn't receive the correct color, we have to insert instruction to to move
the value to the required register. Also, this phase produces the caller 
saving code. All adition code produced is kept separately until the last
phase (see 6.6)


6.6. Update instruction stream  and insert spill code
-----------------------------------------------------
After we have assigned registers for all values and after we have produced
additional code to be inserted before some instructions, we update the
machine instruction stream. While we are updating the machine instruction
stream, if an instruction referes to a spilled value, we insert spill
instructions before/after that instruction. Also, we prepend/append additonal
instructions that have been produced for that instruction by the register
allocation (e.g., caller saving code)


7. Furture work
===============
If it is necessary to port the register allocator to another architecture
than Sparc, only the target specific code in ../lib/Target/Sparc needs to
be rewritten. Methods defined in class MachineRegInfo must be provided for
the new architecure.

7.1 Using  ReservedColorList in RegClass
----------------------------------------
The register allocator allows reserving a set of registers - i.e. the reserved
registers are not used by the register allocator. Currently, there are no
reserved registers. It it is necessary to make some registers unavailable to
a particular method, this feature will become handy. To do that, the reserved
register list must be passed to the register allocator. See PhyRegAlloc.cpp


7.2 %g registers on Sparc
-------------------------
Currently, %g registers are not allocated on Sparc. If it is necessary to
allocate these %g registers, the enumeration of registers in SparcIntRegClass
in SparcRegClassInfo.h must be changed. %g registers can be easily added as
volatile registers just by moving them above in the eneumeration - see
SparcRegClassInfo.h