LLVM API Documentation
00001 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the LiveInterval analysis pass which is used 00011 // by the Linear Scan Register allocator. This pass linearizes the 00012 // basic blocks of the function in DFS order and uses the 00013 // LiveVariables pass to conservatively compute live intervals for 00014 // each virtual and physical register. 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #define DEBUG_TYPE "liveintervals" 00019 #include "LiveIntervalAnalysis.h" 00020 #include "VirtRegMap.h" 00021 #include "llvm/Value.h" 00022 #include "llvm/Analysis/LoopInfo.h" 00023 #include "llvm/CodeGen/LiveVariables.h" 00024 #include "llvm/CodeGen/MachineFrameInfo.h" 00025 #include "llvm/CodeGen/MachineInstr.h" 00026 #include "llvm/CodeGen/Passes.h" 00027 #include "llvm/CodeGen/SSARegMap.h" 00028 #include "llvm/Target/MRegisterInfo.h" 00029 #include "llvm/Target/TargetInstrInfo.h" 00030 #include "llvm/Target/TargetMachine.h" 00031 #include "llvm/Support/CommandLine.h" 00032 #include "llvm/Support/Debug.h" 00033 #include "llvm/ADT/Statistic.h" 00034 #include "llvm/ADT/STLExtras.h" 00035 #include <algorithm> 00036 #include <cmath> 00037 using namespace llvm; 00038 00039 namespace { 00040 RegisterAnalysis<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 00041 00042 Statistic<> numIntervals 00043 ("liveintervals", "Number of original intervals"); 00044 00045 Statistic<> numIntervalsAfter 00046 ("liveintervals", "Number of intervals after coalescing"); 00047 00048 Statistic<> numJoins 00049 ("liveintervals", "Number of interval joins performed"); 00050 00051 Statistic<> numPeep 00052 ("liveintervals", "Number of identity moves eliminated after coalescing"); 00053 00054 Statistic<> numFolded 00055 ("liveintervals", "Number of loads/stores folded into instructions"); 00056 00057 cl::opt<bool> 00058 EnableJoining("join-liveintervals", 00059 cl::desc("Join compatible live intervals"), 00060 cl::init(true)); 00061 }; 00062 00063 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 00064 { 00065 AU.addPreserved<LiveVariables>(); 00066 AU.addRequired<LiveVariables>(); 00067 AU.addPreservedID(PHIEliminationID); 00068 AU.addRequiredID(PHIEliminationID); 00069 AU.addRequiredID(TwoAddressInstructionPassID); 00070 AU.addRequired<LoopInfo>(); 00071 MachineFunctionPass::getAnalysisUsage(AU); 00072 } 00073 00074 void LiveIntervals::releaseMemory() 00075 { 00076 mi2iMap_.clear(); 00077 i2miMap_.clear(); 00078 r2iMap_.clear(); 00079 r2rMap_.clear(); 00080 } 00081 00082 00083 /// runOnMachineFunction - Register allocate the whole function 00084 /// 00085 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 00086 mf_ = &fn; 00087 tm_ = &fn.getTarget(); 00088 mri_ = tm_->getRegisterInfo(); 00089 lv_ = &getAnalysis<LiveVariables>(); 00090 allocatableRegs_ = mri_->getAllocatableSet(fn); 00091 r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 00092 00093 // number MachineInstrs 00094 unsigned miIndex = 0; 00095 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 00096 mbb != mbbEnd; ++mbb) 00097 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 00098 mi != miEnd; ++mi) { 00099 bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 00100 assert(inserted && "multiple MachineInstr -> index mappings"); 00101 i2miMap_.push_back(mi); 00102 miIndex += InstrSlots::NUM; 00103 } 00104 00105 computeIntervals(); 00106 00107 numIntervals += getNumIntervals(); 00108 00109 #if 1 00110 DEBUG(std::cerr << "********** INTERVALS **********\n"); 00111 DEBUG(for (iterator I = begin(), E = end(); I != E; ++I) 00112 std::cerr << I->second << "\n"); 00113 #endif 00114 00115 // join intervals if requested 00116 if (EnableJoining) joinIntervals(); 00117 00118 numIntervalsAfter += getNumIntervals(); 00119 00120 // perform a final pass over the instructions and compute spill 00121 // weights, coalesce virtual registers and remove identity moves 00122 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 00123 const TargetInstrInfo& tii = *tm_->getInstrInfo(); 00124 00125 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 00126 mbbi != mbbe; ++mbbi) { 00127 MachineBasicBlock* mbb = mbbi; 00128 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 00129 00130 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 00131 mii != mie; ) { 00132 // if the move will be an identity move delete it 00133 unsigned srcReg, dstReg, RegRep; 00134 if (tii.isMoveInstr(*mii, srcReg, dstReg) && 00135 (RegRep = rep(srcReg)) == rep(dstReg)) { 00136 // remove from def list 00137 LiveInterval &interval = getOrCreateInterval(RegRep); 00138 // remove index -> MachineInstr and 00139 // MachineInstr -> index mappings 00140 Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 00141 if (mi2i != mi2iMap_.end()) { 00142 i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 00143 mi2iMap_.erase(mi2i); 00144 } 00145 mii = mbbi->erase(mii); 00146 ++numPeep; 00147 } 00148 else { 00149 for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 00150 const MachineOperand& mop = mii->getOperand(i); 00151 if (mop.isRegister() && mop.getReg() && 00152 MRegisterInfo::isVirtualRegister(mop.getReg())) { 00153 // replace register with representative register 00154 unsigned reg = rep(mop.getReg()); 00155 mii->SetMachineOperandReg(i, reg); 00156 00157 LiveInterval &RegInt = getInterval(reg); 00158 RegInt.weight += 00159 (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth); 00160 } 00161 } 00162 ++mii; 00163 } 00164 } 00165 } 00166 00167 DEBUG(dump()); 00168 return true; 00169 } 00170 00171 /// print - Implement the dump method. 00172 void LiveIntervals::print(std::ostream &O) const { 00173 O << "********** INTERVALS **********\n"; 00174 for (const_iterator I = begin(), E = end(); I != E; ++I) 00175 O << " " << I->second << "\n"; 00176 00177 O << "********** MACHINEINSTRS **********\n"; 00178 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 00179 mbbi != mbbe; ++mbbi) { 00180 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 00181 for (MachineBasicBlock::iterator mii = mbbi->begin(), 00182 mie = mbbi->end(); mii != mie; ++mii) { 00183 O << getInstructionIndex(mii) << '\t' << *mii; 00184 } 00185 } 00186 } 00187 00188 std::vector<LiveInterval*> LiveIntervals:: 00189 addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 00190 // since this is called after the analysis is done we don't know if 00191 // LiveVariables is available 00192 lv_ = getAnalysisToUpdate<LiveVariables>(); 00193 00194 std::vector<LiveInterval*> added; 00195 00196 assert(li.weight != HUGE_VAL && 00197 "attempt to spill already spilled interval!"); 00198 00199 DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 00200 << li << '\n'); 00201 00202 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 00203 00204 for (LiveInterval::Ranges::const_iterator 00205 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 00206 unsigned index = getBaseIndex(i->start); 00207 unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 00208 for (; index != end; index += InstrSlots::NUM) { 00209 // skip deleted instructions 00210 while (index != end && !getInstructionFromIndex(index)) 00211 index += InstrSlots::NUM; 00212 if (index == end) break; 00213 00214 MachineBasicBlock::iterator mi = getInstructionFromIndex(index); 00215 00216 for_operand: 00217 for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 00218 MachineOperand& mop = mi->getOperand(i); 00219 if (mop.isRegister() && mop.getReg() == li.reg) { 00220 // First thing, attempt to fold the memory reference into the 00221 // instruction. If we can do this, we don't need to insert spill 00222 // code. 00223 if (MachineInstr* fmi = mri_->foldMemoryOperand(mi, i, slot)) { 00224 if (lv_) 00225 lv_->instructionChanged(mi, fmi); 00226 vrm.virtFolded(li.reg, mi, i, fmi); 00227 mi2iMap_.erase(mi); 00228 i2miMap_[index/InstrSlots::NUM] = fmi; 00229 mi2iMap_[fmi] = index; 00230 MachineBasicBlock &MBB = *mi->getParent(); 00231 mi = MBB.insert(MBB.erase(mi), fmi); 00232 ++numFolded; 00233 00234 // Folding the load/store can completely change the instruction in 00235 // unpredictable ways, rescan it from the beginning. 00236 goto for_operand; 00237 } else { 00238 // This is tricky. We need to add information in the interval about 00239 // the spill code so we have to use our extra load/store slots. 00240 // 00241 // If we have a use we are going to have a load so we start the 00242 // interval from the load slot onwards. Otherwise we start from the 00243 // def slot. 00244 unsigned start = (mop.isUse() ? 00245 getLoadIndex(index) : 00246 getDefIndex(index)); 00247 // If we have a def we are going to have a store right after it so 00248 // we end the interval after the use of the next 00249 // instruction. Otherwise we end after the use of this instruction. 00250 unsigned end = 1 + (mop.isDef() ? 00251 getStoreIndex(index) : 00252 getUseIndex(index)); 00253 00254 // create a new register for this spill 00255 unsigned nReg = mf_->getSSARegMap()->createVirtualRegister(rc); 00256 mi->SetMachineOperandReg(i, nReg); 00257 vrm.grow(); 00258 vrm.assignVirt2StackSlot(nReg, slot); 00259 LiveInterval& nI = getOrCreateInterval(nReg); 00260 assert(nI.empty()); 00261 00262 // the spill weight is now infinity as it 00263 // cannot be spilled again 00264 nI.weight = HUGE_VAL; 00265 LiveRange LR(start, end, nI.getNextValue()); 00266 DEBUG(std::cerr << " +" << LR); 00267 nI.addRange(LR); 00268 added.push_back(&nI); 00269 00270 // update live variables if it is available 00271 if (lv_) 00272 lv_->addVirtualRegisterKilled(nReg, mi); 00273 DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n'); 00274 } 00275 } 00276 } 00277 } 00278 } 00279 00280 return added; 00281 } 00282 00283 void LiveIntervals::printRegName(unsigned reg) const 00284 { 00285 if (MRegisterInfo::isPhysicalRegister(reg)) 00286 std::cerr << mri_->getName(reg); 00287 else 00288 std::cerr << "%reg" << reg; 00289 } 00290 00291 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 00292 MachineBasicBlock::iterator mi, 00293 LiveInterval& interval) 00294 { 00295 DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 00296 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 00297 00298 // Virtual registers may be defined multiple times (due to phi 00299 // elimination and 2-addr elimination). Much of what we do only has to be 00300 // done once for the vreg. We use an empty interval to detect the first 00301 // time we see a vreg. 00302 if (interval.empty()) { 00303 // Get the Idx of the defining instructions. 00304 unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 00305 00306 unsigned ValNum = interval.getNextValue(); 00307 assert(ValNum == 0 && "First value in interval is not 0?"); 00308 ValNum = 0; // Clue in the optimizer. 00309 00310 // Loop over all of the blocks that the vreg is defined in. There are 00311 // two cases we have to handle here. The most common case is a vreg 00312 // whose lifetime is contained within a basic block. In this case there 00313 // will be a single kill, in MBB, which comes after the definition. 00314 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 00315 // FIXME: what about dead vars? 00316 unsigned killIdx; 00317 if (vi.Kills[0] != mi) 00318 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 00319 else 00320 killIdx = defIndex+1; 00321 00322 // If the kill happens after the definition, we have an intra-block 00323 // live range. 00324 if (killIdx > defIndex) { 00325 assert(vi.AliveBlocks.empty() && 00326 "Shouldn't be alive across any blocks!"); 00327 LiveRange LR(defIndex, killIdx, ValNum); 00328 interval.addRange(LR); 00329 DEBUG(std::cerr << " +" << LR << "\n"); 00330 return; 00331 } 00332 } 00333 00334 // The other case we handle is when a virtual register lives to the end 00335 // of the defining block, potentially live across some blocks, then is 00336 // live into some number of blocks, but gets killed. Start by adding a 00337 // range that goes from this definition to the end of the defining block. 00338 LiveRange NewLR(defIndex, 00339 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 00340 ValNum); 00341 DEBUG(std::cerr << " +" << NewLR); 00342 interval.addRange(NewLR); 00343 00344 // Iterate over all of the blocks that the variable is completely 00345 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 00346 // live interval. 00347 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 00348 if (vi.AliveBlocks[i]) { 00349 MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 00350 if (!mbb->empty()) { 00351 LiveRange LR(getInstructionIndex(&mbb->front()), 00352 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 00353 ValNum); 00354 interval.addRange(LR); 00355 DEBUG(std::cerr << " +" << LR); 00356 } 00357 } 00358 } 00359 00360 // Finally, this virtual register is live from the start of any killing 00361 // block to the 'use' slot of the killing instruction. 00362 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 00363 MachineInstr *Kill = vi.Kills[i]; 00364 LiveRange LR(getInstructionIndex(Kill->getParent()->begin()), 00365 getUseIndex(getInstructionIndex(Kill))+1, 00366 ValNum); 00367 interval.addRange(LR); 00368 DEBUG(std::cerr << " +" << LR); 00369 } 00370 00371 } else { 00372 // If this is the second time we see a virtual register definition, it 00373 // must be due to phi elimination or two addr elimination. If this is 00374 // the result of two address elimination, then the vreg is the first 00375 // operand, and is a def-and-use. 00376 if (mi->getOperand(0).isRegister() && 00377 mi->getOperand(0).getReg() == interval.reg && 00378 mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) { 00379 // If this is a two-address definition, then we have already processed 00380 // the live range. The only problem is that we didn't realize there 00381 // are actually two values in the live interval. Because of this we 00382 // need to take the LiveRegion that defines this register and split it 00383 // into two values. 00384 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 00385 unsigned RedefIndex = getDefIndex(getInstructionIndex(mi)); 00386 00387 // Delete the initial value, which should be short and continuous, 00388 // becuase the 2-addr copy must be in the same MBB as the redef. 00389 interval.removeRange(DefIndex, RedefIndex); 00390 00391 LiveRange LR(DefIndex, RedefIndex, interval.getNextValue()); 00392 DEBUG(std::cerr << " replace range with " << LR); 00393 interval.addRange(LR); 00394 00395 // If this redefinition is dead, we need to add a dummy unit live 00396 // range covering the def slot. 00397 for (LiveVariables::killed_iterator KI = lv_->dead_begin(mi), 00398 E = lv_->dead_end(mi); KI != E; ++KI) 00399 if (KI->second == interval.reg) { 00400 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 00401 break; 00402 } 00403 00404 DEBUG(std::cerr << "RESULT: " << interval); 00405 00406 } else { 00407 // Otherwise, this must be because of phi elimination. If this is the 00408 // first redefinition of the vreg that we have seen, go back and change 00409 // the live range in the PHI block to be a different value number. 00410 if (interval.containsOneValue()) { 00411 assert(vi.Kills.size() == 1 && 00412 "PHI elimination vreg should have one kill, the PHI itself!"); 00413 00414 // Remove the old range that we now know has an incorrect number. 00415 MachineInstr *Killer = vi.Kills[0]; 00416 unsigned Start = getInstructionIndex(Killer->getParent()->begin()); 00417 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 00418 DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: " 00419 << interval << "\n"); 00420 interval.removeRange(Start, End); 00421 DEBUG(std::cerr << "RESULT: " << interval); 00422 00423 // Replace the interval with one of a NEW value number. 00424 LiveRange LR(Start, End, interval.getNextValue()); 00425 DEBUG(std::cerr << " replace range with " << LR); 00426 interval.addRange(LR); 00427 DEBUG(std::cerr << "RESULT: " << interval); 00428 } 00429 00430 // In the case of PHI elimination, each variable definition is only 00431 // live until the end of the block. We've already taken care of the 00432 // rest of the live range. 00433 unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 00434 LiveRange LR(defIndex, 00435 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 00436 interval.getNextValue()); 00437 interval.addRange(LR); 00438 DEBUG(std::cerr << " +" << LR); 00439 } 00440 } 00441 00442 DEBUG(std::cerr << '\n'); 00443 } 00444 00445 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 00446 MachineBasicBlock::iterator mi, 00447 LiveInterval& interval) 00448 { 00449 // A physical register cannot be live across basic block, so its 00450 // lifetime must end somewhere in its defining basic block. 00451 DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 00452 typedef LiveVariables::killed_iterator KillIter; 00453 00454 unsigned baseIndex = getInstructionIndex(mi); 00455 unsigned start = getDefIndex(baseIndex); 00456 unsigned end = start; 00457 00458 // If it is not used after definition, it is considered dead at 00459 // the instruction defining it. Hence its interval is: 00460 // [defSlot(def), defSlot(def)+1) 00461 for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 00462 ki != ke; ++ki) { 00463 if (interval.reg == ki->second) { 00464 DEBUG(std::cerr << " dead"); 00465 end = getDefIndex(start) + 1; 00466 goto exit; 00467 } 00468 } 00469 00470 // If it is not dead on definition, it must be killed by a 00471 // subsequent instruction. Hence its interval is: 00472 // [defSlot(def), useSlot(kill)+1) 00473 while (true) { 00474 ++mi; 00475 assert(mi != MBB->end() && "physreg was not killed in defining block!"); 00476 baseIndex += InstrSlots::NUM; 00477 for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 00478 ki != ke; ++ki) { 00479 if (interval.reg == ki->second) { 00480 DEBUG(std::cerr << " killed"); 00481 end = getUseIndex(baseIndex) + 1; 00482 goto exit; 00483 } 00484 } 00485 } 00486 00487 exit: 00488 assert(start < end && "did not find end of interval?"); 00489 LiveRange LR(start, end, interval.getNextValue()); 00490 interval.addRange(LR); 00491 DEBUG(std::cerr << " +" << LR << '\n'); 00492 } 00493 00494 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 00495 MachineBasicBlock::iterator MI, 00496 unsigned reg) { 00497 if (MRegisterInfo::isVirtualRegister(reg)) 00498 handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); 00499 else if (allocatableRegs_[reg]) { 00500 handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg)); 00501 for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) 00502 handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS)); 00503 } 00504 } 00505 00506 /// computeIntervals - computes the live intervals for virtual 00507 /// registers. for some ordering of the machine instructions [1,N] a 00508 /// live interval is an interval [i, j) where 1 <= i <= j < N for 00509 /// which a variable is live 00510 void LiveIntervals::computeIntervals() 00511 { 00512 DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 00513 DEBUG(std::cerr << "********** Function: " 00514 << ((Value*)mf_->getFunction())->getName() << '\n'); 00515 00516 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 00517 I != E; ++I) { 00518 MachineBasicBlock* mbb = I; 00519 DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 00520 00521 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 00522 mi != miEnd; ++mi) { 00523 const TargetInstrDescriptor& tid = 00524 tm_->getInstrInfo()->get(mi->getOpcode()); 00525 DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi); 00526 00527 // handle implicit defs 00528 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 00529 handleRegisterDef(mbb, mi, *id); 00530 00531 // handle explicit defs 00532 for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 00533 MachineOperand& mop = mi->getOperand(i); 00534 // handle register defs - build intervals 00535 if (mop.isRegister() && mop.getReg() && mop.isDef()) 00536 handleRegisterDef(mbb, mi, mop.getReg()); 00537 } 00538 } 00539 } 00540 } 00541 00542 void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { 00543 DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 00544 const TargetInstrInfo &TII = *tm_->getInstrInfo(); 00545 00546 for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); 00547 mi != mie; ++mi) { 00548 DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi); 00549 00550 // we only join virtual registers with allocatable 00551 // physical registers since we do not have liveness information 00552 // on not allocatable physical registers 00553 unsigned regA, regB; 00554 if (TII.isMoveInstr(*mi, regA, regB) && 00555 (MRegisterInfo::isVirtualRegister(regA) || allocatableRegs_[regA]) && 00556 (MRegisterInfo::isVirtualRegister(regB) || allocatableRegs_[regB])) { 00557 00558 // Get representative registers. 00559 regA = rep(regA); 00560 regB = rep(regB); 00561 00562 // If they are already joined we continue. 00563 if (regA == regB) 00564 continue; 00565 00566 // If they are both physical registers, we cannot join them. 00567 if (MRegisterInfo::isPhysicalRegister(regA) && 00568 MRegisterInfo::isPhysicalRegister(regB)) 00569 continue; 00570 00571 // If they are not of the same register class, we cannot join them. 00572 if (differingRegisterClasses(regA, regB)) 00573 continue; 00574 00575 LiveInterval &IntA = getInterval(regA); 00576 LiveInterval &IntB = getInterval(regB); 00577 assert(IntA.reg == regA && IntB.reg == regB && 00578 "Register mapping is horribly broken!"); 00579 00580 DEBUG(std::cerr << "\t\tInspecting " << IntA << " and " << IntB << ": "); 00581 00582 // If two intervals contain a single value and are joined by a copy, it 00583 // does not matter if the intervals overlap, they can always be joined. 00584 bool TriviallyJoinable = 00585 IntA.containsOneValue() && IntB.containsOneValue(); 00586 00587 unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi)); 00588 if ((TriviallyJoinable || IntB.joinable(IntA, MIDefIdx)) && 00589 !overlapsAliases(&IntA, &IntB)) { 00590 IntB.join(IntA, MIDefIdx); 00591 00592 if (!MRegisterInfo::isPhysicalRegister(regA)) { 00593 r2iMap_.erase(regA); 00594 r2rMap_[regA] = regB; 00595 } else { 00596 // Otherwise merge the data structures the other way so we don't lose 00597 // the physreg information. 00598 r2rMap_[regB] = regA; 00599 IntB.reg = regA; 00600 IntA.swap(IntB); 00601 r2iMap_.erase(regB); 00602 } 00603 DEBUG(std::cerr << "Joined. Result = " << IntB << "\n"); 00604 ++numJoins; 00605 } else { 00606 DEBUG(std::cerr << "Interference!\n"); 00607 } 00608 } 00609 } 00610 } 00611 00612 namespace { 00613 // DepthMBBCompare - Comparison predicate that sort first based on the loop 00614 // depth of the basic block (the unsigned), and then on the MBB number. 00615 struct DepthMBBCompare { 00616 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 00617 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 00618 if (LHS.first > RHS.first) return true; // Deeper loops first 00619 return LHS.first == RHS.first && 00620 LHS.second->getNumber() < RHS.second->getNumber(); 00621 } 00622 }; 00623 } 00624 00625 void LiveIntervals::joinIntervals() { 00626 DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 00627 00628 const LoopInfo &LI = getAnalysis<LoopInfo>(); 00629 if (LI.begin() == LI.end()) { 00630 // If there are no loops in the function, join intervals in function order. 00631 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 00632 I != E; ++I) 00633 joinIntervalsInMachineBB(I); 00634 } else { 00635 // Otherwise, join intervals in inner loops before other intervals. 00636 // Unfortunately we can't just iterate over loop hierarchy here because 00637 // there may be more MBB's than BB's. Collect MBB's for sorting. 00638 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 00639 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 00640 I != E; ++I) 00641 MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 00642 00643 // Sort by loop depth. 00644 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 00645 00646 // Finally, join intervals in loop nest order. 00647 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 00648 joinIntervalsInMachineBB(MBBs[i].second); 00649 } 00650 00651 DEBUG(std::cerr << "*** Register mapping ***\n"); 00652 DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) 00653 if (r2rMap_[i]) 00654 std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n"); 00655 } 00656 00657 /// Return true if the two specified registers belong to different register 00658 /// classes. The registers may be either phys or virt regs. 00659 bool LiveIntervals::differingRegisterClasses(unsigned RegA, 00660 unsigned RegB) const { 00661 00662 // Get the register classes for the first reg. 00663 if (MRegisterInfo::isPhysicalRegister(RegA)) { 00664 assert(MRegisterInfo::isVirtualRegister(RegB) && 00665 "Shouldn't consider two physregs!"); 00666 return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); 00667 } 00668 00669 // Compare against the regclass for the second reg. 00670 const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); 00671 if (MRegisterInfo::isVirtualRegister(RegB)) 00672 return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 00673 else 00674 return !RegClass->contains(RegB); 00675 } 00676 00677 bool LiveIntervals::overlapsAliases(const LiveInterval *LHS, 00678 const LiveInterval *RHS) const { 00679 if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) { 00680 if (!MRegisterInfo::isPhysicalRegister(RHS->reg)) 00681 return false; // vreg-vreg merge has no aliases! 00682 std::swap(LHS, RHS); 00683 } 00684 00685 assert(MRegisterInfo::isPhysicalRegister(LHS->reg) && 00686 MRegisterInfo::isVirtualRegister(RHS->reg) && 00687 "first interval must describe a physical register"); 00688 00689 for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS) 00690 if (RHS->overlaps(getInterval(*AS))) 00691 return true; 00692 00693 return false; 00694 } 00695 00696 LiveInterval LiveIntervals::createInterval(unsigned reg) { 00697 float Weight = MRegisterInfo::isPhysicalRegister(reg) ? HUGE_VAL :0.0F; 00698 return LiveInterval(reg, Weight); 00699 }