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/MachineFunction.h"
12 #include "llvm/Target/TargetMachine.h"
13 #include "llvm/Target/MachineInstrInfo.h"
14 #include "llvm/Function.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 = 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 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 MachineFunction &MF = MachineFunction::get(Meth);
150 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
151 MachineBasicBlock &MBB = *BBI;
153 // iterate over all the machine instructions in BB
154 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
155 MInstIterator != MBB.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().getType()
172 == MachineOperand::MO_CCRegister);
173 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 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 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.isDef()) { // iff this operand is a def
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)) {
288 // If the two RegTypes are the same
289 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
291 unsigned CombinedDegree =
292 LROfDef->getUserIGNode()->getNumOfNeighbors() +
293 LROfUse->getUserIGNode()->getNumOfNeighbors();
295 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
296 // get more precise estimate of combined degree
297 CombinedDegree = LROfDef->getUserIGNode()->
298 getCombinedDegree(LROfUse->getUserIGNode());
301 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
302 // if both LRs do not have suggested colors
303 if (!(LROfDef->hasSuggestedColor() &&
304 LROfUse->hasSuggestedColor())) {
306 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
307 unionAndUpdateLRs(LROfDef, LROfUse);
310 } // if combined degree is less than # of regs
311 } // if def and use do not interfere
312 }// if reg classes are the same
316 } // for all machine instructions
319 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
320 cerr << "\nCoalescing Done!\n";
327 /*--------------------------- Debug code for printing ---------------*/
330 void LiveRangeInfo::printLiveRanges() {
331 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
332 cerr << "\nPrinting Live Ranges from Hash Map:\n";
333 for( ; HMI != LiveRangeMap.end(); ++HMI) {
334 if (HMI->first && HMI->second) {
335 cerr << " Value* " << RAV(HMI->first) << "\t: ";
336 if (IGNode* igNode = HMI->second->getUserIGNode())
337 cerr << "LR# " << igNode->getIndex();
339 cerr << "LR# " << "<no-IGNode>";
340 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";