1 //===-- LiveRangeInfo.cpp -------------------------------------------------===//
3 // Live range construction for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/CodeGen/LiveRangeInfo.h"
8 #include "RegAllocCommon.h"
10 #include "llvm/CodeGen/IGNode.h"
11 #include "llvm/CodeGen/MachineInstr.h"
12 #include "llvm/CodeGen/MachineFunction.h"
13 #include "llvm/Target/TargetMachine.h"
14 #include "llvm/Target/TargetInstrInfo.h"
15 #include "llvm/Target/TargetRegInfo.h"
16 #include "llvm/Function.h"
17 #include "Support/SetOperations.h"
20 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); }
22 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
23 std::vector<RegClass *> &RCL)
24 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
27 LiveRangeInfo::~LiveRangeInfo() {
28 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
29 MI != LiveRangeMap.end(); ++MI) {
31 if (MI->first && MI->second) {
32 LiveRange *LR = MI->second;
34 // we need to be careful in deleting LiveRanges in LiveRangeMap
35 // since two/more Values in the live range map can point to the same
36 // live range. We have to make the other entries NULL when we delete
39 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
40 LiveRangeMap[*LI] = 0;
48 //---------------------------------------------------------------------------
49 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
50 // Note: the caller must make sure that L1 and L2 are distinct and both
51 // LRs don't have suggested colors
52 //---------------------------------------------------------------------------
54 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
55 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
56 assert(! (L1->hasColor() && L2->hasColor()) ||
57 L1->getColor() == L2->getColor());
59 set_union(*L1, *L2); // add elements of L2 to L1
61 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
62 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
64 L1->insert(*L2It); // add the var in L2 to L1
65 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
69 // set call interference for L1 from L2
70 if (L2->isCallInterference())
71 L1->setCallInterference();
73 // add the spill costs
74 L1->addSpillCost(L2->getSpillCost());
76 // If L2 has a color, give L1 that color. Note that L1 may have had the same
77 // color or none, but would not have a different color as asserted above.
79 L1->setColor(L2->getColor());
81 // Similarly, if LROfUse(L2) has a suggested color, the new range
82 // must have the same color.
83 if (L2->hasSuggestedColor())
84 L1->setSuggestedColor(L2->getSuggestedColor());
86 delete L2; // delete L2 as it is no longer needed
90 //---------------------------------------------------------------------------
91 // Method for creating a single live range for a definition.
92 // The definition must be represented by a virtual register (a Value).
93 // Note: this function does *not* check that no live range exists for def.
94 //---------------------------------------------------------------------------
97 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
99 LiveRange* DefRange = new LiveRange(); // Create a new live range,
100 DefRange->insert(Def); // add Def to it,
101 LiveRangeMap[Def] = DefRange; // and update the map.
103 // set the register class of the new live range
104 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
107 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
108 cerr << " Creating a LR for def ";
109 if (isCC) cerr << " (CC Register!)";
110 cerr << " : " << RAV(Def) << "\n";
117 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
119 LiveRange *DefRange = LiveRangeMap[Def];
121 // check if the LR is already there (because of multiple defs)
123 DefRange = createNewLiveRange(Def, isCC);
124 } else { // live range already exists
125 DefRange->insert(Def); // add the operand to the range
126 LiveRangeMap[Def] = DefRange; // make operand point to merged set
127 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
128 cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
134 //---------------------------------------------------------------------------
135 // Method for constructing all live ranges in a function. It creates live
136 // ranges for all values defined in the instruction stream. Also, it
137 // creates live ranges for all incoming arguments of the function.
138 //---------------------------------------------------------------------------
139 void LiveRangeInfo::constructLiveRanges() {
141 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
142 cerr << "Constructing Live Ranges ...\n";
144 // first find the live ranges for all incoming args of the function since
145 // those LRs start from the start of the function
146 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
147 createNewLiveRange(AI, /*isCC*/ false);
149 // Now suggest hardware registers for these function args
150 MRI.suggestRegs4MethodArgs(Meth, *this);
152 // Now create LRs for machine instructions. A new LR will be created
153 // only for defs in the machine instr since, we assume that all Values are
154 // defined before they are used. However, there can be multiple defs for
155 // the same Value in machine instructions.
157 // Also, find CALL and RETURN instructions, which need extra work.
159 MachineFunction &MF = MachineFunction::get(Meth);
160 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
161 MachineBasicBlock &MBB = *BBI;
163 // iterate over all the machine instructions in BB
164 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
165 MInstIterator != MBB.end(); ++MInstIterator) {
166 MachineInstr *MInst = *MInstIterator;
168 // If the machine instruction is a call/return instruction, add it to
169 // CallRetInstrList for processing its args, ret value, and ret addr.
171 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
172 TM.getInstrInfo().isCall(MInst->getOpCode()))
173 CallRetInstrList.push_back(MInst);
175 // iterate over explicit MI operands and create a new LR
176 // for each operand that is defined by the instruction
177 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
178 OpE = MInst->end(); OpI != OpE; ++OpI)
179 if (OpI.isDefOnly() || OpI.isDefAndUse()) {
180 const Value *Def = *OpI;
181 bool isCC = (OpI.getMachineOperand().getType()
182 == MachineOperand::MO_CCRegister);
183 LiveRange* LR = createOrAddToLiveRange(Def, isCC);
185 // If the operand has a pre-assigned register,
186 // set it directly in the LiveRange
187 if (OpI.getMachineOperand().hasAllocatedReg()) {
189 LR->setColor(MRI.getClassRegNum(
190 OpI.getMachineOperand().getAllocatedRegNum(),
195 // iterate over implicit MI operands and create a new LR
196 // for each operand that is defined by the instruction
197 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
198 if (MInst->getImplicitOp(i).opIsDefOnly() ||
199 MInst->getImplicitOp(i).opIsDefAndUse()) {
200 const Value *Def = MInst->getImplicitRef(i);
201 LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false);
203 // If the implicit operand has a pre-assigned register,
204 // set it directly in the LiveRange
205 if (MInst->getImplicitOp(i).hasAllocatedReg()) {
207 LR->setColor(MRI.getClassRegNum(
208 MInst->getImplicitOp(i).getAllocatedRegNum(),
213 } // for all machine instructions in the BB
215 } // for all BBs in function
217 // Now we have to suggest clors for call and return arg live ranges.
218 // Also, if there are implicit defs (e.g., retun value of a call inst)
219 // they must be added to the live range list
221 suggestRegs4CallRets();
223 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
224 cerr << "Initial Live Ranges constructed!\n";
228 //---------------------------------------------------------------------------
229 // If some live ranges must be colored with specific hardware registers
230 // (e.g., for outgoing call args), suggesting of colors for such live
231 // ranges is done using target specific function. Those functions are called
232 // from this function. The target specific methods must:
233 // 1) suggest colors for call and return args.
234 // 2) create new LRs for implicit defs in machine instructions
235 //---------------------------------------------------------------------------
236 void LiveRangeInfo::suggestRegs4CallRets() {
237 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
238 for( ; It != CallRetInstrList.end(); ++It) {
239 MachineInstr *MInst = *It;
240 MachineOpCode OpCode = MInst->getOpCode();
242 if ((TM.getInstrInfo()).isReturn(OpCode))
243 MRI.suggestReg4RetValue(MInst, *this);
244 else if ((TM.getInstrInfo()).isCall(OpCode))
245 MRI.suggestRegs4CallArgs(MInst, *this);
247 assert( 0 && "Non call/ret instr in CallRetInstrList" );
252 //--------------------------------------------------------------------------
253 // The following method coalesces live ranges when possible. This method
254 // must be called after the interference graph has been constructed.
258 for each BB in function
259 for each machine instruction (inst)
260 for each definition (def) in inst
261 for each operand (op) of inst that is a use
262 if the def and op are of the same register type
263 if the def and op do not interfere //i.e., not simultaneously live
264 if (degree(LR of def) + degree(LR of op)) <= # avail regs
265 if both LRs do not have suggested colors
266 merge2IGNodes(def, op) // i.e., merge 2 LRs
269 //---------------------------------------------------------------------------
272 // Checks if live range LR interferes with any node assigned or suggested to
273 // be assigned the specified color
275 inline bool InterferesWithColor(const LiveRange& LR, unsigned color)
277 IGNode* lrNode = LR.getUserIGNode();
278 for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) {
279 LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR();
280 if (neighLR->hasColor() && neighLR->getColor() == color)
282 if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color)
288 // Cannot coalesce if any of the following is true:
289 // (1) Both LRs have suggested colors (should be "different suggested colors"?)
290 // (2) Both LR1 and LR2 have colors and the colors are different
291 // (but if the colors are the same, it is definitely safe to coalesce)
292 // (3) LR1 has color and LR2 interferes with any LR that has the same color
293 // (4) LR2 has color and LR1 interferes with any LR that has the same color
295 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef,
296 const LiveRange& LROfUse)
298 // (4) if they have different suggested colors, cannot coalesce
299 if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor())
302 // if neither has a color, nothing more to do.
303 if (! LROfDef.hasColor() && ! LROfUse.hasColor())
306 // (2, 3) if L1 has color...
307 if (LROfDef.hasColor()) {
308 if (LROfUse.hasColor())
309 return (LROfUse.getColor() != LROfDef.getColor());
310 return InterferesWithColor(LROfUse, LROfDef.getColor());
313 // (4) else only LROfUse has a color: check if that could interfere
314 return InterferesWithColor(LROfDef, LROfUse.getColor());
318 void LiveRangeInfo::coalesceLRs()
320 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
321 cerr << "\nCoalescing LRs ...\n";
323 MachineFunction &MF = MachineFunction::get(Meth);
324 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
325 MachineBasicBlock &MBB = *BBI;
327 // iterate over all the machine instructions in BB
328 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
329 const MachineInstr *MI = *MII;
331 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
332 cerr << " *Iterating over machine instr ";
337 // iterate over MI operands to find defs
338 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
339 DefE = MI->end(); DefI != DefE; ++DefI) {
340 if (DefI.isDefOnly() || DefI.isDefAndUse()) { // this operand is modified
341 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
342 RegClass *RCOfDef = LROfDef->getRegClass();
344 MachineInstr::const_val_op_iterator UseI = MI->begin(),
346 for( ; UseI != UseE; ++UseI) { // for all uses
347 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
348 if (!LROfUse) { // if LR of use is not found
349 //don't warn about labels
350 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
351 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
352 continue; // ignore and continue
355 if (LROfUse == LROfDef) // nothing to merge if they are same
358 if (MRI.getRegTypeForLR(LROfDef) ==
359 MRI.getRegTypeForLR(LROfUse)) {
360 // If the two RegTypes are the same
361 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
363 unsigned CombinedDegree =
364 LROfDef->getUserIGNode()->getNumOfNeighbors() +
365 LROfUse->getUserIGNode()->getNumOfNeighbors();
367 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
368 // get more precise estimate of combined degree
369 CombinedDegree = LROfDef->getUserIGNode()->
370 getCombinedDegree(LROfUse->getUserIGNode());
373 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
374 // if both LRs do not have different pre-assigned colors
375 // and both LRs do not have suggested colors
376 if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) {
377 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
378 unionAndUpdateLRs(LROfDef, LROfUse);
381 } // if combined degree is less than # of regs
382 } // if def and use do not interfere
383 }// if reg classes are the same
387 } // for all machine instructions
390 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
391 cerr << "\nCoalescing Done!\n";
394 /*--------------------------- Debug code for printing ---------------*/
397 void LiveRangeInfo::printLiveRanges() {
398 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
399 cerr << "\nPrinting Live Ranges from Hash Map:\n";
400 for( ; HMI != LiveRangeMap.end(); ++HMI) {
401 if (HMI->first && HMI->second) {
402 cerr << " Value* " << RAV(HMI->first) << "\t: ";
403 if (IGNode* igNode = HMI->second->getUserIGNode())
404 cerr << "LR# " << igNode->getIndex();
406 cerr << "LR# " << "<no-IGNode>";
407 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";