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"
6 #include "Support/SetOperations.h"
10 //---------------------------------------------------------------------------
12 //---------------------------------------------------------------------------
13 LiveRangeInfo::LiveRangeInfo(const Method *const M,
14 const TargetMachine& tm,
15 std::vector<RegClass *> &RCL)
17 RegClassList(RCL), MRI(tm.getRegInfo())
21 //---------------------------------------------------------------------------
22 // Destructor: Deletes all LiveRanges in the LiveRangeMap
23 //---------------------------------------------------------------------------
24 LiveRangeInfo::~LiveRangeInfo() {
25 LiveRangeMapType::iterator MI = LiveRangeMap.begin();
27 for( ; MI != LiveRangeMap.end() ; ++MI) {
28 if (MI->first && MI->second) {
29 LiveRange *LR = MI->second;
31 // we need to be careful in deleting LiveRanges in LiveRangeMap
32 // since two/more Values in the live range map can point to the same
33 // live range. We have to make the other entries NULL when we delete
36 LiveRange::iterator LI = LR->begin();
38 for( ; LI != LR->end() ; ++LI)
39 LiveRangeMap[*LI] = 0;
47 //---------------------------------------------------------------------------
48 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
49 // Note: the caller must make sure that L1 and L2 are distinct and both
50 // LRs don't have suggested colors
51 //---------------------------------------------------------------------------
53 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
54 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
55 set_union(*L1, *L2); // add elements of L2 to L1
57 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
58 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
60 L1->insert(*L2It); // add the var in L2 to L1
61 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
66 // Now if LROfDef(L1) has a suggested color, it will remain.
67 // But, if LROfUse(L2) has a suggested color, the new range
68 // must have the same color.
70 if(L2->hasSuggestedColor())
71 L1->setSuggestedColor(L2->getSuggestedColor());
74 if (L2->isCallInterference())
75 L1->setCallInterference();
77 // add the spill costs
78 L1->addSpillCost(L2->getSpillCost());
80 delete L2; // delete L2 as it is no longer needed
85 //---------------------------------------------------------------------------
86 // Method for constructing all live ranges in a method. It creates live
87 // ranges for all values defined in the instruction stream. Also, it
88 // creates live ranges for all incoming arguments of the method.
89 //---------------------------------------------------------------------------
90 void LiveRangeInfo::constructLiveRanges()
94 cerr << "Consturcting Live Ranges ...\n";
96 // first find the live ranges for all incoming args of the method since
97 // those LRs start from the start of the method
99 // get the argument list
100 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
101 // get an iterator to arg list
102 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
105 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
106 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
107 const Value *Val = (const Value *) *ArgIt;
109 ArgRange->insert(Val); // add the arg (def) to it
110 LiveRangeMap[Val] = ArgRange;
112 // create a temp machine op to find the register class of value
113 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
115 unsigned rcid = MRI.getRegClassIDOfValue( Val );
116 ArgRange->setRegClass(RegClassList[ rcid ] );
120 cerr << " adding LiveRange for argument "
121 << RAV((const Value *)*ArgIt) << "\n";
125 // Now suggest hardware registers for these method args
126 MRI.suggestRegs4MethodArgs(Meth, *this);
130 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
134 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
135 for( ; BBI != Meth->end(); ++BBI) { // go thru BBs in random order
137 // Now find all LRs for machine the instructions. A new LR will be created
138 // only for defs in the machine instr since, we assume that all Values are
139 // defined before they are used. However, there can be multiple defs for
140 // the same Value in machine instructions.
142 // get the iterator for machine instructions
143 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
144 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
146 // iterate over all the machine instructions in BB
147 for( ; MInstIterator != MIVec.end(); MInstIterator++) {
149 const MachineInstr * MInst = *MInstIterator;
151 // Now if the machine instruction is a call/return instruction,
152 // add it to CallRetInstrList for processing its implicit operands
154 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
155 TM.getInstrInfo().isCall(MInst->getOpCode()))
156 CallRetInstrList.push_back( MInst );
159 // iterate over MI operands to find defs
160 for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done(); ++OpI) {
162 MachineOperand::MachineOperandType OpTyp =
163 OpI.getMachineOperand().getOperandType();
165 if (OpTyp == MachineOperand::MO_CCRegister)
166 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"
167 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
170 // create a new LR iff this operand is a def
172 const Value *Def = *OpI;
174 // Only instruction values are accepted for live ranges here
175 if (Def->getValueType() != Value::InstructionVal ) {
176 cerr << "\n**%%Error: Def is not an instruction val. Def="
181 LiveRange *DefRange = LiveRangeMap[Def];
183 // see LR already there (because of multiple defs)
184 if( !DefRange) { // if it is not in LiveRangeMap
185 DefRange = new LiveRange(); // creates a new live range and
186 DefRange->insert(Def); // add the instruction (def) to it
187 LiveRangeMap[ Def ] = DefRange; // update the map
190 cerr << " creating a LR for def: " << RAV(Def) << "\n";
192 // set the register class of the new live range
193 //assert( RegClassList.size() );
194 MachineOperand::MachineOperandType OpTy =
195 OpI.getMachineOperand().getOperandType();
197 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
198 unsigned rcid = MRI.getRegClassIDOfValue(
199 OpI.getMachineOperand().getVRegValue(), isCC );
202 if (isCC && DEBUG_RA)
203 cerr << "\a**created a LR for a CC reg:"
204 << RAV(OpI.getMachineOperand().getVRegValue());
206 DefRange->setRegClass(RegClassList[rcid]);
208 DefRange->insert(Def); // add the opearand to def range
209 // update the map - Operand points
211 LiveRangeMap[Def] = DefRange;
214 cerr << " added to an existing LR for def: "
220 } // for all opereands in machine instructions
222 } // for all machine instructions in the BB
224 } // for all BBs in method
227 // Now we have to suggest clors for call and return arg live ranges.
228 // Also, if there are implicit defs (e.g., retun value of a call inst)
229 // they must be added to the live range list
231 suggestRegs4CallRets();
234 cerr << "Initial Live Ranges constructed!\n";
239 //---------------------------------------------------------------------------
240 // If some live ranges must be colored with specific hardware registers
241 // (e.g., for outgoing call args), suggesting of colors for such live
242 // ranges is done using target specific method. Those methods are called
243 // from this function. The target specific methods must:
244 // 1) suggest colors for call and return args.
245 // 2) create new LRs for implicit defs in machine instructions
246 //---------------------------------------------------------------------------
247 void LiveRangeInfo::suggestRegs4CallRets()
250 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
252 for( ; It != CallRetInstrList.end(); ++It ) {
254 const MachineInstr *MInst = *It;
255 MachineOpCode OpCode = MInst->getOpCode();
257 if( (TM.getInstrInfo()).isReturn(OpCode) )
258 MRI.suggestReg4RetValue( MInst, *this);
260 else if( (TM.getInstrInfo()).isCall( OpCode ) )
261 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
264 assert( 0 && "Non call/ret instr in CallRetInstrList" );
270 //--------------------------------------------------------------------------
271 // The following method coalesces live ranges when possible. This method
272 // must be called after the interference graph has been constructed.
276 for each BB in method
277 for each machine instruction (inst)
278 for each definition (def) in inst
279 for each operand (op) of inst that is a use
280 if the def and op are of the same register type
281 if the def and op do not interfere //i.e., not simultaneously live
282 if (degree(LR of def) + degree(LR of op)) <= # avail regs
283 if both LRs do not have suggested colors
284 merge2IGNodes(def, op) // i.e., merge 2 LRs
287 //---------------------------------------------------------------------------
288 void LiveRangeInfo::coalesceLRs()
291 cerr << "\nCoalscing LRs ...\n";
293 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
295 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
297 // get the iterator for machine instructions
298 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
299 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
301 // iterate over all the machine instructions in BB
302 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
304 const MachineInstr * MInst = *MInstIterator;
307 cerr << " *Iterating over machine instr ";
313 // iterate over MI operands to find defs
314 for(MachineInstr::val_const_op_iterator DefI(MInst);!DefI.done();++DefI){
316 if( DefI.isDef() ) { // iff this operand is a def
318 LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
320 RegClass *const RCOfDef = LROfDef->getRegClass();
322 MachineInstr::val_const_op_iterator UseI(MInst);
323 for( ; !UseI.done(); ++UseI){ // for all uses
325 LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
327 if( ! LROfUse ) { // if LR of use is not found
329 //don't warn about labels
330 if (!isa<BasicBlock>(*UseI) && DEBUG_RA)
331 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
332 continue; // ignore and continue
335 if( LROfUse == LROfDef) // nothing to merge if they are same
338 //RegClass *const RCOfUse = LROfUse->getRegClass();
339 //if( RCOfDef == RCOfUse ) { // if the reg classes are the same
341 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
343 // 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()) {
351 // if both LRs do not have suggested colors
352 if (!(LROfDef->hasSuggestedColor() &&
353 LROfUse->hasSuggestedColor())) {
355 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
356 unionAndUpdateLRs(LROfDef, LROfUse);
360 } // if combined degree is less than # of regs
362 } // if def and use do not interfere
364 }// if reg classes are the same
372 } // for all machine instructions
377 cerr << "\nCoalscing Done!\n";
385 /*--------------------------- Debug code for printing ---------------*/
388 void LiveRangeInfo::printLiveRanges() {
389 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
390 cerr << "\nPrinting Live Ranges from Hash Map:\n";
391 for( ; HMI != LiveRangeMap.end(); ++HMI) {
392 if (HMI->first && HMI->second) {
393 cerr << " " << RAV(HMI->first) << "\t: ";
394 printSet(*HMI->second); cerr << "\n";