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->insert(*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 *Val = (const Value *) *ArgIt;
110 ArgRange->insert(Val); // add the arg (def) to it
111 LiveRangeMap[Val] = ArgRange;
113 // create a temp machine op to find the register class of value
114 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
116 unsigned rcid = MRI.getRegClassIDOfValue( Val );
117 ArgRange->setRegClass(RegClassList[ rcid ] );
121 cerr << " adding LiveRange for argument ";
122 printValue((const Value *) *ArgIt); cerr << "\n";
126 // Now suggest hardware registers for these method args
127 MRI.suggestRegs4MethodArgs(Meth, *this);
131 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
135 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
136 for( ; BBI != Meth->end(); ++BBI) { // go thru BBs in random order
138 // Now find all LRs for machine the instructions. A new LR will be created
139 // only for defs in the machine instr since, we assume that all Values are
140 // defined before they are used. However, there can be multiple defs for
141 // the same Value in machine instructions.
143 // get the iterator for machine instructions
144 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
145 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
147 // iterate over all the machine instructions in BB
148 for( ; MInstIterator != MIVec.end(); MInstIterator++) {
150 const MachineInstr * MInst = *MInstIterator;
152 // Now if the machine instruction is a call/return instruction,
153 // add it to CallRetInstrList for processing its implicit operands
155 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
156 TM.getInstrInfo().isCall(MInst->getOpCode()))
157 CallRetInstrList.push_back( MInst );
160 // iterate over MI operands to find defs
161 for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
163 MachineOperand::MachineOperandType OpTyp =
164 OpI.getMachineOperand().getOperandType();
166 if (OpTyp == MachineOperand::MO_CCRegister) {
167 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
168 printValue( OpI.getMachineOperand().getVRegValue() );
173 // create a new LR iff this operand is a def
175 const Value *Def = *OpI;
177 // Only instruction values are accepted for live ranges here
178 if( Def->getValueType() != Value::InstructionVal ) {
179 cerr << "\n**%%Error: Def is not an instruction val. Def=";
180 printValue( Def ); cerr << "\n";
184 LiveRange *DefRange = LiveRangeMap[Def];
186 // see LR already there (because of multiple defs)
187 if( !DefRange) { // if it is not in LiveRangeMap
188 DefRange = new LiveRange(); // creates a new live range and
189 DefRange->insert(Def); // add the instruction (def) to it
190 LiveRangeMap[ Def ] = DefRange; // update the map
193 cerr << " creating a LR for def: ";
194 printValue(Def); cerr << "\n";
197 // set the register class of the new live range
198 //assert( RegClassList.size() );
199 MachineOperand::MachineOperandType OpTy =
200 OpI.getMachineOperand().getOperandType();
202 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
203 unsigned rcid = MRI.getRegClassIDOfValue(
204 OpI.getMachineOperand().getVRegValue(), isCC );
207 if(isCC && DEBUG_RA) {
208 cerr << "\a**created a LR for a CC reg:";
209 printValue( OpI.getMachineOperand().getVRegValue() );
212 DefRange->setRegClass( RegClassList[ rcid ] );
216 DefRange->insert(Def); // add the opearand to def range
217 // update the map - Operand points
219 LiveRangeMap[ Def ] = DefRange;
222 cerr << " added to an existing LR for def: ";
223 printValue( Def ); cerr << "\n";
229 } // for all opereands in machine instructions
231 } // for all machine instructions in the BB
233 } // for all BBs in method
236 // Now we have to suggest clors for call and return arg live ranges.
237 // Also, if there are implicit defs (e.g., retun value of a call inst)
238 // they must be added to the live range list
240 suggestRegs4CallRets();
243 cerr << "Initial Live Ranges constructed!\n";
248 //---------------------------------------------------------------------------
249 // If some live ranges must be colored with specific hardware registers
250 // (e.g., for outgoing call args), suggesting of colors for such live
251 // ranges is done using target specific method. Those methods are called
252 // from this function. The target specific methods must:
253 // 1) suggest colors for call and return args.
254 // 2) create new LRs for implicit defs in machine instructions
255 //---------------------------------------------------------------------------
256 void LiveRangeInfo::suggestRegs4CallRets()
259 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
261 for( ; It != CallRetInstrList.end(); ++It ) {
263 const MachineInstr *MInst = *It;
264 MachineOpCode OpCode = MInst->getOpCode();
266 if( (TM.getInstrInfo()).isReturn(OpCode) )
267 MRI.suggestReg4RetValue( MInst, *this);
269 else if( (TM.getInstrInfo()).isCall( OpCode ) )
270 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
273 assert( 0 && "Non call/ret instr in CallRetInstrList" );
279 //--------------------------------------------------------------------------
280 // The following method coalesces live ranges when possible. This method
281 // must be called after the interference graph has been constructed.
285 for each BB in method
286 for each machine instruction (inst)
287 for each definition (def) in inst
288 for each operand (op) of inst that is a use
289 if the def and op are of the same register type
290 if the def and op do not interfere //i.e., not simultaneously live
291 if (degree(LR of def) + degree(LR of op)) <= # avail regs
292 if both LRs do not have suggested colors
293 merge2IGNodes(def, op) // i.e., merge 2 LRs
296 //---------------------------------------------------------------------------
297 void LiveRangeInfo::coalesceLRs()
300 cerr << "\nCoalscing LRs ...\n";
302 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
304 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
306 // get the iterator for machine instructions
307 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
308 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
310 // iterate over all the machine instructions in BB
311 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
313 const MachineInstr * MInst = *MInstIterator;
316 cerr << " *Iterating over machine instr ";
322 // iterate over MI operands to find defs
323 for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
325 if( DefI.isDef() ) { // iff this operand is a def
327 LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
329 RegClass *const RCOfDef = LROfDef->getRegClass();
331 MachineInstr::val_const_op_iterator UseI(MInst);
332 for( ; !UseI.done(); ++UseI){ // for all uses
334 LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
336 if( ! LROfUse ) { // if LR of use is not found
338 //don't warn about labels
339 if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
340 cerr<<" !! Warning: No LR for use "; printValue(*UseI);
343 continue; // ignore and continue
346 if( LROfUse == LROfDef) // nothing to merge if they are same
349 //RegClass *const RCOfUse = LROfUse->getRegClass();
350 //if( RCOfDef == RCOfUse ) { // if the reg classes are the same
352 if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
354 // If the two RegTypes are the same
356 if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
358 unsigned CombinedDegree =
359 LROfDef->getUserIGNode()->getNumOfNeighbors() +
360 LROfUse->getUserIGNode()->getNumOfNeighbors();
362 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
364 // if both LRs do not have suggested colors
365 if( ! (LROfDef->hasSuggestedColor() &&
366 LROfUse->hasSuggestedColor() ) ) {
368 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
369 unionAndUpdateLRs(LROfDef, LROfUse);
373 } // if combined degree is less than # of regs
375 } // if def and use do not interfere
377 }// if reg classes are the same
385 } // for all machine instructions
390 cerr << "\nCoalscing Done!\n";
398 /*--------------------------- Debug code for printing ---------------*/
401 void LiveRangeInfo::printLiveRanges()
403 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
404 cerr << "\nPrinting Live Ranges from Hash Map:\n";
405 for( ; HMI != LiveRangeMap.end() ; ++HMI) {
406 if( HMI->first && HMI->second ) {
407 cerr <<" "; printValue((*HMI).first); cerr << "\t: ";
408 HMI->second->printSet(); cerr << "\n";