1 //===-- LiveRangeInfo.cpp -------------------------------------------------===//
3 // Live range construction for coloring-based register allocation for LLVM.
5 //===----------------------------------------------------------------------===//
7 #include "llvm/CodeGen/LiveRangeInfo.h"
8 #include "RegAllocCommon.h"
10 #include "llvm/CodeGen/IGNode.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/Function.h"
16 #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 set_union(*L1, *L2); // add elements of L2 to L1
57 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
58 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
60 L1->insert(*L2It); // add the var in L2 to L1
61 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
66 // Now if LROfDef(L1) has a suggested color, it will remain.
67 // But, if LROfUse(L2) has a suggested color, the new range
68 // must have the same color.
70 if(L2->hasSuggestedColor())
71 L1->setSuggestedColor(L2->getSuggestedColor());
74 if (L2->isCallInterference())
75 L1->setCallInterference();
77 // add the spill costs
78 L1->addSpillCost(L2->getSpillCost());
80 delete L2; // delete L2 as it is no longer needed
84 //---------------------------------------------------------------------------
85 // Method for creating a single live range for a definition.
86 // The definition must be represented by a virtual register (a Value).
87 // Note: this function does *not* check that no live range exists for def.
88 //---------------------------------------------------------------------------
91 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
93 LiveRange* DefRange = new LiveRange(); // Create a new live range,
94 DefRange->insert(Def); // add Def to it,
95 LiveRangeMap[Def] = DefRange; // and update the map.
97 // set the register class of the new live range
98 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(),
101 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
102 cerr << " Creating a LR for def ";
103 if (isCC) cerr << " (CC Register!)";
104 cerr << " : " << RAV(Def) << "\n";
111 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
113 LiveRange *DefRange = LiveRangeMap[Def];
115 // check if the LR is already there (because of multiple defs)
117 DefRange = createNewLiveRange(Def, isCC);
118 } else { // live range already exists
119 DefRange->insert(Def); // add the operand to the range
120 LiveRangeMap[Def] = DefRange; // make operand point to merged set
121 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
122 cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
128 //---------------------------------------------------------------------------
129 // Method for constructing all live ranges in a function. It creates live
130 // ranges for all values defined in the instruction stream. Also, it
131 // creates live ranges for all incoming arguments of the function.
132 //---------------------------------------------------------------------------
133 void LiveRangeInfo::constructLiveRanges() {
135 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
136 cerr << "Constructing Live Ranges ...\n";
138 // first find the live ranges for all incoming args of the function since
139 // those LRs start from the start of the function
140 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
141 createNewLiveRange(AI, /*isCC*/ false);
143 // Now suggest hardware registers for these function args
144 MRI.suggestRegs4MethodArgs(Meth, *this);
146 // Now create LRs for machine instructions. A new LR will be created
147 // only for defs in the machine instr since, we assume that all Values are
148 // defined before they are used. However, there can be multiple defs for
149 // the same Value in machine instructions.
151 // Also, find CALL and RETURN instructions, which need extra work.
153 MachineFunction &MF = MachineFunction::get(Meth);
154 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
155 MachineBasicBlock &MBB = *BBI;
157 // iterate over all the machine instructions in BB
158 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
159 MInstIterator != MBB.end(); ++MInstIterator) {
160 MachineInstr *MInst = *MInstIterator;
162 // If the machine instruction is a call/return instruction, add it to
163 // CallRetInstrList for processing its args, ret value, and ret addr.
165 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
166 TM.getInstrInfo().isCall(MInst->getOpCode()))
167 CallRetInstrList.push_back(MInst);
169 // iterate over explicit MI operands and create a new LR
170 // for each operand that is defined by the instruction
171 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
172 OpE = MInst->end(); OpI != OpE; ++OpI)
174 const Value *Def = *OpI;
175 bool isCC = (OpI.getMachineOperand().getType()
176 == MachineOperand::MO_CCRegister);
177 createOrAddToLiveRange(Def, isCC);
180 // iterate over implicit MI operands and create a new LR
181 // for each operand that is defined by the instruction
182 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
183 if (MInst->implicitRefIsDefined(i)) {
184 const Value *Def = MInst->getImplicitRef(i);
185 createOrAddToLiveRange(Def, /*isCC*/ false);
188 } // for all machine instructions in the BB
190 } // for all BBs in function
192 // Now we have to suggest clors for call and return arg live ranges.
193 // Also, if there are implicit defs (e.g., retun value of a call inst)
194 // they must be added to the live range list
196 suggestRegs4CallRets();
198 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
199 cerr << "Initial Live Ranges constructed!\n";
203 //---------------------------------------------------------------------------
204 // If some live ranges must be colored with specific hardware registers
205 // (e.g., for outgoing call args), suggesting of colors for such live
206 // ranges is done using target specific function. Those functions are called
207 // from this function. The target specific methods must:
208 // 1) suggest colors for call and return args.
209 // 2) create new LRs for implicit defs in machine instructions
210 //---------------------------------------------------------------------------
211 void LiveRangeInfo::suggestRegs4CallRets() {
212 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
213 for( ; It != CallRetInstrList.end(); ++It) {
214 MachineInstr *MInst = *It;
215 MachineOpCode OpCode = MInst->getOpCode();
217 if ((TM.getInstrInfo()).isReturn(OpCode))
218 MRI.suggestReg4RetValue(MInst, *this);
219 else if ((TM.getInstrInfo()).isCall(OpCode))
220 MRI.suggestRegs4CallArgs(MInst, *this);
222 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 MachineFunction &MF = MachineFunction::get(Meth);
251 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
252 MachineBasicBlock &MBB = *BBI;
254 // iterate over all the machine instructions in BB
255 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
256 const MachineInstr *MI = *MII;
258 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
259 cerr << " *Iterating over machine instr ";
264 // iterate over MI operands to find defs
265 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
266 DefE = MI->end(); DefI != DefE; ++DefI) {
267 if (DefI.isDef()) { // iff this operand is a def
268 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
269 RegClass *RCOfDef = LROfDef->getRegClass();
271 MachineInstr::const_val_op_iterator UseI = MI->begin(),
273 for( ; UseI != UseE; ++UseI) { // for all uses
274 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
275 if (!LROfUse) { // if LR of use is not found
276 //don't warn about labels
277 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
278 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
279 continue; // ignore and continue
282 if (LROfUse == LROfDef) // nothing to merge if they are same
285 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
286 // If the two RegTypes are the same
287 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
289 unsigned CombinedDegree =
290 LROfDef->getUserIGNode()->getNumOfNeighbors() +
291 LROfUse->getUserIGNode()->getNumOfNeighbors();
293 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
294 // get more precise estimate of combined degree
295 CombinedDegree = LROfDef->getUserIGNode()->
296 getCombinedDegree(LROfUse->getUserIGNode());
299 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
300 // if both LRs do not have suggested colors
301 if (!(LROfDef->hasSuggestedColor() &&
302 LROfUse->hasSuggestedColor())) {
304 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
305 unionAndUpdateLRs(LROfDef, LROfUse);
308 } // if combined degree is less than # of regs
309 } // if def and use do not interfere
310 }// if reg classes are the same
314 } // for all machine instructions
317 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
318 cerr << "\nCoalescing Done!\n";
325 /*--------------------------- Debug code for printing ---------------*/
328 void LiveRangeInfo::printLiveRanges() {
329 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
330 cerr << "\nPrinting Live Ranges from Hash Map:\n";
331 for( ; HMI != LiveRangeMap.end(); ++HMI) {
332 if (HMI->first && HMI->second) {
333 cerr << " Value* " << RAV(HMI->first) << "\t: ";
334 if (IGNode* igNode = HMI->second->getUserIGNode())
335 cerr << "LR# " << igNode->getIndex();
337 cerr << "LR# " << "<no-IGNode>";
338 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";