2 //***************************************************************************
7 // Register allocation for LLVM.
10 // 9/10/01 - Ruchira Sasanka - created.
11 //**************************************************************************/
13 #include "llvm/CodeGen/PhyRegAlloc.h"
14 #include "llvm/CodeGen/MachineInstr.h"
15 #include "llvm/CodeGen/MachineCodeForMethod.h"
16 #include "llvm/Target/TargetMachine.h"
17 #include "llvm/Target/MachineFrameInfo.h"
23 // ***TODO: There are several places we add instructions. Validate the order
24 // of adding these instructions.
28 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
29 "enable register allocation debugging information",
30 clEnumValN(RA_DEBUG_None , "n", "disable debug output"),
31 clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
32 clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
35 //----------------------------------------------------------------------------
36 // Constructor: Init local composite objects and create register classes.
37 //----------------------------------------------------------------------------
38 PhyRegAlloc::PhyRegAlloc(Method *M,
39 const TargetMachine& tm,
40 MethodLiveVarInfo *const Lvi)
42 mcInfo(MachineCodeForMethod::get(M)),
43 LVI(Lvi), LRI(M, tm, RegClassList),
44 MRI( tm.getRegInfo() ),
45 NumOfRegClasses(MRI.getNumOfRegClasses()),
48 // create each RegisterClass and put in RegClassList
50 for(unsigned int rc=0; rc < NumOfRegClasses; rc++)
51 RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc),
56 //----------------------------------------------------------------------------
57 // Destructor: Deletes register classes
58 //----------------------------------------------------------------------------
59 PhyRegAlloc::~PhyRegAlloc() {
60 for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
61 delete RegClassList[rc];
64 //----------------------------------------------------------------------------
65 // This method initally creates interference graphs (one in each reg class)
66 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
67 //----------------------------------------------------------------------------
68 void PhyRegAlloc::createIGNodeListsAndIGs() {
69 if (DEBUG_RA) cerr << "Creating LR lists ...\n";
72 LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin();
75 LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
77 for (; HMI != HMIEnd ; ++HMI ) {
79 LiveRange *L = HMI->second; // get the LiveRange
82 cerr << "\n*?!?Warning: Null liver range found for: ";
83 printValue(HMI->first); cerr << "\n";
87 // if the Value * is not null, and LR
88 // is not yet written to the IGNodeList
89 if( !(L->getUserIGNode()) ) {
90 RegClass *const RC = // RegClass of first value in the LR
91 RegClassList[ L->getRegClass()->getID() ];
93 RC->addLRToIG(L); // add this LR to an IG
99 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
100 RegClassList[rc]->createInterferenceGraph();
103 cerr << "LRLists Created!\n";
109 //----------------------------------------------------------------------------
110 // This method will add all interferences at for a given instruction.
111 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
112 // class as that of live var. The live var passed to this function is the
113 // LVset AFTER the instruction
114 //----------------------------------------------------------------------------
115 void PhyRegAlloc::addInterference(const Value *const Def,
116 const LiveVarSet *const LVSet,
117 const bool isCallInst) {
119 LiveVarSet::const_iterator LIt = LVSet->begin();
121 // get the live range of instruction
123 const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
125 IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
126 assert( IGNodeOfDef );
128 RegClass *const RCOfDef = LROfDef->getRegClass();
130 // for each live var in live variable set
132 for( ; LIt != LVSet->end(); ++LIt) {
135 cerr << "< Def="; printValue(Def);
136 cerr << ", Lvar="; printValue( *LIt); cerr << "> ";
139 // get the live range corresponding to live var
141 LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
143 // LROfVar can be null if it is a const since a const
144 // doesn't have a dominating def - see Assumptions above
147 if(LROfDef == LROfVar) // do not set interf for same LR
150 // if 2 reg classes are the same set interference
152 if(RCOfDef == LROfVar->getRegClass()) {
153 RCOfDef->setInterference( LROfDef, LROfVar);
154 } else if(DEBUG_RA > 1) {
155 // we will not have LRs for values not explicitly allocated in the
156 // instruction stream (e.g., constants)
157 cerr << " warning: no live range for " ;
158 printValue(*LIt); cerr << "\n";
166 //----------------------------------------------------------------------------
167 // For a call instruction, this method sets the CallInterference flag in
168 // the LR of each variable live int the Live Variable Set live after the
169 // call instruction (except the return value of the call instruction - since
170 // the return value does not interfere with that call itself).
171 //----------------------------------------------------------------------------
173 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
174 const LiveVarSet *const LVSetAft ) {
176 // Now find the LR of the return value of the call
177 // We do this because, we look at the LV set *after* the instruction
178 // to determine, which LRs must be saved across calls. The return value
179 // of the call is live in this set - but it does not interfere with call
180 // (i.e., we can allocate a volatile register to the return value)
182 LiveRange *RetValLR = NULL;
183 const Value *RetVal = MRI.getCallInstRetVal( MInst );
186 RetValLR = LRI.getLiveRangeForValue( RetVal );
187 assert( RetValLR && "No LR for RetValue of call");
191 cerr << "\n For call inst: " << *MInst;
193 LiveVarSet::const_iterator LIt = LVSetAft->begin();
195 // for each live var in live variable set after machine inst
197 for( ; LIt != LVSetAft->end(); ++LIt) {
199 // get the live range corresponding to live var
201 LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
203 if( LR && DEBUG_RA) {
204 cerr << "\n\tLR Aft Call: ";
209 // LR can be null if it is a const since a const
210 // doesn't have a dominating def - see Assumptions above
212 if( LR && (LR != RetValLR) ) {
213 LR->setCallInterference();
215 cerr << "\n ++Added call interf for LR: " ;
227 //----------------------------------------------------------------------------
228 // This method will walk thru code and create interferences in the IG of
229 // each RegClass. Also, this method calculates the spill cost of each
230 // Live Range (it is done in this method to save another pass over the code).
231 //----------------------------------------------------------------------------
232 void PhyRegAlloc::buildInterferenceGraphs()
235 if(DEBUG_RA) cerr << "Creating interference graphs ...\n";
237 unsigned BBLoopDepthCost;
238 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
240 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
242 // find the 10^(loop_depth) of this BB
244 BBLoopDepthCost = (unsigned) pow( 10.0, LoopDepthCalc.getLoopDepth(*BBI));
246 // get the iterator for machine instructions
248 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
249 MachineCodeForBasicBlock::const_iterator
250 MInstIterator = MIVec.begin();
252 // iterate over all the machine instructions in BB
254 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
256 const MachineInstr * MInst = *MInstIterator;
258 // get the LV set after the instruction
260 const LiveVarSet *const LVSetAI =
261 LVI->getLiveVarSetAfterMInst(MInst, *BBI);
263 const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
266 // set the isCallInterference flag of each live range wich extends
267 // accross this call instruction. This information is used by graph
268 // coloring algo to avoid allocating volatile colors to live ranges
269 // that span across calls (since they have to be saved/restored)
271 setCallInterferences( MInst, LVSetAI);
275 // iterate over all MI operands to find defs
277 for( MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done(); ++OpI) {
280 // create a new LR iff this operand is a def
282 addInterference(*OpI, LVSetAI, isCallInst );
285 // Calculate the spill cost of each live range
287 LiveRange *LR = LRI.getLiveRangeForValue( *OpI );
289 LR->addSpillCost(BBLoopDepthCost);
293 // if there are multiple defs in this instruction e.g. in SETX
295 if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
296 addInterf4PseudoInstr(MInst);
299 // Also add interference for any implicit definitions in a machine
300 // instr (currently, only calls have this).
302 unsigned NumOfImpRefs = MInst->getNumImplicitRefs();
303 if( NumOfImpRefs > 0 ) {
304 for(unsigned z=0; z < NumOfImpRefs; z++)
305 if( MInst->implicitRefIsDefined(z) )
306 addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
310 } // for all machine instructions in BB
312 } // for all BBs in method
315 // add interferences for method arguments. Since there are no explict
316 // defs in method for args, we have to add them manually
318 addInterferencesForArgs();
321 cerr << "Interference graphs calculted!\n";
327 //--------------------------------------------------------------------------
328 // Pseudo instructions will be exapnded to multiple instructions by the
329 // assembler. Consequently, all the opernds must get distinct registers.
330 // Therefore, we mark all operands of a pseudo instruction as they interfere
332 //--------------------------------------------------------------------------
333 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
335 bool setInterf = false;
337 // iterate over MI operands to find defs
339 for( MachineInstr::val_const_op_iterator It1(MInst);!It1.done(); ++It1) {
341 const LiveRange *const LROfOp1 = LRI.getLiveRangeForValue( *It1 );
343 if( !LROfOp1 && It1.isDef() )
344 assert( 0 && "No LR for Def in PSEUDO insruction");
346 MachineInstr::val_const_op_iterator It2 = It1;
349 for( ; !It2.done(); ++It2) {
351 const LiveRange *const LROfOp2 = LRI.getLiveRangeForValue( *It2 );
355 RegClass *const RCOfOp1 = LROfOp1->getRegClass();
356 RegClass *const RCOfOp2 = LROfOp2->getRegClass();
358 if( RCOfOp1 == RCOfOp2 ){
359 RCOfOp1->setInterference( LROfOp1, LROfOp2 );
365 } // for all other defs in machine instr
367 } // for all operands in an instruction
369 if( !setInterf && (MInst->getNumOperands() > 2) ) {
370 cerr << "\nInterf not set for any operand in pseudo instr:\n";
372 assert(0 && "Interf not set for pseudo instr with > 2 operands" );
380 //----------------------------------------------------------------------------
381 // This method will add interferences for incoming arguments to a method.
382 //----------------------------------------------------------------------------
383 void PhyRegAlloc::addInterferencesForArgs()
385 // get the InSet of root BB
386 const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
388 // get the argument list
389 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
391 // get an iterator to arg list
392 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
395 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
396 addInterference( *ArgIt, InSet, false ); // add interferences between
397 // args and LVars at start
399 cerr << " - %% adding interference for argument ";
400 printValue((const Value *)*ArgIt); cerr << "\n";
408 //----------------------------------------------------------------------------
409 // This method is called after register allocation is complete to set the
410 // allocated reisters in the machine code. This code will add register numbers
411 // to MachineOperands that contain a Value. Also it calls target specific
412 // methods to produce caller saving instructions. At the end, it adds all
413 // additional instructions produced by the register allocator to the
414 // instruction stream.
415 //----------------------------------------------------------------------------
416 void PhyRegAlloc::updateMachineCode()
419 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
421 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
423 // get the iterator for machine instructions
425 MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
426 MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
428 // iterate over all the machine instructions in BB
430 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
432 MachineInstr *MInst = *MInstIterator;
434 unsigned Opcode = MInst->getOpCode();
436 // do not process Phis
437 if (TM.getInstrInfo().isPhi(Opcode))
440 // Now insert speical instructions (if necessary) for call/return
443 if (TM.getInstrInfo().isCall(Opcode) ||
444 TM.getInstrInfo().isReturn(Opcode)) {
446 AddedInstrns *AI = AddedInstrMap[ MInst];
448 AI = new AddedInstrns();
449 AddedInstrMap[ MInst ] = AI;
452 // Tmp stack poistions are needed by some calls that have spilled args
453 // So reset it before we call each such method
455 mcInfo.popAllTempValues(TM);
457 if (TM.getInstrInfo().isCall(Opcode))
458 MRI.colorCallArgs(MInst, LRI, AI, *this, *BBI);
459 else if (TM.getInstrInfo().isReturn(Opcode))
460 MRI.colorRetValue(MInst, LRI, AI);
464 /* -- Using above code instead of this
466 // if this machine instr is call, insert caller saving code
468 if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
469 MRI.insertCallerSavingCode(MInst, *BBI, *this );
474 // reset the stack offset for temporary variables since we may
475 // need that to spill
476 // mcInfo.popAllTempValues(TM);
477 // TODO ** : do later
479 //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
482 // Now replace set the registers for operands in the machine instruction
484 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
486 MachineOperand& Op = MInst->getOperand(OpNum);
488 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
489 Op.getOperandType() == MachineOperand::MO_CCRegister) {
491 const Value *const Val = Op.getVRegValue();
493 // delete this condition checking later (must assert if Val is null)
496 cerr << "Warning: NULL Value found for operand\n";
499 assert( Val && "Value is NULL");
501 LiveRange *const LR = LRI.getLiveRangeForValue(Val);
505 // nothing to worry if it's a const or a label
508 cerr << "*NO LR for operand : " << Op ;
509 cerr << " [reg:" << Op.getAllocatedRegNum() << "]";
510 cerr << " in inst:\t" << *MInst << "\n";
513 // if register is not allocated, mark register as invalid
514 if( Op.getAllocatedRegNum() == -1)
515 Op.setRegForValue( MRI.getInvalidRegNum());
521 unsigned RCID = (LR->getRegClass())->getID();
523 if( LR->hasColor() ) {
524 Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
528 // LR did NOT receive a color (register). Now, insert spill code
529 // for spilled opeands in this machine instruction
531 //assert(0 && "LR must be spilled");
532 insertCode4SpilledLR(LR, MInst, *BBI, OpNum );
537 } // for each operand
540 // Now add instructions that the register allocator inserts before/after
541 // this machine instructions (done only for calls/rets/incoming args)
542 // We do this here, to ensure that spill for an instruction is inserted
543 // closest as possible to an instruction (see above insertCode4Spill...)
545 // If there are instructions to be added, *before* this machine
546 // instruction, add them now.
548 if( AddedInstrMap[ MInst ] ) {
549 std::deque<MachineInstr *> &IBef = AddedInstrMap[MInst]->InstrnsBefore;
551 if( ! IBef.empty() ) {
552 std::deque<MachineInstr *>::iterator AdIt;
554 for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
557 cerr << "For inst " << *MInst;
558 cerr << " PREPENDed instr: " << **AdIt << "\n";
561 MInstIterator = MIVec.insert( MInstIterator, *AdIt );
569 // If there are instructions to be added *after* this machine
570 // instruction, add them now
572 if(AddedInstrMap[MInst] &&
573 !AddedInstrMap[MInst]->InstrnsAfter.empty() ) {
575 // if there are delay slots for this instruction, the instructions
576 // added after it must really go after the delayed instruction(s)
577 // So, we move the InstrAfter of the current instruction to the
578 // corresponding delayed instruction
581 if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
582 move2DelayedInstr(MInst, *(MInstIterator+delay) );
584 if(DEBUG_RA) cerr<< "\nMoved an added instr after the delay slot";
590 // Here we can add the "instructions after" to the current
591 // instruction since there are no delay slots for this instruction
593 std::deque<MachineInstr *> &IAft = AddedInstrMap[MInst]->InstrnsAfter;
595 if( ! IAft.empty() ) {
597 std::deque<MachineInstr *>::iterator AdIt;
599 ++MInstIterator; // advance to the next instruction
601 for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
604 cerr << "For inst " << *MInst;
605 cerr << " APPENDed instr: " << **AdIt << "\n";
608 MInstIterator = MIVec.insert( MInstIterator, *AdIt );
612 // MInsterator already points to the next instr. Since the
613 // for loop also increments it, decrement it to point to the
614 // instruction added last
623 } // for each machine instruction
629 //----------------------------------------------------------------------------
630 // This method inserts spill code for AN operand whose LR was spilled.
631 // This method may be called several times for a single machine instruction
632 // if it contains many spilled operands. Each time it is called, it finds
633 // a register which is not live at that instruction and also which is not
634 // used by other spilled operands of the same instruction. Then it uses
635 // this register temporarily to accomodate the spilled value.
636 //----------------------------------------------------------------------------
637 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
639 const BasicBlock *BB,
640 const unsigned OpNum) {
642 assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
643 (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
644 "Arg of a call/ret must be handled elsewhere");
646 MachineOperand& Op = MInst->getOperand(OpNum);
647 bool isDef = MInst->operandIsDefined(OpNum);
648 unsigned RegType = MRI.getRegType( LR );
649 int SpillOff = LR->getSpillOffFromFP();
650 RegClass *RC = LR->getRegClass();
651 const LiveVarSet *LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
653 mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
655 MachineInstr *MIBef=NULL, *AdIMid=NULL, *MIAft=NULL;
657 int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,LVSetBef, MIBef, MIAft);
659 // get the added instructions for this instruciton
660 AddedInstrns *AI = AddedInstrMap[ MInst ];
662 AI = new AddedInstrns();
663 AddedInstrMap[ MInst ] = AI;
669 // for a USE, we have to load the value of LR from stack to a TmpReg
670 // and use the TmpReg as one operand of instruction
672 // actual loading instruction
673 AdIMid = MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType);
676 AI->InstrnsBefore.push_back(MIBef);
678 AI->InstrnsBefore.push_back(AdIMid);
681 AI->InstrnsAfter.push_front(MIAft);
685 else { // if this is a Def
687 // for a DEF, we have to store the value produced by this instruction
688 // on the stack position allocated for this LR
690 // actual storing instruction
691 AdIMid = MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType);
694 AI->InstrnsBefore.push_back(MIBef);
696 AI->InstrnsAfter.push_front(AdIMid);
699 AI->InstrnsAfter.push_front(MIAft);
703 cerr << "\nFor Inst " << *MInst;
704 cerr << " - SPILLED LR: "; LR->printSet();
705 cerr << "\n - Added Instructions:";
706 if( MIBef ) cerr << *MIBef;
708 if( MIAft ) cerr << *MIAft;
710 Op.setRegForValue( TmpRegU ); // set the opearnd
720 //----------------------------------------------------------------------------
721 // We can use the following method to get a temporary register to be used
722 // BEFORE any given machine instruction. If there is a register available,
723 // this method will simply return that register and set MIBef = MIAft = NULL.
724 // Otherwise, it will return a register and MIAft and MIBef will contain
725 // two instructions used to free up this returned register.
726 // Returned register number is the UNIFIED register number
727 //----------------------------------------------------------------------------
729 int PhyRegAlloc::getUsableUniRegAtMI(RegClass *RC,
731 const MachineInstr *MInst,
732 const LiveVarSet *LVSetBef,
734 MachineInstr *MIAft) {
736 int RegU = getUnusedUniRegAtMI(RC, MInst, LVSetBef);
740 // we found an unused register, so we can simply use it
741 MIBef = MIAft = NULL;
744 // we couldn't find an unused register. Generate code to free up a reg by
745 // saving it on stack and restoring after the instruction
747 int TmpOff = mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
749 RegU = getUniRegNotUsedByThisInst(RC, MInst);
750 MIBef = MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType );
751 MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType );
757 //----------------------------------------------------------------------------
758 // This method is called to get a new unused register that can be used to
759 // accomodate a spilled value.
760 // This method may be called several times for a single machine instruction
761 // if it contains many spilled operands. Each time it is called, it finds
762 // a register which is not live at that instruction and also which is not
763 // used by other spilled operands of the same instruction.
764 // Return register number is relative to the register class. NOT
766 //----------------------------------------------------------------------------
767 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
768 const MachineInstr *MInst,
769 const LiveVarSet *LVSetBef) {
771 unsigned NumAvailRegs = RC->getNumOfAvailRegs();
773 bool *IsColorUsedArr = RC->getIsColorUsedArr();
775 for(unsigned i=0; i < NumAvailRegs; i++) // Reset array
776 IsColorUsedArr[i] = false;
778 LiveVarSet::const_iterator LIt = LVSetBef->begin();
780 // for each live var in live variable set after machine inst
781 for( ; LIt != LVSetBef->end(); ++LIt) {
783 // get the live range corresponding to live var
784 LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
786 // LR can be null if it is a const since a const
787 // doesn't have a dominating def - see Assumptions above
789 if( LRofLV->hasColor() )
790 IsColorUsedArr[ LRofLV->getColor() ] = true;
793 // It is possible that one operand of this MInst was already spilled
794 // and it received some register temporarily. If that's the case,
795 // it is recorded in machine operand. We must skip such registers.
797 setRelRegsUsedByThisInst(RC, MInst);
799 unsigned c; // find first unused color
800 for( c=0; c < NumAvailRegs; c++)
801 if( ! IsColorUsedArr[ c ] ) break;
804 return MRI.getUnifiedRegNum(RC->getID(), c);
812 //----------------------------------------------------------------------------
813 // Get any other register in a register class, other than what is used
814 // by operands of a machine instruction. Returns the unified reg number.
815 //----------------------------------------------------------------------------
816 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
817 const MachineInstr *MInst) {
819 bool *IsColorUsedArr = RC->getIsColorUsedArr();
820 unsigned NumAvailRegs = RC->getNumOfAvailRegs();
823 for(unsigned i=0; i < NumAvailRegs ; i++) // Reset array
824 IsColorUsedArr[i] = false;
826 setRelRegsUsedByThisInst(RC, MInst);
828 unsigned c; // find first unused color
829 for( c=0; c < RC->getNumOfAvailRegs(); c++)
830 if( ! IsColorUsedArr[ c ] ) break;
833 return MRI.getUnifiedRegNum(RC->getID(), c);
835 assert( 0 && "FATAL: No free register could be found in reg class!!");
840 //----------------------------------------------------------------------------
841 // This method modifies the IsColorUsedArr of the register class passed to it.
842 // It sets the bits corresponding to the registers used by this machine
843 // instructions. Both explicit and implicit operands are set.
844 //----------------------------------------------------------------------------
845 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
846 const MachineInstr *MInst ) {
848 bool *IsColorUsedArr = RC->getIsColorUsedArr();
850 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
852 const MachineOperand& Op = MInst->getOperand(OpNum);
854 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
855 Op.getOperandType() == MachineOperand::MO_CCRegister ) {
857 const Value *const Val = Op.getVRegValue();
860 if( MRI.getRegClassIDOfValue(Val) == RC->getID() ) {
862 if( (Reg=Op.getAllocatedRegNum()) != -1) {
863 IsColorUsedArr[ Reg ] = true;
866 // it is possilbe that this operand still is not marked with
867 // a register but it has a LR and that received a color
869 LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
871 if( LROfVal->hasColor() )
872 IsColorUsedArr[ LROfVal->getColor() ] = true;
875 } // if reg classes are the same
877 else if (Op.getOperandType() == MachineOperand::MO_MachineRegister) {
878 IsColorUsedArr[ Op.getMachineRegNum() ] = true;
882 // If there are implicit references, mark them as well
884 for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
886 LiveRange *const LRofImpRef =
887 LRI.getLiveRangeForValue( MInst->getImplicitRef(z) );
889 if(LRofImpRef && LRofImpRef->hasColor())
890 IsColorUsedArr[LRofImpRef->getColor()] = true;
901 //----------------------------------------------------------------------------
902 // If there are delay slots for an instruction, the instructions
903 // added after it must really go after the delayed instruction(s).
904 // So, we move the InstrAfter of that instruction to the
905 // corresponding delayed instruction using the following method.
907 //----------------------------------------------------------------------------
908 void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI,
909 const MachineInstr *DelayedMI) {
911 // "added after" instructions of the original instr
912 std::deque<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI]->InstrnsAfter;
914 // "added instructions" of the delayed instr
915 AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI];
917 if(! DelayAdI ) { // create a new "added after" if necessary
918 DelayAdI = new AddedInstrns();
919 AddedInstrMap[DelayedMI] = DelayAdI;
922 // "added after" instructions of the delayed instr
923 std::deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
925 // go thru all the "added after instructions" of the original instruction
926 // and append them to the "addded after instructions" of the delayed
928 DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
930 // empty the "added after instructions" of the original instruction
934 //----------------------------------------------------------------------------
935 // This method prints the code with registers after register allocation is
937 //----------------------------------------------------------------------------
938 void PhyRegAlloc::printMachineCode()
941 cerr << "\n;************** Method " << Meth->getName()
942 << " *****************\n";
944 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
946 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
948 cerr << "\n"; printLabel( *BBI); cerr << ": ";
950 // get the iterator for machine instructions
951 MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
952 MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
954 // iterate over all the machine instructions in BB
955 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
957 MachineInstr *const MInst = *MInstIterator;
961 cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
964 //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
966 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
968 MachineOperand& Op = MInst->getOperand(OpNum);
970 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
971 Op.getOperandType() == MachineOperand::MO_CCRegister /*||
972 Op.getOperandType() == MachineOperand::MO_PCRelativeDisp*/ ) {
974 const Value *const Val = Op.getVRegValue () ;
975 // ****this code is temporary till NULL Values are fixed
977 cerr << "\t<*NULL*>";
981 // if a label or a constant
982 if(isa<BasicBlock>(Val)) {
983 cerr << "\t"; printLabel( Op.getVRegValue () );
985 // else it must be a register value
986 const int RegNum = Op.getAllocatedRegNum();
988 cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
990 cerr << "(" << Val->getName() << ")";
992 cerr << "(" << Val << ")";
997 const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
999 if( LROfVal->hasSpillOffset() )
1004 else if(Op.getOperandType() == MachineOperand::MO_MachineRegister) {
1005 cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
1009 cerr << "\t" << Op; // use dump field
1014 unsigned NumOfImpRefs = MInst->getNumImplicitRefs();
1015 if( NumOfImpRefs > 0 ) {
1017 cerr << "\tImplicit:";
1019 for(unsigned z=0; z < NumOfImpRefs; z++) {
1020 printValue( MInst->getImplicitRef(z) );
1026 } // for all machine instructions
1038 //----------------------------------------------------------------------------
1040 //----------------------------------------------------------------------------
1042 void PhyRegAlloc::colorCallRetArgs()
1045 CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
1046 CallRetInstrListType::const_iterator It = CallRetInstList.begin();
1048 for( ; It != CallRetInstList.end(); ++It ) {
1050 const MachineInstr *const CRMI = *It;
1051 unsigned OpCode = CRMI->getOpCode();
1053 // get the added instructions for this Call/Ret instruciton
1054 AddedInstrns *AI = AddedInstrMap[ CRMI ];
1056 AI = new AddedInstrns();
1057 AddedInstrMap[ CRMI ] = AI;
1060 // Tmp stack poistions are needed by some calls that have spilled args
1061 // So reset it before we call each such method
1062 //mcInfo.popAllTempValues(TM);
1066 if (TM.getInstrInfo().isCall(OpCode))
1067 MRI.colorCallArgs(CRMI, LRI, AI, *this);
1068 else if (TM.getInstrInfo().isReturn(OpCode))
1069 MRI.colorRetValue( CRMI, LRI, AI );
1071 assert(0 && "Non Call/Ret instrn in CallRetInstrList\n");
1077 //----------------------------------------------------------------------------
1079 //----------------------------------------------------------------------------
1080 void PhyRegAlloc::colorIncomingArgs()
1082 const BasicBlock *const FirstBB = Meth->front();
1083 const MachineInstr *FirstMI = FirstBB->getMachineInstrVec().front();
1084 assert(FirstMI && "No machine instruction in entry BB");
1086 AddedInstrns *AI = AddedInstrMap[FirstMI];
1088 AddedInstrMap[FirstMI] = AI = new AddedInstrns();
1090 MRI.colorMethodArgs(Meth, LRI, AI);
1094 //----------------------------------------------------------------------------
1095 // Used to generate a label for a basic block
1096 //----------------------------------------------------------------------------
1097 void PhyRegAlloc::printLabel(const Value *const Val) {
1099 cerr << Val->getName();
1101 cerr << "Label" << Val;
1105 //----------------------------------------------------------------------------
1106 // This method calls setSugColorUsable method of each live range. This
1107 // will determine whether the suggested color of LR is really usable.
1108 // A suggested color is not usable when the suggested color is volatile
1109 // AND when there are call interferences
1110 //----------------------------------------------------------------------------
1112 void PhyRegAlloc::markUnusableSugColors()
1114 if(DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n";
1116 // hash map iterator
1117 LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1118 LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1120 for(; HMI != HMIEnd ; ++HMI ) {
1122 LiveRange *L = HMI->second; // get the LiveRange
1124 if(L->hasSuggestedColor()) {
1125 int RCID = L->getRegClass()->getID();
1126 if( MRI.isRegVolatile( RCID, L->getSuggestedColor()) &&
1127 L->isCallInterference() )
1128 L->setSuggestedColorUsable( false );
1130 L->setSuggestedColorUsable( true );
1132 } // if L->hasSuggestedColor()
1134 } // for all LR's in hash map
1139 //----------------------------------------------------------------------------
1140 // The following method will set the stack offsets of the live ranges that
1141 // are decided to be spillled. This must be called just after coloring the
1142 // LRs using the graph coloring algo. For each live range that is spilled,
1143 // this method allocate a new spill position on the stack.
1144 //----------------------------------------------------------------------------
1146 void PhyRegAlloc::allocateStackSpace4SpilledLRs()
1148 if(DEBUG_RA ) cerr << "\nsetting LR stack offsets ...\n";
1150 // hash map iterator
1151 LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1152 LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1154 for( ; HMI != HMIEnd ; ++HMI ) {
1155 if(HMI->first && HMI->second) {
1156 LiveRange *L = HMI->second; // get the LiveRange
1157 if( ! L->hasColor() )
1158 // NOTE: ** allocating the size of long Type **
1159 L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy));
1161 } // for all LR's in hash map
1166 //----------------------------------------------------------------------------
1167 // The entry pont to Register Allocation
1168 //----------------------------------------------------------------------------
1170 void PhyRegAlloc::allocateRegisters()
1173 // make sure that we put all register classes into the RegClassList
1174 // before we call constructLiveRanges (now done in the constructor of
1175 // PhyRegAlloc class).
1177 LRI.constructLiveRanges(); // create LR info
1180 LRI.printLiveRanges();
1182 createIGNodeListsAndIGs(); // create IGNode list and IGs
1184 buildInterferenceGraphs(); // build IGs in all reg classes
1188 // print all LRs in all reg classes
1189 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1190 RegClassList[ rc ]->printIGNodeList();
1192 // print IGs in all register classes
1193 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1194 RegClassList[ rc ]->printIG();
1198 LRI.coalesceLRs(); // coalesce all live ranges
1202 // print all LRs in all reg classes
1203 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1204 RegClassList[ rc ]->printIGNodeList();
1206 // print IGs in all register classes
1207 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1208 RegClassList[ rc ]->printIG();
1212 // mark un-usable suggested color before graph coloring algorithm.
1213 // When this is done, the graph coloring algo will not reserve
1214 // suggested color unnecessarily - they can be used by another LR
1216 markUnusableSugColors();
1218 // color all register classes using the graph coloring algo
1219 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1220 RegClassList[ rc ]->colorAllRegs();
1222 // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1223 // a poistion for such spilled LRs
1225 allocateStackSpace4SpilledLRs();
1227 mcInfo.popAllTempValues(TM); // TODO **Check
1229 // color incoming args - if the correct color was not received
1230 // insert code to copy to the correct register
1232 colorIncomingArgs();
1234 // Now update the machine code with register names and add any
1235 // additional code inserted by the register allocator to the instruction
1238 updateMachineCode();
1241 MachineCodeForMethod::get(Meth).dump();
1242 printMachineCode(); // only for DEBUGGING