1 //***************************************************************************
6 // Register allocation for LLVM.
9 // 9/10/01 - Ruchira Sasanka - created.
10 //**************************************************************************/
12 #include "llvm/CodeGen/RegisterAllocation.h"
13 #include "llvm/CodeGen/PhyRegAlloc.h"
14 #include "llvm/CodeGen/MachineInstr.h"
15 #include "llvm/CodeGen/MachineInstrAnnot.h"
16 #include "llvm/CodeGen/MachineCodeForBasicBlock.h"
17 #include "llvm/CodeGen/MachineCodeForMethod.h"
18 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/Target/TargetMachine.h"
21 #include "llvm/Target/MachineFrameInfo.h"
22 #include "llvm/BasicBlock.h"
23 #include "llvm/Function.h"
24 #include "llvm/Type.h"
25 #include "llvm/iOther.h"
26 #include "llvm/CodeGen/RegAllocCommon.h"
27 #include "Support/CommandLine.h"
28 #include "Support/STLExtras.h"
34 RegAllocDebugLevel_t DEBUG_RA;
35 static cl::Enum<RegAllocDebugLevel_t> DEBUG_RA_c(DEBUG_RA, "dregalloc",
37 "enable register allocation debugging information",
38 clEnumValN(RA_DEBUG_None , "n", "disable debug output"),
39 clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
40 clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
43 //----------------------------------------------------------------------------
44 // RegisterAllocation pass front end...
45 //----------------------------------------------------------------------------
47 class RegisterAllocator : public FunctionPass {
48 TargetMachine &Target;
50 inline RegisterAllocator(TargetMachine &T) : Target(T) {}
52 const char *getPassName() const { return "Register Allocation"; }
54 bool runOnFunction(Function &F) {
56 cerr << "\n********* Function "<< F.getName() << " ***********\n";
58 PhyRegAlloc PRA(&F, Target, &getAnalysis<FunctionLiveVarInfo>(),
59 &getAnalysis<LoopInfo>());
60 PRA.allocateRegisters();
62 if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
66 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
67 AU.addRequired(LoopInfo::ID);
68 AU.addRequired(FunctionLiveVarInfo::ID);
73 Pass *getRegisterAllocator(TargetMachine &T) {
74 return new RegisterAllocator(T);
77 //----------------------------------------------------------------------------
78 // Constructor: Init local composite objects and create register classes.
79 //----------------------------------------------------------------------------
80 PhyRegAlloc::PhyRegAlloc(Function *F, const TargetMachine& tm,
81 FunctionLiveVarInfo *Lvi, LoopInfo *LDC)
83 mcInfo(MachineCodeForMethod::get(F)),
84 LVI(Lvi), LRI(F, tm, RegClassList),
86 NumOfRegClasses(MRI.getNumOfRegClasses()),
89 // create each RegisterClass and put in RegClassList
91 for (unsigned rc=0; rc < NumOfRegClasses; rc++)
92 RegClassList.push_back(new RegClass(F, MRI.getMachineRegClass(rc),
97 //----------------------------------------------------------------------------
98 // Destructor: Deletes register classes
99 //----------------------------------------------------------------------------
100 PhyRegAlloc::~PhyRegAlloc() {
101 for ( unsigned rc=0; rc < NumOfRegClasses; rc++)
102 delete RegClassList[rc];
104 AddedInstrMap.clear();
107 //----------------------------------------------------------------------------
108 // This method initally creates interference graphs (one in each reg class)
109 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
110 //----------------------------------------------------------------------------
111 void PhyRegAlloc::createIGNodeListsAndIGs() {
112 if (DEBUG_RA) cerr << "Creating LR lists ...\n";
115 LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin();
118 LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
120 for (; HMI != HMIEnd ; ++HMI ) {
122 LiveRange *L = HMI->second; // get the LiveRange
125 cerr << "\n*?!?Warning: Null liver range found for: "
126 << RAV(HMI->first) << "\n";
130 // if the Value * is not null, and LR
131 // is not yet written to the IGNodeList
132 if (!(L->getUserIGNode()) ) {
133 RegClass *const RC = // RegClass of first value in the LR
134 RegClassList[ L->getRegClass()->getID() ];
136 RC->addLRToIG(L); // add this LR to an IG
142 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
143 RegClassList[rc]->createInterferenceGraph();
146 cerr << "LRLists Created!\n";
152 //----------------------------------------------------------------------------
153 // This method will add all interferences at for a given instruction.
154 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
155 // class as that of live var. The live var passed to this function is the
156 // LVset AFTER the instruction
157 //----------------------------------------------------------------------------
158 void PhyRegAlloc::addInterference(const Value *Def,
159 const ValueSet *LVSet,
162 ValueSet::const_iterator LIt = LVSet->begin();
164 // get the live range of instruction
166 const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
168 IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
169 assert( IGNodeOfDef );
171 RegClass *const RCOfDef = LROfDef->getRegClass();
173 // for each live var in live variable set
175 for ( ; LIt != LVSet->end(); ++LIt) {
177 if (DEBUG_RA >= RA_DEBUG_Verbose)
178 cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> ";
180 // get the live range corresponding to live var
182 LiveRange *LROfVar = LRI.getLiveRangeForValue(*LIt);
184 // LROfVar can be null if it is a const since a const
185 // doesn't have a dominating def - see Assumptions above
188 if (LROfDef == LROfVar) // do not set interf for same LR
191 // if 2 reg classes are the same set interference
193 if (RCOfDef == LROfVar->getRegClass()) {
194 RCOfDef->setInterference( LROfDef, LROfVar);
195 } else if (DEBUG_RA >= RA_DEBUG_Verbose) {
196 // we will not have LRs for values not explicitly allocated in the
197 // instruction stream (e.g., constants)
198 cerr << " warning: no live range for " << RAV(*LIt) << "\n";
206 //----------------------------------------------------------------------------
207 // For a call instruction, this method sets the CallInterference flag in
208 // the LR of each variable live int the Live Variable Set live after the
209 // call instruction (except the return value of the call instruction - since
210 // the return value does not interfere with that call itself).
211 //----------------------------------------------------------------------------
213 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
214 const ValueSet *LVSetAft) {
217 cerr << "\n For call inst: " << *MInst;
219 ValueSet::const_iterator LIt = LVSetAft->begin();
221 // for each live var in live variable set after machine inst
223 for ( ; LIt != LVSetAft->end(); ++LIt) {
225 // get the live range corresponding to live var
227 LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
229 if (LR && DEBUG_RA) {
230 cerr << "\n\tLR Aft Call: ";
234 // LR can be null if it is a const since a const
235 // doesn't have a dominating def - see Assumptions above
238 LR->setCallInterference();
240 cerr << "\n ++Added call interf for LR: " ;
247 // Now find the LR of the return value of the call
248 // We do this because, we look at the LV set *after* the instruction
249 // to determine, which LRs must be saved across calls. The return value
250 // of the call is live in this set - but it does not interfere with call
251 // (i.e., we can allocate a volatile register to the return value)
253 CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
255 if (const Value *RetVal = argDesc->getReturnValue()) {
256 LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
257 assert( RetValLR && "No LR for RetValue of call");
258 RetValLR->clearCallInterference();
261 // If the CALL is an indirect call, find the LR of the function pointer.
262 // That has a call interference because it conflicts with outgoing args.
263 if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
264 LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal );
265 assert( AddrValLR && "No LR for indirect addr val of call");
266 AddrValLR->setCallInterference();
274 //----------------------------------------------------------------------------
275 // This method will walk thru code and create interferences in the IG of
276 // each RegClass. Also, this method calculates the spill cost of each
277 // Live Range (it is done in this method to save another pass over the code).
278 //----------------------------------------------------------------------------
279 void PhyRegAlloc::buildInterferenceGraphs()
282 if (DEBUG_RA) cerr << "Creating interference graphs ...\n";
284 unsigned BBLoopDepthCost;
285 for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
288 // find the 10^(loop_depth) of this BB
290 BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BBI));
292 // get the iterator for machine instructions
294 const MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
295 MachineCodeForBasicBlock::const_iterator MII = MIVec.begin();
297 // iterate over all the machine instructions in BB
299 for ( ; MII != MIVec.end(); ++MII) {
301 const MachineInstr *MInst = *MII;
303 // get the LV set after the instruction
305 const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BBI);
307 const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
310 // set the isCallInterference flag of each live range wich extends
311 // accross this call instruction. This information is used by graph
312 // coloring algo to avoid allocating volatile colors to live ranges
313 // that span across calls (since they have to be saved/restored)
315 setCallInterferences(MInst, &LVSetAI);
319 // iterate over all MI operands to find defs
321 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
322 OpE = MInst->end(); OpI != OpE; ++OpI) {
323 if (OpI.isDef()) // create a new LR iff this operand is a def
324 addInterference(*OpI, &LVSetAI, isCallInst);
326 // Calculate the spill cost of each live range
328 LiveRange *LR = LRI.getLiveRangeForValue(*OpI);
329 if (LR) LR->addSpillCost(BBLoopDepthCost);
333 // if there are multiple defs in this instruction e.g. in SETX
335 if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
336 addInterf4PseudoInstr(MInst);
339 // Also add interference for any implicit definitions in a machine
340 // instr (currently, only calls have this).
342 unsigned NumOfImpRefs = MInst->getNumImplicitRefs();
343 if ( NumOfImpRefs > 0 ) {
344 for (unsigned z=0; z < NumOfImpRefs; z++)
345 if (MInst->implicitRefIsDefined(z) )
346 addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
350 } // for all machine instructions in BB
351 } // for all BBs in function
354 // add interferences for function arguments. Since there are no explict
355 // defs in the function for args, we have to add them manually
357 addInterferencesForArgs();
360 cerr << "Interference graphs calculted!\n";
366 //--------------------------------------------------------------------------
367 // Pseudo instructions will be exapnded to multiple instructions by the
368 // assembler. Consequently, all the opernds must get distinct registers.
369 // Therefore, we mark all operands of a pseudo instruction as they interfere
371 //--------------------------------------------------------------------------
372 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
374 bool setInterf = false;
376 // iterate over MI operands to find defs
378 for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
379 ItE = MInst->end(); It1 != ItE; ++It1) {
380 const LiveRange *LROfOp1 = LRI.getLiveRangeForValue(*It1);
381 assert((LROfOp1 || !It1.isDef()) && "No LR for Def in PSEUDO insruction");
383 MachineInstr::const_val_op_iterator It2 = It1;
384 for (++It2; It2 != ItE; ++It2) {
385 const LiveRange *LROfOp2 = LRI.getLiveRangeForValue(*It2);
388 RegClass *RCOfOp1 = LROfOp1->getRegClass();
389 RegClass *RCOfOp2 = LROfOp2->getRegClass();
391 if (RCOfOp1 == RCOfOp2 ){
392 RCOfOp1->setInterference( LROfOp1, LROfOp2 );
396 } // for all other defs in machine instr
397 } // for all operands in an instruction
399 if (!setInterf && MInst->getNumOperands() > 2) {
400 cerr << "\nInterf not set for any operand in pseudo instr:\n";
402 assert(0 && "Interf not set for pseudo instr with > 2 operands" );
408 //----------------------------------------------------------------------------
409 // This method will add interferences for incoming arguments to a function.
410 //----------------------------------------------------------------------------
411 void PhyRegAlloc::addInterferencesForArgs() {
412 // get the InSet of root BB
413 const ValueSet &InSet = LVI->getInSetOfBB(&Meth->front());
415 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI) {
416 // add interferences between args and LVars at start
417 addInterference(AI, &InSet, false);
419 if (DEBUG_RA >= RA_DEBUG_Verbose)
420 cerr << " - %% adding interference for argument " << RAV(AI) << "\n";
425 //----------------------------------------------------------------------------
426 // This method is called after register allocation is complete to set the
427 // allocated reisters in the machine code. This code will add register numbers
428 // to MachineOperands that contain a Value. Also it calls target specific
429 // methods to produce caller saving instructions. At the end, it adds all
430 // additional instructions produced by the register allocator to the
431 // instruction stream.
432 //----------------------------------------------------------------------------
434 //-----------------------------
435 // Utility functions used below
436 //-----------------------------
438 PrependInstructions(vector<MachineInstr *> &IBef,
439 MachineCodeForBasicBlock& MIVec,
440 MachineCodeForBasicBlock::iterator& MII,
441 const std::string& msg)
445 MachineInstr* OrigMI = *MII;
446 std::vector<MachineInstr *>::iterator AdIt;
447 for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
450 if (OrigMI) cerr << "For MInst: " << *OrigMI;
451 cerr << msg << " PREPENDed instr: " << **AdIt << "\n";
453 MII = MIVec.insert(MII, *AdIt);
460 AppendInstructions(std::vector<MachineInstr *> &IAft,
461 MachineCodeForBasicBlock& MIVec,
462 MachineCodeForBasicBlock::iterator& MII,
463 const std::string& msg)
467 MachineInstr* OrigMI = *MII;
468 std::vector<MachineInstr *>::iterator AdIt;
469 for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
472 if (OrigMI) cerr << "For MInst: " << *OrigMI;
473 cerr << msg << " APPENDed instr: " << **AdIt << "\n";
475 ++MII; // insert before the next instruction
476 MII = MIVec.insert(MII, *AdIt);
482 void PhyRegAlloc::updateMachineCode()
484 MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(&Meth->getEntryNode());
486 // Insert any instructions needed at method entry
487 MachineCodeForBasicBlock::iterator MII = MIVec.begin();
488 PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MIVec, MII,
489 "At function entry: \n");
490 assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
491 "InstrsAfter should be unnecessary since we are just inserting at "
492 "the function entry point here.");
494 for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
497 // iterate over all the machine instructions in BB
498 MachineCodeForBasicBlock &MIVec = MachineCodeForBasicBlock::get(BBI);
499 for (MachineCodeForBasicBlock::iterator MII = MIVec.begin();
500 MII != MIVec.end(); ++MII) {
502 MachineInstr *MInst = *MII;
504 unsigned Opcode = MInst->getOpCode();
506 // do not process Phis
507 if (TM.getInstrInfo().isDummyPhiInstr(Opcode))
510 // Reset tmp stack positions so they can be reused for each machine instr.
511 mcInfo.popAllTempValues(TM);
513 // Now insert speical instructions (if necessary) for call/return
516 if (TM.getInstrInfo().isCall(Opcode) ||
517 TM.getInstrInfo().isReturn(Opcode)) {
519 AddedInstrns &AI = AddedInstrMap[MInst];
521 if (TM.getInstrInfo().isCall(Opcode))
522 MRI.colorCallArgs(MInst, LRI, &AI, *this, BBI);
523 else if (TM.getInstrInfo().isReturn(Opcode))
524 MRI.colorRetValue(MInst, LRI, &AI);
527 // Set the registers for operands in the machine instruction
528 // if a register was successfully allocated. If not, insert
529 // code to spill the register value.
531 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
533 MachineOperand& Op = MInst->getOperand(OpNum);
534 if (Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
535 Op.getOperandType() == MachineOperand::MO_CCRegister)
537 const Value *const Val = Op.getVRegValue();
539 LiveRange *const LR = LRI.getLiveRangeForValue(Val);
540 if (!LR) // consts or labels will have no live range
542 // if register is not allocated, mark register as invalid
543 if (Op.getAllocatedRegNum() == -1)
544 MInst->SetRegForOperand(OpNum, MRI.getInvalidRegNum());
549 MInst->SetRegForOperand(OpNum,
550 MRI.getUnifiedRegNum(LR->getRegClass()->getID(),
553 // LR did NOT receive a color (register). Insert spill code.
554 insertCode4SpilledLR(LR, MInst, BBI, OpNum );
556 } // for each operand
559 // Now add instructions that the register allocator inserts before/after
560 // this machine instructions (done only for calls/rets/incoming args)
561 // We do this here, to ensure that spill for an instruction is inserted
562 // closest as possible to an instruction (see above insertCode4Spill...)
564 // If there are instructions to be added, *before* this machine
565 // instruction, add them now.
567 if (AddedInstrMap.count(MInst)) {
568 PrependInstructions(AddedInstrMap[MInst].InstrnsBefore, MIVec, MII,"");
571 // If there are instructions to be added *after* this machine
572 // instruction, add them now
574 if (!AddedInstrMap[MInst].InstrnsAfter.empty()) {
576 // if there are delay slots for this instruction, the instructions
577 // added after it must really go after the delayed instruction(s)
578 // So, we move the InstrAfter of the current instruction to the
579 // corresponding delayed instruction
582 if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
583 move2DelayedInstr(MInst, *(MII+delay) );
586 // Here we can add the "instructions after" to the current
587 // instruction since there are no delay slots for this instruction
588 AppendInstructions(AddedInstrMap[MInst].InstrnsAfter, MIVec, MII,"");
592 } // for each machine instruction
598 //----------------------------------------------------------------------------
599 // This method inserts spill code for AN operand whose LR was spilled.
600 // This method may be called several times for a single machine instruction
601 // if it contains many spilled operands. Each time it is called, it finds
602 // a register which is not live at that instruction and also which is not
603 // used by other spilled operands of the same instruction. Then it uses
604 // this register temporarily to accomodate the spilled value.
605 //----------------------------------------------------------------------------
606 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
608 const BasicBlock *BB,
609 const unsigned OpNum) {
611 assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
612 (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
613 "Arg of a call/ret must be handled elsewhere");
615 MachineOperand& Op = MInst->getOperand(OpNum);
616 bool isDef = MInst->operandIsDefined(OpNum);
617 bool isDefAndUse = MInst->operandIsDefinedAndUsed(OpNum);
618 unsigned RegType = MRI.getRegType( LR );
619 int SpillOff = LR->getSpillOffFromFP();
620 RegClass *RC = LR->getRegClass();
621 const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
623 mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
625 vector<MachineInstr*> MIBef, MIAft;
626 vector<MachineInstr*> AdIMid;
628 // Choose a register to hold the spilled value. This may insert code
629 // before and after MInst to free up the value. If so, this code should
630 // be first and last in the spill sequence before/after MInst.
631 int TmpRegU = getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef, MIAft);
633 // Set the operand first so that it this register does not get used
634 // as a scratch register for later calls to getUsableUniRegAtMI below
635 MInst->SetRegForOperand(OpNum, TmpRegU);
637 // get the added instructions for this instruction
638 AddedInstrns &AI = AddedInstrMap[MInst];
640 // We may need a scratch register to copy the spilled value to/from memory.
641 // This may itself have to insert code to free up a scratch register.
642 // Any such code should go before (after) the spill code for a load (store).
643 int scratchRegType = -1;
645 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
647 scratchReg = this->getUsableUniRegAtMI(scratchRegType, &LVSetBef,
648 MInst, MIBef, MIAft);
649 assert(scratchReg != MRI.getInvalidRegNum());
650 MInst->getRegsUsed().insert(scratchReg);
653 if (!isDef || isDefAndUse) {
654 // for a USE, we have to load the value of LR from stack to a TmpReg
655 // and use the TmpReg as one operand of instruction
657 // actual loading instruction(s)
658 MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, RegType,
661 // the actual load should be after the instructions to free up TmpRegU
662 MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
666 if (isDef) { // if this is a Def
667 // for a DEF, we have to store the value produced by this instruction
668 // on the stack position allocated for this LR
670 // actual storing instruction(s)
671 MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, RegType,
674 MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
677 // Finally, insert the entire spill code sequences before/after MInst
678 AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
679 AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
682 cerr << "\nFor Inst " << *MInst;
683 cerr << " - SPILLED LR: "; printSet(*LR);
684 cerr << "\n - Added Instructions:";
685 for_each(MIBef.begin(), MIBef.end(), mem_fun(&MachineInstr::dump));
686 for_each(MIAft.begin(), MIAft.end(), mem_fun(&MachineInstr::dump));
691 //----------------------------------------------------------------------------
692 // We can use the following method to get a temporary register to be used
693 // BEFORE any given machine instruction. If there is a register available,
694 // this method will simply return that register and set MIBef = MIAft = NULL.
695 // Otherwise, it will return a register and MIAft and MIBef will contain
696 // two instructions used to free up this returned register.
697 // Returned register number is the UNIFIED register number
698 //----------------------------------------------------------------------------
700 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
701 const ValueSet *LVSetBef,
703 std::vector<MachineInstr*>& MIBef,
704 std::vector<MachineInstr*>& MIAft) {
706 RegClass* RC = this->getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
708 int RegU = getUnusedUniRegAtMI(RC, MInst, LVSetBef);
711 // we couldn't find an unused register. Generate code to free up a reg by
712 // saving it on stack and restoring after the instruction
714 int TmpOff = mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
716 RegU = getUniRegNotUsedByThisInst(RC, MInst);
718 // Check if we need a scratch register to copy this register to memory.
719 int scratchRegType = -1;
720 if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
722 int scratchReg = this->getUsableUniRegAtMI(scratchRegType, LVSetBef,
723 MInst, MIBef, MIAft);
724 assert(scratchReg != MRI.getInvalidRegNum());
726 // We may as well hold the value in the scratch register instead
727 // of copying it to memory and back. But we have to mark the
728 // register as used by this instruction, so it does not get used
729 // as a scratch reg. by another operand or anyone else.
730 MInst->getRegsUsed().insert(scratchReg);
731 MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
732 MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
735 { // the register can be copied directly to/from memory so do it.
736 MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
737 MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
744 //----------------------------------------------------------------------------
745 // This method is called to get a new unused register that can be used to
746 // accomodate a spilled value.
747 // This method may be called several times for a single machine instruction
748 // if it contains many spilled operands. Each time it is called, it finds
749 // a register which is not live at that instruction and also which is not
750 // used by other spilled operands of the same instruction.
751 // Return register number is relative to the register class. NOT
753 //----------------------------------------------------------------------------
754 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
755 const MachineInstr *MInst,
756 const ValueSet *LVSetBef) {
758 unsigned NumAvailRegs = RC->getNumOfAvailRegs();
760 std::vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
762 for (unsigned i=0; i < NumAvailRegs; i++) // Reset array
763 IsColorUsedArr[i] = false;
765 ValueSet::const_iterator LIt = LVSetBef->begin();
767 // for each live var in live variable set after machine inst
768 for ( ; LIt != LVSetBef->end(); ++LIt) {
770 // get the live range corresponding to live var
771 LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
773 // LR can be null if it is a const since a const
774 // doesn't have a dominating def - see Assumptions above
775 if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor() )
776 IsColorUsedArr[ LRofLV->getColor() ] = true;
779 // It is possible that one operand of this MInst was already spilled
780 // and it received some register temporarily. If that's the case,
781 // it is recorded in machine operand. We must skip such registers.
783 setRelRegsUsedByThisInst(RC, MInst);
785 for (unsigned c=0; c < NumAvailRegs; c++) // find first unused color
786 if (!IsColorUsedArr[c])
787 return MRI.getUnifiedRegNum(RC->getID(), c);
793 //----------------------------------------------------------------------------
794 // Get any other register in a register class, other than what is used
795 // by operands of a machine instruction. Returns the unified reg number.
796 //----------------------------------------------------------------------------
797 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
798 const MachineInstr *MInst) {
800 vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
801 unsigned NumAvailRegs = RC->getNumOfAvailRegs();
803 for (unsigned i=0; i < NumAvailRegs ; i++) // Reset array
804 IsColorUsedArr[i] = false;
806 setRelRegsUsedByThisInst(RC, MInst);
808 for (unsigned c=0; c < RC->getNumOfAvailRegs(); c++)// find first unused color
809 if (!IsColorUsedArr[c])
810 return MRI.getUnifiedRegNum(RC->getID(), c);
812 assert(0 && "FATAL: No free register could be found in reg class!!");
817 //----------------------------------------------------------------------------
818 // This method modifies the IsColorUsedArr of the register class passed to it.
819 // It sets the bits corresponding to the registers used by this machine
820 // instructions. Both explicit and implicit operands are set.
821 //----------------------------------------------------------------------------
822 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
823 const MachineInstr *MInst ) {
825 vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
827 // Add the registers already marked as used by the instruction.
828 // This should include any scratch registers that are used to save
829 // values across the instruction (e.g., for saving state register values).
830 const hash_set<int>& regsUsed = MInst->getRegsUsed();
831 for (hash_set<int>::const_iterator SI=regsUsed.begin(), SE=regsUsed.end();
834 unsigned classId = 0;
835 int classRegNum = MRI.getClassRegNum(*SI, classId);
836 if (RC->getID() == classId)
838 assert(classRegNum < (int) IsColorUsedArr.size() &&
839 "Illegal register number for this reg class?");
840 IsColorUsedArr[classRegNum] = true;
844 // Now add registers allocated to the live ranges of values used in
845 // the instruction. These are not yet recorded in the instruction.
846 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
848 const MachineOperand& Op = MInst->getOperand(OpNum);
850 if (Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
851 Op.getOperandType() == MachineOperand::MO_CCRegister)
852 if (const Value* Val = Op.getVRegValue())
853 if (MRI.getRegClassIDOfValue(Val) == RC->getID())
854 if (Op.getAllocatedRegNum() == -1)
855 if (LiveRange *LROfVal = LRI.getLiveRangeForValue(Val))
856 if (LROfVal->hasColor() )
857 // this operand is in a LR that received a color
858 IsColorUsedArr[LROfVal->getColor()] = true;
861 // If there are implicit references, mark their allocated regs as well
863 for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++)
865 LRofImpRef = LRI.getLiveRangeForValue(MInst->getImplicitRef(z)))
866 if (LRofImpRef->hasColor())
867 // this implicit reference is in a LR that received a color
868 IsColorUsedArr[LRofImpRef->getColor()] = true;
872 //----------------------------------------------------------------------------
873 // If there are delay slots for an instruction, the instructions
874 // added after it must really go after the delayed instruction(s).
875 // So, we move the InstrAfter of that instruction to the
876 // corresponding delayed instruction using the following method.
878 //----------------------------------------------------------------------------
879 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
880 const MachineInstr *DelayedMI) {
882 // "added after" instructions of the original instr
883 std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
885 // "added instructions" of the delayed instr
886 AddedInstrns &DelayAdI = AddedInstrMap[DelayedMI];
888 // "added after" instructions of the delayed instr
889 std::vector<MachineInstr *> &DelayedAft = DelayAdI.InstrnsAfter;
891 // go thru all the "added after instructions" of the original instruction
892 // and append them to the "addded after instructions" of the delayed
894 DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
896 // empty the "added after instructions" of the original instruction
900 //----------------------------------------------------------------------------
901 // This method prints the code with registers after register allocation is
903 //----------------------------------------------------------------------------
904 void PhyRegAlloc::printMachineCode()
907 cerr << "\n;************** Function " << Meth->getName()
908 << " *****************\n";
910 for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
912 cerr << "\n"; printLabel(BBI); cerr << ": ";
914 // get the iterator for machine instructions
915 MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
916 MachineCodeForBasicBlock::iterator MII = MIVec.begin();
918 // iterate over all the machine instructions in BB
919 for ( ; MII != MIVec.end(); ++MII) {
920 MachineInstr *const MInst = *MII;
923 cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
925 for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
926 MachineOperand& Op = MInst->getOperand(OpNum);
928 if (Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
929 Op.getOperandType() == MachineOperand::MO_CCRegister /*||
930 Op.getOperandType() == MachineOperand::MO_PCRelativeDisp*/ ) {
932 const Value *const Val = Op.getVRegValue () ;
933 // ****this code is temporary till NULL Values are fixed
935 cerr << "\t<*NULL*>";
939 // if a label or a constant
940 if (isa<BasicBlock>(Val)) {
941 cerr << "\t"; printLabel( Op.getVRegValue () );
943 // else it must be a register value
944 const int RegNum = Op.getAllocatedRegNum();
946 cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
948 cerr << "(" << Val->getName() << ")";
950 cerr << "(" << Val << ")";
955 const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
957 if (LROfVal->hasSpillOffset() )
962 else if (Op.getOperandType() == MachineOperand::MO_MachineRegister) {
963 cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
967 cerr << "\t" << Op; // use dump field
972 unsigned NumOfImpRefs = MInst->getNumImplicitRefs();
973 if (NumOfImpRefs > 0) {
974 cerr << "\tImplicit:";
976 for (unsigned z=0; z < NumOfImpRefs; z++)
977 cerr << RAV(MInst->getImplicitRef(z)) << "\t";
980 } // for all machine instructions
990 //----------------------------------------------------------------------------
992 //----------------------------------------------------------------------------
993 void PhyRegAlloc::colorIncomingArgs()
995 const BasicBlock &FirstBB = Meth->front();
996 const MachineInstr *FirstMI = MachineCodeForBasicBlock::get(&FirstBB).front();
997 assert(FirstMI && "No machine instruction in entry BB");
999 MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
1003 //----------------------------------------------------------------------------
1004 // Used to generate a label for a basic block
1005 //----------------------------------------------------------------------------
1006 void PhyRegAlloc::printLabel(const Value *const Val) {
1008 cerr << Val->getName();
1010 cerr << "Label" << Val;
1014 //----------------------------------------------------------------------------
1015 // This method calls setSugColorUsable method of each live range. This
1016 // will determine whether the suggested color of LR is really usable.
1017 // A suggested color is not usable when the suggested color is volatile
1018 // AND when there are call interferences
1019 //----------------------------------------------------------------------------
1021 void PhyRegAlloc::markUnusableSugColors()
1023 if (DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n";
1025 // hash map iterator
1026 LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1027 LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1029 for (; HMI != HMIEnd ; ++HMI ) {
1031 LiveRange *L = HMI->second; // get the LiveRange
1033 if (L->hasSuggestedColor()) {
1034 int RCID = L->getRegClass()->getID();
1035 if (MRI.isRegVolatile( RCID, L->getSuggestedColor()) &&
1036 L->isCallInterference() )
1037 L->setSuggestedColorUsable( false );
1039 L->setSuggestedColorUsable( true );
1041 } // if L->hasSuggestedColor()
1043 } // for all LR's in hash map
1048 //----------------------------------------------------------------------------
1049 // The following method will set the stack offsets of the live ranges that
1050 // are decided to be spillled. This must be called just after coloring the
1051 // LRs using the graph coloring algo. For each live range that is spilled,
1052 // this method allocate a new spill position on the stack.
1053 //----------------------------------------------------------------------------
1055 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1056 if (DEBUG_RA) cerr << "\nsetting LR stack offsets ...\n";
1058 LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin();
1059 LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
1061 for ( ; HMI != HMIEnd ; ++HMI) {
1062 if (HMI->first && HMI->second) {
1063 LiveRange *L = HMI->second; // get the LiveRange
1064 if (!L->hasColor()) // NOTE: ** allocating the size of long Type **
1065 L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy));
1067 } // for all LR's in hash map
1072 //----------------------------------------------------------------------------
1073 // The entry pont to Register Allocation
1074 //----------------------------------------------------------------------------
1076 void PhyRegAlloc::allocateRegisters()
1079 // make sure that we put all register classes into the RegClassList
1080 // before we call constructLiveRanges (now done in the constructor of
1081 // PhyRegAlloc class).
1083 LRI.constructLiveRanges(); // create LR info
1086 LRI.printLiveRanges();
1088 createIGNodeListsAndIGs(); // create IGNode list and IGs
1090 buildInterferenceGraphs(); // build IGs in all reg classes
1094 // print all LRs in all reg classes
1095 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1096 RegClassList[rc]->printIGNodeList();
1098 // print IGs in all register classes
1099 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1100 RegClassList[rc]->printIG();
1104 LRI.coalesceLRs(); // coalesce all live ranges
1108 // print all LRs in all reg classes
1109 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1110 RegClassList[ rc ]->printIGNodeList();
1112 // print IGs in all register classes
1113 for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1114 RegClassList[ rc ]->printIG();
1118 // mark un-usable suggested color before graph coloring algorithm.
1119 // When this is done, the graph coloring algo will not reserve
1120 // suggested color unnecessarily - they can be used by another LR
1122 markUnusableSugColors();
1124 // color all register classes using the graph coloring algo
1125 for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
1126 RegClassList[ rc ]->colorAllRegs();
1128 // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1129 // a poistion for such spilled LRs
1131 allocateStackSpace4SpilledLRs();
1133 mcInfo.popAllTempValues(TM); // TODO **Check
1135 // color incoming args - if the correct color was not received
1136 // insert code to copy to the correct register
1138 colorIncomingArgs();
1140 // Now update the machine code with register names and add any
1141 // additional code inserted by the register allocator to the instruction
1144 updateMachineCode();
1147 MachineCodeForMethod::get(Meth).dump();
1148 printMachineCode(); // only for DEBUGGING