LLVM API Documentation
00001 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/AliasAnalysis.h" 00023 #include "llvm/CodeGen/LiveVariables.h" 00024 #include "llvm/CodeGen/MachineFrameInfo.h" 00025 #include "llvm/CodeGen/MachineInstr.h" 00026 #include "llvm/CodeGen/MachineInstrBuilder.h" 00027 #include "llvm/CodeGen/MachineLoopInfo.h" 00028 #include "llvm/CodeGen/MachineRegisterInfo.h" 00029 #include "llvm/CodeGen/Passes.h" 00030 #include "llvm/CodeGen/PseudoSourceValue.h" 00031 #include "llvm/Target/TargetRegisterInfo.h" 00032 #include "llvm/Target/TargetInstrInfo.h" 00033 #include "llvm/Target/TargetMachine.h" 00034 #include "llvm/Target/TargetOptions.h" 00035 #include "llvm/Support/CommandLine.h" 00036 #include "llvm/Support/Debug.h" 00037 #include "llvm/Support/ErrorHandling.h" 00038 #include "llvm/Support/raw_ostream.h" 00039 #include "llvm/ADT/DepthFirstIterator.h" 00040 #include "llvm/ADT/SmallSet.h" 00041 #include "llvm/ADT/Statistic.h" 00042 #include "llvm/ADT/STLExtras.h" 00043 #include <algorithm> 00044 #include <limits> 00045 #include <cmath> 00046 using namespace llvm; 00047 00048 // Hidden options for help debugging. 00049 static cl::opt<bool> DisableReMat("disable-rematerialization", 00050 cl::init(false), cl::Hidden); 00051 00052 static cl::opt<bool> SplitAtBB("split-intervals-at-bb", 00053 cl::init(true), cl::Hidden); 00054 static cl::opt<int> SplitLimit("split-limit", 00055 cl::init(-1), cl::Hidden); 00056 00057 static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden); 00058 00059 static cl::opt<bool> EnableFastSpilling("fast-spill", 00060 cl::init(false), cl::Hidden); 00061 00062 STATISTIC(numIntervals, "Number of original intervals"); 00063 STATISTIC(numFolds , "Number of loads/stores folded into instructions"); 00064 STATISTIC(numSplits , "Number of intervals split"); 00065 00066 char LiveIntervals::ID = 0; 00067 static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 00068 00069 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 00070 AU.setPreservesCFG(); 00071 AU.addRequired<AliasAnalysis>(); 00072 AU.addPreserved<AliasAnalysis>(); 00073 AU.addPreserved<LiveVariables>(); 00074 AU.addRequired<LiveVariables>(); 00075 AU.addPreservedID(MachineLoopInfoID); 00076 AU.addPreservedID(MachineDominatorsID); 00077 00078 if (!StrongPHIElim) { 00079 AU.addPreservedID(PHIEliminationID); 00080 AU.addRequiredID(PHIEliminationID); 00081 } 00082 00083 AU.addRequiredID(TwoAddressInstructionPassID); 00084 MachineFunctionPass::getAnalysisUsage(AU); 00085 } 00086 00087 void LiveIntervals::releaseMemory() { 00088 // Free the live intervals themselves. 00089 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 00090 E = r2iMap_.end(); I != E; ++I) 00091 delete I->second; 00092 00093 MBB2IdxMap.clear(); 00094 Idx2MBBMap.clear(); 00095 mi2iMap_.clear(); 00096 i2miMap_.clear(); 00097 r2iMap_.clear(); 00098 terminatorGaps.clear(); 00099 00100 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 00101 VNInfoAllocator.Reset(); 00102 while (!ClonedMIs.empty()) { 00103 MachineInstr *MI = ClonedMIs.back(); 00104 ClonedMIs.pop_back(); 00105 mf_->DeleteMachineInstr(MI); 00106 } 00107 } 00108 00109 static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg, 00110 const TargetInstrInfo *tii_) { 00111 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00112 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 00113 Reg == SrcReg) 00114 return true; 00115 00116 if ((MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 00117 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) && 00118 MI->getOperand(2).getReg() == Reg) 00119 return true; 00120 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG && 00121 MI->getOperand(1).getReg() == Reg) 00122 return true; 00123 return false; 00124 } 00125 00126 /// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure 00127 /// there is one implicit_def for each use. Add isUndef marker to 00128 /// implicit_def defs and their uses. 00129 void LiveIntervals::processImplicitDefs() { 00130 SmallSet<unsigned, 8> ImpDefRegs; 00131 SmallVector<MachineInstr*, 8> ImpDefMIs; 00132 MachineBasicBlock *Entry = mf_->begin(); 00133 SmallPtrSet<MachineBasicBlock*,16> Visited; 00134 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 00135 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 00136 DFI != E; ++DFI) { 00137 MachineBasicBlock *MBB = *DFI; 00138 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 00139 I != E; ) { 00140 MachineInstr *MI = &*I; 00141 ++I; 00142 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 00143 unsigned Reg = MI->getOperand(0).getReg(); 00144 ImpDefRegs.insert(Reg); 00145 ImpDefMIs.push_back(MI); 00146 continue; 00147 } 00148 00149 bool ChangedToImpDef = false; 00150 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00151 MachineOperand& MO = MI->getOperand(i); 00152 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) 00153 continue; 00154 unsigned Reg = MO.getReg(); 00155 if (!Reg) 00156 continue; 00157 if (!ImpDefRegs.count(Reg)) 00158 continue; 00159 // Use is a copy, just turn it into an implicit_def. 00160 if (CanTurnIntoImplicitDef(MI, Reg, tii_)) { 00161 bool isKill = MO.isKill(); 00162 MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 00163 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 00164 MI->RemoveOperand(j); 00165 if (isKill) 00166 ImpDefRegs.erase(Reg); 00167 ChangedToImpDef = true; 00168 break; 00169 } 00170 00171 MO.setIsUndef(); 00172 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { 00173 // Make sure other uses of 00174 for (unsigned j = i+1; j != e; ++j) { 00175 MachineOperand &MOJ = MI->getOperand(j); 00176 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) 00177 MOJ.setIsUndef(); 00178 } 00179 ImpDefRegs.erase(Reg); 00180 } 00181 } 00182 00183 if (ChangedToImpDef) { 00184 // Backtrack to process this new implicit_def. 00185 --I; 00186 } else { 00187 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 00188 MachineOperand& MO = MI->getOperand(i); 00189 if (!MO.isReg() || !MO.isDef()) 00190 continue; 00191 ImpDefRegs.erase(MO.getReg()); 00192 } 00193 } 00194 } 00195 00196 // Any outstanding liveout implicit_def's? 00197 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { 00198 MachineInstr *MI = ImpDefMIs[i]; 00199 unsigned Reg = MI->getOperand(0).getReg(); 00200 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 00201 !ImpDefRegs.count(Reg)) { 00202 // Delete all "local" implicit_def's. That include those which define 00203 // physical registers since they cannot be liveout. 00204 MI->eraseFromParent(); 00205 continue; 00206 } 00207 00208 // If there are multiple defs of the same register and at least one 00209 // is not an implicit_def, do not insert implicit_def's before the 00210 // uses. 00211 bool Skip = false; 00212 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), 00213 DE = mri_->def_end(); DI != DE; ++DI) { 00214 if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { 00215 Skip = true; 00216 break; 00217 } 00218 } 00219 if (Skip) 00220 continue; 00221 00222 // The only implicit_def which we want to keep are those that are live 00223 // out of its block. 00224 MI->eraseFromParent(); 00225 00226 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 00227 UE = mri_->use_end(); UI != UE; ) { 00228 MachineOperand &RMO = UI.getOperand(); 00229 MachineInstr *RMI = &*UI; 00230 ++UI; 00231 MachineBasicBlock *RMBB = RMI->getParent(); 00232 if (RMBB == MBB) 00233 continue; 00234 00235 // Turn a copy use into an implicit_def. 00236 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00237 if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 00238 Reg == SrcReg) { 00239 RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 00240 for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j) 00241 RMI->RemoveOperand(j); 00242 continue; 00243 } 00244 00245 const TargetRegisterClass* RC = mri_->getRegClass(Reg); 00246 unsigned NewVReg = mri_->createVirtualRegister(RC); 00247 RMO.setReg(NewVReg); 00248 RMO.setIsUndef(); 00249 RMO.setIsKill(); 00250 } 00251 } 00252 ImpDefRegs.clear(); 00253 ImpDefMIs.clear(); 00254 } 00255 } 00256 00257 void LiveIntervals::computeNumbering() { 00258 Index2MiMap OldI2MI = i2miMap_; 00259 std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; 00260 00261 Idx2MBBMap.clear(); 00262 MBB2IdxMap.clear(); 00263 mi2iMap_.clear(); 00264 i2miMap_.clear(); 00265 terminatorGaps.clear(); 00266 00267 FunctionSize = 0; 00268 00269 // Number MachineInstrs and MachineBasicBlocks. 00270 // Initialize MBB indexes to a sentinal. 00271 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 00272 00273 unsigned MIIndex = 0; 00274 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 00275 MBB != E; ++MBB) { 00276 unsigned StartIdx = MIIndex; 00277 00278 // Insert an empty slot at the beginning of each block. 00279 MIIndex += InstrSlots::NUM; 00280 i2miMap_.push_back(0); 00281 00282 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 00283 I != E; ++I) { 00284 00285 if (I == MBB->getFirstTerminator()) { 00286 // Leave a gap for before terminators, this is where we will point 00287 // PHI kills. 00288 bool inserted = 00289 terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second; 00290 assert(inserted && 00291 "Multiple 'first' terminators encountered during numbering."); 00292 inserted = inserted; // Avoid compiler warning if assertions turned off. 00293 i2miMap_.push_back(0); 00294 00295 MIIndex += InstrSlots::NUM; 00296 } 00297 00298 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 00299 assert(inserted && "multiple MachineInstr -> index mappings"); 00300 inserted = true; 00301 i2miMap_.push_back(I); 00302 MIIndex += InstrSlots::NUM; 00303 FunctionSize++; 00304 00305 // Insert max(1, numdefs) empty slots after every instruction. 00306 unsigned Slots = I->getDesc().getNumDefs(); 00307 if (Slots == 0) 00308 Slots = 1; 00309 MIIndex += InstrSlots::NUM * Slots; 00310 while (Slots--) 00311 i2miMap_.push_back(0); 00312 } 00313 00314 if (MBB->getFirstTerminator() == MBB->end()) { 00315 // Leave a gap for before terminators, this is where we will point 00316 // PHI kills. 00317 bool inserted = 00318 terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second; 00319 assert(inserted && 00320 "Multiple 'first' terminators encountered during numbering."); 00321 inserted = inserted; // Avoid compiler warning if assertions turned off. 00322 i2miMap_.push_back(0); 00323 00324 MIIndex += InstrSlots::NUM; 00325 } 00326 00327 // Set the MBB2IdxMap entry for this MBB. 00328 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 00329 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 00330 } 00331 00332 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 00333 00334 if (!OldI2MI.empty()) 00335 for (iterator OI = begin(), OE = end(); OI != OE; ++OI) { 00336 for (LiveInterval::iterator LI = OI->second->begin(), 00337 LE = OI->second->end(); LI != LE; ++LI) { 00338 00339 // Remap the start index of the live range to the corresponding new 00340 // number, or our best guess at what it _should_ correspond to if the 00341 // original instruction has been erased. This is either the following 00342 // instruction or its predecessor. 00343 unsigned index = LI->start / InstrSlots::NUM; 00344 unsigned offset = LI->start % InstrSlots::NUM; 00345 if (offset == InstrSlots::LOAD) { 00346 std::vector<IdxMBBPair>::const_iterator I = 00347 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); 00348 // Take the pair containing the index 00349 std::vector<IdxMBBPair>::const_iterator J = 00350 (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 00351 00352 LI->start = getMBBStartIdx(J->second); 00353 } else { 00354 LI->start = mi2iMap_[OldI2MI[index]] + offset; 00355 } 00356 00357 // Remap the ending index in the same way that we remapped the start, 00358 // except for the final step where we always map to the immediately 00359 // following instruction. 00360 index = (LI->end - 1) / InstrSlots::NUM; 00361 offset = LI->end % InstrSlots::NUM; 00362 if (offset == InstrSlots::LOAD) { 00363 // VReg dies at end of block. 00364 std::vector<IdxMBBPair>::const_iterator I = 00365 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); 00366 --I; 00367 00368 LI->end = getMBBEndIdx(I->second) + 1; 00369 } else { 00370 unsigned idx = index; 00371 while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 00372 00373 if (index != OldI2MI.size()) 00374 LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); 00375 else 00376 LI->end = InstrSlots::NUM * i2miMap_.size(); 00377 } 00378 } 00379 00380 for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), 00381 VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 00382 VNInfo* vni = *VNI; 00383 00384 // Remap the VNInfo def index, which works the same as the 00385 // start indices above. VN's with special sentinel defs 00386 // don't need to be remapped. 00387 if (vni->isDefAccurate() && !vni->isUnused()) { 00388 unsigned index = vni->def / InstrSlots::NUM; 00389 unsigned offset = vni->def % InstrSlots::NUM; 00390 if (offset == InstrSlots::LOAD) { 00391 std::vector<IdxMBBPair>::const_iterator I = 00392 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); 00393 // Take the pair containing the index 00394 std::vector<IdxMBBPair>::const_iterator J = 00395 (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 00396 00397 vni->def = getMBBStartIdx(J->second); 00398 } else { 00399 vni->def = mi2iMap_[OldI2MI[index]] + offset; 00400 } 00401 } 00402 00403 // Remap the VNInfo kill indices, which works the same as 00404 // the end indices above. 00405 for (size_t i = 0; i < vni->kills.size(); ++i) { 00406 unsigned killIdx = vni->kills[i].killIdx; 00407 00408 unsigned index = (killIdx - 1) / InstrSlots::NUM; 00409 unsigned offset = killIdx % InstrSlots::NUM; 00410 00411 if (offset == InstrSlots::LOAD) { 00412 assert("Value killed at a load slot."); 00413 /*std::vector<IdxMBBPair>::const_iterator I = 00414 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); 00415 --I; 00416 00417 vni->kills[i] = getMBBEndIdx(I->second);*/ 00418 } else { 00419 if (vni->kills[i].isPHIKill) { 00420 std::vector<IdxMBBPair>::const_iterator I = 00421 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index); 00422 --I; 00423 vni->kills[i].killIdx = terminatorGaps[I->second]; 00424 } else { 00425 assert(OldI2MI[index] != 0 && 00426 "Kill refers to instruction not present in index maps."); 00427 vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset; 00428 } 00429 00430 /* 00431 unsigned idx = index; 00432 while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 00433 00434 if (index != OldI2MI.size()) 00435 vni->kills[i] = mi2iMap_[OldI2MI[index]] + 00436 (idx == index ? offset : 0); 00437 else 00438 vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); 00439 */ 00440 } 00441 } 00442 } 00443 } 00444 } 00445 00446 void LiveIntervals::scaleNumbering(int factor) { 00447 // Need to 00448 // * scale MBB begin and end points 00449 // * scale all ranges. 00450 // * Update VNI structures. 00451 // * Scale instruction numberings 00452 00453 // Scale the MBB indices. 00454 Idx2MBBMap.clear(); 00455 for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end(); 00456 MBB != MBBE; ++MBB) { 00457 std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()]; 00458 mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor); 00459 mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor); 00460 Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); 00461 } 00462 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 00463 00464 // Scale terminator gaps. 00465 for (DenseMap<MachineBasicBlock*, unsigned>::iterator 00466 TGI = terminatorGaps.begin(), TGE = terminatorGaps.end(); 00467 TGI != TGE; ++TGI) { 00468 terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor); 00469 } 00470 00471 // Scale the intervals. 00472 for (iterator LI = begin(), LE = end(); LI != LE; ++LI) { 00473 LI->second->scaleNumbering(factor); 00474 } 00475 00476 // Scale MachineInstrs. 00477 Mi2IndexMap oldmi2iMap = mi2iMap_; 00478 unsigned highestSlot = 0; 00479 for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end(); 00480 MI != ME; ++MI) { 00481 unsigned newSlot = InstrSlots::scale(MI->second, factor); 00482 mi2iMap_[MI->first] = newSlot; 00483 highestSlot = std::max(highestSlot, newSlot); 00484 } 00485 00486 i2miMap_.clear(); 00487 i2miMap_.resize(highestSlot + 1); 00488 for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end(); 00489 MI != ME; ++MI) { 00490 i2miMap_[MI->second] = const_cast<MachineInstr *>(MI->first); 00491 } 00492 00493 } 00494 00495 00496 /// runOnMachineFunction - Register allocate the whole function 00497 /// 00498 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 00499 mf_ = &fn; 00500 mri_ = &mf_->getRegInfo(); 00501 tm_ = &fn.getTarget(); 00502 tri_ = tm_->getRegisterInfo(); 00503 tii_ = tm_->getInstrInfo(); 00504 aa_ = &getAnalysis<AliasAnalysis>(); 00505 lv_ = &getAnalysis<LiveVariables>(); 00506 allocatableRegs_ = tri_->getAllocatableSet(fn); 00507 00508 processImplicitDefs(); 00509 computeNumbering(); 00510 computeIntervals(); 00511 00512 numIntervals += getNumIntervals(); 00513 00514 DEBUG(dump()); 00515 return true; 00516 } 00517 00518 /// print - Implement the dump method. 00519 void LiveIntervals::print(std::ostream &O, const Module* ) const { 00520 O << "********** INTERVALS **********\n"; 00521 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00522 I->second->print(O, tri_); 00523 O << "\n"; 00524 } 00525 00526 O << "********** MACHINEINSTRS **********\n"; 00527 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 00528 mbbi != mbbe; ++mbbi) { 00529 O << ((Value*)mbbi->getBasicBlock())->getNameStr() << ":\n"; 00530 for (MachineBasicBlock::iterator mii = mbbi->begin(), 00531 mie = mbbi->end(); mii != mie; ++mii) { 00532 O << getInstructionIndex(mii) << '\t' << *mii; 00533 } 00534 } 00535 } 00536 00537 /// conflictsWithPhysRegDef - Returns true if the specified register 00538 /// is defined during the duration of the specified interval. 00539 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 00540 VirtRegMap &vrm, unsigned reg) { 00541 for (LiveInterval::Ranges::const_iterator 00542 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 00543 for (unsigned index = getBaseIndex(I->start), 00544 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 00545 index += InstrSlots::NUM) { 00546 // skip deleted instructions 00547 while (index != end && !getInstructionFromIndex(index)) 00548 index += InstrSlots::NUM; 00549 if (index == end) break; 00550 00551 MachineInstr *MI = getInstructionFromIndex(index); 00552 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00553 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 00554 if (SrcReg == li.reg || DstReg == li.reg) 00555 continue; 00556 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 00557 MachineOperand& mop = MI->getOperand(i); 00558 if (!mop.isReg()) 00559 continue; 00560 unsigned PhysReg = mop.getReg(); 00561 if (PhysReg == 0 || PhysReg == li.reg) 00562 continue; 00563 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 00564 if (!vrm.hasPhys(PhysReg)) 00565 continue; 00566 PhysReg = vrm.getPhys(PhysReg); 00567 } 00568 if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 00569 return true; 00570 } 00571 } 00572 } 00573 00574 return false; 00575 } 00576 00577 /// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except 00578 /// it can check use as well. 00579 bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, 00580 unsigned Reg, bool CheckUse, 00581 SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 00582 for (LiveInterval::Ranges::const_iterator 00583 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 00584 for (unsigned index = getBaseIndex(I->start), 00585 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 00586 index += InstrSlots::NUM) { 00587 // Skip deleted instructions. 00588 MachineInstr *MI = 0; 00589 while (index != end) { 00590 MI = getInstructionFromIndex(index); 00591 if (MI) 00592 break; 00593 index += InstrSlots::NUM; 00594 } 00595 if (index == end) break; 00596 00597 if (JoinedCopies.count(MI)) 00598 continue; 00599 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00600 MachineOperand& MO = MI->getOperand(i); 00601 if (!MO.isReg()) 00602 continue; 00603 if (MO.isUse() && !CheckUse) 00604 continue; 00605 unsigned PhysReg = MO.getReg(); 00606 if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 00607 continue; 00608 if (tri_->isSubRegister(Reg, PhysReg)) 00609 return true; 00610 } 00611 } 00612 } 00613 00614 return false; 00615 } 00616 00617 00618 void LiveIntervals::printRegName(unsigned reg) const { 00619 if (TargetRegisterInfo::isPhysicalRegister(reg)) 00620 errs() << tri_->getName(reg); 00621 else 00622 errs() << "%reg" << reg; 00623 } 00624 00625 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 00626 MachineBasicBlock::iterator mi, 00627 unsigned MIIdx, MachineOperand& MO, 00628 unsigned MOIdx, 00629 LiveInterval &interval) { 00630 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 00631 00632 // Virtual registers may be defined multiple times (due to phi 00633 // elimination and 2-addr elimination). Much of what we do only has to be 00634 // done once for the vreg. We use an empty interval to detect the first 00635 // time we see a vreg. 00636 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 00637 if (interval.empty()) { 00638 // Get the Idx of the defining instructions. 00639 unsigned defIndex = getDefIndex(MIIdx); 00640 // Earlyclobbers move back one. 00641 if (MO.isEarlyClobber()) 00642 defIndex = getUseIndex(MIIdx); 00643 VNInfo *ValNo; 00644 MachineInstr *CopyMI = NULL; 00645 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00646 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 00647 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 00648 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 00649 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 00650 CopyMI = mi; 00651 // Earlyclobbers move back one. 00652 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 00653 00654 assert(ValNo->id == 0 && "First value in interval is not 0?"); 00655 00656 // Loop over all of the blocks that the vreg is defined in. There are 00657 // two cases we have to handle here. The most common case is a vreg 00658 // whose lifetime is contained within a basic block. In this case there 00659 // will be a single kill, in MBB, which comes after the definition. 00660 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 00661 // FIXME: what about dead vars? 00662 unsigned killIdx; 00663 if (vi.Kills[0] != mi) 00664 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 00665 else 00666 killIdx = defIndex+1; 00667 00668 // If the kill happens after the definition, we have an intra-block 00669 // live range. 00670 if (killIdx > defIndex) { 00671 assert(vi.AliveBlocks.empty() && 00672 "Shouldn't be alive across any blocks!"); 00673 LiveRange LR(defIndex, killIdx, ValNo); 00674 interval.addRange(LR); 00675 DOUT << " +" << LR << "\n"; 00676 interval.addKill(ValNo, killIdx, false); 00677 return; 00678 } 00679 } 00680 00681 // The other case we handle is when a virtual register lives to the end 00682 // of the defining block, potentially live across some blocks, then is 00683 // live into some number of blocks, but gets killed. Start by adding a 00684 // range that goes from this definition to the end of the defining block. 00685 LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); 00686 DOUT << " +" << NewLR; 00687 interval.addRange(NewLR); 00688 00689 // Iterate over all of the blocks that the variable is completely 00690 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 00691 // live interval. 00692 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 00693 E = vi.AliveBlocks.end(); I != E; ++I) { 00694 LiveRange LR(getMBBStartIdx(*I), 00695 getMBBEndIdx(*I)+1, // MBB ends at -1. 00696 ValNo); 00697 interval.addRange(LR); 00698 DOUT << " +" << LR; 00699 } 00700 00701 // Finally, this virtual register is live from the start of any killing 00702 // block to the 'use' slot of the killing instruction. 00703 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 00704 MachineInstr *Kill = vi.Kills[i]; 00705 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 00706 LiveRange LR(getMBBStartIdx(Kill->getParent()), 00707 killIdx, ValNo); 00708 interval.addRange(LR); 00709 interval.addKill(ValNo, killIdx, false); 00710 DOUT << " +" << LR; 00711 } 00712 00713 } else { 00714 // If this is the second time we see a virtual register definition, it 00715 // must be due to phi elimination or two addr elimination. If this is 00716 // the result of two address elimination, then the vreg is one of the 00717 // def-and-use register operand. 00718 if (mi->isRegTiedToUseOperand(MOIdx)) { 00719 // If this is a two-address definition, then we have already processed 00720 // the live range. The only problem is that we didn't realize there 00721 // are actually two values in the live interval. Because of this we 00722 // need to take the LiveRegion that defines this register and split it 00723 // into two values. 00724 assert(interval.containsOneValue()); 00725 unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 00726 unsigned RedefIndex = getDefIndex(MIIdx); 00727 if (MO.isEarlyClobber()) 00728 RedefIndex = getUseIndex(MIIdx); 00729 00730 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 00731 VNInfo *OldValNo = OldLR->valno; 00732 00733 // Delete the initial value, which should be short and continuous, 00734 // because the 2-addr copy must be in the same MBB as the redef. 00735 interval.removeRange(DefIndex, RedefIndex); 00736 00737 // Two-address vregs should always only be redefined once. This means 00738 // that at this point, there should be exactly one value number in it. 00739 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 00740 00741 // The new value number (#1) is defined by the instruction we claimed 00742 // defined value #0. 00743 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 00744 false, // update at * 00745 VNInfoAllocator); 00746 ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 00747 00748 // Value#0 is now defined by the 2-addr instruction. 00749 OldValNo->def = RedefIndex; 00750 OldValNo->setCopy(0); 00751 if (MO.isEarlyClobber()) 00752 OldValNo->setHasRedefByEC(true); 00753 00754 // Add the new live interval which replaces the range for the input copy. 00755 LiveRange LR(DefIndex, RedefIndex, ValNo); 00756 DOUT << " replace range with " << LR; 00757 interval.addRange(LR); 00758 interval.addKill(ValNo, RedefIndex, false); 00759 00760 // If this redefinition is dead, we need to add a dummy unit live 00761 // range covering the def slot. 00762 if (MO.isDead()) 00763 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 00764 00765 DOUT << " RESULT: "; 00766 interval.print(DOUT, tri_); 00767 00768 } else { 00769 // Otherwise, this must be because of phi elimination. If this is the 00770 // first redefinition of the vreg that we have seen, go back and change 00771 // the live range in the PHI block to be a different value number. 00772 if (interval.containsOneValue()) { 00773 assert(vi.Kills.size() == 1 && 00774 "PHI elimination vreg should have one kill, the PHI itself!"); 00775 00776 // Remove the old range that we now know has an incorrect number. 00777 VNInfo *VNI = interval.getValNumInfo(0); 00778 MachineInstr *Killer = vi.Kills[0]; 00779 unsigned Start = getMBBStartIdx(Killer->getParent()); 00780 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 00781 DOUT << " Removing [" << Start << "," << End << "] from: "; 00782 interval.print(DOUT, tri_); DOUT << "\n"; 00783 interval.removeRange(Start, End); 00784 assert(interval.ranges.size() == 1 && 00785 "newly discovered PHI interval has >1 ranges."); 00786 MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber()); 00787 interval.addKill(VNI, terminatorGaps[killMBB], true); 00788 VNI->setHasPHIKill(true); 00789 DOUT << " RESULT: "; interval.print(DOUT, tri_); 00790 00791 // Replace the interval with one of a NEW value number. Note that this 00792 // value number isn't actually defined by an instruction, weird huh? :) 00793 LiveRange LR(Start, End, 00794 interval.getNextValue(mbb->getNumber(), 0, false, VNInfoAllocator)); 00795 LR.valno->setIsPHIDef(true); 00796 DOUT << " replace range with " << LR; 00797 interval.addRange(LR); 00798 interval.addKill(LR.valno, End, false); 00799 DOUT << " RESULT: "; interval.print(DOUT, tri_); 00800 } 00801 00802 // In the case of PHI elimination, each variable definition is only 00803 // live until the end of the block. We've already taken care of the 00804 // rest of the live range. 00805 unsigned defIndex = getDefIndex(MIIdx); 00806 if (MO.isEarlyClobber()) 00807 defIndex = getUseIndex(MIIdx); 00808 00809 VNInfo *ValNo; 00810 MachineInstr *CopyMI = NULL; 00811 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00812 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 00813 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 00814 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 00815 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 00816 CopyMI = mi; 00817 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 00818 00819 unsigned killIndex = getMBBEndIdx(mbb) + 1; 00820 LiveRange LR(defIndex, killIndex, ValNo); 00821 interval.addRange(LR); 00822 interval.addKill(ValNo, terminatorGaps[mbb], true); 00823 ValNo->setHasPHIKill(true); 00824 DOUT << " +" << LR; 00825 } 00826 } 00827 00828 DOUT << '\n'; 00829 } 00830 00831 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 00832 MachineBasicBlock::iterator mi, 00833 unsigned MIIdx, 00834 MachineOperand& MO, 00835 LiveInterval &interval, 00836 MachineInstr *CopyMI) { 00837 // A physical register cannot be live across basic block, so its 00838 // lifetime must end somewhere in its defining basic block. 00839 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 00840 00841 unsigned baseIndex = MIIdx; 00842 unsigned start = getDefIndex(baseIndex); 00843 // Earlyclobbers move back one. 00844 if (MO.isEarlyClobber()) 00845 start = getUseIndex(MIIdx); 00846 unsigned end = start; 00847 00848 // If it is not used after definition, it is considered dead at 00849 // the instruction defining it. Hence its interval is: 00850 // [defSlot(def), defSlot(def)+1) 00851 if (MO.isDead()) { 00852 DOUT << " dead"; 00853 end = start + 1; 00854 goto exit; 00855 } 00856 00857 // If it is not dead on definition, it must be killed by a 00858 // subsequent instruction. Hence its interval is: 00859 // [defSlot(def), useSlot(kill)+1) 00860 baseIndex += InstrSlots::NUM; 00861 while (++mi != MBB->end()) { 00862 while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 00863 getInstructionFromIndex(baseIndex) == 0) 00864 baseIndex += InstrSlots::NUM; 00865 if (mi->killsRegister(interval.reg, tri_)) { 00866 DOUT << " killed"; 00867 end = getUseIndex(baseIndex) + 1; 00868 goto exit; 00869 } else { 00870 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 00871 if (DefIdx != -1) { 00872 if (mi->isRegTiedToUseOperand(DefIdx)) { 00873 // Two-address instruction. 00874 end = getDefIndex(baseIndex); 00875 if (mi->getOperand(DefIdx).isEarlyClobber()) 00876 end = getUseIndex(baseIndex); 00877 } else { 00878 // Another instruction redefines the register before it is ever read. 00879 // Then the register is essentially dead at the instruction that defines 00880 // it. Hence its interval is: 00881 // [defSlot(def), defSlot(def)+1) 00882 DOUT << " dead"; 00883 end = start + 1; 00884 } 00885 goto exit; 00886 } 00887 } 00888 00889 baseIndex += InstrSlots::NUM; 00890 } 00891 00892 // The only case we should have a dead physreg here without a killing or 00893 // instruction where we know it's dead is if it is live-in to the function 00894 // and never used. Another possible case is the implicit use of the 00895 // physical register has been deleted by two-address pass. 00896 end = start + 1; 00897 00898 exit: 00899 assert(start < end && "did not find end of interval?"); 00900 00901 // Already exists? Extend old live interval. 00902 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 00903 bool Extend = OldLR != interval.end(); 00904 VNInfo *ValNo = Extend 00905 ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 00906 if (MO.isEarlyClobber() && Extend) 00907 ValNo->setHasRedefByEC(true); 00908 LiveRange LR(start, end, ValNo); 00909 interval.addRange(LR); 00910 interval.addKill(LR.valno, end, false); 00911 DOUT << " +" << LR << '\n'; 00912 } 00913 00914 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 00915 MachineBasicBlock::iterator MI, 00916 unsigned MIIdx, 00917 MachineOperand& MO, 00918 unsigned MOIdx) { 00919 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 00920 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 00921 getOrCreateInterval(MO.getReg())); 00922 else if (allocatableRegs_[MO.getReg()]) { 00923 MachineInstr *CopyMI = NULL; 00924 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00925 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 00926 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 00927 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 00928 tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 00929 CopyMI = MI; 00930 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 00931 getOrCreateInterval(MO.getReg()), CopyMI); 00932 // Def of a register also defines its sub-registers. 00933 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 00934 // If MI also modifies the sub-register explicitly, avoid processing it 00935 // more than once. Do not pass in TRI here so it checks for exact match. 00936 if (!MI->modifiesRegister(*AS)) 00937 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 00938 getOrCreateInterval(*AS), 0); 00939 } 00940 } 00941 00942 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 00943 unsigned MIIdx, 00944 LiveInterval &interval, bool isAlias) { 00945 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 00946 00947 // Look for kills, if it reaches a def before it's killed, then it shouldn't 00948 // be considered a livein. 00949 MachineBasicBlock::iterator mi = MBB->begin(); 00950 unsigned baseIndex = MIIdx; 00951 unsigned start = baseIndex; 00952 while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 00953 getInstructionFromIndex(baseIndex) == 0) 00954 baseIndex += InstrSlots::NUM; 00955 unsigned end = baseIndex; 00956 bool SeenDefUse = false; 00957 00958 while (mi != MBB->end()) { 00959 if (mi->killsRegister(interval.reg, tri_)) { 00960 DOUT << " killed"; 00961 end = getUseIndex(baseIndex) + 1; 00962 SeenDefUse = true; 00963 break; 00964 } else if (mi->modifiesRegister(interval.reg, tri_)) { 00965 // Another instruction redefines the register before it is ever read. 00966 // Then the register is essentially dead at the instruction that defines 00967 // it. Hence its interval is: 00968 // [defSlot(def), defSlot(def)+1) 00969 DOUT << " dead"; 00970 end = getDefIndex(start) + 1; 00971 SeenDefUse = true; 00972 break; 00973 } 00974 00975 baseIndex += InstrSlots::NUM; 00976 ++mi; 00977 if (mi != MBB->end()) { 00978 while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 00979 getInstructionFromIndex(baseIndex) == 0) 00980 baseIndex += InstrSlots::NUM; 00981 } 00982 } 00983 00984 // Live-in register might not be used at all. 00985 if (!SeenDefUse) { 00986 if (isAlias) { 00987 DOUT << " dead"; 00988 end = getDefIndex(MIIdx) + 1; 00989 } else { 00990 DOUT << " live through"; 00991 end = baseIndex; 00992 } 00993 } 00994 00995 VNInfo *vni = 00996 interval.getNextValue(MBB->getNumber(), 0, false, VNInfoAllocator); 00997 vni->setIsPHIDef(true); 00998 LiveRange LR(start, end, vni); 00999 01000 interval.addRange(LR); 01001 interval.addKill(LR.valno, end, false); 01002 DOUT << " +" << LR << '\n'; 01003 } 01004 01005 /// computeIntervals - computes the live intervals for virtual 01006 /// registers. for some ordering of the machine instructions [1,N] a 01007 /// live interval is an interval [i, j) where 1 <= i <= j < N for 01008 /// which a variable is live 01009 void LiveIntervals::computeIntervals() { 01010 01011 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" 01012 << "********** Function: " 01013 << ((Value*)mf_->getFunction())->getName() << '\n'); 01014 01015 SmallVector<unsigned, 8> UndefUses; 01016 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 01017 MBBI != E; ++MBBI) { 01018 MachineBasicBlock *MBB = MBBI; 01019 // Track the index of the current machine instr. 01020 unsigned MIIndex = getMBBStartIdx(MBB); 01021 DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 01022 01023 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 01024 01025 // Create intervals for live-ins to this BB first. 01026 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 01027 LE = MBB->livein_end(); LI != LE; ++LI) { 01028 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 01029 // Multiple live-ins can alias the same register. 01030 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 01031 if (!hasInterval(*AS)) 01032 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 01033 true); 01034 } 01035 01036 // Skip over empty initial indices. 01037 while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 01038 getInstructionFromIndex(MIIndex) == 0) 01039 MIIndex += InstrSlots::NUM; 01040 01041 for (; MI != miEnd; ++MI) { 01042 DOUT << MIIndex << "\t" << *MI; 01043 01044 // Handle defs. 01045 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 01046 MachineOperand &MO = MI->getOperand(i); 01047 if (!MO.isReg() || !MO.getReg()) 01048 continue; 01049 01050 // handle register defs - build intervals 01051 if (MO.isDef()) 01052 handleRegisterDef(MBB, MI, MIIndex, MO, i); 01053 else if (MO.isUndef()) 01054 UndefUses.push_back(MO.getReg()); 01055 } 01056 01057 // Skip over the empty slots after each instruction. 01058 unsigned Slots = MI->getDesc().getNumDefs(); 01059 if (Slots == 0) 01060 Slots = 1; 01061 MIIndex += InstrSlots::NUM * Slots; 01062 01063 // Skip over empty indices. 01064 while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 01065 getInstructionFromIndex(MIIndex) == 0) 01066 MIIndex += InstrSlots::NUM; 01067 } 01068 } 01069 01070 // Create empty intervals for registers defined by implicit_def's (except 01071 // for those implicit_def that define values which are liveout of their 01072 // blocks. 01073 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 01074 unsigned UndefReg = UndefUses[i]; 01075 (void)getOrCreateInterval(UndefReg); 01076 } 01077 } 01078 01079 bool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End, 01080 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 01081 std::vector<IdxMBBPair>::const_iterator I = 01082 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 01083 01084 bool ResVal = false; 01085 while (I != Idx2MBBMap.end()) { 01086 if (I->first >= End) 01087 break; 01088 MBBs.push_back(I->second); 01089 ResVal = true; 01090 ++I; 01091 } 01092 return ResVal; 01093 } 01094 01095 bool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End, 01096 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 01097 std::vector<IdxMBBPair>::const_iterator I = 01098 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 01099 01100 bool ResVal = false; 01101 while (I != Idx2MBBMap.end()) { 01102 if (I->first > End) 01103 break; 01104 MachineBasicBlock *MBB = I->second; 01105 if (getMBBEndIdx(MBB) > End) 01106 break; 01107 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 01108 SE = MBB->succ_end(); SI != SE; ++SI) 01109 MBBs.push_back(*SI); 01110 ResVal = true; 01111 ++I; 01112 } 01113 return ResVal; 01114 } 01115 01116 LiveInterval* LiveIntervals::createInterval(unsigned reg) { 01117 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 01118 return new LiveInterval(reg, Weight); 01119 } 01120 01121 /// dupInterval - Duplicate a live interval. The caller is responsible for 01122 /// managing the allocated memory. 01123 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 01124 LiveInterval *NewLI = createInterval(li->reg); 01125 NewLI->Copy(*li, mri_, getVNInfoAllocator()); 01126 return NewLI; 01127 } 01128 01129 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo 01130 /// copy field and returns the source register that defines it. 01131 unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 01132 if (!VNI->getCopy()) 01133 return 0; 01134 01135 if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 01136 // If it's extracting out of a physical register, return the sub-register. 01137 unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 01138 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 01139 Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 01140 return Reg; 01141 } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 01142 VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 01143 return VNI->getCopy()->getOperand(2).getReg(); 01144 01145 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 01146 if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 01147 return SrcReg; 01148 llvm_unreachable("Unrecognized copy instruction!"); 01149 return 0; 01150 } 01151 01152 //===----------------------------------------------------------------------===// 01153 // Register allocator hooks. 01154 // 01155 01156 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only 01157 /// allow one) virtual register operand, then its uses are implicitly using 01158 /// the register. Returns the virtual register. 01159 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 01160 MachineInstr *MI) const { 01161 unsigned RegOp = 0; 01162 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 01163 MachineOperand &MO = MI->getOperand(i); 01164 if (!MO.isReg() || !MO.isUse()) 01165 continue; 01166 unsigned Reg = MO.getReg(); 01167 if (Reg == 0 || Reg == li.reg) 01168 continue; 01169 01170 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 01171 !allocatableRegs_[Reg]) 01172 continue; 01173 // FIXME: For now, only remat MI with at most one register operand. 01174 assert(!RegOp && 01175 "Can't rematerialize instruction with multiple register operand!"); 01176 RegOp = MO.getReg(); 01177 #ifndef NDEBUG 01178 break; 01179 #endif 01180 } 01181 return RegOp; 01182 } 01183 01184 /// isValNoAvailableAt - Return true if the val# of the specified interval 01185 /// which reaches the given instruction also reaches the specified use index. 01186 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 01187 unsigned UseIdx) const { 01188 unsigned Index = getInstructionIndex(MI); 01189 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 01190 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 01191 return UI != li.end() && UI->valno == ValNo; 01192 } 01193 01194 /// isReMaterializable - Returns true if the definition MI of the specified 01195 /// val# of the specified interval is re-materializable. 01196 bool LiveIntervals::isReMaterializable(const LiveInterval &li, 01197 const VNInfo *ValNo, MachineInstr *MI, 01198 SmallVectorImpl<LiveInterval*> &SpillIs, 01199 bool &isLoad) { 01200 if (DisableReMat) 01201 return false; 01202 01203 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 01204 return true; 01205 01206 int FrameIdx = 0; 01207 if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 01208 mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 01209 // FIXME: Let target specific isReallyTriviallyReMaterializable determines 01210 // this but remember this is not safe to fold into a two-address 01211 // instruction. 01212 // This is a load from fixed stack slot. It can be rematerialized. 01213 return true; 01214 01215 // If the target-specific rules don't identify an instruction as 01216 // being trivially rematerializable, use some target-independent 01217 // rules. 01218 if (!MI->getDesc().isRematerializable() || 01219 !tii_->isTriviallyReMaterializable(MI)) { 01220 if (!EnableAggressiveRemat) 01221 return false; 01222 01223 // If the instruction accesses memory but the memoperands have been lost, 01224 // we can't analyze it. 01225 const TargetInstrDesc &TID = MI->getDesc(); 01226 if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) 01227 return false; 01228 01229 // Avoid instructions obviously unsafe for remat. 01230 if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) 01231 return false; 01232 01233 // If the instruction accesses memory and the memory could be non-constant, 01234 // assume the instruction is not rematerializable. 01235 for (std::list<MachineMemOperand>::const_iterator 01236 I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ 01237 const MachineMemOperand &MMO = *I; 01238 if (MMO.isVolatile() || MMO.isStore()) 01239 return false; 01240 const Value *V = MMO.getValue(); 01241 if (!V) 01242 return false; 01243 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 01244 if (!PSV->isConstant(mf_->getFrameInfo())) 01245 return false; 01246 } else if (!aa_->pointsToConstantMemory(V)) 01247 return false; 01248 } 01249 01250 // If any of the registers accessed are non-constant, conservatively assume 01251 // the instruction is not rematerializable. 01252 unsigned ImpUse = 0; 01253 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 01254 const MachineOperand &MO = MI->getOperand(i); 01255 if (MO.isReg()) { 01256 unsigned Reg = MO.getReg(); 01257 if (Reg == 0) 01258 continue; 01259 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 01260 return false; 01261 01262 // Only allow one def, and that in the first operand. 01263 if (MO.isDef() != (i == 0)) 01264 return false; 01265 01266 // Only allow constant-valued registers. 01267 bool IsLiveIn = mri_->isLiveIn(Reg); 01268 MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), 01269 E = mri_->def_end(); 01270 01271 // For the def, it should be the only def of that register. 01272 if (MO.isDef() && (next(I) != E || IsLiveIn)) 01273 return false; 01274 01275 if (MO.isUse()) { 01276 // Only allow one use other register use, as that's all the 01277 // remat mechanisms support currently. 01278 if (Reg != li.reg) { 01279 if (ImpUse == 0) 01280 ImpUse = Reg; 01281 else if (Reg != ImpUse) 01282 return false; 01283 } 01284 // For the use, there should be only one associated def. 01285 if (I != E && (next(I) != E || IsLiveIn)) 01286 return false; 01287 } 01288 } 01289 } 01290 } 01291 01292 unsigned ImpUse = getReMatImplicitUse(li, MI); 01293 if (ImpUse) { 01294 const LiveInterval &ImpLi = getInterval(ImpUse); 01295 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 01296 re = mri_->use_end(); ri != re; ++ri) { 01297 MachineInstr *UseMI = &*ri; 01298 unsigned UseIdx = getInstructionIndex(UseMI); 01299 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 01300 continue; 01301 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 01302 return false; 01303 } 01304 01305 // If a register operand of the re-materialized instruction is going to 01306 // be spilled next, then it's not legal to re-materialize this instruction. 01307 for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 01308 if (ImpUse == SpillIs[i]->reg) 01309 return false; 01310 } 01311 return true; 01312 } 01313 01314 /// isReMaterializable - Returns true if the definition MI of the specified 01315 /// val# of the specified interval is re-materializable. 01316 bool LiveIntervals::isReMaterializable(const LiveInterval &li, 01317 const VNInfo *ValNo, MachineInstr *MI) { 01318 SmallVector<LiveInterval*, 4> Dummy1; 01319 bool Dummy2; 01320 return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 01321 } 01322 01323 /// isReMaterializable - Returns true if every definition of MI of every 01324 /// val# of the specified interval is re-materializable. 01325 bool LiveIntervals::isReMaterializable(const LiveInterval &li, 01326 SmallVectorImpl<LiveInterval*> &SpillIs, 01327 bool &isLoad) { 01328 isLoad = false; 01329 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 01330 i != e; ++i) { 01331 const VNInfo *VNI = *i; 01332 if (VNI->isUnused()) 01333 continue; // Dead val#. 01334 // Is the def for the val# rematerializable? 01335 if (!VNI->isDefAccurate()) 01336 return false; 01337 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 01338 bool DefIsLoad = false; 01339 if (!ReMatDefMI || 01340 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 01341 return false; 01342 isLoad |= DefIsLoad; 01343 } 01344 return true; 01345 } 01346 01347 /// FilterFoldedOps - Filter out two-address use operands. Return 01348 /// true if it finds any issue with the operands that ought to prevent 01349 /// folding. 01350 static bool FilterFoldedOps(MachineInstr *MI, 01351 SmallVector<unsigned, 2> &Ops, 01352 unsigned &MRInfo, 01353 SmallVector<unsigned, 2> &FoldOps) { 01354 MRInfo = 0; 01355 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 01356 unsigned OpIdx = Ops[i]; 01357 MachineOperand &MO = MI->getOperand(OpIdx); 01358 // FIXME: fold subreg use. 01359 if (MO.getSubReg()) 01360 return true; 01361 if (MO.isDef()) 01362 MRInfo |= (unsigned)VirtRegMap::isMod; 01363 else { 01364 // Filter out two-address use operand(s). 01365 if (MI->isRegTiedToDefOperand(OpIdx)) { 01366 MRInfo = VirtRegMap::isModRef; 01367 continue; 01368 } 01369 MRInfo |= (unsigned)VirtRegMap::isRef; 01370 } 01371 FoldOps.push_back(OpIdx); 01372 } 01373 return false; 01374 } 01375 01376 01377 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 01378 /// slot / to reg or any rematerialized load into ith operand of specified 01379 /// MI. If it is successul, MI is updated with the newly created MI and 01380 /// returns true. 01381 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 01382 VirtRegMap &vrm, MachineInstr *DefMI, 01383 unsigned InstrIdx, 01384 SmallVector<unsigned, 2> &Ops, 01385 bool isSS, int Slot, unsigned Reg) { 01386 // If it is an implicit def instruction, just delete it. 01387 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 01388 RemoveMachineInstrFromMaps(MI); 01389 vrm.RemoveMachineInstrFromMaps(MI); 01390 MI->eraseFromParent(); 01391 ++numFolds; 01392 return true; 01393 } 01394 01395 // Filter the list of operand indexes that are to be folded. Abort if 01396 // any operand will prevent folding. 01397 unsigned MRInfo = 0; 01398 SmallVector<unsigned, 2> FoldOps; 01399 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 01400 return false; 01401 01402 // The only time it's safe to fold into a two address instruction is when 01403 // it's folding reload and spill from / into a spill stack slot. 01404 if (DefMI && (MRInfo & VirtRegMap::isMod)) 01405 return false; 01406 01407 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 01408 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 01409 if (fmi) { 01410 // Remember this instruction uses the spill slot. 01411 if (isSS) vrm.addSpillSlotUse(Slot, fmi); 01412 01413 // Attempt to fold the memory reference into the instruction. If 01414 // we can do this, we don't need to insert spill code. 01415 MachineBasicBlock &MBB = *MI->getParent(); 01416 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 01417 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 01418 vrm.transferSpillPts(MI, fmi); 01419 vrm.transferRestorePts(MI, fmi); 01420 vrm.transferEmergencySpills(MI, fmi); 01421 mi2iMap_.erase(MI); 01422 i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 01423 mi2iMap_[fmi] = InstrIdx; 01424 MI = MBB.insert(MBB.erase(MI), fmi); 01425 ++numFolds; 01426 return true; 01427 } 01428 return false; 01429 } 01430 01431 /// canFoldMemoryOperand - Returns true if the specified load / store 01432 /// folding is possible. 01433 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 01434 SmallVector<unsigned, 2> &Ops, 01435 bool ReMat) const { 01436 // Filter the list of operand indexes that are to be folded. Abort if 01437 // any operand will prevent folding. 01438 unsigned MRInfo = 0; 01439 SmallVector<unsigned, 2> FoldOps; 01440 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 01441 return false; 01442 01443 // It's only legal to remat for a use, not a def. 01444 if (ReMat && (MRInfo & VirtRegMap::isMod)) 01445 return false; 01446 01447 return tii_->canFoldMemoryOperand(MI, FoldOps); 01448 } 01449 01450 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 01451 SmallPtrSet<MachineBasicBlock*, 4> MBBs; 01452 for (LiveInterval::Ranges::const_iterator 01453 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 01454 std::vector<IdxMBBPair>::const_iterator II = 01455 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 01456 if (II == Idx2MBBMap.end()) 01457 continue; 01458 if (I->end > II->first) // crossing a MBB. 01459 return false; 01460 MBBs.insert(II->second); 01461 if (MBBs.size() > 1) 01462 return false; 01463 } 01464 return true; 01465 } 01466 01467 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 01468 /// interval on to-be re-materialized operands of MI) with new register. 01469 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 01470 MachineInstr *MI, unsigned NewVReg, 01471 VirtRegMap &vrm) { 01472 // There is an implicit use. That means one of the other operand is 01473 // being remat'ed and the remat'ed instruction has li.reg as an 01474 // use operand. Make sure we rewrite that as well. 01475 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 01476 MachineOperand &MO = MI->getOperand(i); 01477 if (!MO.isReg()) 01478 continue; 01479 unsigned Reg = MO.getReg(); 01480 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 01481 continue; 01482 if (!vrm.isReMaterialized(Reg)) 01483 continue; 01484 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 01485 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 01486 if (UseMO) 01487 UseMO->setReg(NewVReg); 01488 } 01489 } 01490 01491 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 01492 /// for addIntervalsForSpills to rewrite uses / defs for the given live range. 01493 bool LiveIntervals:: 01494 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 01495 bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 01496 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 01497 unsigned Slot, int LdSlot, 01498 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 01499 VirtRegMap &vrm, 01500 const TargetRegisterClass* rc, 01501 SmallVector<int, 4> &ReMatIds, 01502 const MachineLoopInfo *loopInfo, 01503 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 01504 DenseMap<unsigned,unsigned> &MBBVRegsMap, 01505 std::vector<LiveInterval*> &NewLIs) { 01506 bool CanFold = false; 01507 RestartInstruction: 01508 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 01509 MachineOperand& mop = MI->getOperand(i); 01510 if (!mop.isReg()) 01511 continue; 01512 unsigned Reg = mop.getReg(); 01513 unsigned RegI = Reg; 01514 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 01515 continue; 01516 if (Reg != li.reg) 01517 continue; 01518 01519 bool TryFold = !DefIsReMat; 01520 bool FoldSS = true; // Default behavior unless it's a remat. 01521 int FoldSlot = Slot; 01522 if (DefIsReMat) { 01523 // If this is the rematerializable definition MI itself and 01524 // all of its uses are rematerialized, simply delete it. 01525 if (MI == ReMatOrigDefMI && CanDelete) { 01526 DOUT << "\t\t\t\tErasing re-materlizable def: "; 01527 DOUT << MI << '\n'; 01528 RemoveMachineInstrFromMaps(MI); 01529 vrm.RemoveMachineInstrFromMaps(MI); 01530 MI->eraseFromParent(); 01531 break; 01532 } 01533 01534 // If def for this use can't be rematerialized, then try folding. 01535 // If def is rematerializable and it's a load, also try folding. 01536 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 01537 if (isLoad) { 01538 // Try fold loads (from stack slot, constant pool, etc.) into uses. 01539 FoldSS = isLoadSS; 01540 FoldSlot = LdSlot; 01541 } 01542 } 01543 01544 // Scan all of the operands of this instruction rewriting operands 01545 // to use NewVReg instead of li.reg as appropriate. We do this for 01546 // two reasons: 01547 // 01548 // 1. If the instr reads the same spilled vreg multiple times, we 01549 // want to reuse the NewVReg. 01550 // 2. If the instr is a two-addr instruction, we are required to 01551 // keep the src/dst regs pinned. 01552 // 01553 // Keep track of whether we replace a use and/or def so that we can 01554 // create the spill interval with the appropriate range. 01555 01556 HasUse = mop.isUse(); 01557 HasDef = mop.isDef(); 01558 SmallVector<unsigned, 2> Ops; 01559 Ops.push_back(i); 01560 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 01561 const MachineOperand &MOj = MI->getOperand(j); 01562 if (!MOj.isReg()) 01563 continue; 01564 unsigned RegJ = MOj.getReg(); 01565 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 01566 continue; 01567 if (RegJ == RegI) { 01568 Ops.push_back(j); 01569 if (!MOj.isUndef()) { 01570 HasUse |= MOj.isUse(); 01571 HasDef |= MOj.isDef(); 01572 } 01573 } 01574 } 01575 01576 // Create a new virtual register for the spill interval. 01577 // Create the new register now so we can map the fold instruction 01578 // to the new register so when it is unfolded we get the correct 01579 // answer. 01580 bool CreatedNewVReg = false; 01581 if (NewVReg == 0) { 01582 NewVReg = mri_->createVirtualRegister(rc); 01583 vrm.grow(); 01584 CreatedNewVReg = true; 01585 } 01586 01587 if (!TryFold) 01588 CanFold = false; 01589 else { 01590 // Do not fold load / store here if we are splitting. We'll find an 01591 // optimal point to insert a load / store later. 01592 if (!TrySplit) { 01593 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 01594 Ops, FoldSS, FoldSlot, NewVReg)) { 01595 // Folding the load/store can completely change the instruction in 01596 // unpredictable ways, rescan it from the beginning. 01597 01598 if (FoldSS) { 01599 // We need to give the new vreg the same stack slot as the 01600 // spilled interval. 01601 vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 01602 } 01603 01604 HasUse = false; 01605 HasDef = false; 01606 CanFold = false; 01607 if (isNotInMIMap(MI)) 01608 break; 01609 goto RestartInstruction; 01610 } 01611 } else { 01612 // We'll try to fold it later if it's profitable. 01613 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 01614 } 01615 } 01616 01617 mop.setReg(NewVReg); 01618 if (mop.isImplicit()) 01619 rewriteImplicitOps(li, MI, NewVReg, vrm); 01620 01621 // Reuse NewVReg for other reads. 01622 for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 01623 MachineOperand &mopj = MI->getOperand(Ops[j]); 01624 mopj.setReg(NewVReg); 01625 if (mopj.isImplicit()) 01626 rewriteImplicitOps(li, MI, NewVReg, vrm); 01627 } 01628 01629 if (CreatedNewVReg) { 01630 if (DefIsReMat) { 01631 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 01632 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 01633 // Each valnum may have its own remat id. 01634 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 01635 } else { 01636 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 01637 } 01638 if (!CanDelete || (HasUse && HasDef)) { 01639 // If this is a two-addr instruction then its use operands are 01640 // rematerializable but its def is not. It should be assigned a 01641 // stack slot. 01642 vrm.assignVirt2StackSlot(NewVReg, Slot); 01643 } 01644 } else { 01645 vrm.assignVirt2StackSlot(NewVReg, Slot); 01646 } 01647 } else if (HasUse && HasDef && 01648 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 01649 // If this interval hasn't been assigned a stack slot (because earlier 01650 // def is a deleted remat def), do it now. 01651 assert(Slot != VirtRegMap::NO_STACK_SLOT); 01652 vrm.assignVirt2StackSlot(NewVReg, Slot); 01653 } 01654 01655 // Re-matting an instruction with virtual register use. Add the 01656 // register as an implicit use on the use MI. 01657 if (DefIsReMat && ImpUse) 01658 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 01659 01660 // Create a new register interval for this spill / remat. 01661 LiveInterval &nI = getOrCreateInterval(NewVReg); 01662 if (CreatedNewVReg) { 01663 NewLIs.push_back(&nI); 01664 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 01665 if (TrySplit) 01666 vrm.setIsSplitFromReg(NewVReg, li.reg); 01667 } 01668 01669 if (HasUse) { 01670 if (CreatedNewVReg) { 01671 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 01672 nI.getNextValue(0, 0, false, VNInfoAllocator)); 01673 DOUT << " +" << LR; 01674 nI.addRange(LR); 01675 } else { 01676 // Extend the split live interval to this def / use. 01677 unsigned End = getUseIndex(index)+1; 01678 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 01679 nI.getValNumInfo(nI.getNumValNums()-1)); 01680 DOUT << " +" << LR; 01681 nI.addRange(LR); 01682 } 01683 } 01684 if (HasDef) { 01685 LiveRange LR(getDefIndex(index), getStoreIndex(index), 01686 nI.getNextValue(0, 0, false, VNInfoAllocator)); 01687 DOUT << " +" << LR; 01688 nI.addRange(LR); 01689 } 01690 01691 DOUT << "\t\t\t\tAdded new interval: "; 01692 nI.print(DOUT, tri_); 01693 DOUT << '\n'; 01694 } 01695 return CanFold; 01696 } 01697 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 01698 const VNInfo *VNI, 01699 MachineBasicBlock *MBB, unsigned Idx) const { 01700 unsigned End = getMBBEndIdx(MBB); 01701 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 01702 if (VNI->kills[j].isPHIKill) 01703 continue; 01704 01705 unsigned KillIdx = VNI->kills[j].killIdx; 01706 if (KillIdx > Idx && KillIdx < End) 01707 return true; 01708 } 01709 return false; 01710 } 01711 01712 /// RewriteInfo - Keep track of machine instrs that will be rewritten 01713 /// during spilling. 01714 namespace { 01715 struct RewriteInfo { 01716 unsigned Index; 01717 MachineInstr *MI; 01718 bool HasUse; 01719 bool HasDef; 01720 RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 01721 : Index(i), MI(mi), HasUse(u), HasDef(d) {} 01722 }; 01723 01724 struct RewriteInfoCompare { 01725 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 01726 return LHS.Index < RHS.Index; 01727 } 01728 }; 01729 } 01730 01731 void LiveIntervals:: 01732 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 01733 LiveInterval::Ranges::const_iterator &I, 01734 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 01735 unsigned Slot, int LdSlot, 01736 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 01737 VirtRegMap &vrm, 01738 const TargetRegisterClass* rc, 01739 SmallVector<int, 4> &ReMatIds, 01740 const MachineLoopInfo *loopInfo, 01741 BitVector &SpillMBBs, 01742 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 01743 BitVector &RestoreMBBs, 01744 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 01745 DenseMap<unsigned,unsigned> &MBBVRegsMap, 01746 std::vector<LiveInterval*> &NewLIs) { 01747 bool AllCanFold = true; 01748 unsigned NewVReg = 0; 01749 unsigned start = getBaseIndex(I->start); 01750 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 01751 01752 // First collect all the def / use in this live range that will be rewritten. 01753 // Make sure they are sorted according to instruction index. 01754 std::vector<RewriteInfo> RewriteMIs; 01755 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 01756 re = mri_->reg_end(); ri != re; ) { 01757 MachineInstr *MI = &*ri; 01758 MachineOperand &O = ri.getOperand(); 01759 ++ri; 01760 assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 01761 unsigned index = getInstructionIndex(MI); 01762 if (index < start || index >= end) 01763 continue; 01764 01765 if (O.isUndef()) 01766 // Must be defined by an implicit def. It should not be spilled. Note, 01767 // this is for correctness reason. e.g. 01768 // 8 %reg1024<def> = IMPLICIT_DEF 01769 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 01770 // The live range [12, 14) are not part of the r1024 live interval since 01771 // it's defined by an implicit def. It will not conflicts with live 01772 // interval of r1025. Now suppose both registers are spilled, you can 01773 // easily see a situation where both registers are reloaded before 01774 // the INSERT_SUBREG and both target registers that would overlap. 01775 continue; 01776 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 01777 } 01778 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 01779 01780 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 01781 // Now rewrite the defs and uses. 01782 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 01783 RewriteInfo &rwi = RewriteMIs[i]; 01784 ++i; 01785 unsigned index = rwi.Index; 01786 bool MIHasUse = rwi.HasUse; 01787 bool MIHasDef = rwi.HasDef; 01788 MachineInstr *MI = rwi.MI; 01789 // If MI def and/or use the same register multiple times, then there 01790 // are multiple entries. 01791 unsigned NumUses = MIHasUse; 01792 while (i != e && RewriteMIs[i].MI == MI) { 01793 assert(RewriteMIs[i].Index == index); 01794 bool isUse = RewriteMIs[i].HasUse; 01795 if (isUse) ++NumUses; 01796 MIHasUse |= isUse; 01797 MIHasDef |= RewriteMIs[i].HasDef; 01798 ++i; 01799 } 01800 MachineBasicBlock *MBB = MI->getParent(); 01801 01802 if (ImpUse && MI != ReMatDefMI) { 01803 // Re-matting an instruction with virtual register use. Update the 01804 // register interval's spill weight to HUGE_VALF to prevent it from 01805 // being spilled. 01806 LiveInterval &ImpLi = getInterval(ImpUse); 01807 ImpLi.weight = HUGE_VALF; 01808 } 01809 01810 unsigned MBBId = MBB->getNumber(); 01811 unsigned ThisVReg = 0; 01812 if (TrySplit) { 01813 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 01814 if (NVI != MBBVRegsMap.end()) { 01815 ThisVReg = NVI->second; 01816 // One common case: 01817 // x = use 01818 // ... 01819 // ... 01820 // def = ... 01821 // = use 01822 // It's better to start a new interval to avoid artifically 01823 // extend the new interval. 01824 if (MIHasDef && !MIHasUse) { 01825 MBBVRegsMap.erase(MBB->getNumber()); 01826 ThisVReg = 0; 01827 } 01828 } 01829 } 01830 01831 bool IsNew = ThisVReg == 0; 01832 if (IsNew) { 01833 // This ends the previous live interval. If all of its def / use 01834 // can be folded, give it a low spill weight. 01835 if (NewVReg && TrySplit && AllCanFold) { 01836 LiveInterval &nI = getOrCreateInterval(NewVReg); 01837 nI.weight /= 10.0F; 01838 } 01839 AllCanFold = true; 01840 } 01841 NewVReg = ThisVReg; 01842 01843 bool HasDef = false; 01844 bool HasUse = false; 01845 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 01846 index, end, MI, ReMatOrigDefMI, ReMatDefMI, 01847 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 01848 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 01849 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 01850 if (!HasDef && !HasUse) 01851 continue; 01852 01853 AllCanFold &= CanFold; 01854 01855 // Update weight of spill interval. 01856 LiveInterval &nI = getOrCreateInterval(NewVReg); 01857 if (!TrySplit) { 01858 // The spill weight is now infinity as it cannot be spilled again. 01859 nI.weight = HUGE_VALF; 01860 continue; 01861 } 01862 01863 // Keep track of the last def and first use in each MBB. 01864 if (HasDef) { 01865 if (MI != ReMatOrigDefMI || !CanDelete) { 01866 bool HasKill = false; 01867 if (!HasUse) 01868 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 01869 else { 01870 // If this is a two-address code, then this index starts a new VNInfo. 01871 const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); 01872 if (VNI) 01873 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 01874 } 01875 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 01876 SpillIdxes.find(MBBId); 01877 if (!HasKill) { 01878 if (SII == SpillIdxes.end()) { 01879 std::vector<SRInfo> S; 01880 S.push_back(SRInfo(index, NewVReg, true)); 01881 SpillIdxes.insert(std::make_pair(MBBId, S)); 01882 } else if (SII->second.back().vreg != NewVReg) { 01883 SII->second.push_back(SRInfo(index, NewVReg, true)); 01884 } else if ((int)index > SII->second.back().index) { 01885 // If there is an earlier def and this is a two-address 01886 // instruction, then it's not possible to fold the store (which 01887 // would also fold the load). 01888 SRInfo &Info = SII->second.back(); 01889 Info.index = index; 01890 Info.canFold = !HasUse; 01891 } 01892 SpillMBBs.set(MBBId); 01893 } else if (SII != SpillIdxes.end() && 01894 SII->second.back().vreg == NewVReg && 01895 (int)index > SII->second.back().index) { 01896 // There is an earlier def that's not killed (must be two-address). 01897 // The spill is no longer needed. 01898 SII->second.pop_back(); 01899 if (SII->second.empty()) { 01900 SpillIdxes.erase(MBBId); 01901 SpillMBBs.reset(MBBId); 01902 } 01903 } 01904 } 01905 } 01906 01907 if (HasUse) { 01908 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 01909 SpillIdxes.find(MBBId); 01910 if (SII != SpillIdxes.end() && 01911 SII->second.back().vreg == NewVReg && 01912 (int)index > SII->second.back().index) 01913 // Use(s) following the last def, it's not safe to fold the spill. 01914 SII->second.back().canFold = false; 01915 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 01916 RestoreIdxes.find(MBBId); 01917 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 01918 // If we are splitting live intervals, only fold if it's the first 01919 // use and there isn't another use later in the MBB. 01920 RII->second.back().canFold = false; 01921 else if (IsNew) { 01922 // Only need a reload if there isn't an earlier def / use. 01923 if (RII == RestoreIdxes.end()) { 01924 std::vector<SRInfo> Infos; 01925 Infos.push_back(SRInfo(index, NewVReg, true)); 01926 RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 01927 } else { 01928 RII->second.push_back(SRInfo(index, NewVReg, true)); 01929 } 01930 RestoreMBBs.set(MBBId); 01931 } 01932 } 01933 01934 // Update spill weight. 01935 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 01936 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 01937 } 01938 01939 if (NewVReg && TrySplit && AllCanFold) { 01940 // If all of its def / use can be folded, give it a low spill weight. 01941 LiveInterval &nI = getOrCreateInterval(NewVReg); 01942 nI.weight /= 10.0F; 01943 } 01944 } 01945 01946 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 01947 BitVector &RestoreMBBs, 01948 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 01949 if (!RestoreMBBs[Id]) 01950 return false; 01951 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 01952 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 01953 if (Restores[i].index == index && 01954 Restores[i].vreg == vr && 01955 Restores[i].canFold) 01956 return true; 01957 return false; 01958 } 01959 01960 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 01961 BitVector &RestoreMBBs, 01962 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 01963 if (!RestoreMBBs[Id]) 01964 return; 01965 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 01966 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 01967 if (Restores[i].index == index && Restores[i].vreg) 01968 Restores[i].index = -1; 01969 } 01970 01971 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 01972 /// spilled and create empty intervals for their uses. 01973 void 01974 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 01975 const TargetRegisterClass* rc, 01976 std::vector<LiveInterval*> &NewLIs) { 01977 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 01978 re = mri_->reg_end(); ri != re; ) { 01979 MachineOperand &O = ri.getOperand(); 01980 MachineInstr *MI = &*ri; 01981 ++ri; 01982 if (O.isDef()) { 01983 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 01984 "Register def was not rewritten?"); 01985 RemoveMachineInstrFromMaps(MI); 01986 vrm.RemoveMachineInstrFromMaps(MI); 01987 MI->eraseFromParent(); 01988 } else { 01989 // This must be an use of an implicit_def so it's not part of the live 01990 // interval. Create a new empty live interval for it. 01991 // FIXME: Can we simply erase some of the instructions? e.g. Stores? 01992 unsigned NewVReg = mri_->createVirtualRegister(rc); 01993 vrm.grow(); 01994 vrm.setIsImplicitlyDefined(NewVReg); 01995 NewLIs.push_back(&getOrCreateInterval(NewVReg)); 01996 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 01997 MachineOperand &MO = MI->getOperand(i); 01998 if (MO.isReg() && MO.getReg() == li.reg) { 01999 MO.setReg(NewVReg); 02000 MO.setIsUndef(); 02001 } 02002 } 02003 } 02004 } 02005 } 02006 02007 std::vector<LiveInterval*> LiveIntervals:: 02008 addIntervalsForSpillsFast(const LiveInterval &li, 02009 const MachineLoopInfo *loopInfo, 02010 VirtRegMap &vrm) { 02011 unsigned slot = vrm.assignVirt2StackSlot(li.reg); 02012 02013 std::vector<LiveInterval*> added; 02014 02015 assert(li.weight != HUGE_VALF && 02016 "attempt to spill already spilled interval!"); 02017 02018 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 02019 DEBUG(li.dump()); 02020 DOUT << '\n'; 02021 02022 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 02023 02024 MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 02025 while (RI != mri_->reg_end()) { 02026 MachineInstr* MI = &*RI; 02027 02028 SmallVector<unsigned, 2> Indices; 02029 bool HasUse = false; 02030 bool HasDef = false; 02031 02032 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 02033 MachineOperand& mop = MI->getOperand(i); 02034 if (!mop.isReg() || mop.getReg() != li.reg) continue; 02035 02036 HasUse |= MI->getOperand(i).isUse(); 02037 HasDef |= MI->getOperand(i).isDef(); 02038 02039 Indices.push_back(i); 02040 } 02041 02042 if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 02043 Indices, true, slot, li.reg)) { 02044 unsigned NewVReg = mri_->createVirtualRegister(rc); 02045 vrm.grow(); 02046 vrm.assignVirt2StackSlot(NewVReg, slot); 02047 02048 // create a new register for this spill 02049 LiveInterval &nI = getOrCreateInterval(NewVReg); 02050 02051 // the spill weight is now infinity as it 02052 // cannot be spilled again 02053 nI.weight = HUGE_VALF; 02054 02055 // Rewrite register operands to use the new vreg. 02056 for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 02057 E = Indices.end(); I != E; ++I) { 02058 MI->getOperand(*I).setReg(NewVReg); 02059 02060 if (MI->getOperand(*I).isUse()) 02061 MI->getOperand(*I).setIsKill(true); 02062 } 02063 02064 // Fill in the new live interval. 02065 unsigned index = getInstructionIndex(MI); 02066 if (HasUse) { 02067 LiveRange LR(getLoadIndex(index), getUseIndex(index), 02068 nI.getNextValue(0, 0, false, getVNInfoAllocator())); 02069 DOUT << " +" << LR; 02070 nI.addRange(LR); 02071 vrm.addRestorePoint(NewVReg, MI); 02072 } 02073 if (HasDef) { 02074 LiveRange LR(getDefIndex(index), getStoreIndex(index), 02075 nI.getNextValue(0, 0, false, getVNInfoAllocator())); 02076 DOUT << " +" << LR; 02077 nI.addRange(LR); 02078 vrm.addSpillPoint(NewVReg, true, MI); 02079 } 02080 02081 added.push_back(&nI); 02082 02083 DOUT << "\t\t\t\tadded new interval: "; 02084 DEBUG(nI.dump()); 02085 DOUT << '\n'; 02086 } 02087 02088 02089 RI = mri_->reg_begin(li.reg); 02090 } 02091 02092 return added; 02093 } 02094 02095 std::vector<LiveInterval*> LiveIntervals:: 02096 addIntervalsForSpills(const LiveInterval &li, 02097 SmallVectorImpl<LiveInterval*> &SpillIs, 02098 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 02099 02100 if (EnableFastSpilling) 02101 return addIntervalsForSpillsFast(li, loopInfo, vrm); 02102 02103 assert(li.weight != HUGE_VALF && 02104 "attempt to spill already spilled interval!"); 02105 02106 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 02107 li.print(DOUT, tri_); 02108 DOUT << '\n'; 02109 02110 // Each bit specify whether a spill is required in the MBB. 02111 BitVector SpillMBBs(mf_->getNumBlockIDs()); 02112 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 02113 BitVector RestoreMBBs(mf_->getNumBlockIDs()); 02114 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 02115 DenseMap<unsigned,unsigned> MBBVRegsMap; 02116 std::vector<LiveInterval*> NewLIs; 02117 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 02118 02119 unsigned NumValNums = li.getNumValNums(); 02120 SmallVector<MachineInstr*, 4> ReMatDefs; 02121 ReMatDefs.resize(NumValNums, NULL); 02122 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 02123 ReMatOrigDefs.resize(NumValNums, NULL); 02124 SmallVector<int, 4> ReMatIds; 02125 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 02126 BitVector ReMatDelete(NumValNums); 02127 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 02128 02129 // Spilling a split live interval. It cannot be split any further. Also, 02130 // it's also guaranteed to be a single val# / range interval. 02131 if (vrm.getPreSplitReg(li.reg)) { 02132 vrm.setIsSplitFromReg(li.reg, 0); 02133 // Unset the split kill marker on the last use. 02134 unsigned KillIdx = vrm.getKillPoint(li.reg); 02135 if (KillIdx) { 02136 MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 02137 assert(KillMI && "Last use disappeared?"); 02138 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 02139 assert(KillOp != -1 && "Last use disappeared?"); 02140 KillMI->getOperand(KillOp).setIsKill(false); 02141 } 02142 vrm.removeKillPoint(li.reg); 02143 bool DefIsReMat = vrm.isReMaterialized(li.reg); 02144 Slot = vrm.getStackSlot(li.reg); 02145 assert(Slot != VirtRegMap::MAX_STACK_SLOT); 02146 MachineInstr *ReMatDefMI = DefIsReMat ? 02147 vrm.getReMaterializedMI(li.reg) : NULL; 02148 int LdSlot = 0; 02149 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 02150 bool isLoad = isLoadSS || 02151 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 02152 bool IsFirstRange = true; 02153 for (LiveInterval::Ranges::const_iterator 02154 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 02155 // If this is a split live interval with multiple ranges, it means there 02156 // are two-address instructions that re-defined the value. Only the 02157 // first def can be rematerialized! 02158 if (IsFirstRange) { 02159 // Note ReMatOrigDefMI has already been deleted. 02160 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 02161 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 02162 false, vrm, rc, ReMatIds, loopInfo, 02163 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 02164 MBBVRegsMap, NewLIs); 02165 } else { 02166 rewriteInstructionsForSpills(li, false, I, NULL, 0, 02167 Slot, 0, false, false, false, 02168 false, vrm, rc, ReMatIds, loopInfo, 02169 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 02170 MBBVRegsMap, NewLIs); 02171 } 02172 IsFirstRange = false; 02173 } 02174 02175 handleSpilledImpDefs(li, vrm, rc, NewLIs); 02176 return NewLIs; 02177 } 02178 02179 bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 02180 if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 02181 TrySplit = false; 02182 if (TrySplit) 02183 ++numSplits; 02184 bool NeedStackSlot = false; 02185 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 02186 i != e; ++i) { 02187 const VNInfo *VNI = *i; 02188 unsigned VN = VNI->id; 02189 if (VNI->isUnused()) 02190 continue; // Dead val#. 02191 // Is the def for the val# rematerializable? 02192 MachineInstr *ReMatDefMI = VNI->isDefAccurate() 02193 ? getInstructionFromIndex(VNI->def) : 0; 02194 bool dummy; 02195 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 02196 // Remember how to remat the def of this val#. 02197 ReMatOrigDefs[VN] = ReMatDefMI; 02198 // Original def may be modified so we have to make a copy here. 02199 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 02200 ClonedMIs.push_back(Clone); 02201 ReMatDefs[VN] = Clone; 02202 02203 bool CanDelete = true; 02204 if (VNI->hasPHIKill()) { 02205 // A kill is a phi node, not all of its uses can be rematerialized. 02206 // It must not be deleted. 02207 CanDelete = false; 02208 // Need a stack slot if there is any live range where uses cannot be 02209 // rematerialized. 02210 NeedStackSlot = true; 02211 } 02212 if (CanDelete) 02213 ReMatDelete.set(VN); 02214 } else { 02215 // Need a stack slot if there is any live range where uses cannot be 02216 // rematerialized. 02217 NeedStackSlot = true; 02218 } 02219 } 02220 02221 // One stack slot per live interval. 02222 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 02223 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 02224 Slot = vrm.assignVirt2StackSlot(li.reg); 02225 02226 // This case only occurs when the prealloc splitter has already assigned 02227 // a stack slot to this vreg. 02228 else 02229 Slot = vrm.getStackSlot(li.reg); 02230 } 02231 02232 // Create new intervals and rewrite defs and uses. 02233 for (LiveInterval::Ranges::const_iterator 02234 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 02235 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 02236 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 02237 bool DefIsReMat = ReMatDefMI != NULL; 02238 bool CanDelete = ReMatDelete[I->valno->id]; 02239 int LdSlot = 0; 02240 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 02241 bool isLoad = isLoadSS || 02242 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 02243 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 02244 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 02245 CanDelete, vrm, rc, ReMatIds, loopInfo, 02246 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 02247 MBBVRegsMap, NewLIs); 02248 } 02249 02250 // Insert spills / restores if we are splitting. 02251 if (!TrySplit) { 02252 handleSpilledImpDefs(li, vrm, rc, NewLIs); 02253 return NewLIs; 02254 } 02255 02256 SmallPtrSet<LiveInterval*, 4> AddedKill; 02257 SmallVector<unsigned, 2> Ops; 02258 if (NeedStackSlot) { 02259 int Id = SpillMBBs.find_first(); 02260 while (Id != -1) { 02261 std::vector<SRInfo> &spills = SpillIdxes[Id]; 02262 for (unsigned i = 0, e = spills.size(); i != e; ++i) { 02263 int index = spills[i].index; 02264 unsigned VReg = spills[i].vreg; 02265 LiveInterval &nI = getOrCreateInterval(VReg); 02266 bool isReMat = vrm.isReMaterialized(VReg); 02267 MachineInstr *MI = getInstructionFromIndex(index); 02268 bool CanFold = false; 02269 bool FoundUse = false; 02270 Ops.clear(); 02271 if (spills[i].canFold) { 02272 CanFold = true; 02273 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 02274 MachineOperand &MO = MI->getOperand(j); 02275 if (!MO.isReg() || MO.getReg() != VReg) 02276 continue; 02277 02278 Ops.push_back(j); 02279 if (MO.isDef()) 02280 continue; 02281 if (isReMat || 02282 (!FoundUse && !alsoFoldARestore(Id, index, VReg, 02283 RestoreMBBs, RestoreIdxes))) { 02284 // MI has two-address uses of the same register. If the use 02285 // isn't the first and only use in the BB, then we can't fold 02286 // it. FIXME: Move this to rewriteInstructionsForSpills. 02287 CanFold = false; 02288 break; 02289 } 02290 FoundUse = true; 02291 } 02292 } 02293 // Fold the store into the def if possible. 02294 bool Folded = false; 02295 if (CanFold && !Ops.empty()) { 02296 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 02297 Folded = true; 02298 if (FoundUse) { 02299 // Also folded uses, do not issue a load. 02300 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 02301 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 02302 } 02303 nI.removeRange(getDefIndex(index), getStoreIndex(index)); 02304 } 02305 } 02306 02307 // Otherwise tell the spiller to issue a spill. 02308 if (!Folded) { 02309 LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 02310 bool isKill = LR->end == getStoreIndex(index); 02311 if (!MI->registerDefIsDead(nI.reg)) 02312 // No need to spill a dead def. 02313 vrm.addSpillPoint(VReg, isKill, MI); 02314 if (isKill) 02315 AddedKill.insert(&nI); 02316 } 02317 } 02318 Id = SpillMBBs.find_next(Id); 02319 } 02320 } 02321 02322 int Id = RestoreMBBs.find_first(); 02323 while (Id != -1) { 02324 std::vector<SRInfo> &restores = RestoreIdxes[Id]; 02325 for (unsigned i = 0, e = restores.size(); i != e; ++i) { 02326 int index = restores[i].index; 02327 if (index == -1) 02328 continue; 02329 unsigned VReg = restores[i].vreg; 02330 LiveInterval &nI = getOrCreateInterval(VReg); 02331 bool isReMat = vrm.isReMaterialized(VReg); 02332 MachineInstr *MI = getInstructionFromIndex(index); 02333 bool CanFold = false; 02334 Ops.clear(); 02335 if (restores[i].canFold) { 02336 CanFold = true; 02337 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 02338 MachineOperand &MO = MI->getOperand(j); 02339 if (!MO.isReg() || MO.getReg() != VReg) 02340 continue; 02341 02342 if (MO.isDef()) { 02343 // If this restore were to be folded, it would have been folded 02344 // already. 02345 CanFold = false; 02346 break; 02347 } 02348 Ops.push_back(j); 02349 } 02350 } 02351 02352 // Fold the load into the use if possible. 02353 bool Folded = false; 02354 if (CanFold && !Ops.empty()) { 02355 if (!isReMat) 02356 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 02357 else { 02358 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 02359 int LdSlot = 0; 02360 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 02361 // If the rematerializable def is a load, also try to fold it. 02362 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 02363 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 02364 Ops, isLoadSS, LdSlot, VReg); 02365 if (!Folded) { 02366 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 02367 if (ImpUse) { 02368 // Re-matting an instruction with virtual register use. Add the 02369 // register as an implicit use on the use MI and update the register 02370 // interval's spill weight to HUGE_VALF to prevent it from being 02371 // spilled. 02372 LiveInterval &ImpLi = getInterval(ImpUse); 02373 ImpLi.weight = HUGE_VALF; 02374 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 02375 } 02376 } 02377 } 02378 } 02379 // If folding is not possible / failed, then tell the spiller to issue a 02380 // load / rematerialization for us. 02381 if (Folded) 02382 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 02383 else 02384 vrm.addRestorePoint(VReg, MI); 02385 } 02386 Id = RestoreMBBs.find_next(Id); 02387 } 02388 02389 // Finalize intervals: add kills, finalize spill weights, and filter out 02390 // dead intervals. 02391 std::vector<LiveInterval*> RetNewLIs; 02392 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 02393 LiveInterval *LI = NewLIs[i]; 02394 if (!LI->empty()) { 02395 LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); 02396 if (!AddedKill.count(LI)) { 02397 LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 02398 unsigned LastUseIdx = getBaseIndex(LR->end); 02399 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 02400 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 02401 assert(UseIdx != -1); 02402 if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 02403 LastUse->getOperand(UseIdx).setIsKill(); 02404 vrm.addKillPoint(LI->reg, LastUseIdx); 02405 } 02406 } 02407 RetNewLIs.push_back(LI); 02408 } 02409 } 02410 02411 handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 02412 return RetNewLIs; 02413 } 02414 02415 /// hasAllocatableSuperReg - Return true if the specified physical register has 02416 /// any super register that's allocatable. 02417 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 02418 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 02419 if (allocatableRegs_[*AS] && hasInterval(*AS)) 02420 return true; 02421 return false; 02422 } 02423 02424 /// getRepresentativeReg - Find the largest super register of the specified 02425 /// physical register. 02426 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 02427 // Find the largest super-register that is allocatable. 02428 unsigned BestReg = Reg; 02429 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 02430 unsigned SuperReg = *AS; 02431 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 02432 BestReg = SuperReg; 02433 break; 02434 } 02435 } 02436 return BestReg; 02437 } 02438 02439 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the 02440 /// specified interval that conflicts with the specified physical register. 02441 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 02442 unsigned PhysReg) const { 02443 unsigned NumConflicts = 0; 02444 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 02445 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 02446 E = mri_->reg_end(); I != E; ++I) { 02447 MachineOperand &O = I.getOperand(); 02448 MachineInstr *MI = O.getParent(); 02449 unsigned Index = getInstructionIndex(MI); 02450 if (pli.liveAt(Index)) 02451 ++NumConflicts; 02452 } 02453 return NumConflicts; 02454 } 02455 02456 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register 02457 /// around all defs and uses of the specified interval. Return true if it 02458 /// was able to cut its interval. 02459 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 02460 unsigned PhysReg, VirtRegMap &vrm) { 02461 unsigned SpillReg = getRepresentativeReg(PhysReg); 02462 02463 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 02464 // If there are registers which alias PhysReg, but which are not a 02465 // sub-register of the chosen representative super register. Assert 02466 // since we can't handle it yet. 02467 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 02468 tri_->isSuperRegister(*AS, SpillReg)); 02469 02470 bool Cut = false; 02471 LiveInterval &pli = getInterval(SpillReg); 02472 SmallPtrSet<MachineInstr*, 8> SeenMIs; 02473 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 02474 E = mri_->reg_end(); I != E; ++I) { 02475 MachineOperand &O = I.getOperand(); 02476 MachineInstr *MI = O.getParent(); 02477 if (SeenMIs.count(MI)) 02478 continue; 02479 SeenMIs.insert(MI); 02480 unsigned Index = getInstructionIndex(MI); 02481 if (pli.liveAt(Index)) { 02482 vrm.addEmergencySpill(SpillReg, MI); 02483 unsigned StartIdx = getLoadIndex(Index); 02484 unsigned EndIdx = getStoreIndex(Index)+1; 02485 if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 02486 pli.removeRange(StartIdx, EndIdx); 02487 Cut = true; 02488 } else { 02489 std::string msg; 02490 raw_string_ostream Msg(msg); 02491 Msg << "Ran out of registers during register allocation!"; 02492 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 02493 Msg << "\nPlease check your inline asm statement for invalid " 02494 << "constraints:\n"; 02495 MI->print(Msg, tm_); 02496 } 02497 llvm_report_error(Msg.str()); 02498 } 02499 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 02500 if (!hasInterval(*AS)) 02501 continue; 02502 LiveInterval &spli = getInterval(*AS); 02503 if (spli.liveAt(Index)) 02504 spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 02505 } 02506 } 02507 } 02508 return Cut; 02509 } 02510 02511 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 02512 MachineInstr* startInst) { 02513 LiveInterval& Interval = getOrCreateInterval(reg); 02514 VNInfo* VN = Interval.getNextValue( 02515 getInstructionIndex(startInst) + InstrSlots::DEF, 02516 startInst, true, getVNInfoAllocator()); 02517 VN->setHasPHIKill(true); 02518 VN->kills.push_back( 02519 VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true)); 02520 LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, 02521 getMBBEndIdx(startInst->getParent()) + 1, VN); 02522 Interval.addRange(LR); 02523 02524 return LR; 02525 } 02526 02527 raw_ostream & 02528 IntervalPrefixPrinter::operator()(raw_ostream &out, 02529 const MachineInstr &instr) const { 02530 return out << liinfo.getInstructionIndex(&instr); 02531 }