Added comments, destructors where necessary.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1491 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/docs/RegisterAllocatorInfo.txt b/docs/RegisterAllocatorInfo.txt
index 557a2e5..58a5450 100644
--- a/docs/RegisterAllocatorInfo.txt
+++ b/docs/RegisterAllocatorInfo.txt
@@ -34,7 +34,6 @@
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.
@@ -50,6 +49,15 @@
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.
+
@@ -69,6 +77,11 @@
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
--------------------------------------------------------------------------
@@ -159,3 +172,11 @@
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.
+
+using ReservedColorList in RegClass
\ No newline at end of file
diff --git a/include/llvm/CodeGen/RegClass.h b/include/llvm/CodeGen/RegClass.h
index 3fb448a..d6cbaf8 100644
--- a/include/llvm/CodeGen/RegClass.h
+++ b/include/llvm/CodeGen/RegClass.h
@@ -3,17 +3,6 @@
Date: Aug 20, 01
Purpose: Contains machine independent methods for register coloring.
- This is the class that contains all data structures and common algos
- for coloring a particular register class (e.g., int class, fp class).
- This class is hardware independent. This class accepts a hardware
- dependent description of machine registers (MachineRegInfo class) to
- get hardware specific info and color and indidual IG node.
-
- This class contains the InterferenceGraph (IG).
- Also it contains an IGNode stack that can be used for coloring.
- The class provides some easy access methods to the IG methods, since these
- methods are called thru a register class.
-
*/
#ifndef REG_CLASS_H
@@ -28,6 +17,23 @@
typedef vector<unsigned int> ReservedColorListType;
+//-----------------------------------------------------------------------------
+// Class RegClass
+//
+// Implements a machine independant register class.
+//
+// This is the class that contains all data structures and common algos
+// for coloring a particular register class (e.g., int class, fp class).
+// This class is hardware independent. This class accepts a hardware
+// dependent description of machine registers (MachineRegInfo class) to
+// get hardware specific info and to color an individual IG node.
+//
+// This class contains the InterferenceGraph (IG).
+// Also it contains an IGNode stack that can be used for coloring.
+// The class provides some easy access methods to the IG methods, since these
+// methods are called thru a register class.
+//
+//-----------------------------------------------------------------------------
class RegClass
{
@@ -42,28 +48,37 @@
// buildInterferenceGraph
stack <IGNode *> IGNodeStack; // the stack used for coloring
- // for passing registered that are pre-allocated (e.g., %g's)
const ReservedColorListType *const ReservedColorList;
-
+ //
+ // for passing registers that are pre-allocated and cannot be used by the
+ // register allocator for this method.
+
+ bool *IsColorUsedArr;
+ //
// An array used for coloring each node. This array must be of size
// MRC->getNumOfAllRegs(). Allocated once in the constructor
// for efficiency.
- bool *IsColorUsedArr;
- //------------ private methods ------------------
+ //--------------------------- private methods ------------------------------
void pushAllIGNodes();
+
bool pushUnconstrainedIGNodes();
+
IGNode * getIGNodeWithMinSpillCost();
+
void colorIGNode(IGNode *const Node);
+
public:
RegClass(const Method *const M,
const MachineRegClassInfo *const MRC,
const ReservedColorListType *const RCL = NULL);
+ ~RegClass() { delete[] IsColorUsedArr; };
+
inline void createInterferenceGraph()
{ IG.createGraph(); }
@@ -71,19 +86,17 @@
inline const unsigned getID() const { return RegClassID; }
- void colorAllRegs(); // main method called for coloring regs
+ // main method called for coloring regs
+ //
+ void colorAllRegs();
inline unsigned getNumOfAvailRegs() const
{ return MRC->getNumOfAvailRegs(); }
- ~RegClass() { delete[] IsColorUsedArr; };
-
-
// --- following methods are provided to access the IG contained within this
// ---- RegClass easilly.
-
inline void addLRToIG(LiveRange *const LR)
{ IG.addLRToIG(LR); }
diff --git a/lib/CodeGen/RegAlloc/IGNode.h b/lib/CodeGen/RegAlloc/IGNode.h
index bcaf439..0f4cf9c 100644
--- a/lib/CodeGen/RegAlloc/IGNode.h
+++ b/lib/CodeGen/RegAlloc/IGNode.h
@@ -14,9 +14,9 @@
OnStack flag set (therefore, they are in the IG).
The methods that modify/use the CurDegree Must be called only
- fter all modifications to the IG are over (i.e., all neighbors are fixed).
+ after all modifications to the IG are over (i.e., all neighbors are fixed).
- The vector representation the most efficient one for adj list.
+ The vector representation is the most efficient one for adj list.
Though nodes are removed when coalsing is done, we access it in sequence
for far many times when coloring (colorNode()).
@@ -29,6 +29,14 @@
#include "llvm/CodeGen/RegAllocCommon.h"
#include "llvm/CodeGen/LiveRange.h"
+
+
+//----------------------------------------------------------------------------
+// Class IGNode
+//
+// Represents a node in an interference graph.
+//----------------------------------------------------------------------------
+
class IGNode
{
private:
@@ -39,22 +47,33 @@
vector<IGNode *> AdjList; // adjacency list for this live range
-
+ int CurDegree;
+ //
// set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
// all adjacency lists.
// Decremented when a neighbor is pushed on to the stack.
// After that, never incremented/set again nor used.
- int CurDegree;
- LiveRange *const ParentLR; // parent LR (cannot be a const)
+
+ LiveRange *const ParentLR; // parent LR (cannot be a const)
public:
+ // constructor
+ //
+ IGNode(LiveRange *const LR, unsigned int index);
+
+ // an empty destructor
+ //
+ ~IGNode() { }
+
+
inline unsigned int getIndex() const
{ return Index; }
// adjLists must be updated only once. However, the CurDegree can be changed
+ //
inline void addAdjIGNode( IGNode *const AdjNode)
{ AdjList.push_back(AdjNode); }
@@ -63,6 +82,7 @@
// delete a node in AdjList - node must be in the list
// should not be called often
+ //
void delAdjIGNode(const IGNode *const Node);
inline unsigned int getNumOfNeighbors() const
@@ -73,13 +93,14 @@
{ return OnStack; }
// remove form IG and pushes on to stack (reduce the degree of neighbors)
+ //
void pushOnStack();
// CurDegree is the effective number of neighbors when neighbors are
// pushed on to the stack during the coloring phase. Must be called
// after all modifications to the IG are over (i.e., all neighbors are
// fixed).
-
+ //
inline void setCurDegree()
{ assert( CurDegree == -1); CurDegree = AdjList.size(); }
@@ -87,6 +108,7 @@
{ return CurDegree; }
// called when a neigh is pushed on to stack
+ //
inline void decCurDegree()
{ assert( CurDegree > 0 ); --CurDegree; }
@@ -118,10 +140,6 @@
inline void markForSaveAcrossCalls()
{ ParentLR->markForSaveAcrossCalls(); }
- // inline void markForLoadFromStack()
- // { ParentLR->markForLoadFromStack(); }
-
-
inline unsigned int isCallInterference() const
{ return ParentLR->isCallInterference(); }
@@ -132,15 +150,6 @@
{ return ParentLR->getTypeID(); }
-
- //---- constructor and destructor ----
-
-
- IGNode(LiveRange *const LR, unsigned int index);
-
- ~IGNode() { } // an empty destructor
-
-
};
diff --git a/lib/CodeGen/RegAlloc/LiveRange.h b/lib/CodeGen/RegAlloc/LiveRange.h
index 3ef627e..778e070 100644
--- a/lib/CodeGen/RegAlloc/LiveRange.h
+++ b/lib/CodeGen/RegAlloc/LiveRange.h
@@ -14,56 +14,88 @@
#include "llvm/Analysis/LiveVar/ValueSet.h"
#include "llvm/Type.h"
-
-
-
class RegClass;
class IGNode;
+//----------------------------------------------------------------------------
+// Class LiveRange
+//
+// Implements a live range using a ValueSet. A LiveRange is a simple set
+// of Values.
+//----------------------------------------------------------------------------
+
class LiveRange : public ValueSet
{
private:
RegClass *MyRegClass; // register classs (e.g., int, FP) for this LR
- // a list of call instructions that interferes with this live range
- //vector<const Instruction *> CallInterferenceList;
- // does this live range span across calls?
+ bool doesSpanAcrossCalls;
+ //
+ // Does this live range span across calls?
// This information is used by graph
// coloring algo to avoid allocating volatile colors to live ranges
// that span across calls (since they have to be saved/restored)
-
- bool doesSpanAcrossCalls;
+
IGNode *UserIGNode; // IGNode which uses this LR
+
int Color; // color assigned to this live range
+
bool mustSpill; // whether this LR must be spilt
- // whether this LR must be saved accross calls ***TODO REMOVE this
+
bool mustSaveAcrossCalls;
-
- // bool mustLoadFromStack; // must load from stack at start of method
-
-
+ //
+ // whether this LR must be saved accross calls ***TODO REMOVE this
+
int SuggestedColor; // The suggested color for this LR
-
+ //
// if this LR has a suggested color, can it be really alloated?
// A suggested color cannot be allocated when the suggested color is
// volatile and when there are call interferences.
bool CanUseSuggestedCol;
+ //
+ // It is possible that a suggested color for this live range is not
+ // available before graph coloring (e.g., it can be allocated to another
+ // live range which interferes with this)
+ int SpilledStackOffsetFromFP;
+ //
// if this LR is spilled, its stack offset from *FP*. The spilled offsets
// must always be relative to the FP.
- int SpilledStackOffsetFromFP;
+
bool HasSpillOffset;
+ //
+ // Whether this live range has a spill offset
+
+ unsigned SpillCost;
+ //
+ // The spill cost of this live range. Calculated using loop depth of
+ // each reference to each Value in the live range
public:
+ // constructor
+ //
+ LiveRange() : ValueSet() {
+ Color = SuggestedColor = -1; // not yet colored
+ mustSpill = mustSaveAcrossCalls = false;
+ MyRegClass = NULL;
+ UserIGNode = NULL;
+ doesSpanAcrossCalls = false;
+ CanUseSuggestedCol = true;
+ HasSpillOffset = false;
+ SpillCost = 0;
+ }
- ~LiveRange() {} // empty destructor
+ // empty destructor since there are nothing to be deleted
+ //
+ ~LiveRange() {}
+
void setRegClass(RegClass *const RC)
{ MyRegClass = RC; }
@@ -90,7 +122,6 @@
return (doesSpanAcrossCalls == 1);
}
-
inline void markForSpill() { mustSpill = true; }
inline bool isMarkedForSpill() { return mustSpill; }
@@ -122,9 +153,7 @@
inline void markForSaveAcrossCalls() { mustSaveAcrossCalls = true; }
- // inline void markForLoadFromStack() { mustLoadFromStack = true;
-
-
+
inline void setUserIGNode( IGNode *const IGN)
{ assert( !UserIGNode); UserIGNode = IGN; }
@@ -169,22 +198,13 @@
CanUseSuggestedCol = val;
}
+ inline void addSpillCost(unsigned cost) {
+ SpillCost += cost;
+ }
-
-
-
-
-
- inline LiveRange() : ValueSet() /* , CallInterferenceList() */
- {
- Color = SuggestedColor = -1; // not yet colored
- mustSpill = mustSaveAcrossCalls = false;
- MyRegClass = NULL;
- UserIGNode = NULL;
- doesSpanAcrossCalls = false;
- CanUseSuggestedCol = true;
- HasSpillOffset = false;
- }
+ inline unsigned getSpillCost() const {
+ return SpillCost;
+ }
};
diff --git a/lib/CodeGen/RegAlloc/LiveRangeInfo.h b/lib/CodeGen/RegAlloc/LiveRangeInfo.h
index 9347373..1eee1ae 100644
--- a/lib/CodeGen/RegAlloc/LiveRangeInfo.h
+++ b/lib/CodeGen/RegAlloc/LiveRangeInfo.h
@@ -3,8 +3,8 @@
Date: Jun 30, 01
Purpose:
- This file constructs and keeps the LiveRang map which contains all the live
- ranges used in a method.
+ This file contains the class LiveRangeInfo which constructs and keeps
+ the LiveRangMap which contains all the live ranges used in a method.
Assumptions:
@@ -23,7 +23,6 @@
#ifndef LIVE_RANGE_INFO_H
#define LIVE_RANGE_INFO_H
-
#include "llvm/Type.h"
#include "llvm/Method.h"
#include "llvm/CodeGen/MachineInstr.h"
@@ -34,16 +33,19 @@
#include "llvm/CodeGen/LiveRange.h"
#include "llvm/CodeGen/RegClass.h"
-/*
- #ifndef size_type
- #define size_type (unsigned int)
- #endif
-*/
-
typedef hash_map <const Value *, LiveRange *, hashFuncValue> LiveRangeMapType;
typedef vector <const MachineInstr *> CallRetInstrListType;
+
+
+//----------------------------------------------------------------------------
+// Class LiveRangeInfo
+//
+// Constructs and keeps the LiveRangMap which contains all the live
+// ranges used in a method. Also contain methods to coalesce live ranges.
+//----------------------------------------------------------------------------
+
class LiveRangeInfo
{
@@ -51,15 +53,21 @@
const Method *const Meth; // Method for which live range info is held
- LiveRangeMapType LiveRangeMap; // A map from Value * to LiveRange *
+ LiveRangeMapType LiveRangeMap; // A map from Value * to LiveRange * to
+ // record all live ranges in a method
// created by constructLiveRanges
-
+
const TargetMachine& TM; // target machine description
+
vector<RegClass *> & RegClassList;// a vector containing register classess
+
const MachineRegInfo& MRI; // machine reg info
CallRetInstrListType CallRetInstrList; // a list of all call/ret instrs
+
+ //------------ Private methods (see LiveRangeInfo.cpp for description)-------
+
void unionAndUpdateLRs(LiveRange *L1, LiveRange *L2);
void addInterference(const Instruction *const Inst,
@@ -67,37 +75,55 @@
void suggestRegs4CallRets();
+ const Method* getMethod() { return Meth; }
+
+
public:
LiveRangeInfo(const Method *const M,
const TargetMachine& tm,
vector<RegClass *> & RCList);
+
+ // Destructor to destroy all LiveRanges in the LiveRange Map
+ ~LiveRangeInfo();
+
+ // Main entry point for live range construction
+ //
void constructLiveRanges();
- const Method* getMethod() { return Meth; }
-
+ // This method is used to add a live range created elsewhere (e.g.,
+ // in machine specific code) to the common live range map
+ //
inline void addLRToMap(const Value *Val, LiveRange *LR) {
assert( Val && LR && "Val/LR is NULL!\n");
assert( (! LiveRangeMap[ Val ]) && "LR already set in map");
LiveRangeMap[ Val ] = LR;
}
-
+ // return the common live range map for this method
+ //
inline const LiveRangeMapType *const getLiveRangeMap() const
{ return &LiveRangeMap; }
+ // Method sed to get the corresponding live range of a Value
+ //
inline LiveRange *getLiveRangeForValue( const Value *const Val)
{ return LiveRangeMap[ Val ]; }
+ // Method used to get the Call and Return instruction list
+ //
inline CallRetInstrListType &getCallRetInstrList() {
return CallRetInstrList;
}
-
-
+ // Method for coalescing live ranges. Called only after interference info
+ // is calculated.
+ //
void coalesceLRs();
+ // debugging method to print the live ranges
+ //
void printLiveRanges();
};
diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.h b/lib/CodeGen/RegAlloc/PhyRegAlloc.h
index f76e68b..9d34557 100644
--- a/lib/CodeGen/RegAlloc/PhyRegAlloc.h
+++ b/lib/CodeGen/RegAlloc/PhyRegAlloc.h
@@ -4,6 +4,7 @@
Purpose: This is the main entry point for register allocation.
Notes:
+ =====
* RegisterClasses: Each RegClass accepts a
MachineRegClass which contains machine specific info about that register
@@ -14,18 +15,18 @@
* Machine dependent work: All parts of the register coloring algorithm
except coloring of an individual node are machine independent.
- Register allocation must be done as:
+ Register allocation must be done as:
- static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
+ MethodLiveVarInfo LVI(*MethodI ); // compute LV info
+ LVI.analyze();
- MethodLiveVarInfo LVI(*MethodI ); // compute LV info
- LVI.analyze();
+ TargetMachine &target = ....
- PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
- PRA.allocateRegisters();
- Assumptions:
- All values in a live range will be of the same physical reg class.
+ PhyRegAlloc PRA(*MethodI, target, &LVI); // allocate regs
+ PRA.allocateRegisters();
+
+
*/
@@ -36,6 +37,7 @@
#include "llvm/CodeGen/RegClass.h"
#include "llvm/CodeGen/LiveRangeInfo.h"
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+#include "llvm/Analysis/LoopDepth.h"
#include <deque>
@@ -82,15 +84,15 @@
const MachineRegInfo &MRI; // Machine Register information
const unsigned NumOfRegClasses; // recorded here for efficiency
- //vector<const Instruction *> CallInstrList; // a list of all call instrs
- //vector<const Instruction *> RetInstrList; // a list of all return instrs
-
AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
+ LoopDepthCalculator LoopDepthCalc; // to calculate loop depths
+ ReservedColorListType ResColList; // A set of reserved regs if desired.
+ // currently not used
- //vector<const MachineInstr *> PhiInstList; // a list of all phi instrs
- //------- private methods ---------------------------------------------------
+
+ //------- ------------------ private methods---------------------------------
void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
const bool isCallInst);
@@ -98,8 +100,6 @@
void addInterferencesForArgs();
void createIGNodeListsAndIGs();
void buildInterferenceGraphs();
- //void insertCallerSavingCode(const MachineInstr *MInst,
- // const BasicBlock *BB );
void setCallInterferences(const MachineInstr *MInst,
const LiveVarSet *const LVSetAft );
@@ -147,7 +147,11 @@
PhyRegAlloc(Method *const M, const TargetMachine& TM,
MethodLiveVarInfo *const Lvi);
- void allocateRegisters(); // main method called for allocatin
+ ~PhyRegAlloc();
+
+ // main method called for allocating registers
+ //
+ void allocateRegisters();
};
diff --git a/lib/CodeGen/RegAlloc/RegClass.h b/lib/CodeGen/RegAlloc/RegClass.h
index 3fb448a..d6cbaf8 100644
--- a/lib/CodeGen/RegAlloc/RegClass.h
+++ b/lib/CodeGen/RegAlloc/RegClass.h
@@ -3,17 +3,6 @@
Date: Aug 20, 01
Purpose: Contains machine independent methods for register coloring.
- This is the class that contains all data structures and common algos
- for coloring a particular register class (e.g., int class, fp class).
- This class is hardware independent. This class accepts a hardware
- dependent description of machine registers (MachineRegInfo class) to
- get hardware specific info and color and indidual IG node.
-
- This class contains the InterferenceGraph (IG).
- Also it contains an IGNode stack that can be used for coloring.
- The class provides some easy access methods to the IG methods, since these
- methods are called thru a register class.
-
*/
#ifndef REG_CLASS_H
@@ -28,6 +17,23 @@
typedef vector<unsigned int> ReservedColorListType;
+//-----------------------------------------------------------------------------
+// Class RegClass
+//
+// Implements a machine independant register class.
+//
+// This is the class that contains all data structures and common algos
+// for coloring a particular register class (e.g., int class, fp class).
+// This class is hardware independent. This class accepts a hardware
+// dependent description of machine registers (MachineRegInfo class) to
+// get hardware specific info and to color an individual IG node.
+//
+// This class contains the InterferenceGraph (IG).
+// Also it contains an IGNode stack that can be used for coloring.
+// The class provides some easy access methods to the IG methods, since these
+// methods are called thru a register class.
+//
+//-----------------------------------------------------------------------------
class RegClass
{
@@ -42,28 +48,37 @@
// buildInterferenceGraph
stack <IGNode *> IGNodeStack; // the stack used for coloring
- // for passing registered that are pre-allocated (e.g., %g's)
const ReservedColorListType *const ReservedColorList;
-
+ //
+ // for passing registers that are pre-allocated and cannot be used by the
+ // register allocator for this method.
+
+ bool *IsColorUsedArr;
+ //
// An array used for coloring each node. This array must be of size
// MRC->getNumOfAllRegs(). Allocated once in the constructor
// for efficiency.
- bool *IsColorUsedArr;
- //------------ private methods ------------------
+ //--------------------------- private methods ------------------------------
void pushAllIGNodes();
+
bool pushUnconstrainedIGNodes();
+
IGNode * getIGNodeWithMinSpillCost();
+
void colorIGNode(IGNode *const Node);
+
public:
RegClass(const Method *const M,
const MachineRegClassInfo *const MRC,
const ReservedColorListType *const RCL = NULL);
+ ~RegClass() { delete[] IsColorUsedArr; };
+
inline void createInterferenceGraph()
{ IG.createGraph(); }
@@ -71,19 +86,17 @@
inline const unsigned getID() const { return RegClassID; }
- void colorAllRegs(); // main method called for coloring regs
+ // main method called for coloring regs
+ //
+ void colorAllRegs();
inline unsigned getNumOfAvailRegs() const
{ return MRC->getNumOfAvailRegs(); }
- ~RegClass() { delete[] IsColorUsedArr; };
-
-
// --- following methods are provided to access the IG contained within this
// ---- RegClass easilly.
-
inline void addLRToIG(LiveRange *const LR)
{ IG.addLRToIG(LR); }
diff --git a/lib/Target/SparcV9/RegAlloc/IGNode.h b/lib/Target/SparcV9/RegAlloc/IGNode.h
index bcaf439..0f4cf9c 100644
--- a/lib/Target/SparcV9/RegAlloc/IGNode.h
+++ b/lib/Target/SparcV9/RegAlloc/IGNode.h
@@ -14,9 +14,9 @@
OnStack flag set (therefore, they are in the IG).
The methods that modify/use the CurDegree Must be called only
- fter all modifications to the IG are over (i.e., all neighbors are fixed).
+ after all modifications to the IG are over (i.e., all neighbors are fixed).
- The vector representation the most efficient one for adj list.
+ The vector representation is the most efficient one for adj list.
Though nodes are removed when coalsing is done, we access it in sequence
for far many times when coloring (colorNode()).
@@ -29,6 +29,14 @@
#include "llvm/CodeGen/RegAllocCommon.h"
#include "llvm/CodeGen/LiveRange.h"
+
+
+//----------------------------------------------------------------------------
+// Class IGNode
+//
+// Represents a node in an interference graph.
+//----------------------------------------------------------------------------
+
class IGNode
{
private:
@@ -39,22 +47,33 @@
vector<IGNode *> AdjList; // adjacency list for this live range
-
+ int CurDegree;
+ //
// set by InterferenceGraph::setCurDegreeOfIGNodes() after calculating
// all adjacency lists.
// Decremented when a neighbor is pushed on to the stack.
// After that, never incremented/set again nor used.
- int CurDegree;
- LiveRange *const ParentLR; // parent LR (cannot be a const)
+
+ LiveRange *const ParentLR; // parent LR (cannot be a const)
public:
+ // constructor
+ //
+ IGNode(LiveRange *const LR, unsigned int index);
+
+ // an empty destructor
+ //
+ ~IGNode() { }
+
+
inline unsigned int getIndex() const
{ return Index; }
// adjLists must be updated only once. However, the CurDegree can be changed
+ //
inline void addAdjIGNode( IGNode *const AdjNode)
{ AdjList.push_back(AdjNode); }
@@ -63,6 +82,7 @@
// delete a node in AdjList - node must be in the list
// should not be called often
+ //
void delAdjIGNode(const IGNode *const Node);
inline unsigned int getNumOfNeighbors() const
@@ -73,13 +93,14 @@
{ return OnStack; }
// remove form IG and pushes on to stack (reduce the degree of neighbors)
+ //
void pushOnStack();
// CurDegree is the effective number of neighbors when neighbors are
// pushed on to the stack during the coloring phase. Must be called
// after all modifications to the IG are over (i.e., all neighbors are
// fixed).
-
+ //
inline void setCurDegree()
{ assert( CurDegree == -1); CurDegree = AdjList.size(); }
@@ -87,6 +108,7 @@
{ return CurDegree; }
// called when a neigh is pushed on to stack
+ //
inline void decCurDegree()
{ assert( CurDegree > 0 ); --CurDegree; }
@@ -118,10 +140,6 @@
inline void markForSaveAcrossCalls()
{ ParentLR->markForSaveAcrossCalls(); }
- // inline void markForLoadFromStack()
- // { ParentLR->markForLoadFromStack(); }
-
-
inline unsigned int isCallInterference() const
{ return ParentLR->isCallInterference(); }
@@ -132,15 +150,6 @@
{ return ParentLR->getTypeID(); }
-
- //---- constructor and destructor ----
-
-
- IGNode(LiveRange *const LR, unsigned int index);
-
- ~IGNode() { } // an empty destructor
-
-
};
diff --git a/lib/Target/SparcV9/RegAlloc/LiveRange.h b/lib/Target/SparcV9/RegAlloc/LiveRange.h
index 3ef627e..778e070 100644
--- a/lib/Target/SparcV9/RegAlloc/LiveRange.h
+++ b/lib/Target/SparcV9/RegAlloc/LiveRange.h
@@ -14,56 +14,88 @@
#include "llvm/Analysis/LiveVar/ValueSet.h"
#include "llvm/Type.h"
-
-
-
class RegClass;
class IGNode;
+//----------------------------------------------------------------------------
+// Class LiveRange
+//
+// Implements a live range using a ValueSet. A LiveRange is a simple set
+// of Values.
+//----------------------------------------------------------------------------
+
class LiveRange : public ValueSet
{
private:
RegClass *MyRegClass; // register classs (e.g., int, FP) for this LR
- // a list of call instructions that interferes with this live range
- //vector<const Instruction *> CallInterferenceList;
- // does this live range span across calls?
+ bool doesSpanAcrossCalls;
+ //
+ // Does this live range span across calls?
// This information is used by graph
// coloring algo to avoid allocating volatile colors to live ranges
// that span across calls (since they have to be saved/restored)
-
- bool doesSpanAcrossCalls;
+
IGNode *UserIGNode; // IGNode which uses this LR
+
int Color; // color assigned to this live range
+
bool mustSpill; // whether this LR must be spilt
- // whether this LR must be saved accross calls ***TODO REMOVE this
+
bool mustSaveAcrossCalls;
-
- // bool mustLoadFromStack; // must load from stack at start of method
-
-
+ //
+ // whether this LR must be saved accross calls ***TODO REMOVE this
+
int SuggestedColor; // The suggested color for this LR
-
+ //
// if this LR has a suggested color, can it be really alloated?
// A suggested color cannot be allocated when the suggested color is
// volatile and when there are call interferences.
bool CanUseSuggestedCol;
+ //
+ // It is possible that a suggested color for this live range is not
+ // available before graph coloring (e.g., it can be allocated to another
+ // live range which interferes with this)
+ int SpilledStackOffsetFromFP;
+ //
// if this LR is spilled, its stack offset from *FP*. The spilled offsets
// must always be relative to the FP.
- int SpilledStackOffsetFromFP;
+
bool HasSpillOffset;
+ //
+ // Whether this live range has a spill offset
+
+ unsigned SpillCost;
+ //
+ // The spill cost of this live range. Calculated using loop depth of
+ // each reference to each Value in the live range
public:
+ // constructor
+ //
+ LiveRange() : ValueSet() {
+ Color = SuggestedColor = -1; // not yet colored
+ mustSpill = mustSaveAcrossCalls = false;
+ MyRegClass = NULL;
+ UserIGNode = NULL;
+ doesSpanAcrossCalls = false;
+ CanUseSuggestedCol = true;
+ HasSpillOffset = false;
+ SpillCost = 0;
+ }
- ~LiveRange() {} // empty destructor
+ // empty destructor since there are nothing to be deleted
+ //
+ ~LiveRange() {}
+
void setRegClass(RegClass *const RC)
{ MyRegClass = RC; }
@@ -90,7 +122,6 @@
return (doesSpanAcrossCalls == 1);
}
-
inline void markForSpill() { mustSpill = true; }
inline bool isMarkedForSpill() { return mustSpill; }
@@ -122,9 +153,7 @@
inline void markForSaveAcrossCalls() { mustSaveAcrossCalls = true; }
- // inline void markForLoadFromStack() { mustLoadFromStack = true;
-
-
+
inline void setUserIGNode( IGNode *const IGN)
{ assert( !UserIGNode); UserIGNode = IGN; }
@@ -169,22 +198,13 @@
CanUseSuggestedCol = val;
}
+ inline void addSpillCost(unsigned cost) {
+ SpillCost += cost;
+ }
-
-
-
-
-
- inline LiveRange() : ValueSet() /* , CallInterferenceList() */
- {
- Color = SuggestedColor = -1; // not yet colored
- mustSpill = mustSaveAcrossCalls = false;
- MyRegClass = NULL;
- UserIGNode = NULL;
- doesSpanAcrossCalls = false;
- CanUseSuggestedCol = true;
- HasSpillOffset = false;
- }
+ inline unsigned getSpillCost() const {
+ return SpillCost;
+ }
};
diff --git a/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.h b/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.h
index 9347373..1eee1ae 100644
--- a/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.h
+++ b/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.h
@@ -3,8 +3,8 @@
Date: Jun 30, 01
Purpose:
- This file constructs and keeps the LiveRang map which contains all the live
- ranges used in a method.
+ This file contains the class LiveRangeInfo which constructs and keeps
+ the LiveRangMap which contains all the live ranges used in a method.
Assumptions:
@@ -23,7 +23,6 @@
#ifndef LIVE_RANGE_INFO_H
#define LIVE_RANGE_INFO_H
-
#include "llvm/Type.h"
#include "llvm/Method.h"
#include "llvm/CodeGen/MachineInstr.h"
@@ -34,16 +33,19 @@
#include "llvm/CodeGen/LiveRange.h"
#include "llvm/CodeGen/RegClass.h"
-/*
- #ifndef size_type
- #define size_type (unsigned int)
- #endif
-*/
-
typedef hash_map <const Value *, LiveRange *, hashFuncValue> LiveRangeMapType;
typedef vector <const MachineInstr *> CallRetInstrListType;
+
+
+//----------------------------------------------------------------------------
+// Class LiveRangeInfo
+//
+// Constructs and keeps the LiveRangMap which contains all the live
+// ranges used in a method. Also contain methods to coalesce live ranges.
+//----------------------------------------------------------------------------
+
class LiveRangeInfo
{
@@ -51,15 +53,21 @@
const Method *const Meth; // Method for which live range info is held
- LiveRangeMapType LiveRangeMap; // A map from Value * to LiveRange *
+ LiveRangeMapType LiveRangeMap; // A map from Value * to LiveRange * to
+ // record all live ranges in a method
// created by constructLiveRanges
-
+
const TargetMachine& TM; // target machine description
+
vector<RegClass *> & RegClassList;// a vector containing register classess
+
const MachineRegInfo& MRI; // machine reg info
CallRetInstrListType CallRetInstrList; // a list of all call/ret instrs
+
+ //------------ Private methods (see LiveRangeInfo.cpp for description)-------
+
void unionAndUpdateLRs(LiveRange *L1, LiveRange *L2);
void addInterference(const Instruction *const Inst,
@@ -67,37 +75,55 @@
void suggestRegs4CallRets();
+ const Method* getMethod() { return Meth; }
+
+
public:
LiveRangeInfo(const Method *const M,
const TargetMachine& tm,
vector<RegClass *> & RCList);
+
+ // Destructor to destroy all LiveRanges in the LiveRange Map
+ ~LiveRangeInfo();
+
+ // Main entry point for live range construction
+ //
void constructLiveRanges();
- const Method* getMethod() { return Meth; }
-
+ // This method is used to add a live range created elsewhere (e.g.,
+ // in machine specific code) to the common live range map
+ //
inline void addLRToMap(const Value *Val, LiveRange *LR) {
assert( Val && LR && "Val/LR is NULL!\n");
assert( (! LiveRangeMap[ Val ]) && "LR already set in map");
LiveRangeMap[ Val ] = LR;
}
-
+ // return the common live range map for this method
+ //
inline const LiveRangeMapType *const getLiveRangeMap() const
{ return &LiveRangeMap; }
+ // Method sed to get the corresponding live range of a Value
+ //
inline LiveRange *getLiveRangeForValue( const Value *const Val)
{ return LiveRangeMap[ Val ]; }
+ // Method used to get the Call and Return instruction list
+ //
inline CallRetInstrListType &getCallRetInstrList() {
return CallRetInstrList;
}
-
-
+ // Method for coalescing live ranges. Called only after interference info
+ // is calculated.
+ //
void coalesceLRs();
+ // debugging method to print the live ranges
+ //
void printLiveRanges();
};
diff --git a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
index f76e68b..9d34557 100644
--- a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
+++ b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
@@ -4,6 +4,7 @@
Purpose: This is the main entry point for register allocation.
Notes:
+ =====
* RegisterClasses: Each RegClass accepts a
MachineRegClass which contains machine specific info about that register
@@ -14,18 +15,18 @@
* Machine dependent work: All parts of the register coloring algorithm
except coloring of an individual node are machine independent.
- Register allocation must be done as:
+ Register allocation must be done as:
- static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
+ MethodLiveVarInfo LVI(*MethodI ); // compute LV info
+ LVI.analyze();
- MethodLiveVarInfo LVI(*MethodI ); // compute LV info
- LVI.analyze();
+ TargetMachine &target = ....
- PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
- PRA.allocateRegisters();
- Assumptions:
- All values in a live range will be of the same physical reg class.
+ PhyRegAlloc PRA(*MethodI, target, &LVI); // allocate regs
+ PRA.allocateRegisters();
+
+
*/
@@ -36,6 +37,7 @@
#include "llvm/CodeGen/RegClass.h"
#include "llvm/CodeGen/LiveRangeInfo.h"
#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+#include "llvm/Analysis/LoopDepth.h"
#include <deque>
@@ -82,15 +84,15 @@
const MachineRegInfo &MRI; // Machine Register information
const unsigned NumOfRegClasses; // recorded here for efficiency
- //vector<const Instruction *> CallInstrList; // a list of all call instrs
- //vector<const Instruction *> RetInstrList; // a list of all return instrs
-
AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
+ LoopDepthCalculator LoopDepthCalc; // to calculate loop depths
+ ReservedColorListType ResColList; // A set of reserved regs if desired.
+ // currently not used
- //vector<const MachineInstr *> PhiInstList; // a list of all phi instrs
- //------- private methods ---------------------------------------------------
+
+ //------- ------------------ private methods---------------------------------
void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
const bool isCallInst);
@@ -98,8 +100,6 @@
void addInterferencesForArgs();
void createIGNodeListsAndIGs();
void buildInterferenceGraphs();
- //void insertCallerSavingCode(const MachineInstr *MInst,
- // const BasicBlock *BB );
void setCallInterferences(const MachineInstr *MInst,
const LiveVarSet *const LVSetAft );
@@ -147,7 +147,11 @@
PhyRegAlloc(Method *const M, const TargetMachine& TM,
MethodLiveVarInfo *const Lvi);
- void allocateRegisters(); // main method called for allocatin
+ ~PhyRegAlloc();
+
+ // main method called for allocating registers
+ //
+ void allocateRegisters();
};
diff --git a/lib/Target/SparcV9/RegAlloc/RegClass.h b/lib/Target/SparcV9/RegAlloc/RegClass.h
index 3fb448a..d6cbaf8 100644
--- a/lib/Target/SparcV9/RegAlloc/RegClass.h
+++ b/lib/Target/SparcV9/RegAlloc/RegClass.h
@@ -3,17 +3,6 @@
Date: Aug 20, 01
Purpose: Contains machine independent methods for register coloring.
- This is the class that contains all data structures and common algos
- for coloring a particular register class (e.g., int class, fp class).
- This class is hardware independent. This class accepts a hardware
- dependent description of machine registers (MachineRegInfo class) to
- get hardware specific info and color and indidual IG node.
-
- This class contains the InterferenceGraph (IG).
- Also it contains an IGNode stack that can be used for coloring.
- The class provides some easy access methods to the IG methods, since these
- methods are called thru a register class.
-
*/
#ifndef REG_CLASS_H
@@ -28,6 +17,23 @@
typedef vector<unsigned int> ReservedColorListType;
+//-----------------------------------------------------------------------------
+// Class RegClass
+//
+// Implements a machine independant register class.
+//
+// This is the class that contains all data structures and common algos
+// for coloring a particular register class (e.g., int class, fp class).
+// This class is hardware independent. This class accepts a hardware
+// dependent description of machine registers (MachineRegInfo class) to
+// get hardware specific info and to color an individual IG node.
+//
+// This class contains the InterferenceGraph (IG).
+// Also it contains an IGNode stack that can be used for coloring.
+// The class provides some easy access methods to the IG methods, since these
+// methods are called thru a register class.
+//
+//-----------------------------------------------------------------------------
class RegClass
{
@@ -42,28 +48,37 @@
// buildInterferenceGraph
stack <IGNode *> IGNodeStack; // the stack used for coloring
- // for passing registered that are pre-allocated (e.g., %g's)
const ReservedColorListType *const ReservedColorList;
-
+ //
+ // for passing registers that are pre-allocated and cannot be used by the
+ // register allocator for this method.
+
+ bool *IsColorUsedArr;
+ //
// An array used for coloring each node. This array must be of size
// MRC->getNumOfAllRegs(). Allocated once in the constructor
// for efficiency.
- bool *IsColorUsedArr;
- //------------ private methods ------------------
+ //--------------------------- private methods ------------------------------
void pushAllIGNodes();
+
bool pushUnconstrainedIGNodes();
+
IGNode * getIGNodeWithMinSpillCost();
+
void colorIGNode(IGNode *const Node);
+
public:
RegClass(const Method *const M,
const MachineRegClassInfo *const MRC,
const ReservedColorListType *const RCL = NULL);
+ ~RegClass() { delete[] IsColorUsedArr; };
+
inline void createInterferenceGraph()
{ IG.createGraph(); }
@@ -71,19 +86,17 @@
inline const unsigned getID() const { return RegClassID; }
- void colorAllRegs(); // main method called for coloring regs
+ // main method called for coloring regs
+ //
+ void colorAllRegs();
inline unsigned getNumOfAvailRegs() const
{ return MRC->getNumOfAvailRegs(); }
- ~RegClass() { delete[] IsColorUsedArr; };
-
-
// --- following methods are provided to access the IG contained within this
// ---- RegClass easilly.
-
inline void addLRToIG(LiveRange *const LR)
{ IG.addLRToIG(LR); }