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() {
209 std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin();
210 for( ; It != CallRetInstrList.end(); ++It) {
211 MachineInstr *MInst = *It;
212 MachineOpCode OpCode = MInst->getOpCode();
214 if ((TM.getInstrInfo()).isReturn(OpCode))
215 MRI.suggestReg4RetValue(MInst, *this);
216 else if ((TM.getInstrInfo()).isCall(OpCode))
217 MRI.suggestRegs4CallArgs(MInst, *this);
219 assert( 0 && "Non call/ret instr in CallRetInstrList" );
224 //--------------------------------------------------------------------------
225 // The following method coalesces live ranges when possible. This method
226 // must be called after the interference graph has been constructed.
230 for each BB in function
231 for each machine instruction (inst)
232 for each definition (def) in inst
233 for each operand (op) of inst that is a use
234 if the def and op are of the same register type
235 if the def and op do not interfere //i.e., not simultaneously live
236 if (degree(LR of def) + degree(LR of op)) <= # avail regs
237 if both LRs do not have suggested colors
238 merge2IGNodes(def, op) // i.e., merge 2 LRs
241 //---------------------------------------------------------------------------
242 void LiveRangeInfo::coalesceLRs()
244 if(DEBUG_RA >= RA_DEBUG_LiveRanges)
245 cerr << "\nCoalescing LRs ...\n";
247 MachineFunction &MF = MachineFunction::get(Meth);
248 for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) {
249 MachineBasicBlock &MBB = *BBI;
251 // iterate over all the machine instructions in BB
252 for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){
253 const MachineInstr *MI = *MII;
255 if( DEBUG_RA >= RA_DEBUG_LiveRanges) {
256 cerr << " *Iterating over machine instr ";
261 // iterate over MI operands to find defs
262 for(MachineInstr::const_val_op_iterator DefI = MI->begin(),
263 DefE = MI->end(); DefI != DefE; ++DefI) {
264 if (DefI.isDef()) { // iff this operand is a def
265 LiveRange *LROfDef = getLiveRangeForValue( *DefI );
266 RegClass *RCOfDef = LROfDef->getRegClass();
268 MachineInstr::const_val_op_iterator UseI = MI->begin(),
270 for( ; UseI != UseE; ++UseI) { // for all uses
271 LiveRange *LROfUse = getLiveRangeForValue( *UseI );
272 if (!LROfUse) { // if LR of use is not found
273 //don't warn about labels
274 if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges)
275 cerr << " !! Warning: No LR for use " << RAV(*UseI) << "\n";
276 continue; // ignore and continue
279 if (LROfUse == LROfDef) // nothing to merge if they are same
282 if (MRI.getRegType(LROfDef) == MRI.getRegType(LROfUse)) {
284 // If the two RegTypes are the same
285 if (!RCOfDef->getInterference(LROfDef, LROfUse) ) {
287 unsigned CombinedDegree =
288 LROfDef->getUserIGNode()->getNumOfNeighbors() +
289 LROfUse->getUserIGNode()->getNumOfNeighbors();
291 if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) {
292 // get more precise estimate of combined degree
293 CombinedDegree = LROfDef->getUserIGNode()->
294 getCombinedDegree(LROfUse->getUserIGNode());
297 if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) {
298 // if both LRs do not have suggested colors
299 if (!(LROfDef->hasSuggestedColor() &&
300 LROfUse->hasSuggestedColor())) {
302 RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
303 unionAndUpdateLRs(LROfDef, LROfUse);
306 } // if combined degree is less than # of regs
307 } // if def and use do not interfere
308 }// if reg classes are the same
312 } // for all machine instructions
315 if (DEBUG_RA >= RA_DEBUG_LiveRanges)
316 cerr << "\nCoalescing Done!\n";
323 /*--------------------------- Debug code for printing ---------------*/
326 void LiveRangeInfo::printLiveRanges() {
327 LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator
328 cerr << "\nPrinting Live Ranges from Hash Map:\n";
329 for( ; HMI != LiveRangeMap.end(); ++HMI) {
330 if (HMI->first && HMI->second) {
331 cerr << " Value* " << RAV(HMI->first) << "\t: ";
332 if (IGNode* igNode = HMI->second->getUserIGNode())
333 cerr << "LR# " << igNode->getIndex();
335 cerr << "LR# " << "<no-IGNode>";
336 cerr << "\t:Values = "; printSet(*HMI->second); cerr << "\n";