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)
173 if (OpI.isDefOnly() || OpI.isDefAndUse()) {
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->getImplicitOp(i).opIsDefOnly() ||
184 MInst->getImplicitOp(i).opIsDefAndUse()) {
185 const Value *Def = MInst->getImplicitRef(i);
186 createOrAddToLiveRange(Def, /*isCC*/ false);
189 } // for all machine instructions in the BB
191 } // for all BBs in function
193 // Now we have to suggest clors for call and return arg live ranges.
194 // Also, if there are implicit defs (e.g., retun value of a call inst)
195 // they must be added to the live range list
197 suggestRegs4CallRets();
199 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
200 cerr << "Initial Live Ranges constructed!\n";
204 //---------------------------------------------------------------------------
205 // If some live ranges must be colored with specific hardware registers
206 // (e.g., for outgoing call args), suggesting of colors for such live
207 // ranges is done using target specific function. Those functions are called
208 // from this function. The target specific methods must:
209 // 1) suggest colors for call and return args.
210 // 2) create new LRs for implicit defs in machine instructions
211 //---------------------------------------------------------------------------
212 void LiveRangeInfo::suggestRegs4CallRets() {
213 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
214 for( ; It != CallRetInstrList.end(); ++It) {
215 MachineInstr *MInst = *It;
216 MachineOpCode OpCode = MInst->getOpCode();
218 if ((TM.getInstrInfo()).isReturn(OpCode))
219 MRI.suggestReg4RetValue(MInst, *this);
220 else if ((TM.getInstrInfo()).isCall(OpCode))
221 MRI.suggestRegs4CallArgs(MInst, *this);
223 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 MachineFunction &MF = MachineFunction::get(Meth);
252 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
253 MachineBasicBlock &MBB = *BBI;
255 // iterate over all the machine instructions in BB
256 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
257 const MachineInstr *MI = *MII;
259 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
260 cerr << " *Iterating over machine instr ";
265 // iterate over MI operands to find defs
266 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
267 DefE = MI->end(); DefI != DefE; ++DefI) {
268 if (DefI.isDefOnly() || DefI.isDefAndUse()) { // this operand is modified
269 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
270 RegClass *RCOfDef = LROfDef->getRegClass();
272 MachineInstr::const_val_op_iterator UseI = MI->begin(),
274 for( ; UseI != UseE; ++UseI) { // for all uses
275 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
276 if (!LROfUse) { // if LR of use is not found
277 //don't warn about labels
278 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
279 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
280 continue; // ignore and continue
283 if (LROfUse == LROfDef) // nothing to merge if they are same
286 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
287 // If the two RegTypes are the same
288 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
290 unsigned CombinedDegree =
291 LROfDef->getUserIGNode()->getNumOfNeighbors() +
292 LROfUse->getUserIGNode()->getNumOfNeighbors();
294 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
295 // get more precise estimate of combined degree
296 CombinedDegree = LROfDef->getUserIGNode()->
297 getCombinedDegree(LROfUse->getUserIGNode());
300 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
301 // if both LRs do not have suggested colors
302 if (!(LROfDef->hasSuggestedColor() &&
303 LROfUse->hasSuggestedColor())) {
305 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
306 unionAndUpdateLRs(LROfDef, LROfUse);
309 } // if combined degree is less than # of regs
310 } // if def and use do not interfere
311 }// if reg classes are the same
315 } // for all machine instructions
318 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
319 cerr << "\nCoalescing Done!\n";
326 /*--------------------------- Debug code for printing ---------------*/
329 void LiveRangeInfo::printLiveRanges() {
330 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
331 cerr << "\nPrinting Live Ranges from Hash Map:\n";
332 for( ; HMI != LiveRangeMap.end(); ++HMI) {
333 if (HMI->first && HMI->second) {
334 cerr << " Value* " << RAV(HMI->first) << "\t: ";
335 if (IGNode* igNode = HMI->second->getUserIGNode())
336 cerr << "LR# " << igNode->getIndex();
338 cerr << "LR# " << "<no-IGNode>";
339 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";