2 //***************************************************************************
7 // Register allocation for LLVM.
10 // 9/10/01 - Ruchira Sasanka - created.
11 //**************************************************************************/
13 #include "llvm/CodeGen/RegisterAllocation.h"
14 #include "llvm/CodeGen/PhyRegAlloc.h"
15 #include "llvm/CodeGen/MachineInstr.h"
16 #include "llvm/CodeGen/MachineCodeForMethod.h"
17 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "llvm/Target/MachineFrameInfo.h"
21 #include "llvm/Method.h"
27 // ***TODO: There are several places we add instructions. Validate the order
28 // of adding these instructions.
30 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
31 "enable register allocation debugging information",
32 clEnumValN(RA_DEBUG_None , "n", "disable debug output"),
33 clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
34 clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
37 //----------------------------------------------------------------------------
38 // RegisterAllocation pass front end...
39 //----------------------------------------------------------------------------
41 class RegisterAllocator : public MethodPass {
42 TargetMachine &Target;
44 inline RegisterAllocator(TargetMachine &T) : Target(T) {}
46 bool runOnMethod(Method *M) {
48 cerr << "\n******************** Method "<< M->getName()
49 << " ********************\n";
51 MethodLiveVarInfo LVI(M); // Analyze live varaibles
54 PhyRegAlloc PRA(M, Target, &LVI,
55 &getAnalysis<cfg::LoopInfo>());
56 PRA.allocateRegisters();
58 if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
62 virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
63 Pass::AnalysisSet &Destroyed,
64 Pass::AnalysisSet &Provided) {
65 Requires.push_back(cfg::LoopInfo::ID);
70 MethodPass *getRegisterAllocator(TargetMachine &T) {
71 return new RegisterAllocator(T);
74 //----------------------------------------------------------------------------
75 // Constructor: Init local composite objects and create register classes.
76 //----------------------------------------------------------------------------
77 PhyRegAlloc::PhyRegAlloc(Method *M,
78 const TargetMachine& tm,
79 MethodLiveVarInfo *Lvi,
82 mcInfo(MachineCodeForMethod::get(M)),
83 LVI(Lvi), LRI(M, tm, RegClassList),
84 MRI( tm.getRegInfo() ),
85 NumOfRegClasses(MRI.getNumOfRegClasses()),
88 // create each RegisterClass and put in RegClassList
90 for(unsigned int rc=0; rc < NumOfRegClasses; rc++)
91 RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc),
96 //----------------------------------------------------------------------------
97 // Destructor: Deletes register classes
98 //----------------------------------------------------------------------------
99 PhyRegAlloc::~PhyRegAlloc() {
100 for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
101 delete RegClassList[rc];
104 //----------------------------------------------------------------------------
105 // This method initally creates interference graphs (one in each reg class)
106 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
107 //----------------------------------------------------------------------------
108 void PhyRegAlloc::createIGNodeListsAndIGs() {
109 if (DEBUG_RA) cerr << "Creating LR lists ...\n";
112 LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin();
115 LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
117 for (; HMI != HMIEnd ; ++HMI ) {
119 LiveRange *L = HMI->second; // get the LiveRange
122 cerr << "\n*?!?Warning: Null liver range found for: ";
123 printValue(HMI->first); cerr << "\n";
127 // if the Value * is not null, and LR
128 // is not yet written to the IGNodeList
129 if( !(L->getUserIGNode()) ) {
130 RegClass *const RC = // RegClass of first value in the LR
131 RegClassList[ L->getRegClass()->getID() ];
133 RC->addLRToIG(L); // add this LR to an IG
139 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
140 RegClassList[rc]->createInterferenceGraph();
143 cerr << "LRLists Created!\n";
149 //----------------------------------------------------------------------------
150 // This method will add all interferences at for a given instruction.
151 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
152 // class as that of live var. The live var passed to this function is the
153 // LVset AFTER the instruction
154 //----------------------------------------------------------------------------
155 void PhyRegAlloc::addInterference(const Value *const Def,
156 const LiveVarSet *const LVSet,
157 const bool isCallInst) {
159 LiveVarSet::const_iterator LIt = LVSet->begin();
161 // get the live range of instruction
163 const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
165 IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
166 assert( IGNodeOfDef );
168 RegClass *const RCOfDef = LROfDef->getRegClass();
170 // for each live var in live variable set
172 for( ; LIt != LVSet->end(); ++LIt) {
175 cerr << "< Def="; printValue(Def);
176 cerr << ", Lvar="; printValue( *LIt); cerr << "> ";
179 // get the live range corresponding to live var
181 LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
183 // LROfVar can be null if it is a const since a const
184 // doesn't have a dominating def - see Assumptions above
187 if(LROfDef == LROfVar) // do not set interf for same LR
190 // if 2 reg classes are the same set interference
192 if(RCOfDef == LROfVar->getRegClass()) {
193 RCOfDef->setInterference( LROfDef, LROfVar);
194 } else if(DEBUG_RA > 1) {
195 // we will not have LRs for values not explicitly allocated in the
196 // instruction stream (e.g., constants)
197 cerr << " warning: no live range for " ;
198 printValue(*LIt); cerr << "\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 LiveVarSet *const LVSetAft ) {
216 // Now find the LR of the return value of the call
217 // We do this because, we look at the LV set *after* the instruction
218 // to determine, which LRs must be saved across calls. The return value
219 // of the call is live in this set - but it does not interfere with call
220 // (i.e., we can allocate a volatile register to the return value)
222 LiveRange *RetValLR = NULL;
223 const Value *RetVal = MRI.getCallInstRetVal( MInst );
226 RetValLR = LRI.getLiveRangeForValue( RetVal );
227 assert( RetValLR && "No LR for RetValue of call");
231 cerr << "\n For call inst: " << *MInst;
233 LiveVarSet::const_iterator LIt = LVSetAft->begin();
235 // for each live var in live variable set after machine inst
237 for( ; LIt != LVSetAft->end(); ++LIt) {
239 // get the live range corresponding to live var
241 LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
243 if( LR && DEBUG_RA) {
244 cerr << "\n\tLR Aft Call: ";
249 // LR can be null if it is a const since a const
250 // doesn't have a dominating def - see Assumptions above
252 if( LR && (LR != RetValLR) ) {
253 LR->setCallInterference();
255 cerr << "\n ++Added call interf for LR: " ;
267 //----------------------------------------------------------------------------
268 // This method will walk thru code and create interferences in the IG of
269 // each RegClass. Also, this method calculates the spill cost of each
270 // Live Range (it is done in this method to save another pass over the code).
271 //----------------------------------------------------------------------------
272 void PhyRegAlloc::buildInterferenceGraphs()
275 if(DEBUG_RA) cerr << "Creating interference graphs ...\n";
277 unsigned BBLoopDepthCost;
278 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
280 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
282 // find the 10^(loop_depth) of this BB
284 BBLoopDepthCost = (unsigned) pow( 10.0, LoopDepthCalc->getLoopDepth(*BBI));
286 // get the iterator for machine instructions
288 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
289 MachineCodeForBasicBlock::const_iterator
290 MInstIterator = MIVec.begin();
292 // iterate over all the machine instructions in BB
294 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
296 const MachineInstr * MInst = *MInstIterator;
298 // get the LV set after the instruction
300 const LiveVarSet *const LVSetAI =
301 LVI->getLiveVarSetAfterMInst(MInst, *BBI);
303 const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
306 // set the isCallInterference flag of each live range wich extends
307 // accross this call instruction. This information is used by graph
308 // coloring algo to avoid allocating volatile colors to live ranges
309 // that span across calls (since they have to be saved/restored)
311 setCallInterferences( MInst, LVSetAI);
315 // iterate over all MI operands to find defs
317 for( MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done(); ++OpI) {
320 // create a new LR iff this operand is a def
322 addInterference(*OpI, LVSetAI, isCallInst );
325 // Calculate the spill cost of each live range
327 LiveRange *LR = LRI.getLiveRangeForValue( *OpI );
329 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
352 } // for all BBs in method
355 // add interferences for method arguments. Since there are no explict
356 // defs in method for args, we have to add them manually
358 addInterferencesForArgs();
361 cerr << "Interference graphs calculted!\n";
367 //--------------------------------------------------------------------------
368 // Pseudo instructions will be exapnded to multiple instructions by the
369 // assembler. Consequently, all the opernds must get distinct registers.
370 // Therefore, we mark all operands of a pseudo instruction as they interfere
372 //--------------------------------------------------------------------------
373 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
375 bool setInterf = false;
377 // iterate over MI operands to find defs
379 for( MachineInstr::val_const_op_iterator It1(MInst);!It1.done(); ++It1) {
381 const LiveRange *const LROfOp1 = LRI.getLiveRangeForValue( *It1 );
383 if( !LROfOp1 && It1.isDef() )
384 assert( 0 && "No LR for Def in PSEUDO insruction");
386 MachineInstr::val_const_op_iterator It2 = It1;
389 for( ; !It2.done(); ++It2) {
391 const LiveRange *const LROfOp2 = LRI.getLiveRangeForValue( *It2 );
395 RegClass *const RCOfOp1 = LROfOp1->getRegClass();
396 RegClass *const RCOfOp2 = LROfOp2->getRegClass();
398 if( RCOfOp1 == RCOfOp2 ){
399 RCOfOp1->setInterference( LROfOp1, LROfOp2 );
405 } // for all other defs in machine instr
407 } // for all operands in an instruction
409 if( !setInterf && (MInst->getNumOperands() > 2) ) {
410 cerr << "\nInterf not set for any operand in pseudo instr:\n";
412 assert(0 && "Interf not set for pseudo instr with > 2 operands" );
420 //----------------------------------------------------------------------------
421 // This method will add interferences for incoming arguments to a method.
422 //----------------------------------------------------------------------------
423 void PhyRegAlloc::addInterferencesForArgs()
425 // get the InSet of root BB
426 const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
428 // get the argument list
429 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
431 // get an iterator to arg list
432 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
435 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
436 addInterference((Value*)*ArgIt, InSet, false); // add interferences between
437 // args and LVars at start
439 cerr << " - %% adding interference for argument ";
440 printValue((const Value *)*ArgIt); cerr << "\n";
448 //----------------------------------------------------------------------------
449 // This method is called after register allocation is complete to set the
450 // allocated reisters in the machine code. This code will add register numbers
451 // to MachineOperands that contain a Value. Also it calls target specific
452 // methods to produce caller saving instructions. At the end, it adds all
453 // additional instructions produced by the register allocator to the
454 // instruction stream.
455 //----------------------------------------------------------------------------
456 void PhyRegAlloc::updateMachineCode()
459 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
461 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
463 // get the iterator for machine instructions
465 MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
466 MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
468 // iterate over all the machine instructions in BB
470 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
472 MachineInstr *MInst = *MInstIterator;
474 unsigned Opcode = MInst->getOpCode();
476 // do not process Phis
477 if (TM.getInstrInfo().isPhi(Opcode))
480 // Now insert speical instructions (if necessary) for call/return
483 if (TM.getInstrInfo().isCall(Opcode) ||
484 TM.getInstrInfo().isReturn(Opcode)) {
486 AddedInstrns *AI = AddedInstrMap[ MInst];
488 AI = new AddedInstrns();
489 AddedInstrMap[ MInst ] = AI;
492 // Tmp stack poistions are needed by some calls that have spilled args
493 // So reset it before we call each such method
495 mcInfo.popAllTempValues(TM);
497 if (TM.getInstrInfo().isCall(Opcode))
498 MRI.colorCallArgs(MInst, LRI, AI, *this, *BBI);
499 else if (TM.getInstrInfo().isReturn(Opcode))
500 MRI.colorRetValue(MInst, LRI, AI);
504 /* -- Using above code instead of this
506 // if this machine instr is call, insert caller saving code
508 if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
509 MRI.insertCallerSavingCode(MInst, *BBI, *this );
514 // reset the stack offset for temporary variables since we may
515 // need that to spill
516 // mcInfo.popAllTempValues(TM);
517 // TODO ** : do later
519 //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
522 // Now replace set the registers for operands in the machine instruction
524 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
526 MachineOperand& Op = MInst->getOperand(OpNum);
528 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
529 Op.getOperandType() == MachineOperand::MO_CCRegister) {
531 const Value *const Val = Op.getVRegValue();
533 // delete this condition checking later (must assert if Val is null)
536 cerr << "Warning: NULL Value found for operand\n";
539 assert( Val && "Value is NULL");
541 LiveRange *const LR = LRI.getLiveRangeForValue(Val);
545 // nothing to worry if it's a const or a label
548 cerr << "*NO LR for operand : " << Op ;
549 cerr << " [reg:" << Op.getAllocatedRegNum() << "]";
550 cerr << " in inst:\t" << *MInst << "\n";
553 // if register is not allocated, mark register as invalid
554 if( Op.getAllocatedRegNum() == -1)
555 Op.setRegForValue( MRI.getInvalidRegNum());
561 unsigned RCID = (LR->getRegClass())->getID();
563 if( LR->hasColor() ) {
564 Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
568 // LR did NOT receive a color (register). Now, insert spill code
569 // for spilled opeands in this machine instruction
571 //assert(0 && "LR must be spilled");
572 insertCode4SpilledLR(LR, MInst, *BBI, OpNum );
577 } // for each operand
580 // Now add instructions that the register allocator inserts before/after
581 // this machine instructions (done only for calls/rets/incoming args)
582 // We do this here, to ensure that spill for an instruction is inserted
583 // closest as possible to an instruction (see above insertCode4Spill...)
585 // If there are instructions to be added, *before* this machine
586 // instruction, add them now.
588 if( AddedInstrMap[ MInst ] ) {
589 std::deque<MachineInstr *> &IBef = AddedInstrMap[MInst]->InstrnsBefore;
591 if( ! IBef.empty() ) {
592 std::deque<MachineInstr *>::iterator AdIt;
594 for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
597 cerr << "For inst " << *MInst;
598 cerr << " PREPENDed instr: " << **AdIt << "\n";
601 MInstIterator = MIVec.insert( MInstIterator, *AdIt );
609 // If there are instructions to be added *after* this machine
610 // instruction, add them now
612 if(AddedInstrMap[MInst] &&
613 !AddedInstrMap[MInst]->InstrnsAfter.empty() ) {
615 // if there are delay slots for this instruction, the instructions
616 // added after it must really go after the delayed instruction(s)
617 // So, we move the InstrAfter of the current instruction to the
618 // corresponding delayed instruction
621 if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
622 move2DelayedInstr(MInst, *(MInstIterator+delay) );
624 if(DEBUG_RA) cerr<< "\nMoved an added instr after the delay slot";
630 // Here we can add the "instructions after" to the current
631 // instruction since there are no delay slots for this instruction
633 std::deque<MachineInstr *> &IAft = AddedInstrMap[MInst]->InstrnsAfter;
635 if( ! IAft.empty() ) {
637 std::deque<MachineInstr *>::iterator AdIt;
639 ++MInstIterator; // advance to the next instruction
641 for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
644 cerr << "For inst " << *MInst;
645 cerr << " APPENDed instr: " << **AdIt << "\n";
648 MInstIterator = MIVec.insert( MInstIterator, *AdIt );
652 // MInsterator already points to the next instr. Since the
653 // for loop also increments it, decrement it to point to the
654 // instruction added last
663 } // for each machine instruction
669 //----------------------------------------------------------------------------
670 // This method inserts spill code for AN operand whose LR was spilled.
671 // This method may be called several times for a single machine instruction
672 // if it contains many spilled operands. Each time it is called, it finds
673 // a register which is not live at that instruction and also which is not
674 // used by other spilled operands of the same instruction. Then it uses
675 // this register temporarily to accomodate the spilled value.
676 //----------------------------------------------------------------------------
677 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
679 const BasicBlock *BB,
680 const unsigned OpNum) {
682 assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
683 (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
684 "Arg of a call/ret must be handled elsewhere");
686 MachineOperand& Op = MInst->getOperand(OpNum);
687 bool isDef = MInst->operandIsDefined(OpNum);
688 unsigned RegType = MRI.getRegType( LR );
689 int SpillOff = LR->getSpillOffFromFP();
690 RegClass *RC = LR->getRegClass();
691 const LiveVarSet *LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
693 mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
695 MachineInstr *MIBef=NULL, *AdIMid=NULL, *MIAft=NULL;
697 int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,LVSetBef, MIBef, MIAft);
699 // get the added instructions for this instruciton
700 AddedInstrns *AI = AddedInstrMap[ MInst ];
702 AI = new AddedInstrns();
703 AddedInstrMap[ MInst ] = AI;
709 // for a USE, we have to load the value of LR from stack to a TmpReg
710 // and use the TmpReg as one operand of instruction
712 // actual loading instruction
713 AdIMid = MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType);
716 AI->InstrnsBefore.push_back(MIBef);
718 AI->InstrnsBefore.push_back(AdIMid);
721 AI->InstrnsAfter.push_front(MIAft);
725 else { // if this is a Def
727 // for a DEF, we have to store the value produced by this instruction
728 // on the stack position allocated for this LR
730 // actual storing instruction
731 AdIMid = MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType);
734 AI->InstrnsBefore.push_back(MIBef);
736 AI->InstrnsAfter.push_front(AdIMid);
739 AI->InstrnsAfter.push_front(MIAft);
743 cerr << "\nFor Inst " << *MInst;
744 cerr << " - SPILLED LR: "; LR->printSet();
745 cerr << "\n - Added Instructions:";
746 if( MIBef ) cerr << *MIBef;
748 if( MIAft ) cerr << *MIAft;
750 Op.setRegForValue( TmpRegU ); // set the opearnd
760 //----------------------------------------------------------------------------
761 // We can use the following method to get a temporary register to be used
762 // BEFORE any given machine instruction. If there is a register available,
763 // this method will simply return that register and set MIBef = MIAft = NULL.
764 // Otherwise, it will return a register and MIAft and MIBef will contain
765 // two instructions used to free up this returned register.
766 // Returned register number is the UNIFIED register number
767 //----------------------------------------------------------------------------
769 int PhyRegAlloc::getUsableUniRegAtMI(RegClass *RC,
771 const MachineInstr *MInst,
772 const LiveVarSet *LVSetBef,
774 MachineInstr *MIAft) {
776 int RegU = getUnusedUniRegAtMI(RC, MInst, LVSetBef);
780 // we found an unused register, so we can simply use it
781 MIBef = MIAft = NULL;
784 // we couldn't find an unused register. Generate code to free up a reg by
785 // saving it on stack and restoring after the instruction
787 int TmpOff = mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
789 RegU = getUniRegNotUsedByThisInst(RC, MInst);
790 MIBef = MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType );
791 MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType );
797 //----------------------------------------------------------------------------
798 // This method is called to get a new unused register that can be used to
799 // accomodate a spilled value.
800 // This method may be called several times for a single machine instruction
801 // if it contains many spilled operands. Each time it is called, it finds
802 // a register which is not live at that instruction and also which is not
803 // used by other spilled operands of the same instruction.
804 // Return register number is relative to the register class. NOT
806 //----------------------------------------------------------------------------
807 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
808 const MachineInstr *MInst,
809 const LiveVarSet *LVSetBef) {
811 unsigned NumAvailRegs = RC->getNumOfAvailRegs();
813 bool *IsColorUsedArr = RC->getIsColorUsedArr();
815 for(unsigned i=0; i < NumAvailRegs; i++) // Reset array
816 IsColorUsedArr[i] = false;
818 LiveVarSet::const_iterator LIt = LVSetBef->begin();
820 // for each live var in live variable set after machine inst
821 for( ; LIt != LVSetBef->end(); ++LIt) {
823 // get the live range corresponding to live var
824 LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
826 // LR can be null if it is a const since a const
827 // doesn't have a dominating def - see Assumptions above
829 if( LRofLV->hasColor() )
830 IsColorUsedArr[ LRofLV->getColor() ] = true;
833 // It is possible that one operand of this MInst was already spilled
834 // and it received some register temporarily. If that's the case,
835 // it is recorded in machine operand. We must skip such registers.
837 setRelRegsUsedByThisInst(RC, MInst);
839 unsigned c; // find first unused color
840 for( c=0; c < NumAvailRegs; c++)
841 if( ! IsColorUsedArr[ c ] ) break;
844 return MRI.getUnifiedRegNum(RC->getID(), c);
852 //----------------------------------------------------------------------------
853 // Get any other register in a register class, other than what is used
854 // by operands of a machine instruction. Returns the unified reg number.
855 //----------------------------------------------------------------------------
856 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
857 const MachineInstr *MInst) {
859 bool *IsColorUsedArr = RC->getIsColorUsedArr();
860 unsigned NumAvailRegs = RC->getNumOfAvailRegs();
863 for(unsigned i=0; i < NumAvailRegs ; i++) // Reset array
864 IsColorUsedArr[i] = false;
866 setRelRegsUsedByThisInst(RC, MInst);
868 unsigned c; // find first unused color
869 for( c=0; c < RC->getNumOfAvailRegs(); c++)
870 if( ! IsColorUsedArr[ c ] ) break;
873 return MRI.getUnifiedRegNum(RC->getID(), c);
875 assert( 0 && "FATAL: No free register could be found in reg class!!");
880 //----------------------------------------------------------------------------
881 // This method modifies the IsColorUsedArr of the register class passed to it.
882 // It sets the bits corresponding to the registers used by this machine
883 // instructions. Both explicit and implicit operands are set.
884 //----------------------------------------------------------------------------
885 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
886 const MachineInstr *MInst ) {
888 bool *IsColorUsedArr = RC->getIsColorUsedArr();
890 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
892 const MachineOperand& Op = MInst->getOperand(OpNum);
894 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
895 Op.getOperandType() == MachineOperand::MO_CCRegister ) {
897 const Value *const Val = Op.getVRegValue();
900 if( MRI.getRegClassIDOfValue(Val) == RC->getID() ) {
902 if( (Reg=Op.getAllocatedRegNum()) != -1) {
903 IsColorUsedArr[ Reg ] = true;
906 // it is possilbe that this operand still is not marked with
907 // a register but it has a LR and that received a color
909 LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
911 if( LROfVal->hasColor() )
912 IsColorUsedArr[ LROfVal->getColor() ] = true;
915 } // if reg classes are the same
917 else if (Op.getOperandType() == MachineOperand::MO_MachineRegister) {
918 IsColorUsedArr[ Op.getMachineRegNum() ] = true;
922 // If there are implicit references, mark them as well
924 for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
926 LiveRange *const LRofImpRef =
927 LRI.getLiveRangeForValue( MInst->getImplicitRef(z) );
929 if(LRofImpRef && LRofImpRef->hasColor())
930 IsColorUsedArr[LRofImpRef->getColor()] = true;
941 //----------------------------------------------------------------------------
942 // If there are delay slots for an instruction, the instructions
943 // added after it must really go after the delayed instruction(s).
944 // So, we move the InstrAfter of that instruction to the
945 // corresponding delayed instruction using the following method.
947 //----------------------------------------------------------------------------
948 void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI,
949 const MachineInstr *DelayedMI) {
951 // "added after" instructions of the original instr
952 std::deque<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI]->InstrnsAfter;
954 // "added instructions" of the delayed instr
955 AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI];
957 if(! DelayAdI ) { // create a new "added after" if necessary
958 DelayAdI = new AddedInstrns();
959 AddedInstrMap[DelayedMI] = DelayAdI;
962 // "added after" instructions of the delayed instr
963 std::deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
965 // go thru all the "added after instructions" of the original instruction
966 // and append them to the "addded after instructions" of the delayed
968 DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
970 // empty the "added after instructions" of the original instruction
974 //----------------------------------------------------------------------------
975 // This method prints the code with registers after register allocation is
977 //----------------------------------------------------------------------------
978 void PhyRegAlloc::printMachineCode()
981 cerr << "\n;************** Method " << Meth->getName()
982 << " *****************\n";
984 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
986 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
988 cerr << "\n"; printLabel( *BBI); cerr << ": ";
990 // get the iterator for machine instructions
991 MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
992 MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
994 // iterate over all the machine instructions in BB
995 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
997 MachineInstr *const MInst = *MInstIterator;
1001 cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
1004 //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
1006 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
1008 MachineOperand& Op = MInst->getOperand(OpNum);
1010 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
1011 Op.getOperandType() == MachineOperand::MO_CCRegister /*||
1012 Op.getOperandType() == MachineOperand::MO_PCRelativeDisp*/ ) {
1014 const Value *const Val = Op.getVRegValue () ;
1015 // ****this code is temporary till NULL Values are fixed
1017 cerr << "\t<*NULL*>";
1021 // if a label or a constant
1022 if(isa<BasicBlock>(Val)) {
1023 cerr << "\t"; printLabel( Op.getVRegValue () );
1025 // else it must be a register value
1026 const int RegNum = Op.getAllocatedRegNum();
1028 cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
1029 if (Val->hasName() )
1030 cerr << "(" << Val->getName() << ")";
1032 cerr << "(" << Val << ")";
1037 const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
1039 if( LROfVal->hasSpillOffset() )
1044 else if(Op.getOperandType() == MachineOperand::MO_MachineRegister) {
1045 cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
1049 cerr << "\t" << Op; // use dump field
1054 unsigned NumOfImpRefs = MInst->getNumImplicitRefs();
1055 if( NumOfImpRefs > 0 ) {
1057 cerr << "\tImplicit:";
1059 for(unsigned z=0; z < NumOfImpRefs; z++) {
1060 printValue( MInst->getImplicitRef(z) );
1066 } // for all machine instructions
1078 //----------------------------------------------------------------------------
1080 //----------------------------------------------------------------------------
1082 void PhyRegAlloc::colorCallRetArgs()
1085 CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
1086 CallRetInstrListType::const_iterator It = CallRetInstList.begin();
1088 for( ; It != CallRetInstList.end(); ++It ) {
1090 const MachineInstr *const CRMI = *It;
1091 unsigned OpCode = CRMI->getOpCode();
1093 // get the added instructions for this Call/Ret instruciton
1094 AddedInstrns *AI = AddedInstrMap[ CRMI ];
1096 AI = new AddedInstrns();
1097 AddedInstrMap[ CRMI ] = AI;
1100 // Tmp stack poistions are needed by some calls that have spilled args
1101 // So reset it before we call each such method
1102 //mcInfo.popAllTempValues(TM);
1106 if (TM.getInstrInfo().isCall(OpCode))
1107 MRI.colorCallArgs(CRMI, LRI, AI, *this);
1108 else if (TM.getInstrInfo().isReturn(OpCode))
1109 MRI.colorRetValue( CRMI, LRI, AI );
1111 assert(0 && "Non Call/Ret instrn in CallRetInstrList\n");
1117 //----------------------------------------------------------------------------
1119 //----------------------------------------------------------------------------
1120 void PhyRegAlloc::colorIncomingArgs()
1122 const BasicBlock *const FirstBB = Meth->front();
1123 const MachineInstr *FirstMI = FirstBB->getMachineInstrVec().front();
1124 assert(FirstMI && "No machine instruction in entry BB");
1126 AddedInstrns *AI = AddedInstrMap[FirstMI];
1128 AddedInstrMap[FirstMI] = AI = new AddedInstrns();
1130 MRI.colorMethodArgs(Meth, LRI, AI);
1134 //----------------------------------------------------------------------------
1135 // Used to generate a label for a basic block
1136 //----------------------------------------------------------------------------
1137 void PhyRegAlloc::printLabel(const Value *const Val) {
1139 cerr << Val->getName();
1141 cerr << "Label" << Val;
1145 //----------------------------------------------------------------------------
1146 // This method calls setSugColorUsable method of each live range. This
1147 // will determine whether the suggested color of LR is really usable.
1148 // A suggested color is not usable when the suggested color is volatile
1149 // AND when there are call interferences
1150 //----------------------------------------------------------------------------
1152 void PhyRegAlloc::markUnusableSugColors()
1154 if(DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n";
1156 // hash map iterator
1157 LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1158 LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1160 for(; HMI != HMIEnd ; ++HMI ) {
1162 LiveRange *L = HMI->second; // get the LiveRange
1164 if(L->hasSuggestedColor()) {
1165 int RCID = L->getRegClass()->getID();
1166 if( MRI.isRegVolatile( RCID, L->getSuggestedColor()) &&
1167 L->isCallInterference() )
1168 L->setSuggestedColorUsable( false );
1170 L->setSuggestedColorUsable( true );
1172 } // if L->hasSuggestedColor()
1174 } // for all LR's in hash map
1179 //----------------------------------------------------------------------------
1180 // The following method will set the stack offsets of the live ranges that
1181 // are decided to be spillled. This must be called just after coloring the
1182 // LRs using the graph coloring algo. For each live range that is spilled,
1183 // this method allocate a new spill position on the stack.
1184 //----------------------------------------------------------------------------
1186 void PhyRegAlloc::allocateStackSpace4SpilledLRs()
1188 if(DEBUG_RA ) cerr << "\nsetting LR stack offsets ...\n";
1190 // hash map iterator
1191 LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1192 LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1194 for( ; HMI != HMIEnd ; ++HMI ) {
1195 if(HMI->first && HMI->second) {
1196 LiveRange *L = HMI->second; // get the LiveRange
1197 if( ! L->hasColor() )
1198 // NOTE: ** allocating the size of long Type **
1199 L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy));
1201 } // for all LR's in hash map
1206 //----------------------------------------------------------------------------
1207 // The entry pont to Register Allocation
1208 //----------------------------------------------------------------------------
1210 void PhyRegAlloc::allocateRegisters()
1213 // make sure that we put all register classes into the RegClassList
1214 // before we call constructLiveRanges (now done in the constructor of
1215 // PhyRegAlloc class).
1217 LRI.constructLiveRanges(); // create LR info
1220 LRI.printLiveRanges();
1222 createIGNodeListsAndIGs(); // create IGNode list and IGs
1224 buildInterferenceGraphs(); // build IGs in all reg classes
1228 // print all LRs in all reg classes
1229 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1230 RegClassList[ rc ]->printIGNodeList();
1232 // print IGs in all register classes
1233 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1234 RegClassList[ rc ]->printIG();
1238 LRI.coalesceLRs(); // coalesce all live ranges
1242 // print all LRs in all reg classes
1243 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1244 RegClassList[ rc ]->printIGNodeList();
1246 // print IGs in all register classes
1247 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1248 RegClassList[ rc ]->printIG();
1252 // mark un-usable suggested color before graph coloring algorithm.
1253 // When this is done, the graph coloring algo will not reserve
1254 // suggested color unnecessarily - they can be used by another LR
1256 markUnusableSugColors();
1258 // color all register classes using the graph coloring algo
1259 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1260 RegClassList[ rc ]->colorAllRegs();
1262 // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1263 // a poistion for such spilled LRs
1265 allocateStackSpace4SpilledLRs();
1267 mcInfo.popAllTempValues(TM); // TODO **Check
1269 // color incoming args - if the correct color was not received
1270 // insert code to copy to the correct register
1272 colorIncomingArgs();
1274 // Now update the machine code with register names and add any
1275 // additional code inserted by the register allocator to the instruction
1278 updateMachineCode();
1281 MachineCodeForMethod::get(Meth).dump();
1282 printMachineCode(); // only for DEBUGGING