diff options
author | Chris Lattner <sabre@nondot.org> | 2004-01-09 06:17:12 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2004-01-09 06:17:12 +0000 |
commit | 75e260990d81fdddd8660bbee854cb2c0d4c42c9 (patch) | |
tree | 072ba6fe423815512af7093859c0a6ae38689c24 | |
parent | f7703df4968084c18c248c1feea9961c19a32e6a (diff) | |
download | external_llvm-75e260990d81fdddd8660bbee854cb2c0d4c42c9.zip external_llvm-75e260990d81fdddd8660bbee854cb2c0d4c42c9.tar.gz external_llvm-75e260990d81fdddd8660bbee854cb2c0d4c42c9.tar.bz2 |
Move lib/Codegen/RegAlloc into lib/Target/Sparc, as it is sparc specific
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10728 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/CodeGen/Makefile | 2 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/AllocInfo.h | 84 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/IGNode.cpp | 62 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/IGNode.h | 123 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/InterferenceGraph.cpp | 252 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/InterferenceGraph.h | 75 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/LiveRange.h | 184 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/LiveRangeInfo.cpp | 416 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/LiveRangeInfo.h | 128 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/Makefile | 17 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/PhyRegAlloc.cpp | 1397 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/PhyRegAlloc.h | 186 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/RegAllocCommon.h | 32 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/RegClass.cpp | 250 | ||||
-rw-r--r-- | lib/CodeGen/RegAlloc/RegClass.h | 147 | ||||
-rw-r--r-- | lib/Target/SparcV9/Makefile | 1 | ||||
-rw-r--r-- | lib/Target/SparcV9/RegAlloc/Makefile | 2 |
17 files changed, 3 insertions, 3355 deletions
diff --git a/lib/CodeGen/Makefile b/lib/CodeGen/Makefile index 4463921..e5c81e8 100644 --- a/lib/CodeGen/Makefile +++ b/lib/CodeGen/Makefile @@ -7,7 +7,7 @@ # ##===----------------------------------------------------------------------===## LEVEL = ../.. -PARALLEL_DIRS = InstrSelection InstrSched RegAlloc SelectionDAG +PARALLEL_DIRS = InstrSelection InstrSched SelectionDAG LIBRARYNAME = codegen include $(LEVEL)/Makefile.common diff --git a/lib/CodeGen/RegAlloc/AllocInfo.h b/lib/CodeGen/RegAlloc/AllocInfo.h deleted file mode 100644 index 67f58a7..0000000 --- a/lib/CodeGen/RegAlloc/AllocInfo.h +++ /dev/null @@ -1,84 +0,0 @@ -//===-- AllocInfo.h - Store info about regalloc decisions -------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This header file contains the data structure used to save the state -// of the global, graph-coloring register allocator. -// -//===----------------------------------------------------------------------===// - -#ifndef ALLOCINFO_H -#define ALLOCINFO_H - -#include "llvm/Type.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constants.h" - -namespace llvm { - -/// AllocInfo - Structure representing one instruction's operand's-worth of -/// register allocation state. We create tables made out of these data -/// structures to generate mapping information for this register allocator. -/// -struct AllocInfo { - unsigned Instruction; - int Operand; // (-1 if Instruction, or 0...n-1 for an operand.) - enum AllocStateTy { NotAllocated = 0, Allocated, Spilled }; - AllocStateTy AllocState; - int Placement; - - AllocInfo (unsigned Instruction_, unsigned Operand_, - AllocStateTy AllocState_, int Placement_) : - Instruction (Instruction_), Operand (Operand_), - AllocState (AllocState_), Placement (Placement_) { } - - /// getConstantType - Return a StructType representing an AllocInfo object. - /// - static StructType *getConstantType () { - std::vector<const Type *> TV; - TV.push_back (Type::UIntTy); - TV.push_back (Type::IntTy); - TV.push_back (Type::UIntTy); - TV.push_back (Type::IntTy); - return StructType::get (TV); - } - - /// toConstant - Convert this AllocInfo into an LLVM Constant of type - /// getConstantType(), and return the Constant. - /// - Constant *toConstant () const { - StructType *ST = getConstantType (); - std::vector<Constant *> CV; - CV.push_back (ConstantUInt::get (Type::UIntTy, Instruction)); - CV.push_back (ConstantSInt::get (Type::IntTy, Operand)); - CV.push_back (ConstantUInt::get (Type::UIntTy, AllocState)); - CV.push_back (ConstantSInt::get (Type::IntTy, Placement)); - return ConstantStruct::get (ST, CV); - } - - /// AllocInfos compare equal if the allocation placements are equal - /// (i.e., they can be equal even if they refer to operands from two - /// different instructions.) - /// - bool operator== (const AllocInfo &X) const { - return (X.AllocState == AllocState) && (X.Placement == Placement); - } - bool operator!= (const AllocInfo &X) const { return !(*this == X); } - - /// Returns a human-readable string representation of the AllocState member. - /// - const std::string allocStateToString () const { - static const char *AllocStateNames[] = - { "NotAllocated", "Allocated", "Spilled" }; - return std::string (AllocStateNames[AllocState]); - } -}; - -} // End llvm namespace - -#endif // ALLOCINFO_H diff --git a/lib/CodeGen/RegAlloc/IGNode.cpp b/lib/CodeGen/RegAlloc/IGNode.cpp deleted file mode 100644 index a76fdea..0000000 --- a/lib/CodeGen/RegAlloc/IGNode.cpp +++ /dev/null @@ -1,62 +0,0 @@ -//===-- IGNode.cpp --------------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements an Interference graph node for coloring-based register -// allocation. -// -//===----------------------------------------------------------------------===// - -#include "IGNode.h" -#include <algorithm> -#include <iostream> - -namespace llvm { - -//----------------------------------------------------------------------------- -// Sets this IGNode on stack and reduce the degree of neighbors -//----------------------------------------------------------------------------- - -void IGNode::pushOnStack() { - OnStack = true; - int neighs = AdjList.size(); - - if (neighs < 0) { - std::cerr << "\nAdj List size = " << neighs; - assert(0 && "Invalid adj list size"); - } - - for (int i=0; i < neighs; i++) - AdjList[i]->decCurDegree(); -} - -//----------------------------------------------------------------------------- -// Deletes an adjacency node. IGNodes are deleted when coalescing merges -// two IGNodes together. -//----------------------------------------------------------------------------- - -void IGNode::delAdjIGNode(const IGNode *Node) { - std::vector<IGNode *>::iterator It=find(AdjList.begin(), AdjList.end(), Node); - assert(It != AdjList.end() && "The node must be there!"); - AdjList.erase(It); -} - -//----------------------------------------------------------------------------- -// Get the number of unique neighbors if these two nodes are merged -//----------------------------------------------------------------------------- - -unsigned -IGNode::getCombinedDegree(const IGNode* otherNode) const { - std::vector<IGNode*> nbrs(AdjList); - nbrs.insert(nbrs.end(), otherNode->AdjList.begin(), otherNode->AdjList.end()); - sort(nbrs.begin(), nbrs.end()); - std::vector<IGNode*>::iterator new_end = unique(nbrs.begin(), nbrs.end()); - return new_end - nbrs.begin(); -} - -} // End llvm namespace diff --git a/lib/CodeGen/RegAlloc/IGNode.h b/lib/CodeGen/RegAlloc/IGNode.h deleted file mode 100644 index 9fdc7a6..0000000 --- a/lib/CodeGen/RegAlloc/IGNode.h +++ /dev/null @@ -1,123 +0,0 @@ -//===-- IGNode.h - Represent a node in an interference graph ----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file represents a node in an interference graph. -// -// For efficiency, the AdjList is updated only once - ie. we can add but not -// remove nodes from AdjList. -// -// The removal of nodes from IG is simulated by decrementing the CurDegree. -// If this node is put on stack (that is removed from IG), the CurDegree of all -// the neighbors are decremented and this node is marked OnStack. Hence -// the effective neighbors in the AdjList are the ones that do not have the -// OnStack flag set (therefore, they are in the IG). -// -// The methods that modify/use the CurDegree must be called only -// after all modifications to the IG are over (i.e., all neighbors are fixed). -// -// The vector representation is the most efficient one for adj list. -// Though nodes are removed when coalescing is done, we access it in sequence -// for far many times when coloring (colorNode()). -// -//===----------------------------------------------------------------------===// - -#ifndef IGNODE_H -#define IGNODE_H - -#include "LiveRange.h" -#include <vector> - -namespace llvm { - -class RegClass; - -//---------------------------------------------------------------------------- -// Class IGNode -// -// Represents a node in an interference graph. -//---------------------------------------------------------------------------- - -class IGNode { - const unsigned Index; // index within IGNodeList - bool OnStack; // this has been pushed on to stack for coloring - std::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. - - LiveRange *const ParentLR; -public: - - IGNode(LiveRange *LR, unsigned index) : Index(index), ParentLR(LR) { - OnStack = false; - CurDegree = -1; - ParentLR->setUserIGNode(this); - } - - inline unsigned int getIndex() const { return Index; } - - // adjLists must be updated only once. However, the CurDegree can be changed - // - inline void addAdjIGNode(IGNode *AdjNode) { AdjList.push_back(AdjNode); } - - inline IGNode *getAdjIGNode(unsigned ind) const - { assert ( ind < AdjList.size()); return AdjList[ind]; } - - // delete a node in AdjList - node must be in the list - // should not be called often - // - void delAdjIGNode(const IGNode *Node); - - inline unsigned getNumOfNeighbors() const { return AdjList.size(); } - - // Get the number of unique neighbors if these two nodes are merged - unsigned getCombinedDegree(const IGNode* otherNode) const; - - inline bool isOnStack() const { 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(); - } - - inline int getCurDegree() const { return CurDegree; } - - // called when a neigh is pushed on to stack - // - inline void decCurDegree() { assert(CurDegree > 0); --CurDegree; } - - // The following methods call the methods in ParentLR - // They are added to this class for convenience - // If many of these are called within a single scope, - // consider calling the methods directly on LR - inline bool hasColor() const { return ParentLR->hasColor(); } - - inline unsigned int getColor() const { return ParentLR->getColor(); } - - inline void setColor(unsigned Col) { ParentLR->setColor(Col); } - - inline LiveRange *getParentLR() const { return ParentLR; } -}; - -} // End llvm namespace - -#endif diff --git a/lib/CodeGen/RegAlloc/InterferenceGraph.cpp b/lib/CodeGen/RegAlloc/InterferenceGraph.cpp deleted file mode 100644 index 3cef19e..0000000 --- a/lib/CodeGen/RegAlloc/InterferenceGraph.cpp +++ /dev/null @@ -1,252 +0,0 @@ -//===-- InterferenceGraph.cpp ---------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Interference graph for coloring-based register allocation for LLVM. -// -//===----------------------------------------------------------------------===// - -#include "IGNode.h" -#include "InterferenceGraph.h" -#include "RegAllocCommon.h" -#include "Support/STLExtras.h" -#include <algorithm> - -namespace llvm { - -// for asserting this IG node is infact in the IGNodeList of this class -inline static void assertIGNode(const InterferenceGraph *IG, - const IGNode *Node) { - assert(IG->getIGNodeList()[Node->getIndex()] == Node); -} - -//----------------------------------------------------------------------------- -// Constructor: Records the RegClass and initalizes IGNodeList. -// The matrix is NOT yet created by the constructor. Call createGraph() -// to create it after adding all IGNodes to the IGNodeList. -//----------------------------------------------------------------------------- -InterferenceGraph::InterferenceGraph(RegClass *const RC) : RegCl(RC) { - IG = NULL; - Size = 0; - if( DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << "Interference graph created!\n"; -} - - -//----------------------------------------------------------------------------- -// destructor. Deletes the bit matrix and all IGNodes -//----------------------------------------------------------------------------- -InterferenceGraph:: ~InterferenceGraph() { - // delete the matrix - for(unsigned int r=0; r < IGNodeList.size(); ++r) - delete[] IG[r]; - delete[] IG; - - // delete all IGNodes in the IGNodeList - for_each(IGNodeList.begin(), IGNodeList.end(), deleter<IGNode>); -} - - - -//----------------------------------------------------------------------------- -// Creates (dynamically allocates) the bit matrix necessary to hold the -// interference graph. -//----------------------------------------------------------------------------- -void InterferenceGraph::createGraph() -{ - Size = IGNodeList.size(); - IG = new char*[Size]; - for( unsigned int r=0; r < Size; ++r) - IG[r] = new char[Size]; - - // init IG matrix - for(unsigned int i=0; i < Size; i++) - for(unsigned int j=0; j < Size; j++) - IG[i][j] = 0; -} - -//----------------------------------------------------------------------------- -// creates a new IGNode for the given live range and add to IG -//----------------------------------------------------------------------------- -void InterferenceGraph::addLRToIG(LiveRange *const LR) -{ - IGNodeList.push_back(new IGNode(LR, IGNodeList.size())); -} - - -//----------------------------------------------------------------------------- -// set interference for two live ranges -// update both the matrix and AdjLists of nodes. -// If there is already an interference between LR1 and LR2, adj lists -// are not updated. LR1 and LR2 must be distinct since if not, it suggests -// that there is some wrong logic in some other method. -//----------------------------------------------------------------------------- -void InterferenceGraph::setInterference(const LiveRange *const LR1, - const LiveRange *const LR2 ) { - assert(LR1 != LR2); - - IGNode *IGNode1 = LR1->getUserIGNode(); - IGNode *IGNode2 = LR2->getUserIGNode(); - - assertIGNode(this, IGNode1); - assertIGNode(this, IGNode2); - - unsigned row = IGNode1->getIndex(); - unsigned col = IGNode2->getIndex(); - - char *val; - - if( DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << "setting intf for: [" << row << "][" << col << "]\n"; - - ( row > col) ? val = &IG[row][col]: val = &IG[col][row]; - - if( ! (*val) ) { // if this interf is not previously set - *val = 1; // add edges between nodes - IGNode1->addAdjIGNode( IGNode2 ); - IGNode2->addAdjIGNode( IGNode1 ); - } - -} - - -//---------------------------------------------------------------------------- -// return whether two live ranges interfere -//---------------------------------------------------------------------------- -unsigned InterferenceGraph::getInterference(const LiveRange *const LR1, - const LiveRange *const LR2) const { - assert(LR1 != LR2); - assertIGNode(this, LR1->getUserIGNode()); - assertIGNode(this, LR2->getUserIGNode()); - - const unsigned int row = LR1->getUserIGNode()->getIndex(); - const unsigned int col = LR2->getUserIGNode()->getIndex(); - - char ret; - if (row > col) - ret = IG[row][col]; - else - ret = IG[col][row]; - return ret; - -} - - -//---------------------------------------------------------------------------- -// Merge 2 IGNodes. The neighbors of the SrcNode will be added to the DestNode. -// Then the IGNode2L will be deleted. Necessary for coalescing. -// IMPORTANT: The live ranges are NOT merged by this method. Use -// LiveRangeInfo::unionAndUpdateLRs for that purpose. -//---------------------------------------------------------------------------- - -void InterferenceGraph::mergeIGNodesOfLRs(const LiveRange *LR1, - LiveRange *LR2) { - - assert( LR1 != LR2); // cannot merge the same live range - - IGNode *const DestNode = LR1->getUserIGNode(); - IGNode *SrcNode = LR2->getUserIGNode(); - - assertIGNode(this, DestNode); - assertIGNode(this, SrcNode); - - if( DEBUG_RA >= RA_DEBUG_Interference) { - std::cerr << "Merging LRs: \""; printSet(*LR1); - std::cerr << "\" and \""; printSet(*LR2); - std::cerr << "\"\n"; - } - - unsigned SrcDegree = SrcNode->getNumOfNeighbors(); - const unsigned SrcInd = SrcNode->getIndex(); - - - // for all neighs of SrcNode - for(unsigned i=0; i < SrcDegree; i++) { - IGNode *NeighNode = SrcNode->getAdjIGNode(i); - - LiveRange *const LROfNeigh = NeighNode->getParentLR(); - - // delete edge between src and neigh - even neigh == dest - NeighNode->delAdjIGNode(SrcNode); - - // set the matrix posn to 0 betn src and neigh - even neigh == dest - const unsigned NInd = NeighNode->getIndex(); - ( SrcInd > NInd) ? (IG[SrcInd][NInd]=0) : (IG[NInd][SrcInd]=0) ; - - - if( LR1 != LROfNeigh) { // if the neigh != dest - - // add edge betwn Dest and Neigh - if there is no current edge - setInterference(LR1, LROfNeigh ); - } - - } - - IGNodeList[ SrcInd ] = NULL; - - // SrcNode is no longer necessary - LR2 must be deleted by the caller - delete( SrcNode ); - -} - - -//---------------------------------------------------------------------------- -// must be called after modifications to the graph are over but before -// pushing IGNodes on to the stack for coloring. -//---------------------------------------------------------------------------- -void InterferenceGraph::setCurDegreeOfIGNodes() -{ - unsigned Size = IGNodeList.size(); - - for( unsigned i=0; i < Size; i++) { - IGNode *Node = IGNodeList[i]; - if( Node ) - Node->setCurDegree(); - } -} - - - - - -//--------------------- debugging (Printing) methods ----------------------- - -//---------------------------------------------------------------------------- -// Print the IGnodes -//---------------------------------------------------------------------------- -void InterferenceGraph::printIG() const { - for(unsigned i=0; i < Size; i++) { - const IGNode *const Node = IGNodeList[i]; - if(Node) { - std::cerr << " [" << i << "] "; - - for( unsigned int j=0; j < Size; j++) - if(IG[i][j]) - std::cerr << "(" << i << "," << j << ") "; - std::cerr << "\n"; - } - } -} - -//---------------------------------------------------------------------------- -// Print the IGnodes in the IGNode List -//---------------------------------------------------------------------------- -void InterferenceGraph::printIGNodeList() const { - for(unsigned i=0; i < IGNodeList.size() ; ++i) { - const IGNode *const Node = IGNodeList[i]; - - if (Node) { - std::cerr << " [" << Node->getIndex() << "] "; - printSet(*Node->getParentLR()); - //int Deg = Node->getCurDegree(); - std::cerr << "\t <# of Neighs: " << Node->getNumOfNeighbors() << ">\n"; - } - } -} - -} // End llvm namespace diff --git a/lib/CodeGen/RegAlloc/InterferenceGraph.h b/lib/CodeGen/RegAlloc/InterferenceGraph.h deleted file mode 100644 index 79850c1..0000000 --- a/lib/CodeGen/RegAlloc/InterferenceGraph.h +++ /dev/null @@ -1,75 +0,0 @@ -//===-- InterferenceGraph.h - Interference graph for register coloring -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -/* Title: InterferenceGraph.h -*- C++ -*- - 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 INTERFERENCEGRAPH_H -#define INTERFERENCEGRAPH_H - -#include <vector> - -namespace llvm { - -class LiveRange; -class RegClass; -class IGNode; - -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 - std::vector<IGNode *> IGNodeList; // a list of all IGNodes in a reg class - - public: - // the matrix is not yet created by the constructor. Call createGraph() - // to create it after adding all IGNodes to the IGNodeList - InterferenceGraph(RegClass *RC); - ~InterferenceGraph(); - - void createGraph(); - - void addLRToIG(LiveRange *LR); - - void setInterference(const LiveRange *LR1, - const LiveRange *LR2); - - unsigned getInterference(const LiveRange *LR1, - const LiveRange *LR2) const ; - - void mergeIGNodesOfLRs(const LiveRange *LR1, LiveRange *LR2); - - std::vector<IGNode *> &getIGNodeList() { return IGNodeList; } - const std::vector<IGNode *> &getIGNodeList() const { return IGNodeList; } - - void setCurDegreeOfIGNodes(); - - void printIG() const; - void printIGNodeList() const; -}; - -} // End llvm namespace - -#endif diff --git a/lib/CodeGen/RegAlloc/LiveRange.h b/lib/CodeGen/RegAlloc/LiveRange.h deleted file mode 100644 index d6e2cf6..0000000 --- a/lib/CodeGen/RegAlloc/LiveRange.h +++ /dev/null @@ -1,184 +0,0 @@ -//===-- LiveRange.h - Store info about a live range -------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Implements a live range using a ValueSet. A LiveRange is a simple set -// of Values. -// -// Since the Value pointed by a use is the same as of its def, it is sufficient -// to keep only defs in a LiveRange. -// -//===----------------------------------------------------------------------===// - -#ifndef LIVERANGE_H -#define LIVERANGE_H - -#include "llvm/Value.h" -#include "llvm/CodeGen/ValueSet.h" - -namespace llvm { - -class RegClass; -class IGNode; - -class LiveRange : public ValueSet { - RegClass *MyRegClass; // register class (e.g., int, FP) for this LR - - /// 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 - - /// mustSaveAcrossCalls - whether this LR must be saved accross calls - /// ***TODO REMOVE this - /// - bool mustSaveAcrossCalls; - - /// SuggestedColor - 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. - /// - int SuggestedColor; // The suggested color for this LR - - /// 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) - /// - bool CanUseSuggestedCol; - - /// SpilledStackOffsetFromFP - If this LR is spilled, its stack - /// offset from *FP*. The spilled offsets must always be relative to - /// the FP. - /// - int SpilledStackOffsetFromFP; - - /// HasSpillOffset 0 Whether this live range has a spill offset - /// - bool HasSpillOffset; - - /// The spill cost of this live range. Calculated using loop depth of - /// each reference to each Value in the live range - /// - unsigned SpillCost; - -public: - LiveRange() { - Color = SuggestedColor = -1; // not yet colored - mustSpill = mustSaveAcrossCalls = false; - MyRegClass = 0; - UserIGNode = 0; - doesSpanAcrossCalls = false; - CanUseSuggestedCol = true; - HasSpillOffset = false; - SpillCost = 0; - } - - void setRegClass(RegClass *RC) { MyRegClass = RC; } - - RegClass *getRegClass() const { assert(MyRegClass); return MyRegClass; } - unsigned getRegClassID() const; - - bool hasColor() const { return Color != -1; } - - unsigned getColor() const { assert(Color != -1); return (unsigned)Color; } - - void setColor(unsigned Col) { Color = (int)Col; } - - inline void setCallInterference() { - doesSpanAcrossCalls = 1; - } - inline void clearCallInterference() { - doesSpanAcrossCalls = 0; - } - - inline bool isCallInterference() const { - return doesSpanAcrossCalls == 1; - } - - inline void markForSpill() { mustSpill = true; } - - inline bool isMarkedForSpill() const { return mustSpill; } - - inline void setSpillOffFromFP(int StackOffset) { - assert(mustSpill && "This LR is not spilled"); - SpilledStackOffsetFromFP = StackOffset; - HasSpillOffset = true; - } - - inline void modifySpillOffFromFP(int StackOffset) { - assert(mustSpill && "This LR is not spilled"); - SpilledStackOffsetFromFP = StackOffset; - HasSpillOffset = true; - } - - inline bool hasSpillOffset() const { - return HasSpillOffset; - } - - inline int getSpillOffFromFP() const { - assert(HasSpillOffset && "This LR is not spilled"); - return SpilledStackOffsetFromFP; - } - - inline void markForSaveAcrossCalls() { mustSaveAcrossCalls = true; } - - inline void setUserIGNode(IGNode *IGN) { - assert(!UserIGNode); UserIGNode = IGN; - } - - // getUserIGNode - NULL if the user is not allocated - inline IGNode *getUserIGNode() const { return UserIGNode; } - - inline const Type *getType() const { - return (*begin())->getType(); // set's don't have a front - } - - inline void setSuggestedColor(int Col) { - if (SuggestedColor == -1) - SuggestedColor = Col; - } - - inline unsigned getSuggestedColor() const { - assert(SuggestedColor != -1); // only a valid color is obtained - return (unsigned)SuggestedColor; - } - - inline bool hasSuggestedColor() const { - return SuggestedColor != -1; - } - - inline bool isSuggestedColorUsable() const { - assert(hasSuggestedColor() && "No suggested color"); - return CanUseSuggestedCol; - } - - inline void setSuggestedColorUsable(bool val) { - assert(hasSuggestedColor() && "No suggested color"); - CanUseSuggestedCol = val; - } - - inline void addSpillCost(unsigned cost) { - SpillCost += cost; - } - - inline unsigned getSpillCost() const { - return SpillCost; - } -}; - -} // End llvm namespace - -#endif diff --git a/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp b/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp deleted file mode 100644 index 3806804..0000000 --- a/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp +++ /dev/null @@ -1,416 +0,0 @@ -//===-- LiveRangeInfo.cpp -------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Live range construction for coloring-based register allocation for LLVM. -// -//===----------------------------------------------------------------------===// - -#include "IGNode.h" -#include "LiveRangeInfo.h" -#include "RegAllocCommon.h" -#include "RegClass.h" -#include "llvm/Function.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetRegInfo.h" -#include "Support/SetOperations.h" - -namespace llvm { - -unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); } - -LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm, - std::vector<RegClass *> &RCL) - : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { } - - -LiveRangeInfo::~LiveRangeInfo() { - for (LiveRangeMapType::iterator MI = LiveRangeMap.begin(); - MI != LiveRangeMap.end(); ++MI) { - - if (MI->first && MI->second) { - LiveRange *LR = MI->second; - - // we need to be careful in deleting LiveRanges in LiveRangeMap - // since two/more Values in the live range map can point to the same - // live range. We have to make the other entries NULL when we delete - // a live range. - - for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI) - LiveRangeMap[*LI] = 0; - - delete LR; - } - } -} - - -//--------------------------------------------------------------------------- -// union two live ranges into one. The 2nd LR is deleted. Used for coalescing. -// Note: the caller must make sure that L1 and L2 are distinct and both -// LRs don't have suggested colors -//--------------------------------------------------------------------------- - -void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) { - assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor())); - assert(! (L1->hasColor() && L2->hasColor()) || - L1->getColor() == L2->getColor()); - - set_union(*L1, *L2); // add elements of L2 to L1 - - for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) { - //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types"); - - L1->insert(*L2It); // add the var in L2 to L1 - LiveRangeMap[*L2It] = L1; // now the elements in L2 should map - //to L1 - } - - // set call interference for L1 from L2 - if (L2->isCallInterference()) - L1->setCallInterference(); - - // add the spill costs - L1->addSpillCost(L2->getSpillCost()); - - // If L2 has a color, give L1 that color. Note that L1 may have had the same - // color or none, but would not have a different color as asserted above. - if (L2->hasColor()) - L1->setColor(L2->getColor()); - - // Similarly, if LROfUse(L2) has a suggested color, the new range - // must have the same color. - if (L2->hasSuggestedColor()) - L1->setSuggestedColor(L2->getSuggestedColor()); - - delete L2; // delete L2 as it is no longer needed -} - - -//--------------------------------------------------------------------------- -// Method for creating a single live range for a definition. -// The definition must be represented by a virtual register (a Value). -// Note: this function does *not* check that no live range exists for def. -//--------------------------------------------------------------------------- - -LiveRange* -LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/) -{ - LiveRange* DefRange = new LiveRange(); // Create a new live range, - DefRange->insert(Def); // add Def to it, - LiveRangeMap[Def] = DefRange; // and update the map. - - // set the register class of the new live range - DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(), - isCC)]); - - if (DEBUG_RA >= RA_DEBUG_LiveRanges) { - std::cerr << " Creating a LR for def "; - if (isCC) std::cerr << " (CC Register!)"; - std::cerr << " : " << RAV(Def) << "\n"; - } - return DefRange; -} - - -LiveRange* -LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/) -{ - LiveRange *DefRange = LiveRangeMap[Def]; - - // check if the LR is already there (because of multiple defs) - if (!DefRange) { - DefRange = createNewLiveRange(Def, isCC); - } else { // live range already exists - DefRange->insert(Def); // add the operand to the range - LiveRangeMap[Def] = DefRange; // make operand point to merged set - if (DEBUG_RA >= RA_DEBUG_LiveRanges) - std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n"; - } - return DefRange; -} - - -//--------------------------------------------------------------------------- -// Method for constructing all live ranges in a function. It creates live -// ranges for all values defined in the instruction stream. Also, it -// creates live ranges for all incoming arguments of the function. -//--------------------------------------------------------------------------- -void LiveRangeInfo::constructLiveRanges() { - - if (DEBUG_RA >= RA_DEBUG_LiveRanges) - std::cerr << "Constructing Live Ranges ...\n"; - - // first find the live ranges for all incoming args of the function since - // those LRs start from the start of the function - for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI) - createNewLiveRange(AI, /*isCC*/ false); - - // Now suggest hardware registers for these function args - MRI.suggestRegs4MethodArgs(Meth, *this); - - // Now create LRs for machine instructions. A new LR will be created - // only for defs in the machine instr since, we assume that all Values are - // defined before they are used. However, there can be multiple defs for - // the same Value in machine instructions. - // - // Also, find CALL and RETURN instructions, which need extra work. - // - MachineFunction &MF = MachineFunction::get(Meth); - for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) { - MachineBasicBlock &MBB = *BBI; - - // iterate over all the machine instructions in BB - for(MachineBasicBlock::iterator MInstIterator = MBB.begin(); - MInstIterator != MBB.end(); ++MInstIterator) { - MachineInstr *MInst = *MInstIterator; - - // If the machine instruction is a call/return instruction, add it to - // CallRetInstrList for processing its args, ret value, and ret addr. - // - if(TM.getInstrInfo().isReturn(MInst->getOpCode()) || - TM.getInstrInfo().isCall(MInst->getOpCode())) - CallRetInstrList.push_back(MInst); - - // iterate over explicit MI operands and create a new LR - // for each operand that is defined by the instruction - for (MachineInstr::val_op_iterator OpI = MInst->begin(), - OpE = MInst->end(); OpI != OpE; ++OpI) - if (OpI.isDef()) { - const Value *Def = *OpI; - bool isCC = (OpI.getMachineOperand().getType() - == MachineOperand::MO_CCRegister); - LiveRange* LR = createOrAddToLiveRange(Def, isCC); - - // If the operand has a pre-assigned register, - // set it directly in the LiveRange - if (OpI.getMachineOperand().hasAllocatedReg()) { - unsigned getClassId; - LR->setColor(MRI.getClassRegNum( - OpI.getMachineOperand().getAllocatedRegNum(), - getClassId)); - } - } - - // iterate over implicit MI operands and create a new LR - // for each operand that is defined by the instruction - for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i) - if (MInst->getImplicitOp(i).isDef()) { - const Value *Def = MInst->getImplicitRef(i); - LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false); - - // If the implicit operand has a pre-assigned register, - // set it directly in the LiveRange - if (MInst->getImplicitOp(i).hasAllocatedReg()) { - unsigned getClassId; - LR->setColor(MRI.getClassRegNum( - MInst->getImplicitOp(i).getAllocatedRegNum(), - getClassId)); - } - } - - } // for all machine instructions in the BB - } // for all BBs in function - - // Now we have to suggest clors for call and return arg live ranges. - // Also, if there are implicit defs (e.g., retun value of a call inst) - // they must be added to the live range list - // - suggestRegs4CallRets(); - - if( DEBUG_RA >= RA_DEBUG_LiveRanges) - std::cerr << "Initial Live Ranges constructed!\n"; -} - - -//--------------------------------------------------------------------------- -// If some live ranges must be colored with specific hardware registers -// (e.g., for outgoing call args), suggesting of colors for such live -// ranges is done using target specific function. Those functions are called -// from this function. The target specific methods must: -// 1) suggest colors for call and return args. -// 2) create new LRs for implicit defs in machine instructions -//--------------------------------------------------------------------------- -void LiveRangeInfo::suggestRegs4CallRets() { - std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin(); - for( ; It != CallRetInstrList.end(); ++It) { - MachineInstr *MInst = *It; - MachineOpCode OpCode = MInst->getOpCode(); - - if ((TM.getInstrInfo()).isReturn(OpCode)) - MRI.suggestReg4RetValue(MInst, *this); - else if ((TM.getInstrInfo()).isCall(OpCode)) - MRI.suggestRegs4CallArgs(MInst, *this); - else - assert( 0 && "Non call/ret instr in CallRetInstrList" ); - } -} - - -//-------------------------------------------------------------------------- -// The following method coalesces live ranges when possible. This method -// must be called after the interference graph has been constructed. - - -/* Algorithm: - for each BB in function - for each machine instruction (inst) - for each definition (def) in inst - for each operand (op) of inst that is a use - if the def and op are of the same register type - if the def and op do not interfere //i.e., not simultaneously live - if (degree(LR of def) + degree(LR of op)) <= # avail regs - if both LRs do not have suggested colors - merge2IGNodes(def, op) // i.e., merge 2 LRs - -*/ -//--------------------------------------------------------------------------- - - -// Checks if live range LR interferes with any node assigned or suggested to -// be assigned the specified color -// -inline bool InterferesWithColor(const LiveRange& LR, unsigned color) { - IGNode* lrNode = LR.getUserIGNode(); - for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) { - LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR(); - if (neighLR->hasColor() && neighLR->getColor() == color) - return true; - if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color) - return true; - } - return false; -} - -// Cannot coalesce if any of the following is true: -// (1) Both LRs have suggested colors (should be "different suggested colors"?) -// (2) Both LR1 and LR2 have colors and the colors are different -// (but if the colors are the same, it is definitely safe to coalesce) -// (3) LR1 has color and LR2 interferes with any LR that has the same color -// (4) LR2 has color and LR1 interferes with any LR that has the same color -// -inline bool InterfsPreventCoalescing(const LiveRange& LROfDef, - const LiveRange& LROfUse) { - // (4) if they have different suggested colors, cannot coalesce - if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor()) - return true; - - // if neither has a color, nothing more to do. - if (! LROfDef.hasColor() && ! LROfUse.hasColor()) - return false; - - // (2, 3) if L1 has color... - if (LROfDef.hasColor()) { - if (LROfUse.hasColor()) - return (LROfUse.getColor() != LROfDef.getColor()); - return InterferesWithColor(LROfUse, LROfDef.getColor()); - } - - // (4) else only LROfUse has a color: check if that could interfere - return InterferesWithColor(LROfDef, LROfUse.getColor()); -} - - -void LiveRangeInfo::coalesceLRs() -{ - if(DEBUG_RA >= RA_DEBUG_LiveRanges) - std::cerr << "\nCoalescing LRs ...\n"; - - MachineFunction &MF = MachineFunction::get(Meth); - for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) { - MachineBasicBlock &MBB = *BBI; - - // iterate over all the machine instructions in BB - for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){ - const MachineInstr *MI = *MII; - - if( DEBUG_RA >= RA_DEBUG_LiveRanges) { - std::cerr << " *Iterating over machine instr "; - MI->dump(); - std::cerr << "\n"; - } - - // iterate over MI operands to find defs - for(MachineInstr::const_val_op_iterator DefI = MI->begin(), - DefE = MI->end(); DefI != DefE; ++DefI) { - if (DefI.isDef()) { // this operand is modified - LiveRange *LROfDef = getLiveRangeForValue( *DefI ); - RegClass *RCOfDef = LROfDef->getRegClass(); - - MachineInstr::const_val_op_iterator UseI = MI->begin(), - UseE = MI->end(); - for( ; UseI != UseE; ++UseI) { // for all uses - LiveRange *LROfUse = getLiveRangeForValue( *UseI ); - if (!LROfUse) { // if LR of use is not found - //don't warn about labels - if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges) - std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n"; - continue; // ignore and continue - } - - if (LROfUse == LROfDef) // nothing to merge if they are same - continue; - - if (MRI.getRegTypeForLR(LROfDef) == - MRI.getRegTypeForLR(LROfUse)) { - // If the two RegTypes are the same - if (!RCOfDef->getInterference(LROfDef, LROfUse) ) { - - unsigned CombinedDegree = - LROfDef->getUserIGNode()->getNumOfNeighbors() + - LROfUse->getUserIGNode()->getNumOfNeighbors(); - - if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) { - // get more precise estimate of combined degree - CombinedDegree = LROfDef->getUserIGNode()-> - getCombinedDegree(LROfUse->getUserIGNode()); - } - - if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) { - // if both LRs do not have different pre-assigned colors - // and both LRs do not have suggested colors - if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) { - RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse); - unionAndUpdateLRs(LROfDef, LROfUse); - } - - } // if combined degree is less than # of regs - } // if def and use do not interfere - }// if reg classes are the same - } // for all uses - } // if def - } // for all defs - } // for all machine instructions - } // for all BBs - - if (DEBUG_RA >= RA_DEBUG_LiveRanges) - std::cerr << "\nCoalescing Done!\n"; -} - -/*--------------------------- Debug code for printing ---------------*/ - - -void LiveRangeInfo::printLiveRanges() { - LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator - std::cerr << "\nPrinting Live Ranges from Hash Map:\n"; - for( ; HMI != LiveRangeMap.end(); ++HMI) { - if (HMI->first && HMI->second) { - std::cerr << " Value* " << RAV(HMI->first) << "\t: "; - if (IGNode* igNode = HMI->second->getUserIGNode()) - std::cerr << "LR# " << igNode->getIndex(); - else - std::cerr << "LR# " << "<no-IGNode>"; - std::cerr << "\t:Values = "; printSet(*HMI->second); std::cerr << "\n"; - } - } -} - -} // End llvm namespace diff --git a/lib/CodeGen/RegAlloc/LiveRangeInfo.h b/lib/CodeGen/RegAlloc/LiveRangeInfo.h deleted file mode 100644 index a8d0e71..0000000 --- a/lib/CodeGen/RegAlloc/LiveRangeInfo.h +++ /dev/null @@ -1,128 +0,0 @@ -//===-- LiveRangeInfo.h - Track all LiveRanges for a Function ----*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains the class LiveRangeInfo which constructs and keeps -// the LiveRangeMap which contains all the live ranges used in a method. -// -// 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. -// -//===----------------------------------------------------------------------===// - -#ifndef LIVERANGEINFO_H -#define LIVERANGEINFO_H - -#include "llvm/CodeGen/ValueSet.h" -#include "Support/hash_map" - -namespace llvm { - -class LiveRange; -class MachineInstr; -class RegClass; -class TargetRegInfo; -class TargetMachine; -class Value; -class Function; -class Instruction; - -typedef hash_map<const Value*, LiveRange*> LiveRangeMapType; - -//---------------------------------------------------------------------------- -// Class LiveRangeInfo -// -// Constructs and keeps the LiveRangeMap which contains all the live -// ranges used in a method. Also contain methods to coalesce live ranges. -//---------------------------------------------------------------------------- - -class LiveRangeInfo { - const Function *const Meth; // Func for which live range info is held - 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 - - std::vector<RegClass *> & RegClassList;// vector containing register classess - - const TargetRegInfo& MRI; // machine reg info - - std::vector<MachineInstr*> CallRetInstrList; // a list of all call/ret instrs - - - //------------ Private methods (see LiveRangeInfo.cpp for description)------- - - LiveRange* createNewLiveRange (const Value* Def, - bool isCC = false); - - LiveRange* createOrAddToLiveRange (const Value* Def, - bool isCC = false); - - void unionAndUpdateLRs (LiveRange *L1, - LiveRange *L2); - - void addInterference (const Instruction *Inst, - const ValueSet *LVSet); - - void suggestRegs4CallRets (); - - const Function *getMethod () const { return Meth; } - -public: - - LiveRangeInfo(const Function *F, - const TargetMachine& tm, - std::vector<RegClass *> & RCList); - - - /// Destructor to destroy all LiveRanges in the LiveRange Map - /// - ~LiveRangeInfo(); - - // Main entry point for live range construction - // - void constructLiveRanges(); - - /// return the common live range map for this method - /// - inline const LiveRangeMapType *getLiveRangeMap() const - { return &LiveRangeMap; } - - /// Method used to get the live range containing a Value. - /// This may return NULL if no live range exists for a Value (eg, some consts) - /// - inline LiveRange *getLiveRangeForValue(const Value *Val) { - return LiveRangeMap[Val]; - } - inline const LiveRange *getLiveRangeForValue(const Value *Val) const { - LiveRangeMapType::const_iterator I = LiveRangeMap.find(Val); - return I->second; - } - - /// Method for coalescing live ranges. Called only after interference info - /// is calculated. - /// - void coalesceLRs(); - - /// debugging method to print the live ranges - /// - void printLiveRanges(); -}; - -} // End llvm namespace - -#endif diff --git a/lib/CodeGen/RegAlloc/Makefile b/lib/CodeGen/RegAlloc/Makefile deleted file mode 100644 index 6c4f50b..0000000 --- a/lib/CodeGen/RegAlloc/Makefile +++ /dev/null @@ -1,17 +0,0 @@ -##===- lib/CodeGen/RegAlloc/Makefile -----------------------*- Makefile -*-===## -# -# The LLVM Compiler Infrastructure -# -# This file was developed by the LLVM research group and is distributed under -# the University of Illinois Open Source License. See LICENSE.TXT for details. -# -##===----------------------------------------------------------------------===## -LEVEL = ../../.. - -DIRS = - -LIBRARYNAME = regalloc - -BUILD_ARCHIVE = 1 - -include $(LEVEL)/Makefile.common diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp deleted file mode 100644 index a9a5f3d..0000000 --- a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp +++ /dev/null @@ -1,1397 +0,0 @@ -//===-- PhyRegAlloc.cpp ---------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Traditional graph-coloring global register allocator currently used -// by the SPARC back-end. -// -// NOTE: This register allocator has some special support -// for the Reoptimizer, such as not saving some registers on calls to -// the first-level instrumentation function. -// -// NOTE 2: This register allocator can save its state in a global -// variable in the module it's working on. This feature is not -// thread-safe; if you have doubts, leave it turned off. -// -//===----------------------------------------------------------------------===// - -#include "AllocInfo.h" -#include "IGNode.h" -#include "PhyRegAlloc.h" -#include "RegAllocCommon.h" -#include "RegClass.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/iOther.h" -#include "llvm/Module.h" -#include "llvm/Type.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/CodeGen/FunctionLiveVarInfo.h" -#include "llvm/CodeGen/InstrSelection.h" -#include "llvm/CodeGen/MachineCodeForInstruction.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineFunctionInfo.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineInstrBuilder.h" -#include "llvm/CodeGen/MachineInstrAnnot.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/Support/InstIterator.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "Support/CommandLine.h" -#include "Support/SetOperations.h" -#include "Support/STLExtras.h" -#include <cmath> - -namespace llvm { - -RegAllocDebugLevel_t DEBUG_RA; - -/// The reoptimizer wants to be able to grovel through the register -/// allocator's state after it has done its job. This is a hack. -/// -PhyRegAlloc::SavedStateMapTy ExportedFnAllocState; -const bool SaveStateToModule = true; - -static cl::opt<RegAllocDebugLevel_t, true> -DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA), - cl::desc("enable register allocation debugging information"), - cl::values( - clEnumValN(RA_DEBUG_None , "n", "disable debug output"), - clEnumValN(RA_DEBUG_Results, "y", "debug output for allocation results"), - clEnumValN(RA_DEBUG_Coloring, "c", "debug output for graph coloring step"), - clEnumValN(RA_DEBUG_Interference,"ig","debug output for interference graphs"), - clEnumValN(RA_DEBUG_LiveRanges , "lr","debug output for live ranges"), - clEnumValN(RA_DEBUG_Verbose, "v", "extra debug output"), - 0)); - -static cl::opt<bool> -SaveRegAllocState("save-ra-state", cl::Hidden, - cl::desc("write reg. allocator state into module")); - -FunctionPass *getRegisterAllocator(TargetMachine &T) { - return new PhyRegAlloc (T); -} - -void PhyRegAlloc::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<LoopInfo> (); - AU.addRequired<FunctionLiveVarInfo> (); -} - - -/// Initialize interference graphs (one in each reg class) and IGNodeLists -/// (one in each IG). The actual nodes will be pushed later. -/// -void PhyRegAlloc::createIGNodeListsAndIGs() { - if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "Creating LR lists ...\n"; - - LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin(); - LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end(); - - for (; HMI != HMIEnd ; ++HMI ) { - if (HMI->first) { - LiveRange *L = HMI->second; // get the LiveRange - if (!L) { - if (DEBUG_RA) - std::cerr << "\n**** ?!?WARNING: NULL LIVE RANGE FOUND FOR: " - << RAV(HMI->first) << "****\n"; - continue; - } - - // if the Value * is not null, and LR is not yet written to the IGNodeList - if (!(L->getUserIGNode()) ) { - RegClass *const RC = // RegClass of first value in the LR - RegClassList[ L->getRegClassID() ]; - RC->addLRToIG(L); // add this LR to an IG - } - } - } - - // init RegClassList - for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) - RegClassList[rc]->createInterferenceGraph(); - - if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "LRLists Created!\n"; -} - - -/// Add all interferences for a given instruction. Interference occurs only -/// if the LR of Def (Inst or Arg) is of the same reg class as that of live -/// var. The live var passed to this function is the LVset AFTER the -/// instruction. -/// -void PhyRegAlloc::addInterference(const Value *Def, const ValueSet *LVSet, - bool isCallInst) { - ValueSet::const_iterator LIt = LVSet->begin(); - - // get the live range of instruction - const LiveRange *const LROfDef = LRI->getLiveRangeForValue( Def ); - - IGNode *const IGNodeOfDef = LROfDef->getUserIGNode(); - assert( IGNodeOfDef ); - - RegClass *const RCOfDef = LROfDef->getRegClass(); - - // for each live var in live variable set - for ( ; LIt != LVSet->end(); ++LIt) { - - if (DEBUG_RA >= RA_DEBUG_Verbose) - std::cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> "; - - // get the live range corresponding to live var - LiveRange *LROfVar = LRI->getLiveRangeForValue(*LIt); - - // LROfVar can be null if it is a const since a const - // doesn't have a dominating def - see Assumptions above - if (LROfVar) - if (LROfDef != LROfVar) // do not set interf for same LR - if (RCOfDef == LROfVar->getRegClass()) // 2 reg classes are the same - RCOfDef->setInterference( LROfDef, LROfVar); - } -} - - -/// For a call instruction, this method sets the CallInterference flag in -/// the LR of each variable live in the Live Variable Set live after the -/// call instruction (except the return value of the call instruction - since -/// the return value does not interfere with that call itself). -/// -void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst, - const ValueSet *LVSetAft) { - if (DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << "\n For call inst: " << *MInst; - - // for each live var in live variable set after machine inst - for (ValueSet::const_iterator LIt = LVSetAft->begin(), LEnd = LVSetAft->end(); - LIt != LEnd; ++LIt) { - - // get the live range corresponding to live var - LiveRange *const LR = LRI->getLiveRangeForValue(*LIt ); - - // LR can be null if it is a const since a const - // doesn't have a dominating def - see Assumptions above - if (LR ) { - if (DEBUG_RA >= RA_DEBUG_Interference) { - std::cerr << "\n\tLR after Call: "; - printSet(*LR); - } - LR->setCallInterference(); - if (DEBUG_RA >= RA_DEBUG_Interference) { - std::cerr << "\n ++After adding call interference for LR: " ; - printSet(*LR); - } - } - - } - - // Now find the LR of the return value of the call - // We do this because, we look at the LV set *after* the instruction - // to determine, which LRs must be saved across calls. The return value - // of the call is live in this set - but it does not interfere with call - // (i.e., we can allocate a volatile register to the return value) - CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst); - - if (const Value *RetVal = argDesc->getReturnValue()) { - LiveRange *RetValLR = LRI->getLiveRangeForValue( RetVal ); - assert( RetValLR && "No LR for RetValue of call"); - RetValLR->clearCallInterference(); - } - - // If the CALL is an indirect call, find the LR of the function pointer. - // That has a call interference because it conflicts with outgoing args. - if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) { - LiveRange *AddrValLR = LRI->getLiveRangeForValue( AddrVal ); - assert( AddrValLR && "No LR for indirect addr val of call"); - AddrValLR->setCallInterference(); - } -} - - -/// Create interferences in the IG of each RegClass, and calculate the spill -/// cost of each Live Range (it is done in this method to save another pass -/// over the code). -/// -void PhyRegAlloc::buildInterferenceGraphs() { - if (DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << "Creating interference graphs ...\n"; - - unsigned BBLoopDepthCost; - for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end(); - BBI != BBE; ++BBI) { - const MachineBasicBlock &MBB = *BBI; - const BasicBlock *BB = MBB.getBasicBlock(); - - // find the 10^(loop_depth) of this BB - BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BB)); - - // get the iterator for machine instructions - MachineBasicBlock::const_iterator MII = MBB.begin(); - - // iterate over all the machine instructions in BB - for ( ; MII != MBB.end(); ++MII) { - const MachineInstr *MInst = *MII; - - // get the LV set after the instruction - const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB); - bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode()); - - if (isCallInst) { - // set the isCallInterference flag of each live range which extends - // across this call instruction. This information is used by graph - // coloring algorithm to avoid allocating volatile colors to live ranges - // that span across calls (since they have to be saved/restored) - setCallInterferences(MInst, &LVSetAI); - } - - // iterate over all MI operands to find defs - for (MachineInstr::const_val_op_iterator OpI = MInst->begin(), - OpE = MInst->end(); OpI != OpE; ++OpI) { - if (OpI.isDef()) // create a new LR since def - addInterference(*OpI, &LVSetAI, isCallInst); - - // Calculate the spill cost of each live range - LiveRange *LR = LRI->getLiveRangeForValue(*OpI); - if (LR) LR->addSpillCost(BBLoopDepthCost); - } - - // Mark all operands of pseudo-instructions as interfering with one - // another. This must be done because pseudo-instructions may be - // expanded to multiple instructions by the assembler, so all the - // operands must get distinct registers. - if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode())) - addInterf4PseudoInstr(MInst); - - // Also add interference for any implicit definitions in a machine - // instr (currently, only calls have this). - unsigned NumOfImpRefs = MInst->getNumImplicitRefs(); - for (unsigned z=0; z < NumOfImpRefs; z++) - if (MInst->getImplicitOp(z).isDef()) - addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst ); - - } // for all machine instructions in BB - } // for all BBs in function - - // add interferences for function arguments. Since there are no explicit - // defs in the function for args, we have to add them manually - addInterferencesForArgs(); - - if (DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << "Interference graphs calculated!\n"; -} - - -/// Mark all operands of the given MachineInstr as interfering with one -/// another. -/// -void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) { - bool setInterf = false; - - // iterate over MI operands to find defs - for (MachineInstr::const_val_op_iterator It1 = MInst->begin(), - ItE = MInst->end(); It1 != ItE; ++It1) { - const LiveRange *LROfOp1 = LRI->getLiveRangeForValue(*It1); - assert((LROfOp1 || It1.isDef()) && "No LR for Def in PSEUDO insruction"); - - MachineInstr::const_val_op_iterator It2 = It1; - for (++It2; It2 != ItE; ++It2) { - const LiveRange *LROfOp2 = LRI->getLiveRangeForValue(*It2); - - if (LROfOp2) { - RegClass *RCOfOp1 = LROfOp1->getRegClass(); - RegClass *RCOfOp2 = LROfOp2->getRegClass(); - - if (RCOfOp1 == RCOfOp2 ){ - RCOfOp1->setInterference( LROfOp1, LROfOp2 ); - setInterf = true; - } - } // if Op2 has a LR - } // for all other defs in machine instr - } // for all operands in an instruction - - if (!setInterf && MInst->getNumOperands() > 2) { - std::cerr << "\nInterf not set for any operand in pseudo instr:\n"; - std::cerr << *MInst; - assert(0 && "Interf not set for pseudo instr with > 2 operands" ); - } -} - - -/// Add interferences for incoming arguments to a function. -/// -void PhyRegAlloc::addInterferencesForArgs() { - // get the InSet of root BB - const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front()); - - for (Function::const_aiterator AI = Fn->abegin(); AI != Fn->aend(); ++AI) { - // add interferences between args and LVars at start - addInterference(AI, &InSet, false); - - if (DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << " - %% adding interference for argument " << RAV(AI) << "\n"; - } -} - - -/// The following are utility functions used solely by updateMachineCode and -/// the functions that it calls. They should probably be folded back into -/// updateMachineCode at some point. -/// - -// used by: updateMachineCode (1 time), PrependInstructions (1 time) -inline void InsertBefore(MachineInstr* newMI, MachineBasicBlock& MBB, - MachineBasicBlock::iterator& MII) { - MII = MBB.insert(MII, newMI); - ++MII; -} - -// used by: AppendInstructions (1 time) -inline void InsertAfter(MachineInstr* newMI, MachineBasicBlock& MBB, - MachineBasicBlock::iterator& MII) { - ++MII; // insert before the next instruction - MII = MBB.insert(MII, newMI); -} - -// used by: updateMachineCode (1 time) -inline void DeleteInstruction(MachineBasicBlock& MBB, - MachineBasicBlock::iterator& MII) { - MII = MBB.erase(MII); -} - -// used by: updateMachineCode (1 time) -inline void SubstituteInPlace(MachineInstr* newMI, MachineBasicBlock& MBB, - MachineBasicBlock::iterator MII) { - *MII = newMI; -} - -// used by: updateMachineCode (2 times) -inline void PrependInstructions(std::vector<MachineInstr *> &IBef, - MachineBasicBlock& MBB, - MachineBasicBlock::iterator& MII, - const std::string& msg) { - if (!IBef.empty()) { - MachineInstr* OrigMI = *MII; - std::vector<MachineInstr *>::iterator AdIt; - for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt) { - if (DEBUG_RA) { - if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI; - std::cerr << msg << "PREPENDed instr:\n " << **AdIt << "\n"; - } - InsertBefore(*AdIt, MBB, MII); - } - } -} - -// used by: updateMachineCode (1 time) -inline void AppendInstructions(std::vector<MachineInstr *> &IAft, - MachineBasicBlock& MBB, - MachineBasicBlock::iterator& MII, - const std::string& msg) { - if (!IAft.empty()) { - MachineInstr* OrigMI = *MII; - std::vector<MachineInstr *>::iterator AdIt; - for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) { - if (DEBUG_RA) { - if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI; - std::cerr << msg << "APPENDed instr:\n " << **AdIt << "\n"; - } - InsertAfter(*AdIt, MBB, MII); - } - } -} - -/// Set the registers for operands in the given MachineInstr, if a register was -/// successfully allocated. Return true if any of its operands has been marked -/// for spill. -/// -bool PhyRegAlloc::markAllocatedRegs(MachineInstr* MInst) -{ - bool instrNeedsSpills = false; - - // First, set the registers for operands in the machine instruction - // if a register was successfully allocated. Do this first because we - // will need to know which registers are already used by this instr'n. - for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { - MachineOperand& Op = MInst->getOperand(OpNum); - if (Op.getType() == MachineOperand::MO_VirtualRegister || - Op.getType() == MachineOperand::MO_CCRegister) { - const Value *const Val = Op.getVRegValue(); - if (const LiveRange* LR = LRI->getLiveRangeForValue(Val)) { - // Remember if any operand needs spilling - instrNeedsSpills |= LR->isMarkedForSpill(); - - // An operand may have a color whether or not it needs spilling - if (LR->hasColor()) - MInst->SetRegForOperand(OpNum, - MRI.getUnifiedRegNum(LR->getRegClassID(), - LR->getColor())); - } - } - } // for each operand - - return instrNeedsSpills; -} - -/// Mark allocated registers (using markAllocatedRegs()) on the instruction -/// that MII points to. Then, if it's a call instruction, insert caller-saving -/// code before and after it. Finally, insert spill code before and after it, -/// using insertCode4SpilledLR(). -/// -void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII, - MachineBasicBlock &MBB) { - MachineInstr* MInst = *MII; - unsigned Opcode = MInst->getOpCode(); - - // Reset tmp stack positions so they can be reused for each machine instr. - MF->getInfo()->popAllTempValues(); - - // Mark the operands for which regs have been allocated. - bool instrNeedsSpills = markAllocatedRegs(*MII); - -#ifndef NDEBUG - // Mark that the operands have been updated. Later, - // setRelRegsUsedByThisInst() is called to find registers used by each - // MachineInst, and it should not be used for an instruction until - // this is done. This flag just serves as a sanity check. - OperandsColoredMap[MInst] = true; -#endif - - // Now insert caller-saving code before/after the call. - // Do this before inserting spill code since some registers must be - // used by save/restore and spill code should not use those registers. - if (TM.getInstrInfo().isCall(Opcode)) { - AddedInstrns &AI = AddedInstrMap[MInst]; - insertCallerSavingCode(AI.InstrnsBefore, AI.InstrnsAfter, MInst, - MBB.getBasicBlock()); - } - - // Now insert spill code for remaining operands not allocated to - // registers. This must be done even for call return instructions - // since those are not handled by the special code above. - if (instrNeedsSpills) - for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) { - MachineOperand& Op = MInst->getOperand(OpNum); - if (Op.getType() == MachineOperand::MO_VirtualRegister || - Op.getType() == MachineOperand::MO_CCRegister) { - const Value* Val = Op.getVRegValue(); - if (const LiveRange *LR = LRI->getLiveRangeForValue(Val)) - if (LR->isMarkedForSpill()) - insertCode4SpilledLR(LR, MII, MBB, OpNum); - } - } // for each operand -} - -/// Iterate over all the MachineBasicBlocks in the current function and set -/// the allocated registers for each instruction (using updateInstruction()), -/// after register allocation is complete. Then move code out of delay slots. -/// -void PhyRegAlloc::updateMachineCode() -{ - // Insert any instructions needed at method entry - MachineBasicBlock::iterator MII = MF->front().begin(); - PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MF->front(), MII, - "At function entry: \n"); - assert(AddedInstrAtEntry.InstrnsAfter.empty() && - "InstrsAfter should be unnecessary since we are just inserting at " - "the function entry point here."); - - for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end(); - BBI != BBE; ++BBI) { - MachineBasicBlock &MBB = *BBI; - - // Iterate over all machine instructions in BB and mark operands with - // their assigned registers or insert spill code, as appropriate. - // Also, fix operands of call/return instructions. - for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII) - if (! TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpCode())) - updateInstruction(MII, MBB); - - // Now, move code out of delay slots of branches and returns if needed. - // (Also, move "after" code from calls to the last delay slot instruction.) - // Moving code out of delay slots is needed in 2 situations: - // (1) If this is a branch and it needs instructions inserted after it, - // move any existing instructions out of the delay slot so that the - // instructions can go into the delay slot. This only supports the - // case that #instrsAfter <= #delay slots. - // - // (2) If any instruction in the delay slot needs - // instructions inserted, move it out of the delay slot and before the - // branch because putting code before or after it would be VERY BAD! - // - // If the annul bit of the branch is set, neither of these is legal! - // If so, we need to handle spill differently but annulling is not yet used. - for (MachineBasicBlock::iterator MII = MBB.begin(); - MII != MBB.end(); ++MII) - if (unsigned delaySlots = - TM.getInstrInfo().getNumDelaySlots((*MII)->getOpCode())) { - MachineInstr *MInst = *MII, *DelaySlotMI = *(MII+1); - - // Check the 2 conditions above: - // (1) Does a branch need instructions added after it? - // (2) O/w does delay slot instr. need instrns before or after? - bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) || - TM.getInstrInfo().isReturn(MInst->getOpCode())); - bool cond1 = (isBranch && - AddedInstrMap.count(MInst) && - AddedInstrMap[MInst].InstrnsAfter.size() > 0); - bool cond2 = (AddedInstrMap.count(DelaySlotMI) && - (AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 || - AddedInstrMap[DelaySlotMI].InstrnsAfter.size() > 0)); - - if (cond1 || cond2) { - assert((MInst->getOpCodeFlags() & AnnulFlag) == 0 && - "FIXME: Moving an annulled delay slot instruction!"); - assert(delaySlots==1 && - "InsertBefore does not yet handle >1 delay slots!"); - InsertBefore(DelaySlotMI, MBB, MII); // MII pts back to branch - - // In case (1), delete it and don't replace with anything! - // Otherwise (i.e., case (2) only) replace it with a NOP. - if (cond1) { - DeleteInstruction(MBB, ++MII); // MII now points to next inst. - --MII; // reset MII for ++MII of loop - } - else - SubstituteInPlace(BuildMI(TM.getInstrInfo().getNOPOpCode(),1), - MBB, MII+1); // replace with NOP - - if (DEBUG_RA) { - std::cerr << "\nRegAlloc: Moved instr. with added code: " - << *DelaySlotMI - << " out of delay slots of instr: " << *MInst; - } - } - else - // For non-branch instr with delay slots (probably a call), move - // InstrAfter to the instr. in the last delay slot. - move2DelayedInstr(*MII, *(MII+delaySlots)); - } - - // Finally iterate over all instructions in BB and insert before/after - for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) { - MachineInstr *MInst = *MII; - - // do not process Phis - if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode())) - continue; - - // if there are any added instructions... - if (AddedInstrMap.count(MInst)) { - AddedInstrns &CallAI = AddedInstrMap[MInst]; - -#ifndef NDEBUG - bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) || - TM.getInstrInfo().isReturn(MInst->getOpCode())); - assert((!isBranch || - AddedInstrMap[MInst].InstrnsAfter.size() <= - TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) && - "Cannot put more than #delaySlots instrns after " - "branch or return! Need to handle temps differently."); -#endif - -#ifndef NDEBUG - // Temporary sanity checking code to detect whether the same machine - // instruction is ever inserted twice before/after a call. - // I suspect this is happening but am not sure. --Vikram, 7/1/03. - std::set<const MachineInstr*> instrsSeen; - for (int i = 0, N = CallAI.InstrnsBefore.size(); i < N; ++i) { - assert(instrsSeen.count(CallAI.InstrnsBefore[i]) == 0 && - "Duplicate machine instruction in InstrnsBefore!"); - instrsSeen.insert(CallAI.InstrnsBefore[i]); - } - for (int i = 0, N = CallAI.InstrnsAfter.size(); i < N; ++i) { - assert(instrsSeen.count(CallAI.InstrnsAfter[i]) == 0 && - "Duplicate machine instruction in InstrnsBefore/After!"); - instrsSeen.insert(CallAI.InstrnsAfter[i]); - } -#endif - - // Now add the instructions before/after this MI. - // We do this here to ensure that spill for an instruction is inserted - // as close as possible to an instruction (see above insertCode4Spill) - if (! CallAI.InstrnsBefore.empty()) - PrependInstructions(CallAI.InstrnsBefore, MBB, MII,""); - - if (! CallAI.InstrnsAfter.empty()) - AppendInstructions(CallAI.InstrnsAfter, MBB, MII,""); - - } // if there are any added instructions - } // for each machine instruction - } -} - - -/// Insert spill code for AN operand whose LR was spilled. May be called -/// repeatedly for a single MachineInstr if it has many spilled operands. On -/// each call, it finds a register which is not live at that instruction and -/// also which is not used by other spilled operands of the same -/// instruction. Then it uses this register temporarily to accommodate the -/// spilled value. -/// -void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR, - MachineBasicBlock::iterator& MII, - MachineBasicBlock &MBB, - const unsigned OpNum) { - MachineInstr *MInst = *MII; - const BasicBlock *BB = MBB.getBasicBlock(); - - assert((! TM.getInstrInfo().isCall(MInst->getOpCode()) || OpNum == 0) && - "Outgoing arg of a call must be handled elsewhere (func arg ok)"); - assert(! TM.getInstrInfo().isReturn(MInst->getOpCode()) && - "Return value of a ret must be handled elsewhere"); - - MachineOperand& Op = MInst->getOperand(OpNum); - bool isDef = Op.isDef(); - bool isUse = Op.isUse(); - unsigned RegType = MRI.getRegTypeForLR(LR); - int SpillOff = LR->getSpillOffFromFP(); - RegClass *RC = LR->getRegClass(); - - // Get the live-variable set to find registers free before this instr. - const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB); - -#ifndef NDEBUG - // If this instr. is in the delay slot of a branch or return, we need to - // include all live variables before that branch or return -- we don't want to - // trample those! Verify that the set is included in the LV set before MInst. - if (MII != MBB.begin()) { - MachineInstr *PredMI = *(MII-1); - if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(PredMI->getOpCode())) - assert(set_difference(LVI->getLiveVarSetBeforeMInst(PredMI), LVSetBef) - .empty() && "Live-var set before branch should be included in " - "live-var set of each delay slot instruction!"); - } -#endif - - MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType)); - - std::vector<MachineInstr*> MIBef, MIAft; - std::vector<MachineInstr*> AdIMid; - - // Choose a register to hold the spilled value, if one was not preallocated. - // This may insert code before and after MInst to free up the value. If so, - // this code should be first/last in the spill sequence before/after MInst. - int TmpRegU=(LR->hasColor() - ? MRI.getUnifiedRegNum(LR->getRegClassID(),LR->getColor()) - : getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef,MIAft)); - - // Set the operand first so that it this register does not get used - // as a scratch register for later calls to getUsableUniRegAtMI below - MInst->SetRegForOperand(OpNum, TmpRegU); - - // get the added instructions for this instruction - AddedInstrns &AI = AddedInstrMap[MInst]; - - // We may need a scratch register to copy the spilled value to/from memory. - // This may itself have to insert code to free up a scratch register. - // Any such code should go before (after) the spill code for a load (store). - // The scratch reg is not marked as used because it is only used - // for the copy and not used across MInst. - int scratchRegType = -1; - int scratchReg = -1; - if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) { - scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef, - MInst, MIBef, MIAft); - assert(scratchReg != MRI.getInvalidRegNum()); - } - - if (isUse) { - // for a USE, we have to load the value of LR from stack to a TmpReg - // and use the TmpReg as one operand of instruction - - // actual loading instruction(s) - MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, - RegType, scratchReg); - - // the actual load should be after the instructions to free up TmpRegU - MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end()); - AdIMid.clear(); - } - - if (isDef) { // if this is a Def - // for a DEF, we have to store the value produced by this instruction - // on the stack position allocated for this LR - - // actual storing instruction(s) - MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, - RegType, scratchReg); - - MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end()); - } // if !DEF - - // Finally, insert the entire spill code sequences before/after MInst - AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end()); - AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end()); - - if (DEBUG_RA) { - std::cerr << "\nFor Inst:\n " << *MInst; - std::cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex(); - std::cerr << "; added Instructions:"; - for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump)); - for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump)); - } -} - - -/// Insert caller saving/restoring instructions before/after a call machine -/// instruction (before or after any other instructions that were inserted for -/// the call). -/// -void -PhyRegAlloc::insertCallerSavingCode(std::vector<MachineInstr*> &instrnsBefore, - std::vector<MachineInstr*> &instrnsAfter, - MachineInstr *CallMI, - const BasicBlock *BB) { - assert(TM.getInstrInfo().isCall(CallMI->getOpCode())); - - // hash set to record which registers were saved/restored - hash_set<unsigned> PushedRegSet; - - CallArgsDescriptor* argDesc = CallArgsDescriptor::get(CallMI); - - // if the call is to a instrumentation function, do not insert save and - // restore instructions the instrumentation function takes care of save - // restore for volatile regs. - // - // FIXME: this should be made general, not specific to the reoptimizer! - const Function *Callee = argDesc->getCallInst()->getCalledFunction(); - bool isLLVMFirstTrigger = Callee && Callee->getName() == "llvm_first_trigger"; - - // Now check if the call has a return value (using argDesc) and if so, - // find the LR of the TmpInstruction representing the return value register. - // (using the last or second-last *implicit operand* of the call MI). - // Insert it to to the PushedRegSet since we must not save that register - // and restore it after the call. - // We do this because, we look at the LV set *after* the instruction - // to determine, which LRs must be saved across calls. The return value - // of the call is live in this set - but we must not save/restore it. - if (const Value *origRetVal = argDesc->getReturnValue()) { - unsigned retValRefNum = (CallMI->getNumImplicitRefs() - - (argDesc->getIndirectFuncPtr()? 1 : 2)); - const TmpInstruction* tmpRetVal = - cast<TmpInstruction>(CallMI->getImplicitRef(retValRefNum)); - assert(tmpRetVal->getOperand(0) == origRetVal && - tmpRetVal->getType() == origRetVal->getType() && - "Wrong implicit ref?"); - LiveRange *RetValLR = LRI->getLiveRangeForValue(tmpRetVal); - assert(RetValLR && "No LR for RetValue of call"); - - if (! RetValLR->isMarkedForSpill()) - PushedRegSet.insert(MRI.getUnifiedRegNum(RetValLR->getRegClassID(), - RetValLR->getColor())); - } - - const ValueSet &LVSetAft = LVI->getLiveVarSetAfterMInst(CallMI, BB); - ValueSet::const_iterator LIt = LVSetAft.begin(); - - // for each live var in live variable set after machine inst - for( ; LIt != LVSetAft.end(); ++LIt) { - // get the live range corresponding to live var - LiveRange *const LR = LRI->getLiveRangeForValue(*LIt); - - // LR can be null if it is a const since a const - // doesn't have a dominating def - see Assumptions above - if (LR) { - if (! LR->isMarkedForSpill()) { - assert(LR->hasColor() && "LR is neither spilled nor colored?"); - unsigned RCID = LR->getRegClassID(); - unsigned Color = LR->getColor(); - - if (MRI.isRegVolatile(RCID, Color) ) { - // if this is a call to the first-level reoptimizer - // instrumentation entry point, and the register is not - // modified by call, don't save and restore it. - if (isLLVMFirstTrigger && !MRI.modifiedByCall(RCID, Color)) - continue; - - // if the value is in both LV sets (i.e., live before and after - // the call machine instruction) - unsigned Reg = MRI.getUnifiedRegNum(RCID, Color); - - // if we haven't already pushed this register... - if( PushedRegSet.find(Reg) == PushedRegSet.end() ) { - unsigned RegType = MRI.getRegTypeForLR(LR); - - // Now get two instructions - to push on stack and pop from stack - // and add them to InstrnsBefore and InstrnsAfter of the - // call instruction - int StackOff = - MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType)); - - //---- Insert code for pushing the reg on stack ---------- - - std::vector<MachineInstr*> AdIBef, AdIAft; - - // We may need a scratch register to copy the saved value - // to/from memory. This may itself have to insert code to - // free up a scratch register. Any such code should go before - // the save code. The scratch register, if any, is by default - // temporary and not "used" by the instruction unless the - // copy code itself decides to keep the value in the scratch reg. - int scratchRegType = -1; - int scratchReg = -1; - if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) - { // Find a register not live in the LVSet before CallMI - const ValueSet &LVSetBef = - LVI->getLiveVarSetBeforeMInst(CallMI, BB); - scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef, - CallMI, AdIBef, AdIAft); - assert(scratchReg != MRI.getInvalidRegNum()); - } - - if (AdIBef.size() > 0) - instrnsBefore.insert(instrnsBefore.end(), - AdIBef.begin(), AdIBef.end()); - - MRI.cpReg2MemMI(instrnsBefore, Reg, MRI.getFramePointer(), - StackOff, RegType, scratchReg); - - if (AdIAft.size() > 0) - instrnsBefore.insert(instrnsBefore.end(), - AdIAft.begin(), AdIAft.end()); - - //---- Insert code for popping the reg from the stack ---------- - AdIBef.clear(); - AdIAft.clear(); - - // We may need a scratch register to copy the saved value - // from memory. This may itself have to insert code to - // free up a scratch register. Any such code should go - // after the save code. As above, scratch is not marked "used". - scratchRegType = -1; - scratchReg = -1; - if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) - { // Find a register not live in the LVSet after CallMI - scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetAft, - CallMI, AdIBef, AdIAft); - assert(scratchReg != MRI.getInvalidRegNum()); - } - - if (AdIBef.size() > 0) - instrnsAfter.insert(instrnsAfter.end(), - AdIBef.begin(), AdIBef.end()); - - MRI.cpMem2RegMI(instrnsAfter, MRI.getFramePointer(), StackOff, - Reg, RegType, scratchReg); - - if (AdIAft.size() > 0) - instrnsAfter.insert(instrnsAfter.end(), - AdIAft.begin(), AdIAft.end()); - - PushedRegSet.insert(Reg); - - if(DEBUG_RA) { - std::cerr << "\nFor call inst:" << *CallMI; - std::cerr << " -inserted caller saving instrs: Before:\n\t "; - for_each(instrnsBefore.begin(), instrnsBefore.end(), - std::mem_fun(&MachineInstr::dump)); - std::cerr << " -and After:\n\t "; - for_each(instrnsAfter.begin(), instrnsAfter.end(), - std::mem_fun(&MachineInstr::dump)); - } - } // if not already pushed - } // if LR has a volatile color - } // if LR has color - } // if there is a LR for Var - } // for each value in the LV set after instruction -} - - -/// Returns the unified register number of a temporary register to be used -/// BEFORE MInst. If no register is available, it will pick one and modify -/// MIBef and MIAft to contain instructions used to free up this returned -/// register. -/// -int PhyRegAlloc::getUsableUniRegAtMI(const int RegType, - const ValueSet *LVSetBef, - MachineInstr *MInst, - std::vector<MachineInstr*>& MIBef, - std::vector<MachineInstr*>& MIAft) { - RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType)); - - int RegU = getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef); - - if (RegU == -1) { - // we couldn't find an unused register. Generate code to free up a reg by - // saving it on stack and restoring after the instruction - - int TmpOff = MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType)); - - RegU = getUniRegNotUsedByThisInst(RC, RegType, MInst); - - // Check if we need a scratch register to copy this register to memory. - int scratchRegType = -1; - if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) { - int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef, - MInst, MIBef, MIAft); - assert(scratchReg != MRI.getInvalidRegNum()); - - // We may as well hold the value in the scratch register instead - // of copying it to memory and back. But we have to mark the - // register as used by this instruction, so it does not get used - // as a scratch reg. by another operand or anyone else. - ScratchRegsUsed.insert(std::make_pair(MInst, scratchReg)); - MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType); - MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType); - } else { // the register can be copied directly to/from memory so do it. - MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType); - MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType); - } - } - - return RegU; -} - - -/// Returns the register-class register number of a new unused register that -/// can be used to accommodate a temporary value. May be called repeatedly -/// for a single MachineInstr. On each call, it finds a register which is not -/// live at that instruction and which is not used by any spilled operands of -/// that instruction. -/// -int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC, const int RegType, - const MachineInstr *MInst, - const ValueSet* LVSetBef) { - RC->clearColorsUsed(); // Reset array - - if (LVSetBef == NULL) { - LVSetBef = &LVI->getLiveVarSetBeforeMInst(MInst); - assert(LVSetBef != NULL && "Unable to get live-var set before MInst?"); - } - - ValueSet::const_iterator LIt = LVSetBef->begin(); - - // for each live var in live variable set after machine inst - for ( ; LIt != LVSetBef->end(); ++LIt) { - // Get the live range corresponding to live var, and its RegClass - LiveRange *const LRofLV = LRI->getLiveRangeForValue(*LIt ); - - // LR can be null if it is a const since a const - // doesn't have a dominating def - see Assumptions above - if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor()) - RC->markColorsUsed(LRofLV->getColor(), - MRI.getRegTypeForLR(LRofLV), RegType); - } - - // It is possible that one operand of this MInst was already spilled - // and it received some register temporarily. If that's the case, - // it is recorded in machine operand. We must skip such registers. - setRelRegsUsedByThisInst(RC, RegType, MInst); - - int unusedReg = RC->getUnusedColor(RegType); // find first unused color - if (unusedReg >= 0) - return MRI.getUnifiedRegNum(RC->getID(), unusedReg); - - return -1; -} - - -/// Return the unified register number of a register in class RC which is not -/// used by any operands of MInst. -/// -int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC, - const int RegType, - const MachineInstr *MInst) { - RC->clearColorsUsed(); - - setRelRegsUsedByThisInst(RC, RegType, MInst); - - // find the first unused color - int unusedReg = RC->getUnusedColor(RegType); - assert(unusedReg >= 0 && - "FATAL: No free register could be found in reg class!!"); - - return MRI.getUnifiedRegNum(RC->getID(), unusedReg); -} - - -/// Modify the IsColorUsedArr of register class RC, by setting the bits -/// corresponding to register RegNo. This is a helper method of -/// setRelRegsUsedByThisInst(). -/// -static void markRegisterUsed(int RegNo, RegClass *RC, int RegType, - const TargetRegInfo &TRI) { - unsigned classId = 0; - int classRegNum = TRI.getClassRegNum(RegNo, classId); - if (RC->getID() == classId) - RC->markColorsUsed(classRegNum, RegType, RegType); -} - -void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, int RegType, - const MachineInstr *MI) { - assert(OperandsColoredMap[MI] == true && - "Illegal to call setRelRegsUsedByThisInst() until colored operands " - "are marked for an instruction."); - - // Add the registers already marked as used by the instruction. Both - // explicit and implicit operands are set. - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) - if (MI->getOperand(i).hasAllocatedReg()) - markRegisterUsed(MI->getOperand(i).getAllocatedRegNum(), RC, RegType,MRI); - - for (unsigned i = 0, e = MI->getNumImplicitRefs(); i != e; ++i) - if (MI->getImplicitOp(i).hasAllocatedReg()) - markRegisterUsed(MI->getImplicitOp(i).getAllocatedRegNum(), RC, - RegType,MRI); - - // Add all of the scratch registers that are used to save values across the - // instruction (e.g., for saving state register values). - std::pair<ScratchRegsUsedTy::iterator, ScratchRegsUsedTy::iterator> - IR = ScratchRegsUsed.equal_range(MI); - for (ScratchRegsUsedTy::iterator I = IR.first; I != IR.second; ++I) - markRegisterUsed(I->second, RC, RegType, MRI); - - // If there are implicit references, mark their allocated regs as well - for (unsigned z=0; z < MI->getNumImplicitRefs(); z++) - if (const LiveRange* - LRofImpRef = LRI->getLiveRangeForValue(MI->getImplicitRef(z))) - if (LRofImpRef->hasColor()) - // this implicit reference is in a LR that received a color - RC->markColorsUsed(LRofImpRef->getColor(), - MRI.getRegTypeForLR(LRofImpRef), RegType); -} - - -/// If there are delay slots for an instruction, the instructions added after -/// it must really go after the delayed instruction(s). So, we Move the -/// InstrAfter of that instruction to the corresponding delayed instruction -/// using the following method. -/// -void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI, - const MachineInstr *DelayedMI) -{ - // "added after" instructions of the original instr - std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter; - - if (DEBUG_RA && OrigAft.size() > 0) { - std::cerr << "\nRegAlloc: Moved InstrnsAfter for: " << *OrigMI; - std::cerr << " to last delay slot instrn: " << *DelayedMI; - } - - // "added after" instructions of the delayed instr - std::vector<MachineInstr *> &DelayedAft=AddedInstrMap[DelayedMI].InstrnsAfter; - - // go thru all the "added after instructions" of the original instruction - // and append them to the "added after instructions" of the delayed - // instructions - DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end()); - - // empty the "added after instructions" of the original instruction - OrigAft.clear(); -} - - -void PhyRegAlloc::colorIncomingArgs() -{ - MRI.colorMethodArgs(Fn, *LRI, AddedInstrAtEntry.InstrnsBefore, - AddedInstrAtEntry.InstrnsAfter); -} - - -/// Determine whether the suggested color of each live range is really usable, -/// and then call its setSuggestedColorUsable() method to record the answer. A -/// suggested color is NOT usable when the suggested color is volatile AND -/// when there are call interferences. -/// -void PhyRegAlloc::markUnusableSugColors() -{ - LiveRangeMapType::const_iterator HMI = (LRI->getLiveRangeMap())->begin(); - LiveRangeMapType::const_iterator HMIEnd = (LRI->getLiveRangeMap())->end(); - - for (; HMI != HMIEnd ; ++HMI ) { - if (HMI->first) { - LiveRange *L = HMI->second; // get the LiveRange - if (L && L->hasSuggestedColor ()) - L->setSuggestedColorUsable - (!(MRI.isRegVolatile (L->getRegClassID (), L->getSuggestedColor ()) - && L->isCallInterference ())); - } - } // for all LR's in hash map -} - - -/// For each live range that is spilled, allocates a new spill position on the -/// stack, and set the stack offsets of the live range that will be spilled to -/// that position. This must be called just after coloring the LRs. -/// -void PhyRegAlloc::allocateStackSpace4SpilledLRs() { - if (DEBUG_RA) std::cerr << "\nSetting LR stack offsets for spills...\n"; - - LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin(); - LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end(); - - for ( ; HMI != HMIEnd ; ++HMI) { - if (HMI->first && HMI->second) { - LiveRange *L = HMI->second; // get the LiveRange - if (L->isMarkedForSpill()) { // NOTE: allocating size of long Type ** - int stackOffset = MF->getInfo()->allocateSpilledValue(Type::LongTy); - L->setSpillOffFromFP(stackOffset); - if (DEBUG_RA) - std::cerr << " LR# " << L->getUserIGNode()->getIndex() - << ": stack-offset = " << stackOffset << "\n"; - } - } - } // for all LR's in hash map -} - - -void PhyRegAlloc::saveStateForValue (std::vector<AllocInfo> &state, - const Value *V, unsigned Insn, int Opnd) { - LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap ()->find (V); - LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap ()->end (); - AllocInfo::AllocStateTy AllocState = AllocInfo::NotAllocated; - int Placement = -1; - if ((HMI != HMIEnd) && HMI->second) { - LiveRange *L = HMI->second; - assert ((L->hasColor () || L->isMarkedForSpill ()) - && "Live range exists but not colored or spilled"); - if (L->hasColor ()) { - AllocState = AllocInfo::Allocated; - Placement = MRI.getUnifiedRegNum (L->getRegClassID (), - L->getColor ()); - } else if (L->isMarkedForSpill ()) { - AllocState = AllocInfo::Spilled; - assert (L->hasSpillOffset () - && "Live range marked for spill but has no spill offset"); - Placement = L->getSpillOffFromFP (); - } - } - state.push_back (AllocInfo (Insn, Opnd, AllocState, Placement)); -} - - -/// Save the global register allocation decisions made by the register -/// allocator so that they can be accessed later (sort of like "poor man's -/// debug info"). -/// -void PhyRegAlloc::saveState () { - std::vector<AllocInfo> &state = FnAllocState[Fn]; - unsigned Insn = 0; - for (const_inst_iterator II=inst_begin (Fn), IE=inst_end (Fn); II!=IE; ++II){ - saveStateForValue (state, (*II), Insn, -1); - for (unsigned i = 0; i < (*II)->getNumOperands (); ++i) { - const Value *V = (*II)->getOperand (i); - // Don't worry about it unless it's something whose reg. we'll need. - if (!isa<Argument> (V) && !isa<Instruction> (V)) - continue; - saveStateForValue (state, V, Insn, i); - } - ++Insn; - } -} - - -/// Check the saved state filled in by saveState(), and abort if it looks -/// wrong. Only used when debugging. FIXME: Currently it just prints out -/// the state, which isn't quite as useful. -/// -void PhyRegAlloc::verifySavedState () { - std::vector<AllocInfo> &state = FnAllocState[Fn]; - unsigned Insn = 0; - for (const_inst_iterator II=inst_begin (Fn), IE=inst_end (Fn); II!=IE; ++II) { - const Instruction *I = *II; - MachineCodeForInstruction &Instrs = MachineCodeForInstruction::get (I); - std::cerr << "Instruction:\n" << " " << *I << "\n" - << "MachineCodeForInstruction:\n"; - for (unsigned i = 0, n = Instrs.size (); i != n; ++i) - std::cerr << " " << *Instrs[i] << "\n"; - std::cerr << "FnAllocState:\n"; - for (unsigned i = 0; i < state.size (); ++i) { - AllocInfo &S = state[i]; - if (Insn == S.Instruction) { - std::cerr << " (Instruction " << S.Instruction - << ", Operand " << S.Operand - << ", AllocState " << S.allocStateToString () - << ", Placement " << S.Placement << ")\n"; - } - } - std::cerr << "----------\n"; - ++Insn; - } -} - - -/// Finish the job of saveState(), by collapsing FnAllocState into an LLVM -/// Constant and stuffing it inside the Module. (NOTE: Soon, there will be -/// other, better ways of storing the saved state; this one is cumbersome and -/// does not work well with the JIT.) -/// -bool PhyRegAlloc::doFinalization (Module &M) { - if (!SaveRegAllocState) - return false; // Nothing to do here, unless we're saving state. - - // If saving state into the module, just copy new elements to the - // correct global. - if (!SaveStateToModule) { - ExportedFnAllocState = FnAllocState; - // FIXME: should ONLY copy new elements in FnAllocState - return false; - } - - // Convert FnAllocState to a single Constant array and add it - // to the Module. - ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), 0); - std::vector<const Type *> TV; - TV.push_back (Type::UIntTy); - TV.push_back (AT); - PointerType *PT = PointerType::get (StructType::get (TV)); - - std::vector<Constant *> allstate; - for (Module::iterator I = M.begin (), E = M.end (); I != E; ++I) { - Function *F = I; - if (F->isExternal ()) continue; - if (FnAllocState.find (F) == FnAllocState.end ()) { - allstate.push_back (ConstantPointerNull::get (PT)); - } else { - std::vector<AllocInfo> &state = FnAllocState[F]; - - // Convert state into an LLVM ConstantArray, and put it in a - // ConstantStruct (named S) along with its size. - std::vector<Constant *> stateConstants; - for (unsigned i = 0, s = state.size (); i != s; ++i) - stateConstants.push_back (state[i].toConstant ()); - unsigned Size = stateConstants.size (); - ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), Size); - std::vector<const Type *> TV; - TV.push_back (Type::UIntTy); - TV.push_back (AT); - StructType *ST = StructType::get (TV); - std::vector<Constant *> CV; - CV.push_back (ConstantUInt::get (Type::UIntTy, Size)); - CV.push_back (ConstantArray::get (AT, stateConstants)); - Constant *S = ConstantStruct::get (ST, CV); - - GlobalVariable *GV = - new GlobalVariable (ST, true, - GlobalValue::InternalLinkage, S, - F->getName () + ".regAllocState", &M); - - // Have: { uint, [Size x { uint, int, uint, int }] } * - // Cast it to: { uint, [0 x { uint, int, uint, int }] } * - Constant *CE = ConstantExpr::getCast (ConstantPointerRef::get (GV), PT); - allstate.push_back (CE); - } - } - - unsigned Size = allstate.size (); - // Final structure type is: - // { uint, [Size x { uint, [0 x { uint, int, uint, int }] } *] } - std::vector<const Type *> TV2; - TV2.push_back (Type::UIntTy); - ArrayType *AT2 = ArrayType::get (PT, Size); - TV2.push_back (AT2); - StructType *ST2 = StructType::get (TV2); - std::vector<Constant *> CV2; - CV2.push_back (ConstantUInt::get (Type::UIntTy, Size)); - CV2.push_back (ConstantArray::get (AT2, allstate)); - new GlobalVariable (ST2, true, GlobalValue::ExternalLinkage, - ConstantStruct::get (ST2, CV2), "_llvm_regAllocState", - &M); - return false; // No error. -} - - -/// Allocate registers for the machine code previously generated for F using -/// the graph-coloring algorithm. -/// -bool PhyRegAlloc::runOnFunction (Function &F) { - if (DEBUG_RA) - std::cerr << "\n********* Function "<< F.getName () << " ***********\n"; - - Fn = &F; - MF = &MachineFunction::get (Fn); - LVI = &getAnalysis<FunctionLiveVarInfo> (); - LRI = new LiveRangeInfo (Fn, TM, RegClassList); - LoopDepthCalc = &getAnalysis<LoopInfo> (); - - // Create each RegClass for the target machine and add it to the - // RegClassList. This must be done before calling constructLiveRanges(). - for (unsigned rc = 0; rc != NumOfRegClasses; ++rc) - RegClassList.push_back (new RegClass (Fn, &TM.getRegInfo (), - MRI.getMachineRegClass (rc))); - - LRI->constructLiveRanges(); // create LR info - if (DEBUG_RA >= RA_DEBUG_LiveRanges) - LRI->printLiveRanges(); - - createIGNodeListsAndIGs(); // create IGNode list and IGs - - buildInterferenceGraphs(); // build IGs in all reg classes - - if (DEBUG_RA >= RA_DEBUG_LiveRanges) { - // print all LRs in all reg classes - for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) - RegClassList[rc]->printIGNodeList(); - - // print IGs in all register classes - for ( unsigned rc=0; rc < NumOfRegClasses ; rc++) - RegClassList[rc]->printIG(); - } - - LRI->coalesceLRs(); // coalesce all live ranges - - if (DEBUG_RA >= RA_DEBUG_LiveRanges) { - // print all LRs in all reg classes - for (unsigned rc=0; rc < NumOfRegClasses; rc++) - RegClassList[rc]->printIGNodeList(); - - // print IGs in all register classes - for (unsigned rc=0; rc < NumOfRegClasses; rc++) - RegClassList[rc]->printIG(); - } - - // mark un-usable suggested color before graph coloring algorithm. - // When this is done, the graph coloring algo will not reserve - // suggested color unnecessarily - they can be used by another LR - markUnusableSugColors(); - - // color all register classes using the graph coloring algo - for (unsigned rc=0; rc < NumOfRegClasses ; rc++) - RegClassList[rc]->colorAllRegs(); - - // After graph coloring, if some LRs did not receive a color (i.e, spilled) - // a position for such spilled LRs - allocateStackSpace4SpilledLRs(); - - // Reset the temp. area on the stack before use by the first instruction. - // This will also happen after updating each instruction. - MF->getInfo()->popAllTempValues(); - - // color incoming args - if the correct color was not received - // insert code to copy to the correct register - colorIncomingArgs(); - - // Save register allocation state for this function in a Constant. - if (SaveRegAllocState) - saveState(); - if (DEBUG_RA) { // Check our work. - verifySavedState (); - } - - // Now update the machine code with register names and add any additional - // code inserted by the register allocator to the instruction stream. - updateMachineCode(); - - if (DEBUG_RA) { - std::cerr << "\n**** Machine Code After Register Allocation:\n\n"; - MF->dump(); - } - - // Tear down temporary data structures - for (unsigned rc = 0; rc < NumOfRegClasses; ++rc) - delete RegClassList[rc]; - RegClassList.clear (); - AddedInstrMap.clear (); - OperandsColoredMap.clear (); - ScratchRegsUsed.clear (); - AddedInstrAtEntry.clear (); - delete LRI; - - if (DEBUG_RA) std::cerr << "\nRegister allocation complete!\n"; - return false; // Function was not modified -} - -} // End llvm namespace diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.h b/lib/CodeGen/RegAlloc/PhyRegAlloc.h deleted file mode 100644 index 4ec083c..0000000 --- a/lib/CodeGen/RegAlloc/PhyRegAlloc.h +++ /dev/null @@ -1,186 +0,0 @@ -//===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This is the main entry point for register allocation. -// -// Notes: -// * RegisterClasses: Each RegClass accepts a -// TargetRegClass which contains machine specific info about that register -// class. The code in the RegClass is machine independent and they use -// access functions in the TargetRegClass 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. -// -//===----------------------------------------------------------------------===// - -#ifndef PHYREGALLOC_H -#define PHYREGALLOC_H - -#include "LiveRangeInfo.h" -#include "llvm/Pass.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegInfo.h" -#include <map> - -namespace llvm { - -class MachineFunction; -class FunctionLiveVarInfo; -class MachineInstr; -class LoopInfo; -class RegClass; -class Constant; - -//---------------------------------------------------------------------------- -// Class AddedInstrns: -// When register allocator inserts new instructions in to the existing -// instruction stream, it does NOT directly modify the instruction stream. -// Rather, it creates an object of AddedInstrns and stick it in the -// AddedInstrMap for an existing instruction. This class contains two vectors -// to store such instructions added before and after an existing instruction. -//---------------------------------------------------------------------------- - -struct AddedInstrns { - std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst - std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst - inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); } -}; - -//---------------------------------------------------------------------------- -// class PhyRegAlloc: -// Main class the register allocator. Call runOnFunction() to allocate -// registers for a Function. -//---------------------------------------------------------------------------- - -class PhyRegAlloc : public FunctionPass { - std::vector<RegClass *> RegClassList; // vector of register classes - const TargetMachine &TM; // target machine - const Function *Fn; // name of the function we work on - MachineFunction *MF; // descriptor for method's native code - FunctionLiveVarInfo *LVI; // LV information for this method - // (already computed for BBs) - LiveRangeInfo *LRI; // LR info (will be computed) - const TargetRegInfo &MRI; // Machine Register information - const unsigned NumOfRegClasses; // recorded here for efficiency - - // Map to indicate whether operands of each MachineInstr have been - // updated according to their assigned colors. This is only used in - // assertion checking (debug builds). - std::map<const MachineInstr *, bool> OperandsColoredMap; - - // AddedInstrMap - Used to store instrns added in this phase - std::map<const MachineInstr *, AddedInstrns> AddedInstrMap; - - // ScratchRegsUsed - Contains scratch register uses for a particular MI. - typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy; - ScratchRegsUsedTy ScratchRegsUsed; - - AddedInstrns AddedInstrAtEntry; // to store instrns added at entry - const LoopInfo *LoopDepthCalc; // to calculate loop depths - - PhyRegAlloc(const PhyRegAlloc&); // DO NOT IMPLEMENT - void operator=(const PhyRegAlloc&); // DO NOT IMPLEMENT -public: - typedef std::map<const Function *, std::vector<AllocInfo> > SavedStateMapTy; - - inline PhyRegAlloc (const TargetMachine &TM_) : - TM (TM_), MRI (TM.getRegInfo ()), - NumOfRegClasses (MRI.getNumOfRegClasses ()) { } - virtual ~PhyRegAlloc() { } - - /// runOnFunction - Main method called for allocating registers. - /// - virtual bool runOnFunction (Function &F); - - virtual bool doFinalization (Module &M); - - virtual void getAnalysisUsage (AnalysisUsage &AU) const; - - const char *getPassName () const { - return "Traditional graph-coloring reg. allocator"; - } - - inline const RegClass* getRegClassByID(unsigned id) const { - return RegClassList[id]; - } - inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; } - -private: - SavedStateMapTy FnAllocState; - - void addInterference(const Value *Def, const ValueSet *LVSet, - bool isCallInst); - bool markAllocatedRegs(MachineInstr* MInst); - - void addInterferencesForArgs(); - void createIGNodeListsAndIGs(); - void buildInterferenceGraphs(); - - void saveStateForValue (std::vector<AllocInfo> &state, - const Value *V, unsigned Insn, int Opnd); - void saveState(); - void verifySavedState(); - - void setCallInterferences(const MachineInstr *MI, - const ValueSet *LVSetAft); - - void move2DelayedInstr(const MachineInstr *OrigMI, - const MachineInstr *DelayedMI); - - void markUnusableSugColors(); - void allocateStackSpace4SpilledLRs(); - - void insertCode4SpilledLR(const LiveRange *LR, - MachineBasicBlock::iterator& MII, - MachineBasicBlock &MBB, unsigned OpNum); - - /// Method for inserting caller saving code. The caller must save all the - /// volatile registers live across a call. - /// - void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore, - std::vector<MachineInstr*>& instrnsAfter, - MachineInstr *CallMI, - const BasicBlock *BB); - - void colorIncomingArgs(); - void colorCallRetArgs(); - void updateMachineCode(); - void updateInstruction(MachineBasicBlock::iterator& MII, - MachineBasicBlock &MBB); - - int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef, - MachineInstr *MI, - std::vector<MachineInstr*>& MIBef, - std::vector<MachineInstr*>& MIAft); - - /// Callback method used to find unused registers. - /// LVSetBef is the live variable set to search for an unused register. - /// If it is not specified, the LV set before the current MI is used. - /// This is sufficient as long as no new copy instructions are generated - /// to copy the free register to memory. - /// - int getUnusedUniRegAtMI(RegClass *RC, int RegType, - const MachineInstr *MI, - const ValueSet *LVSetBef = 0); - - void setRelRegsUsedByThisInst(RegClass *RC, int RegType, - const MachineInstr *MI); - - int getUniRegNotUsedByThisInst(RegClass *RC, int RegType, - const MachineInstr *MI); - - void addInterf4PseudoInstr(const MachineInstr *MI); -}; - -} // End llvm namespace - -#endif diff --git a/lib/CodeGen/RegAlloc/RegAllocCommon.h b/lib/CodeGen/RegAlloc/RegAllocCommon.h deleted file mode 100644 index 7dd86b2..0000000 --- a/lib/CodeGen/RegAlloc/RegAllocCommon.h +++ /dev/null @@ -1,32 +0,0 @@ -//===-- RegAllocCommon.h --------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Shared declarations for register allocation. -// -//===----------------------------------------------------------------------===// - -#ifndef REGALLOCCOMMON_H -#define REGALLOCCOMMON_H - -namespace llvm { - -enum RegAllocDebugLevel_t { - RA_DEBUG_None = 0, - RA_DEBUG_Results = 1, - RA_DEBUG_Coloring = 2, - RA_DEBUG_Interference = 3, - RA_DEBUG_LiveRanges = 4, - RA_DEBUG_Verbose = 5 -}; - -extern RegAllocDebugLevel_t DEBUG_RA; - -} // End llvm namespace - -#endif diff --git a/lib/CodeGen/RegAlloc/RegClass.cpp b/lib/CodeGen/RegAlloc/RegClass.cpp deleted file mode 100644 index 9af87ba..0000000 --- a/lib/CodeGen/RegAlloc/RegClass.cpp +++ /dev/null @@ -1,250 +0,0 @@ -//===-- RegClass.cpp -----------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// class RegClass for coloring-based register allocation for LLVM. -// -//===----------------------------------------------------------------------===// - -#include "IGNode.h" -#include "RegAllocCommon.h" -#include "RegClass.h" -#include "llvm/Target/TargetRegInfo.h" - -namespace llvm { - -//---------------------------------------------------------------------------- -// This constructor inits IG. The actual matrix is created by a call to -// createInterferenceGraph() above. -//---------------------------------------------------------------------------- -RegClass::RegClass(const Function *M, - const TargetRegInfo *_MRI_, - const TargetRegClassInfo *_MRC_) - : Meth(M), MRI(_MRI_), MRC(_MRC_), - RegClassID( _MRC_->getRegClassID() ), - IG(this), IGNodeStack() { - if (DEBUG_RA >= RA_DEBUG_Interference) - std::cerr << "Created Reg Class: " << RegClassID << "\n"; - - IsColorUsedArr.resize(MRC->getNumOfAllRegs()); -} - - - -//---------------------------------------------------------------------------- -// Main entry point for coloring a register class. -//---------------------------------------------------------------------------- -void RegClass::colorAllRegs() -{ - if (DEBUG_RA >= RA_DEBUG_Coloring) - std::cerr << "Coloring IG of reg class " << RegClassID << " ...\n"; - // pre-color IGNodes - pushAllIGNodes(); // push all IG Nodes - - unsigned int StackSize = IGNodeStack.size(); - IGNode *CurIGNode; - // for all LRs on stack - for (unsigned int IGN=0; IGN < StackSize; IGN++) { - CurIGNode = IGNodeStack.top(); // pop the IGNode on top of stack - IGNodeStack.pop(); - colorIGNode (CurIGNode); // color it - } -} - - - -//---------------------------------------------------------------------------- -// The method for pushing all IGNodes on to the stack. -//---------------------------------------------------------------------------- -void RegClass::pushAllIGNodes() -{ - bool NeedMoreSpills; - - - IG.setCurDegreeOfIGNodes(); // calculate degree of IGNodes - - // push non-constrained IGNodes - bool PushedAll = pushUnconstrainedIGNodes(); - - if (DEBUG_RA >= RA_DEBUG_Coloring) { - std::cerr << " Puhsed all-unconstrained IGNodes. "; - if( PushedAll ) std::cerr << " No constrained nodes left."; - std::cerr << "\n"; - } - - if (PushedAll) // if NO constrained nodes left - return; - - - // now, we have constrained nodes. So, push one of them (the one with min - // spill cost) and try to push the others as unConstrained nodes. - // Repeat this. - - do { - //get node with min spill cost - IGNode *IGNodeSpill = getIGNodeWithMinSpillCost(); - // push that node on to stack - IGNodeStack.push(IGNodeSpill); - // set its OnStack flag and decrement degree of neighs - IGNodeSpill->pushOnStack(); - // now push NON-constrained ones, if any - NeedMoreSpills = !pushUnconstrainedIGNodes(); - if (DEBUG_RA >= RA_DEBUG_Coloring) - std::cerr << "\nConstrained IG Node found !@!" << IGNodeSpill->getIndex(); - } while(NeedMoreSpills); // repeat until we have pushed all - -} - - - - -//-------------------------------------------------------------------------- -// This method goes thru all IG nodes in the IGNodeList of an IG of a -// register class and push any unconstrained IG node left (that is not -// already pushed) -//-------------------------------------------------------------------------- - -bool RegClass::pushUnconstrainedIGNodes() -{ - // # of LRs for this reg class - unsigned int IGNodeListSize = IG.getIGNodeList().size(); - bool pushedall = true; - - // a pass over IGNodeList - for (unsigned i =0; i < IGNodeListSize; i++) { - - // get IGNode i from IGNodeList - IGNode *IGNode = IG.getIGNodeList()[i]; - - if (!IGNode ) // can be null due to merging - continue; - - // if already pushed on stack, continue. This can happen since this - // method can be called repeatedly until all constrained nodes are - // pushed - if (IGNode->isOnStack() ) - continue; - // if the degree of IGNode is lower - if ((unsigned) IGNode->getCurDegree() < MRC->getNumOfAvailRegs()) { - IGNodeStack.push( IGNode ); // push IGNode on to the stack - IGNode->pushOnStack(); // set OnStack and dec deg of neighs - - if (DEBUG_RA >= RA_DEBUG_Coloring) { - std::cerr << " pushed un-constrained IGNode " << IGNode->getIndex() - << " on to stack\n"; - } - } - else pushedall = false; // we didn't push all live ranges - - } // for - - // returns true if we pushed all live ranges - else false - return pushedall; -} - - - -//---------------------------------------------------------------------------- -// Get the IGNode with the minimum spill cost -//---------------------------------------------------------------------------- -IGNode * RegClass::getIGNodeWithMinSpillCost() { - unsigned int IGNodeListSize = IG.getIGNodeList().size(); - double MinSpillCost = 0; - IGNode *MinCostIGNode = NULL; - bool isFirstNode = true; - - // pass over IGNodeList to find the IGNode with minimum spill cost - // among all IGNodes that are not yet pushed on to the stack - for (unsigned int i =0; i < IGNodeListSize; i++) { - IGNode *IGNode = IG.getIGNodeList()[i]; - - if (!IGNode) // can be null due to merging - continue; - - if (!IGNode->isOnStack()) { - double SpillCost = (double) IGNode->getParentLR()->getSpillCost() / - (double) (IGNode->getCurDegree() + 1); - - if (isFirstNode) { // for the first IG node - MinSpillCost = SpillCost; - MinCostIGNode = IGNode; - isFirstNode = false; - } else if (MinSpillCost > SpillCost) { - MinSpillCost = SpillCost; - MinCostIGNode = IGNode; - } - } - } - - assert (MinCostIGNode && "No IGNode to spill"); - return MinCostIGNode; -} - - -//---------------------------------------------------------------------------- -// Color the IGNode using the machine specific code. -//---------------------------------------------------------------------------- -void RegClass::colorIGNode(IGNode *const Node) { - if (! Node->hasColor()) { // not colored as an arg etc. - - // init all elements of to IsColorUsedAr false; - clearColorsUsed(); - - // initialize all colors used by neighbors of this node to true - LiveRange *LR = Node->getParentLR(); - unsigned NumNeighbors = Node->getNumOfNeighbors(); - for (unsigned n=0; n < NumNeighbors; n++) { - IGNode *NeighIGNode = Node->getAdjIGNode(n); - LiveRange *NeighLR = NeighIGNode->getParentLR(); - - // Don't use a color if it is in use by the neighbor, - // or is suggested for use by the neighbor, - // markColorsUsed() should be given the color and the reg type for - // LR, not for NeighLR, because it should mark registers used based on - // the type we are looking for, not on the regType for the neighbour. - if (NeighLR->hasColor()) - this->markColorsUsed(NeighLR->getColor(), - MRI->getRegTypeForLR(NeighLR), - MRI->getRegTypeForLR(LR)); // use LR, not NeighLR - else if (NeighLR->hasSuggestedColor() && - NeighLR->isSuggestedColorUsable()) - this->markColorsUsed(NeighLR->getSuggestedColor(), - MRI->getRegTypeForLR(NeighLR), - MRI->getRegTypeForLR(LR)); // use LR, not NeighLR - } - - // call the target specific code for coloring - // - MRC->colorIGNode(Node, IsColorUsedArr); - } else { - if (DEBUG_RA >= RA_DEBUG_Coloring) { - std::cerr << " Node " << Node->getIndex(); - std::cerr << " already colored with color " << Node->getColor() << "\n"; - } - } - - - if (!Node->hasColor() ) { - if (DEBUG_RA >= RA_DEBUG_Coloring) { - std::cerr << " Node " << Node->getIndex(); - std::cerr << " - could not find a color (needs spilling)\n"; - } - } -} - -void RegClass::printIGNodeList() const { - std::cerr << "IG Nodes for Register Class " << RegClassID << ":" << "\n"; - IG.printIGNodeList(); -} - -void RegClass::printIG() { - std::cerr << "IG for Register Class " << RegClassID << ":" << "\n"; - IG.printIG(); -} - -} // End llvm namespace diff --git a/lib/CodeGen/RegAlloc/RegClass.h b/lib/CodeGen/RegAlloc/RegClass.h deleted file mode 100644 index 0071f7c..0000000 --- a/lib/CodeGen/RegAlloc/RegClass.h +++ /dev/null @@ -1,147 +0,0 @@ -//===-- RegClass.h - Machine Independent register coloring ------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -/* Title: RegClass.h -*- C++ -*- - Author: Ruchira Sasanka - Date: Aug 20, 01 - Purpose: Contains machine independent methods for register coloring. - -*/ - -#ifndef REGCLASS_H -#define REGCLASS_H - -#include "llvm/Target/TargetRegInfo.h" -#include "InterferenceGraph.h" -#include <stack> - -namespace llvm { - -class TargetRegClassInfo; - - -//----------------------------------------------------------------------------- -// Class RegClass -// -// Implements a machine independent 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 (TargetRegInfo 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 { - const Function *const Meth; // Function we are working on - const TargetRegInfo *MRI; // Machine register information - const TargetRegClassInfo *const MRC; // Machine reg. class for this RegClass - const unsigned RegClassID; // my int ID - - InterferenceGraph IG; // Interference graph - constructed by - // buildInterferenceGraph - std::stack<IGNode *> IGNodeStack; // the stack used for coloring - - // IsColorUsedArr - An array used for coloring each node. This array must be - // of size MRC->getNumOfAllRegs(). Allocated once in the constructor for - // efficiency. - // - std::vector<bool> IsColorUsedArr; - - - - //--------------------------- private methods ------------------------------ - - void pushAllIGNodes(); - - bool pushUnconstrainedIGNodes(); - - IGNode * getIGNodeWithMinSpillCost(); - - void colorIGNode(IGNode *const Node); - - // This directly marks the colors used by a particular register number - // within the register class. External users should use the public - // versions of this function below. - inline void markColorUsed(unsigned classRegNum) { - assert(classRegNum < IsColorUsedArr.size() && "Invalid register used?"); - IsColorUsedArr[classRegNum] = true; - } - - inline bool isColorUsed(unsigned regNum) const { - assert(regNum < IsColorUsedArr.size() && "Invalid register used?"); - return IsColorUsedArr[regNum]; - } - - public: - - RegClass(const Function *M, - const TargetRegInfo *_MRI_, - const TargetRegClassInfo *_MRC_); - - inline void createInterferenceGraph() { IG.createGraph(); } - - inline InterferenceGraph &getIG() { return IG; } - - inline const unsigned getID() const { return RegClassID; } - - inline const TargetRegClassInfo* getTargetRegClass() const { return MRC; } - - // main method called for coloring regs - // - void colorAllRegs(); - - inline unsigned getNumOfAvailRegs() const - { return MRC->getNumOfAvailRegs(); } - - - // --- 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 clearColorsUsed() { - IsColorUsedArr.clear(); - IsColorUsedArr.resize(MRC->getNumOfAllRegs()); - } - inline void markColorsUsed(unsigned ClassRegNum, - int UserRegType, - int RegTypeWanted) { - MRC->markColorsUsed(ClassRegNum, UserRegType, RegTypeWanted,IsColorUsedArr); - } - inline int getUnusedColor(int machineRegType) const { - return MRC->findUnusedColor(machineRegType, IsColorUsedArr); - } - - void printIGNodeList() const; - void printIG(); -}; - -} // End llvm namespace - -#endif diff --git a/lib/Target/SparcV9/Makefile b/lib/Target/SparcV9/Makefile index ab923a0..4972eb9 100644 --- a/lib/Target/SparcV9/Makefile +++ b/lib/Target/SparcV9/Makefile @@ -8,6 +8,7 @@ ##===----------------------------------------------------------------------===## LEVEL = ../../.. LIBRARYNAME = sparc +DIRS = RegAlloc ExtraSource = Sparc.burm.cpp diff --git a/lib/Target/SparcV9/RegAlloc/Makefile b/lib/Target/SparcV9/RegAlloc/Makefile index 6c4f50b..374c70f 100644 --- a/lib/Target/SparcV9/RegAlloc/Makefile +++ b/lib/Target/SparcV9/RegAlloc/Makefile @@ -6,7 +6,7 @@ # the University of Illinois Open Source License. See LICENSE.TXT for details. # ##===----------------------------------------------------------------------===## -LEVEL = ../../.. +LEVEL = ../../../.. DIRS = |