1 #include "llvm/CodeGen/LiveRangeInfo.h"
2 #include "llvm/CodeGen/RegClass.h"
3 #include "llvm/CodeGen/MachineInstr.h"
4 #include "llvm/Target/TargetMachine.h"
5 #include "llvm/Function.h"
6 #include "llvm/BasicBlock.h"
7 #include "Support/SetOperations.h"
8 #include "llvm/CodeGen/RegAllocCommon.h"
11 LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm,
12 std::vector<RegClass *> &RCL)
13 : Meth(F), TM(tm), RegClassList(RCL), MRI(tm.getRegInfo()) { }
16 LiveRangeInfo::~LiveRangeInfo() {
17 for (LiveRangeMapType::iterator MI = LiveRangeMap.begin();
18 MI != LiveRangeMap.end(); ++MI) {
20 if (MI->first && MI->second) {
21 LiveRange *LR = MI->second;
23 // we need to be careful in deleting LiveRanges in LiveRangeMap
24 // since two/more Values in the live range map can point to the same
25 // live range. We have to make the other entries NULL when we delete
28 for(LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI)
29 LiveRangeMap[*LI] = 0;
37 //---------------------------------------------------------------------------
38 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
39 // Note: the caller must make sure that L1 and L2 are distinct and both
40 // LRs don't have suggested colors
41 //---------------------------------------------------------------------------
43 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) {
44 assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor()));
45 set_union(*L1, *L2); // add elements of L2 to L1
47 for(ValueSet::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) {
48 //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
50 L1->insert(*L2It); // add the var in L2 to L1
51 LiveRangeMap[*L2It] = L1; // now the elements in L2 should map
56 // Now if LROfDef(L1) has a suggested color, it will remain.
57 // But, if LROfUse(L2) has a suggested color, the new range
58 // must have the same color.
60 if(L2->hasSuggestedColor())
61 L1->setSuggestedColor(L2->getSuggestedColor());
64 if (L2->isCallInterference())
65 L1->setCallInterference();
67 // add the spill costs
68 L1->addSpillCost(L2->getSpillCost());
70 delete L2; // delete L2 as it is no longer needed
75 //---------------------------------------------------------------------------
76 // Method for constructing all live ranges in a function. It creates live
77 // ranges for all values defined in the instruction stream. Also, it
78 // creates live ranges for all incoming arguments of the function.
79 //---------------------------------------------------------------------------
80 void LiveRangeInfo::constructLiveRanges() {
83 cerr << "Consturcting Live Ranges ...\n";
85 // first find the live ranges for all incoming args of the function since
86 // those LRs start from the start of the function
87 for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI){
88 LiveRange *ArgRange = new LiveRange(); // creates a new LR and
89 ArgRange->insert(AI); // add the arg (def) to it
90 LiveRangeMap[AI] = ArgRange;
92 // create a temp machine op to find the register class of value
93 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
95 unsigned rcid = MRI.getRegClassIDOfValue(AI);
96 ArgRange->setRegClass(RegClassList[rcid]);
100 cerr << " adding LiveRange for argument " << RAV(AI) << "\n";
103 // Now suggest hardware registers for these function args
104 MRI.suggestRegs4MethodArgs(Meth, *this);
107 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
110 for (Function::const_iterator BBI = Meth->begin(); BBI != Meth->end(); ++BBI){
111 // Now find all LRs for machine the instructions. A new LR will be created
112 // only for defs in the machine instr since, we assume that all Values are
113 // defined before they are used. However, there can be multiple defs for
114 // the same Value in machine instructions.
116 // get the iterator for machine instructions
117 const MachineCodeForBasicBlock& MIVec = BBI->getMachineInstrVec();
119 // iterate over all the machine instructions in BB
120 for(MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
121 MInstIterator != MIVec.end(); ++MInstIterator) {
122 const MachineInstr *MInst = *MInstIterator;
124 // Now if the machine instruction is a call/return instruction,
125 // add it to CallRetInstrList for processing its implicit operands
127 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
128 TM.getInstrInfo().isCall(MInst->getOpCode()))
129 CallRetInstrList.push_back( MInst );
132 // iterate over MI operands to find defs
133 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
134 OpE = MInst->end(); OpI != OpE; ++OpI) {
136 MachineOperand::MachineOperandType OpTyp =
137 OpI.getMachineOperand().getOperandType();
139 if (OpTyp == MachineOperand::MO_CCRegister)
140 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"
141 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
144 // create a new LR iff this operand is a def
146 const Value *Def = *OpI;
148 // Only instruction values are accepted for live ranges here
149 if (Def->getValueType() != Value::InstructionVal ) {
150 cerr << "\n**%%Error: Def is not an instruction val. Def="
155 LiveRange *DefRange = LiveRangeMap[Def];
157 // see LR already there (because of multiple defs)
158 if( !DefRange) { // if it is not in LiveRangeMap
159 DefRange = new LiveRange(); // creates a new live range and
160 DefRange->insert(Def); // add the instruction (def) to it
161 LiveRangeMap[ Def ] = DefRange; // update the map
164 cerr << " creating a LR for def: " << RAV(Def) << "\n";
166 // set the register class of the new live range
167 //assert( RegClassList.size() );
168 MachineOperand::MachineOperandType OpTy =
169 OpI.getMachineOperand().getOperandType();
171 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
172 unsigned rcid = MRI.getRegClassIDOfValue(
173 OpI.getMachineOperand().getVRegValue(), isCC );
176 if (isCC && DEBUG_RA)
177 cerr << "\a**created a LR for a CC reg:"
178 << RAV(OpI.getMachineOperand().getVRegValue());
180 DefRange->setRegClass(RegClassList[rcid]);
182 DefRange->insert(Def); // add the opearand to def range
183 // update the map - Operand points
185 LiveRangeMap[Def] = DefRange;
188 cerr << " added to an existing LR for def: "
194 } // for all opereands in machine instructions
196 } // for all machine instructions in the BB
198 } // for all BBs in function
201 // Now we have to suggest clors for call and return arg live ranges.
202 // Also, if there are implicit defs (e.g., retun value of a call inst)
203 // they must be added to the live range list
205 suggestRegs4CallRets();
208 cerr << "Initial Live Ranges constructed!\n";
213 //---------------------------------------------------------------------------
214 // If some live ranges must be colored with specific hardware registers
215 // (e.g., for outgoing call args), suggesting of colors for such live
216 // ranges is done using target specific function. Those functions are called
217 // from this function. The target specific methods must:
218 // 1) suggest colors for call and return args.
219 // 2) create new LRs for implicit defs in machine instructions
220 //---------------------------------------------------------------------------
221 void LiveRangeInfo::suggestRegs4CallRets()
223 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
224 for( ; It != CallRetInstrList.end(); ++It ) {
226 const MachineInstr *MInst = *It;
227 MachineOpCode OpCode = MInst->getOpCode();
229 if( (TM.getInstrInfo()).isReturn(OpCode) )
230 MRI.suggestReg4RetValue( MInst, *this);
232 else if( (TM.getInstrInfo()).isCall( OpCode ) )
233 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
236 assert( 0 && "Non call/ret instr in CallRetInstrList" );
242 //--------------------------------------------------------------------------
243 // The following method coalesces live ranges when possible. This method
244 // must be called after the interference graph has been constructed.
248 for each BB in function
249 for each machine instruction (inst)
250 for each definition (def) in inst
251 for each operand (op) of inst that is a use
252 if the def and op are of the same register type
253 if the def and op do not interfere //i.e., not simultaneously live
254 if (degree(LR of def) + degree(LR of op)) <= # avail regs
255 if both LRs do not have suggested colors
256 merge2IGNodes(def, op) // i.e., merge 2 LRs
259 //---------------------------------------------------------------------------
260 void LiveRangeInfo::coalesceLRs()
263 cerr << "\nCoalscing LRs ...\n";
265 for(Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
268 // get the iterator for machine instructions
269 const MachineCodeForBasicBlock& MIVec = BBI->getMachineInstrVec();
270 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
272 // iterate over all the machine instructions in BB
273 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
275 const MachineInstr * MInst = *MInstIterator;
278 cerr << " *Iterating over machine instr ";
284 // iterate over MI operands to find defs
285 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
286 DefE = MInst->end(); DefI != DefE; ++DefI) {
287 if (DefI.isDef()) { // iff this operand is a def
288 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
289 RegClass *RCOfDef = LROfDef->getRegClass();
291 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
293 for( ; UseI != UseE; ++UseI){ // for all uses
295 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
296 if (!LROfUse) { // if LR of use is not found
297 //don't warn about labels
298 if (!isa<BasicBlock>(*UseI) && DEBUG_RA)
299 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
300 continue; // ignore and continue
303 if (LROfUse == LROfDef) // nothing to merge if they are same
306 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
308 // If the two RegTypes are the same
309 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
311 unsigned CombinedDegree =
312 LROfDef->getUserIGNode()->getNumOfNeighbors() +
313 LROfUse->getUserIGNode()->getNumOfNeighbors();
315 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
316 // if both LRs do not have suggested colors
317 if (!(LROfDef->hasSuggestedColor() &&
318 LROfUse->hasSuggestedColor())) {
320 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
321 unionAndUpdateLRs(LROfDef, LROfUse);
324 } // if combined degree is less than # of regs
325 } // if def and use do not interfere
326 }// if reg classes are the same
330 } // for all machine instructions
334 cerr << "\nCoalscing Done!\n";
341 /*--------------------------- Debug code for printing ---------------*/
344 void LiveRangeInfo::printLiveRanges() {
345 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
346 cerr << "\nPrinting Live Ranges from Hash Map:\n";
347 for( ; HMI != LiveRangeMap.end(); ++HMI) {
348 if (HMI->first && HMI->second) {
349 cerr << " " << RAV(HMI->first) << "\t: ";
350 printSet(*HMI->second); cerr << "\n";