aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/CodeGen/RegAlloc/InterferenceGraph.h76
-rw-r--r--lib/CodeGen/RegAlloc/PhyRegAlloc.h106
-rw-r--r--lib/CodeGen/RegAlloc/RegAllocCommon.h10
-rw-r--r--lib/CodeGen/RegAlloc/RegClass.h125
-rw-r--r--lib/Target/SparcV9/RegAlloc/InterferenceGraph.h76
-rw-r--r--lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h106
-rw-r--r--lib/Target/SparcV9/RegAlloc/RegAllocCommon.h10
-rw-r--r--lib/Target/SparcV9/RegAlloc/RegClass.h125
8 files changed, 634 insertions, 0 deletions
diff --git a/lib/CodeGen/RegAlloc/InterferenceGraph.h b/lib/CodeGen/RegAlloc/InterferenceGraph.h
new file mode 100644
index 0000000000..99dea8fbe0
--- /dev/null
+++ b/lib/CodeGen/RegAlloc/InterferenceGraph.h
@@ -0,0 +1,76 @@
+/* Title: InterferenceGraph.h
+ Author: Ruchira Sasanka
+ Date: July 20, 01
+ Purpose: Interference Graph used for register coloring.
+
+ Notes:
+ Adj Info is stored in the lower trangular matrix (i.e., row > col )
+
+ This class must be used in the following way:
+
+ * Construct class
+ * call addLRToIG as many times to add ALL LRs to this IG
+ * call createGraph to create the actual matrix
+ * Then setInterference, getInterference, mergeIGNodesOfLRs can be
+ called as desired to modify the graph.
+ * Once the modifications to the graph are over, call
+ setCurDegreeOfIGNodes() before pushing IGNodes on to stack for coloring.
+*/
+
+
+#ifndef INTERFERENCE_GRAPH_H
+#define INTERFERENCE_GRAPH_H
+
+
+#include "llvm/CodeGen/IGNode.h"
+
+typedef vector <IGNode *> IGNodeListType;
+
+
+class InterferenceGraph
+{
+ char **IG; // a poiner to the interference graph
+ unsigned int Size; // size of a side of the IG
+ RegClass *const RegCl; // RegCl contains this IG
+ IGNodeListType IGNodeList; // a list of all IGNodes in a reg class
+
+ // for asserting this IG node is infact in the IGNodeList of this class
+ inline void assertIGNode(const IGNode *const Node) const {
+ assert( IGNodeList[ Node->getIndex() ] == Node );
+ }
+
+
+
+ public:
+
+ // the matrix is not yet created by the constructor. Call createGraph()
+ // to create it after adding all IGNodes to the IGNodeList
+
+ InterferenceGraph(RegClass *const RC);
+ void createGraph();
+
+ void addLRToIG(LiveRange *const LR);
+
+ void setInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2 );
+
+ unsigned getInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2 ) const ;
+
+ void mergeIGNodesOfLRs(const LiveRange *const LR1, LiveRange *const LR2);
+
+ inline IGNodeListType &getIGNodeList() { return IGNodeList; }
+
+ void setCurDegreeOfIGNodes();
+
+ void printIG() const;
+ void printIGNodeList() const;
+
+ ~InterferenceGraph();
+
+
+};
+
+
+#endif
+
diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.h b/lib/CodeGen/RegAlloc/PhyRegAlloc.h
new file mode 100644
index 0000000000..bcb8aa56ea
--- /dev/null
+++ b/lib/CodeGen/RegAlloc/PhyRegAlloc.h
@@ -0,0 +1,106 @@
+/* Title: PhyRegAlloc.h
+ Author: Ruchira Sasanka
+ Date: Aug 20, 01
+ 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
+ class. The code in the RegClass is machine independent and they use
+ access functions in the MachineRegClass object passed into it to get
+ machine specific info.
+
+ * 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:
+
+ static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
+
+ MethodLiveVarInfo LVI(*MethodI ); // compute LV info
+ LVI.analyze();
+
+ PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
+ PRA.allocateRegisters();
+
+ Assumptions:
+ All values in a live range will be of the same physical reg class.
+
+*/
+
+
+
+#ifndef PHY_REG_ALLOC_H
+#define PHY_REG_ALLOC_H
+
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/Sparc.h"
+
+#include "llvm/CodeGen/RegClass.h"
+#include "llvm/CodeGen/LiveRangeInfo.h"
+#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+
+
+class AddedInstrns
+{
+ public:
+ vector<const MachineInstr *> InstrnsBefore;
+ vector<const MachineInstr *> InstrnsAfter;
+
+ AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
+};
+
+typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
+
+
+
+class PhyRegAlloc
+{
+
+ vector<RegClass *> RegClassList ; // vector of register classes
+ const Method *const Meth; // name of the method we work on
+ const TargetMachine &TM; // target machine
+ MethodLiveVarInfo *const LVI; // LV information for this method
+ // (already computed for BBs)
+ LiveRangeInfo LRI; // LR info (will be computed)
+ const MachineRegInfo &MRI; // Machine Register information
+ const unsigned NumOfRegClasses; // recorded here for efficiency
+
+ vector<const Instruction *> CallInstrList; // a list of all call instrs
+
+ AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
+
+
+ //------- private methods ---------------------------------------------------
+
+ void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
+ const bool isCallInst);
+
+ void addInterferencesForArgs();
+ void createIGNodeListsAndIGs();
+ void buildInterferenceGraphs();
+
+ inline void constructLiveRanges()
+ { LRI.constructLiveRanges(); }
+
+ void colorIncomingArgs();
+ void updateMachineCode();
+
+ public:
+ PhyRegAlloc(const Method *const M, const TargetMachine& TM,
+ MethodLiveVarInfo *const Lvi);
+
+ void allocateRegisters(); // main method called for allocatin
+
+};
+
+
+
+
+
+
+
+
+#endif
+
diff --git a/lib/CodeGen/RegAlloc/RegAllocCommon.h b/lib/CodeGen/RegAlloc/RegAllocCommon.h
new file mode 100644
index 0000000000..2e3286a887
--- /dev/null
+++ b/lib/CodeGen/RegAlloc/RegAllocCommon.h
@@ -0,0 +1,10 @@
+#ifndef REG_ALLOC_COMMON_H
+#define REG_ALLOC_COMMON_H
+
+// set DEBUG_RA for printing out debug messages
+// if DEBUG_RA is 1 normal output messages
+// if DEBUG_RA is 2 extensive debug info for each instr
+
+#define DEBUG_RA (1)
+
+#endif
diff --git a/lib/CodeGen/RegAlloc/RegClass.h b/lib/CodeGen/RegAlloc/RegClass.h
new file mode 100644
index 0000000000..1d08502445
--- /dev/null
+++ b/lib/CodeGen/RegAlloc/RegClass.h
@@ -0,0 +1,125 @@
+/* Title: RegClass.h
+ Author: Ruchira Sasanka
+ 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
+#define REG_CLASS_H
+
+#include "llvm/CodeGen/IGNode.h"
+#include "llvm/CodeGen/InterferenceGraph.h"
+#include "llvm/CodeGen/TargetMachine.h"
+
+
+#include <stack>
+
+
+typedef vector<unsigned int> ReservedColorListType;
+
+
+class RegClass
+{
+
+ private:
+ const Method *const Meth; // Method we are working on
+
+ const MachineRegClassInfo *const MRC; // corresponding MRC
+
+ const unsigned RegClassID; // my int ID
+
+ InterferenceGraph IG; // Interference graph - constructed by
+ // buildInterferenceGraph
+ stack <IGNode *> IGNodeStack; // the stack used for coloring
+
+ // for passing registered that are pre-allocated (e.g., %g's)
+ const ReservedColorListType *const ReservedColorList;
+
+ // 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 ------------------
+
+ 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);
+
+ inline void createInterferenceGraph()
+ { IG.createGraph(); }
+
+ inline InterferenceGraph &getIG() { return IG; }
+
+ inline const unsigned getID() const { return RegClassID; }
+
+ void colorAllRegs(); // main method called for coloring regs
+
+ 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); }
+
+ inline void setInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2)
+ { IG.setInterference(LR1, LR2); }
+
+ inline unsigned getInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2) const
+ { return IG.getInterference(LR1, LR2); }
+
+ inline void mergeIGNodesOfLRs(const LiveRange *const LR1,
+ LiveRange *const LR2)
+ { IG.mergeIGNodesOfLRs(LR1, LR2); }
+
+
+ inline void printIGNodeList() const {
+ cout << "IG Nodes for Register Class " << RegClassID << ":" << endl;
+ IG.printIGNodeList();
+ }
+
+ inline void printIG() {
+ cout << "IG for Register Class " << RegClassID << ":" << endl;
+ IG.printIG();
+ }
+
+};
+
+
+
+
+
+
+
+#endif
diff --git a/lib/Target/SparcV9/RegAlloc/InterferenceGraph.h b/lib/Target/SparcV9/RegAlloc/InterferenceGraph.h
new file mode 100644
index 0000000000..99dea8fbe0
--- /dev/null
+++ b/lib/Target/SparcV9/RegAlloc/InterferenceGraph.h
@@ -0,0 +1,76 @@
+/* Title: InterferenceGraph.h
+ Author: Ruchira Sasanka
+ Date: July 20, 01
+ Purpose: Interference Graph used for register coloring.
+
+ Notes:
+ Adj Info is stored in the lower trangular matrix (i.e., row > col )
+
+ This class must be used in the following way:
+
+ * Construct class
+ * call addLRToIG as many times to add ALL LRs to this IG
+ * call createGraph to create the actual matrix
+ * Then setInterference, getInterference, mergeIGNodesOfLRs can be
+ called as desired to modify the graph.
+ * Once the modifications to the graph are over, call
+ setCurDegreeOfIGNodes() before pushing IGNodes on to stack for coloring.
+*/
+
+
+#ifndef INTERFERENCE_GRAPH_H
+#define INTERFERENCE_GRAPH_H
+
+
+#include "llvm/CodeGen/IGNode.h"
+
+typedef vector <IGNode *> IGNodeListType;
+
+
+class InterferenceGraph
+{
+ char **IG; // a poiner to the interference graph
+ unsigned int Size; // size of a side of the IG
+ RegClass *const RegCl; // RegCl contains this IG
+ IGNodeListType IGNodeList; // a list of all IGNodes in a reg class
+
+ // for asserting this IG node is infact in the IGNodeList of this class
+ inline void assertIGNode(const IGNode *const Node) const {
+ assert( IGNodeList[ Node->getIndex() ] == Node );
+ }
+
+
+
+ public:
+
+ // the matrix is not yet created by the constructor. Call createGraph()
+ // to create it after adding all IGNodes to the IGNodeList
+
+ InterferenceGraph(RegClass *const RC);
+ void createGraph();
+
+ void addLRToIG(LiveRange *const LR);
+
+ void setInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2 );
+
+ unsigned getInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2 ) const ;
+
+ void mergeIGNodesOfLRs(const LiveRange *const LR1, LiveRange *const LR2);
+
+ inline IGNodeListType &getIGNodeList() { return IGNodeList; }
+
+ void setCurDegreeOfIGNodes();
+
+ void printIG() const;
+ void printIGNodeList() const;
+
+ ~InterferenceGraph();
+
+
+};
+
+
+#endif
+
diff --git a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
new file mode 100644
index 0000000000..bcb8aa56ea
--- /dev/null
+++ b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h
@@ -0,0 +1,106 @@
+/* Title: PhyRegAlloc.h
+ Author: Ruchira Sasanka
+ Date: Aug 20, 01
+ 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
+ class. The code in the RegClass is machine independent and they use
+ access functions in the MachineRegClass object passed into it to get
+ machine specific info.
+
+ * 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:
+
+ static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
+
+ MethodLiveVarInfo LVI(*MethodI ); // compute LV info
+ LVI.analyze();
+
+ PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
+ PRA.allocateRegisters();
+
+ Assumptions:
+ All values in a live range will be of the same physical reg class.
+
+*/
+
+
+
+#ifndef PHY_REG_ALLOC_H
+#define PHY_REG_ALLOC_H
+
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/Sparc.h"
+
+#include "llvm/CodeGen/RegClass.h"
+#include "llvm/CodeGen/LiveRangeInfo.h"
+#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+
+
+class AddedInstrns
+{
+ public:
+ vector<const MachineInstr *> InstrnsBefore;
+ vector<const MachineInstr *> InstrnsAfter;
+
+ AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
+};
+
+typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
+
+
+
+class PhyRegAlloc
+{
+
+ vector<RegClass *> RegClassList ; // vector of register classes
+ const Method *const Meth; // name of the method we work on
+ const TargetMachine &TM; // target machine
+ MethodLiveVarInfo *const LVI; // LV information for this method
+ // (already computed for BBs)
+ LiveRangeInfo LRI; // LR info (will be computed)
+ const MachineRegInfo &MRI; // Machine Register information
+ const unsigned NumOfRegClasses; // recorded here for efficiency
+
+ vector<const Instruction *> CallInstrList; // a list of all call instrs
+
+ AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
+
+
+ //------- private methods ---------------------------------------------------
+
+ void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
+ const bool isCallInst);
+
+ void addInterferencesForArgs();
+ void createIGNodeListsAndIGs();
+ void buildInterferenceGraphs();
+
+ inline void constructLiveRanges()
+ { LRI.constructLiveRanges(); }
+
+ void colorIncomingArgs();
+ void updateMachineCode();
+
+ public:
+ PhyRegAlloc(const Method *const M, const TargetMachine& TM,
+ MethodLiveVarInfo *const Lvi);
+
+ void allocateRegisters(); // main method called for allocatin
+
+};
+
+
+
+
+
+
+
+
+#endif
+
diff --git a/lib/Target/SparcV9/RegAlloc/RegAllocCommon.h b/lib/Target/SparcV9/RegAlloc/RegAllocCommon.h
new file mode 100644
index 0000000000..2e3286a887
--- /dev/null
+++ b/lib/Target/SparcV9/RegAlloc/RegAllocCommon.h
@@ -0,0 +1,10 @@
+#ifndef REG_ALLOC_COMMON_H
+#define REG_ALLOC_COMMON_H
+
+// set DEBUG_RA for printing out debug messages
+// if DEBUG_RA is 1 normal output messages
+// if DEBUG_RA is 2 extensive debug info for each instr
+
+#define DEBUG_RA (1)
+
+#endif
diff --git a/lib/Target/SparcV9/RegAlloc/RegClass.h b/lib/Target/SparcV9/RegAlloc/RegClass.h
new file mode 100644
index 0000000000..1d08502445
--- /dev/null
+++ b/lib/Target/SparcV9/RegAlloc/RegClass.h
@@ -0,0 +1,125 @@
+/* Title: RegClass.h
+ Author: Ruchira Sasanka
+ 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
+#define REG_CLASS_H
+
+#include "llvm/CodeGen/IGNode.h"
+#include "llvm/CodeGen/InterferenceGraph.h"
+#include "llvm/CodeGen/TargetMachine.h"
+
+
+#include <stack>
+
+
+typedef vector<unsigned int> ReservedColorListType;
+
+
+class RegClass
+{
+
+ private:
+ const Method *const Meth; // Method we are working on
+
+ const MachineRegClassInfo *const MRC; // corresponding MRC
+
+ const unsigned RegClassID; // my int ID
+
+ InterferenceGraph IG; // Interference graph - constructed by
+ // buildInterferenceGraph
+ stack <IGNode *> IGNodeStack; // the stack used for coloring
+
+ // for passing registered that are pre-allocated (e.g., %g's)
+ const ReservedColorListType *const ReservedColorList;
+
+ // 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 ------------------
+
+ 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);
+
+ inline void createInterferenceGraph()
+ { IG.createGraph(); }
+
+ inline InterferenceGraph &getIG() { return IG; }
+
+ inline const unsigned getID() const { return RegClassID; }
+
+ void colorAllRegs(); // main method called for coloring regs
+
+ 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); }
+
+ inline void setInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2)
+ { IG.setInterference(LR1, LR2); }
+
+ inline unsigned getInterference(const LiveRange *const LR1,
+ const LiveRange *const LR2) const
+ { return IG.getInterference(LR1, LR2); }
+
+ inline void mergeIGNodesOfLRs(const LiveRange *const LR1,
+ LiveRange *const LR2)
+ { IG.mergeIGNodesOfLRs(LR1, LR2); }
+
+
+ inline void printIGNodeList() const {
+ cout << "IG Nodes for Register Class " << RegClassID << ":" << endl;
+ IG.printIGNodeList();
+ }
+
+ inline void printIG() {
+ cout << "IG for Register Class " << RegClassID << ":" << endl;
+ IG.printIG();
+ }
+
+};
+
+
+
+
+
+
+
+#endif
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-03 23:12:28 +0000