1 //===-- LiveRangeInfo.cpp -------------------------------------------------===//
3 // Live range construction for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "LiveRangeInfo.h"
8 #include "RegAllocCommon.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"
19 unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); }
21 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
22 std::vector<RegClass *> &RCL)
23 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
26 LiveRangeInfo::~LiveRangeInfo() {
27 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
28 MI != LiveRangeMap.end(); ++MI) {
30 if (MI->first && MI->second) {
31 LiveRange *LR = MI->second;
33 // we need to be careful in deleting LiveRanges in LiveRangeMap
34 // since two/more Values in the live range map can point to the same
35 // live range. We have to make the other entries NULL when we delete
38 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
39 LiveRangeMap[*LI] = 0;
47 //---------------------------------------------------------------------------
48 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
49 // Note: the caller must make sure that L1 and L2 are distinct and both
50 // LRs don't have suggested colors
51 //---------------------------------------------------------------------------
53 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
54 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
55 assert(! (L1->hasColor() && L2->hasColor()) ||
56 L1->getColor() == L2->getColor());
58 set_union(*L1, *L2); // add elements of L2 to L1
60 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
61 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
63 L1->insert(*L2It); // add the var in L2 to L1
64 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
68 // set call interference for L1 from L2
69 if (L2->isCallInterference())
70 L1->setCallInterference();
72 // add the spill costs
73 L1->addSpillCost(L2->getSpillCost());
75 // If L2 has a color, give L1 that color. Note that L1 may have had the same
76 // color or none, but would not have a different color as asserted above.
78 L1->setColor(L2->getColor());
80 // Similarly, if LROfUse(L2) has a suggested color, the new range
81 // must have the same color.
82 if (L2->hasSuggestedColor())
83 L1->setSuggestedColor(L2->getSuggestedColor());
85 delete L2; // delete L2 as it is no longer needed
89 //---------------------------------------------------------------------------
90 // Method for creating a single live range for a definition.
91 // The definition must be represented by a virtual register (a Value).
92 // Note: this function does *not* check that no live range exists for def.
93 //---------------------------------------------------------------------------
96 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
98 LiveRange* DefRange = new LiveRange(); // Create a new live range,
99 DefRange->insert(Def); // add Def to it,
100 LiveRangeMap[Def] = DefRange; // and update the map.
102 // set the register class of the new live range
103 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
106 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
107 std::cerr << " Creating a LR for def ";
108 if (isCC) std::cerr << " (CC Register!)";
109 std::cerr << " : " << RAV(Def) << "\n";
116 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
118 LiveRange *DefRange = LiveRangeMap[Def];
120 // check if the LR is already there (because of multiple defs)
122 DefRange = createNewLiveRange(Def, isCC);
123 } else { // live range already exists
124 DefRange->insert(Def); // add the operand to the range
125 LiveRangeMap[Def] = DefRange; // make operand point to merged set
126 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
127 std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
133 //---------------------------------------------------------------------------
134 // Method for constructing all live ranges in a function. It creates live
135 // ranges for all values defined in the instruction stream. Also, it
136 // creates live ranges for all incoming arguments of the function.
137 //---------------------------------------------------------------------------
138 void LiveRangeInfo::constructLiveRanges() {
140 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
141 std::cerr << "Constructing Live Ranges ...\n";
143 // first find the live ranges for all incoming args of the function since
144 // those LRs start from the start of the function
145 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
146 createNewLiveRange(AI, /*isCC*/ false);
148 // Now suggest hardware registers for these function args
149 MRI.suggestRegs4MethodArgs(Meth, *this);
151 // Now create LRs for machine instructions. A new LR will be created
152 // only for defs in the machine instr since, we assume that all Values are
153 // defined before they are used. However, there can be multiple defs for
154 // the same Value in machine instructions.
156 // Also, find CALL and RETURN instructions, which need extra work.
158 MachineFunction &MF = MachineFunction::get(Meth);
159 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
160 MachineBasicBlock &MBB = *BBI;
162 // iterate over all the machine instructions in BB
163 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
164 MInstIterator != MBB.end(); ++MInstIterator) {
165 MachineInstr *MInst = *MInstIterator;
167 // If the machine instruction is a call/return instruction, add it to
168 // CallRetInstrList for processing its args, ret value, and ret addr.
170 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
171 TM.getInstrInfo().isCall(MInst->getOpCode()))
172 CallRetInstrList.push_back(MInst);
174 // iterate over explicit MI operands and create a new LR
175 // for each operand that is defined by the instruction
176 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
177 OpE = MInst->end(); OpI != OpE; ++OpI)
178 if (OpI.isDefOnly() || OpI.isDefAndUse()) {
179 const Value *Def = *OpI;
180 bool isCC = (OpI.getMachineOperand().getType()
181 == MachineOperand::MO_CCRegister);
182 LiveRange* LR = createOrAddToLiveRange(Def, isCC);
184 // If the operand has a pre-assigned register,
185 // set it directly in the LiveRange
186 if (OpI.getMachineOperand().hasAllocatedReg()) {
188 LR->setColor(MRI.getClassRegNum(
189 OpI.getMachineOperand().getAllocatedRegNum(),
194 // iterate over implicit MI operands and create a new LR
195 // for each operand that is defined by the instruction
196 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
197 if (MInst->getImplicitOp(i).opIsDefOnly() ||
198 MInst->getImplicitOp(i).opIsDefAndUse()) {
199 const Value *Def = MInst->getImplicitRef(i);
200 LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false);
202 // If the implicit operand has a pre-assigned register,
203 // set it directly in the LiveRange
204 if (MInst->getImplicitOp(i).hasAllocatedReg()) {
206 LR->setColor(MRI.getClassRegNum(
207 MInst->getImplicitOp(i).getAllocatedRegNum(),
212 } // for all machine instructions in the BB
214 } // for all BBs in function
216 // Now we have to suggest clors for call and return arg live ranges.
217 // Also, if there are implicit defs (e.g., retun value of a call inst)
218 // they must be added to the live range list
220 suggestRegs4CallRets();
222 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
223 std::cerr << "Initial Live Ranges constructed!\n";
227 //---------------------------------------------------------------------------
228 // If some live ranges must be colored with specific hardware registers
229 // (e.g., for outgoing call args), suggesting of colors for such live
230 // ranges is done using target specific function. Those functions are called
231 // from this function. The target specific methods must:
232 // 1) suggest colors for call and return args.
233 // 2) create new LRs for implicit defs in machine instructions
234 //---------------------------------------------------------------------------
235 void LiveRangeInfo::suggestRegs4CallRets() {
236 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
237 for( ; It != CallRetInstrList.end(); ++It) {
238 MachineInstr *MInst = *It;
239 MachineOpCode OpCode = MInst->getOpCode();
241 if ((TM.getInstrInfo()).isReturn(OpCode))
242 MRI.suggestReg4RetValue(MInst, *this);
243 else if ((TM.getInstrInfo()).isCall(OpCode))
244 MRI.suggestRegs4CallArgs(MInst, *this);
246 assert( 0 && "Non call/ret instr in CallRetInstrList" );
251 //--------------------------------------------------------------------------
252 // The following method coalesces live ranges when possible. This method
253 // must be called after the interference graph has been constructed.
257 for each BB in function
258 for each machine instruction (inst)
259 for each definition (def) in inst
260 for each operand (op) of inst that is a use
261 if the def and op are of the same register type
262 if the def and op do not interfere //i.e., not simultaneously live
263 if (degree(LR of def) + degree(LR of op)) <= # avail regs
264 if both LRs do not have suggested colors
265 merge2IGNodes(def, op) // i.e., merge 2 LRs
268 //---------------------------------------------------------------------------
271 // Checks if live range LR interferes with any node assigned or suggested to
272 // be assigned the specified color
274 inline bool InterferesWithColor(const LiveRange& LR, unsigned color)
276 IGNode* lrNode = LR.getUserIGNode();
277 for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) {
278 LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR();
279 if (neighLR->hasColor() && neighLR->getColor() == color)
281 if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color)
287 // Cannot coalesce if any of the following is true:
288 // (1) Both LRs have suggested colors (should be "different suggested colors"?)
289 // (2) Both LR1 and LR2 have colors and the colors are different
290 // (but if the colors are the same, it is definitely safe to coalesce)
291 // (3) LR1 has color and LR2 interferes with any LR that has the same color
292 // (4) LR2 has color and LR1 interferes with any LR that has the same color
294 inline bool InterfsPreventCoalescing(const LiveRange& LROfDef,
295 const LiveRange& LROfUse)
297 // (4) if they have different suggested colors, cannot coalesce
298 if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor())
301 // if neither has a color, nothing more to do.
302 if (! LROfDef.hasColor() && ! LROfUse.hasColor())
305 // (2, 3) if L1 has color...
306 if (LROfDef.hasColor()) {
307 if (LROfUse.hasColor())
308 return (LROfUse.getColor() != LROfDef.getColor());
309 return InterferesWithColor(LROfUse, LROfDef.getColor());
312 // (4) else only LROfUse has a color: check if that could interfere
313 return InterferesWithColor(LROfDef, LROfUse.getColor());
317 void LiveRangeInfo::coalesceLRs()
319 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
320 std::cerr << "\nCoalescing LRs ...\n";
322 MachineFunction &MF = MachineFunction::get(Meth);
323 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
324 MachineBasicBlock &MBB = *BBI;
326 // iterate over all the machine instructions in BB
327 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
328 const MachineInstr *MI = *MII;
330 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
331 std::cerr << " *Iterating over machine instr ";
336 // iterate over MI operands to find defs
337 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
338 DefE = MI->end(); DefI != DefE; ++DefI) {
339 if (DefI.isDefOnly() || DefI.isDefAndUse()) { // this operand is modified
340 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
341 RegClass *RCOfDef = LROfDef->getRegClass();
343 MachineInstr::const_val_op_iterator UseI = MI->begin(),
345 for( ; UseI != UseE; ++UseI) { // for all uses
346 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
347 if (!LROfUse) { // if LR of use is not found
348 //don't warn about labels
349 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
350 std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n";
351 continue; // ignore and continue
354 if (LROfUse == LROfDef) // nothing to merge if they are same
357 if (MRI.getRegTypeForLR(LROfDef) ==
358 MRI.getRegTypeForLR(LROfUse)) {
359 // If the two RegTypes are the same
360 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
362 unsigned CombinedDegree =
363 LROfDef->getUserIGNode()->getNumOfNeighbors() +
364 LROfUse->getUserIGNode()->getNumOfNeighbors();
366 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
367 // get more precise estimate of combined degree
368 CombinedDegree = LROfDef->getUserIGNode()->
369 getCombinedDegree(LROfUse->getUserIGNode());
372 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
373 // if both LRs do not have different pre-assigned colors
374 // and both LRs do not have suggested colors
375 if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) {
376 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
377 unionAndUpdateLRs(LROfDef, LROfUse);
380 } // if combined degree is less than # of regs
381 } // if def and use do not interfere
382 }// if reg classes are the same
386 } // for all machine instructions
389 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
390 std::cerr << "\nCoalescing Done!\n";
393 /*--------------------------- Debug code for printing ---------------*/
396 void LiveRangeInfo::printLiveRanges() {
397 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
398 std::cerr << "\nPrinting Live Ranges from Hash Map:\n";
399 for( ; HMI != LiveRangeMap.end(); ++HMI) {
400 if (HMI->first && HMI->second) {
401 std::cerr << " Value* " << RAV(HMI->first) << "\t: ";
402 if (IGNode* igNode = HMI->second->getUserIGNode())
403 std::cerr << "LR# " << igNode->getIndex();
405 std::cerr << "LR# " << "<no-IGNode>";
406 std::cerr << "\t:Values = "; printSet(*HMI->second); std::cerr << "\n";