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/Method.h"
6 #include "llvm/BasicBlock.h"
7 #include "Support/SetOperations.h"
11 LiveRangeInfo::LiveRangeInfo(const Method *M, const TargetMachine &tm,
12 std::vector<RegClass *> &RCL)
13 : Meth(M), 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 method. 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 method.
79 //---------------------------------------------------------------------------
80 void LiveRangeInfo::constructLiveRanges() {
83 cerr << "Consturcting Live Ranges ...\n";
85 // first find the live ranges for all incoming args of the method since
86 // those LRs start from the start of the method
88 // get the argument list
89 const Method::ArgumentListType& ArgList = Meth->getArgumentList();
90 // get an iterator to arg list
91 Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
94 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
95 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
96 const Value *Val = (const Value *) *ArgIt;
98 ArgRange->insert(Val); // add the arg (def) to it
99 LiveRangeMap[Val] = ArgRange;
101 // create a temp machine op to find the register class of value
102 //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
104 unsigned rcid = MRI.getRegClassIDOfValue( Val );
105 ArgRange->setRegClass(RegClassList[ rcid ] );
109 cerr << " adding LiveRange for argument "
110 << RAV((const Value *)*ArgIt) << "\n";
114 // Now suggest hardware registers for these method args
115 MRI.suggestRegs4MethodArgs(Meth, *this);
119 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
122 for (Method::const_iterator BBI = Meth->begin(); BBI != Meth->end(); ++BBI) {
123 // Now find all LRs for machine the instructions. A new LR will be created
124 // only for defs in the machine instr since, we assume that all Values are
125 // defined before they are used. However, there can be multiple defs for
126 // the same Value in machine instructions.
128 // get the iterator for machine instructions
129 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
131 // iterate over all the machine instructions in BB
132 for(MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
133 MInstIterator != MIVec.end(); ++MInstIterator) {
134 const MachineInstr *MInst = *MInstIterator;
136 // Now if the machine instruction is a call/return instruction,
137 // add it to CallRetInstrList for processing its implicit operands
139 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
140 TM.getInstrInfo().isCall(MInst->getOpCode()))
141 CallRetInstrList.push_back( MInst );
144 // iterate over MI operands to find defs
145 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
146 OpE = MInst->end(); OpI != OpE; ++OpI) {
148 MachineOperand::MachineOperandType OpTyp =
149 OpI.getMachineOperand().getOperandType();
151 if (OpTyp == MachineOperand::MO_CCRegister)
152 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"
153 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
156 // create a new LR iff this operand is a def
158 const Value *Def = *OpI;
160 // Only instruction values are accepted for live ranges here
161 if (Def->getValueType() != Value::InstructionVal ) {
162 cerr << "\n**%%Error: Def is not an instruction val. Def="
167 LiveRange *DefRange = LiveRangeMap[Def];
169 // see LR already there (because of multiple defs)
170 if( !DefRange) { // if it is not in LiveRangeMap
171 DefRange = new LiveRange(); // creates a new live range and
172 DefRange->insert(Def); // add the instruction (def) to it
173 LiveRangeMap[ Def ] = DefRange; // update the map
176 cerr << " creating a LR for def: " << RAV(Def) << "\n";
178 // set the register class of the new live range
179 //assert( RegClassList.size() );
180 MachineOperand::MachineOperandType OpTy =
181 OpI.getMachineOperand().getOperandType();
183 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
184 unsigned rcid = MRI.getRegClassIDOfValue(
185 OpI.getMachineOperand().getVRegValue(), isCC );
188 if (isCC && DEBUG_RA)
189 cerr << "\a**created a LR for a CC reg:"
190 << RAV(OpI.getMachineOperand().getVRegValue());
192 DefRange->setRegClass(RegClassList[rcid]);
194 DefRange->insert(Def); // add the opearand to def range
195 // update the map - Operand points
197 LiveRangeMap[Def] = DefRange;
200 cerr << " added to an existing LR for def: "
206 } // for all opereands in machine instructions
208 } // for all machine instructions in the BB
210 } // for all BBs in method
213 // Now we have to suggest clors for call and return arg live ranges.
214 // Also, if there are implicit defs (e.g., retun value of a call inst)
215 // they must be added to the live range list
217 suggestRegs4CallRets();
220 cerr << "Initial Live Ranges constructed!\n";
225 //---------------------------------------------------------------------------
226 // If some live ranges must be colored with specific hardware registers
227 // (e.g., for outgoing call args), suggesting of colors for such live
228 // ranges is done using target specific method. Those methods are called
229 // from this function. The target specific methods must:
230 // 1) suggest colors for call and return args.
231 // 2) create new LRs for implicit defs in machine instructions
232 //---------------------------------------------------------------------------
233 void LiveRangeInfo::suggestRegs4CallRets()
236 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
238 for( ; It != CallRetInstrList.end(); ++It ) {
240 const MachineInstr *MInst = *It;
241 MachineOpCode OpCode = MInst->getOpCode();
243 if( (TM.getInstrInfo()).isReturn(OpCode) )
244 MRI.suggestReg4RetValue( MInst, *this);
246 else if( (TM.getInstrInfo()).isCall( OpCode ) )
247 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
250 assert( 0 && "Non call/ret instr in CallRetInstrList" );
256 //--------------------------------------------------------------------------
257 // The following method coalesces live ranges when possible. This method
258 // must be called after the interference graph has been constructed.
262 for each BB in method
263 for each machine instruction (inst)
264 for each definition (def) in inst
265 for each operand (op) of inst that is a use
266 if the def and op are of the same register type
267 if the def and op do not interfere //i.e., not simultaneously live
268 if (degree(LR of def) + degree(LR of op)) <= # avail regs
269 if both LRs do not have suggested colors
270 merge2IGNodes(def, op) // i.e., merge 2 LRs
273 //---------------------------------------------------------------------------
274 void LiveRangeInfo::coalesceLRs()
277 cerr << "\nCoalscing LRs ...\n";
279 Method::const_iterator BBI = Meth->begin(); // random iterator for BBs
281 for( ; BBI != Meth->end(); ++BBI) { // traverse BBs in random order
283 // get the iterator for machine instructions
284 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
285 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
287 // iterate over all the machine instructions in BB
288 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
290 const MachineInstr * MInst = *MInstIterator;
293 cerr << " *Iterating over machine instr ";
299 // iterate over MI operands to find defs
300 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
301 DefE = MInst->end(); DefI != DefE; ++DefI) {
302 if (DefI.isDef()) { // iff this operand is a def
303 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
304 RegClass *RCOfDef = LROfDef->getRegClass();
306 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
308 for( ; UseI != UseE; ++UseI){ // for all uses
310 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
311 if (!LROfUse) { // if LR of use is not found
312 //don't warn about labels
313 if (!isa<BasicBlock>(*UseI) && DEBUG_RA)
314 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
315 continue; // ignore and continue
318 if (LROfUse == LROfDef) // nothing to merge if they are same
321 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
323 // If the two RegTypes are the same
324 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
326 unsigned CombinedDegree =
327 LROfDef->getUserIGNode()->getNumOfNeighbors() +
328 LROfUse->getUserIGNode()->getNumOfNeighbors();
330 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
331 // if both LRs do not have suggested colors
332 if (!(LROfDef->hasSuggestedColor() &&
333 LROfUse->hasSuggestedColor())) {
335 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
336 unionAndUpdateLRs(LROfDef, LROfUse);
339 } // if combined degree is less than # of regs
340 } // if def and use do not interfere
341 }// if reg classes are the same
345 } // for all machine instructions
349 cerr << "\nCoalscing Done!\n";
356 /*--------------------------- Debug code for printing ---------------*/
359 void LiveRangeInfo::printLiveRanges() {
360 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
361 cerr << "\nPrinting Live Ranges from Hash Map:\n";
362 for( ; HMI != LiveRangeMap.end(); ++HMI) {
363 if (HMI->first && HMI->second) {
364 cerr << " " << RAV(HMI->first) << "\t: ";
365 printSet(*HMI->second); cerr << "\n";