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/IGNode.h"
11 #include "llvm/CodeGen/MachineInstr.h"
12 #include "llvm/CodeGen/MachineFunction.h"
13 #include "llvm/Target/TargetMachine.h"
14 #include "llvm/Target/MachineInstrInfo.h"
15 #include "llvm/Function.h"
16 #include "Support/SetOperations.h"
19 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
20 std::vector<RegClass *> &RCL)
21 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
24 LiveRangeInfo::~LiveRangeInfo() {
25 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
26 MI != LiveRangeMap.end(); ++MI) {
28 if (MI->first && MI->second) {
29 LiveRange *LR = MI->second;
31 // we need to be careful in deleting LiveRanges in LiveRangeMap
32 // since two/more Values in the live range map can point to the same
33 // live range. We have to make the other entries NULL when we delete
36 for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
37 LiveRangeMap[*LI] = 0;
45 //---------------------------------------------------------------------------
46 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
47 // Note: the caller must make sure that L1 and L2 are distinct and both
48 // LRs don't have suggested colors
49 //---------------------------------------------------------------------------
51 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
52 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
53 set_union(*L1, *L2); // add elements of L2 to L1
55 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
56 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
58 L1->insert(*L2It); // add the var in L2 to L1
59 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
64 // Now if LROfDef(L1) has a suggested color, it will remain.
65 // But, if LROfUse(L2) has a suggested color, the new range
66 // must have the same color.
68 if(L2->hasSuggestedColor())
69 L1->setSuggestedColor(L2->getSuggestedColor());
72 if (L2->isCallInterference())
73 L1->setCallInterference();
75 // add the spill costs
76 L1->addSpillCost(L2->getSpillCost());
78 delete L2; // delete L2 as it is no longer needed
82 //---------------------------------------------------------------------------
83 // Method for creating a single live range for a definition.
84 // The definition must be represented by a virtual register (a Value).
85 // Note: this function does *not* check that no live range exists for def.
86 //---------------------------------------------------------------------------
89 LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/)
91 LiveRange* DefRange = new LiveRange(); // Create a new live range,
92 DefRange->insert(Def); // add Def to it,
93 LiveRangeMap[Def] = DefRange; // and update the map.
95 // set the register class of the new live range
96 DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfValue(Def, isCC)]);
98 if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
99 cerr << " Creating a LR for def ";
100 if (isCC) cerr << " (CC Register!)";
101 cerr << " : " << RAV(Def) << "\n";
108 LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/)
110 LiveRange *DefRange = LiveRangeMap[Def];
112 // check if the LR is already there (because of multiple defs)
114 DefRange = createNewLiveRange(Def, isCC);
115 } else { // live range already exists
116 DefRange->insert(Def); // add the operand to the range
117 LiveRangeMap[Def] = DefRange; // make operand point to merged set
118 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
119 cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
125 //---------------------------------------------------------------------------
126 // Method for constructing all live ranges in a function. It creates live
127 // ranges for all values defined in the instruction stream. Also, it
128 // creates live ranges for all incoming arguments of the function.
129 //---------------------------------------------------------------------------
130 void LiveRangeInfo::constructLiveRanges() {
132 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
133 cerr << "Constructing Live Ranges ...\n";
135 // first find the live ranges for all incoming args of the function since
136 // those LRs start from the start of the function
137 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI)
138 createNewLiveRange(AI, /*isCC*/ false);
140 // Now suggest hardware registers for these function args
141 MRI.suggestRegs4MethodArgs(Meth, *this);
143 // Now create LRs for machine instructions. A new LR will be created
144 // only for defs in the machine instr since, we assume that all Values are
145 // defined before they are used. However, there can be multiple defs for
146 // the same Value in machine instructions.
148 // Also, find CALL and RETURN instructions, which need extra work.
150 MachineFunction &MF = MachineFunction::get(Meth);
151 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
152 MachineBasicBlock &MBB = *BBI;
154 // iterate over all the machine instructions in BB
155 for(MachineBasicBlock::iterator MInstIterator = MBB.begin();
156 MInstIterator != MBB.end(); ++MInstIterator) {
157 MachineInstr *MInst = *MInstIterator;
159 // If the machine instruction is a call/return instruction, add it to
160 // CallRetInstrList for processing its args, ret value, and ret addr.
162 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
163 TM.getInstrInfo().isCall(MInst->getOpCode()))
164 CallRetInstrList.push_back(MInst);
166 // iterate over explicit MI operands and create a new LR
167 // for each operand that is defined by the instruction
168 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
169 OpE = MInst->end(); OpI != OpE; ++OpI)
171 const Value *Def = *OpI;
172 bool isCC = (OpI.getMachineOperand().getType()
173 == MachineOperand::MO_CCRegister);
174 createOrAddToLiveRange(Def, isCC);
177 // iterate over implicit MI operands and create a new LR
178 // for each operand that is defined by the instruction
179 for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i)
180 if (MInst->implicitRefIsDefined(i)) {
181 const Value *Def = MInst->getImplicitRef(i);
182 createOrAddToLiveRange(Def, /*isCC*/ false);
185 } // for all machine instructions in the BB
187 } // for all BBs in function
189 // Now we have to suggest clors for call and return arg live ranges.
190 // Also, if there are implicit defs (e.g., retun value of a call inst)
191 // they must be added to the live range list
193 suggestRegs4CallRets();
195 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
196 cerr << "Initial Live Ranges constructed!\n";
200 //---------------------------------------------------------------------------
201 // If some live ranges must be colored with specific hardware registers
202 // (e.g., for outgoing call args), suggesting of colors for such live
203 // ranges is done using target specific function. Those functions are called
204 // from this function. The target specific methods must:
205 // 1) suggest colors for call and return args.
206 // 2) create new LRs for implicit defs in machine instructions
207 //---------------------------------------------------------------------------
208 void LiveRangeInfo::suggestRegs4CallRets()
210 CallRetInstrListType::iterator It = CallRetInstrList.begin();
211 for( ; It != CallRetInstrList.end(); ++It ) {
213 MachineInstr *MInst = *It;
214 MachineOpCode OpCode = MInst->getOpCode();
216 if( (TM.getInstrInfo()).isReturn(OpCode) )
217 MRI.suggestReg4RetValue( MInst, *this);
219 else if( (TM.getInstrInfo()).isCall( OpCode ) )
220 MRI.suggestRegs4CallArgs( MInst, *this);
223 assert( 0 && "Non call/ret instr in CallRetInstrList" );
229 //--------------------------------------------------------------------------
230 // The following method coalesces live ranges when possible. This method
231 // must be called after the interference graph has been constructed.
235 for each BB in function
236 for each machine instruction (inst)
237 for each definition (def) in inst
238 for each operand (op) of inst that is a use
239 if the def and op are of the same register type
240 if the def and op do not interfere //i.e., not simultaneously live
241 if (degree(LR of def) + degree(LR of op)) <= # avail regs
242 if both LRs do not have suggested colors
243 merge2IGNodes(def, op) // i.e., merge 2 LRs
246 //---------------------------------------------------------------------------
247 void LiveRangeInfo::coalesceLRs()
249 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
250 cerr << "\nCoalescing LRs ...\n";
252 MachineFunction &MF = MachineFunction::get(Meth);
253 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
254 MachineBasicBlock &MBB = *BBI;
256 // iterate over all the machine instructions in BB
257 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
258 const MachineInstr *MI = *MII;
260 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
261 cerr << " *Iterating over machine instr ";
266 // iterate over MI operands to find defs
267 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
268 DefE = MI->end(); DefI != DefE; ++DefI) {
269 if (DefI.isDef()) { // iff this operand is a def
270 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
271 RegClass *RCOfDef = LROfDef->getRegClass();
273 MachineInstr::const_val_op_iterator UseI = MI->begin(),
275 for( ; UseI != UseE; ++UseI) { // for all uses
276 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
277 if (!LROfUse) { // if LR of use is not found
278 //don't warn about labels
279 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
280 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
281 continue; // ignore and continue
284 if (LROfUse == LROfDef) // nothing to merge if they are same
287 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
289 // If the two RegTypes are the same
290 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
292 unsigned CombinedDegree =
293 LROfDef->getUserIGNode()->getNumOfNeighbors() +
294 LROfUse->getUserIGNode()->getNumOfNeighbors();
296 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
297 // get more precise estimate of combined degree
298 CombinedDegree = LROfDef->getUserIGNode()->
299 getCombinedDegree(LROfUse->getUserIGNode());
302 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
303 // if both LRs do not have suggested colors
304 if (!(LROfDef->hasSuggestedColor() &&
305 LROfUse->hasSuggestedColor())) {
307 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
308 unionAndUpdateLRs(LROfDef, LROfUse);
311 } // if combined degree is less than # of regs
312 } // if def and use do not interfere
313 }// if reg classes are the same
317 } // for all machine instructions
320 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
321 cerr << "\nCoalescing Done!\n";
328 /*--------------------------- Debug code for printing ---------------*/
331 void LiveRangeInfo::printLiveRanges() {
332 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
333 cerr << "\nPrinting Live Ranges from Hash Map:\n";
334 for( ; HMI != LiveRangeMap.end(); ++HMI) {
335 if (HMI->first && HMI->second) {
336 cerr << " Value* " << RAV(HMI->first) << "\t: ";
337 if (IGNode* igNode = HMI->second->getUserIGNode())
338 cerr << "LR# " << igNode->getIndex();
340 cerr << "LR# " << "<no-IGNode>";
341 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";