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)
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 //---------------------------------------------------------------------------
52 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
53 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
54 set_union(*L1, *L2); // add elements of L2 to L1
56 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
57 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
59 L1->insert(*L2It); // add the var in L2 to L1
60 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
65 // Now if LROfDef(L1) has a suggested color, it will remain.
66 // But, if LROfUse(L2) has a suggested color, the new range
67 // must have the same color.
69 if(L2->hasSuggestedColor())
70 L1->setSuggestedColor(L2->getSuggestedColor());
73 if (L2->isCallInterference())
74 L1->setCallInterference();
76 // add the spill costs
77 L1->addSpillCost(L2->getSpillCost());
79 delete L2; // delete L2 as it is no longer needed
84 //---------------------------------------------------------------------------
85 // Method for constructing all live ranges in a method. It creates live
86 // ranges for all values defined in the instruction stream. Also, it
87 // creates live ranges for all incoming arguments of the method.
88 //---------------------------------------------------------------------------
89 void LiveRangeInfo::constructLiveRanges()
93 cerr << "Consturcting Live Ranges ...\n";
95 // first find the live ranges for all incoming args of the method since
96 // those LRs start from the start of the method
98 // get the argument list
99 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
100 // get an iterator to arg list
101 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
104 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
105 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
106 const Value *Val = (const Value *) *ArgIt;
108 ArgRange->insert(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 << RAV((const Value *)*ArgIt) << "\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 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
169 // create a new LR iff this operand is a def
171 const Value *Def = *OpI;
173 // Only instruction values are accepted for live ranges here
174 if (Def->getValueType() != Value::InstructionVal ) {
175 cerr << "\n**%%Error: Def is not an instruction val. Def="
180 LiveRange *DefRange = LiveRangeMap[Def];
182 // see LR already there (because of multiple defs)
183 if( !DefRange) { // if it is not in LiveRangeMap
184 DefRange = new LiveRange(); // creates a new live range and
185 DefRange->insert(Def); // add the instruction (def) to it
186 LiveRangeMap[ Def ] = DefRange; // update the map
189 cerr << " creating a LR for def: " << RAV(Def) << "\n";
191 // set the register class of the new live range
192 //assert( RegClassList.size() );
193 MachineOperand::MachineOperandType OpTy =
194 OpI.getMachineOperand().getOperandType();
196 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
197 unsigned rcid = MRI.getRegClassIDOfValue(
198 OpI.getMachineOperand().getVRegValue(), isCC );
201 if (isCC && DEBUG_RA)
202 cerr << "\a**created a LR for a CC reg:"
203 << RAV(OpI.getMachineOperand().getVRegValue());
205 DefRange->setRegClass(RegClassList[rcid]);
207 DefRange->insert(Def); // add the opearand to def range
208 // update the map - Operand points
210 LiveRangeMap[Def] = DefRange;
213 cerr << " added to an existing LR for def: "
219 } // for all opereands in machine instructions
221 } // for all machine instructions in the BB
223 } // for all BBs in method
226 // Now we have to suggest clors for call and return arg live ranges.
227 // Also, if there are implicit defs (e.g., retun value of a call inst)
228 // they must be added to the live range list
230 suggestRegs4CallRets();
233 cerr << "Initial Live Ranges constructed!\n";
238 //---------------------------------------------------------------------------
239 // If some live ranges must be colored with specific hardware registers
240 // (e.g., for outgoing call args), suggesting of colors for such live
241 // ranges is done using target specific method. Those methods are called
242 // from this function. The target specific methods must:
243 // 1) suggest colors for call and return args.
244 // 2) create new LRs for implicit defs in machine instructions
245 //---------------------------------------------------------------------------
246 void LiveRangeInfo::suggestRegs4CallRets()
249 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
251 for( ; It != CallRetInstrList.end(); ++It ) {
253 const MachineInstr *MInst = *It;
254 MachineOpCode OpCode = MInst->getOpCode();
256 if( (TM.getInstrInfo()).isReturn(OpCode) )
257 MRI.suggestReg4RetValue( MInst, *this);
259 else if( (TM.getInstrInfo()).isCall( OpCode ) )
260 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
263 assert( 0 && "Non call/ret instr in CallRetInstrList" );
269 //--------------------------------------------------------------------------
270 // The following method coalesces live ranges when possible. This method
271 // must be called after the interference graph has been constructed.
275 for each BB in method
276 for each machine instruction (inst)
277 for each definition (def) in inst
278 for each operand (op) of inst that is a use
279 if the def and op are of the same register type
280 if the def and op do not interfere //i.e., not simultaneously live
281 if (degree(LR of def) + degree(LR of op)) <= # avail regs
282 if both LRs do not have suggested colors
283 merge2IGNodes(def, op) // i.e., merge 2 LRs
286 //---------------------------------------------------------------------------
287 void LiveRangeInfo::coalesceLRs()
290 cerr << "\nCoalscing LRs ...\n";
292 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
294 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
296 // get the iterator for machine instructions
297 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
298 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
300 // iterate over all the machine instructions in BB
301 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
303 const MachineInstr * MInst = *MInstIterator;
306 cerr << " *Iterating over machine instr ";
312 // iterate over MI operands to find defs
313 for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
315 if( DefI.isDef() ) { // iff this operand is a def
317 LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
319 RegClass *const RCOfDef = LROfDef->getRegClass();
321 MachineInstr::val_const_op_iterator UseI(MInst);
322 for( ; !UseI.done(); ++UseI){ // for all uses
324 LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
326 if( ! LROfUse ) { // if LR of use is not found
328 //don't warn about labels
329 if (!((*UseI)->getType())->isLabelType() && DEBUG_RA)
330 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
331 continue; // ignore and continue
334 if( LROfUse == LROfDef) // nothing to merge if they are same
337 //RegClass *const RCOfUse = LROfUse->getRegClass();
338 //if( RCOfDef == RCOfUse ) { // if the reg classes are the same
340 if( MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse) ) {
342 // If the two RegTypes are the same
344 if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
346 unsigned CombinedDegree =
347 LROfDef->getUserIGNode()->getNumOfNeighbors() +
348 LROfUse->getUserIGNode()->getNumOfNeighbors();
350 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
352 // if both LRs do not have suggested colors
353 if( ! (LROfDef->hasSuggestedColor() &&
354 LROfUse->hasSuggestedColor() ) ) {
356 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
357 unionAndUpdateLRs(LROfDef, LROfUse);
361 } // if combined degree is less than # of regs
363 } // if def and use do not interfere
365 }// if reg classes are the same
373 } // for all machine instructions
378 cerr << "\nCoalscing Done!\n";
386 /*--------------------------- Debug code for printing ---------------*/
389 void LiveRangeInfo::printLiveRanges() {
390 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
391 cerr << "\nPrinting Live Ranges from Hash Map:\n";
392 for( ; HMI != LiveRangeMap.end(); ++HMI) {
393 if (HMI->first && HMI->second) {
394 cerr << " " << RAV(HMI->first) << "\t: ";
395 printSet(*HMI->second); cerr << "\n";