1 //===-- PhyRegAlloc.cpp ---------------------------------------------------===//
3 // Register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "PhyRegAlloc.h"
8 #include "RegAllocCommon.h"
11 #include "llvm/CodeGen/MachineInstr.h"
12 #include "llvm/CodeGen/MachineInstrBuilder.h"
13 #include "llvm/CodeGen/MachineInstrAnnot.h"
14 #include "llvm/CodeGen/MachineFunction.h"
15 #include "llvm/CodeGen/MachineFunctionInfo.h"
16 #include "llvm/CodeGen/FunctionLiveVarInfo.h"
17 #include "llvm/CodeGen/InstrSelection.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Function.h"
21 #include "llvm/Type.h"
22 #include "llvm/iOther.h"
23 #include "Support/STLExtras.h"
24 #include "Support/SetOperations.h"
25 #include "Support/CommandLine.h"
28 RegAllocDebugLevel_t DEBUG_RA;
30 static cl::opt<RegAllocDebugLevel_t, true>
31 DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA),
32 cl::desc("enable register allocation debugging information"),
34 clEnumValN(RA_DEBUG_None , "n", "disable debug output"),
35 clEnumValN(RA_DEBUG_Results, "y", "debug output for allocation results"),
36 clEnumValN(RA_DEBUG_Coloring, "c", "debug output for graph coloring step"),
37 clEnumValN(RA_DEBUG_Interference,"ig","debug output for interference graphs"),
38 clEnumValN(RA_DEBUG_LiveRanges , "lr","debug output for live ranges"),
39 clEnumValN(RA_DEBUG_Verbose, "v", "extra debug output"),
42 FunctionPass *getRegisterAllocator(TargetMachine &T) {
43 return new PhyRegAlloc (T);
46 void PhyRegAlloc::getAnalysisUsage(AnalysisUsage &AU) const {
47 AU.addRequired<LoopInfo> ();
48 AU.addRequired<FunctionLiveVarInfo> ();
53 //----------------------------------------------------------------------------
54 // This method initially creates interference graphs (one in each reg class)
55 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
56 //----------------------------------------------------------------------------
57 void PhyRegAlloc::createIGNodeListsAndIGs() {
58 if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "Creating LR lists ...\n";
61 LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin();
64 LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end();
66 for (; HMI != HMIEnd ; ++HMI ) {
68 LiveRange *L = HMI->second; // get the LiveRange
71 std::cerr << "\n**** ?!?WARNING: NULL LIVE RANGE FOUND FOR: "
72 << RAV(HMI->first) << "****\n";
76 // if the Value * is not null, and LR is not yet written to the IGNodeList
77 if (!(L->getUserIGNode()) ) {
78 RegClass *const RC = // RegClass of first value in the LR
79 RegClassList[ L->getRegClass()->getID() ];
80 RC->addLRToIG(L); // add this LR to an IG
86 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
87 RegClassList[rc]->createInterferenceGraph();
89 if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "LRLists Created!\n";
93 //----------------------------------------------------------------------------
94 // This method will add all interferences at for a given instruction.
95 // Interference occurs only if the LR of Def (Inst or Arg) is of the same reg
96 // class as that of live var. The live var passed to this function is the
97 // LVset AFTER the instruction
98 //----------------------------------------------------------------------------
100 void PhyRegAlloc::addInterference(const Value *Def,
101 const ValueSet *LVSet,
103 ValueSet::const_iterator LIt = LVSet->begin();
105 // get the live range of instruction
106 const LiveRange *const LROfDef = LRI->getLiveRangeForValue( Def );
108 IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
109 assert( IGNodeOfDef );
111 RegClass *const RCOfDef = LROfDef->getRegClass();
113 // for each live var in live variable set
114 for ( ; LIt != LVSet->end(); ++LIt) {
116 if (DEBUG_RA >= RA_DEBUG_Verbose)
117 std::cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> ";
119 // get the live range corresponding to live var
120 LiveRange *LROfVar = LRI->getLiveRangeForValue(*LIt);
122 // LROfVar can be null if it is a const since a const
123 // doesn't have a dominating def - see Assumptions above
125 if (LROfDef != LROfVar) // do not set interf for same LR
126 if (RCOfDef == LROfVar->getRegClass()) // 2 reg classes are the same
127 RCOfDef->setInterference( LROfDef, LROfVar);
132 //----------------------------------------------------------------------------
133 // For a call instruction, this method sets the CallInterference flag in
134 // the LR of each variable live int the Live Variable Set live after the
135 // call instruction (except the return value of the call instruction - since
136 // the return value does not interfere with that call itself).
137 //----------------------------------------------------------------------------
139 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
140 const ValueSet *LVSetAft) {
141 if (DEBUG_RA >= RA_DEBUG_Interference)
142 std::cerr << "\n For call inst: " << *MInst;
144 // for each live var in live variable set after machine inst
145 for (ValueSet::const_iterator LIt = LVSetAft->begin(), LEnd = LVSetAft->end();
146 LIt != LEnd; ++LIt) {
148 // get the live range corresponding to live var
149 LiveRange *const LR = LRI->getLiveRangeForValue(*LIt );
151 // LR can be null if it is a const since a const
152 // doesn't have a dominating def - see Assumptions above
154 if (DEBUG_RA >= RA_DEBUG_Interference) {
155 std::cerr << "\n\tLR after Call: ";
158 LR->setCallInterference();
159 if (DEBUG_RA >= RA_DEBUG_Interference) {
160 std::cerr << "\n ++After adding call interference for LR: " ;
167 // Now find the LR of the return value of the call
168 // We do this because, we look at the LV set *after* the instruction
169 // to determine, which LRs must be saved across calls. The return value
170 // of the call is live in this set - but it does not interfere with call
171 // (i.e., we can allocate a volatile register to the return value)
172 CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
174 if (const Value *RetVal = argDesc->getReturnValue()) {
175 LiveRange *RetValLR = LRI->getLiveRangeForValue( RetVal );
176 assert( RetValLR && "No LR for RetValue of call");
177 RetValLR->clearCallInterference();
180 // If the CALL is an indirect call, find the LR of the function pointer.
181 // That has a call interference because it conflicts with outgoing args.
182 if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
183 LiveRange *AddrValLR = LRI->getLiveRangeForValue( AddrVal );
184 assert( AddrValLR && "No LR for indirect addr val of call");
185 AddrValLR->setCallInterference();
190 //----------------------------------------------------------------------------
191 // This method will walk thru code and create interferences in the IG of
192 // each RegClass. Also, this method calculates the spill cost of each
193 // Live Range (it is done in this method to save another pass over the code).
194 //----------------------------------------------------------------------------
196 void PhyRegAlloc::buildInterferenceGraphs()
198 if (DEBUG_RA >= RA_DEBUG_Interference)
199 std::cerr << "Creating interference graphs ...\n";
201 unsigned BBLoopDepthCost;
202 for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end();
204 const MachineBasicBlock &MBB = *BBI;
205 const BasicBlock *BB = MBB.getBasicBlock();
207 // find the 10^(loop_depth) of this BB
208 BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BB));
210 // get the iterator for machine instructions
211 MachineBasicBlock::const_iterator MII = MBB.begin();
213 // iterate over all the machine instructions in BB
214 for ( ; MII != MBB.end(); ++MII) {
215 const MachineInstr *MInst = *MII;
217 // get the LV set after the instruction
218 const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB);
219 bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
222 // set the isCallInterference flag of each live range which extends
223 // across this call instruction. This information is used by graph
224 // coloring algorithm to avoid allocating volatile colors to live ranges
225 // that span across calls (since they have to be saved/restored)
226 setCallInterferences(MInst, &LVSetAI);
229 // iterate over all MI operands to find defs
230 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
231 OpE = MInst->end(); OpI != OpE; ++OpI) {
232 if (OpI.isDefOnly() || OpI.isDefAndUse()) // create a new LR since def
233 addInterference(*OpI, &LVSetAI, isCallInst);
235 // Calculate the spill cost of each live range
236 LiveRange *LR = LRI->getLiveRangeForValue(*OpI);
237 if (LR) LR->addSpillCost(BBLoopDepthCost);
240 // if there are multiple defs in this instruction e.g. in SETX
241 if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
242 addInterf4PseudoInstr(MInst);
244 // Also add interference for any implicit definitions in a machine
245 // instr (currently, only calls have this).
246 unsigned NumOfImpRefs = MInst->getNumImplicitRefs();
247 for (unsigned z=0; z < NumOfImpRefs; z++)
248 if (MInst->getImplicitOp(z).opIsDefOnly() ||
249 MInst->getImplicitOp(z).opIsDefAndUse())
250 addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
252 } // for all machine instructions in BB
253 } // for all BBs in function
255 // add interferences for function arguments. Since there are no explicit
256 // defs in the function for args, we have to add them manually
257 addInterferencesForArgs();
259 if (DEBUG_RA >= RA_DEBUG_Interference)
260 std::cerr << "Interference graphs calculated!\n";
264 //--------------------------------------------------------------------------
265 // Pseudo-instructions may be expanded to multiple instructions by the
266 // assembler. Consequently, all the operands must get distinct registers.
267 // Therefore, we mark all operands of a pseudo-instruction as interfering
269 //--------------------------------------------------------------------------
271 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
272 bool setInterf = false;
274 // iterate over MI operands to find defs
275 for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
276 ItE = MInst->end(); It1 != ItE; ++It1) {
277 const LiveRange *LROfOp1 = LRI->getLiveRangeForValue(*It1);
278 assert((LROfOp1 || !It1.isUseOnly())&&"No LR for Def in PSEUDO insruction");
280 MachineInstr::const_val_op_iterator It2 = It1;
281 for (++It2; It2 != ItE; ++It2) {
282 const LiveRange *LROfOp2 = LRI->getLiveRangeForValue(*It2);
285 RegClass *RCOfOp1 = LROfOp1->getRegClass();
286 RegClass *RCOfOp2 = LROfOp2->getRegClass();
288 if (RCOfOp1 == RCOfOp2 ){
289 RCOfOp1->setInterference( LROfOp1, LROfOp2 );
293 } // for all other defs in machine instr
294 } // for all operands in an instruction
296 if (!setInterf && MInst->getNumOperands() > 2) {
297 std::cerr << "\nInterf not set for any operand in pseudo instr:\n";
299 assert(0 && "Interf not set for pseudo instr with > 2 operands" );
304 //----------------------------------------------------------------------------
305 // This method adds interferences for incoming arguments to a function.
306 //----------------------------------------------------------------------------
308 void PhyRegAlloc::addInterferencesForArgs() {
309 // get the InSet of root BB
310 const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front());
312 for (Function::const_aiterator AI = Fn->abegin(); AI != Fn->aend(); ++AI) {
313 // add interferences between args and LVars at start
314 addInterference(AI, &InSet, false);
316 if (DEBUG_RA >= RA_DEBUG_Interference)
317 std::cerr << " - %% adding interference for argument " << RAV(AI) << "\n";
322 //----------------------------------------------------------------------------
323 // This method is called after register allocation is complete to set the
324 // allocated registers in the machine code. This code will add register numbers
325 // to MachineOperands that contain a Value. Also it calls target specific
326 // methods to produce caller saving instructions. At the end, it adds all
327 // additional instructions produced by the register allocator to the
328 // instruction stream.
329 //----------------------------------------------------------------------------
331 //-----------------------------
332 // Utility functions used below
333 //-----------------------------
335 InsertBefore(MachineInstr* newMI,
336 MachineBasicBlock& MBB,
337 MachineBasicBlock::iterator& MII)
339 MII = MBB.insert(MII, newMI);
344 InsertAfter(MachineInstr* newMI,
345 MachineBasicBlock& MBB,
346 MachineBasicBlock::iterator& MII)
348 ++MII; // insert before the next instruction
349 MII = MBB.insert(MII, newMI);
353 DeleteInstruction(MachineBasicBlock& MBB,
354 MachineBasicBlock::iterator& MII)
356 MII = MBB.erase(MII);
360 SubstituteInPlace(MachineInstr* newMI,
361 MachineBasicBlock& MBB,
362 MachineBasicBlock::iterator MII)
368 PrependInstructions(std::vector<MachineInstr *> &IBef,
369 MachineBasicBlock& MBB,
370 MachineBasicBlock::iterator& MII,
371 const std::string& msg)
375 MachineInstr* OrigMI = *MII;
376 std::vector<MachineInstr *>::iterator AdIt;
377 for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
380 if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI;
381 std::cerr << msg << "PREPENDed instr:\n " << **AdIt << "\n";
383 InsertBefore(*AdIt, MBB, MII);
389 AppendInstructions(std::vector<MachineInstr *> &IAft,
390 MachineBasicBlock& MBB,
391 MachineBasicBlock::iterator& MII,
392 const std::string& msg)
396 MachineInstr* OrigMI = *MII;
397 std::vector<MachineInstr *>::iterator AdIt;
398 for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
401 if (OrigMI) std::cerr << "For MInst:\n " << *OrigMI;
402 std::cerr << msg << "APPENDed instr:\n " << **AdIt << "\n";
404 InsertAfter(*AdIt, MBB, MII);
409 bool PhyRegAlloc::markAllocatedRegs(MachineInstr* MInst)
411 bool instrNeedsSpills = false;
413 // First, set the registers for operands in the machine instruction
414 // if a register was successfully allocated. Do this first because we
415 // will need to know which registers are already used by this instr'n.
416 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
418 MachineOperand& Op = MInst->getOperand(OpNum);
419 if (Op.getType() == MachineOperand::MO_VirtualRegister ||
420 Op.getType() == MachineOperand::MO_CCRegister)
422 const Value *const Val = Op.getVRegValue();
423 if (const LiveRange* LR = LRI->getLiveRangeForValue(Val)) {
424 // Remember if any operand needs spilling
425 instrNeedsSpills |= LR->isMarkedForSpill();
427 // An operand may have a color whether or not it needs spilling
429 MInst->SetRegForOperand(OpNum,
430 MRI.getUnifiedRegNum(LR->getRegClass()->getID(),
434 } // for each operand
436 return instrNeedsSpills;
439 void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII,
440 MachineBasicBlock &MBB)
442 MachineInstr* MInst = *MII;
443 unsigned Opcode = MInst->getOpCode();
445 // Reset tmp stack positions so they can be reused for each machine instr.
446 MF->getInfo()->popAllTempValues();
448 // Mark the operands for which regs have been allocated.
449 bool instrNeedsSpills = markAllocatedRegs(*MII);
452 // Mark that the operands have been updated. Later,
453 // setRelRegsUsedByThisInst() is called to find registers used by each
454 // MachineInst, and it should not be used for an instruction until
455 // this is done. This flag just serves as a sanity check.
456 OperandsColoredMap[MInst] = true;
459 // Now insert caller-saving code before/after the call.
460 // Do this before inserting spill code since some registers must be
461 // used by save/restore and spill code should not use those registers.
462 if (TM.getInstrInfo().isCall(Opcode)) {
463 AddedInstrns &AI = AddedInstrMap[MInst];
464 insertCallerSavingCode(AI.InstrnsBefore, AI.InstrnsAfter, MInst,
465 MBB.getBasicBlock());
468 // Now insert spill code for remaining operands not allocated to
469 // registers. This must be done even for call return instructions
470 // since those are not handled by the special code above.
471 if (instrNeedsSpills)
472 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
474 MachineOperand& Op = MInst->getOperand(OpNum);
475 if (Op.getType() == MachineOperand::MO_VirtualRegister ||
476 Op.getType() == MachineOperand::MO_CCRegister)
478 const Value* Val = Op.getVRegValue();
479 if (const LiveRange *LR = LRI->getLiveRangeForValue(Val))
480 if (LR->isMarkedForSpill())
481 insertCode4SpilledLR(LR, MII, MBB, OpNum);
483 } // for each operand
486 void PhyRegAlloc::updateMachineCode()
488 // Insert any instructions needed at method entry
489 MachineBasicBlock::iterator MII = MF->front().begin();
490 PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MF->front(), MII,
491 "At function entry: \n");
492 assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
493 "InstrsAfter should be unnecessary since we are just inserting at "
494 "the function entry point here.");
496 for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end();
499 MachineBasicBlock &MBB = *BBI;
501 // Iterate over all machine instructions in BB and mark operands with
502 // their assigned registers or insert spill code, as appropriate.
503 // Also, fix operands of call/return instructions.
504 for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
505 if (! TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpCode()))
506 updateInstruction(MII, MBB);
508 // Now, move code out of delay slots of branches and returns if needed.
509 // (Also, move "after" code from calls to the last delay slot instruction.)
510 // Moving code out of delay slots is needed in 2 situations:
511 // (1) If this is a branch and it needs instructions inserted after it,
512 // move any existing instructions out of the delay slot so that the
513 // instructions can go into the delay slot. This only supports the
514 // case that #instrsAfter <= #delay slots.
516 // (2) If any instruction in the delay slot needs
517 // instructions inserted, move it out of the delay slot and before the
518 // branch because putting code before or after it would be VERY BAD!
520 // If the annul bit of the branch is set, neither of these is legal!
521 // If so, we need to handle spill differently but annulling is not yet used.
522 for (MachineBasicBlock::iterator MII = MBB.begin();
523 MII != MBB.end(); ++MII)
524 if (unsigned delaySlots =
525 TM.getInstrInfo().getNumDelaySlots((*MII)->getOpCode()))
527 MachineInstr *MInst = *MII, *DelaySlotMI = *(MII+1);
529 // Check the 2 conditions above:
530 // (1) Does a branch need instructions added after it?
531 // (2) O/w does delay slot instr. need instrns before or after?
532 bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) ||
533 TM.getInstrInfo().isReturn(MInst->getOpCode()));
534 bool cond1 = (isBranch &&
535 AddedInstrMap.count(MInst) &&
536 AddedInstrMap[MInst].InstrnsAfter.size() > 0);
537 bool cond2 = (AddedInstrMap.count(DelaySlotMI) &&
538 (AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 ||
539 AddedInstrMap[DelaySlotMI].InstrnsAfter.size() > 0));
543 assert((MInst->getOpCodeFlags() & AnnulFlag) == 0 &&
544 "FIXME: Moving an annulled delay slot instruction!");
545 assert(delaySlots==1 &&
546 "InsertBefore does not yet handle >1 delay slots!");
547 InsertBefore(DelaySlotMI, MBB, MII); // MII pts back to branch
549 // In case (1), delete it and don't replace with anything!
550 // Otherwise (i.e., case (2) only) replace it with a NOP.
552 DeleteInstruction(MBB, ++MII); // MII now points to next inst.
553 --MII; // reset MII for ++MII of loop
556 SubstituteInPlace(BuildMI(TM.getInstrInfo().getNOPOpCode(),1),
557 MBB, MII+1); // replace with NOP
560 std::cerr << "\nRegAlloc: Moved instr. with added code: "
562 << " out of delay slots of instr: " << *MInst;
566 // For non-branch instr with delay slots (probably a call), move
567 // InstrAfter to the instr. in the last delay slot.
568 move2DelayedInstr(*MII, *(MII+delaySlots));
571 // Finally iterate over all instructions in BB and insert before/after
572 for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) {
573 MachineInstr *MInst = *MII;
575 // do not process Phis
576 if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()))
579 // if there are any added instructions...
580 if (AddedInstrMap.count(MInst)) {
581 AddedInstrns &CallAI = AddedInstrMap[MInst];
584 bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) ||
585 TM.getInstrInfo().isReturn(MInst->getOpCode()));
587 AddedInstrMap[MInst].InstrnsAfter.size() <=
588 TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) &&
589 "Cannot put more than #delaySlots instrns after "
590 "branch or return! Need to handle temps differently.");
594 // Temporary sanity checking code to detect whether the same machine
595 // instruction is ever inserted twice before/after a call.
596 // I suspect this is happening but am not sure. --Vikram, 7/1/03.
597 std::set<const MachineInstr*> instrsSeen;
598 for (int i = 0, N = CallAI.InstrnsBefore.size(); i < N; ++i) {
599 assert(instrsSeen.count(CallAI.InstrnsBefore[i]) == 0 &&
600 "Duplicate machine instruction in InstrnsBefore!");
601 instrsSeen.insert(CallAI.InstrnsBefore[i]);
603 for (int i = 0, N = CallAI.InstrnsAfter.size(); i < N; ++i) {
604 assert(instrsSeen.count(CallAI.InstrnsAfter[i]) == 0 &&
605 "Duplicate machine instruction in InstrnsBefore/After!");
606 instrsSeen.insert(CallAI.InstrnsAfter[i]);
610 // Now add the instructions before/after this MI.
611 // We do this here to ensure that spill for an instruction is inserted
612 // as close as possible to an instruction (see above insertCode4Spill)
613 if (! CallAI.InstrnsBefore.empty())
614 PrependInstructions(CallAI.InstrnsBefore, MBB, MII,"");
616 if (! CallAI.InstrnsAfter.empty())
617 AppendInstructions(CallAI.InstrnsAfter, MBB, MII,"");
619 } // if there are any added instructions
620 } // for each machine instruction
625 //----------------------------------------------------------------------------
626 // This method inserts spill code for AN operand whose LR was spilled.
627 // This method may be called several times for a single machine instruction
628 // if it contains many spilled operands. Each time it is called, it finds
629 // a register which is not live at that instruction and also which is not
630 // used by other spilled operands of the same instruction. Then it uses
631 // this register temporarily to accommodate the spilled value.
632 //----------------------------------------------------------------------------
634 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
635 MachineBasicBlock::iterator& MII,
636 MachineBasicBlock &MBB,
637 const unsigned OpNum) {
638 MachineInstr *MInst = *MII;
639 const BasicBlock *BB = MBB.getBasicBlock();
641 assert((! TM.getInstrInfo().isCall(MInst->getOpCode()) || OpNum == 0) &&
642 "Outgoing arg of a call must be handled elsewhere (func arg ok)");
643 assert(! TM.getInstrInfo().isReturn(MInst->getOpCode()) &&
644 "Return value of a ret must be handled elsewhere");
646 MachineOperand& Op = MInst->getOperand(OpNum);
647 bool isDef = Op.opIsDefOnly();
648 bool isDefAndUse = Op.opIsDefAndUse();
649 unsigned RegType = MRI.getRegTypeForLR(LR);
650 int SpillOff = LR->getSpillOffFromFP();
651 RegClass *RC = LR->getRegClass();
653 // Get the live-variable set to find registers free before this instr.
654 const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
657 // If this instr. is in the delay slot of a branch or return, we need to
658 // include all live variables before that branch or return -- we don't want to
659 // trample those! Verify that the set is included in the LV set before MInst.
660 if (MII != MBB.begin()) {
661 MachineInstr *PredMI = *(MII-1);
662 if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(PredMI->getOpCode()))
663 assert(set_difference(LVI->getLiveVarSetBeforeMInst(PredMI), LVSetBef)
664 .empty() && "Live-var set before branch should be included in "
665 "live-var set of each delay slot instruction!");
669 MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType) );
671 std::vector<MachineInstr*> MIBef, MIAft;
672 std::vector<MachineInstr*> AdIMid;
674 // Choose a register to hold the spilled value, if one was not preallocated.
675 // This may insert code before and after MInst to free up the value. If so,
676 // this code should be first/last in the spill sequence before/after MInst.
677 int TmpRegU=(LR->hasColor()
678 ? MRI.getUnifiedRegNum(LR->getRegClass()->getID(),LR->getColor())
679 : getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef,MIAft));
681 // Set the operand first so that it this register does not get used
682 // as a scratch register for later calls to getUsableUniRegAtMI below
683 MInst->SetRegForOperand(OpNum, TmpRegU);
685 // get the added instructions for this instruction
686 AddedInstrns &AI = AddedInstrMap[MInst];
688 // We may need a scratch register to copy the spilled value to/from memory.
689 // This may itself have to insert code to free up a scratch register.
690 // Any such code should go before (after) the spill code for a load (store).
691 // The scratch reg is not marked as used because it is only used
692 // for the copy and not used across MInst.
693 int scratchRegType = -1;
695 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
697 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
698 MInst, MIBef, MIAft);
699 assert(scratchReg != MRI.getInvalidRegNum());
702 if (!isDef || isDefAndUse) {
703 // for a USE, we have to load the value of LR from stack to a TmpReg
704 // and use the TmpReg as one operand of instruction
706 // actual loading instruction(s)
707 MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU,
708 RegType, scratchReg);
710 // the actual load should be after the instructions to free up TmpRegU
711 MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
715 if (isDef || isDefAndUse) { // if this is a Def
716 // for a DEF, we have to store the value produced by this instruction
717 // on the stack position allocated for this LR
719 // actual storing instruction(s)
720 MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff,
721 RegType, scratchReg);
723 MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
726 // Finally, insert the entire spill code sequences before/after MInst
727 AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
728 AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
731 std::cerr << "\nFor Inst:\n " << *MInst;
732 std::cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex();
733 std::cerr << "; added Instructions:";
734 for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump));
735 for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump));
740 //----------------------------------------------------------------------------
741 // This method inserts caller saving/restoring instructions before/after
742 // a call machine instruction. The caller saving/restoring instructions are
744 // ** caller saving instructions
745 // other instructions inserted for the call by ColorCallArg
747 // other instructions inserted for the call ColorCallArg
748 // ** caller restoring instructions
749 //----------------------------------------------------------------------------
752 PhyRegAlloc::insertCallerSavingCode(std::vector<MachineInstr*> &instrnsBefore,
753 std::vector<MachineInstr*> &instrnsAfter,
754 MachineInstr *CallMI,
755 const BasicBlock *BB)
757 assert(TM.getInstrInfo().isCall(CallMI->getOpCode()));
759 // hash set to record which registers were saved/restored
760 hash_set<unsigned> PushedRegSet;
762 CallArgsDescriptor* argDesc = CallArgsDescriptor::get(CallMI);
764 // if the call is to a instrumentation function, do not insert save and
765 // restore instructions the instrumentation function takes care of save
766 // restore for volatile regs.
768 // FIXME: this should be made general, not specific to the reoptimizer!
769 const Function *Callee = argDesc->getCallInst()->getCalledFunction();
770 bool isLLVMFirstTrigger = Callee && Callee->getName() == "llvm_first_trigger";
772 // Now check if the call has a return value (using argDesc) and if so,
773 // find the LR of the TmpInstruction representing the return value register.
774 // (using the last or second-last *implicit operand* of the call MI).
775 // Insert it to to the PushedRegSet since we must not save that register
776 // and restore it after the call.
777 // We do this because, we look at the LV set *after* the instruction
778 // to determine, which LRs must be saved across calls. The return value
779 // of the call is live in this set - but we must not save/restore it.
780 if (const Value *origRetVal = argDesc->getReturnValue()) {
781 unsigned retValRefNum = (CallMI->getNumImplicitRefs() -
782 (argDesc->getIndirectFuncPtr()? 1 : 2));
783 const TmpInstruction* tmpRetVal =
784 cast<TmpInstruction>(CallMI->getImplicitRef(retValRefNum));
785 assert(tmpRetVal->getOperand(0) == origRetVal &&
786 tmpRetVal->getType() == origRetVal->getType() &&
787 "Wrong implicit ref?");
788 LiveRange *RetValLR = LRI->getLiveRangeForValue(tmpRetVal);
789 assert(RetValLR && "No LR for RetValue of call");
791 if (! RetValLR->isMarkedForSpill())
792 PushedRegSet.insert(MRI.getUnifiedRegNum(RetValLR->getRegClassID(),
793 RetValLR->getColor()));
796 const ValueSet &LVSetAft = LVI->getLiveVarSetAfterMInst(CallMI, BB);
797 ValueSet::const_iterator LIt = LVSetAft.begin();
799 // for each live var in live variable set after machine inst
800 for( ; LIt != LVSetAft.end(); ++LIt) {
801 // get the live range corresponding to live var
802 LiveRange *const LR = LRI->getLiveRangeForValue(*LIt);
804 // LR can be null if it is a const since a const
805 // doesn't have a dominating def - see Assumptions above
807 if(! LR->isMarkedForSpill()) {
808 assert(LR->hasColor() && "LR is neither spilled nor colored?");
809 unsigned RCID = LR->getRegClassID();
810 unsigned Color = LR->getColor();
812 if (MRI.isRegVolatile(RCID, Color) ) {
813 // if this is a call to the first-level reoptimizer
814 // instrumentation entry point, and the register is not
815 // modified by call, don't save and restore it.
816 if (isLLVMFirstTrigger && !MRI.modifiedByCall(RCID, Color))
819 // if the value is in both LV sets (i.e., live before and after
820 // the call machine instruction)
821 unsigned Reg = MRI.getUnifiedRegNum(RCID, Color);
823 // if we haven't already pushed this register...
824 if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
825 unsigned RegType = MRI.getRegTypeForLR(LR);
827 // Now get two instructions - to push on stack and pop from stack
828 // and add them to InstrnsBefore and InstrnsAfter of the
831 MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType));
833 //---- Insert code for pushing the reg on stack ----------
835 std::vector<MachineInstr*> AdIBef, AdIAft;
837 // We may need a scratch register to copy the saved value
838 // to/from memory. This may itself have to insert code to
839 // free up a scratch register. Any such code should go before
840 // the save code. The scratch register, if any, is by default
841 // temporary and not "used" by the instruction unless the
842 // copy code itself decides to keep the value in the scratch reg.
843 int scratchRegType = -1;
845 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
846 { // Find a register not live in the LVSet before CallMI
847 const ValueSet &LVSetBef =
848 LVI->getLiveVarSetBeforeMInst(CallMI, BB);
849 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
850 CallMI, AdIBef, AdIAft);
851 assert(scratchReg != MRI.getInvalidRegNum());
854 if (AdIBef.size() > 0)
855 instrnsBefore.insert(instrnsBefore.end(),
856 AdIBef.begin(), AdIBef.end());
858 MRI.cpReg2MemMI(instrnsBefore, Reg, MRI.getFramePointer(),
859 StackOff, RegType, scratchReg);
861 if (AdIAft.size() > 0)
862 instrnsBefore.insert(instrnsBefore.end(),
863 AdIAft.begin(), AdIAft.end());
865 //---- Insert code for popping the reg from the stack ----------
869 // We may need a scratch register to copy the saved value
870 // from memory. This may itself have to insert code to
871 // free up a scratch register. Any such code should go
872 // after the save code. As above, scratch is not marked "used".
875 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
876 { // Find a register not live in the LVSet after CallMI
877 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetAft,
878 CallMI, AdIBef, AdIAft);
879 assert(scratchReg != MRI.getInvalidRegNum());
882 if (AdIBef.size() > 0)
883 instrnsAfter.insert(instrnsAfter.end(),
884 AdIBef.begin(), AdIBef.end());
886 MRI.cpMem2RegMI(instrnsAfter, MRI.getFramePointer(), StackOff,
887 Reg, RegType, scratchReg);
889 if (AdIAft.size() > 0)
890 instrnsAfter.insert(instrnsAfter.end(),
891 AdIAft.begin(), AdIAft.end());
893 PushedRegSet.insert(Reg);
896 std::cerr << "\nFor call inst:" << *CallMI;
897 std::cerr << " -inserted caller saving instrs: Before:\n\t ";
898 for_each(instrnsBefore.begin(), instrnsBefore.end(),
899 std::mem_fun(&MachineInstr::dump));
900 std::cerr << " -and After:\n\t ";
901 for_each(instrnsAfter.begin(), instrnsAfter.end(),
902 std::mem_fun(&MachineInstr::dump));
904 } // if not already pushed
905 } // if LR has a volatile color
907 } // if there is a LR for Var
908 } // for each value in the LV set after instruction
912 //----------------------------------------------------------------------------
913 // We can use the following method to get a temporary register to be used
914 // BEFORE any given machine instruction. If there is a register available,
915 // this method will simply return that register and set MIBef = MIAft = NULL.
916 // Otherwise, it will return a register and MIAft and MIBef will contain
917 // two instructions used to free up this returned register.
918 // Returned register number is the UNIFIED register number
919 //----------------------------------------------------------------------------
921 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
922 const ValueSet *LVSetBef,
924 std::vector<MachineInstr*>& MIBef,
925 std::vector<MachineInstr*>& MIAft) {
926 RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
928 int RegU = getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef);
931 // we couldn't find an unused register. Generate code to free up a reg by
932 // saving it on stack and restoring after the instruction
934 int TmpOff = MF->getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType));
936 RegU = getUniRegNotUsedByThisInst(RC, RegType, MInst);
938 // Check if we need a scratch register to copy this register to memory.
939 int scratchRegType = -1;
940 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
942 int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef,
943 MInst, MIBef, MIAft);
944 assert(scratchReg != MRI.getInvalidRegNum());
946 // We may as well hold the value in the scratch register instead
947 // of copying it to memory and back. But we have to mark the
948 // register as used by this instruction, so it does not get used
949 // as a scratch reg. by another operand or anyone else.
950 ScratchRegsUsed.insert(std::make_pair(MInst, scratchReg));
951 MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
952 MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
955 { // the register can be copied directly to/from memory so do it.
956 MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
957 MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
965 //----------------------------------------------------------------------------
966 // This method is called to get a new unused register that can be used
967 // to accommodate a temporary value. This method may be called several times
968 // for a single machine instruction. Each time it is called, it finds a
969 // register which is not live at that instruction and also which is not used
970 // by other spilled operands of the same instruction. Return register number
971 // is relative to the register class, NOT the unified number.
972 //----------------------------------------------------------------------------
974 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
976 const MachineInstr *MInst,
977 const ValueSet* LVSetBef) {
978 RC->clearColorsUsed(); // Reset array
980 if (LVSetBef == NULL) {
981 LVSetBef = &LVI->getLiveVarSetBeforeMInst(MInst);
982 assert(LVSetBef != NULL && "Unable to get live-var set before MInst?");
985 ValueSet::const_iterator LIt = LVSetBef->begin();
987 // for each live var in live variable set after machine inst
988 for ( ; LIt != LVSetBef->end(); ++LIt) {
989 // Get the live range corresponding to live var, and its RegClass
990 LiveRange *const LRofLV = LRI->getLiveRangeForValue(*LIt );
992 // LR can be null if it is a const since a const
993 // doesn't have a dominating def - see Assumptions above
994 if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor())
995 RC->markColorsUsed(LRofLV->getColor(),
996 MRI.getRegTypeForLR(LRofLV), RegType);
999 // It is possible that one operand of this MInst was already spilled
1000 // and it received some register temporarily. If that's the case,
1001 // it is recorded in machine operand. We must skip such registers.
1002 setRelRegsUsedByThisInst(RC, RegType, MInst);
1004 int unusedReg = RC->getUnusedColor(RegType); // find first unused color
1006 return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
1012 //----------------------------------------------------------------------------
1013 // Get any other register in a register class, other than what is used
1014 // by operands of a machine instruction. Returns the unified reg number.
1015 //----------------------------------------------------------------------------
1017 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
1019 const MachineInstr *MInst) {
1020 RC->clearColorsUsed();
1022 setRelRegsUsedByThisInst(RC, RegType, MInst);
1024 // find the first unused color
1025 int unusedReg = RC->getUnusedColor(RegType);
1026 assert(unusedReg >= 0 &&
1027 "FATAL: No free register could be found in reg class!!");
1029 return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
1033 //----------------------------------------------------------------------------
1034 // This method modifies the IsColorUsedArr of the register class passed to it.
1035 // It sets the bits corresponding to the registers used by this machine
1036 // instructions. Both explicit and implicit operands are set.
1037 //----------------------------------------------------------------------------
1039 static void markRegisterUsed(int RegNo, RegClass *RC, int RegType,
1040 const TargetRegInfo &TRI) {
1041 unsigned classId = 0;
1042 int classRegNum = TRI.getClassRegNum(RegNo, classId);
1043 if (RC->getID() == classId)
1044 RC->markColorsUsed(classRegNum, RegType, RegType);
1047 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, int RegType,
1048 const MachineInstr *MI)
1050 assert(OperandsColoredMap[MI] == true &&
1051 "Illegal to call setRelRegsUsedByThisInst() until colored operands "
1052 "are marked for an instruction.");
1054 // Add the registers already marked as used by the instruction.
1055 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
1056 if (MI->getOperand(i).hasAllocatedReg())
1057 markRegisterUsed(MI->getOperand(i).getAllocatedRegNum(), RC, RegType,MRI);
1059 for (unsigned i = 0, e = MI->getNumImplicitRefs(); i != e; ++i)
1060 if (MI->getImplicitOp(i).hasAllocatedReg())
1061 markRegisterUsed(MI->getImplicitOp(i).getAllocatedRegNum(), RC,
1064 // Add all of the scratch registers that are used to save values across the
1065 // instruction (e.g., for saving state register values).
1066 std::pair<ScratchRegsUsedTy::iterator, ScratchRegsUsedTy::iterator>
1067 IR = ScratchRegsUsed.equal_range(MI);
1068 for (ScratchRegsUsedTy::iterator I = IR.first; I != IR.second; ++I)
1069 markRegisterUsed(I->second, RC, RegType, MRI);
1071 // If there are implicit references, mark their allocated regs as well
1072 for (unsigned z=0; z < MI->getNumImplicitRefs(); z++)
1073 if (const LiveRange*
1074 LRofImpRef = LRI->getLiveRangeForValue(MI->getImplicitRef(z)))
1075 if (LRofImpRef->hasColor())
1076 // this implicit reference is in a LR that received a color
1077 RC->markColorsUsed(LRofImpRef->getColor(),
1078 MRI.getRegTypeForLR(LRofImpRef), RegType);
1082 //----------------------------------------------------------------------------
1083 // If there are delay slots for an instruction, the instructions
1084 // added after it must really go after the delayed instruction(s).
1085 // So, we move the InstrAfter of that instruction to the
1086 // corresponding delayed instruction using the following method.
1087 //----------------------------------------------------------------------------
1089 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
1090 const MachineInstr *DelayedMI)
1092 // "added after" instructions of the original instr
1093 std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
1095 if (DEBUG_RA && OrigAft.size() > 0) {
1096 std::cerr << "\nRegAlloc: Moved InstrnsAfter for: " << *OrigMI;
1097 std::cerr << " to last delay slot instrn: " << *DelayedMI;
1100 // "added after" instructions of the delayed instr
1101 std::vector<MachineInstr *> &DelayedAft=AddedInstrMap[DelayedMI].InstrnsAfter;
1103 // go thru all the "added after instructions" of the original instruction
1104 // and append them to the "added after instructions" of the delayed
1106 DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
1108 // empty the "added after instructions" of the original instruction
1113 void PhyRegAlloc::colorIncomingArgs()
1115 MRI.colorMethodArgs(Fn, *LRI, AddedInstrAtEntry.InstrnsBefore,
1116 AddedInstrAtEntry.InstrnsAfter);
1120 //----------------------------------------------------------------------------
1121 // This method calls setSugColorUsable method of each live range. This
1122 // will determine whether the suggested color of LR is really usable.
1123 // A suggested color is not usable when the suggested color is volatile
1124 // AND when there are call interferences
1125 //----------------------------------------------------------------------------
1127 void PhyRegAlloc::markUnusableSugColors()
1129 LiveRangeMapType::const_iterator HMI = (LRI->getLiveRangeMap())->begin();
1130 LiveRangeMapType::const_iterator HMIEnd = (LRI->getLiveRangeMap())->end();
1132 for (; HMI != HMIEnd ; ++HMI ) {
1134 LiveRange *L = HMI->second; // get the LiveRange
1136 if (L->hasSuggestedColor()) {
1137 int RCID = L->getRegClass()->getID();
1138 if (MRI.isRegVolatile( RCID, L->getSuggestedColor()) &&
1139 L->isCallInterference() )
1140 L->setSuggestedColorUsable( false );
1142 L->setSuggestedColorUsable( true );
1144 } // if L->hasSuggestedColor()
1146 } // for all LR's in hash map
1150 //----------------------------------------------------------------------------
1151 // The following method will set the stack offsets of the live ranges that
1152 // are decided to be spilled. This must be called just after coloring the
1153 // LRs using the graph coloring algo. For each live range that is spilled,
1154 // this method allocate a new spill position on the stack.
1155 //----------------------------------------------------------------------------
1157 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1158 if (DEBUG_RA) std::cerr << "\nSetting LR stack offsets for spills...\n";
1160 LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin();
1161 LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end();
1163 for ( ; HMI != HMIEnd ; ++HMI) {
1164 if (HMI->first && HMI->second) {
1165 LiveRange *L = HMI->second; // get the LiveRange
1166 if (L->isMarkedForSpill()) { // NOTE: allocating size of long Type **
1167 int stackOffset = MF->getInfo()->allocateSpilledValue(Type::LongTy);
1168 L->setSpillOffFromFP(stackOffset);
1170 std::cerr << " LR# " << L->getUserIGNode()->getIndex()
1171 << ": stack-offset = " << stackOffset << "\n";
1174 } // for all LR's in hash map
1178 //----------------------------------------------------------------------------
1179 // The entry point to Register Allocation
1180 //----------------------------------------------------------------------------
1182 bool PhyRegAlloc::runOnFunction (Function &F) {
1184 std::cerr << "\n********* Function "<< F.getName () << " ***********\n";
1187 MF = &MachineFunction::get (Fn);
1188 LVI = &getAnalysis<FunctionLiveVarInfo> ();
1189 LRI = new LiveRangeInfo (Fn, TM, RegClassList);
1190 LoopDepthCalc = &getAnalysis<LoopInfo> ();
1192 // Create each RegClass for the target machine and add it to the
1193 // RegClassList. This must be done before calling constructLiveRanges().
1194 for (unsigned rc = 0; rc != NumOfRegClasses; ++rc)
1195 RegClassList.push_back (new RegClass (Fn, &TM.getRegInfo (),
1196 MRI.getMachineRegClass (rc)));
1198 LRI->constructLiveRanges(); // create LR info
1199 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
1200 LRI->printLiveRanges();
1202 createIGNodeListsAndIGs(); // create IGNode list and IGs
1204 buildInterferenceGraphs(); // build IGs in all reg classes
1206 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
1207 // print all LRs in all reg classes
1208 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1209 RegClassList[rc]->printIGNodeList();
1211 // print IGs in all register classes
1212 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1213 RegClassList[rc]->printIG();
1216 LRI->coalesceLRs(); // coalesce all live ranges
1218 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
1219 // print all LRs in all reg classes
1220 for (unsigned rc=0; rc < NumOfRegClasses; rc++)
1221 RegClassList[rc]->printIGNodeList();
1223 // print IGs in all register classes
1224 for (unsigned rc=0; rc < NumOfRegClasses; rc++)
1225 RegClassList[rc]->printIG();
1228 // mark un-usable suggested color before graph coloring algorithm.
1229 // When this is done, the graph coloring algo will not reserve
1230 // suggested color unnecessarily - they can be used by another LR
1231 markUnusableSugColors();
1233 // color all register classes using the graph coloring algo
1234 for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
1235 RegClassList[rc]->colorAllRegs();
1237 // After graph coloring, if some LRs did not receive a color (i.e, spilled)
1238 // a position for such spilled LRs
1239 allocateStackSpace4SpilledLRs();
1241 // Reset the temp. area on the stack before use by the first instruction.
1242 // This will also happen after updating each instruction.
1243 MF->getInfo()->popAllTempValues();
1245 // color incoming args - if the correct color was not received
1246 // insert code to copy to the correct register
1247 colorIncomingArgs();
1249 // Now update the machine code with register names and add any
1250 // additional code inserted by the register allocator to the instruction
1252 updateMachineCode();
1255 std::cerr << "\n**** Machine Code After Register Allocation:\n\n";
1259 // Tear down temporary data structures
1260 for (unsigned rc = 0; rc < NumOfRegClasses; ++rc)
1261 delete RegClassList[rc];
1262 RegClassList.clear ();
1263 AddedInstrMap.clear ();
1264 OperandsColoredMap.clear ();
1265 ScratchRegsUsed.clear ();
1266 AddedInstrAtEntry.clear ();
1269 if (DEBUG_RA) std::cerr << "\nRegister allocation complete!\n";
1270 return false; // Function was not modified