Move this file out of the top-level docs directory

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15429 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 197 insertions, 0 deletions

diff --git a/lib/Target/SparcV9/RegAlloc/Notes.txt b/lib/Target/SparcV9/RegAlloc/Notes.txt
new file mode 100644
index 0000000000..b20b635020
--- /dev/null
+++ b/lib/Target/SparcV9/RegAlloc/Notes.txt
@@ -0,0 +1,197 @@
+		===================
+		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