1 #include "llvm/CodeGen/LiveRangeInfo.h"
5 //---------------------------------------------------------------------------
7 //---------------------------------------------------------------------------
8 LiveRangeInfo::LiveRangeInfo(const Method *const M,
9 const TargetMachine& tm,
10 std::vector<RegClass *> &RCL)
11 : Meth(M), LiveRangeMap(), TM(tm),
12 RegClassList(RCL), MRI(tm.getRegInfo())
16 //---------------------------------------------------------------------------
17 // Destructor: Deletes all LiveRanges in the LiveRangeMap
18 //---------------------------------------------------------------------------
19 LiveRangeInfo::~LiveRangeInfo() {
20 LiveRangeMapType::iterator MI = LiveRangeMap.begin();
22 for( ; MI != LiveRangeMap.end() ; ++MI) {
23 if (MI->first && MI->second) {
24 LiveRange *LR = MI->second;
26 // we need to be careful in deleting LiveRanges in LiveRangeMap
27 // since two/more Values in the live range map can point to the same
28 // live range. We have to make the other entries NULL when we delete
31 LiveRange::iterator LI = LR->begin();
33 for( ; LI != LR->end() ; ++LI)
34 LiveRangeMap[*LI] = 0;
42 //---------------------------------------------------------------------------
43 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
44 // Note: the caller must make sure that L1 and L2 are distinct and both
45 // LRs don't have suggested colors
46 //---------------------------------------------------------------------------
47 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
50 L1->setUnion( L2 ); // add elements of L2 to L1
51 ValueSet::iterator L2It;
53 for( L2It = L2->begin() ; L2It != L2->end(); ++L2It) {
55 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
57 L1->add( *L2It ); // add the var in L2 to L1
58 LiveRangeMap[ *L2It ] = L1; // now the elements in L2 should map
63 // Now if LROfDef(L1) has a suggested color, it will remain.
64 // But, if LROfUse(L2) has a suggested color, the new range
65 // must have the same color.
67 if(L2->hasSuggestedColor())
68 L1->setSuggestedColor( L2->getSuggestedColor() );
71 if( L2->isCallInterference() )
72 L1->setCallInterference();
75 L1->addSpillCost( L2->getSpillCost() ); // add the spill costs
77 delete L2; // delete L2 as it is no longer needed
82 //---------------------------------------------------------------------------
83 // Method for constructing all live ranges in a method. It creates live
84 // ranges for all values defined in the instruction stream. Also, it
85 // creates live ranges for all incoming arguments of the method.
86 //---------------------------------------------------------------------------
87 void LiveRangeInfo::constructLiveRanges()
91 cerr << "Consturcting Live Ranges ...\n";
93 // first find the live ranges for all incoming args of the method since
94 // those LRs start from the start of the method
96 // get the argument list
97 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
98 // get an iterator to arg list
99 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
102 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
103 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
104 const Value *const Val = (const Value *) *ArgIt;
108 ArgRange->add(Val); // add the arg (def) to it
109 LiveRangeMap[Val] = ArgRange;
111 // create a temp machine op to find the register class of value
112 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
114 unsigned rcid = MRI.getRegClassIDOfValue( Val );
115 ArgRange->setRegClass(RegClassList[ rcid ] );
119 cerr << " adding LiveRange for argument ";
120 printValue((const Value *) *ArgIt); cerr << "\n";
124 // Now suggest hardware registers for these method args
125 MRI.suggestRegs4MethodArgs(Meth, *this);
129 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
133 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
134 for( ; BBI != Meth->end(); ++BBI) { // go thru BBs in random order
136 // Now find all LRs for machine the instructions. A new LR will be created
137 // only for defs in the machine instr since, we assume that all Values are
138 // defined before they are used. However, there can be multiple defs for
139 // the same Value in machine instructions.
141 // get the iterator for machine instructions
142 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
143 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
145 // iterate over all the machine instructions in BB
146 for( ; MInstIterator != MIVec.end(); MInstIterator++) {
148 const MachineInstr * MInst = *MInstIterator;
150 // Now if the machine instruction is a call/return instruction,
151 // add it to CallRetInstrList for processing its implicit operands
153 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
154 TM.getInstrInfo().isCall(MInst->getOpCode()))
155 CallRetInstrList.push_back( MInst );
158 // iterate over MI operands to find defs
159 for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
161 MachineOperand::MachineOperandType OpTyp =
162 OpI.getMachineOperand().getOperandType();
164 if (OpTyp == MachineOperand::MO_CCRegister) {
165 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
166 printValue( OpI.getMachineOperand().getVRegValue() );
171 // create a new LR iff this operand is a def
173 const Value *const Def = *OpI;
175 // Only instruction values are accepted for live ranges here
176 if( Def->getValueType() != Value::InstructionVal ) {
177 cerr << "\n**%%Error: Def is not an instruction val. Def=";
178 printValue( Def ); cerr << "\n";
182 LiveRange *DefRange = LiveRangeMap[Def];
184 // see LR already there (because of multiple defs)
185 if( !DefRange) { // if it is not in LiveRangeMap
186 DefRange = new LiveRange(); // creates a new live range and
187 DefRange->add( Def ); // add the instruction (def) to it
188 LiveRangeMap[ Def ] = DefRange; // update the map
191 cerr << " creating a LR for def: ";
192 printValue(Def); cerr << "\n";
195 // set the register class of the new live range
196 //assert( RegClassList.size() );
197 MachineOperand::MachineOperandType OpTy =
198 OpI.getMachineOperand().getOperandType();
200 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
201 unsigned rcid = MRI.getRegClassIDOfValue(
202 OpI.getMachineOperand().getVRegValue(), isCC );
205 if(isCC && DEBUG_RA) {
206 cerr << "\a**created a LR for a CC reg:";
207 printValue( OpI.getMachineOperand().getVRegValue() );
210 DefRange->setRegClass( RegClassList[ rcid ] );
214 DefRange->add( Def ); // add the opearand to def range
215 // update the map - Operand points
217 LiveRangeMap[ Def ] = DefRange;
220 cerr << " added to an existing LR for def: ";
221 printValue( Def ); cerr << "\n";
227 } // for all opereands in machine instructions
229 } // for all machine instructions in the BB
231 } // for all BBs in method
234 // Now we have to suggest clors for call and return arg live ranges.
235 // Also, if there are implicit defs (e.g., retun value of a call inst)
236 // they must be added to the live range list
238 suggestRegs4CallRets();
241 cerr << "Initial Live Ranges constructed!\n";
246 //---------------------------------------------------------------------------
247 // If some live ranges must be colored with specific hardware registers
248 // (e.g., for outgoing call args), suggesting of colors for such live
249 // ranges is done using target specific method. Those methods are called
250 // from this function. The target specific methods must:
251 // 1) suggest colors for call and return args.
252 // 2) create new LRs for implicit defs in machine instructions
253 //---------------------------------------------------------------------------
254 void LiveRangeInfo::suggestRegs4CallRets()
257 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
259 for( ; It != CallRetInstrList.end(); ++It ) {
261 const MachineInstr *MInst = *It;
262 MachineOpCode OpCode = MInst->getOpCode();
264 if( (TM.getInstrInfo()).isReturn(OpCode) )
265 MRI.suggestReg4RetValue( MInst, *this);
267 else if( (TM.getInstrInfo()).isCall( OpCode ) )
268 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
271 assert( 0 && "Non call/ret instr in CallRetInstrList" );
277 //--------------------------------------------------------------------------
278 // The following method coalesces live ranges when possible. This method
279 // must be called after the interference graph has been constructed.
283 for each BB in method
284 for each machine instruction (inst)
285 for each definition (def) in inst
286 for each operand (op) of inst that is a use
287 if the def and op are of the same register type
288 if the def and op do not interfere //i.e., not simultaneously live
289 if (degree(LR of def) + degree(LR of op)) <= # avail regs
290 if both LRs do not have suggested colors
291 merge2IGNodes(def, op) // i.e., merge 2 LRs
294 //---------------------------------------------------------------------------
295 void LiveRangeInfo::coalesceLRs()
298 cerr << "\nCoalscing LRs ...\n";
300 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
302 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
304 // get the iterator for machine instructions
305 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
306 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
308 // iterate over all the machine instructions in BB
309 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
311 const MachineInstr * MInst = *MInstIterator;
314 cerr << " *Iterating over machine instr ";
320 // iterate over MI operands to find defs
321 for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
323 if( DefI.isDef() ) { // iff this operand is a def
325 LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
327 RegClass *const RCOfDef = LROfDef->getRegClass();
329 MachineInstr::val_const_op_iterator UseI(MInst);
330 for( ; !UseI.done(); ++UseI){ // for all uses
332 LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
334 if( ! LROfUse ) { // if LR of use is not found
336 //don't warn about labels
337 if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
338 cerr<<" !! Warning: No LR for use "; printValue(*UseI);
341 continue; // ignore and continue
344 if( LROfUse == LROfDef) // nothing to merge if they are same
347 //RegClass *const RCOfUse = LROfUse->getRegClass();
348 //if( RCOfDef == RCOfUse ) { // if the reg classes are the same
350 if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
352 // If the two RegTypes are the same
354 if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
356 unsigned CombinedDegree =
357 LROfDef->getUserIGNode()->getNumOfNeighbors() +
358 LROfUse->getUserIGNode()->getNumOfNeighbors();
360 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
362 // if both LRs do not have suggested colors
363 if( ! (LROfDef->hasSuggestedColor() &&
364 LROfUse->hasSuggestedColor() ) ) {
366 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
367 unionAndUpdateLRs(LROfDef, LROfUse);
371 } // if combined degree is less than # of regs
373 } // if def and use do not interfere
375 }// if reg classes are the same
383 } // for all machine instructions
388 cerr << "\nCoalscing Done!\n";
396 /*--------------------------- Debug code for printing ---------------*/
399 void LiveRangeInfo::printLiveRanges()
401 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
402 cerr << "\nPrinting Live Ranges from Hash Map:\n";
403 for( ; HMI != LiveRangeMap.end() ; ++HMI) {
404 if( HMI->first && HMI->second ) {
405 cerr <<" "; printValue((*HMI).first); cerr << "\t: ";
406 HMI->second->printSet(); cerr << "\n";