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"
26 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); }
28 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
29 std::vector<RegClass *> &RCL)
30 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
33 LiveRangeInfo::~LiveRangeInfo() {
34 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
35 MI != LiveRangeMap.end(); ++MI) {
37 if (MI->first && MI->second) {
38 LiveRange *LR = MI->second;
40 // we need to be careful in deleting LiveRanges in LiveRangeMap
41 // since two/more Values in the live range map can point to the same
42 // live range. We have to make the other entries NULL when we delete
45 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
46 LiveRangeMap[*LI] = 0;
54 //---------------------------------------------------------------------------
55 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
56 // Note: the caller must make sure that L1 and L2 are distinct and both
57 // LRs don't have suggested colors
58 //---------------------------------------------------------------------------
60 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
61 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
62 assert(! (L1->hasColor() && L2->hasColor()) ||
63 L1->getColor() == L2->getColor());
65 set_union(*L1, *L2); // add elements of L2 to L1
67 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
68 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
70 L1->insert(*L2It); // add the var in L2 to L1
71 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
75 // set call interference for L1 from L2
76 if (L2->isCallInterference())
77 L1->setCallInterference();
79 // add the spill costs
80 L1->addSpillCost(L2->getSpillCost());
82 // If L2 has a color, give L1 that color. Note that L1 may have had the same
83 // color or none, but would not have a different color as asserted above.
85 L1->setColor(L2->getColor());
87 // Similarly, if LROfUse(L2) has a suggested color, the new range
88 // must have the same color.
89 if (L2->hasSuggestedColor())
90 L1->setSuggestedColor(L2->getSuggestedColor());
92 delete L2; // delete L2 as it is no longer needed
96 //---------------------------------------------------------------------------
97 // Method for creating a single live range for a definition.
98 // The definition must be represented by a virtual register (a Value).
99 // Note: this function does *not* check that no live range exists for def.
100 //---------------------------------------------------------------------------
103 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
105 LiveRange* DefRange = new LiveRange(); // Create a new live range,
106 DefRange->insert(Def); // add Def to it,
107 LiveRangeMap[Def] = DefRange; // and update the map.
109 // set the register class of the new live range
110 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
113 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
114 std::cerr << " Creating a LR for def ";
115 if (isCC) std::cerr << " (CC Register!)";
116 std::cerr << " : " << RAV(Def) << "\n";
123 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
125 LiveRange *DefRange = LiveRangeMap[Def];
127 // check if the LR is already there (because of multiple defs)
129 DefRange = createNewLiveRange(Def, isCC);
130 } else { // live range already exists
131 DefRange->insert(Def); // add the operand to the range
132 LiveRangeMap[Def] = DefRange; // make operand point to merged set
133 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
134 std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
140 //---------------------------------------------------------------------------
141 // Method for constructing all live ranges in a function. It creates live
142 // ranges for all values defined in the instruction stream. Also, it
143 // creates live ranges for all incoming arguments of the function.
144 //---------------------------------------------------------------------------
145 void LiveRangeInfo::constructLiveRanges() {
147 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
148 std::cerr << "Constructing Live Ranges ...\n";
150 // first find the live ranges for all incoming args of the function since
151 // those LRs start from the start of the function
152 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
153 createNewLiveRange(AI, /*isCC*/ false);
155 // Now suggest hardware registers for these function args
156 MRI.suggestRegs4MethodArgs(Meth, *this);
158 // Now create LRs for machine instructions. A new LR will be created
159 // only for defs in the machine instr since, we assume that all Values are
160 // defined before they are used. However, there can be multiple defs for
161 // the same Value in machine instructions.
163 // Also, find CALL and RETURN instructions, which need extra work.
165 MachineFunction &MF = MachineFunction::get(Meth);
166 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
167 MachineBasicBlock &MBB = *BBI;
169 // iterate over all the machine instructions in BB
170 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
171 MInstIterator != MBB.end(); ++MInstIterator) {
172 MachineInstr *MInst = *MInstIterator;
174 // If the machine instruction is a call/return instruction, add it to
175 // CallRetInstrList for processing its args, ret value, and ret addr.
177 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
178 TM.getInstrInfo().isCall(MInst->getOpCode()))
179 CallRetInstrList.push_back(MInst);
181 // iterate over explicit MI operands and create a new LR
182 // for each operand that is defined by the instruction
183 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
184 OpE = MInst->end(); OpI != OpE; ++OpI)
185 if (OpI.isDefOnly() || OpI.isDefAndUse()) {
186 const Value *Def = *OpI;
187 bool isCC = (OpI.getMachineOperand().getType()
188 == MachineOperand::MO_CCRegister);
189 LiveRange* LR = createOrAddToLiveRange(Def, isCC);
191 // If the operand has a pre-assigned register,
192 // set it directly in the LiveRange
193 if (OpI.getMachineOperand().hasAllocatedReg()) {
195 LR->setColor(MRI.getClassRegNum(
196 OpI.getMachineOperand().getAllocatedRegNum(),
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).opIsDefOnly() ||
205 MInst->getImplicitOp(i).opIsDefAndUse()) {
206 const Value *Def = MInst->getImplicitRef(i);
207 LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false);
209 // If the implicit operand has a pre-assigned register,
210 // set it directly in the LiveRange
211 if (MInst->getImplicitOp(i).hasAllocatedReg()) {
213 LR->setColor(MRI.getClassRegNum(
214 MInst->getImplicitOp(i).getAllocatedRegNum(),
219 } // for all machine instructions in the BB
220 } // for all BBs in function
222 // Now we have to suggest clors for call and return arg live ranges.
223 // Also, if there are implicit defs (e.g., retun value of a call inst)
224 // they must be added to the live range list
226 suggestRegs4CallRets();
228 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
229 std::cerr << "Initial Live Ranges constructed!\n";
233 //---------------------------------------------------------------------------
234 // If some live ranges must be colored with specific hardware registers
235 // (e.g., for outgoing call args), suggesting of colors for such live
236 // ranges is done using target specific function. Those functions are called
237 // from this function. The target specific methods must:
238 // 1) suggest colors for call and return args.
239 // 2) create new LRs for implicit defs in machine instructions
240 //---------------------------------------------------------------------------
241 void LiveRangeInfo::suggestRegs4CallRets() {
242 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
243 for( ; It != CallRetInstrList.end(); ++It) {
244 MachineInstr *MInst = *It;
245 MachineOpCode OpCode = MInst->getOpCode();
247 if ((TM.getInstrInfo()).isReturn(OpCode))
248 MRI.suggestReg4RetValue(MInst, *this);
249 else if ((TM.getInstrInfo()).isCall(OpCode))
250 MRI.suggestRegs4CallArgs(MInst, *this);
252 assert( 0 && "Non call/ret instr in CallRetInstrList" );
257 //--------------------------------------------------------------------------
258 // The following method coalesces live ranges when possible. This method
259 // must be called after the interference graph has been constructed.
263 for each BB in function
264 for each machine instruction (inst)
265 for each definition (def) in inst
266 for each operand (op) of inst that is a use
267 if the def and op are of the same register type
268 if the def and op do not interfere //i.e., not simultaneously live
269 if (degree(LR of def) + degree(LR of op)) <= # avail regs
270 if both LRs do not have suggested colors
271 merge2IGNodes(def, op) // i.e., merge 2 LRs
274 //---------------------------------------------------------------------------
277 // Checks if live range LR interferes with any node assigned or suggested to
278 // be assigned the specified color
280 inline bool InterferesWithColor(const LiveRange& LR, unsigned color) {
281 IGNode* lrNode = LR.getUserIGNode();
282 for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) {
283 LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR();
284 if (neighLR->hasColor() && neighLR->getColor() == color)
286 if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color)
292 // Cannot coalesce if any of the following is true:
293 // (1) Both LRs have suggested colors (should be "different suggested colors"?)
294 // (2) Both LR1 and LR2 have colors and the colors are different
295 // (but if the colors are the same, it is definitely safe to coalesce)
296 // (3) LR1 has color and LR2 interferes with any LR that has the same color
297 // (4) LR2 has color and LR1 interferes with any LR that has the same color
299 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef,
300 const LiveRange& LROfUse) {
301 // (4) if they have different suggested colors, cannot coalesce
302 if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor())
305 // if neither has a color, nothing more to do.
306 if (! LROfDef.hasColor() && ! LROfUse.hasColor())
309 // (2, 3) if L1 has color...
310 if (LROfDef.hasColor()) {
311 if (LROfUse.hasColor())
312 return (LROfUse.getColor() != LROfDef.getColor());
313 return InterferesWithColor(LROfUse, LROfDef.getColor());
316 // (4) else only LROfUse has a color: check if that could interfere
317 return InterferesWithColor(LROfDef, LROfUse.getColor());
321 void LiveRangeInfo::coalesceLRs()
323 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
324 std::cerr << "\nCoalescing LRs ...\n";
326 MachineFunction &MF = MachineFunction::get(Meth);
327 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
328 MachineBasicBlock &MBB = *BBI;
330 // iterate over all the machine instructions in BB
331 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
332 const MachineInstr *MI = *MII;
334 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
335 std::cerr << " *Iterating over machine instr ";
340 // iterate over MI operands to find defs
341 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
342 DefE = MI->end(); DefI != DefE; ++DefI) {
343 if (DefI.isDefOnly() || DefI.isDefAndUse()) { // this operand is modified
344 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
345 RegClass *RCOfDef = LROfDef->getRegClass();
347 MachineInstr::const_val_op_iterator UseI = MI->begin(),
349 for( ; UseI != UseE; ++UseI) { // for all uses
350 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
351 if (!LROfUse) { // if LR of use is not found
352 //don't warn about labels
353 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
354 std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n";
355 continue; // ignore and continue
358 if (LROfUse == LROfDef) // nothing to merge if they are same
361 if (MRI.getRegTypeForLR(LROfDef) ==
362 MRI.getRegTypeForLR(LROfUse)) {
363 // If the two RegTypes are the same
364 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
366 unsigned CombinedDegree =
367 LROfDef->getUserIGNode()->getNumOfNeighbors() +
368 LROfUse->getUserIGNode()->getNumOfNeighbors();
370 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
371 // get more precise estimate of combined degree
372 CombinedDegree = LROfDef->getUserIGNode()->
373 getCombinedDegree(LROfUse->getUserIGNode());
376 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
377 // if both LRs do not have different pre-assigned colors
378 // and both LRs do not have suggested colors
379 if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) {
380 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
381 unionAndUpdateLRs(LROfDef, LROfUse);
384 } // if combined degree is less than # of regs
385 } // if def and use do not interfere
386 }// if reg classes are the same
390 } // for all machine instructions
393 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
394 std::cerr << "\nCoalescing Done!\n";
397 /*--------------------------- Debug code for printing ---------------*/
400 void LiveRangeInfo::printLiveRanges() {
401 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
402 std::cerr << "\nPrinting Live Ranges from Hash Map:\n";
403 for( ; HMI != LiveRangeMap.end(); ++HMI) {
404 if (HMI->first && HMI->second) {
405 std::cerr << " Value* " << RAV(HMI->first) << "\t: ";
406 if (IGNode* igNode = HMI->second->getUserIGNode())
407 std::cerr << "LR# " << igNode->getIndex();
409 std::cerr << "LR# " << "<no-IGNode>";
410 std::cerr << "\t:Values = "; printSet(*HMI->second); std::cerr << "\n";