#
##===----------------------------------------------------------------------===##
LEVEL = ../..
-PARALLEL_DIRS = InstrSelection InstrSched RegAlloc SelectionDAG
+PARALLEL_DIRS = InstrSelection InstrSched SelectionDAG
LIBRARYNAME = codegen
include $(LEVEL)/Makefile.common
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-##===- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
+++ /dev/null
-//===-- 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
##===----------------------------------------------------------------------===##
LEVEL = ../../..
LIBRARYNAME = sparc
+DIRS = RegAlloc
ExtraSource = Sparc.burm.cpp
# the University of Illinois Open Source License. See LICENSE.TXT for details.
#
##===----------------------------------------------------------------------===##
-LEVEL = ../../..
+LEVEL = ../../../..
DIRS =
projects / oota-llvm.git / commitdiff