1 #include "llvm/CodeGen/PhyRegAlloc.h"
6 //----------------------------------------------------------------------------
7 // Constructor: Init local composite objects and create register classes.
8 //----------------------------------------------------------------------------
9 PhyRegAlloc::PhyRegAlloc(const Method *const M,
10 const TargetMachine& tm,
11 MethodLiveVarInfo *const Lvi)
13 Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList),
14 MRI( tm.getRegInfo() ),
15 NumOfRegClasses(MRI.getNumOfRegClasses()),
21 // **TODO: use an actual reserved color list
22 ReservedColorListType *RCL = new ReservedColorListType();
24 // create each RegisterClass and put in RegClassList
25 for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
26 RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc), RCL) );
30 //----------------------------------------------------------------------------
31 // This method initally creates interference graphs (one in each reg class)
32 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
33 //----------------------------------------------------------------------------
35 void PhyRegAlloc::createIGNodeListsAndIGs()
37 if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
40 LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
43 LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
45 for( ; HMI != HMIEnd ; ++HMI ) {
47 LiveRange *L = (*HMI).second; // get the LiveRange
50 // if the Value * is not null, and LR
51 // is not yet written to the IGNodeList
52 if( !(L->getUserIGNode()) ) {
54 RegClass *const RC = // RegClass of first value in the LR
55 //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
56 RegClassList[ L->getRegClass()->getID() ];
58 RC-> addLRToIG( L ); // add this LR to an IG
64 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
65 RegClassList[ rc ]->createInterferenceGraph();
68 cout << "LRLists Created!" << endl;
73 //----------------------------------------------------------------------------
74 // This method will add all interferences at for a given instruction.
75 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
76 // class as that of live var. The live var passed to this function is the
77 // LVset AFTER the instruction
78 //----------------------------------------------------------------------------
80 void PhyRegAlloc::addInterference(const Value *const Def,
81 const LiveVarSet *const LVSet,
82 const bool isCallInst) {
84 LiveVarSet::const_iterator LIt = LVSet->begin();
86 // get the live range of instruction
87 const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
89 IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
90 assert( IGNodeOfDef );
92 RegClass *const RCOfDef = LROfDef->getRegClass();
94 // for each live var in live variable set
95 for( ; LIt != LVSet->end(); ++LIt) {
98 cout << "< Def="; printValue(Def);
99 cout << ", Lvar="; printValue( *LIt); cout << "> ";
102 // get the live range corresponding to live var
103 LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
105 // LROfVar can be null if it is a const since a const
106 // doesn't have a dominating def - see Assumptions above
109 if(LROfDef == LROfVar) // do not set interf for same LR
112 // if 2 reg classes are the same set interference
113 if( RCOfDef == LROfVar->getRegClass() ){
114 RCOfDef->setInterference( LROfDef, LROfVar);
118 //the live range of this var interferes with this call
120 LROfVar->addCallInterference( (const Instruction *const) Def );
123 else if(DEBUG_RA > 1) {
124 // we will not have LRs for values not explicitly allocated in the
125 // instruction stream (e.g., constants)
126 cout << " warning: no live range for " ;
127 printValue( *LIt); cout << endl; }
133 //----------------------------------------------------------------------------
134 // This method will walk thru code and create interferences in the IG of
136 //----------------------------------------------------------------------------
138 void PhyRegAlloc::buildInterferenceGraphs()
141 if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
143 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
145 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
147 // get the iterator for machine instructions
148 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
149 MachineCodeForBasicBlock::const_iterator
150 MInstIterator = MIVec.begin();
152 // iterate over all the machine instructions in BB
153 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
155 const MachineInstr *const MInst = *MInstIterator;
157 // get the LV set after the instruction
158 const LiveVarSet *const LVSetAI =
159 LVI->getLiveVarSetAfterMInst(MInst, *BBI);
161 const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
163 // iterate over MI operands to find defs
164 for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
167 // create a new LR iff this operand is a def
168 addInterference(*OpI, LVSetAI, isCallInst );
172 } // for all operands
174 } // for all machine instructions in BB
177 // go thru LLVM instructions in the basic block and record all CALL
178 // instructions and Return instructions in the CallInstrList
179 // This is done because since there are no reverse pointers in machine
180 // instructions to find the llvm instruction, when we encounter a call
181 // or a return whose args must be specailly colored (e.g., %o's for args)
182 BasicBlock::const_iterator InstIt = (*BBI)->begin();
184 for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
185 unsigned OpCode = (*InstIt)->getOpcode();
187 if( OpCode == Instruction::Call )
188 CallInstrList.push_back( *InstIt );
190 else if( OpCode == Instruction::Ret )
191 RetInstrList.push_back( *InstIt );
194 } // for all BBs in method
197 // add interferences for method arguments. Since there are no explict
198 // defs in method for args, we have to add them manually
200 addInterferencesForArgs(); // add interference for method args
203 cout << "Interference graphs calculted!" << endl;
210 //----------------------------------------------------------------------------
211 // This method will add interferences for incoming arguments to a method.
212 //----------------------------------------------------------------------------
213 void PhyRegAlloc::addInterferencesForArgs()
215 // get the InSet of root BB
216 const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
218 // get the argument list
219 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
221 // get an iterator to arg list
222 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
225 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
226 addInterference( *ArgIt, InSet, false ); // add interferences between
227 // args and LVars at start
229 cout << " - %% adding interference for argument ";
230 printValue( (const Value *) *ArgIt); cout << endl;
236 //----------------------------------------------------------------------------
237 // This method is called after register allocation is complete to set the
238 // allocated reisters in the machine code. This code will add register numbers
239 // to MachineOperands that contain a Value.
240 //----------------------------------------------------------------------------
242 void PhyRegAlloc::updateMachineCode()
245 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
247 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
249 // get the iterator for machine instructions
250 MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
251 MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
253 // iterate over all the machine instructions in BB
254 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
256 MachineInstr *const MInst = *MInstIterator;
258 //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
260 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
262 MachineOperand& Op = MInst->getOperand(OpNum);
264 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
265 Op.getOperandType() == MachineOperand::MO_CCRegister) {
267 const Value *const Val = Op.getVRegValue();
269 // delete this condition checking later (must assert if Val is null)
270 if( !Val && DEBUG_RA) {
271 cout << "Warning: NULL Value found for operand" << endl;
274 assert( Val && "Value is NULL");
276 const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
280 // nothing to worry if it's a const or a label
283 cout << "*NO LR for inst opcode: ";
284 cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
287 Op.setRegForValue( -1 ); // mark register as invalid
289 if( ((Val->getType())->isLabelType()) ||
290 (Val->getValueType() == Value::ConstantVal) )
293 // The return address is not explicitly defined within a
294 // method. So, it is not colored by usual algorithm. In that case
297 //else if (TM.getInstrInfo().isCall(MInst->getOpCode()))
298 //Op.setRegForValue( MRI.getCallAddressReg() );
300 //TM.getInstrInfo().isReturn(MInst->getOpCode())
301 else if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ) {
302 if (DEBUG_RA) cout << endl << "RETURN found" << endl;
303 Op.setRegForValue( MRI.getReturnAddressReg() );
309 cout << "!Warning: No LiveRange for: ";
310 printValue( Val); cout << " Type: " << Val->getValueType();
311 cout << " RegVal=" << Op.getAllocatedRegNum() << endl;
317 unsigned RCID = (LR->getRegClass())->getID();
319 Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
321 int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
334 //----------------------------------------------------------------------------
335 // This method prints the code with registers after register allocation is
337 //----------------------------------------------------------------------------
338 void PhyRegAlloc::printMachineCode()
341 cout << endl << ";************** Method ";
342 cout << Meth->getName() << " *****************" << endl;
344 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
346 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
348 cout << endl ; printLabel( *BBI); cout << ": ";
350 // get the iterator for machine instructions
351 MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
352 MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
354 // iterate over all the machine instructions in BB
355 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
357 MachineInstr *const MInst = *MInstIterator;
360 cout << endl << "\t";
361 cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
364 //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
366 for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
368 MachineOperand& Op = MInst->getOperand(OpNum);
370 if( Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
371 Op.getOperandType() == MachineOperand::MO_CCRegister ||
372 Op.getOperandType() == MachineOperand::MO_PCRelativeDisp ) {
376 const Value *const Val = Op.getVRegValue () ;
377 // ****this code is temporary till NULL Values are fixed
379 cout << "\t<*NULL*>";
383 // if a label or a constant
384 if( (Val->getValueType() == Value::BasicBlockVal) ||
385 (Val->getValueType() == Value::ConstantVal) ) {
387 cout << "\t"; printLabel( Op.getVRegValue () );
390 // else it must be a register value
391 const int RegNum = Op.getAllocatedRegNum();
393 cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
398 else if(Op.getOperandType() == MachineOperand::MO_MachineRegister) {
399 cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
403 cout << "\t" << Op; // use dump field
417 //----------------------------------------------------------------------------
418 // Used to generate a label for a basic block
419 //----------------------------------------------------------------------------
420 void PhyRegAlloc::printLabel(const Value *const Val)
423 cout << Val->getName();
425 cout << "Label" << Val;
429 //----------------------------------------------------------------------------
430 // The entry pont to Register Allocation
431 //----------------------------------------------------------------------------
433 void PhyRegAlloc::allocateRegisters()
435 constructLiveRanges(); // create LR info
438 LRI.printLiveRanges();
440 createIGNodeListsAndIGs(); // create IGNode list and IGs
442 buildInterferenceGraphs(); // build IGs in all reg classes
446 // print all LRs in all reg classes
447 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
448 RegClassList[ rc ]->printIGNodeList();
450 // print IGs in all register classes
451 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
452 RegClassList[ rc ]->printIG();
455 LRI.coalesceLRs(); // coalesce all live ranges
458 // print all LRs in all reg classes
459 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
460 RegClassList[ rc ]->printIGNodeList();
462 // print IGs in all register classes
463 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
464 RegClassList[ rc ]->printIG();
468 // the following three calls must be made in that order since
469 // coloring or definitions must come before their uses
470 MRI.colorArgs(Meth, LRI); // color method args
471 // color call args of call instrns
472 MRI.colorCallArgs(CallInstrList, LRI, AddedInstrMap);
474 MRI.colorRetArg(CallInstrList, LRI, AddedInstrMap);
478 // color all register classes
479 for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
480 RegClassList[ rc ]->colorAllRegs();
483 PrintMachineInstructions(Meth);
484 printMachineCode(); // only for DEBUGGING