1 //===-- LiveRangeInfo.cpp -------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Live range construction for coloring-based register allocation for LLVM.
12 //===----------------------------------------------------------------------===//
15 #include "LiveRangeInfo.h"
16 #include "RegAllocCommon.h"
18 #include "llvm/Function.h"
19 #include "llvm/CodeGen/MachineInstr.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/Target/TargetRegInfo.h"
24 #include "Support/SetOperations.h"
28 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); }
30 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
31 std::vector<RegClass *> &RCL)
32 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
35 LiveRangeInfo::~LiveRangeInfo() {
36 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
37 MI != LiveRangeMap.end(); ++MI) {
39 if (MI->first && MI->second) {
40 LiveRange *LR = MI->second;
42 // we need to be careful in deleting LiveRanges in LiveRangeMap
43 // since two/more Values in the live range map can point to the same
44 // live range. We have to make the other entries NULL when we delete
47 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
48 LiveRangeMap[*LI] = 0;
56 //---------------------------------------------------------------------------
57 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
58 // Note: the caller must make sure that L1 and L2 are distinct and both
59 // LRs don't have suggested colors
60 //---------------------------------------------------------------------------
62 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
63 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
64 assert(! (L1->hasColor() && L2->hasColor()) ||
65 L1->getColor() == L2->getColor());
67 set_union(*L1, *L2); // add elements of L2 to L1
69 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
70 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
72 L1->insert(*L2It); // add the var in L2 to L1
73 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
77 // set call interference for L1 from L2
78 if (L2->isCallInterference())
79 L1->setCallInterference();
81 // add the spill costs
82 L1->addSpillCost(L2->getSpillCost());
84 // If L2 has a color, give L1 that color. Note that L1 may have had the same
85 // color or none, but would not have a different color as asserted above.
87 L1->setColor(L2->getColor());
89 // Similarly, if LROfUse(L2) has a suggested color, the new range
90 // must have the same color.
91 if (L2->hasSuggestedColor())
92 L1->setSuggestedColor(L2->getSuggestedColor());
94 delete L2; // delete L2 as it is no longer needed
98 //---------------------------------------------------------------------------
99 // Method for creating a single live range for a definition.
100 // The definition must be represented by a virtual register (a Value).
101 // Note: this function does *not* check that no live range exists for def.
102 //---------------------------------------------------------------------------
105 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
107 LiveRange* DefRange = new LiveRange(); // Create a new live range,
108 DefRange->insert(Def); // add Def to it,
109 LiveRangeMap[Def] = DefRange; // and update the map.
111 // set the register class of the new live range
112 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
115 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
116 std::cerr << " Creating a LR for def ";
117 if (isCC) std::cerr << " (CC Register!)";
118 std::cerr << " : " << RAV(Def) << "\n";
125 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
127 LiveRange *DefRange = LiveRangeMap[Def];
129 // check if the LR is already there (because of multiple defs)
131 DefRange = createNewLiveRange(Def, isCC);
132 } else { // live range already exists
133 DefRange->insert(Def); // add the operand to the range
134 LiveRangeMap[Def] = DefRange; // make operand point to merged set
135 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
136 std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
142 //---------------------------------------------------------------------------
143 // Method for constructing all live ranges in a function. It creates live
144 // ranges for all values defined in the instruction stream. Also, it
145 // creates live ranges for all incoming arguments of the function.
146 //---------------------------------------------------------------------------
147 void LiveRangeInfo::constructLiveRanges() {
149 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
150 std::cerr << "Constructing Live Ranges ...\n";
152 // first find the live ranges for all incoming args of the function since
153 // those LRs start from the start of the function
154 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
155 createNewLiveRange(AI, /*isCC*/ false);
157 // Now suggest hardware registers for these function args
158 MRI.suggestRegs4MethodArgs(Meth, *this);
160 // Now create LRs for machine instructions. A new LR will be created
161 // only for defs in the machine instr since, we assume that all Values are
162 // defined before they are used. However, there can be multiple defs for
163 // the same Value in machine instructions.
165 // Also, find CALL and RETURN instructions, which need extra work.
167 MachineFunction &MF = MachineFunction::get(Meth);
168 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
169 MachineBasicBlock &MBB = *BBI;
171 // iterate over all the machine instructions in BB
172 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
173 MInstIterator != MBB.end(); ++MInstIterator) {
174 MachineInstr *MInst = *MInstIterator;
176 // If the machine instruction is a call/return instruction, add it to
177 // CallRetInstrList for processing its args, ret value, and ret addr.
179 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
180 TM.getInstrInfo().isCall(MInst->getOpCode()))
181 CallRetInstrList.push_back(MInst);
183 // iterate over explicit MI operands and create a new LR
184 // for each operand that is defined by the instruction
185 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
186 OpE = MInst->end(); OpI != OpE; ++OpI)
187 if (OpI.isDefOnly() || OpI.isDefAndUse()) {
188 const Value *Def = *OpI;
189 bool isCC = (OpI.getMachineOperand().getType()
190 == MachineOperand::MO_CCRegister);
191 LiveRange* LR = createOrAddToLiveRange(Def, isCC);
193 // If the operand has a pre-assigned register,
194 // set it directly in the LiveRange
195 if (OpI.getMachineOperand().hasAllocatedReg()) {
197 LR->setColor(MRI.getClassRegNum(
198 OpI.getMachineOperand().getAllocatedRegNum(),
203 // iterate over implicit MI operands and create a new LR
204 // for each operand that is defined by the instruction
205 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
206 if (MInst->getImplicitOp(i).opIsDefOnly() ||
207 MInst->getImplicitOp(i).opIsDefAndUse()) {
208 const Value *Def = MInst->getImplicitRef(i);
209 LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false);
211 // If the implicit operand has a pre-assigned register,
212 // set it directly in the LiveRange
213 if (MInst->getImplicitOp(i).hasAllocatedReg()) {
215 LR->setColor(MRI.getClassRegNum(
216 MInst->getImplicitOp(i).getAllocatedRegNum(),
221 } // for all machine instructions in the BB
222 } // for all BBs in function
224 // Now we have to suggest clors for call and return arg live ranges.
225 // Also, if there are implicit defs (e.g., retun value of a call inst)
226 // they must be added to the live range list
228 suggestRegs4CallRets();
230 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
231 std::cerr << "Initial Live Ranges constructed!\n";
235 //---------------------------------------------------------------------------
236 // If some live ranges must be colored with specific hardware registers
237 // (e.g., for outgoing call args), suggesting of colors for such live
238 // ranges is done using target specific function. Those functions are called
239 // from this function. The target specific methods must:
240 // 1) suggest colors for call and return args.
241 // 2) create new LRs for implicit defs in machine instructions
242 //---------------------------------------------------------------------------
243 void LiveRangeInfo::suggestRegs4CallRets() {
244 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
245 for( ; It != CallRetInstrList.end(); ++It) {
246 MachineInstr *MInst = *It;
247 MachineOpCode OpCode = MInst->getOpCode();
249 if ((TM.getInstrInfo()).isReturn(OpCode))
250 MRI.suggestReg4RetValue(MInst, *this);
251 else if ((TM.getInstrInfo()).isCall(OpCode))
252 MRI.suggestRegs4CallArgs(MInst, *this);
254 assert( 0 && "Non call/ret instr in CallRetInstrList" );
259 //--------------------------------------------------------------------------
260 // The following method coalesces live ranges when possible. This method
261 // must be called after the interference graph has been constructed.
265 for each BB in function
266 for each machine instruction (inst)
267 for each definition (def) in inst
268 for each operand (op) of inst that is a use
269 if the def and op are of the same register type
270 if the def and op do not interfere //i.e., not simultaneously live
271 if (degree(LR of def) + degree(LR of op)) <= # avail regs
272 if both LRs do not have suggested colors
273 merge2IGNodes(def, op) // i.e., merge 2 LRs
276 //---------------------------------------------------------------------------
279 // Checks if live range LR interferes with any node assigned or suggested to
280 // be assigned the specified color
282 inline bool InterferesWithColor(const LiveRange& LR, unsigned color) {
283 IGNode* lrNode = LR.getUserIGNode();
284 for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) {
285 LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR();
286 if (neighLR->hasColor() && neighLR->getColor() == color)
288 if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color)
294 // Cannot coalesce if any of the following is true:
295 // (1) Both LRs have suggested colors (should be "different suggested colors"?)
296 // (2) Both LR1 and LR2 have colors and the colors are different
297 // (but if the colors are the same, it is definitely safe to coalesce)
298 // (3) LR1 has color and LR2 interferes with any LR that has the same color
299 // (4) LR2 has color and LR1 interferes with any LR that has the same color
301 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef,
302 const LiveRange& LROfUse) {
303 // (4) if they have different suggested colors, cannot coalesce
304 if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor())
307 // if neither has a color, nothing more to do.
308 if (! LROfDef.hasColor() && ! LROfUse.hasColor())
311 // (2, 3) if L1 has color...
312 if (LROfDef.hasColor()) {
313 if (LROfUse.hasColor())
314 return (LROfUse.getColor() != LROfDef.getColor());
315 return InterferesWithColor(LROfUse, LROfDef.getColor());
318 // (4) else only LROfUse has a color: check if that could interfere
319 return InterferesWithColor(LROfDef, LROfUse.getColor());
323 void LiveRangeInfo::coalesceLRs()
325 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
326 std::cerr << "\nCoalescing LRs ...\n";
328 MachineFunction &MF = MachineFunction::get(Meth);
329 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
330 MachineBasicBlock &MBB = *BBI;
332 // iterate over all the machine instructions in BB
333 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
334 const MachineInstr *MI = *MII;
336 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
337 std::cerr << " *Iterating over machine instr ";
342 // iterate over MI operands to find defs
343 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
344 DefE = MI->end(); DefI != DefE; ++DefI) {
345 if (DefI.isDefOnly() || DefI.isDefAndUse()) { // this operand is modified
346 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
347 RegClass *RCOfDef = LROfDef->getRegClass();
349 MachineInstr::const_val_op_iterator UseI = MI->begin(),
351 for( ; UseI != UseE; ++UseI) { // for all uses
352 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
353 if (!LROfUse) { // if LR of use is not found
354 //don't warn about labels
355 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
356 std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n";
357 continue; // ignore and continue
360 if (LROfUse == LROfDef) // nothing to merge if they are same
363 if (MRI.getRegTypeForLR(LROfDef) ==
364 MRI.getRegTypeForLR(LROfUse)) {
365 // If the two RegTypes are the same
366 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
368 unsigned CombinedDegree =
369 LROfDef->getUserIGNode()->getNumOfNeighbors() +
370 LROfUse->getUserIGNode()->getNumOfNeighbors();
372 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
373 // get more precise estimate of combined degree
374 CombinedDegree = LROfDef->getUserIGNode()->
375 getCombinedDegree(LROfUse->getUserIGNode());
378 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
379 // if both LRs do not have different pre-assigned colors
380 // and both LRs do not have suggested colors
381 if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) {
382 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
383 unionAndUpdateLRs(LROfDef, LROfUse);
386 } // if combined degree is less than # of regs
387 } // if def and use do not interfere
388 }// if reg classes are the same
392 } // for all machine instructions
395 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
396 std::cerr << "\nCoalescing Done!\n";
399 /*--------------------------- Debug code for printing ---------------*/
402 void LiveRangeInfo::printLiveRanges() {
403 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
404 std::cerr << "\nPrinting Live Ranges from Hash Map:\n";
405 for( ; HMI != LiveRangeMap.end(); ++HMI) {
406 if (HMI->first && HMI->second) {
407 std::cerr << " Value* " << RAV(HMI->first) << "\t: ";
408 if (IGNode* igNode = HMI->second->getUserIGNode())
409 std::cerr << "LR# " << igNode->getIndex();
411 std::cerr << "LR# " << "<no-IGNode>";
412 std::cerr << "\t:Values = "; printSet(*HMI->second); std::cerr << "\n";
417 } // End llvm namespace