LLVM API Documentation
00001 //===-- PreAllocSplitting.cpp - Pre-allocation Interval Spltting Pass. ----===// 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 machine instruction level pre-register allocation 00011 // live interval splitting pass. It finds live interval barriers, i.e. 00012 // instructions which will kill all physical registers in certain register 00013 // classes, and split all live intervals which cross the barrier. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #define DEBUG_TYPE "pre-alloc-split" 00018 #include "VirtRegMap.h" 00019 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00020 #include "llvm/CodeGen/LiveStackAnalysis.h" 00021 #include "llvm/CodeGen/MachineDominators.h" 00022 #include "llvm/CodeGen/MachineFrameInfo.h" 00023 #include "llvm/CodeGen/MachineFunctionPass.h" 00024 #include "llvm/CodeGen/MachineLoopInfo.h" 00025 #include "llvm/CodeGen/MachineRegisterInfo.h" 00026 #include "llvm/CodeGen/Passes.h" 00027 #include "llvm/CodeGen/RegisterCoalescer.h" 00028 #include "llvm/Target/TargetInstrInfo.h" 00029 #include "llvm/Target/TargetMachine.h" 00030 #include "llvm/Target/TargetOptions.h" 00031 #include "llvm/Target/TargetRegisterInfo.h" 00032 #include "llvm/Support/CommandLine.h" 00033 #include "llvm/Support/Debug.h" 00034 #include "llvm/Support/ErrorHandling.h" 00035 #include "llvm/ADT/DenseMap.h" 00036 #include "llvm/ADT/DepthFirstIterator.h" 00037 #include "llvm/ADT/SmallPtrSet.h" 00038 #include "llvm/ADT/Statistic.h" 00039 using namespace llvm; 00040 00041 static cl::opt<int> PreSplitLimit("pre-split-limit", cl::init(-1), cl::Hidden); 00042 static cl::opt<int> DeadSplitLimit("dead-split-limit", cl::init(-1), cl::Hidden); 00043 static cl::opt<int> RestoreFoldLimit("restore-fold-limit", cl::init(-1), cl::Hidden); 00044 00045 STATISTIC(NumSplits, "Number of intervals split"); 00046 STATISTIC(NumRemats, "Number of intervals split by rematerialization"); 00047 STATISTIC(NumFolds, "Number of intervals split with spill folding"); 00048 STATISTIC(NumRestoreFolds, "Number of intervals split with restore folding"); 00049 STATISTIC(NumRenumbers, "Number of intervals renumbered into new registers"); 00050 STATISTIC(NumDeadSpills, "Number of dead spills removed"); 00051 00052 namespace { 00053 class VISIBILITY_HIDDEN PreAllocSplitting : public MachineFunctionPass { 00054 MachineFunction *CurrMF; 00055 const TargetMachine *TM; 00056 const TargetInstrInfo *TII; 00057 const TargetRegisterInfo* TRI; 00058 MachineFrameInfo *MFI; 00059 MachineRegisterInfo *MRI; 00060 LiveIntervals *LIs; 00061 LiveStacks *LSs; 00062 VirtRegMap *VRM; 00063 00064 // Barrier - Current barrier being processed. 00065 MachineInstr *Barrier; 00066 00067 // BarrierMBB - Basic block where the barrier resides in. 00068 MachineBasicBlock *BarrierMBB; 00069 00070 // Barrier - Current barrier index. 00071 unsigned BarrierIdx; 00072 00073 // CurrLI - Current live interval being split. 00074 LiveInterval *CurrLI; 00075 00076 // CurrSLI - Current stack slot live interval. 00077 LiveInterval *CurrSLI; 00078 00079 // CurrSValNo - Current val# for the stack slot live interval. 00080 VNInfo *CurrSValNo; 00081 00082 // IntervalSSMap - A map from live interval to spill slots. 00083 DenseMap<unsigned, int> IntervalSSMap; 00084 00085 // Def2SpillMap - A map from a def instruction index to spill index. 00086 DenseMap<unsigned, unsigned> Def2SpillMap; 00087 00088 public: 00089 static char ID; 00090 PreAllocSplitting() : MachineFunctionPass(&ID) {} 00091 00092 virtual bool runOnMachineFunction(MachineFunction &MF); 00093 00094 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00095 AU.setPreservesCFG(); 00096 AU.addRequired<LiveIntervals>(); 00097 AU.addPreserved<LiveIntervals>(); 00098 AU.addRequired<LiveStacks>(); 00099 AU.addPreserved<LiveStacks>(); 00100 AU.addPreserved<RegisterCoalescer>(); 00101 if (StrongPHIElim) 00102 AU.addPreservedID(StrongPHIEliminationID); 00103 else 00104 AU.addPreservedID(PHIEliminationID); 00105 AU.addRequired<MachineDominatorTree>(); 00106 AU.addRequired<MachineLoopInfo>(); 00107 AU.addRequired<VirtRegMap>(); 00108 AU.addPreserved<MachineDominatorTree>(); 00109 AU.addPreserved<MachineLoopInfo>(); 00110 AU.addPreserved<VirtRegMap>(); 00111 MachineFunctionPass::getAnalysisUsage(AU); 00112 } 00113 00114 virtual void releaseMemory() { 00115 IntervalSSMap.clear(); 00116 Def2SpillMap.clear(); 00117 } 00118 00119 virtual const char *getPassName() const { 00120 return "Pre-Register Allocaton Live Interval Splitting"; 00121 } 00122 00123 /// print - Implement the dump method. 00124 virtual void print(std::ostream &O, const Module* M = 0) const { 00125 LIs->print(O, M); 00126 } 00127 00128 void print(std::ostream *O, const Module* M = 0) const { 00129 if (O) print(*O, M); 00130 } 00131 00132 private: 00133 MachineBasicBlock::iterator 00134 findNextEmptySlot(MachineBasicBlock*, MachineInstr*, 00135 unsigned&); 00136 00137 MachineBasicBlock::iterator 00138 findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*, 00139 SmallPtrSet<MachineInstr*, 4>&, unsigned&); 00140 00141 MachineBasicBlock::iterator 00142 findRestorePoint(MachineBasicBlock*, MachineInstr*, unsigned, 00143 SmallPtrSet<MachineInstr*, 4>&, unsigned&); 00144 00145 int CreateSpillStackSlot(unsigned, const TargetRegisterClass *); 00146 00147 bool IsAvailableInStack(MachineBasicBlock*, unsigned, unsigned, unsigned, 00148 unsigned&, int&) const; 00149 00150 void UpdateSpillSlotInterval(VNInfo*, unsigned, unsigned); 00151 00152 bool SplitRegLiveInterval(LiveInterval*); 00153 00154 bool SplitRegLiveIntervals(const TargetRegisterClass **, 00155 SmallPtrSet<LiveInterval*, 8>&); 00156 00157 bool createsNewJoin(LiveRange* LR, MachineBasicBlock* DefMBB, 00158 MachineBasicBlock* BarrierMBB); 00159 bool Rematerialize(unsigned vreg, VNInfo* ValNo, 00160 MachineInstr* DefMI, 00161 MachineBasicBlock::iterator RestorePt, 00162 unsigned RestoreIdx, 00163 SmallPtrSet<MachineInstr*, 4>& RefsInMBB); 00164 MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC, 00165 MachineInstr* DefMI, 00166 MachineInstr* Barrier, 00167 MachineBasicBlock* MBB, 00168 int& SS, 00169 SmallPtrSet<MachineInstr*, 4>& RefsInMBB); 00170 MachineInstr* FoldRestore(unsigned vreg, 00171 const TargetRegisterClass* RC, 00172 MachineInstr* Barrier, 00173 MachineBasicBlock* MBB, 00174 int SS, 00175 SmallPtrSet<MachineInstr*, 4>& RefsInMBB); 00176 void RenumberValno(VNInfo* VN); 00177 void ReconstructLiveInterval(LiveInterval* LI); 00178 bool removeDeadSpills(SmallPtrSet<LiveInterval*, 8>& split); 00179 unsigned getNumberOfNonSpills(SmallPtrSet<MachineInstr*, 4>& MIs, 00180 unsigned Reg, int FrameIndex, bool& TwoAddr); 00181 VNInfo* PerformPHIConstruction(MachineBasicBlock::iterator Use, 00182 MachineBasicBlock* MBB, LiveInterval* LI, 00183 SmallPtrSet<MachineInstr*, 4>& Visited, 00184 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Defs, 00185 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Uses, 00186 DenseMap<MachineInstr*, VNInfo*>& NewVNs, 00187 DenseMap<MachineBasicBlock*, VNInfo*>& LiveOut, 00188 DenseMap<MachineBasicBlock*, VNInfo*>& Phis, 00189 bool IsTopLevel, bool IsIntraBlock); 00190 VNInfo* PerformPHIConstructionFallBack(MachineBasicBlock::iterator Use, 00191 MachineBasicBlock* MBB, LiveInterval* LI, 00192 SmallPtrSet<MachineInstr*, 4>& Visited, 00193 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Defs, 00194 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Uses, 00195 DenseMap<MachineInstr*, VNInfo*>& NewVNs, 00196 DenseMap<MachineBasicBlock*, VNInfo*>& LiveOut, 00197 DenseMap<MachineBasicBlock*, VNInfo*>& Phis, 00198 bool IsTopLevel, bool IsIntraBlock); 00199 }; 00200 } // end anonymous namespace 00201 00202 char PreAllocSplitting::ID = 0; 00203 00204 static RegisterPass<PreAllocSplitting> 00205 X("pre-alloc-splitting", "Pre-Register Allocation Live Interval Splitting"); 00206 00207 const PassInfo *const llvm::PreAllocSplittingID = &X; 00208 00209 00210 /// findNextEmptySlot - Find a gap after the given machine instruction in the 00211 /// instruction index map. If there isn't one, return end(). 00212 MachineBasicBlock::iterator 00213 PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI, 00214 unsigned &SpotIndex) { 00215 MachineBasicBlock::iterator MII = MI; 00216 if (++MII != MBB->end()) { 00217 unsigned Index = LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII)); 00218 if (Index) { 00219 SpotIndex = Index; 00220 return MII; 00221 } 00222 } 00223 return MBB->end(); 00224 } 00225 00226 /// findSpillPoint - Find a gap as far away from the given MI that's suitable 00227 /// for spilling the current live interval. The index must be before any 00228 /// defs and uses of the live interval register in the mbb. Return begin() if 00229 /// none is found. 00230 MachineBasicBlock::iterator 00231 PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI, 00232 MachineInstr *DefMI, 00233 SmallPtrSet<MachineInstr*, 4> &RefsInMBB, 00234 unsigned &SpillIndex) { 00235 MachineBasicBlock::iterator Pt = MBB->begin(); 00236 00237 MachineBasicBlock::iterator MII = MI; 00238 MachineBasicBlock::iterator EndPt = DefMI 00239 ? MachineBasicBlock::iterator(DefMI) : MBB->begin(); 00240 00241 while (MII != EndPt && !RefsInMBB.count(MII) && 00242 MII->getOpcode() != TRI->getCallFrameSetupOpcode()) 00243 --MII; 00244 if (MII == EndPt || RefsInMBB.count(MII)) return Pt; 00245 00246 while (MII != EndPt && !RefsInMBB.count(MII)) { 00247 unsigned Index = LIs->getInstructionIndex(MII); 00248 00249 // We can't insert the spill between the barrier (a call), and its 00250 // corresponding call frame setup. 00251 if (MII->getOpcode() == TRI->getCallFrameDestroyOpcode()) { 00252 while (MII->getOpcode() != TRI->getCallFrameSetupOpcode()) { 00253 --MII; 00254 if (MII == EndPt) { 00255 return Pt; 00256 } 00257 } 00258 continue; 00259 } else if (LIs->hasGapBeforeInstr(Index)) { 00260 Pt = MII; 00261 SpillIndex = LIs->findGapBeforeInstr(Index, true); 00262 } 00263 00264 if (RefsInMBB.count(MII)) 00265 return Pt; 00266 00267 00268 --MII; 00269 } 00270 00271 return Pt; 00272 } 00273 00274 /// findRestorePoint - Find a gap in the instruction index map that's suitable 00275 /// for restoring the current live interval value. The index must be before any 00276 /// uses of the live interval register in the mbb. Return end() if none is 00277 /// found. 00278 MachineBasicBlock::iterator 00279 PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI, 00280 unsigned LastIdx, 00281 SmallPtrSet<MachineInstr*, 4> &RefsInMBB, 00282 unsigned &RestoreIndex) { 00283 // FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb 00284 // begin index accordingly. 00285 MachineBasicBlock::iterator Pt = MBB->end(); 00286 MachineBasicBlock::iterator EndPt = MBB->getFirstTerminator(); 00287 00288 // We start at the call, so walk forward until we find the call frame teardown 00289 // since we can't insert restores before that. Bail if we encounter a use 00290 // during this time. 00291 MachineBasicBlock::iterator MII = MI; 00292 if (MII == EndPt) return Pt; 00293 00294 while (MII != EndPt && !RefsInMBB.count(MII) && 00295 MII->getOpcode() != TRI->getCallFrameDestroyOpcode()) 00296 ++MII; 00297 if (MII == EndPt || RefsInMBB.count(MII)) return Pt; 00298 ++MII; 00299 00300 // FIXME: Limit the number of instructions to examine to reduce 00301 // compile time? 00302 while (MII != EndPt) { 00303 unsigned Index = LIs->getInstructionIndex(MII); 00304 if (Index > LastIdx) 00305 break; 00306 unsigned Gap = LIs->findGapBeforeInstr(Index); 00307 00308 // We can't insert a restore between the barrier (a call) and its 00309 // corresponding call frame teardown. 00310 if (MII->getOpcode() == TRI->getCallFrameSetupOpcode()) { 00311 do { 00312 if (MII == EndPt || RefsInMBB.count(MII)) return Pt; 00313 ++MII; 00314 } while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode()); 00315 } else if (Gap) { 00316 Pt = MII; 00317 RestoreIndex = Gap; 00318 } 00319 00320 if (RefsInMBB.count(MII)) 00321 return Pt; 00322 00323 ++MII; 00324 } 00325 00326 return Pt; 00327 } 00328 00329 /// CreateSpillStackSlot - Create a stack slot for the live interval being 00330 /// split. If the live interval was previously split, just reuse the same 00331 /// slot. 00332 int PreAllocSplitting::CreateSpillStackSlot(unsigned Reg, 00333 const TargetRegisterClass *RC) { 00334 int SS; 00335 DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg); 00336 if (I != IntervalSSMap.end()) { 00337 SS = I->second; 00338 } else { 00339 SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); 00340 IntervalSSMap[Reg] = SS; 00341 } 00342 00343 // Create live interval for stack slot. 00344 CurrSLI = &LSs->getOrCreateInterval(SS, RC); 00345 if (CurrSLI->hasAtLeastOneValue()) 00346 CurrSValNo = CurrSLI->getValNumInfo(0); 00347 else 00348 CurrSValNo = CurrSLI->getNextValue(0, 0, false, LSs->getVNInfoAllocator()); 00349 return SS; 00350 } 00351 00352 /// IsAvailableInStack - Return true if register is available in a split stack 00353 /// slot at the specified index. 00354 bool 00355 PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB, 00356 unsigned Reg, unsigned DefIndex, 00357 unsigned RestoreIndex, unsigned &SpillIndex, 00358 int& SS) const { 00359 if (!DefMBB) 00360 return false; 00361 00362 DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg); 00363 if (I == IntervalSSMap.end()) 00364 return false; 00365 DenseMap<unsigned, unsigned>::iterator II = Def2SpillMap.find(DefIndex); 00366 if (II == Def2SpillMap.end()) 00367 return false; 00368 00369 // If last spill of def is in the same mbb as barrier mbb (where restore will 00370 // be), make sure it's not below the intended restore index. 00371 // FIXME: Undo the previous spill? 00372 assert(LIs->getMBBFromIndex(II->second) == DefMBB); 00373 if (DefMBB == BarrierMBB && II->second >= RestoreIndex) 00374 return false; 00375 00376 SS = I->second; 00377 SpillIndex = II->second; 00378 return true; 00379 } 00380 00381 /// UpdateSpillSlotInterval - Given the specified val# of the register live 00382 /// interval being split, and the spill and restore indicies, update the live 00383 /// interval of the spill stack slot. 00384 void 00385 PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, unsigned SpillIndex, 00386 unsigned RestoreIndex) { 00387 assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB && 00388 "Expect restore in the barrier mbb"); 00389 00390 MachineBasicBlock *MBB = LIs->getMBBFromIndex(SpillIndex); 00391 if (MBB == BarrierMBB) { 00392 // Intra-block spill + restore. We are done. 00393 LiveRange SLR(SpillIndex, RestoreIndex, CurrSValNo); 00394 CurrSLI->addRange(SLR); 00395 return; 00396 } 00397 00398 SmallPtrSet<MachineBasicBlock*, 4> Processed; 00399 unsigned EndIdx = LIs->getMBBEndIdx(MBB); 00400 LiveRange SLR(SpillIndex, EndIdx+1, CurrSValNo); 00401 CurrSLI->addRange(SLR); 00402 Processed.insert(MBB); 00403 00404 // Start from the spill mbb, figure out the extend of the spill slot's 00405 // live interval. 00406 SmallVector<MachineBasicBlock*, 4> WorkList; 00407 const LiveRange *LR = CurrLI->getLiveRangeContaining(SpillIndex); 00408 if (LR->end > EndIdx) 00409 // If live range extend beyond end of mbb, add successors to work list. 00410 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 00411 SE = MBB->succ_end(); SI != SE; ++SI) 00412 WorkList.push_back(*SI); 00413 00414 while (!WorkList.empty()) { 00415 MachineBasicBlock *MBB = WorkList.back(); 00416 WorkList.pop_back(); 00417 if (Processed.count(MBB)) 00418 continue; 00419 unsigned Idx = LIs->getMBBStartIdx(MBB); 00420 LR = CurrLI->getLiveRangeContaining(Idx); 00421 if (LR && LR->valno == ValNo) { 00422 EndIdx = LIs->getMBBEndIdx(MBB); 00423 if (Idx <= RestoreIndex && RestoreIndex < EndIdx) { 00424 // Spill slot live interval stops at the restore. 00425 LiveRange SLR(Idx, RestoreIndex, CurrSValNo); 00426 CurrSLI->addRange(SLR); 00427 } else if (LR->end > EndIdx) { 00428 // Live range extends beyond end of mbb, process successors. 00429 LiveRange SLR(Idx, EndIdx+1, CurrSValNo); 00430 CurrSLI->addRange(SLR); 00431 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 00432 SE = MBB->succ_end(); SI != SE; ++SI) 00433 WorkList.push_back(*SI); 00434 } else { 00435 LiveRange SLR(Idx, LR->end, CurrSValNo); 00436 CurrSLI->addRange(SLR); 00437 } 00438 Processed.insert(MBB); 00439 } 00440 } 00441 } 00442 00443 /// PerformPHIConstruction - From properly set up use and def lists, use a PHI 00444 /// construction algorithm to compute the ranges and valnos for an interval. 00445 VNInfo* 00446 PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI, 00447 MachineBasicBlock* MBB, LiveInterval* LI, 00448 SmallPtrSet<MachineInstr*, 4>& Visited, 00449 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Defs, 00450 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Uses, 00451 DenseMap<MachineInstr*, VNInfo*>& NewVNs, 00452 DenseMap<MachineBasicBlock*, VNInfo*>& LiveOut, 00453 DenseMap<MachineBasicBlock*, VNInfo*>& Phis, 00454 bool IsTopLevel, bool IsIntraBlock) { 00455 // Return memoized result if it's available. 00456 if (IsTopLevel && Visited.count(UseI) && NewVNs.count(UseI)) 00457 return NewVNs[UseI]; 00458 else if (!IsTopLevel && IsIntraBlock && NewVNs.count(UseI)) 00459 return NewVNs[UseI]; 00460 else if (!IsIntraBlock && LiveOut.count(MBB)) 00461 return LiveOut[MBB]; 00462 00463 // Check if our block contains any uses or defs. 00464 bool ContainsDefs = Defs.count(MBB); 00465 bool ContainsUses = Uses.count(MBB); 00466 00467 VNInfo* RetVNI = 0; 00468 00469 // Enumerate the cases of use/def contaning blocks. 00470 if (!ContainsDefs && !ContainsUses) { 00471 return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses, 00472 NewVNs, LiveOut, Phis, 00473 IsTopLevel, IsIntraBlock); 00474 } else if (ContainsDefs && !ContainsUses) { 00475 SmallPtrSet<MachineInstr*, 2>& BlockDefs = Defs[MBB]; 00476 00477 // Search for the def in this block. If we don't find it before the 00478 // instruction we care about, go to the fallback case. Note that that 00479 // should never happen: this cannot be intrablock, so use should 00480 // always be an end() iterator. 00481 assert(UseI == MBB->end() && "No use marked in intrablock"); 00482 00483 MachineBasicBlock::iterator Walker = UseI; 00484 --Walker; 00485 while (Walker != MBB->begin()) { 00486 if (BlockDefs.count(Walker)) 00487 break; 00488 --Walker; 00489 } 00490 00491 // Once we've found it, extend its VNInfo to our instruction. 00492 unsigned DefIndex = LIs->getInstructionIndex(Walker); 00493 DefIndex = LiveIntervals::getDefIndex(DefIndex); 00494 unsigned EndIndex = LIs->getMBBEndIdx(MBB); 00495 00496 RetVNI = NewVNs[Walker]; 00497 LI->addRange(LiveRange(DefIndex, EndIndex+1, RetVNI)); 00498 } else if (!ContainsDefs && ContainsUses) { 00499 SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB]; 00500 00501 // Search for the use in this block that precedes the instruction we care 00502 // about, going to the fallback case if we don't find it. 00503 if (UseI == MBB->begin()) 00504 return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, 00505 Uses, NewVNs, LiveOut, Phis, 00506 IsTopLevel, IsIntraBlock); 00507 00508 MachineBasicBlock::iterator Walker = UseI; 00509 --Walker; 00510 bool found = false; 00511 while (Walker != MBB->begin()) { 00512 if (BlockUses.count(Walker)) { 00513 found = true; 00514 break; 00515 } 00516 --Walker; 00517 } 00518 00519 // Must check begin() too. 00520 if (!found) { 00521 if (BlockUses.count(Walker)) 00522 found = true; 00523 else 00524 return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, 00525 Uses, NewVNs, LiveOut, Phis, 00526 IsTopLevel, IsIntraBlock); 00527 } 00528 00529 unsigned UseIndex = LIs->getInstructionIndex(Walker); 00530 UseIndex = LiveIntervals::getUseIndex(UseIndex); 00531 unsigned EndIndex = 0; 00532 if (IsIntraBlock) { 00533 EndIndex = LIs->getInstructionIndex(UseI); 00534 EndIndex = LiveIntervals::getUseIndex(EndIndex); 00535 } else 00536 EndIndex = LIs->getMBBEndIdx(MBB); 00537 00538 // Now, recursively phi construct the VNInfo for the use we found, 00539 // and then extend it to include the instruction we care about 00540 RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, 00541 NewVNs, LiveOut, Phis, false, true); 00542 00543 LI->addRange(LiveRange(UseIndex, EndIndex+1, RetVNI)); 00544 00545 // FIXME: Need to set kills properly for inter-block stuff. 00546 if (LI->isKill(RetVNI, UseIndex)) LI->removeKill(RetVNI, UseIndex); 00547 if (IsIntraBlock) 00548 LI->addKill(RetVNI, EndIndex, false); 00549 } else if (ContainsDefs && ContainsUses) { 00550 SmallPtrSet<MachineInstr*, 2>& BlockDefs = Defs[MBB]; 00551 SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB]; 00552 00553 // This case is basically a merging of the two preceding case, with the 00554 // special note that checking for defs must take precedence over checking 00555 // for uses, because of two-address instructions. 00556 00557 if (UseI == MBB->begin()) 00558 return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses, 00559 NewVNs, LiveOut, Phis, 00560 IsTopLevel, IsIntraBlock); 00561 00562 MachineBasicBlock::iterator Walker = UseI; 00563 --Walker; 00564 bool foundDef = false; 00565 bool foundUse = false; 00566 while (Walker != MBB->begin()) { 00567 if (BlockDefs.count(Walker)) { 00568 foundDef = true; 00569 break; 00570 } else if (BlockUses.count(Walker)) { 00571 foundUse = true; 00572 break; 00573 } 00574 --Walker; 00575 } 00576 00577 // Must check begin() too. 00578 if (!foundDef && !foundUse) { 00579 if (BlockDefs.count(Walker)) 00580 foundDef = true; 00581 else if (BlockUses.count(Walker)) 00582 foundUse = true; 00583 else 00584 return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, 00585 Uses, NewVNs, LiveOut, Phis, 00586 IsTopLevel, IsIntraBlock); 00587 } 00588 00589 unsigned StartIndex = LIs->getInstructionIndex(Walker); 00590 StartIndex = foundDef ? LiveIntervals::getDefIndex(StartIndex) : 00591 LiveIntervals::getUseIndex(StartIndex); 00592 unsigned EndIndex = 0; 00593 if (IsIntraBlock) { 00594 EndIndex = LIs->getInstructionIndex(UseI); 00595 EndIndex = LiveIntervals::getUseIndex(EndIndex); 00596 } else 00597 EndIndex = LIs->getMBBEndIdx(MBB); 00598 00599 if (foundDef) 00600 RetVNI = NewVNs[Walker]; 00601 else 00602 RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses, 00603 NewVNs, LiveOut, Phis, false, true); 00604 00605 LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); 00606 00607 if (foundUse && LI->isKill(RetVNI, StartIndex)) 00608 LI->removeKill(RetVNI, StartIndex); 00609 if (IsIntraBlock) { 00610 LI->addKill(RetVNI, EndIndex, false); 00611 } 00612 } 00613 00614 // Memoize results so we don't have to recompute them. 00615 if (!IsIntraBlock) LiveOut[MBB] = RetVNI; 00616 else { 00617 if (!NewVNs.count(UseI)) 00618 NewVNs[UseI] = RetVNI; 00619 Visited.insert(UseI); 00620 } 00621 00622 return RetVNI; 00623 } 00624 00625 /// PerformPHIConstructionFallBack - PerformPHIConstruction fall back path. 00626 /// 00627 VNInfo* 00628 PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator UseI, 00629 MachineBasicBlock* MBB, LiveInterval* LI, 00630 SmallPtrSet<MachineInstr*, 4>& Visited, 00631 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Defs, 00632 DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> >& Uses, 00633 DenseMap<MachineInstr*, VNInfo*>& NewVNs, 00634 DenseMap<MachineBasicBlock*, VNInfo*>& LiveOut, 00635 DenseMap<MachineBasicBlock*, VNInfo*>& Phis, 00636 bool IsTopLevel, bool IsIntraBlock) { 00637 // NOTE: Because this is the fallback case from other cases, we do NOT 00638 // assume that we are not intrablock here. 00639 if (Phis.count(MBB)) return Phis[MBB]; 00640 00641 unsigned StartIndex = LIs->getMBBStartIdx(MBB); 00642 VNInfo *RetVNI = Phis[MBB] = 00643 LI->getNextValue(0, /*FIXME*/ 0, false, LIs->getVNInfoAllocator()); 00644 00645 if (!IsIntraBlock) LiveOut[MBB] = RetVNI; 00646 00647 // If there are no uses or defs between our starting point and the 00648 // beginning of the block, then recursive perform phi construction 00649 // on our predecessors. 00650 DenseMap<MachineBasicBlock*, VNInfo*> IncomingVNs; 00651 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 00652 PE = MBB->pred_end(); PI != PE; ++PI) { 00653 VNInfo* Incoming = PerformPHIConstruction((*PI)->end(), *PI, LI, 00654 Visited, Defs, Uses, NewVNs, 00655 LiveOut, Phis, false, false); 00656 if (Incoming != 0) 00657 IncomingVNs[*PI] = Incoming; 00658 } 00659 00660 if (MBB->pred_size() == 1 && !RetVNI->hasPHIKill()) { 00661 VNInfo* OldVN = RetVNI; 00662 VNInfo* NewVN = IncomingVNs.begin()->second; 00663 VNInfo* MergedVN = LI->MergeValueNumberInto(OldVN, NewVN); 00664 if (MergedVN == OldVN) std::swap(OldVN, NewVN); 00665 00666 for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator LOI = LiveOut.begin(), 00667 LOE = LiveOut.end(); LOI != LOE; ++LOI) 00668 if (LOI->second == OldVN) 00669 LOI->second = MergedVN; 00670 for (DenseMap<MachineInstr*, VNInfo*>::iterator NVI = NewVNs.begin(), 00671 NVE = NewVNs.end(); NVI != NVE; ++NVI) 00672 if (NVI->second == OldVN) 00673 NVI->second = MergedVN; 00674 for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator PI = Phis.begin(), 00675 PE = Phis.end(); PI != PE; ++PI) 00676 if (PI->second == OldVN) 00677 PI->second = MergedVN; 00678 RetVNI = MergedVN; 00679 } else { 00680 // Otherwise, merge the incoming VNInfos with a phi join. Create a new 00681 // VNInfo to represent the joined value. 00682 for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator I = 00683 IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) { 00684 I->second->setHasPHIKill(true); 00685 unsigned KillIndex = LIs->getMBBEndIdx(I->first); 00686 if (!LiveInterval::isKill(I->second, KillIndex)) 00687 LI->addKill(I->second, KillIndex, false); 00688 } 00689 } 00690 00691 unsigned EndIndex = 0; 00692 if (IsIntraBlock) { 00693 EndIndex = LIs->getInstructionIndex(UseI); 00694 EndIndex = LiveIntervals::getUseIndex(EndIndex); 00695 } else 00696 EndIndex = LIs->getMBBEndIdx(MBB); 00697 LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI)); 00698 if (IsIntraBlock) 00699 LI->addKill(RetVNI, EndIndex, false); 00700 00701 // Memoize results so we don't have to recompute them. 00702 if (!IsIntraBlock) 00703 LiveOut[MBB] = RetVNI; 00704 else { 00705 if (!NewVNs.count(UseI)) 00706 NewVNs[UseI] = RetVNI; 00707 Visited.insert(UseI); 00708 } 00709 00710 return RetVNI; 00711 } 00712 00713 /// ReconstructLiveInterval - Recompute a live interval from scratch. 00714 void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) { 00715 BumpPtrAllocator& Alloc = LIs->getVNInfoAllocator(); 00716 00717 // Clear the old ranges and valnos; 00718 LI->clear(); 00719 00720 // Cache the uses and defs of the register 00721 typedef DenseMap<MachineBasicBlock*, SmallPtrSet<MachineInstr*, 2> > RegMap; 00722 RegMap Defs, Uses; 00723 00724 // Keep track of the new VNs we're creating. 00725 DenseMap<MachineInstr*, VNInfo*> NewVNs; 00726 SmallPtrSet<VNInfo*, 2> PhiVNs; 00727 00728 // Cache defs, and create a new VNInfo for each def. 00729 for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg), 00730 DE = MRI->def_end(); DI != DE; ++DI) { 00731 Defs[(*DI).getParent()].insert(&*DI); 00732 00733 unsigned DefIdx = LIs->getInstructionIndex(&*DI); 00734 DefIdx = LiveIntervals::getDefIndex(DefIdx); 00735 00736 assert(DI->getOpcode() != TargetInstrInfo::PHI && 00737 "Following NewVN isPHIDef flag incorrect. Fix me!"); 00738 VNInfo* NewVN = LI->getNextValue(DefIdx, 0, true, Alloc); 00739 00740 // If the def is a move, set the copy field. 00741 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 00742 if (TII->isMoveInstr(*DI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) 00743 if (DstReg == LI->reg) 00744 NewVN->setCopy(&*DI); 00745 00746 NewVNs[&*DI] = NewVN; 00747 } 00748 00749 // Cache uses as a separate pass from actually processing them. 00750 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(LI->reg), 00751 UE = MRI->use_end(); UI != UE; ++UI) 00752 Uses[(*UI).getParent()].insert(&*UI); 00753 00754 // Now, actually process every use and use a phi construction algorithm 00755 // to walk from it to its reaching definitions, building VNInfos along 00756 // the way. 00757 DenseMap<MachineBasicBlock*, VNInfo*> LiveOut; 00758 DenseMap<MachineBasicBlock*, VNInfo*> Phis; 00759 SmallPtrSet<MachineInstr*, 4> Visited; 00760 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(LI->reg), 00761 UE = MRI->use_end(); UI != UE; ++UI) { 00762 PerformPHIConstruction(&*UI, UI->getParent(), LI, Visited, Defs, 00763 Uses, NewVNs, LiveOut, Phis, true, true); 00764 } 00765 00766 // Add ranges for dead defs 00767 for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg), 00768 DE = MRI->def_end(); DI != DE; ++DI) { 00769 unsigned DefIdx = LIs->getInstructionIndex(&*DI); 00770 DefIdx = LiveIntervals::getDefIndex(DefIdx); 00771 00772 if (LI->liveAt(DefIdx)) continue; 00773 00774 VNInfo* DeadVN = NewVNs[&*DI]; 00775 LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN)); 00776 LI->addKill(DeadVN, DefIdx, false); 00777 } 00778 } 00779 00780 /// RenumberValno - Split the given valno out into a new vreg, allowing it to 00781 /// be allocated to a different register. This function creates a new vreg, 00782 /// copies the valno and its live ranges over to the new vreg's interval, 00783 /// removes them from the old interval, and rewrites all uses and defs of 00784 /// the original reg to the new vreg within those ranges. 00785 void PreAllocSplitting::RenumberValno(VNInfo* VN) { 00786 SmallVector<VNInfo*, 4> Stack; 00787 SmallVector<VNInfo*, 4> VNsToCopy; 00788 Stack.push_back(VN); 00789 00790 // Walk through and copy the valno we care about, and any other valnos 00791 // that are two-address redefinitions of the one we care about. These 00792 // will need to be rewritten as well. We also check for safety of the 00793 // renumbering here, by making sure that none of the valno involved has 00794 // phi kills. 00795 while (!Stack.empty()) { 00796 VNInfo* OldVN = Stack.back(); 00797 Stack.pop_back(); 00798 00799 // Bail out if we ever encounter a valno that has a PHI kill. We can't 00800 // renumber these. 00801 if (OldVN->hasPHIKill()) return; 00802 00803 VNsToCopy.push_back(OldVN); 00804 00805 // Locate two-address redefinitions 00806 for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(), 00807 KE = OldVN->kills.end(); KI != KE; ++KI) { 00808 assert(!KI->isPHIKill && "VN previously reported having no PHI kills."); 00809 MachineInstr* MI = LIs->getInstructionFromIndex(KI->killIdx); 00810 unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg); 00811 if (DefIdx == ~0U) continue; 00812 if (MI->isRegTiedToUseOperand(DefIdx)) { 00813 VNInfo* NextVN = 00814 CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(KI->killIdx)); 00815 if (NextVN == OldVN) continue; 00816 Stack.push_back(NextVN); 00817 } 00818 } 00819 } 00820 00821 // Create the new vreg 00822 unsigned NewVReg = MRI->createVirtualRegister(MRI->getRegClass(CurrLI->reg)); 00823 00824 // Create the new live interval 00825 LiveInterval& NewLI = LIs->getOrCreateInterval(NewVReg); 00826 00827 for (SmallVector<VNInfo*, 4>::iterator OI = VNsToCopy.begin(), OE = 00828 VNsToCopy.end(); OI != OE; ++OI) { 00829 VNInfo* OldVN = *OI; 00830 00831 // Copy the valno over 00832 VNInfo* NewVN = NewLI.createValueCopy(OldVN, LIs->getVNInfoAllocator()); 00833 NewLI.MergeValueInAsValue(*CurrLI, OldVN, NewVN); 00834 00835 // Remove the valno from the old interval 00836 CurrLI->removeValNo(OldVN); 00837 } 00838 00839 // Rewrite defs and uses. This is done in two stages to avoid invalidating 00840 // the reg_iterator. 00841 SmallVector<std::pair<MachineInstr*, unsigned>, 8> OpsToChange; 00842 00843 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg), 00844 E = MRI->reg_end(); I != E; ++I) { 00845 MachineOperand& MO = I.getOperand(); 00846 unsigned InstrIdx = LIs->getInstructionIndex(&*I); 00847 00848 if ((MO.isUse() && NewLI.liveAt(LiveIntervals::getUseIndex(InstrIdx))) || 00849 (MO.isDef() && NewLI.liveAt(LiveIntervals::getDefIndex(InstrIdx)))) 00850 OpsToChange.push_back(std::make_pair(&*I, I.getOperandNo())); 00851 } 00852 00853 for (SmallVector<std::pair<MachineInstr*, unsigned>, 8>::iterator I = 00854 OpsToChange.begin(), E = OpsToChange.end(); I != E; ++I) { 00855 MachineInstr* Inst = I->first; 00856 unsigned OpIdx = I->second; 00857 MachineOperand& MO = Inst->getOperand(OpIdx); 00858 MO.setReg(NewVReg); 00859 } 00860 00861 // Grow the VirtRegMap, since we've created a new vreg. 00862 VRM->grow(); 00863 00864 // The renumbered vreg shares a stack slot with the old register. 00865 if (IntervalSSMap.count(CurrLI->reg)) 00866 IntervalSSMap[NewVReg] = IntervalSSMap[CurrLI->reg]; 00867 00868 NumRenumbers++; 00869 } 00870 00871 bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo, 00872 MachineInstr* DefMI, 00873 MachineBasicBlock::iterator RestorePt, 00874 unsigned RestoreIdx, 00875 SmallPtrSet<MachineInstr*, 4>& RefsInMBB) { 00876 MachineBasicBlock& MBB = *RestorePt->getParent(); 00877 00878 MachineBasicBlock::iterator KillPt = BarrierMBB->end(); 00879 unsigned KillIdx = 0; 00880 if (!ValNo->isDefAccurate() || DefMI->getParent() == BarrierMBB) 00881 KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx); 00882 else 00883 KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx); 00884 00885 if (KillPt == DefMI->getParent()->end()) 00886 return false; 00887 00888 TII->reMaterialize(MBB, RestorePt, VReg, 0, DefMI); 00889 LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx); 00890 00891 ReconstructLiveInterval(CurrLI); 00892 unsigned RematIdx = LIs->getInstructionIndex(prior(RestorePt)); 00893 RematIdx = LiveIntervals::getDefIndex(RematIdx); 00894 RenumberValno(CurrLI->findDefinedVNInfo(RematIdx)); 00895 00896 ++NumSplits; 00897 ++NumRemats; 00898 return true; 00899 } 00900 00901 MachineInstr* PreAllocSplitting::FoldSpill(unsigned vreg, 00902 const TargetRegisterClass* RC, 00903 MachineInstr* DefMI, 00904 MachineInstr* Barrier, 00905 MachineBasicBlock* MBB, 00906 int& SS, 00907 SmallPtrSet<MachineInstr*, 4>& RefsInMBB) { 00908 MachineBasicBlock::iterator Pt = MBB->begin(); 00909 00910 // Go top down if RefsInMBB is empty. 00911 if (RefsInMBB.empty()) 00912 return 0; 00913 00914 MachineBasicBlock::iterator FoldPt = Barrier; 00915 while (&*FoldPt != DefMI && FoldPt != MBB->begin() && 00916 !RefsInMBB.count(FoldPt)) 00917 --FoldPt; 00918 00919 int OpIdx = FoldPt->findRegisterDefOperandIdx(vreg, false); 00920 if (OpIdx == -1) 00921 return 0; 00922 00923 SmallVector<unsigned, 1> Ops; 00924 Ops.push_back(OpIdx); 00925 00926 if (!TII->canFoldMemoryOperand(FoldPt, Ops)) 00927 return 0; 00928 00929 DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(vreg); 00930 if (I != IntervalSSMap.end()) { 00931 SS = I->second; 00932 } else { 00933 SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment()); 00934 } 00935 00936 MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), 00937 FoldPt, Ops, SS); 00938 00939 if (FMI) { 00940 LIs->ReplaceMachineInstrInMaps(FoldPt, FMI); 00941 FMI = MBB->insert(MBB->erase(FoldPt), FMI); 00942 ++NumFolds; 00943 00944 IntervalSSMap[vreg] = SS; 00945 CurrSLI = &LSs->getOrCreateInterval(SS, RC); 00946 if (CurrSLI->hasAtLeastOneValue()) 00947 CurrSValNo = CurrSLI->getValNumInfo(0); 00948 else 00949 CurrSValNo = CurrSLI->getNextValue(0, 0, false, LSs->getVNInfoAllocator()); 00950 } 00951 00952 return FMI; 00953 } 00954 00955 MachineInstr* PreAllocSplitting::FoldRestore(unsigned vreg, 00956 const TargetRegisterClass* RC, 00957 MachineInstr* Barrier, 00958 MachineBasicBlock* MBB, 00959 int SS, 00960 SmallPtrSet<MachineInstr*, 4>& RefsInMBB) { 00961 if ((int)RestoreFoldLimit != -1 && RestoreFoldLimit == (int)NumRestoreFolds) 00962 return 0; 00963 00964 // Go top down if RefsInMBB is empty. 00965 if (RefsInMBB.empty()) 00966 return 0; 00967 00968 // Can't fold a restore between a call stack setup and teardown. 00969 MachineBasicBlock::iterator FoldPt = Barrier; 00970 00971 // Advance from barrier to call frame teardown. 00972 while (FoldPt != MBB->getFirstTerminator() && 00973 FoldPt->getOpcode() != TRI->getCallFrameDestroyOpcode()) { 00974 if (RefsInMBB.count(FoldPt)) 00975 return 0; 00976 00977 ++FoldPt; 00978 } 00979 00980 if (FoldPt == MBB->getFirstTerminator()) 00981 return 0; 00982 else 00983 ++FoldPt; 00984 00985 // Now find the restore point. 00986 while (FoldPt != MBB->getFirstTerminator() && !RefsInMBB.count(FoldPt)) { 00987 if (FoldPt->getOpcode() == TRI->getCallFrameSetupOpcode()) { 00988 while (FoldPt != MBB->getFirstTerminator() && 00989 FoldPt->getOpcode() != TRI->getCallFrameDestroyOpcode()) { 00990 if (RefsInMBB.count(FoldPt)) 00991 return 0; 00992 00993 ++FoldPt; 00994 } 00995 00996 if (FoldPt == MBB->getFirstTerminator()) 00997 return 0; 00998 } 00999 01000 ++FoldPt; 01001 } 01002 01003 if (FoldPt == MBB->getFirstTerminator()) 01004 return 0; 01005 01006 int OpIdx = FoldPt->findRegisterUseOperandIdx(vreg, true); 01007 if (OpIdx == -1) 01008 return 0; 01009 01010 SmallVector<unsigned, 1> Ops; 01011 Ops.push_back(OpIdx); 01012 01013 if (!TII->canFoldMemoryOperand(FoldPt, Ops)) 01014 return 0; 01015 01016 MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(), 01017 FoldPt, Ops, SS); 01018 01019 if (FMI) { 01020 LIs->ReplaceMachineInstrInMaps(FoldPt, FMI); 01021 FMI = MBB->insert(MBB->erase(FoldPt), FMI); 01022 ++NumRestoreFolds; 01023 } 01024 01025 return FMI; 01026 } 01027 01028 /// SplitRegLiveInterval - Split (spill and restore) the given live interval 01029 /// so it would not cross the barrier that's being processed. Shrink wrap 01030 /// (minimize) the live interval to the last uses. 01031 bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) { 01032 CurrLI = LI; 01033 01034 // Find live range where current interval cross the barrier. 01035 LiveInterval::iterator LR = 01036 CurrLI->FindLiveRangeContaining(LIs->getUseIndex(BarrierIdx)); 01037 VNInfo *ValNo = LR->valno; 01038 01039 assert(!ValNo->isUnused() && "Val# is defined by a dead def?"); 01040 01041 MachineInstr *DefMI = ValNo->isDefAccurate() 01042 ? LIs->getInstructionFromIndex(ValNo->def) : NULL; 01043 01044 // If this would create a new join point, do not split. 01045 if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent())) 01046 return false; 01047 01048 // Find all references in the barrier mbb. 01049 SmallPtrSet<MachineInstr*, 4> RefsInMBB; 01050 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg), 01051 E = MRI->reg_end(); I != E; ++I) { 01052 MachineInstr *RefMI = &*I; 01053 if (RefMI->getParent() == BarrierMBB) 01054 RefsInMBB.insert(RefMI); 01055 } 01056 01057 // Find a point to restore the value after the barrier. 01058 unsigned RestoreIndex = 0; 01059 MachineBasicBlock::iterator RestorePt = 01060 findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex); 01061 if (RestorePt == BarrierMBB->end()) 01062 return false; 01063 01064 if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI)) 01065 if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt, 01066 RestoreIndex, RefsInMBB)) 01067 return true; 01068 01069 // Add a spill either before the barrier or after the definition. 01070 MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL; 01071 const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg); 01072 unsigned SpillIndex = 0; 01073 MachineInstr *SpillMI = NULL; 01074 int SS = -1; 01075 if (!ValNo->isDefAccurate()) { 01076 // If we don't know where the def is we must split just before the barrier. 01077 if ((SpillMI = FoldSpill(LI->reg, RC, 0, Barrier, 01078 BarrierMBB, SS, RefsInMBB))) { 01079 SpillIndex = LIs->getInstructionIndex(SpillMI); 01080 } else { 01081 MachineBasicBlock::iterator SpillPt = 01082 findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex); 01083 if (SpillPt == BarrierMBB->begin()) 01084 return false; // No gap to insert spill. 01085 // Add spill. 01086 01087 SS = CreateSpillStackSlot(CurrLI->reg, RC); 01088 TII->storeRegToStackSlot(*BarrierMBB, SpillPt, CurrLI->reg, true, SS, RC); 01089 SpillMI = prior(SpillPt); 01090 LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex); 01091 } 01092 } else if (!IsAvailableInStack(DefMBB, CurrLI->reg, ValNo->def, 01093 RestoreIndex, SpillIndex, SS)) { 01094 // If it's already split, just restore the value. There is no need to spill 01095 // the def again. 01096 if (!DefMI) 01097 return false; // Def is dead. Do nothing. 01098 01099 if ((SpillMI = FoldSpill(LI->reg, RC, DefMI, Barrier, 01100 BarrierMBB, SS, RefsInMBB))) { 01101 SpillIndex = LIs->getInstructionIndex(SpillMI); 01102 } else { 01103 // Check if it's possible to insert a spill after the def MI. 01104 MachineBasicBlock::iterator SpillPt; 01105 if (DefMBB == BarrierMBB) { 01106 // Add spill after the def and the last use before the barrier. 01107 SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI, 01108 RefsInMBB, SpillIndex); 01109 if (SpillPt == DefMBB->begin()) 01110 return false; // No gap to insert spill. 01111 } else { 01112 SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex); 01113 if (SpillPt == DefMBB->end()) 01114 return false; // No gap to insert spill. 01115 } 01116 // Add spill. The store instruction kills the register if def is before 01117 // the barrier in the barrier block. 01118 SS = CreateSpillStackSlot(CurrLI->reg, RC); 01119 TII->storeRegToStackSlot(*DefMBB, SpillPt, CurrLI->reg, 01120 DefMBB == BarrierMBB, SS, RC); 01121 SpillMI = prior(SpillPt); 01122 LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex); 01123 } 01124 } 01125 01126 // Remember def instruction index to spill index mapping. 01127 if (DefMI && SpillMI) 01128 Def2SpillMap[ValNo->def] = SpillIndex; 01129 01130 // Add restore. 01131 bool FoldedRestore = false; 01132 if (MachineInstr* LMI = FoldRestore(CurrLI->reg, RC, Barrier, 01133 BarrierMBB, SS, RefsInMBB)) { 01134 RestorePt = LMI; 01135 RestoreIndex = LIs->getInstructionIndex(RestorePt); 01136 FoldedRestore = true; 01137 } else { 01138 TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC); 01139 MachineInstr *LoadMI = prior(RestorePt); 01140 LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex); 01141 } 01142 01143 // Update spill stack slot live interval. 01144 UpdateSpillSlotInterval(ValNo, LIs->getUseIndex(SpillIndex)+1, 01145 LIs->getDefIndex(RestoreIndex)); 01146 01147 ReconstructLiveInterval(CurrLI); 01148 01149 if (!FoldedRestore) { 01150 unsigned RestoreIdx = LIs->getInstructionIndex(prior(RestorePt)); 01151 RestoreIdx = LiveIntervals::getDefIndex(RestoreIdx); 01152 RenumberValno(CurrLI->findDefinedVNInfo(RestoreIdx)); 01153 } 01154 01155 ++NumSplits; 01156 return true; 01157 } 01158 01159 /// SplitRegLiveIntervals - Split all register live intervals that cross the 01160 /// barrier that's being processed. 01161 bool 01162 PreAllocSplitting::SplitRegLiveIntervals(const TargetRegisterClass **RCs, 01163 SmallPtrSet<LiveInterval*, 8>& Split) { 01164 // First find all the virtual registers whose live intervals are intercepted 01165 // by the current barrier. 01166 SmallVector<LiveInterval*, 8> Intervals; 01167 for (const TargetRegisterClass **RC = RCs; *RC; ++RC) { 01168 // FIXME: If it's not safe to move any instruction that defines the barrier 01169 // register class, then it means there are some special dependencies which 01170 // codegen is not modelling. Ignore these barriers for now. 01171 if (!TII->isSafeToMoveRegClassDefs(*RC)) 01172 continue; 01173 std::vector<unsigned> &VRs = MRI->getRegClassVirtRegs(*RC); 01174 for (unsigned i = 0, e = VRs.size(); i != e; ++i) { 01175 unsigned Reg = VRs[i]; 01176 if (!LIs->hasInterval(Reg)) 01177 continue; 01178 LiveInterval *LI = &LIs->getInterval(Reg); 01179 if (LI->liveAt(BarrierIdx) && !Barrier->readsRegister(Reg)) 01180 // Virtual register live interval is intercepted by the barrier. We 01181 // should split and shrink wrap its interval if possible. 01182 Intervals.push_back(LI); 01183 } 01184 } 01185 01186 // Process the affected live intervals. 01187 bool Change = false; 01188 while (!Intervals.empty()) { 01189 if (PreSplitLimit != -1 && (int)NumSplits == PreSplitLimit) 01190 break; 01191 else if (NumSplits == 4) 01192 Change |= Change; 01193 LiveInterval *LI = Intervals.back(); 01194 Intervals.pop_back(); 01195 bool result = SplitRegLiveInterval(LI); 01196 if (result) Split.insert(LI); 01197 Change |= result; 01198 } 01199 01200 return Change; 01201 } 01202 01203 unsigned PreAllocSplitting::getNumberOfNonSpills( 01204 SmallPtrSet<MachineInstr*, 4>& MIs, 01205 unsigned Reg, int FrameIndex, 01206 bool& FeedsTwoAddr) { 01207 unsigned NonSpills = 0; 01208 for (SmallPtrSet<MachineInstr*, 4>::iterator UI = MIs.begin(), UE = MIs.end(); 01209 UI != UE; ++UI) { 01210 int StoreFrameIndex; 01211 unsigned StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); 01212 if (StoreVReg != Reg || StoreFrameIndex != FrameIndex) 01213 NonSpills++; 01214 01215 int DefIdx = (*UI)->findRegisterDefOperandIdx(Reg); 01216 if (DefIdx != -1 && (*UI)->isRegTiedToUseOperand(DefIdx)) 01217 FeedsTwoAddr = true; 01218 } 01219 01220 return NonSpills; 01221 } 01222 01223 /// removeDeadSpills - After doing splitting, filter through all intervals we've 01224 /// split, and see if any of the spills are unnecessary. If so, remove them. 01225 bool PreAllocSplitting::removeDeadSpills(SmallPtrSet<LiveInterval*, 8>& split) { 01226 bool changed = false; 01227 01228 // Walk over all of the live intervals that were touched by the splitter, 01229 // and see if we can do any DCE and/or folding. 01230 for (SmallPtrSet<LiveInterval*, 8>::iterator LI = split.begin(), 01231 LE = split.end(); LI != LE; ++LI) { 01232 DenseMap<VNInfo*, SmallPtrSet<MachineInstr*, 4> > VNUseCount; 01233 01234 // First, collect all the uses of the vreg, and sort them by their 01235 // reaching definition (VNInfo). 01236 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin((*LI)->reg), 01237 UE = MRI->use_end(); UI != UE; ++UI) { 01238 unsigned index = LIs->getInstructionIndex(&*UI); 01239 index = LiveIntervals::getUseIndex(index); 01240 01241 const LiveRange* LR = (*LI)->getLiveRangeContaining(index); 01242 VNUseCount[LR->valno].insert(&*UI); 01243 } 01244 01245 // Now, take the definitions (VNInfo's) one at a time and try to DCE 01246 // and/or fold them away. 01247 for (LiveInterval::vni_iterator VI = (*LI)->vni_begin(), 01248 VE = (*LI)->vni_end(); VI != VE; ++VI) { 01249 01250 if (DeadSplitLimit != -1 && (int)NumDeadSpills == DeadSplitLimit) 01251 return changed; 01252 01253 VNInfo* CurrVN = *VI; 01254 01255 // We don't currently try to handle definitions with PHI kills, because 01256 // it would involve processing more than one VNInfo at once. 01257 if (CurrVN->hasPHIKill()) continue; 01258 01259 // We also don't try to handle the results of PHI joins, since there's 01260 // no defining instruction to analyze. 01261 if (!CurrVN->isDefAccurate() || CurrVN->isUnused()) continue; 01262 01263 // We're only interested in eliminating cruft introduced by the splitter, 01264 // is of the form load-use or load-use-store. First, check that the 01265 // definition is a load, and remember what stack slot we loaded it from. 01266 MachineInstr* DefMI = LIs->getInstructionFromIndex(CurrVN->def); 01267 int FrameIndex; 01268 if (!TII->isLoadFromStackSlot(DefMI, FrameIndex)) continue; 01269 01270 // If the definition has no uses at all, just DCE it. 01271 if (VNUseCount[CurrVN].size() == 0) { 01272 LIs->RemoveMachineInstrFromMaps(DefMI); 01273 (*LI)->removeValNo(CurrVN); 01274 DefMI->eraseFromParent(); 01275 VNUseCount.erase(CurrVN); 01276 NumDeadSpills++; 01277 changed = true; 01278 continue; 01279 } 01280 01281 // Second, get the number of non-store uses of the definition, as well as 01282 // a flag indicating whether it feeds into a later two-address definition. 01283 bool FeedsTwoAddr = false; 01284 unsigned NonSpillCount = getNumberOfNonSpills(VNUseCount[CurrVN], 01285 (*LI)->reg, FrameIndex, 01286 FeedsTwoAddr); 01287 01288 // If there's one non-store use and it doesn't feed a two-addr, then 01289 // this is a load-use-store case that we can try to fold. 01290 if (NonSpillCount == 1 && !FeedsTwoAddr) { 01291 // Start by finding the non-store use MachineInstr. 01292 SmallPtrSet<MachineInstr*, 4>::iterator UI = VNUseCount[CurrVN].begin(); 01293 int StoreFrameIndex; 01294 unsigned StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); 01295 while (UI != VNUseCount[CurrVN].end() && 01296 (StoreVReg == (*LI)->reg && StoreFrameIndex == FrameIndex)) { 01297 ++UI; 01298 if (UI != VNUseCount[CurrVN].end()) 01299 StoreVReg = TII->isStoreToStackSlot(*UI, StoreFrameIndex); 01300 } 01301 if (UI == VNUseCount[CurrVN].end()) continue; 01302 01303 MachineInstr* use = *UI; 01304 01305 // Attempt to fold it away! 01306 int OpIdx = use->findRegisterUseOperandIdx((*LI)->reg, false); 01307 if (OpIdx == -1) continue; 01308 SmallVector<unsigned, 1> Ops; 01309 Ops.push_back(OpIdx); 01310 if (!TII->canFoldMemoryOperand(use, Ops)) continue; 01311 01312 MachineInstr* NewMI = 01313 TII->foldMemoryOperand(*use->getParent()->getParent(), 01314 use, Ops, FrameIndex); 01315 01316 if (!NewMI) continue; 01317 01318 // Update relevant analyses. 01319 LIs->RemoveMachineInstrFromMaps(DefMI); 01320 LIs->ReplaceMachineInstrInMaps(use, NewMI); 01321 (*LI)->removeValNo(CurrVN); 01322 01323 DefMI->eraseFromParent(); 01324 MachineBasicBlock* MBB = use->getParent(); 01325 NewMI = MBB->insert(MBB->erase(use), NewMI); 01326 VNUseCount[CurrVN].erase(use); 01327 01328 // Remove deleted instructions. Note that we need to remove them from 01329 // the VNInfo->use map as well, just to be safe. 01330 for (SmallPtrSet<MachineInstr*, 4>::iterator II = 01331 VNUseCount[CurrVN].begin(), IE = VNUseCount[CurrVN].end(); 01332 II != IE; ++II) { 01333 for (DenseMap<VNInfo*, SmallPtrSet<MachineInstr*, 4> >::iterator 01334 VNI = VNUseCount.begin(), VNE = VNUseCount.end(); VNI != VNE; 01335 ++VNI) 01336 if (VNI->first != CurrVN) 01337 VNI->second.erase(*II); 01338 LIs->RemoveMachineInstrFromMaps(*II); 01339 (*II)->eraseFromParent(); 01340 } 01341 01342 VNUseCount.erase(CurrVN); 01343 01344 for (DenseMap<VNInfo*, SmallPtrSet<MachineInstr*, 4> >::iterator 01345 VI = VNUseCount.begin(), VE = VNUseCount.end(); VI != VE; ++VI) 01346 if (VI->second.erase(use)) 01347 VI->second.insert(NewMI); 01348 01349 NumDeadSpills++; 01350 changed = true; 01351 continue; 01352 } 01353 01354 // If there's more than one non-store instruction, we can't profitably 01355 // fold it, so bail. 01356 if (NonSpillCount) continue; 01357 01358 // Otherwise, this is a load-store case, so DCE them. 01359 for (SmallPtrSet<MachineInstr*, 4>::iterator UI = 01360 VNUseCount[CurrVN].begin(), UE = VNUseCount[CurrVN].end(); 01361 UI != UI; ++UI) { 01362 LIs->RemoveMachineInstrFromMaps(*UI); 01363 (*UI)->eraseFromParent(); 01364 } 01365 01366 VNUseCount.erase(CurrVN); 01367 01368 LIs->RemoveMachineInstrFromMaps(DefMI); 01369 (*LI)->removeValNo(CurrVN); 01370 DefMI->eraseFromParent(); 01371 NumDeadSpills++; 01372 changed = true; 01373 } 01374 } 01375 01376 return changed; 01377 } 01378 01379 bool PreAllocSplitting::createsNewJoin(LiveRange* LR, 01380 MachineBasicBlock* DefMBB, 01381 MachineBasicBlock* BarrierMBB) { 01382 if (DefMBB == BarrierMBB) 01383 return false; 01384 01385 if (LR->valno->hasPHIKill()) 01386 return false; 01387 01388 unsigned MBBEnd = LIs->getMBBEndIdx(BarrierMBB); 01389 if (LR->end < MBBEnd) 01390 return false; 01391 01392 MachineLoopInfo& MLI = getAnalysis<MachineLoopInfo>(); 01393 if (MLI.getLoopFor(DefMBB) != MLI.getLoopFor(BarrierMBB)) 01394 return true; 01395 01396 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); 01397 SmallPtrSet<MachineBasicBlock*, 4> Visited; 01398 typedef std::pair<MachineBasicBlock*, 01399 MachineBasicBlock::succ_iterator> ItPair; 01400 SmallVector<ItPair, 4> Stack; 01401 Stack.push_back(std::make_pair(BarrierMBB, BarrierMBB->succ_begin())); 01402 01403 while (!Stack.empty()) { 01404 ItPair P = Stack.back(); 01405 Stack.pop_back(); 01406 01407 MachineBasicBlock* PredMBB = P.first; 01408 MachineBasicBlock::succ_iterator S = P.second; 01409 01410 if (S == PredMBB->succ_end()) 01411 continue; 01412 else if (Visited.count(*S)) { 01413 Stack.push_back(std::make_pair(PredMBB, ++S)); 01414 continue; 01415 } else 01416 Stack.push_back(std::make_pair(PredMBB, S+1)); 01417 01418 MachineBasicBlock* MBB = *S; 01419 Visited.insert(MBB); 01420 01421 if (MBB == BarrierMBB) 01422 return true; 01423 01424 MachineDomTreeNode* DefMDTN = MDT.getNode(DefMBB); 01425 MachineDomTreeNode* BarrierMDTN = MDT.getNode(BarrierMBB); 01426 MachineDomTreeNode* MDTN = MDT.getNode(MBB)->getIDom(); 01427 while (MDTN) { 01428 if (MDTN == DefMDTN) 01429 return true; 01430 else if (MDTN == BarrierMDTN) 01431 break; 01432 MDTN = MDTN->getIDom(); 01433 } 01434 01435 MBBEnd = LIs->getMBBEndIdx(MBB); 01436 if (LR->end > MBBEnd) 01437 Stack.push_back(std::make_pair(MBB, MBB->succ_begin())); 01438 } 01439 01440 return false; 01441 } 01442 01443 01444 bool PreAllocSplitting::runOnMachineFunction(MachineFunction &MF) { 01445 CurrMF = &MF; 01446 TM = &MF.getTarget(); 01447 TRI = TM->getRegisterInfo(); 01448 TII = TM->getInstrInfo(); 01449 MFI = MF.getFrameInfo(); 01450 MRI = &MF.getRegInfo(); 01451 LIs = &getAnalysis<LiveIntervals>(); 01452 LSs = &getAnalysis<LiveStacks>(); 01453 VRM = &getAnalysis<VirtRegMap>(); 01454 01455 bool MadeChange = false; 01456 01457 // Make sure blocks are numbered in order. 01458 MF.RenumberBlocks(); 01459 01460 MachineBasicBlock *Entry = MF.begin(); 01461 SmallPtrSet<MachineBasicBlock*,16> Visited; 01462 01463 SmallPtrSet<LiveInterval*, 8> Split; 01464 01465 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 01466 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 01467 DFI != E; ++DFI) { 01468 BarrierMBB = *DFI; 01469 for (MachineBasicBlock::iterator I = BarrierMBB->begin(), 01470 E = BarrierMBB->end(); I != E; ++I) { 01471 Barrier = &*I; 01472 const TargetRegisterClass **BarrierRCs = 01473 Barrier->getDesc().getRegClassBarriers(); 01474 if (!BarrierRCs) 01475 continue; 01476 BarrierIdx = LIs->getInstructionIndex(Barrier); 01477 MadeChange |= SplitRegLiveIntervals(BarrierRCs, Split); 01478 } 01479 } 01480 01481 MadeChange |= removeDeadSpills(Split); 01482 01483 return MadeChange; 01484 }