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 "Support/SetOperations.h"
17 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
18 std::vector<RegClass *> &RCL)
19 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
22 LiveRangeInfo::~LiveRangeInfo() {
23 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
24 MI != LiveRangeMap.end(); ++MI) {
26 if (MI->first && MI->second) {
27 LiveRange *LR = MI->second;
29 // we need to be careful in deleting LiveRanges in LiveRangeMap
30 // since two/more Values in the live range map can point to the same
31 // live range. We have to make the other entries NULL when we delete
34 for(LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
35 LiveRangeMap[*LI] = 0;
43 //---------------------------------------------------------------------------
44 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
45 // Note: the caller must make sure that L1 and L2 are distinct and both
46 // LRs don't have suggested colors
47 //---------------------------------------------------------------------------
49 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
50 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
51 set_union(*L1, *L2); // add elements of L2 to L1
53 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
54 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
56 L1->insert(*L2It); // add the var in L2 to L1
57 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
62 // Now if LROfDef(L1) has a suggested color, it will remain.
63 // But, if LROfUse(L2) has a suggested color, the new range
64 // must have the same color.
66 if(L2->hasSuggestedColor())
67 L1->setSuggestedColor(L2->getSuggestedColor());
70 if (L2->isCallInterference())
71 L1->setCallInterference();
73 // add the spill costs
74 L1->addSpillCost(L2->getSpillCost());
76 delete L2; // delete L2 as it is no longer needed
80 //---------------------------------------------------------------------------
81 // Method for creating a single live range for a definition.
82 // The definition must be represented by a virtual register (a Value).
83 // Note: this function does *not* check that no live range exists for def.
84 //---------------------------------------------------------------------------
87 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
89 LiveRange* DefRange = new LiveRange(); // Create a new live range,
90 DefRange->insert(Def); // add Def to it,
91 LiveRangeMap[Def] = DefRange; // and update the map.
93 // set the register class of the new live range
94 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfValue(Def, isCC)]);
96 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
97 cerr << " Creating a LR for def ";
98 if (isCC) cerr << " (CC Register!)";
99 cerr << " : " << RAV(Def) << "\n";
106 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
108 LiveRange *DefRange = LiveRangeMap[Def];
110 // check if the LR is already there (because of multiple defs)
112 DefRange = this->createNewLiveRange(Def, isCC);
113 } else { // live range already exists
114 DefRange->insert(Def); // add the operand to the range
115 LiveRangeMap[Def] = DefRange; // make operand point to merged set
116 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
117 cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
123 //---------------------------------------------------------------------------
124 // Method for constructing all live ranges in a function. It creates live
125 // ranges for all values defined in the instruction stream. Also, it
126 // creates live ranges for all incoming arguments of the function.
127 //---------------------------------------------------------------------------
128 void LiveRangeInfo::constructLiveRanges() {
130 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
131 cerr << "Constructing Live Ranges ...\n";
133 // first find the live ranges for all incoming args of the function since
134 // those LRs start from the start of the function
135 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
136 this->createNewLiveRange(AI, /*isCC*/ false);
138 // Now suggest hardware registers for these function args
139 MRI.suggestRegs4MethodArgs(Meth, *this);
141 // Now create LRs for machine instructions. A new LR will be created
142 // only for defs in the machine instr since, we assume that all Values are
143 // defined before they are used. However, there can be multiple defs for
144 // the same Value in machine instructions.
146 // Also, find CALL and RETURN instructions, which need extra work.
148 for (Function::const_iterator BBI=Meth->begin(); BBI != Meth->end(); ++BBI){
149 // get the vector of machine instructions for this basic block.
150 MachineBasicBlock& MIVec = MachineBasicBlock::get(BBI);
152 // iterate over all the machine instructions in BB
153 for(MachineBasicBlock::iterator MInstIterator = MIVec.begin();
154 MInstIterator != MIVec.end(); ++MInstIterator) {
155 MachineInstr *MInst = *MInstIterator;
157 // If the machine instruction is a call/return instruction, add it to
158 // CallRetInstrList for processing its args, ret value, and ret addr.
160 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
161 TM.getInstrInfo().isCall(MInst->getOpCode()))
162 CallRetInstrList.push_back( MInst );
164 // iterate over explicit MI operands and create a new LR
165 // for each operand that is defined by the instruction
166 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
167 OpE = MInst->end(); OpI != OpE; ++OpI)
169 const Value *Def = *OpI;
170 bool isCC = (OpI.getMachineOperand().getOperandType()
171 == MachineOperand::MO_CCRegister);
172 this->createOrAddToLiveRange(Def, isCC);
175 // iterate over implicit MI operands and create a new LR
176 // for each operand that is defined by the instruction
177 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
178 if (MInst->implicitRefIsDefined(i)) {
179 const Value *Def = MInst->getImplicitRef(i);
180 this->createOrAddToLiveRange(Def, /*isCC*/ false);
183 } // for all machine instructions in the BB
185 } // for all BBs in function
187 // Now we have to suggest clors for call and return arg live ranges.
188 // Also, if there are implicit defs (e.g., retun value of a call inst)
189 // they must be added to the live range list
191 suggestRegs4CallRets();
193 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
194 cerr << "Initial Live Ranges constructed!\n";
198 //---------------------------------------------------------------------------
199 // If some live ranges must be colored with specific hardware registers
200 // (e.g., for outgoing call args), suggesting of colors for such live
201 // ranges is done using target specific function. Those functions are called
202 // from this function. The target specific methods must:
203 // 1) suggest colors for call and return args.
204 // 2) create new LRs for implicit defs in machine instructions
205 //---------------------------------------------------------------------------
206 void LiveRangeInfo::suggestRegs4CallRets()
208 CallRetInstrListType::iterator It = CallRetInstrList.begin();
209 for( ; It != CallRetInstrList.end(); ++It ) {
211 MachineInstr *MInst = *It;
212 MachineOpCode OpCode = MInst->getOpCode();
214 if( (TM.getInstrInfo()).isReturn(OpCode) )
215 MRI.suggestReg4RetValue( MInst, *this);
217 else if( (TM.getInstrInfo()).isCall( OpCode ) )
218 MRI.suggestRegs4CallArgs( MInst, *this);
221 assert( 0 && "Non call/ret instr in CallRetInstrList" );
227 //--------------------------------------------------------------------------
228 // The following method coalesces live ranges when possible. This method
229 // must be called after the interference graph has been constructed.
233 for each BB in function
234 for each machine instruction (inst)
235 for each definition (def) in inst
236 for each operand (op) of inst that is a use
237 if the def and op are of the same register type
238 if the def and op do not interfere //i.e., not simultaneously live
239 if (degree(LR of def) + degree(LR of op)) <= # avail regs
240 if both LRs do not have suggested colors
241 merge2IGNodes(def, op) // i.e., merge 2 LRs
244 //---------------------------------------------------------------------------
245 void LiveRangeInfo::coalesceLRs()
247 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
248 cerr << "\nCoalescing LRs ...\n";
250 for(Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
253 // get the iterator for machine instructions
254 const MachineBasicBlock& MIVec = MachineBasicBlock::get(BBI);
255 MachineBasicBlock::const_iterator MInstIterator = MIVec.begin();
257 // iterate over all the machine instructions in BB
258 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
259 const MachineInstr * MInst = *MInstIterator;
261 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
262 cerr << " *Iterating over machine instr ";
268 // iterate over MI operands to find defs
269 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
270 DefE = MInst->end(); DefI != DefE; ++DefI) {
271 if (DefI.isDef()) { // iff this operand is a def
272 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
273 RegClass *RCOfDef = LROfDef->getRegClass();
275 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
277 for( ; UseI != UseE; ++UseI){ // for all uses
279 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
280 if (!LROfUse) { // if LR of use is not found
281 //don't warn about labels
282 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
283 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
284 continue; // ignore and continue
287 if (LROfUse == LROfDef) // nothing to merge if they are same
290 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
292 // If the two RegTypes are the same
293 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
295 unsigned CombinedDegree =
296 LROfDef->getUserIGNode()->getNumOfNeighbors() +
297 LROfUse->getUserIGNode()->getNumOfNeighbors();
299 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
300 // get more precise estimate of combined degree
301 CombinedDegree = LROfDef->getUserIGNode()->
302 getCombinedDegree(LROfUse->getUserIGNode());
305 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
306 // if both LRs do not have suggested colors
307 if (!(LROfDef->hasSuggestedColor() &&
308 LROfUse->hasSuggestedColor())) {
310 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
311 unionAndUpdateLRs(LROfDef, LROfUse);
314 } // if combined degree is less than # of regs
315 } // if def and use do not interfere
316 }// if reg classes are the same
320 } // for all machine instructions
323 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
324 cerr << "\nCoalescing Done!\n";
331 /*--------------------------- Debug code for printing ---------------*/
334 void LiveRangeInfo::printLiveRanges() {
335 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
336 cerr << "\nPrinting Live Ranges from Hash Map:\n";
337 for( ; HMI != LiveRangeMap.end(); ++HMI) {
338 if (HMI->first && HMI->second) {
339 cerr << " Value* " << RAV(HMI->first) << "\t: ";
340 if (IGNode* igNode = HMI->second->getUserIGNode())
341 cerr << "LR# " << igNode->getIndex();
343 cerr << "LR# " << "<no-IGNode>";
344 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";