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
88 // get the argument list
89 const Function::ArgumentListType& ArgList = Meth->getArgumentList();
91 Function::ArgumentListType::const_iterator ArgIt = ArgList.begin();
92 for( ; ArgIt != ArgList.end() ; ++ArgIt) { // for each argument
93 LiveRange * ArgRange = new LiveRange(); // creates a new LR and
94 const Value *Val = (const Value *) *ArgIt;
96 ArgRange->insert(Val); // add the arg (def) to it
97 LiveRangeMap[Val] = 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( Val );
103 ArgRange->setRegClass(RegClassList[ rcid ] );
107 cerr << " adding LiveRange for argument "
108 << RAV((const Value *)*ArgIt) << "\n";
112 // Now suggest hardware registers for these function args
113 MRI.suggestRegs4MethodArgs(Meth, *this);
116 // Now find speical LLVM instructions (CALL, RET) and LRs in machine
119 for (Function::const_iterator BBI = Meth->begin(); BBI != Meth->end(); ++BBI){
120 // Now find all LRs for machine the instructions. A new LR will be created
121 // only for defs in the machine instr since, we assume that all Values are
122 // defined before they are used. However, there can be multiple defs for
123 // the same Value in machine instructions.
125 // get the iterator for machine instructions
126 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
128 // iterate over all the machine instructions in BB
129 for(MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
130 MInstIterator != MIVec.end(); ++MInstIterator) {
131 const MachineInstr *MInst = *MInstIterator;
133 // Now if the machine instruction is a call/return instruction,
134 // add it to CallRetInstrList for processing its implicit operands
136 if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ||
137 TM.getInstrInfo().isCall(MInst->getOpCode()))
138 CallRetInstrList.push_back( MInst );
141 // iterate over MI operands to find defs
142 for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
143 OpE = MInst->end(); OpI != OpE; ++OpI) {
145 MachineOperand::MachineOperandType OpTyp =
146 OpI.getMachineOperand().getOperandType();
148 if (OpTyp == MachineOperand::MO_CCRegister)
149 cerr << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"
150 << RAV(OpI.getMachineOperand().getVRegValue()) << "\n";
153 // create a new LR iff this operand is a def
155 const Value *Def = *OpI;
157 // Only instruction values are accepted for live ranges here
158 if (Def->getValueType() != Value::InstructionVal ) {
159 cerr << "\n**%%Error: Def is not an instruction val. Def="
164 LiveRange *DefRange = LiveRangeMap[Def];
166 // see LR already there (because of multiple defs)
167 if( !DefRange) { // if it is not in LiveRangeMap
168 DefRange = new LiveRange(); // creates a new live range and
169 DefRange->insert(Def); // add the instruction (def) to it
170 LiveRangeMap[ Def ] = DefRange; // update the map
173 cerr << " creating a LR for def: " << RAV(Def) << "\n";
175 // set the register class of the new live range
176 //assert( RegClassList.size() );
177 MachineOperand::MachineOperandType OpTy =
178 OpI.getMachineOperand().getOperandType();
180 bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
181 unsigned rcid = MRI.getRegClassIDOfValue(
182 OpI.getMachineOperand().getVRegValue(), isCC );
185 if (isCC && DEBUG_RA)
186 cerr << "\a**created a LR for a CC reg:"
187 << RAV(OpI.getMachineOperand().getVRegValue());
189 DefRange->setRegClass(RegClassList[rcid]);
191 DefRange->insert(Def); // add the opearand to def range
192 // update the map - Operand points
194 LiveRangeMap[Def] = DefRange;
197 cerr << " added to an existing LR for def: "
203 } // for all opereands in machine instructions
205 } // for all machine instructions in the BB
207 } // for all BBs in function
210 // Now we have to suggest clors for call and return arg live ranges.
211 // Also, if there are implicit defs (e.g., retun value of a call inst)
212 // they must be added to the live range list
214 suggestRegs4CallRets();
217 cerr << "Initial Live Ranges constructed!\n";
222 //---------------------------------------------------------------------------
223 // If some live ranges must be colored with specific hardware registers
224 // (e.g., for outgoing call args), suggesting of colors for such live
225 // ranges is done using target specific function. Those functions are called
226 // from this function. The target specific methods must:
227 // 1) suggest colors for call and return args.
228 // 2) create new LRs for implicit defs in machine instructions
229 //---------------------------------------------------------------------------
230 void LiveRangeInfo::suggestRegs4CallRets()
232 CallRetInstrListType::const_iterator It = CallRetInstrList.begin();
233 for( ; It != CallRetInstrList.end(); ++It ) {
235 const MachineInstr *MInst = *It;
236 MachineOpCode OpCode = MInst->getOpCode();
238 if( (TM.getInstrInfo()).isReturn(OpCode) )
239 MRI.suggestReg4RetValue( MInst, *this);
241 else if( (TM.getInstrInfo()).isCall( OpCode ) )
242 MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
245 assert( 0 && "Non call/ret instr in CallRetInstrList" );
251 //--------------------------------------------------------------------------
252 // The following method coalesces live ranges when possible. This method
253 // must be called after the interference graph has been constructed.
257 for each BB in function
258 for each machine instruction (inst)
259 for each definition (def) in inst
260 for each operand (op) of inst that is a use
261 if the def and op are of the same register type
262 if the def and op do not interfere //i.e., not simultaneously live
263 if (degree(LR of def) + degree(LR of op)) <= # avail regs
264 if both LRs do not have suggested colors
265 merge2IGNodes(def, op) // i.e., merge 2 LRs
268 //---------------------------------------------------------------------------
269 void LiveRangeInfo::coalesceLRs()
272 cerr << "\nCoalscing LRs ...\n";
274 for(Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
277 // get the iterator for machine instructions
278 const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
279 MachineCodeForBasicBlock::const_iterator MInstIterator = MIVec.begin();
281 // iterate over all the machine instructions in BB
282 for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
284 const MachineInstr * MInst = *MInstIterator;
287 cerr << " *Iterating over machine instr ";
293 // iterate over MI operands to find defs
294 for(MachineInstr::const_val_op_iterator DefI = MInst->begin(),
295 DefE = MInst->end(); DefI != DefE; ++DefI) {
296 if (DefI.isDef()) { // iff this operand is a def
297 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
298 RegClass *RCOfDef = LROfDef->getRegClass();
300 MachineInstr::const_val_op_iterator UseI = MInst->begin(),
302 for( ; UseI != UseE; ++UseI){ // for all uses
304 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
305 if (!LROfUse) { // if LR of use is not found
306 //don't warn about labels
307 if (!isa<BasicBlock>(*UseI) && DEBUG_RA)
308 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
309 continue; // ignore and continue
312 if (LROfUse == LROfDef) // nothing to merge if they are same
315 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
317 // If the two RegTypes are the same
318 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
320 unsigned CombinedDegree =
321 LROfDef->getUserIGNode()->getNumOfNeighbors() +
322 LROfUse->getUserIGNode()->getNumOfNeighbors();
324 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
325 // if both LRs do not have suggested colors
326 if (!(LROfDef->hasSuggestedColor() &&
327 LROfUse->hasSuggestedColor())) {
329 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
330 unionAndUpdateLRs(LROfDef, LROfUse);
333 } // if combined degree is less than # of regs
334 } // if def and use do not interfere
335 }// if reg classes are the same
339 } // for all machine instructions
343 cerr << "\nCoalscing Done!\n";
350 /*--------------------------- Debug code for printing ---------------*/
353 void LiveRangeInfo::printLiveRanges() {
354 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
355 cerr << "\nPrinting Live Ranges from Hash Map:\n";
356 for( ; HMI != LiveRangeMap.end(); ++HMI) {
357 if (HMI->first && HMI->second) {
358 cerr << " " << RAV(HMI->first) << "\t: ";
359 printSet(*HMI->second); cerr << "\n";