-#include "SparcRegClassInfo.h"
-#include "llvm/CodeGen/IGNode.h"
-#include "llvm/Target/Sparc.h"
+//===-- SparcV9RegClassInfo.cpp - Register class def'ns for SparcV9 -------===//
+//
+// 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 defines the methods used by the SparcV9 register allocator
+// to pick registers of various classes. Most of this code should be
+// considered part of the register allocator.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Type.h"
+#include "SparcV9RegClassInfo.h"
+#include "SparcV9Internals.h"
+#include "SparcV9RegInfo.h"
+#include "RegAlloc/RegAllocCommon.h"
+#include "RegAlloc/IGNode.h"
#include <iostream>
-using std::cerr;
+
+namespace llvm {
//-----------------------------------------------------------------------------
// Int Register Class - method for coloring a node in the interference graph.
// If both above fail, spill.
//
//-----------------------------------------------------------------------------
-void SparcIntRegClass::colorIGNode(IGNode * Node, bool IsColorUsedArr[]) const {
+void SparcV9IntRegClass::colorIGNode(IGNode * Node,
+ const std::vector<bool> &IsColorUsedArr) const
+{
LiveRange *LR = Node->getParentLR();
- unsigned NumNeighbors = Node->getNumOfNeighbors(); // total # of neighbors
- for (unsigned n=0; n < NumNeighbors; n++) { // for each neigh
- IGNode *NeighIGNode = Node->getAdjIGNode(n);
- LiveRange *NeighLR = NeighIGNode->getParentLR();
-
- if(NeighLR->hasColor()) // if has a color
- IsColorUsedArr[NeighLR->getColor()] = true; // record that color
-
- else if (NeighLR->hasSuggestedColor()) {
-
- // if the neighbout can use the suggested color
- if(NeighLR->isSuggestedColorUsable())
- IsColorUsedArr[NeighLR->getSuggestedColor()] = true;
- }
- }
-
- if( DEBUG_RA ) {
- cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:";
- LR->printSet();
- }
-
- if( LR->hasSuggestedColor() ) {
+ if (DEBUG_RA)
+ std::cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:"
+ << *LR << "\n";
+ if (LR->hasSuggestedColor()) {
unsigned SugCol = LR->getSuggestedColor();
-
- if( ! IsColorUsedArr[ SugCol ] ) {
-
- if( LR->isSuggestedColorUsable() ) {
-
+ if (!IsColorUsedArr[SugCol]) {
+ if (LR->isSuggestedColorUsable()) {
// if the suggested color is volatile, we should use it only if
// there are no call interferences. Otherwise, it will get spilled.
-
if (DEBUG_RA)
- cerr << "\n -Coloring with sug color: " << SugCol;
+ std::cerr << "\n -Coloring with sug color: " << SugCol;
- LR->setColor( LR->getSuggestedColor() );
+ LR->setColor(LR->getSuggestedColor());
return;
+ } else if(DEBUG_RA) {
+ std::cerr << "\n Couldn't alloc Sug col - LR volatile & calls interf";
}
- else if(DEBUG_RA)
- cerr << "\n Couldn't alloc Sug col - LR voloatile & calls interf";
-
- }
- else if ( DEBUG_RA ) { // can't allocate the suggested col
- cerr << " \n Could NOT allocate the suggested color (already used) ";
- LR->printSet(); cerr << "\n";
+ } else if (DEBUG_RA) { // can't allocate the suggested col
+ std::cerr << "\n Could NOT allocate the suggested color (already used) "
+ << *LR << "\n";
}
}
bool ColorFound= false; // have we found a color yet?
//if this Node is between calls
- if( ! LR->isCallInterference() ) {
-
+ if (! LR->isCallInterference()) {
// start with volatiles (we can allocate volatiles safely)
- SearchStart = SparcIntRegOrder::StartOfAllRegs;
- }
- else {
+ SearchStart = SparcV9IntRegClass::StartOfAllRegs;
+ } else {
// start with non volatiles (no non-volatiles)
- SearchStart = SparcIntRegOrder::StartOfNonVolatileRegs;
+ SearchStart = SparcV9IntRegClass::StartOfNonVolatileRegs;
}
unsigned c=0; // color
// find first unused color
- for( c=SearchStart; c < SparcIntRegOrder::NumOfAvailRegs; c++) {
- if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
+ for (c=SearchStart; c < SparcV9IntRegClass::NumOfAvailRegs; c++) {
+ if (!IsColorUsedArr[c]) {
+ ColorFound = true;
+ break;
+ }
}
- if( ColorFound) {
- LR->setColor(c); // first color found in preffered order
- if (DEBUG_RA) cerr << "\n Colored after first search with col " << c ;
+ if (ColorFound) {
+ LR->setColor(c); // first color found in preferred order
+ if (DEBUG_RA) std::cerr << "\n Colored after first search with col " << c;
}
// if color is not found because of call interference
// try even finding a volatile color and insert save across calls
//
- else if( LR->isCallInterference() )
- {
+ else if (LR->isCallInterference()) {
// start from 0 - try to find even a volatile this time
- SearchStart = SparcIntRegOrder::StartOfAllRegs;
+ SearchStart = SparcV9IntRegClass::StartOfAllRegs;
// find first unused volatile color
- for(c=SearchStart; c < SparcIntRegOrder::StartOfNonVolatileRegs; c++) {
- if( ! IsColorUsedArr[ c ] ) { ColorFound = true; break; }
+ for(c=SearchStart; c < SparcV9IntRegClass::StartOfNonVolatileRegs; c++) {
+ if (! IsColorUsedArr[c]) {
+ ColorFound = true;
+ break;
+ }
}
if (ColorFound) {
- LR->setColor(c);
- // get the live range corresponding to live var
- // since LR span across calls, must save across calls
- //
- LR->markForSaveAcrossCalls();
- if(DEBUG_RA) cerr << "\n Colored after SECOND search with col " << c ;
+ LR->setColor(c);
+ // get the live range corresponding to live var
+ // since LR span across calls, must save across calls
+ //
+ if (DEBUG_RA)
+ std::cerr << "\n Colored after SECOND search with col " << c;
}
}
LR->markForSpill(); // no color found - must spill
}
+//-----------------------------------------------------------------------------
+// Int CC Register Class - method for coloring a node in the interference graph.
+//
+// Algorithm:
+//
+// If (node has any interferences)
+// /* all interference operations can use only one register! */
+// mark the LR for spilling
+// else {
+// if (the LR is a 64-bit comparison) use %xcc
+// else /*32-bit or smaller*/ use %icc
+// }
+//
+// Note: The third name (%ccr) is essentially an assembly mnemonic and
+// depends solely on the opcode, so the name can be chosen in EmitAssembly.
+//-----------------------------------------------------------------------------
+void SparcV9IntCCRegClass::colorIGNode(IGNode *Node,
+ const std::vector<bool> &IsColorUsedArr) const
+{
+ if (Node->getNumOfNeighbors() > 0)
+ Node->getParentLR()->markForSpill();
+
+ // Mark the appropriate register in any case (even if it needs to be spilled)
+ // because there is only one possible register, but more importantly, the
+ // spill algorithm cannot find it. In particular, we have to choose
+ // whether to use %xcc or %icc based on type of value compared
+ //
+ const LiveRange* ccLR = Node->getParentLR();
+ const Type* setCCType = (* ccLR->begin())->getType(); // any Value in LR
+ assert(setCCType->isIntegral() || isa<PointerType>(setCCType));
+ int ccReg = ((isa<PointerType>(setCCType) || setCCType == Type::LongTy)
+ ? xcc : icc);
+
+#ifndef NDEBUG
+ // Let's just make sure values of two different types have not been
+ // coalesced into this LR.
+ for (LiveRange::const_iterator I=ccLR->begin(), E=ccLR->end(); I!=E; ++I) {
+ const Type* ccType = (*I)->getType();
+ assert((ccReg == xcc && (isa<PointerType>(ccType)
+ || ccType == Type::LongTy)) ||
+ (ccReg == icc && ccType->isIntegral() && ccType != Type::LongTy)
+ && "Comparisons needing different intCC regs coalesced in LR!");
+ }
+#endif
+
+ Node->setColor(ccReg); // only one int cc reg is available
+}
+void SparcV9FloatCCRegClass::colorIGNode(IGNode *Node,
+ const std::vector<bool> &IsColorUsedArr) const {
+ for(unsigned c = 0; c != 4; ++c)
+ if (!IsColorUsedArr[c]) { // find unused color
+ Node->setColor(c);
+ return;
+ }
+
+ Node->getParentLR()->markForSpill();
+}
// If a color is still not fond, mark for spilling
//
//----------------------------------------------------------------------------
-void SparcFloatRegClass::colorIGNode(IGNode * Node,bool IsColorUsedArr[]) const
+void SparcV9FloatRegClass::colorIGNode(IGNode * Node,
+ const std::vector<bool> &IsColorUsedArr) const
{
+ LiveRange *LR = Node->getParentLR();
- LiveRange * LR = Node->getParentLR();
+#ifndef NDEBUG
+ // Check that the correct colors have been are marked for fp-doubles.
+ //
+ // FIXME: This is old code that is no longer needed. Temporarily converting
+ // it into a big assertion just to check that the replacement logic
+ // (invoking SparcV9FloatRegClass::markColorsUsed() directly from
+ // RegClass::colorIGNode) works correctly.
+ //
+ // In fact, this entire function should be identical to
+ // SparcV9IntRegClass::colorIGNode(), and perhaps can be
+ // made into a general case in CodeGen/RegAlloc/RegClass.cpp.
+ //
unsigned NumNeighbors = Node->getNumOfNeighbors(); // total # of neighbors
-
for(unsigned n=0; n < NumNeighbors; n++) { // for each neigh
IGNode *NeighIGNode = Node->getAdjIGNode(n);
LiveRange *NeighLR = NeighIGNode->getParentLR();
-
- if( NeighLR->hasColor() ) { // if neigh has a color
- IsColorUsedArr[ NeighLR->getColor() ] = true; // record that color
- if( NeighLR->getTypeID() == Type::DoubleTyID )
- IsColorUsedArr[ (NeighLR->getColor()) + 1 ] = true;
- }
- else if( NeighLR->hasSuggestedColor() ) { // if neigh has sugg color
-
- if( NeighLR-> isSuggestedColorUsable() ) {
-
- // if the neighbout can use the suggested color
-
- IsColorUsedArr[ NeighLR->getSuggestedColor() ] = true;
- if( NeighLR->getTypeID() == Type::DoubleTyID )
- IsColorUsedArr[ (NeighLR->getSuggestedColor()) + 1 ] = true;
- }
-
- }
-
+
+ if (NeighLR->hasColor()) {
+ assert(IsColorUsedArr[ NeighLR->getColor() ]);
+ if (NeighLR->getType() == Type::DoubleTy)
+ assert(IsColorUsedArr[ NeighLR->getColor()+1 ]);
+
+ } else if (NeighLR->hasSuggestedColor() &&
+ NeighLR-> isSuggestedColorUsable() ) {
+
+ // if the neighbour can use the suggested color
+ assert(IsColorUsedArr[ NeighLR->getSuggestedColor() ]);
+ if (NeighLR->getType() == Type::DoubleTy)
+ assert(IsColorUsedArr[ NeighLR->getSuggestedColor()+1 ]);
+ }
}
-
+#endif
// **NOTE: We don't check for call interferences in allocating suggested
// color in this class since ALL registers are volatile. If this fact
// changes, we should change the following part
- //- see SparcIntRegClass::colorIGNode()
-
+ //- see SparcV9IntRegClass::colorIGNode()
+ //
if( LR->hasSuggestedColor() ) {
if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
LR->setColor( LR->getSuggestedColor() );
return;
- }
- else if (DEBUG_RA) { // can't allocate the suggested col
- cerr << " Could NOT allocate the suggested color for LR ";
- LR->printSet(); cerr << "\n";
+ } else if (DEBUG_RA) { // can't allocate the suggested col
+ std::cerr << " Could NOT allocate the suggested color for LR " << *LR
+ << "\n";
}
}
int ColorFound = -1; // have we found a color yet?
bool isCallInterf = LR->isCallInterference();
- // if value is a double - search the double only reigon (f32 - f63)
+ // if value is a double - search the double only region (f32 - f63)
// i.e. we try to allocate f32 - f63 first for doubles since singles
// cannot go there. By doing that, we provide more space for singles
// in f0 - f31
//
- if( LR->getTypeID() == Type::DoubleTyID )
+ if (LR->getType() == Type::DoubleTy)
ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
-
- if( ColorFound >= 0 ) { // if we could find a color
+ if (ColorFound >= 0) { // if we could find a color
LR->setColor(ColorFound);
return;
} else {
- // if we didn't find a color becuase the LR was single precision or
+ // if we didn't find a color because the LR was single precision or
// all f32-f63 range is filled, we try to allocate a register from
// the f0 - f31 region
unsigned SearchStart; // start pos of color in pref-order
//if this Node is between calls (i.e., no call interferences )
- if( ! isCallInterf ) {
+ if (! isCallInterf) {
// start with volatiles (we can allocate volatiles safely)
- SearchStart = SparcFloatRegOrder::StartOfAllRegs;
- }
- else {
+ SearchStart = SparcV9FloatRegClass::StartOfAllRegs;
+ } else {
// start with non volatiles (no non-volatiles)
- SearchStart = SparcFloatRegOrder::StartOfNonVolatileRegs;
+ SearchStart = SparcV9FloatRegClass::StartOfNonVolatileRegs;
}
- ColorFound = findFloatColor( LR, SearchStart, 32, IsColorUsedArr );
+ ColorFound = findFloatColor(LR, SearchStart, 32, IsColorUsedArr);
}
-
-
- if( ColorFound >= 0 ) { // if we could find a color
+ if (ColorFound >= 0) { // if we could find a color
LR->setColor(ColorFound);
return;
- }
- else if( isCallInterf ) {
-
+ } else if (isCallInterf) {
// We are here because there is a call interference and no non-volatile
// color could be found.
// Now try to allocate even a volatile color
-
- ColorFound = findFloatColor( LR, SparcFloatRegOrder::StartOfAllRegs,
- SparcFloatRegOrder::StartOfNonVolatileRegs,
+ ColorFound = findFloatColor(LR, SparcV9FloatRegClass::StartOfAllRegs,
+ SparcV9FloatRegClass::StartOfNonVolatileRegs,
IsColorUsedArr);
}
-
-
- if( ColorFound >= 0 ) {
- LR->setColor(ColorFound); // first color found in preffered order
- LR->markForSaveAcrossCalls();
+ if (ColorFound >= 0) {
+ LR->setColor(ColorFound); // first color found in preferred order
} else {
// we are here because no color could be found
LR->markForSpill(); // no color found - must spill
}
}
+//-----------------------------------------------------------------------------
+// This method marks the registers used for a given register number.
+// This marks a single register for Float regs, but the R,R+1 pair
+// for double-precision registers.
+//-----------------------------------------------------------------------------
+
+void SparcV9FloatRegClass::markColorsUsed(unsigned RegInClass,
+ int UserRegType,
+ int RegTypeWanted,
+ std::vector<bool> &IsColorUsedArr) const
+{
+ if (UserRegType == SparcV9RegInfo::FPDoubleRegType ||
+ RegTypeWanted == SparcV9RegInfo::FPDoubleRegType) {
+ // This register is used as or is needed as a double-precision reg.
+ // We need to mark the [even,odd] pair corresponding to this reg.
+ // Get the even numbered register corresponding to this reg.
+ unsigned EvenRegInClass = RegInClass & ~1u;
+ assert(EvenRegInClass+1 < NumOfAllRegs &&
+ EvenRegInClass+1 < IsColorUsedArr.size());
+ IsColorUsedArr[EvenRegInClass] = true;
+ IsColorUsedArr[EvenRegInClass+1] = true;
+ }
+ else {
+ assert(RegInClass < NumOfAllRegs && RegInClass < IsColorUsedArr.size());
+ assert(UserRegType == RegTypeWanted
+ && "Something other than FP single/double types share a reg class?");
+ IsColorUsedArr[RegInClass] = true;
+ }
+}
+
+// This method finds unused registers of the specified register type,
+// using the given "used" flag array IsColorUsedArr. It checks a single
+// entry in the array directly for float regs, and checks the pair [R,R+1]
+// for double-precision registers
+// It returns -1 if no unused color is found.
+//
+int SparcV9FloatRegClass::findUnusedColor(int RegTypeWanted,
+ const std::vector<bool> &IsColorUsedArr) const
+{
+ if (RegTypeWanted == SparcV9RegInfo::FPDoubleRegType) {
+ unsigned NC = 2 * this->getNumOfAvailRegs();
+ assert(IsColorUsedArr.size() == NC && "Invalid colors-used array");
+ for (unsigned c = 0; c < NC; c+=2)
+ if (!IsColorUsedArr[c]) {
+ assert(!IsColorUsedArr[c+1] && "Incorrect used regs for FP double!");
+ return c;
+ }
+ return -1;
+ }
+ else
+ return TargetRegClassInfo::findUnusedColor(RegTypeWanted, IsColorUsedArr);
+}
//-----------------------------------------------------------------------------
// Helper method for coloring a node of Float Reg class.
// type of the Node (i.e., float/double)
//-----------------------------------------------------------------------------
-int SparcFloatRegClass::findFloatColor(const LiveRange *LR,
- unsigned Start, unsigned End,
- bool IsColorUsedArr[] ) const {
- bool ColorFound = false;
- unsigned c;
-
- if (LR->getTypeID() == Type::DoubleTyID) {
+int SparcV9FloatRegClass::findFloatColor(const LiveRange *LR,
+ unsigned Start,
+ unsigned End,
+ const std::vector<bool> &IsColorUsedArr) const
+{
+ if (LR->getType() == Type::DoubleTy) {
// find first unused color for a double
- for (c=Start; c < End ; c+= 2)
- if (!IsColorUsedArr[c] && !IsColorUsedArr[c+1])
+ assert(Start % 2 == 0 && "Odd register number could be used for double!");
+ for (unsigned c=Start; c < End ; c+= 2)
+ if (!IsColorUsedArr[c]) {
+ assert(!IsColorUsedArr[c+1] &&
+ "Incorrect marking of used regs for SparcV9 FP double!");
return c;
+ }
} else {
// find first unused color for a single
- for (c = Start; c < End; c++)
+ for (unsigned c = Start; c < End; c++)
if (!IsColorUsedArr[c])
return c;
}
-
+
return -1;
+
}
+
+} // End llvm namespace