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 LiveRangeInfo::LiveRangeInfo(const Method *M, const TargetMachine &tm,
11 std::vector<RegClass *> &RCL)
12 : Meth(M), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
15 LiveRangeInfo::~LiveRangeInfo() {
16 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
17 MI != LiveRangeMap.end(); ++MI) {
19 if (MI->first && MI->second) {
20 LiveRange *LR = MI->second;
22 // we need to be careful in deleting LiveRanges in LiveRangeMap
23 // since two/more Values in the live range map can point to the same
24 // live range. We have to make the other entries NULL when we delete
27 for(LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
28 LiveRangeMap[*LI] = 0;
36 //---------------------------------------------------------------------------
37 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
38 // Note: the caller must make sure that L1 and L2 are distinct and both
39 // LRs don't have suggested colors
40 //---------------------------------------------------------------------------
42 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
43 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
44 set_union(*L1, *L2); // add elements of L2 to L1
46 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
47 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
49 L1->insert(*L2It); // add the var in L2 to L1
50 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
55 // Now if LROfDef(L1) has a suggested color, it will remain.
56 // But, if LROfUse(L2) has a suggested color, the new range
57 // must have the same color.
59 if(L2->hasSuggestedColor())
60 L1->setSuggestedColor(L2->getSuggestedColor());
63 if (L2->isCallInterference())
64 L1->setCallInterference();
66 // add the spill costs
67 L1->addSpillCost(L2->getSpillCost());
69 delete L2; // delete L2 as it is no longer needed
74 //---------------------------------------------------------------------------
75 // Method for constructing all live ranges in a method. It creates live
76 // ranges for all values defined in the instruction stream. Also, it
77 // creates live ranges for all incoming arguments of the method.
78 //---------------------------------------------------------------------------
79 void LiveRangeInfo::constructLiveRanges() {
82 cerr << "Consturcting Live Ranges ...\n";
84 // first find the live ranges for all incoming args of the method since
85 // those LRs start from the start of the method
87 // get the argument list
88 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
89 // get an iterator to arg list
90 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
93 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
94 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
95 const Value *Val = (const Value *) *ArgIt;
97 ArgRange->insert(Val); // add the arg (def) to it
98 LiveRangeMap[Val] = ArgRange;
100 // create a temp machine op to find the register class of value
101 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
103 unsigned rcid = MRI.getRegClassIDOfValue( Val );
104 ArgRange->setRegClass(RegClassList[ rcid ] );
108 cerr << " adding LiveRange for argument "
109 << RAV((const Value *)*ArgIt) << "\n";
113 // Now suggest hardware registers for these method args
114 MRI.suggestRegs4MethodArgs(Meth, *this);
118 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
121 for (Method::const_iterator BBI = Meth->begin(); BBI != Meth->end(); ++BBI) {
122 // Now find all LRs for machine the instructions. A new LR will be created
123 // only for defs in the machine instr since, we assume that all Values are
124 // defined before they are used. However, there can be multiple defs for
125 // the same Value in machine instructions.
127 // get the iterator for machine instructions
128 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
130 // iterate over all the machine instructions in BB
131 for(MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
132 MInstIterator != MIVec.end(); ++MInstIterator) {
133 const MachineInstr *MInst = *MInstIterator;
135 // Now if the machine instruction is a call/return instruction,
136 // add it to CallRetInstrList for processing its implicit operands
138 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
139 TM.getInstrInfo().isCall(MInst->getOpCode()))
140 CallRetInstrList.push_back( MInst );
143 // iterate over MI operands to find defs
144 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
145 OpE = MInst->end(); OpI != OpE; ++OpI) {
147 MachineOperand::MachineOperandType OpTyp =
148 OpI.getMachineOperand().getOperandType();
150 if (OpTyp == MachineOperand::MO_CCRegister)
151 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"
152 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
155 // create a new LR iff this operand is a def
157 const Value *Def = *OpI;
159 // Only instruction values are accepted for live ranges here
160 if (Def->getValueType() != Value::InstructionVal ) {
161 cerr << "\n**%%Error: Def is not an instruction val. Def="
166 LiveRange *DefRange = LiveRangeMap[Def];
168 // see LR already there (because of multiple defs)
169 if( !DefRange) { // if it is not in LiveRangeMap
170 DefRange = new LiveRange(); // creates a new live range and
171 DefRange->insert(Def); // add the instruction (def) to it
172 LiveRangeMap[ Def ] = DefRange; // update the map
175 cerr << " creating a LR for def: " << RAV(Def) << "\n";
177 // set the register class of the new live range
178 //assert( RegClassList.size() );
179 MachineOperand::MachineOperandType OpTy =
180 OpI.getMachineOperand().getOperandType();
182 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
183 unsigned rcid = MRI.getRegClassIDOfValue(
184 OpI.getMachineOperand().getVRegValue(), isCC );
187 if (isCC && DEBUG_RA)
188 cerr << "\a**created a LR for a CC reg:"
189 << RAV(OpI.getMachineOperand().getVRegValue());
191 DefRange->setRegClass(RegClassList[rcid]);
193 DefRange->insert(Def); // add the opearand to def range
194 // update the map - Operand points
196 LiveRangeMap[Def] = DefRange;
199 cerr << " added to an existing LR for def: "
205 } // for all opereands in machine instructions
207 } // for all machine instructions in the BB
209 } // for all BBs in method
212 // Now we have to suggest clors for call and return arg live ranges.
213 // Also, if there are implicit defs (e.g., retun value of a call inst)
214 // they must be added to the live range list
216 suggestRegs4CallRets();
219 cerr << "Initial Live Ranges constructed!\n";
224 //---------------------------------------------------------------------------
225 // If some live ranges must be colored with specific hardware registers
226 // (e.g., for outgoing call args), suggesting of colors for such live
227 // ranges is done using target specific method. Those methods are called
228 // from this function. The target specific methods must:
229 // 1) suggest colors for call and return args.
230 // 2) create new LRs for implicit defs in machine instructions
231 //---------------------------------------------------------------------------
232 void LiveRangeInfo::suggestRegs4CallRets()
235 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
237 for( ; It != CallRetInstrList.end(); ++It ) {
239 const MachineInstr *MInst = *It;
240 MachineOpCode OpCode = MInst->getOpCode();
242 if( (TM.getInstrInfo()).isReturn(OpCode) )
243 MRI.suggestReg4RetValue( MInst, *this);
245 else if( (TM.getInstrInfo()).isCall( OpCode ) )
246 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
249 assert( 0 && "Non call/ret instr in CallRetInstrList" );
255 //--------------------------------------------------------------------------
256 // The following method coalesces live ranges when possible. This method
257 // must be called after the interference graph has been constructed.
261 for each BB in method
262 for each machine instruction (inst)
263 for each definition (def) in inst
264 for each operand (op) of inst that is a use
265 if the def and op are of the same register type
266 if the def and op do not interfere //i.e., not simultaneously live
267 if (degree(LR of def) + degree(LR of op)) <= # avail regs
268 if both LRs do not have suggested colors
269 merge2IGNodes(def, op) // i.e., merge 2 LRs
272 //---------------------------------------------------------------------------
273 void LiveRangeInfo::coalesceLRs()
276 cerr << "\nCoalscing LRs ...\n";
278 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
280 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
282 // get the iterator for machine instructions
283 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
284 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
286 // iterate over all the machine instructions in BB
287 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
289 const MachineInstr * MInst = *MInstIterator;
292 cerr << " *Iterating over machine instr ";
298 // iterate over MI operands to find defs
299 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
300 DefE = MInst->end(); DefI != DefE; ++DefI) {
301 if (DefI.isDef()) { // iff this operand is a def
302 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
303 RegClass *RCOfDef = LROfDef->getRegClass();
305 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
307 for( ; UseI != UseE; ++UseI){ // for all uses
309 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
310 if (!LROfUse) { // if LR of use is not found
311 //don't warn about labels
312 if (!isa<BasicBlock>(*UseI) && DEBUG_RA)
313 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
314 continue; // ignore and continue
317 if (LROfUse == LROfDef) // nothing to merge if they are same
320 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
322 // If the two RegTypes are the same
323 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
325 unsigned CombinedDegree =
326 LROfDef->getUserIGNode()->getNumOfNeighbors() +
327 LROfUse->getUserIGNode()->getNumOfNeighbors();
329 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
330 // if both LRs do not have suggested colors
331 if (!(LROfDef->hasSuggestedColor() &&
332 LROfUse->hasSuggestedColor())) {
334 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
335 unionAndUpdateLRs(LROfDef, LROfUse);
338 } // if combined degree is less than # of regs
339 } // if def and use do not interfere
340 }// if reg classes are the same
344 } // for all machine instructions
348 cerr << "\nCoalscing Done!\n";
355 /*--------------------------- Debug code for printing ---------------*/
358 void LiveRangeInfo::printLiveRanges() {
359 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
360 cerr << "\nPrinting Live Ranges from Hash Map:\n";
361 for( ; HMI != LiveRangeMap.end(); ++HMI) {
362 if (HMI->first && HMI->second) {
363 cerr << " " << RAV(HMI->first) << "\t: ";
364 printSet(*HMI->second); cerr << "\n";