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/MachineCodeForBasicBlock.h"
12 #include "llvm/Target/TargetMachine.h"
13 #include "llvm/Function.h"
14 #include "llvm/BasicBlock.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
82 //---------------------------------------------------------------------------
83 // Method for constructing all live ranges in a function. It creates live
84 // ranges for all values defined in the instruction stream. Also, it
85 // creates live ranges for all incoming arguments of the function.
86 //---------------------------------------------------------------------------
87 void LiveRangeInfo::constructLiveRanges() {
89 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
90 cerr << "Constructing Live Ranges ...\n";
92 // first find the live ranges for all incoming args of the function since
93 // those LRs start from the start of the function
94 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI){
95 LiveRange *ArgRange = new LiveRange(); // creates a new LR and
96 ArgRange->insert(AI); // add the arg (def) to it
97 LiveRangeMap[AI] = ArgRange;
99 // create a temp machine op to find the register class of value
100 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
102 unsigned rcid = MRI.getRegClassIDOfValue(AI);
103 ArgRange->setRegClass(RegClassList[rcid]);
106 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
107 cerr << " Adding LiveRange for argument " << RAV(AI) << "\n";
110 // Now suggest hardware registers for these function args
111 MRI.suggestRegs4MethodArgs(Meth, *this);
114 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
117 for (Function::const_iterator BBI=Meth->begin(); BBI != Meth->end(); ++BBI){
118 // Now find all LRs for machine the instructions. A new LR will be created
119 // only for defs in the machine instr since, we assume that all Values are
120 // defined before they are used. However, there can be multiple defs for
121 // the same Value in machine instructions.
123 // get the iterator for machine instructions
124 MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
126 // iterate over all the machine instructions in BB
127 for(MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
128 MInstIterator != MIVec.end(); ++MInstIterator) {
129 MachineInstr *MInst = *MInstIterator;
131 // Now if the machine instruction is a call/return instruction,
132 // add it to CallRetInstrList for processing its implicit operands
134 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
135 TM.getInstrInfo().isCall(MInst->getOpCode()))
136 CallRetInstrList.push_back( MInst );
139 // iterate over MI operands to find defs
140 for (MachineInstr::val_op_iterator OpI = MInst->begin(),
141 OpE = MInst->end(); OpI != OpE; ++OpI) {
142 if(DEBUG_RA >= RA_DEBUG_LiveRanges) {
143 MachineOperand::MachineOperandType OpTyp =
144 OpI.getMachineOperand().getOperandType();
146 if (OpTyp == MachineOperand::MO_CCRegister)
147 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"
148 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
151 // create a new LR iff this operand is a def
153 const Value *Def = *OpI;
155 // Only instruction values are accepted for live ranges here
156 if (Def->getValueType() != Value::InstructionVal ) {
157 cerr << "\n**%%Error: Def is not an instruction val. Def="
162 LiveRange *DefRange = LiveRangeMap[Def];
164 // see LR already there (because of multiple defs)
165 if( !DefRange) { // if it is not in LiveRangeMap
166 DefRange = new LiveRange(); // creates a new live range and
167 DefRange->insert(Def); // add the instruction (def) to it
168 LiveRangeMap[ Def ] = DefRange; // update the map
170 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
171 cerr << " creating a LR for def: " << RAV(Def) << "\n";
173 // set the register class of the new live range
174 //assert( RegClassList.size() );
175 MachineOperand::MachineOperandType OpTy =
176 OpI.getMachineOperand().getOperandType();
178 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
179 unsigned rcid = MRI.getRegClassIDOfValue(
180 OpI.getMachineOperand().getVRegValue(), isCC );
183 if (isCC && DEBUG_RA >= RA_DEBUG_LiveRanges)
184 cerr << "\a**created a LR for a CC reg:"
185 << RAV(OpI.getMachineOperand().getVRegValue());
187 DefRange->setRegClass(RegClassList[rcid]);
189 DefRange->insert(Def); // add the opearand to def range
190 // update the map - Operand points
192 LiveRangeMap[Def] = DefRange;
194 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
195 cerr << " Added to existing LR for def: " << RAV(Def) << "\n";
200 } // for all opereands in machine instructions
202 } // for all machine instructions in the BB
204 } // for all BBs in function
207 // Now we have to suggest clors for call and return arg live ranges.
208 // Also, if there are implicit defs (e.g., retun value of a call inst)
209 // they must be added to the live range list
211 suggestRegs4CallRets();
213 if( DEBUG_RA >= RA_DEBUG_LiveRanges)
214 cerr << "Initial Live Ranges constructed!\n";
219 //---------------------------------------------------------------------------
220 // If some live ranges must be colored with specific hardware registers
221 // (e.g., for outgoing call args), suggesting of colors for such live
222 // ranges is done using target specific function. Those functions are called
223 // from this function. The target specific methods must:
224 // 1) suggest colors for call and return args.
225 // 2) create new LRs for implicit defs in machine instructions
226 //---------------------------------------------------------------------------
227 void LiveRangeInfo::suggestRegs4CallRets()
229 CallRetInstrListType::iterator It = CallRetInstrList.begin();
230 for( ; It != CallRetInstrList.end(); ++It ) {
232 MachineInstr *MInst = *It;
233 MachineOpCode OpCode = MInst->getOpCode();
235 if( (TM.getInstrInfo()).isReturn(OpCode) )
236 MRI.suggestReg4RetValue( MInst, *this);
238 else if( (TM.getInstrInfo()).isCall( OpCode ) )
239 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
242 assert( 0 && "Non call/ret instr in CallRetInstrList" );
248 //--------------------------------------------------------------------------
249 // The following method coalesces live ranges when possible. This method
250 // must be called after the interference graph has been constructed.
254 for each BB in function
255 for each machine instruction (inst)
256 for each definition (def) in inst
257 for each operand (op) of inst that is a use
258 if the def and op are of the same register type
259 if the def and op do not interfere //i.e., not simultaneously live
260 if (degree(LR of def) + degree(LR of op)) <= # avail regs
261 if both LRs do not have suggested colors
262 merge2IGNodes(def, op) // i.e., merge 2 LRs
265 //---------------------------------------------------------------------------
266 void LiveRangeInfo::coalesceLRs()
268 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
269 cerr << "\nCoalescing LRs ...\n";
271 for(Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
274 // get the iterator for machine instructions
275 const MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
276 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
278 // iterate over all the machine instructions in BB
279 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
281 const MachineInstr * MInst = *MInstIterator;
283 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
284 cerr << " *Iterating over machine instr ";
290 // iterate over MI operands to find defs
291 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
292 DefE = MInst->end(); DefI != DefE; ++DefI) {
293 if (DefI.isDef()) { // iff this operand is a def
294 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
295 RegClass *RCOfDef = LROfDef->getRegClass();
297 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
299 for( ; UseI != UseE; ++UseI){ // for all uses
301 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
302 if (!LROfUse) { // if LR of use is not found
303 //don't warn about labels
304 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
305 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
306 continue; // ignore and continue
309 if (LROfUse == LROfDef) // nothing to merge if they are same
312 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
314 // If the two RegTypes are the same
315 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
317 unsigned CombinedDegree =
318 LROfDef->getUserIGNode()->getNumOfNeighbors() +
319 LROfUse->getUserIGNode()->getNumOfNeighbors();
321 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
322 // if both LRs do not have suggested colors
323 if (!(LROfDef->hasSuggestedColor() &&
324 LROfUse->hasSuggestedColor())) {
326 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
327 unionAndUpdateLRs(LROfDef, LROfUse);
330 } // if combined degree is less than # of regs
331 } // if def and use do not interfere
332 }// if reg classes are the same
336 } // for all machine instructions
339 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
340 cerr << "\nCoalescing Done!\n";
347 /*--------------------------- Debug code for printing ---------------*/
350 void LiveRangeInfo::printLiveRanges() {
351 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
352 cerr << "\nPrinting Live Ranges from Hash Map:\n";
353 for( ; HMI != LiveRangeMap.end(); ++HMI) {
354 if (HMI->first && HMI->second) {
355 cerr << " Value* " << RAV(HMI->first) << "\t: ";
356 cerr << "LR# " << HMI->second->getUserIGNode()->getIndex();
357 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";