1 //===-- LiveRangeInfo.cpp -------------------------------------------------===//
3 // Live range construction for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/CodeGen/LiveRangeInfo.h"
8 #include "llvm/CodeGen/RegAllocCommon.h"
9 #include "llvm/CodeGen/RegClass.h"
10 #include "llvm/CodeGen/MachineInstr.h"
11 #include "llvm/CodeGen/MachineBasicBlock.h"
12 #include "llvm/Target/TargetMachine.h"
13 #include "llvm/Function.h"
14 #include "llvm/BasicBlock.h"
15 #include "Support/SetOperations.h"
18 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
19 std::vector<RegClass *> &RCL)
20 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
23 LiveRangeInfo::~LiveRangeInfo() {
24 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
25 MI != LiveRangeMap.end(); ++MI) {
27 if (MI->first && MI->second) {
28 LiveRange *LR = MI->second;
30 // we need to be careful in deleting LiveRanges in LiveRangeMap
31 // since two/more Values in the live range map can point to the same
32 // live range. We have to make the other entries NULL when we delete
35 for(LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
36 LiveRangeMap[*LI] = 0;
44 //---------------------------------------------------------------------------
45 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
46 // Note: the caller must make sure that L1 and L2 are distinct and both
47 // LRs don't have suggested colors
48 //---------------------------------------------------------------------------
50 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
51 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
52 set_union(*L1, *L2); // add elements of L2 to L1
54 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
55 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
57 L1->insert(*L2It); // add the var in L2 to L1
58 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
63 // Now if LROfDef(L1) has a suggested color, it will remain.
64 // But, if LROfUse(L2) has a suggested color, the new range
65 // must have the same color.
67 if(L2->hasSuggestedColor())
68 L1->setSuggestedColor(L2->getSuggestedColor());
71 if (L2->isCallInterference())
72 L1->setCallInterference();
74 // add the spill costs
75 L1->addSpillCost(L2->getSpillCost());
77 delete L2; // delete L2 as it is no longer needed
81 //---------------------------------------------------------------------------
82 // Method for creating a single live range for a definition.
83 // The definition must be represented by a virtual register (a Value).
84 // Note: this function does *not* check that no live range exists for def.
85 //---------------------------------------------------------------------------
88 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
90 LiveRange* DefRange = new LiveRange(); // Create a new live range,
91 DefRange->insert(Def); // add Def to it,
92 LiveRangeMap[Def] = DefRange; // and update the map.
94 // set the register class of the new live range
95 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfValue(Def, isCC)]);
97 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
98 cerr << " Creating a LR for def ";
99 if (isCC) cerr << " (CC Register!)";
100 cerr << " : " << RAV(Def) << "\n";
107 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
109 LiveRange *DefRange = LiveRangeMap[Def];
111 // check if the LR is already there (because of multiple defs)
113 DefRange = this->createNewLiveRange(Def, isCC);
114 } else { // live range already exists
115 DefRange->insert(Def); // add the operand to the range
116 LiveRangeMap[Def] = DefRange; // make operand point to merged set
117 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
118 cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
124 //---------------------------------------------------------------------------
125 // Method for constructing all live ranges in a function. It creates live
126 // ranges for all values defined in the instruction stream. Also, it
127 // creates live ranges for all incoming arguments of the function.
128 //---------------------------------------------------------------------------
129 void LiveRangeInfo::constructLiveRanges() {
131 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
132 cerr << "Constructing Live Ranges ...\n";
134 // first find the live ranges for all incoming args of the function since
135 // those LRs start from the start of the function
136 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
137 this->createNewLiveRange(AI, /*isCC*/ false);
139 // Now suggest hardware registers for these function args
140 MRI.suggestRegs4MethodArgs(Meth, *this);
142 // Now create LRs for machine instructions. A new LR will be created
143 // only for defs in the machine instr since, we assume that all Values are
144 // defined before they are used. However, there can be multiple defs for
145 // the same Value in machine instructions.
147 // Also, find CALL and RETURN instructions, which need extra work.
149 for (Function::const_iterator BBI=Meth->begin(); BBI != Meth->end(); ++BBI){
150 // get the vector of machine instructions for this basic block.
151 MachineBasicBlock& MIVec = MachineBasicBlock::get(BBI);
153 // iterate over all the machine instructions in BB
154 for(MachineBasicBlock::iterator MInstIterator = MIVec.begin();
155 MInstIterator != MIVec.end(); ++MInstIterator) {
156 MachineInstr *MInst = *MInstIterator;
158 // If the machine instruction is a call/return instruction, add it to
159 // CallRetInstrList for processing its args, ret value, and ret addr.
161 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
162 TM.getInstrInfo().isCall(MInst->getOpCode()))
163 CallRetInstrList.push_back( MInst );
165 // iterate over explicit MI operands and create a new LR
166 // for each operand that is defined by the instruction
167 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
168 OpE = MInst->end(); OpI != OpE; ++OpI)
170 const Value *Def = *OpI;
171 bool isCC = (OpI.getMachineOperand().getOperandType()
172 == MachineOperand::MO_CCRegister);
173 this->createOrAddToLiveRange(Def, isCC);
176 // iterate over implicit MI operands and create a new LR
177 // for each operand that is defined by the instruction
178 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
179 if (MInst->implicitRefIsDefined(i)) {
180 const Value *Def = MInst->getImplicitRef(i);
181 this->createOrAddToLiveRange(Def, /*isCC*/ false);
184 } // for all machine instructions in the BB
186 } // for all BBs in function
188 // Now we have to suggest clors for call and return arg live ranges.
189 // Also, if there are implicit defs (e.g., retun value of a call inst)
190 // they must be added to the live range list
192 suggestRegs4CallRets();
194 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
195 cerr << "Initial Live Ranges constructed!\n";
199 //---------------------------------------------------------------------------
200 // If some live ranges must be colored with specific hardware registers
201 // (e.g., for outgoing call args), suggesting of colors for such live
202 // ranges is done using target specific function. Those functions are called
203 // from this function. The target specific methods must:
204 // 1) suggest colors for call and return args.
205 // 2) create new LRs for implicit defs in machine instructions
206 //---------------------------------------------------------------------------
207 void LiveRangeInfo::suggestRegs4CallRets()
209 CallRetInstrListType::iterator It = CallRetInstrList.begin();
210 for( ; It != CallRetInstrList.end(); ++It ) {
212 MachineInstr *MInst = *It;
213 MachineOpCode OpCode = MInst->getOpCode();
215 if( (TM.getInstrInfo()).isReturn(OpCode) )
216 MRI.suggestReg4RetValue( MInst, *this);
218 else if( (TM.getInstrInfo()).isCall( OpCode ) )
219 MRI.suggestRegs4CallArgs( MInst, *this);
222 assert( 0 && "Non call/ret instr in CallRetInstrList" );
228 //--------------------------------------------------------------------------
229 // The following method coalesces live ranges when possible. This method
230 // must be called after the interference graph has been constructed.
234 for each BB in function
235 for each machine instruction (inst)
236 for each definition (def) in inst
237 for each operand (op) of inst that is a use
238 if the def and op are of the same register type
239 if the def and op do not interfere //i.e., not simultaneously live
240 if (degree(LR of def) + degree(LR of op)) <= # avail regs
241 if both LRs do not have suggested colors
242 merge2IGNodes(def, op) // i.e., merge 2 LRs
245 //---------------------------------------------------------------------------
246 void LiveRangeInfo::coalesceLRs()
248 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
249 cerr << "\nCoalescing LRs ...\n";
251 for(Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
254 // get the iterator for machine instructions
255 const MachineBasicBlock& MIVec = MachineBasicBlock::get(BBI);
256 MachineBasicBlock::const_iterator MInstIterator = MIVec.begin();
258 // iterate over all the machine instructions in BB
259 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
260 const MachineInstr * MInst = *MInstIterator;
262 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
263 cerr << " *Iterating over machine instr ";
269 // iterate over MI operands to find defs
270 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
271 DefE = MInst->end(); DefI != DefE; ++DefI) {
272 if (DefI.isDef()) { // iff this operand is a def
273 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
274 RegClass *RCOfDef = LROfDef->getRegClass();
276 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
278 for( ; UseI != UseE; ++UseI){ // for all uses
280 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
281 if (!LROfUse) { // if LR of use is not found
282 //don't warn about labels
283 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
284 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
285 continue; // ignore and continue
288 if (LROfUse == LROfDef) // nothing to merge if they are same
291 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
293 // If the two RegTypes are the same
294 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
296 unsigned CombinedDegree =
297 LROfDef->getUserIGNode()->getNumOfNeighbors() +
298 LROfUse->getUserIGNode()->getNumOfNeighbors();
300 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
301 // get more precise estimate of combined degree
302 CombinedDegree = LROfDef->getUserIGNode()->
303 getCombinedDegree(LROfUse->getUserIGNode());
306 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
307 // if both LRs do not have suggested colors
308 if (!(LROfDef->hasSuggestedColor() &&
309 LROfUse->hasSuggestedColor())) {
311 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
312 unionAndUpdateLRs(LROfDef, LROfUse);
315 } // if combined degree is less than # of regs
316 } // if def and use do not interfere
317 }// if reg classes are the same
321 } // for all machine instructions
324 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
325 cerr << "\nCoalescing Done!\n";
332 /*--------------------------- Debug code for printing ---------------*/
335 void LiveRangeInfo::printLiveRanges() {
336 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
337 cerr << "\nPrinting Live Ranges from Hash Map:\n";
338 for( ; HMI != LiveRangeMap.end(); ++HMI) {
339 if (HMI->first && HMI->second) {
340 cerr << " Value* " << RAV(HMI->first) << "\t: ";
341 if (IGNode* igNode = HMI->second->getUserIGNode())
342 cerr << "LR# " << igNode->getIndex();
344 cerr << "LR# " << "<no-IGNode>";
345 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";