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 "../SparcV9RegInfo.h"
24 #include "Support/SetOperations.h"
29 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); }
31 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
32 std::vector<RegClass *> &RCL)
33 : Meth(F), TM(tm), RegClassList(RCL), MRI(*tm.getRegInfo()) { }
36 LiveRangeInfo::~LiveRangeInfo() {
37 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
38 MI != LiveRangeMap.end(); ++MI) {
40 if (MI->first && MI->second) {
41 LiveRange *LR = MI->second;
43 // we need to be careful in deleting LiveRanges in LiveRangeMap
44 // since two/more Values in the live range map can point to the same
45 // live range. We have to make the other entries NULL when we delete
48 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
49 LiveRangeMap[*LI] = 0;
57 //---------------------------------------------------------------------------
58 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
59 // Note: the caller must make sure that L1 and L2 are distinct and both
60 // LRs don't have suggested colors
61 //---------------------------------------------------------------------------
63 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
64 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
65 assert(! (L1->hasColor() && L2->hasColor()) ||
66 L1->getColor() == L2->getColor());
68 L2->insert (L1->begin(), L1->end()); // add elements of L2 to L1
70 for(LiveRange::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
71 L1->insert(*L2It); // add the var in L2 to L1
72 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
76 // set call interference for L1 from L2
77 if (L2->isCallInterference())
78 L1->setCallInterference();
80 // add the spill costs
81 L1->addSpillCost(L2->getSpillCost());
83 // If L2 has a color, give L1 that color. Note that L1 may have had the same
84 // color or none, but would not have a different color as asserted above.
86 L1->setColor(L2->getColor());
88 // Similarly, if LROfUse(L2) has a suggested color, the new range
89 // must have the same color.
90 if (L2->hasSuggestedColor())
91 L1->setSuggestedColor(L2->getSuggestedColor());
93 delete L2; // delete L2 as it is no longer needed
97 //---------------------------------------------------------------------------
98 // Method for creating a single live range for a definition.
99 // The definition must be represented by a virtual register (a Value).
100 // Note: this function does *not* check that no live range exists for def.
101 //---------------------------------------------------------------------------
104 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
106 LiveRange* DefRange = new LiveRange(); // Create a new live range,
107 DefRange->insert(Def); // add Def to it,
108 LiveRangeMap[Def] = DefRange; // and update the map.
110 // set the register class of the new live range
111 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
114 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
115 std::cerr << " Creating a LR for def ";
116 if (isCC) std::cerr << " (CC Register!)";
117 std::cerr << " : " << RAV(Def) << "\n";
124 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
126 LiveRange *DefRange = LiveRangeMap[Def];
128 // check if the LR is already there (because of multiple defs)
130 DefRange = createNewLiveRange(Def, isCC);
131 } else { // live range already exists
132 DefRange->insert(Def); // add the operand to the range
133 LiveRangeMap[Def] = DefRange; // make operand point to merged set
134 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
135 std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
141 //---------------------------------------------------------------------------
142 // Method for constructing all live ranges in a function. It creates live
143 // ranges for all values defined in the instruction stream. Also, it
144 // creates live ranges for all incoming arguments of the function.
145 //---------------------------------------------------------------------------
146 void LiveRangeInfo::constructLiveRanges() {
148 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
149 std::cerr << "Constructing Live Ranges ...\n";
151 // first find the live ranges for all incoming args of the function since
152 // those LRs start from the start of the function
153 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
154 createNewLiveRange(AI, /*isCC*/ false);
156 // Now suggest hardware registers for these function args
157 MRI.suggestRegs4MethodArgs(Meth, *this);
159 // Now create LRs for machine instructions. A new LR will be created
160 // only for defs in the machine instr since, we assume that all Values are
161 // defined before they are used. However, there can be multiple defs for
162 // the same Value in machine instructions.
164 // Also, find CALL and RETURN instructions, which need extra work.
166 MachineFunction &MF = MachineFunction::get(Meth);
167 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
168 MachineBasicBlock &MBB = *BBI;
170 // iterate over all the machine instructions in BB
171 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
172 MInstIterator != MBB.end(); ++MInstIterator) {
173 MachineInstr *MInst = MInstIterator;
175 // If the machine instruction is a call/return instruction, add it to
176 // CallRetInstrList for processing its args, ret value, and ret addr.
178 if(TM.getInstrInfo()->isReturn(MInst->getOpcode()) ||
179 TM.getInstrInfo()->isCall(MInst->getOpcode()))
180 CallRetInstrList.push_back(MInst);
182 // iterate over explicit MI operands and create a new LR
183 // for each operand that is defined by the instruction
184 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
185 OpE = MInst->end(); OpI != OpE; ++OpI)
187 const Value *Def = *OpI;
188 bool isCC = (OpI.getMachineOperand().getType()
189 == MachineOperand::MO_CCRegister);
190 LiveRange* LR = createOrAddToLiveRange(Def, isCC);
192 // If the operand has a pre-assigned register,
193 // set it directly in the LiveRange
194 if (OpI.getMachineOperand().hasAllocatedReg()) {
196 LR->setColor(MRI.getClassRegNum(OpI.getMachineOperand().getReg(),
201 // iterate over implicit MI operands and create a new LR
202 // for each operand that is defined by the instruction
203 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
204 if (MInst->getImplicitOp(i).isDef()) {
205 const Value *Def = MInst->getImplicitRef(i);
206 LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false);
208 // If the implicit operand has a pre-assigned register,
209 // set it directly in the LiveRange
210 if (MInst->getImplicitOp(i).hasAllocatedReg()) {
212 LR->setColor(MRI.getClassRegNum(
213 MInst->getImplicitOp(i).getReg(),
218 } // for all machine instructions in the BB
219 } // for all BBs in function
221 // Now we have to suggest clors for call and return arg live ranges.
222 // Also, if there are implicit defs (e.g., retun value of a call inst)
223 // they must be added to the live range list
225 suggestRegs4CallRets();
227 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
228 std::cerr << "Initial Live Ranges constructed!\n";
232 //---------------------------------------------------------------------------
233 // If some live ranges must be colored with specific hardware registers
234 // (e.g., for outgoing call args), suggesting of colors for such live
235 // ranges is done using target specific function. Those functions are called
236 // from this function. The target specific methods must:
237 // 1) suggest colors for call and return args.
238 // 2) create new LRs for implicit defs in machine instructions
239 //---------------------------------------------------------------------------
240 void LiveRangeInfo::suggestRegs4CallRets() {
241 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
242 for( ; It != CallRetInstrList.end(); ++It) {
243 MachineInstr *MInst = *It;
244 MachineOpCode OpCode = MInst->getOpcode();
246 if (TM.getInstrInfo()->isReturn(OpCode))
247 MRI.suggestReg4RetValue(MInst, *this);
248 else if (TM.getInstrInfo()->isCall(OpCode))
249 MRI.suggestRegs4CallArgs(MInst, *this);
251 assert( 0 && "Non call/ret instr in CallRetInstrList" );
256 //--------------------------------------------------------------------------
257 // The following method coalesces live ranges when possible. This method
258 // must be called after the interference graph has been constructed.
262 for each BB in function
263 for each machine instruction (inst)
264 for each definition (def) in inst
265 for each operand (op) of inst that is a use
266 if the def and op are of the same register type
267 if the def and op do not interfere //i.e., not simultaneously live
268 if (degree(LR of def) + degree(LR of op)) <= # avail regs
269 if both LRs do not have suggested colors
270 merge2IGNodes(def, op) // i.e., merge 2 LRs
273 //---------------------------------------------------------------------------
276 // Checks if live range LR interferes with any node assigned or suggested to
277 // be assigned the specified color
279 inline bool InterferesWithColor(const LiveRange& LR, unsigned color) {
280 IGNode* lrNode = LR.getUserIGNode();
281 for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) {
282 LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR();
283 if (neighLR->hasColor() && neighLR->getColor() == color)
285 if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color)
291 // Cannot coalesce if any of the following is true:
292 // (1) Both LRs have suggested colors (should be "different suggested colors"?)
293 // (2) Both LR1 and LR2 have colors and the colors are different
294 // (but if the colors are the same, it is definitely safe to coalesce)
295 // (3) LR1 has color and LR2 interferes with any LR that has the same color
296 // (4) LR2 has color and LR1 interferes with any LR that has the same color
298 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef,
299 const LiveRange& LROfUse) {
300 // (4) if they have different suggested colors, cannot coalesce
301 if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor())
304 // if neither has a color, nothing more to do.
305 if (! LROfDef.hasColor() && ! LROfUse.hasColor())
308 // (2, 3) if L1 has color...
309 if (LROfDef.hasColor()) {
310 if (LROfUse.hasColor())
311 return (LROfUse.getColor() != LROfDef.getColor());
312 return InterferesWithColor(LROfUse, LROfDef.getColor());
315 // (4) else only LROfUse has a color: check if that could interfere
316 return InterferesWithColor(LROfDef, LROfUse.getColor());
320 void LiveRangeInfo::coalesceLRs()
322 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
323 std::cerr << "\nCoalescing LRs ...\n";
325 MachineFunction &MF = MachineFunction::get(Meth);
326 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
327 MachineBasicBlock &MBB = *BBI;
329 // iterate over all the machine instructions in BB
330 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
331 const MachineInstr *MI = MII;
333 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
334 std::cerr << " *Iterating over machine instr ";
339 // iterate over MI operands to find defs
340 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
341 DefE = MI->end(); DefI != DefE; ++DefI) {
342 if (DefI.isDef()) { // this operand is modified
343 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
344 RegClass *RCOfDef = LROfDef->getRegClass();
346 MachineInstr::const_val_op_iterator UseI = MI->begin(),
348 for( ; UseI != UseE; ++UseI) { // for all uses
349 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
350 if (!LROfUse) { // if LR of use is not found
351 //don't warn about labels
352 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
353 std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n";
354 continue; // ignore and continue
357 if (LROfUse == LROfDef) // nothing to merge if they are same
360 if (MRI.getRegTypeForLR(LROfDef) ==
361 MRI.getRegTypeForLR(LROfUse)) {
362 // If the two RegTypes are the same
363 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
365 unsigned CombinedDegree =
366 LROfDef->getUserIGNode()->getNumOfNeighbors() +
367 LROfUse->getUserIGNode()->getNumOfNeighbors();
369 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
370 // get more precise estimate of combined degree
371 CombinedDegree = LROfDef->getUserIGNode()->
372 getCombinedDegree(LROfUse->getUserIGNode());
375 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
376 // if both LRs do not have different pre-assigned colors
377 // and both LRs do not have suggested colors
378 if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) {
379 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
380 unionAndUpdateLRs(LROfDef, LROfUse);
383 } // if combined degree is less than # of regs
384 } // if def and use do not interfere
385 }// if reg classes are the same
389 } // for all machine instructions
392 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
393 std::cerr << "\nCoalescing Done!\n";
396 /*--------------------------- Debug code for printing ---------------*/
399 void LiveRangeInfo::printLiveRanges() {
400 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
401 std::cerr << "\nPrinting Live Ranges from Hash Map:\n";
402 for( ; HMI != LiveRangeMap.end(); ++HMI) {
403 if (HMI->first && HMI->second) {
404 std::cerr << " Value* " << RAV(HMI->first) << "\t: ";
405 if (IGNode* igNode = HMI->second->getUserIGNode())
406 std::cerr << "LR# " << igNode->getIndex();
408 std::cerr << "LR# " << "<no-IGNode>";
409 std::cerr << "\t:Values = " << *HMI->second << "\n";
414 } // End llvm namespace