1 #include "llvm/CodeGen/LiveRangeInfo.h"
2 #include "llvm/CodeGen/RegClass.h"
3 #include "llvm/CodeGen/MachineInstr.h"
4 #include "llvm/Target/TargetMachine.h"
5 #include "llvm/Method.h"
9 //---------------------------------------------------------------------------
11 //---------------------------------------------------------------------------
12 LiveRangeInfo::LiveRangeInfo(const Method *const M,
13 const TargetMachine& tm,
14 std::vector<RegClass *> &RCL)
15 : Meth(M), LiveRangeMap(), TM(tm),
16 RegClassList(RCL), MRI(tm.getRegInfo())
20 //---------------------------------------------------------------------------
21 // Destructor: Deletes all LiveRanges in the LiveRangeMap
22 //---------------------------------------------------------------------------
23 LiveRangeInfo::~LiveRangeInfo() {
24 LiveRangeMapType::iterator MI = LiveRangeMap.begin();
26 for( ; MI != LiveRangeMap.end() ; ++MI) {
27 if (MI->first && MI->second) {
28 LiveRange *LR = MI->second;
30 // we need to be careful in deleting LiveRanges in LiveRangeMap
31 // since two/more Values in the live range map can point to the same
32 // live range. We have to make the other entries NULL when we delete
35 LiveRange::iterator LI = LR->begin();
37 for( ; LI != LR->end() ; ++LI)
38 LiveRangeMap[*LI] = 0;
46 //---------------------------------------------------------------------------
47 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
48 // Note: the caller must make sure that L1 and L2 are distinct and both
49 // LRs don't have suggested colors
50 //---------------------------------------------------------------------------
51 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
54 L1->setUnion( L2 ); // add elements of L2 to L1
55 ValueSet::iterator L2It;
57 for( L2It = L2->begin() ; L2It != L2->end(); ++L2It) {
59 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
61 L1->add( *L2It ); // add the var in L2 to L1
62 LiveRangeMap[ *L2It ] = L1; // now the elements in L2 should map
67 // Now if LROfDef(L1) has a suggested color, it will remain.
68 // But, if LROfUse(L2) has a suggested color, the new range
69 // must have the same color.
71 if(L2->hasSuggestedColor())
72 L1->setSuggestedColor( L2->getSuggestedColor() );
75 if( L2->isCallInterference() )
76 L1->setCallInterference();
79 L1->addSpillCost( L2->getSpillCost() ); // add the spill costs
81 delete L2; // delete L2 as it is no longer needed
86 //---------------------------------------------------------------------------
87 // Method for constructing all live ranges in a method. It creates live
88 // ranges for all values defined in the instruction stream. Also, it
89 // creates live ranges for all incoming arguments of the method.
90 //---------------------------------------------------------------------------
91 void LiveRangeInfo::constructLiveRanges()
95 cerr << "Consturcting Live Ranges ...\n";
97 // first find the live ranges for all incoming args of the method since
98 // those LRs start from the start of the method
100 // get the argument list
101 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
102 // get an iterator to arg list
103 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
106 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
107 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
108 const Value *const Val = (const Value *) *ArgIt;
112 ArgRange->add(Val); // add the arg (def) to it
113 LiveRangeMap[Val] = ArgRange;
115 // create a temp machine op to find the register class of value
116 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
118 unsigned rcid = MRI.getRegClassIDOfValue( Val );
119 ArgRange->setRegClass(RegClassList[ rcid ] );
123 cerr << " adding LiveRange for argument ";
124 printValue((const Value *) *ArgIt); cerr << "\n";
128 // Now suggest hardware registers for these method args
129 MRI.suggestRegs4MethodArgs(Meth, *this);
133 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
137 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
138 for( ; BBI != Meth->end(); ++BBI) { // go thru BBs in random order
140 // Now find all LRs for machine the instructions. A new LR will be created
141 // only for defs in the machine instr since, we assume that all Values are
142 // defined before they are used. However, there can be multiple defs for
143 // the same Value in machine instructions.
145 // get the iterator for machine instructions
146 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
147 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
149 // iterate over all the machine instructions in BB
150 for( ; MInstIterator != MIVec.end(); MInstIterator++) {
152 const MachineInstr * MInst = *MInstIterator;
154 // Now if the machine instruction is a call/return instruction,
155 // add it to CallRetInstrList for processing its implicit operands
157 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
158 TM.getInstrInfo().isCall(MInst->getOpCode()))
159 CallRetInstrList.push_back( MInst );
162 // iterate over MI operands to find defs
163 for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
165 MachineOperand::MachineOperandType OpTyp =
166 OpI.getMachineOperand().getOperandType();
168 if (OpTyp == MachineOperand::MO_CCRegister) {
169 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
170 printValue( OpI.getMachineOperand().getVRegValue() );
175 // create a new LR iff this operand is a def
177 const Value *const Def = *OpI;
179 // Only instruction values are accepted for live ranges here
180 if( Def->getValueType() != Value::InstructionVal ) {
181 cerr << "\n**%%Error: Def is not an instruction val. Def=";
182 printValue( Def ); cerr << "\n";
186 LiveRange *DefRange = LiveRangeMap[Def];
188 // see LR already there (because of multiple defs)
189 if( !DefRange) { // if it is not in LiveRangeMap
190 DefRange = new LiveRange(); // creates a new live range and
191 DefRange->add( Def ); // add the instruction (def) to it
192 LiveRangeMap[ Def ] = DefRange; // update the map
195 cerr << " creating a LR for def: ";
196 printValue(Def); cerr << "\n";
199 // set the register class of the new live range
200 //assert( RegClassList.size() );
201 MachineOperand::MachineOperandType OpTy =
202 OpI.getMachineOperand().getOperandType();
204 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
205 unsigned rcid = MRI.getRegClassIDOfValue(
206 OpI.getMachineOperand().getVRegValue(), isCC );
209 if(isCC && DEBUG_RA) {
210 cerr << "\a**created a LR for a CC reg:";
211 printValue( OpI.getMachineOperand().getVRegValue() );
214 DefRange->setRegClass( RegClassList[ rcid ] );
218 DefRange->add( Def ); // add the opearand to def range
219 // update the map - Operand points
221 LiveRangeMap[ Def ] = DefRange;
224 cerr << " added to an existing LR for def: ";
225 printValue( Def ); cerr << "\n";
231 } // for all opereands in machine instructions
233 } // for all machine instructions in the BB
235 } // for all BBs in method
238 // Now we have to suggest clors for call and return arg live ranges.
239 // Also, if there are implicit defs (e.g., retun value of a call inst)
240 // they must be added to the live range list
242 suggestRegs4CallRets();
245 cerr << "Initial Live Ranges constructed!\n";
250 //---------------------------------------------------------------------------
251 // If some live ranges must be colored with specific hardware registers
252 // (e.g., for outgoing call args), suggesting of colors for such live
253 // ranges is done using target specific method. Those methods are called
254 // from this function. The target specific methods must:
255 // 1) suggest colors for call and return args.
256 // 2) create new LRs for implicit defs in machine instructions
257 //---------------------------------------------------------------------------
258 void LiveRangeInfo::suggestRegs4CallRets()
261 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
263 for( ; It != CallRetInstrList.end(); ++It ) {
265 const MachineInstr *MInst = *It;
266 MachineOpCode OpCode = MInst->getOpCode();
268 if( (TM.getInstrInfo()).isReturn(OpCode) )
269 MRI.suggestReg4RetValue( MInst, *this);
271 else if( (TM.getInstrInfo()).isCall( OpCode ) )
272 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
275 assert( 0 && "Non call/ret instr in CallRetInstrList" );
281 //--------------------------------------------------------------------------
282 // The following method coalesces live ranges when possible. This method
283 // must be called after the interference graph has been constructed.
287 for each BB in method
288 for each machine instruction (inst)
289 for each definition (def) in inst
290 for each operand (op) of inst that is a use
291 if the def and op are of the same register type
292 if the def and op do not interfere //i.e., not simultaneously live
293 if (degree(LR of def) + degree(LR of op)) <= # avail regs
294 if both LRs do not have suggested colors
295 merge2IGNodes(def, op) // i.e., merge 2 LRs
298 //---------------------------------------------------------------------------
299 void LiveRangeInfo::coalesceLRs()
302 cerr << "\nCoalscing LRs ...\n";
304 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
306 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
308 // get the iterator for machine instructions
309 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
310 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
312 // iterate over all the machine instructions in BB
313 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
315 const MachineInstr * MInst = *MInstIterator;
318 cerr << " *Iterating over machine instr ";
324 // iterate over MI operands to find defs
325 for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
327 if( DefI.isDef() ) { // iff this operand is a def
329 LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
331 RegClass *const RCOfDef = LROfDef->getRegClass();
333 MachineInstr::val_const_op_iterator UseI(MInst);
334 for( ; !UseI.done(); ++UseI){ // for all uses
336 LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
338 if( ! LROfUse ) { // if LR of use is not found
340 //don't warn about labels
341 if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
342 cerr<<" !! Warning: No LR for use "; printValue(*UseI);
345 continue; // ignore and continue
348 if( LROfUse == LROfDef) // nothing to merge if they are same
351 //RegClass *const RCOfUse = LROfUse->getRegClass();
352 //if( RCOfDef == RCOfUse ) { // if the reg classes are the same
354 if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
356 // If the two RegTypes are the same
358 if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
360 unsigned CombinedDegree =
361 LROfDef->getUserIGNode()->getNumOfNeighbors() +
362 LROfUse->getUserIGNode()->getNumOfNeighbors();
364 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
366 // if both LRs do not have suggested colors
367 if( ! (LROfDef->hasSuggestedColor() &&
368 LROfUse->hasSuggestedColor() ) ) {
370 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
371 unionAndUpdateLRs(LROfDef, LROfUse);
375 } // if combined degree is less than # of regs
377 } // if def and use do not interfere
379 }// if reg classes are the same
387 } // for all machine instructions
392 cerr << "\nCoalscing Done!\n";
400 /*--------------------------- Debug code for printing ---------------*/
403 void LiveRangeInfo::printLiveRanges()
405 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
406 cerr << "\nPrinting Live Ranges from Hash Map:\n";
407 for( ; HMI != LiveRangeMap.end() ; ++HMI) {
408 if( HMI->first && HMI->second ) {
409 cerr <<" "; printValue((*HMI).first); cerr << "\t: ";
410 HMI->second->printSet(); cerr << "\n";