1 //===-- SparcV9RegClassInfo.cpp - Register class def'ns for SparcV9 -------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the methods used by the SparcV9 register allocator
11 // to pick registers of various classes. Most of this code should be
12 // considered part of the register allocator.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Type.h"
17 #include "SparcV9RegClassInfo.h"
18 #include "SparcV9Internals.h"
19 #include "SparcV9RegInfo.h"
20 #include "RegAlloc/RegAllocCommon.h"
21 #include "RegAlloc/IGNode.h"
26 //-----------------------------------------------------------------------------
27 // Int Register Class - method for coloring a node in the interference graph.
30 // Record the colors/suggested colors of all neighbors.
32 // If there is a suggested color, try to allocate it
33 // If there is no call interf, try to allocate volatile, then non volatile
34 // If there is call interf, try to allocate non-volatile. If that fails
35 // try to allocate a volatile and insert save across calls
36 // If both above fail, spill.
38 //-----------------------------------------------------------------------------
39 void SparcV9IntRegClass::colorIGNode(IGNode * Node,
40 const std::vector<bool> &IsColorUsedArr) const
42 LiveRange *LR = Node->getParentLR();
45 std::cerr << "\nColoring LR [CallInt=" << LR->isCallInterference() <<"]:";
49 if (LR->hasSuggestedColor()) {
50 unsigned SugCol = LR->getSuggestedColor();
51 if (!IsColorUsedArr[SugCol]) {
52 if (LR->isSuggestedColorUsable()) {
53 // if the suggested color is volatile, we should use it only if
54 // there are no call interferences. Otherwise, it will get spilled.
56 std::cerr << "\n -Coloring with sug color: " << SugCol;
58 LR->setColor(LR->getSuggestedColor());
61 std::cerr << "\n Couldn't alloc Sug col - LR volatile & calls interf";
63 } else if (DEBUG_RA) { // can't allocate the suggested col
64 std::cerr << "\n Could NOT allocate the suggested color (already used) ";
65 printSet(*LR); std::cerr << "\n";
69 unsigned SearchStart; // start pos of color in pref-order
70 bool ColorFound= false; // have we found a color yet?
72 //if this Node is between calls
73 if (! LR->isCallInterference()) {
74 // start with volatiles (we can allocate volatiles safely)
75 SearchStart = SparcV9IntRegClass::StartOfAllRegs;
77 // start with non volatiles (no non-volatiles)
78 SearchStart = SparcV9IntRegClass::StartOfNonVolatileRegs;
81 unsigned c=0; // color
83 // find first unused color
84 for (c=SearchStart; c < SparcV9IntRegClass::NumOfAvailRegs; c++) {
85 if (!IsColorUsedArr[c]) {
92 LR->setColor(c); // first color found in preferred order
93 if (DEBUG_RA) std::cerr << "\n Colored after first search with col " << c;
96 // if color is not found because of call interference
97 // try even finding a volatile color and insert save across calls
99 else if (LR->isCallInterference()) {
100 // start from 0 - try to find even a volatile this time
101 SearchStart = SparcV9IntRegClass::StartOfAllRegs;
103 // find first unused volatile color
104 for(c=SearchStart; c < SparcV9IntRegClass::StartOfNonVolatileRegs; c++) {
105 if (! IsColorUsedArr[c]) {
113 // get the live range corresponding to live var
114 // since LR span across calls, must save across calls
116 LR->markForSaveAcrossCalls();
118 std::cerr << "\n Colored after SECOND search with col " << c;
123 // If we couldn't find a color regardless of call interference - i.e., we
124 // don't have either a volatile or non-volatile color left
127 LR->markForSpill(); // no color found - must spill
130 //-----------------------------------------------------------------------------
131 // Int CC Register Class - method for coloring a node in the interference graph.
135 // If (node has any interferences)
136 // /* all interference operations can use only one register! */
137 // mark the LR for spilling
139 // if (the LR is a 64-bit comparison) use %xcc
140 // else /*32-bit or smaller*/ use %icc
143 // Note: The third name (%ccr) is essentially an assembly mnemonic and
144 // depends solely on the opcode, so the name can be chosen in EmitAssembly.
145 //-----------------------------------------------------------------------------
146 void SparcV9IntCCRegClass::colorIGNode(IGNode *Node,
147 const std::vector<bool> &IsColorUsedArr) const
149 if (Node->getNumOfNeighbors() > 0)
150 Node->getParentLR()->markForSpill();
152 // Mark the appropriate register in any case (even if it needs to be spilled)
153 // because there is only one possible register, but more importantly, the
154 // spill algorithm cannot find it. In particular, we have to choose
155 // whether to use %xcc or %icc based on type of value compared
157 const LiveRange* ccLR = Node->getParentLR();
158 const Type* setCCType = (* ccLR->begin())->getType(); // any Value in LR
159 assert(setCCType->isIntegral() || isa<PointerType>(setCCType));
160 int ccReg = ((isa<PointerType>(setCCType) || setCCType == Type::LongTy)
164 // Let's just make sure values of two different types have not been
165 // coalesced into this LR.
166 for (ValueSet::const_iterator I=ccLR->begin(), E=ccLR->end(); I!=E; ++I) {
167 const Type* ccType = (*I)->getType();
168 assert((ccReg == xcc && (isa<PointerType>(ccType)
169 || ccType == Type::LongTy)) ||
170 (ccReg == icc && ccType->isIntegral() && ccType != Type::LongTy)
171 && "Comparisons needing different intCC regs coalesced in LR!");
175 Node->setColor(ccReg); // only one int cc reg is available
179 void SparcV9FloatCCRegClass::colorIGNode(IGNode *Node,
180 const std::vector<bool> &IsColorUsedArr) const {
181 for(unsigned c = 0; c != 4; ++c)
182 if (!IsColorUsedArr[c]) { // find unused color
187 Node->getParentLR()->markForSpill();
192 //-----------------------------------------------------------------------------
193 // Float Register Class - method for coloring a node in the interference graph.
197 // If the LR is a double try to allocate f32 - f63
198 // If the above fails or LR is single precision
199 // If the LR does not interfere with a call
200 // start allocating from f0
201 // Else start allocating from f6
202 // If a color is still not found because LR interferes with a call
203 // Search in f0 - f6. If found mark for spill across calls.
204 // If a color is still not fond, mark for spilling
206 //----------------------------------------------------------------------------
207 void SparcV9FloatRegClass::colorIGNode(IGNode * Node,
208 const std::vector<bool> &IsColorUsedArr) const
210 LiveRange *LR = Node->getParentLR();
213 // Check that the correct colors have been are marked for fp-doubles.
215 // FIXME: This is old code that is no longer needed. Temporarily converting
216 // it into a big assertion just to check that the replacement logic
217 // (invoking SparcV9FloatRegClass::markColorsUsed() directly from
218 // RegClass::colorIGNode) works correctly.
220 // In fact, this entire function should be identical to
221 // SparcV9IntRegClass::colorIGNode(), and perhaps can be
222 // made into a general case in CodeGen/RegAlloc/RegClass.cpp.
224 unsigned NumNeighbors = Node->getNumOfNeighbors(); // total # of neighbors
225 for(unsigned n=0; n < NumNeighbors; n++) { // for each neigh
226 IGNode *NeighIGNode = Node->getAdjIGNode(n);
227 LiveRange *NeighLR = NeighIGNode->getParentLR();
229 if (NeighLR->hasColor()) {
230 assert(IsColorUsedArr[ NeighLR->getColor() ]);
231 if (NeighLR->getType() == Type::DoubleTy)
232 assert(IsColorUsedArr[ NeighLR->getColor()+1 ]);
234 } else if (NeighLR->hasSuggestedColor() &&
235 NeighLR-> isSuggestedColorUsable() ) {
237 // if the neighbour can use the suggested color
238 assert(IsColorUsedArr[ NeighLR->getSuggestedColor() ]);
239 if (NeighLR->getType() == Type::DoubleTy)
240 assert(IsColorUsedArr[ NeighLR->getSuggestedColor()+1 ]);
245 // **NOTE: We don't check for call interferences in allocating suggested
246 // color in this class since ALL registers are volatile. If this fact
247 // changes, we should change the following part
248 //- see SparcV9IntRegClass::colorIGNode()
250 if( LR->hasSuggestedColor() ) {
251 if( ! IsColorUsedArr[ LR->getSuggestedColor() ] ) {
252 LR->setColor( LR->getSuggestedColor() );
254 } else if (DEBUG_RA) { // can't allocate the suggested col
255 std::cerr << " Could NOT allocate the suggested color for LR ";
256 printSet(*LR); std::cerr << "\n";
261 int ColorFound = -1; // have we found a color yet?
262 bool isCallInterf = LR->isCallInterference();
264 // if value is a double - search the double only region (f32 - f63)
265 // i.e. we try to allocate f32 - f63 first for doubles since singles
266 // cannot go there. By doing that, we provide more space for singles
269 if (LR->getType() == Type::DoubleTy)
270 ColorFound = findFloatColor( LR, 32, 64, IsColorUsedArr );
272 if (ColorFound >= 0) { // if we could find a color
273 LR->setColor(ColorFound);
277 // if we didn't find a color because the LR was single precision or
278 // all f32-f63 range is filled, we try to allocate a register from
279 // the f0 - f31 region
281 unsigned SearchStart; // start pos of color in pref-order
283 //if this Node is between calls (i.e., no call interferences )
284 if (! isCallInterf) {
285 // start with volatiles (we can allocate volatiles safely)
286 SearchStart = SparcV9FloatRegClass::StartOfAllRegs;
288 // start with non volatiles (no non-volatiles)
289 SearchStart = SparcV9FloatRegClass::StartOfNonVolatileRegs;
292 ColorFound = findFloatColor(LR, SearchStart, 32, IsColorUsedArr);
295 if (ColorFound >= 0) { // if we could find a color
296 LR->setColor(ColorFound);
298 } else if (isCallInterf) {
299 // We are here because there is a call interference and no non-volatile
300 // color could be found.
301 // Now try to allocate even a volatile color
302 ColorFound = findFloatColor(LR, SparcV9FloatRegClass::StartOfAllRegs,
303 SparcV9FloatRegClass::StartOfNonVolatileRegs,
307 if (ColorFound >= 0) {
308 LR->setColor(ColorFound); // first color found in preferred order
309 LR->markForSaveAcrossCalls();
311 // we are here because no color could be found
312 LR->markForSpill(); // no color found - must spill
316 //-----------------------------------------------------------------------------
317 // This method marks the registers used for a given register number.
318 // This marks a single register for Float regs, but the R,R+1 pair
319 // for double-precision registers.
320 //-----------------------------------------------------------------------------
322 void SparcV9FloatRegClass::markColorsUsed(unsigned RegInClass,
325 std::vector<bool> &IsColorUsedArr) const
327 if (UserRegType == SparcV9RegInfo::FPDoubleRegType ||
328 RegTypeWanted == SparcV9RegInfo::FPDoubleRegType) {
329 // This register is used as or is needed as a double-precision reg.
330 // We need to mark the [even,odd] pair corresponding to this reg.
331 // Get the even numbered register corresponding to this reg.
332 unsigned EvenRegInClass = RegInClass & ~1u;
333 assert(EvenRegInClass+1 < NumOfAllRegs &&
334 EvenRegInClass+1 < IsColorUsedArr.size());
335 IsColorUsedArr[EvenRegInClass] = true;
336 IsColorUsedArr[EvenRegInClass+1] = true;
339 assert(RegInClass < NumOfAllRegs && RegInClass < IsColorUsedArr.size());
340 assert(UserRegType == RegTypeWanted
341 && "Something other than FP single/double types share a reg class?");
342 IsColorUsedArr[RegInClass] = true;
346 // This method finds unused registers of the specified register type,
347 // using the given "used" flag array IsColorUsedArr. It checks a single
348 // entry in the array directly for float regs, and checks the pair [R,R+1]
349 // for double-precision registers
350 // It returns -1 if no unused color is found.
352 int SparcV9FloatRegClass::findUnusedColor(int RegTypeWanted,
353 const std::vector<bool> &IsColorUsedArr) const
355 if (RegTypeWanted == SparcV9RegInfo::FPDoubleRegType) {
356 unsigned NC = 2 * this->getNumOfAvailRegs();
357 assert(IsColorUsedArr.size() == NC && "Invalid colors-used array");
358 for (unsigned c = 0; c < NC; c+=2)
359 if (!IsColorUsedArr[c]) {
360 assert(!IsColorUsedArr[c+1] && "Incorrect used regs for FP double!");
366 return TargetRegClassInfo::findUnusedColor(RegTypeWanted, IsColorUsedArr);
369 //-----------------------------------------------------------------------------
370 // Helper method for coloring a node of Float Reg class.
371 // Finds the first available color in the range [Start,End] depending on the
372 // type of the Node (i.e., float/double)
373 //-----------------------------------------------------------------------------
375 int SparcV9FloatRegClass::findFloatColor(const LiveRange *LR,
378 const std::vector<bool> &IsColorUsedArr) const
380 if (LR->getType() == Type::DoubleTy) {
381 // find first unused color for a double
382 assert(Start % 2 == 0 && "Odd register number could be used for double!");
383 for (unsigned c=Start; c < End ; c+= 2)
384 if (!IsColorUsedArr[c]) {
385 assert(!IsColorUsedArr[c+1] &&
386 "Incorrect marking of used regs for SparcV9 FP double!");
390 // find first unused color for a single
391 for (unsigned c = Start; c < End; c++)
392 if (!IsColorUsedArr[c])
400 } // End llvm namespace