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 << RAV((const Value *)*ArgIt) << "\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 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
171 // create a new LR iff this operand is a def
173 const Value *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="
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->insert(Def); // add the instruction (def) to it
188 LiveRangeMap[ Def ] = DefRange; // update the map
191 cerr << " creating a LR for def: " << RAV(Def) << "\n";
193 // set the register class of the new live range
194 //assert( RegClassList.size() );
195 MachineOperand::MachineOperandType OpTy =
196 OpI.getMachineOperand().getOperandType();
198 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
199 unsigned rcid = MRI.getRegClassIDOfValue(
200 OpI.getMachineOperand().getVRegValue(), isCC );
203 if (isCC && DEBUG_RA)
204 cerr << "\a**created a LR for a CC reg:"
205 << RAV(OpI.getMachineOperand().getVRegValue());
207 DefRange->setRegClass(RegClassList[rcid]);
209 DefRange->insert(Def); // add the opearand to def range
210 // update the map - Operand points
212 LiveRangeMap[Def] = DefRange;
215 cerr << " added to an existing LR for def: "
221 } // for all opereands in machine instructions
223 } // for all machine instructions in the BB
225 } // for all BBs in method
228 // Now we have to suggest clors for call and return arg live ranges.
229 // Also, if there are implicit defs (e.g., retun value of a call inst)
230 // they must be added to the live range list
232 suggestRegs4CallRets();
235 cerr << "Initial Live Ranges constructed!\n";
240 //---------------------------------------------------------------------------
241 // If some live ranges must be colored with specific hardware registers
242 // (e.g., for outgoing call args), suggesting of colors for such live
243 // ranges is done using target specific method. Those methods are called
244 // from this function. The target specific methods must:
245 // 1) suggest colors for call and return args.
246 // 2) create new LRs for implicit defs in machine instructions
247 //---------------------------------------------------------------------------
248 void LiveRangeInfo::suggestRegs4CallRets()
251 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
253 for( ; It != CallRetInstrList.end(); ++It ) {
255 const MachineInstr *MInst = *It;
256 MachineOpCode OpCode = MInst->getOpCode();
258 if( (TM.getInstrInfo()).isReturn(OpCode) )
259 MRI.suggestReg4RetValue( MInst, *this);
261 else if( (TM.getInstrInfo()).isCall( OpCode ) )
262 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
265 assert( 0 && "Non call/ret instr in CallRetInstrList" );
271 //--------------------------------------------------------------------------
272 // The following method coalesces live ranges when possible. This method
273 // must be called after the interference graph has been constructed.
277 for each BB in method
278 for each machine instruction (inst)
279 for each definition (def) in inst
280 for each operand (op) of inst that is a use
281 if the def and op are of the same register type
282 if the def and op do not interfere //i.e., not simultaneously live
283 if (degree(LR of def) + degree(LR of op)) <= # avail regs
284 if both LRs do not have suggested colors
285 merge2IGNodes(def, op) // i.e., merge 2 LRs
288 //---------------------------------------------------------------------------
289 void LiveRangeInfo::coalesceLRs()
292 cerr << "\nCoalscing LRs ...\n";
294 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
296 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
298 // get the iterator for machine instructions
299 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
300 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
302 // iterate over all the machine instructions in BB
303 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
305 const MachineInstr * MInst = *MInstIterator;
308 cerr << " *Iterating over machine instr ";
314 // iterate over MI operands to find defs
315 for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
317 if( DefI.isDef() ) { // iff this operand is a def
319 LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
321 RegClass *const RCOfDef = LROfDef->getRegClass();
323 MachineInstr::val_const_op_iterator UseI(MInst);
324 for( ; !UseI.done(); ++UseI){ // for all uses
326 LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
328 if( ! LROfUse ) { // if LR of use is not found
330 //don't warn about labels
331 if (!((*UseI)->getType())->isLabelType() && DEBUG_RA)
332 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
333 continue; // ignore and continue
336 if( LROfUse == LROfDef) // nothing to merge if they are same
339 //RegClass *const RCOfUse = LROfUse->getRegClass();
340 //if( RCOfDef == RCOfUse ) { // if the reg classes are the same
342 if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
344 // If the two RegTypes are the same
346 if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
348 unsigned CombinedDegree =
349 LROfDef->getUserIGNode()->getNumOfNeighbors() +
350 LROfUse->getUserIGNode()->getNumOfNeighbors();
352 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
354 // if both LRs do not have suggested colors
355 if( ! (LROfDef->hasSuggestedColor() &&
356 LROfUse->hasSuggestedColor() ) ) {
358 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
359 unionAndUpdateLRs(LROfDef, LROfUse);
363 } // if combined degree is less than # of regs
365 } // if def and use do not interfere
367 }// if reg classes are the same
375 } // for all machine instructions
380 cerr << "\nCoalscing Done!\n";
388 /*--------------------------- Debug code for printing ---------------*/
391 void LiveRangeInfo::printLiveRanges() {
392 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
393 cerr << "\nPrinting Live Ranges from Hash Map:\n";
394 for( ; HMI != LiveRangeMap.end(); ++HMI) {
395 if (HMI->first && HMI->second) {
396 cerr << " " << RAV(HMI->first) << "\t: ";
397 HMI->second->printSet(); cerr << "\n";