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 "llvm/CodeGen/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 #include <iostream> 00038 using namespace llvm; 00039 00040 namespace { 00041 RegisterAnalysis<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 00042 00043 Statistic<> numIntervals 00044 ("liveintervals", "Number of original intervals"); 00045 00046 Statistic<> numIntervalsAfter 00047 ("liveintervals", "Number of intervals after coalescing"); 00048 00049 Statistic<> numJoins 00050 ("liveintervals", "Number of interval joins performed"); 00051 00052 Statistic<> numPeep 00053 ("liveintervals", "Number of identity moves eliminated after coalescing"); 00054 00055 Statistic<> numFolded 00056 ("liveintervals", "Number of loads/stores folded into instructions"); 00057 00058 cl::opt<bool> 00059 EnableJoining("join-liveintervals", 00060 cl::desc("Join compatible live intervals"), 00061 cl::init(true)); 00062 }; 00063 00064 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 00065 { 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 tii_ = tm_->getInstrInfo(); 00090 lv_ = &getAnalysis<LiveVariables>(); 00091 allocatableRegs_ = mri_->getAllocatableSet(fn); 00092 r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 00093 00094 // If this function has any live ins, insert a dummy instruction at the 00095 // beginning of the function that we will pretend "defines" the values. This 00096 // is to make the interval analysis simpler by providing a number. 00097 if (fn.livein_begin() != fn.livein_end()) { 00098 unsigned FirstLiveIn = fn.livein_begin()->first; 00099 00100 // Find a reg class that contains this live in. 00101 const TargetRegisterClass *RC = 0; 00102 for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(), 00103 E = mri_->regclass_end(); RCI != E; ++RCI) 00104 if ((*RCI)->contains(FirstLiveIn)) { 00105 RC = *RCI; 00106 break; 00107 } 00108 00109 MachineInstr *OldFirstMI = fn.begin()->begin(); 00110 mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(), 00111 FirstLiveIn, FirstLiveIn, RC); 00112 assert(OldFirstMI != fn.begin()->begin() && 00113 "copyRetToReg didn't insert anything!"); 00114 } 00115 00116 // number MachineInstrs 00117 unsigned miIndex = 0; 00118 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 00119 mbb != mbbEnd; ++mbb) 00120 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 00121 mi != miEnd; ++mi) { 00122 bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 00123 assert(inserted && "multiple MachineInstr -> index mappings"); 00124 i2miMap_.push_back(mi); 00125 miIndex += InstrSlots::NUM; 00126 } 00127 00128 // Note intervals due to live-in values. 00129 if (fn.livein_begin() != fn.livein_end()) { 00130 MachineBasicBlock *Entry = fn.begin(); 00131 for (MachineFunction::livein_iterator I = fn.livein_begin(), 00132 E = fn.livein_end(); I != E; ++I) { 00133 handlePhysicalRegisterDef(Entry, Entry->begin(), 00134 getOrCreateInterval(I->first), 0, 0, true); 00135 for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS) 00136 handlePhysicalRegisterDef(Entry, Entry->begin(), 00137 getOrCreateInterval(*AS), 0, 0, true); 00138 } 00139 } 00140 00141 computeIntervals(); 00142 00143 numIntervals += getNumIntervals(); 00144 00145 DEBUG(std::cerr << "********** INTERVALS **********\n"; 00146 for (iterator I = begin(), E = end(); I != E; ++I) { 00147 I->second.print(std::cerr, mri_); 00148 std::cerr << "\n"; 00149 }); 00150 00151 // join intervals if requested 00152 if (EnableJoining) joinIntervals(); 00153 00154 numIntervalsAfter += getNumIntervals(); 00155 00156 // perform a final pass over the instructions and compute spill 00157 // weights, coalesce virtual registers and remove identity moves 00158 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 00159 00160 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 00161 mbbi != mbbe; ++mbbi) { 00162 MachineBasicBlock* mbb = mbbi; 00163 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 00164 00165 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 00166 mii != mie; ) { 00167 // if the move will be an identity move delete it 00168 unsigned srcReg, dstReg, RegRep; 00169 if (tii_->isMoveInstr(*mii, srcReg, dstReg) && 00170 (RegRep = rep(srcReg)) == rep(dstReg)) { 00171 // remove from def list 00172 LiveInterval &interval = getOrCreateInterval(RegRep); 00173 // remove index -> MachineInstr and 00174 // MachineInstr -> index mappings 00175 Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 00176 if (mi2i != mi2iMap_.end()) { 00177 i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 00178 mi2iMap_.erase(mi2i); 00179 } 00180 mii = mbbi->erase(mii); 00181 ++numPeep; 00182 } 00183 else { 00184 for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 00185 const MachineOperand& mop = mii->getOperand(i); 00186 if (mop.isRegister() && mop.getReg() && 00187 MRegisterInfo::isVirtualRegister(mop.getReg())) { 00188 // replace register with representative register 00189 unsigned reg = rep(mop.getReg()); 00190 mii->SetMachineOperandReg(i, reg); 00191 00192 LiveInterval &RegInt = getInterval(reg); 00193 RegInt.weight += 00194 (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth); 00195 } 00196 } 00197 ++mii; 00198 } 00199 } 00200 } 00201 00202 DEBUG(dump()); 00203 return true; 00204 } 00205 00206 /// print - Implement the dump method. 00207 void LiveIntervals::print(std::ostream &O, const Module* ) const { 00208 O << "********** INTERVALS **********\n"; 00209 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00210 I->second.print(std::cerr, mri_); 00211 std::cerr << "\n"; 00212 } 00213 00214 O << "********** MACHINEINSTRS **********\n"; 00215 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 00216 mbbi != mbbe; ++mbbi) { 00217 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 00218 for (MachineBasicBlock::iterator mii = mbbi->begin(), 00219 mie = mbbi->end(); mii != mie; ++mii) { 00220 O << getInstructionIndex(mii) << '\t' << *mii; 00221 } 00222 } 00223 } 00224 00225 std::vector<LiveInterval*> LiveIntervals:: 00226 addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 00227 // since this is called after the analysis is done we don't know if 00228 // LiveVariables is available 00229 lv_ = getAnalysisToUpdate<LiveVariables>(); 00230 00231 std::vector<LiveInterval*> added; 00232 00233 assert(li.weight != HUGE_VAL && 00234 "attempt to spill already spilled interval!"); 00235 00236 DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 00237 << li << '\n'); 00238 00239 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 00240 00241 for (LiveInterval::Ranges::const_iterator 00242 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 00243 unsigned index = getBaseIndex(i->start); 00244 unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 00245 for (; index != end; index += InstrSlots::NUM) { 00246 // skip deleted instructions 00247 while (index != end && !getInstructionFromIndex(index)) 00248 index += InstrSlots::NUM; 00249 if (index == end) break; 00250 00251 MachineInstr *MI = getInstructionFromIndex(index); 00252 00253 // NewRegLiveIn - This instruction might have multiple uses of the spilled 00254 // register. In this case, for the first use, keep track of the new vreg 00255 // that we reload it into. If we see a second use, reuse this vreg 00256 // instead of creating live ranges for two reloads. 00257 unsigned NewRegLiveIn = 0; 00258 00259 for_operand: 00260 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 00261 MachineOperand& mop = MI->getOperand(i); 00262 if (mop.isRegister() && mop.getReg() == li.reg) { 00263 if (NewRegLiveIn && mop.isUse()) { 00264 // We already emitted a reload of this value, reuse it for 00265 // subsequent operands. 00266 MI->SetMachineOperandReg(i, NewRegLiveIn); 00267 DEBUG(std::cerr << "\t\t\t\treused reload into reg" << NewRegLiveIn 00268 << " for operand #" << i << '\n'); 00269 } else if (MachineInstr* fmi = mri_->foldMemoryOperand(MI, i, slot)) { 00270 // Attempt to fold the memory reference into the instruction. If we 00271 // can do this, we don't need to insert spill code. 00272 if (lv_) 00273 lv_->instructionChanged(MI, fmi); 00274 vrm.virtFolded(li.reg, MI, i, fmi); 00275 mi2iMap_.erase(MI); 00276 i2miMap_[index/InstrSlots::NUM] = fmi; 00277 mi2iMap_[fmi] = index; 00278 MachineBasicBlock &MBB = *MI->getParent(); 00279 MI = MBB.insert(MBB.erase(MI), fmi); 00280 ++numFolded; 00281 00282 // Folding the load/store can completely change the instruction in 00283 // unpredictable ways, rescan it from the beginning. 00284 goto for_operand; 00285 } else { 00286 // This is tricky. We need to add information in the interval about 00287 // the spill code so we have to use our extra load/store slots. 00288 // 00289 // If we have a use we are going to have a load so we start the 00290 // interval from the load slot onwards. Otherwise we start from the 00291 // def slot. 00292 unsigned start = (mop.isUse() ? 00293 getLoadIndex(index) : 00294 getDefIndex(index)); 00295 // If we have a def we are going to have a store right after it so 00296 // we end the interval after the use of the next 00297 // instruction. Otherwise we end after the use of this instruction. 00298 unsigned end = 1 + (mop.isDef() ? 00299 getStoreIndex(index) : 00300 getUseIndex(index)); 00301 00302 // create a new register for this spill 00303 NewRegLiveIn = mf_->getSSARegMap()->createVirtualRegister(rc); 00304 MI->SetMachineOperandReg(i, NewRegLiveIn); 00305 vrm.grow(); 00306 vrm.assignVirt2StackSlot(NewRegLiveIn, slot); 00307 LiveInterval& nI = getOrCreateInterval(NewRegLiveIn); 00308 assert(nI.empty()); 00309 00310 // the spill weight is now infinity as it 00311 // cannot be spilled again 00312 nI.weight = float(HUGE_VAL); 00313 LiveRange LR(start, end, nI.getNextValue()); 00314 DEBUG(std::cerr << " +" << LR); 00315 nI.addRange(LR); 00316 added.push_back(&nI); 00317 00318 // update live variables if it is available 00319 if (lv_) 00320 lv_->addVirtualRegisterKilled(NewRegLiveIn, MI); 00321 00322 // If this is a live in, reuse it for subsequent live-ins. If it's 00323 // a def, we can't do this. 00324 if (!mop.isUse()) NewRegLiveIn = 0; 00325 00326 DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n'); 00327 } 00328 } 00329 } 00330 } 00331 } 00332 00333 return added; 00334 } 00335 00336 void LiveIntervals::printRegName(unsigned reg) const 00337 { 00338 if (MRegisterInfo::isPhysicalRegister(reg)) 00339 std::cerr << mri_->getName(reg); 00340 else 00341 std::cerr << "%reg" << reg; 00342 } 00343 00344 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 00345 MachineBasicBlock::iterator mi, 00346 LiveInterval& interval) 00347 { 00348 DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 00349 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 00350 00351 // Virtual registers may be defined multiple times (due to phi 00352 // elimination and 2-addr elimination). Much of what we do only has to be 00353 // done once for the vreg. We use an empty interval to detect the first 00354 // time we see a vreg. 00355 if (interval.empty()) { 00356 // Get the Idx of the defining instructions. 00357 unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 00358 00359 unsigned ValNum = interval.getNextValue(); 00360 assert(ValNum == 0 && "First value in interval is not 0?"); 00361 ValNum = 0; // Clue in the optimizer. 00362 00363 // Loop over all of the blocks that the vreg is defined in. There are 00364 // two cases we have to handle here. The most common case is a vreg 00365 // whose lifetime is contained within a basic block. In this case there 00366 // will be a single kill, in MBB, which comes after the definition. 00367 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 00368 // FIXME: what about dead vars? 00369 unsigned killIdx; 00370 if (vi.Kills[0] != mi) 00371 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 00372 else 00373 killIdx = defIndex+1; 00374 00375 // If the kill happens after the definition, we have an intra-block 00376 // live range. 00377 if (killIdx > defIndex) { 00378 assert(vi.AliveBlocks.empty() && 00379 "Shouldn't be alive across any blocks!"); 00380 LiveRange LR(defIndex, killIdx, ValNum); 00381 interval.addRange(LR); 00382 DEBUG(std::cerr << " +" << LR << "\n"); 00383 return; 00384 } 00385 } 00386 00387 // The other case we handle is when a virtual register lives to the end 00388 // of the defining block, potentially live across some blocks, then is 00389 // live into some number of blocks, but gets killed. Start by adding a 00390 // range that goes from this definition to the end of the defining block. 00391 LiveRange NewLR(defIndex, 00392 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 00393 ValNum); 00394 DEBUG(std::cerr << " +" << NewLR); 00395 interval.addRange(NewLR); 00396 00397 // Iterate over all of the blocks that the variable is completely 00398 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 00399 // live interval. 00400 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 00401 if (vi.AliveBlocks[i]) { 00402 MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 00403 if (!mbb->empty()) { 00404 LiveRange LR(getInstructionIndex(&mbb->front()), 00405 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 00406 ValNum); 00407 interval.addRange(LR); 00408 DEBUG(std::cerr << " +" << LR); 00409 } 00410 } 00411 } 00412 00413 // Finally, this virtual register is live from the start of any killing 00414 // block to the 'use' slot of the killing instruction. 00415 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 00416 MachineInstr *Kill = vi.Kills[i]; 00417 LiveRange LR(getInstructionIndex(Kill->getParent()->begin()), 00418 getUseIndex(getInstructionIndex(Kill))+1, 00419 ValNum); 00420 interval.addRange(LR); 00421 DEBUG(std::cerr << " +" << LR); 00422 } 00423 00424 } else { 00425 // If this is the second time we see a virtual register definition, it 00426 // must be due to phi elimination or two addr elimination. If this is 00427 // the result of two address elimination, then the vreg is the first 00428 // operand, and is a def-and-use. 00429 if (mi->getOperand(0).isRegister() && 00430 mi->getOperand(0).getReg() == interval.reg && 00431 mi->getOperand(0).isDef() && mi->getOperand(0).isUse()) { 00432 // If this is a two-address definition, then we have already processed 00433 // the live range. The only problem is that we didn't realize there 00434 // are actually two values in the live interval. Because of this we 00435 // need to take the LiveRegion that defines this register and split it 00436 // into two values. 00437 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 00438 unsigned RedefIndex = getDefIndex(getInstructionIndex(mi)); 00439 00440 // Delete the initial value, which should be short and continuous, 00441 // becuase the 2-addr copy must be in the same MBB as the redef. 00442 interval.removeRange(DefIndex, RedefIndex); 00443 00444 LiveRange LR(DefIndex, RedefIndex, interval.getNextValue()); 00445 DEBUG(std::cerr << " replace range with " << LR); 00446 interval.addRange(LR); 00447 00448 // If this redefinition is dead, we need to add a dummy unit live 00449 // range covering the def slot. 00450 if (lv_->RegisterDefIsDead(mi, interval.reg)) 00451 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 00452 00453 DEBUG(std::cerr << "RESULT: " << interval); 00454 00455 } else { 00456 // Otherwise, this must be because of phi elimination. If this is the 00457 // first redefinition of the vreg that we have seen, go back and change 00458 // the live range in the PHI block to be a different value number. 00459 if (interval.containsOneValue()) { 00460 assert(vi.Kills.size() == 1 && 00461 "PHI elimination vreg should have one kill, the PHI itself!"); 00462 00463 // Remove the old range that we now know has an incorrect number. 00464 MachineInstr *Killer = vi.Kills[0]; 00465 unsigned Start = getInstructionIndex(Killer->getParent()->begin()); 00466 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 00467 DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: " 00468 << interval << "\n"); 00469 interval.removeRange(Start, End); 00470 DEBUG(std::cerr << "RESULT: " << interval); 00471 00472 // Replace the interval with one of a NEW value number. 00473 LiveRange LR(Start, End, interval.getNextValue()); 00474 DEBUG(std::cerr << " replace range with " << LR); 00475 interval.addRange(LR); 00476 DEBUG(std::cerr << "RESULT: " << interval); 00477 } 00478 00479 // In the case of PHI elimination, each variable definition is only 00480 // live until the end of the block. We've already taken care of the 00481 // rest of the live range. 00482 unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 00483 LiveRange LR(defIndex, 00484 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 00485 interval.getNextValue()); 00486 interval.addRange(LR); 00487 DEBUG(std::cerr << " +" << LR); 00488 } 00489 } 00490 00491 DEBUG(std::cerr << '\n'); 00492 } 00493 00494 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 00495 MachineBasicBlock::iterator mi, 00496 LiveInterval& interval, 00497 unsigned SrcReg, unsigned DestReg, 00498 bool isLiveIn) 00499 { 00500 // A physical register cannot be live across basic block, so its 00501 // lifetime must end somewhere in its defining basic block. 00502 DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 00503 typedef LiveVariables::killed_iterator KillIter; 00504 00505 unsigned baseIndex = getInstructionIndex(mi); 00506 unsigned start = getDefIndex(baseIndex); 00507 unsigned end = start; 00508 00509 // If it is not used after definition, it is considered dead at 00510 // the instruction defining it. Hence its interval is: 00511 // [defSlot(def), defSlot(def)+1) 00512 if (lv_->RegisterDefIsDead(mi, interval.reg)) { 00513 DEBUG(std::cerr << " dead"); 00514 end = getDefIndex(start) + 1; 00515 goto exit; 00516 } 00517 00518 // If it is not dead on definition, it must be killed by a 00519 // subsequent instruction. Hence its interval is: 00520 // [defSlot(def), useSlot(kill)+1) 00521 while (++mi != MBB->end()) { 00522 baseIndex += InstrSlots::NUM; 00523 if (lv_->KillsRegister(mi, interval.reg)) { 00524 DEBUG(std::cerr << " killed"); 00525 end = getUseIndex(baseIndex) + 1; 00526 goto exit; 00527 } 00528 } 00529 00530 // The only case we should have a dead physreg here without a killing or 00531 // instruction where we know it's dead is if it is live-in to the function 00532 // and never used. 00533 assert(isLiveIn && "physreg was not killed in defining block!"); 00534 end = getDefIndex(start) + 1; // It's dead. 00535 00536 exit: 00537 assert(start < end && "did not find end of interval?"); 00538 00539 // Finally, if this is defining a new range for the physical register, and if 00540 // that physreg is just a copy from a vreg, and if THAT vreg was a copy from 00541 // the physreg, then the new fragment has the same value as the one copied 00542 // into the vreg. 00543 if (interval.reg == DestReg && !interval.empty() && 00544 MRegisterInfo::isVirtualRegister(SrcReg)) { 00545 00546 // Get the live interval for the vreg, see if it is defined by a copy. 00547 LiveInterval &SrcInterval = getOrCreateInterval(SrcReg); 00548 00549 if (SrcInterval.containsOneValue()) { 00550 assert(!SrcInterval.empty() && "Can't contain a value and be empty!"); 00551 00552 // Get the first index of the first range. Though the interval may have 00553 // multiple liveranges in it, we only check the first. 00554 unsigned StartIdx = SrcInterval.begin()->start; 00555 MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx); 00556 00557 // Check to see if the vreg was defined by a copy instruction, and that 00558 // the source was this physreg. 00559 unsigned VRegSrcSrc, VRegSrcDest; 00560 if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) && 00561 SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) { 00562 // Okay, now we know that the vreg was defined by a copy from this 00563 // physreg. Find the value number being copied and use it as the value 00564 // for this range. 00565 const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1); 00566 if (DefRange) { 00567 LiveRange LR(start, end, DefRange->ValId); 00568 interval.addRange(LR); 00569 DEBUG(std::cerr << " +" << LR << '\n'); 00570 return; 00571 } 00572 } 00573 } 00574 } 00575 00576 00577 LiveRange LR(start, end, interval.getNextValue()); 00578 interval.addRange(LR); 00579 DEBUG(std::cerr << " +" << LR << '\n'); 00580 } 00581 00582 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 00583 MachineBasicBlock::iterator MI, 00584 unsigned reg) { 00585 if (MRegisterInfo::isVirtualRegister(reg)) 00586 handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg)); 00587 else if (allocatableRegs_[reg]) { 00588 unsigned SrcReg = 0, DestReg = 0; 00589 if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) 00590 SrcReg = DestReg = 0; 00591 00592 handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg), 00593 SrcReg, DestReg); 00594 for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS) 00595 handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS), 00596 SrcReg, DestReg); 00597 } 00598 } 00599 00600 /// computeIntervals - computes the live intervals for virtual 00601 /// registers. for some ordering of the machine instructions [1,N] a 00602 /// live interval is an interval [i, j) where 1 <= i <= j < N for 00603 /// which a variable is live 00604 void LiveIntervals::computeIntervals() 00605 { 00606 DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 00607 DEBUG(std::cerr << "********** Function: " 00608 << ((Value*)mf_->getFunction())->getName() << '\n'); 00609 bool IgnoreFirstInstr = mf_->livein_begin() != mf_->livein_end(); 00610 00611 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 00612 I != E; ++I) { 00613 MachineBasicBlock* mbb = I; 00614 DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 00615 00616 MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 00617 if (IgnoreFirstInstr) { ++mi; IgnoreFirstInstr = false; } 00618 for (; mi != miEnd; ++mi) { 00619 const TargetInstrDescriptor& tid = 00620 tm_->getInstrInfo()->get(mi->getOpcode()); 00621 DEBUG(std::cerr << getInstructionIndex(mi) << "\t" << *mi); 00622 00623 // handle implicit defs 00624 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 00625 handleRegisterDef(mbb, mi, *id); 00626 00627 // handle explicit defs 00628 for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 00629 MachineOperand& mop = mi->getOperand(i); 00630 // handle register defs - build intervals 00631 if (mop.isRegister() && mop.getReg() && mop.isDef()) 00632 handleRegisterDef(mbb, mi, mop.getReg()); 00633 } 00634 } 00635 } 00636 } 00637 00638 /// IntA is defined as a copy from IntB and we know it only has one value 00639 /// number. If all of the places that IntA and IntB overlap are defined by 00640 /// copies from IntA to IntB, we know that these two ranges can really be 00641 /// merged if we adjust the value numbers. If it is safe, adjust the value 00642 /// numbers and return true, allowing coalescing to occur. 00643 bool LiveIntervals:: 00644 AdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA, 00645 LiveInterval &IntB, 00646 unsigned CopyIdx) { 00647 std::vector<LiveRange*> Ranges; 00648 IntA.getOverlapingRanges(IntB, CopyIdx, Ranges); 00649 00650 assert(!Ranges.empty() && "Why didn't we do a simple join of this?"); 00651 00652 unsigned IntBRep = rep(IntB.reg); 00653 00654 // Check to see if all of the overlaps (entries in Ranges) are defined by a 00655 // copy from IntA. If not, exit. 00656 for (unsigned i = 0, e = Ranges.size(); i != e; ++i) { 00657 unsigned Idx = Ranges[i]->start; 00658 MachineInstr *MI = getInstructionFromIndex(Idx); 00659 unsigned SrcReg, DestReg; 00660 if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) return false; 00661 00662 // If this copy isn't actually defining this range, it must be a live 00663 // range spanning basic blocks or something. 00664 if (rep(DestReg) != rep(IntA.reg)) return false; 00665 00666 // Check to see if this is coming from IntB. If not, bail out. 00667 if (rep(SrcReg) != IntBRep) return false; 00668 } 00669 00670 // Okay, we can change this one. Get the IntB value number that IntA is 00671 // copied from. 00672 unsigned ActualValNo = IntA.getLiveRangeContaining(CopyIdx-1)->ValId; 00673 00674 // Change all of the value numbers to the same as what we IntA is copied from. 00675 for (unsigned i = 0, e = Ranges.size(); i != e; ++i) 00676 Ranges[i]->ValId = ActualValNo; 00677 00678 return true; 00679 } 00680 00681 void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { 00682 DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 00683 00684 for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); 00685 mi != mie; ++mi) { 00686 DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi); 00687 00688 // we only join virtual registers with allocatable 00689 // physical registers since we do not have liveness information 00690 // on not allocatable physical registers 00691 unsigned SrcReg, DestReg; 00692 if (tii_->isMoveInstr(*mi, SrcReg, DestReg) && 00693 (MRegisterInfo::isVirtualRegister(SrcReg) || allocatableRegs_[SrcReg])&& 00694 (MRegisterInfo::isVirtualRegister(DestReg)||allocatableRegs_[DestReg])){ 00695 00696 // Get representative registers. 00697 SrcReg = rep(SrcReg); 00698 DestReg = rep(DestReg); 00699 00700 // If they are already joined we continue. 00701 if (SrcReg == DestReg) 00702 continue; 00703 00704 // If they are both physical registers, we cannot join them. 00705 if (MRegisterInfo::isPhysicalRegister(SrcReg) && 00706 MRegisterInfo::isPhysicalRegister(DestReg)) 00707 continue; 00708 00709 // If they are not of the same register class, we cannot join them. 00710 if (differingRegisterClasses(SrcReg, DestReg)) 00711 continue; 00712 00713 LiveInterval &SrcInt = getInterval(SrcReg); 00714 LiveInterval &DestInt = getInterval(DestReg); 00715 assert(SrcInt.reg == SrcReg && DestInt.reg == DestReg && 00716 "Register mapping is horribly broken!"); 00717 00718 DEBUG(std::cerr << "\t\tInspecting " << SrcInt << " and " << DestInt 00719 << ": "); 00720 00721 // If two intervals contain a single value and are joined by a copy, it 00722 // does not matter if the intervals overlap, they can always be joined. 00723 bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue(); 00724 00725 unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi)); 00726 00727 // If the intervals think that this is joinable, do so now. 00728 if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx)) 00729 Joinable = true; 00730 00731 // If DestInt is actually a copy from SrcInt (which we know) that is used 00732 // to define another value of SrcInt, we can change the other range of 00733 // SrcInt to be the value of the range that defines DestInt, allowing a 00734 // coalesce. 00735 if (!Joinable && DestInt.containsOneValue() && 00736 AdjustIfAllOverlappingRangesAreCopiesFrom(SrcInt, DestInt, MIDefIdx)) 00737 Joinable = true; 00738 00739 if (!Joinable || overlapsAliases(&SrcInt, &DestInt)) { 00740 DEBUG(std::cerr << "Interference!\n"); 00741 } else { 00742 DestInt.join(SrcInt, MIDefIdx); 00743 DEBUG(std::cerr << "Joined. Result = " << DestInt << "\n"); 00744 00745 if (!MRegisterInfo::isPhysicalRegister(SrcReg)) { 00746 r2iMap_.erase(SrcReg); 00747 r2rMap_[SrcReg] = DestReg; 00748 } else { 00749 // Otherwise merge the data structures the other way so we don't lose 00750 // the physreg information. 00751 r2rMap_[DestReg] = SrcReg; 00752 DestInt.reg = SrcReg; 00753 SrcInt.swap(DestInt); 00754 r2iMap_.erase(DestReg); 00755 } 00756 ++numJoins; 00757 } 00758 } 00759 } 00760 } 00761 00762 namespace { 00763 // DepthMBBCompare - Comparison predicate that sort first based on the loop 00764 // depth of the basic block (the unsigned), and then on the MBB number. 00765 struct DepthMBBCompare { 00766 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 00767 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 00768 if (LHS.first > RHS.first) return true; // Deeper loops first 00769 return LHS.first == RHS.first && 00770 LHS.second->getNumber() < RHS.second->getNumber(); 00771 } 00772 }; 00773 } 00774 00775 void LiveIntervals::joinIntervals() { 00776 DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 00777 00778 const LoopInfo &LI = getAnalysis<LoopInfo>(); 00779 if (LI.begin() == LI.end()) { 00780 // If there are no loops in the function, join intervals in function order. 00781 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 00782 I != E; ++I) 00783 joinIntervalsInMachineBB(I); 00784 } else { 00785 // Otherwise, join intervals in inner loops before other intervals. 00786 // Unfortunately we can't just iterate over loop hierarchy here because 00787 // there may be more MBB's than BB's. Collect MBB's for sorting. 00788 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 00789 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 00790 I != E; ++I) 00791 MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 00792 00793 // Sort by loop depth. 00794 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 00795 00796 // Finally, join intervals in loop nest order. 00797 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 00798 joinIntervalsInMachineBB(MBBs[i].second); 00799 } 00800 00801 DEBUG(std::cerr << "*** Register mapping ***\n"); 00802 DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i) 00803 if (r2rMap_[i]) 00804 std::cerr << " reg " << i << " -> reg " << r2rMap_[i] << "\n"); 00805 } 00806 00807 /// Return true if the two specified registers belong to different register 00808 /// classes. The registers may be either phys or virt regs. 00809 bool LiveIntervals::differingRegisterClasses(unsigned RegA, 00810 unsigned RegB) const { 00811 00812 // Get the register classes for the first reg. 00813 if (MRegisterInfo::isPhysicalRegister(RegA)) { 00814 assert(MRegisterInfo::isVirtualRegister(RegB) && 00815 "Shouldn't consider two physregs!"); 00816 return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); 00817 } 00818 00819 // Compare against the regclass for the second reg. 00820 const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); 00821 if (MRegisterInfo::isVirtualRegister(RegB)) 00822 return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 00823 else 00824 return !RegClass->contains(RegB); 00825 } 00826 00827 bool LiveIntervals::overlapsAliases(const LiveInterval *LHS, 00828 const LiveInterval *RHS) const { 00829 if (!MRegisterInfo::isPhysicalRegister(LHS->reg)) { 00830 if (!MRegisterInfo::isPhysicalRegister(RHS->reg)) 00831 return false; // vreg-vreg merge has no aliases! 00832 std::swap(LHS, RHS); 00833 } 00834 00835 assert(MRegisterInfo::isPhysicalRegister(LHS->reg) && 00836 MRegisterInfo::isVirtualRegister(RHS->reg) && 00837 "first interval must describe a physical register"); 00838 00839 for (const unsigned *AS = mri_->getAliasSet(LHS->reg); *AS; ++AS) 00840 if (RHS->overlaps(getInterval(*AS))) 00841 return true; 00842 00843 return false; 00844 } 00845 00846 LiveInterval LiveIntervals::createInterval(unsigned reg) { 00847 float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 00848 (float)HUGE_VAL :0.0F; 00849 return LiveInterval(reg, Weight); 00850 }