LiveIntervalAnalysis.cpp (199481) | LiveIntervalAnalysis.cpp (199511) |
---|---|
1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LiveInterval analysis pass which is used 11// by the Linear Scan Register allocator. This pass linearizes the 12// basic blocks of the function in DFS order and uses the 13// LiveVariables pass to conservatively compute live intervals for 14// each virtual and physical register. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "liveintervals" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "VirtRegMap.h" 21#include "llvm/Value.h" 22#include "llvm/Analysis/AliasAnalysis.h" 23#include "llvm/CodeGen/LiveVariables.h" 24#include "llvm/CodeGen/MachineFrameInfo.h" 25#include "llvm/CodeGen/MachineInstr.h" 26#include "llvm/CodeGen/MachineInstrBuilder.h" 27#include "llvm/CodeGen/MachineLoopInfo.h" 28#include "llvm/CodeGen/MachineMemOperand.h" 29#include "llvm/CodeGen/MachineRegisterInfo.h" 30#include "llvm/CodeGen/Passes.h" 31#include "llvm/CodeGen/ProcessImplicitDefs.h" 32#include "llvm/Target/TargetRegisterInfo.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/Target/TargetMachine.h" 35#include "llvm/Target/TargetOptions.h" 36#include "llvm/Support/CommandLine.h" 37#include "llvm/Support/Debug.h" 38#include "llvm/Support/ErrorHandling.h" 39#include "llvm/Support/raw_ostream.h" 40#include "llvm/ADT/DepthFirstIterator.h" 41#include "llvm/ADT/SmallSet.h" 42#include "llvm/ADT/Statistic.h" 43#include "llvm/ADT/STLExtras.h" 44#include <algorithm> 45#include <limits> 46#include <cmath> 47using namespace llvm; 48 49// Hidden options for help debugging. 50static cl::opt<bool> DisableReMat("disable-rematerialization", 51 cl::init(false), cl::Hidden); 52 53static cl::opt<bool> EnableFastSpilling("fast-spill", 54 cl::init(false), cl::Hidden); 55 | 1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LiveInterval analysis pass which is used 11// by the Linear Scan Register allocator. This pass linearizes the 12// basic blocks of the function in DFS order and uses the 13// LiveVariables pass to conservatively compute live intervals for 14// each virtual and physical register. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "liveintervals" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "VirtRegMap.h" 21#include "llvm/Value.h" 22#include "llvm/Analysis/AliasAnalysis.h" 23#include "llvm/CodeGen/LiveVariables.h" 24#include "llvm/CodeGen/MachineFrameInfo.h" 25#include "llvm/CodeGen/MachineInstr.h" 26#include "llvm/CodeGen/MachineInstrBuilder.h" 27#include "llvm/CodeGen/MachineLoopInfo.h" 28#include "llvm/CodeGen/MachineMemOperand.h" 29#include "llvm/CodeGen/MachineRegisterInfo.h" 30#include "llvm/CodeGen/Passes.h" 31#include "llvm/CodeGen/ProcessImplicitDefs.h" 32#include "llvm/Target/TargetRegisterInfo.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/Target/TargetMachine.h" 35#include "llvm/Target/TargetOptions.h" 36#include "llvm/Support/CommandLine.h" 37#include "llvm/Support/Debug.h" 38#include "llvm/Support/ErrorHandling.h" 39#include "llvm/Support/raw_ostream.h" 40#include "llvm/ADT/DepthFirstIterator.h" 41#include "llvm/ADT/SmallSet.h" 42#include "llvm/ADT/Statistic.h" 43#include "llvm/ADT/STLExtras.h" 44#include <algorithm> 45#include <limits> 46#include <cmath> 47using namespace llvm; 48 49// Hidden options for help debugging. 50static cl::opt<bool> DisableReMat("disable-rematerialization", 51 cl::init(false), cl::Hidden); 52 53static cl::opt<bool> EnableFastSpilling("fast-spill", 54 cl::init(false), cl::Hidden); 55 |
56static cl::opt<bool> EarlyCoalescing("early-coalescing", 57 cl::init(false), cl::Hidden); 58 59static cl::opt<int> CoalescingLimit("early-coalescing-limit", 60 cl::init(-1), cl::Hidden); 61 | |
62STATISTIC(numIntervals , "Number of original intervals"); 63STATISTIC(numFolds , "Number of loads/stores folded into instructions"); 64STATISTIC(numSplits , "Number of intervals split"); | 56STATISTIC(numIntervals , "Number of original intervals"); 57STATISTIC(numFolds , "Number of loads/stores folded into instructions"); 58STATISTIC(numSplits , "Number of intervals split"); |
65STATISTIC(numCoalescing, "Number of early coalescing performed"); | |
66 67char LiveIntervals::ID = 0; 68static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 69 70void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 71 AU.setPreservesCFG(); 72 AU.addRequired<AliasAnalysis>(); 73 AU.addPreserved<AliasAnalysis>(); 74 AU.addPreserved<LiveVariables>(); 75 AU.addRequired<LiveVariables>(); 76 AU.addPreservedID(MachineLoopInfoID); 77 AU.addPreservedID(MachineDominatorsID); 78 79 if (!StrongPHIElim) { 80 AU.addPreservedID(PHIEliminationID); 81 AU.addRequiredID(PHIEliminationID); 82 } 83 84 AU.addRequiredID(TwoAddressInstructionPassID); 85 AU.addPreserved<ProcessImplicitDefs>(); 86 AU.addRequired<ProcessImplicitDefs>(); 87 AU.addPreserved<SlotIndexes>(); 88 AU.addRequiredTransitive<SlotIndexes>(); 89 MachineFunctionPass::getAnalysisUsage(AU); 90} 91 92void LiveIntervals::releaseMemory() { 93 // Free the live intervals themselves. 94 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 95 E = r2iMap_.end(); I != E; ++I) 96 delete I->second; 97 98 r2iMap_.clear(); | 59 60char LiveIntervals::ID = 0; 61static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 62 63void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 64 AU.setPreservesCFG(); 65 AU.addRequired<AliasAnalysis>(); 66 AU.addPreserved<AliasAnalysis>(); 67 AU.addPreserved<LiveVariables>(); 68 AU.addRequired<LiveVariables>(); 69 AU.addPreservedID(MachineLoopInfoID); 70 AU.addPreservedID(MachineDominatorsID); 71 72 if (!StrongPHIElim) { 73 AU.addPreservedID(PHIEliminationID); 74 AU.addRequiredID(PHIEliminationID); 75 } 76 77 AU.addRequiredID(TwoAddressInstructionPassID); 78 AU.addPreserved<ProcessImplicitDefs>(); 79 AU.addRequired<ProcessImplicitDefs>(); 80 AU.addPreserved<SlotIndexes>(); 81 AU.addRequiredTransitive<SlotIndexes>(); 82 MachineFunctionPass::getAnalysisUsage(AU); 83} 84 85void LiveIntervals::releaseMemory() { 86 // Free the live intervals themselves. 87 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 88 E = r2iMap_.end(); I != E; ++I) 89 delete I->second; 90 91 r2iMap_.clear(); |
99 phiJoinCopies.clear(); | |
100 101 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 102 VNInfoAllocator.Reset(); 103 while (!CloneMIs.empty()) { 104 MachineInstr *MI = CloneMIs.back(); 105 CloneMIs.pop_back(); 106 mf_->DeleteMachineInstr(MI); 107 } 108} 109 110/// runOnMachineFunction - Register allocate the whole function 111/// 112bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 113 mf_ = &fn; 114 mri_ = &mf_->getRegInfo(); 115 tm_ = &fn.getTarget(); 116 tri_ = tm_->getRegisterInfo(); 117 tii_ = tm_->getInstrInfo(); 118 aa_ = &getAnalysis<AliasAnalysis>(); 119 lv_ = &getAnalysis<LiveVariables>(); 120 indexes_ = &getAnalysis<SlotIndexes>(); 121 allocatableRegs_ = tri_->getAllocatableSet(fn); 122 123 computeIntervals(); | 92 93 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 94 VNInfoAllocator.Reset(); 95 while (!CloneMIs.empty()) { 96 MachineInstr *MI = CloneMIs.back(); 97 CloneMIs.pop_back(); 98 mf_->DeleteMachineInstr(MI); 99 } 100} 101 102/// runOnMachineFunction - Register allocate the whole function 103/// 104bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 105 mf_ = &fn; 106 mri_ = &mf_->getRegInfo(); 107 tm_ = &fn.getTarget(); 108 tri_ = tm_->getRegisterInfo(); 109 tii_ = tm_->getInstrInfo(); 110 aa_ = &getAnalysis<AliasAnalysis>(); 111 lv_ = &getAnalysis<LiveVariables>(); 112 indexes_ = &getAnalysis<SlotIndexes>(); 113 allocatableRegs_ = tri_->getAllocatableSet(fn); 114 115 computeIntervals(); |
124 performEarlyCoalescing(); | |
125 126 numIntervals += getNumIntervals(); 127 128 DEBUG(dump()); 129 return true; 130} 131 132/// print - Implement the dump method. 133void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 134 OS << "********** INTERVALS **********\n"; 135 for (const_iterator I = begin(), E = end(); I != E; ++I) { 136 I->second->print(OS, tri_); 137 OS << "\n"; 138 } 139 140 printInstrs(OS); 141} 142 143void LiveIntervals::printInstrs(raw_ostream &OS) const { 144 OS << "********** MACHINEINSTRS **********\n"; 145 146 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 147 mbbi != mbbe; ++mbbi) { 148 OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 149 for (MachineBasicBlock::iterator mii = mbbi->begin(), 150 mie = mbbi->end(); mii != mie; ++mii) { 151 OS << getInstructionIndex(mii) << '\t' << *mii; 152 } 153 } 154} 155 156void LiveIntervals::dumpInstrs() const { 157 printInstrs(errs()); 158} 159 160/// conflictsWithPhysRegDef - Returns true if the specified register 161/// is defined during the duration of the specified interval. 162bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 163 VirtRegMap &vrm, unsigned reg) { 164 for (LiveInterval::Ranges::const_iterator 165 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 166 for (SlotIndex index = I->start.getBaseIndex(), 167 end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 168 index != end; 169 index = index.getNextIndex()) { 170 // skip deleted instructions 171 while (index != end && !getInstructionFromIndex(index)) 172 index = index.getNextIndex(); 173 if (index == end) break; 174 175 MachineInstr *MI = getInstructionFromIndex(index); 176 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 177 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 178 if (SrcReg == li.reg || DstReg == li.reg) 179 continue; 180 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 181 MachineOperand& mop = MI->getOperand(i); 182 if (!mop.isReg()) 183 continue; 184 unsigned PhysReg = mop.getReg(); 185 if (PhysReg == 0 || PhysReg == li.reg) 186 continue; 187 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 188 if (!vrm.hasPhys(PhysReg)) 189 continue; 190 PhysReg = vrm.getPhys(PhysReg); 191 } 192 if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 193 return true; 194 } 195 } 196 } 197 198 return false; 199} 200 201/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except 202/// it can check use as well. 203bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, 204 unsigned Reg, bool CheckUse, 205 SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 206 for (LiveInterval::Ranges::const_iterator 207 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 208 for (SlotIndex index = I->start.getBaseIndex(), 209 end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 210 index != end; 211 index = index.getNextIndex()) { 212 // Skip deleted instructions. 213 MachineInstr *MI = 0; 214 while (index != end) { 215 MI = getInstructionFromIndex(index); 216 if (MI) 217 break; 218 index = index.getNextIndex(); 219 } 220 if (index == end) break; 221 222 if (JoinedCopies.count(MI)) 223 continue; 224 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 225 MachineOperand& MO = MI->getOperand(i); 226 if (!MO.isReg()) 227 continue; 228 if (MO.isUse() && !CheckUse) 229 continue; 230 unsigned PhysReg = MO.getReg(); 231 if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 232 continue; 233 if (tri_->isSubRegister(Reg, PhysReg)) 234 return true; 235 } 236 } 237 } 238 239 return false; 240} 241 242#ifndef NDEBUG 243static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { 244 if (TargetRegisterInfo::isPhysicalRegister(reg)) 245 errs() << tri_->getName(reg); 246 else 247 errs() << "%reg" << reg; 248} 249#endif 250 251void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 252 MachineBasicBlock::iterator mi, 253 SlotIndex MIIdx, 254 MachineOperand& MO, 255 unsigned MOIdx, 256 LiveInterval &interval) { 257 DEBUG({ 258 errs() << "\t\tregister: "; 259 printRegName(interval.reg, tri_); 260 }); 261 262 // Virtual registers may be defined multiple times (due to phi 263 // elimination and 2-addr elimination). Much of what we do only has to be 264 // done once for the vreg. We use an empty interval to detect the first 265 // time we see a vreg. 266 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 267 if (interval.empty()) { 268 // Get the Idx of the defining instructions. 269 SlotIndex defIndex = MIIdx.getDefIndex(); 270 // Earlyclobbers move back one, so that they overlap the live range 271 // of inputs. 272 if (MO.isEarlyClobber()) 273 defIndex = MIIdx.getUseIndex(); 274 VNInfo *ValNo; 275 MachineInstr *CopyMI = NULL; 276 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 277 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 278 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 279 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 280 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 281 CopyMI = mi; 282 // Earlyclobbers move back one. 283 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 284 285 assert(ValNo->id == 0 && "First value in interval is not 0?"); 286 287 // Loop over all of the blocks that the vreg is defined in. There are 288 // two cases we have to handle here. The most common case is a vreg 289 // whose lifetime is contained within a basic block. In this case there 290 // will be a single kill, in MBB, which comes after the definition. 291 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 292 // FIXME: what about dead vars? 293 SlotIndex killIdx; 294 if (vi.Kills[0] != mi) 295 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 296 else 297 killIdx = defIndex.getStoreIndex(); 298 299 // If the kill happens after the definition, we have an intra-block 300 // live range. 301 if (killIdx > defIndex) { 302 assert(vi.AliveBlocks.empty() && 303 "Shouldn't be alive across any blocks!"); 304 LiveRange LR(defIndex, killIdx, ValNo); 305 interval.addRange(LR); 306 DEBUG(errs() << " +" << LR << "\n"); 307 ValNo->addKill(killIdx); 308 return; 309 } 310 } 311 312 // The other case we handle is when a virtual register lives to the end 313 // of the defining block, potentially live across some blocks, then is 314 // live into some number of blocks, but gets killed. Start by adding a 315 // range that goes from this definition to the end of the defining block. 316 LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(), 317 ValNo); 318 DEBUG(errs() << " +" << NewLR); 319 interval.addRange(NewLR); 320 321 // Iterate over all of the blocks that the variable is completely 322 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 323 // live interval. 324 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 325 E = vi.AliveBlocks.end(); I != E; ++I) { 326 LiveRange LR( 327 getMBBStartIdx(mf_->getBlockNumbered(*I)), 328 getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(), 329 ValNo); 330 interval.addRange(LR); 331 DEBUG(errs() << " +" << LR); 332 } 333 334 // Finally, this virtual register is live from the start of any killing 335 // block to the 'use' slot of the killing instruction. 336 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 337 MachineInstr *Kill = vi.Kills[i]; 338 SlotIndex killIdx = 339 getInstructionIndex(Kill).getDefIndex(); 340 LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); 341 interval.addRange(LR); 342 ValNo->addKill(killIdx); 343 DEBUG(errs() << " +" << LR); 344 } 345 346 } else { 347 // If this is the second time we see a virtual register definition, it 348 // must be due to phi elimination or two addr elimination. If this is 349 // the result of two address elimination, then the vreg is one of the 350 // def-and-use register operand. 351 if (mi->isRegTiedToUseOperand(MOIdx)) { 352 // If this is a two-address definition, then we have already processed 353 // the live range. The only problem is that we didn't realize there 354 // are actually two values in the live interval. Because of this we 355 // need to take the LiveRegion that defines this register and split it 356 // into two values. 357 assert(interval.containsOneValue()); 358 SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex(); 359 SlotIndex RedefIndex = MIIdx.getDefIndex(); 360 if (MO.isEarlyClobber()) 361 RedefIndex = MIIdx.getUseIndex(); 362 363 const LiveRange *OldLR = 364 interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 365 VNInfo *OldValNo = OldLR->valno; 366 367 // Delete the initial value, which should be short and continuous, 368 // because the 2-addr copy must be in the same MBB as the redef. 369 interval.removeRange(DefIndex, RedefIndex); 370 371 // Two-address vregs should always only be redefined once. This means 372 // that at this point, there should be exactly one value number in it. 373 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 374 375 // The new value number (#1) is defined by the instruction we claimed 376 // defined value #0. 377 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 378 false, // update at * 379 VNInfoAllocator); 380 ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 381 382 // Value#0 is now defined by the 2-addr instruction. 383 OldValNo->def = RedefIndex; 384 OldValNo->setCopy(0); 385 if (MO.isEarlyClobber()) 386 OldValNo->setHasRedefByEC(true); 387 388 // Add the new live interval which replaces the range for the input copy. 389 LiveRange LR(DefIndex, RedefIndex, ValNo); 390 DEBUG(errs() << " replace range with " << LR); 391 interval.addRange(LR); 392 ValNo->addKill(RedefIndex); 393 394 // If this redefinition is dead, we need to add a dummy unit live 395 // range covering the def slot. 396 if (MO.isDead()) 397 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 398 OldValNo)); 399 400 DEBUG({ 401 errs() << " RESULT: "; 402 interval.print(errs(), tri_); 403 }); 404 } else { 405 // Otherwise, this must be because of phi elimination. If this is the 406 // first redefinition of the vreg that we have seen, go back and change 407 // the live range in the PHI block to be a different value number. 408 if (interval.containsOneValue()) { 409 // Remove the old range that we now know has an incorrect number. 410 VNInfo *VNI = interval.getValNumInfo(0); 411 MachineInstr *Killer = vi.Kills[0]; | 116 117 numIntervals += getNumIntervals(); 118 119 DEBUG(dump()); 120 return true; 121} 122 123/// print - Implement the dump method. 124void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 125 OS << "********** INTERVALS **********\n"; 126 for (const_iterator I = begin(), E = end(); I != E; ++I) { 127 I->second->print(OS, tri_); 128 OS << "\n"; 129 } 130 131 printInstrs(OS); 132} 133 134void LiveIntervals::printInstrs(raw_ostream &OS) const { 135 OS << "********** MACHINEINSTRS **********\n"; 136 137 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 138 mbbi != mbbe; ++mbbi) { 139 OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 140 for (MachineBasicBlock::iterator mii = mbbi->begin(), 141 mie = mbbi->end(); mii != mie; ++mii) { 142 OS << getInstructionIndex(mii) << '\t' << *mii; 143 } 144 } 145} 146 147void LiveIntervals::dumpInstrs() const { 148 printInstrs(errs()); 149} 150 151/// conflictsWithPhysRegDef - Returns true if the specified register 152/// is defined during the duration of the specified interval. 153bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 154 VirtRegMap &vrm, unsigned reg) { 155 for (LiveInterval::Ranges::const_iterator 156 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 157 for (SlotIndex index = I->start.getBaseIndex(), 158 end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 159 index != end; 160 index = index.getNextIndex()) { 161 // skip deleted instructions 162 while (index != end && !getInstructionFromIndex(index)) 163 index = index.getNextIndex(); 164 if (index == end) break; 165 166 MachineInstr *MI = getInstructionFromIndex(index); 167 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 168 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 169 if (SrcReg == li.reg || DstReg == li.reg) 170 continue; 171 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 172 MachineOperand& mop = MI->getOperand(i); 173 if (!mop.isReg()) 174 continue; 175 unsigned PhysReg = mop.getReg(); 176 if (PhysReg == 0 || PhysReg == li.reg) 177 continue; 178 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 179 if (!vrm.hasPhys(PhysReg)) 180 continue; 181 PhysReg = vrm.getPhys(PhysReg); 182 } 183 if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 184 return true; 185 } 186 } 187 } 188 189 return false; 190} 191 192/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except 193/// it can check use as well. 194bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, 195 unsigned Reg, bool CheckUse, 196 SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 197 for (LiveInterval::Ranges::const_iterator 198 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 199 for (SlotIndex index = I->start.getBaseIndex(), 200 end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 201 index != end; 202 index = index.getNextIndex()) { 203 // Skip deleted instructions. 204 MachineInstr *MI = 0; 205 while (index != end) { 206 MI = getInstructionFromIndex(index); 207 if (MI) 208 break; 209 index = index.getNextIndex(); 210 } 211 if (index == end) break; 212 213 if (JoinedCopies.count(MI)) 214 continue; 215 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 216 MachineOperand& MO = MI->getOperand(i); 217 if (!MO.isReg()) 218 continue; 219 if (MO.isUse() && !CheckUse) 220 continue; 221 unsigned PhysReg = MO.getReg(); 222 if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 223 continue; 224 if (tri_->isSubRegister(Reg, PhysReg)) 225 return true; 226 } 227 } 228 } 229 230 return false; 231} 232 233#ifndef NDEBUG 234static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { 235 if (TargetRegisterInfo::isPhysicalRegister(reg)) 236 errs() << tri_->getName(reg); 237 else 238 errs() << "%reg" << reg; 239} 240#endif 241 242void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 243 MachineBasicBlock::iterator mi, 244 SlotIndex MIIdx, 245 MachineOperand& MO, 246 unsigned MOIdx, 247 LiveInterval &interval) { 248 DEBUG({ 249 errs() << "\t\tregister: "; 250 printRegName(interval.reg, tri_); 251 }); 252 253 // Virtual registers may be defined multiple times (due to phi 254 // elimination and 2-addr elimination). Much of what we do only has to be 255 // done once for the vreg. We use an empty interval to detect the first 256 // time we see a vreg. 257 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 258 if (interval.empty()) { 259 // Get the Idx of the defining instructions. 260 SlotIndex defIndex = MIIdx.getDefIndex(); 261 // Earlyclobbers move back one, so that they overlap the live range 262 // of inputs. 263 if (MO.isEarlyClobber()) 264 defIndex = MIIdx.getUseIndex(); 265 VNInfo *ValNo; 266 MachineInstr *CopyMI = NULL; 267 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 268 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 269 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 270 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 271 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 272 CopyMI = mi; 273 // Earlyclobbers move back one. 274 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 275 276 assert(ValNo->id == 0 && "First value in interval is not 0?"); 277 278 // Loop over all of the blocks that the vreg is defined in. There are 279 // two cases we have to handle here. The most common case is a vreg 280 // whose lifetime is contained within a basic block. In this case there 281 // will be a single kill, in MBB, which comes after the definition. 282 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 283 // FIXME: what about dead vars? 284 SlotIndex killIdx; 285 if (vi.Kills[0] != mi) 286 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex(); 287 else 288 killIdx = defIndex.getStoreIndex(); 289 290 // If the kill happens after the definition, we have an intra-block 291 // live range. 292 if (killIdx > defIndex) { 293 assert(vi.AliveBlocks.empty() && 294 "Shouldn't be alive across any blocks!"); 295 LiveRange LR(defIndex, killIdx, ValNo); 296 interval.addRange(LR); 297 DEBUG(errs() << " +" << LR << "\n"); 298 ValNo->addKill(killIdx); 299 return; 300 } 301 } 302 303 // The other case we handle is when a virtual register lives to the end 304 // of the defining block, potentially live across some blocks, then is 305 // live into some number of blocks, but gets killed. Start by adding a 306 // range that goes from this definition to the end of the defining block. 307 LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(), 308 ValNo); 309 DEBUG(errs() << " +" << NewLR); 310 interval.addRange(NewLR); 311 312 // Iterate over all of the blocks that the variable is completely 313 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 314 // live interval. 315 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 316 E = vi.AliveBlocks.end(); I != E; ++I) { 317 LiveRange LR( 318 getMBBStartIdx(mf_->getBlockNumbered(*I)), 319 getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(), 320 ValNo); 321 interval.addRange(LR); 322 DEBUG(errs() << " +" << LR); 323 } 324 325 // Finally, this virtual register is live from the start of any killing 326 // block to the 'use' slot of the killing instruction. 327 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 328 MachineInstr *Kill = vi.Kills[i]; 329 SlotIndex killIdx = 330 getInstructionIndex(Kill).getDefIndex(); 331 LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); 332 interval.addRange(LR); 333 ValNo->addKill(killIdx); 334 DEBUG(errs() << " +" << LR); 335 } 336 337 } else { 338 // If this is the second time we see a virtual register definition, it 339 // must be due to phi elimination or two addr elimination. If this is 340 // the result of two address elimination, then the vreg is one of the 341 // def-and-use register operand. 342 if (mi->isRegTiedToUseOperand(MOIdx)) { 343 // If this is a two-address definition, then we have already processed 344 // the live range. The only problem is that we didn't realize there 345 // are actually two values in the live interval. Because of this we 346 // need to take the LiveRegion that defines this register and split it 347 // into two values. 348 assert(interval.containsOneValue()); 349 SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex(); 350 SlotIndex RedefIndex = MIIdx.getDefIndex(); 351 if (MO.isEarlyClobber()) 352 RedefIndex = MIIdx.getUseIndex(); 353 354 const LiveRange *OldLR = 355 interval.getLiveRangeContaining(RedefIndex.getUseIndex()); 356 VNInfo *OldValNo = OldLR->valno; 357 358 // Delete the initial value, which should be short and continuous, 359 // because the 2-addr copy must be in the same MBB as the redef. 360 interval.removeRange(DefIndex, RedefIndex); 361 362 // Two-address vregs should always only be redefined once. This means 363 // that at this point, there should be exactly one value number in it. 364 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 365 366 // The new value number (#1) is defined by the instruction we claimed 367 // defined value #0. 368 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 369 false, // update at * 370 VNInfoAllocator); 371 ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 372 373 // Value#0 is now defined by the 2-addr instruction. 374 OldValNo->def = RedefIndex; 375 OldValNo->setCopy(0); 376 if (MO.isEarlyClobber()) 377 OldValNo->setHasRedefByEC(true); 378 379 // Add the new live interval which replaces the range for the input copy. 380 LiveRange LR(DefIndex, RedefIndex, ValNo); 381 DEBUG(errs() << " replace range with " << LR); 382 interval.addRange(LR); 383 ValNo->addKill(RedefIndex); 384 385 // If this redefinition is dead, we need to add a dummy unit live 386 // range covering the def slot. 387 if (MO.isDead()) 388 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(), 389 OldValNo)); 390 391 DEBUG({ 392 errs() << " RESULT: "; 393 interval.print(errs(), tri_); 394 }); 395 } else { 396 // Otherwise, this must be because of phi elimination. If this is the 397 // first redefinition of the vreg that we have seen, go back and change 398 // the live range in the PHI block to be a different value number. 399 if (interval.containsOneValue()) { 400 // Remove the old range that we now know has an incorrect number. 401 VNInfo *VNI = interval.getValNumInfo(0); 402 MachineInstr *Killer = vi.Kills[0]; |
412 phiJoinCopies.push_back(Killer); | |
413 SlotIndex Start = getMBBStartIdx(Killer->getParent()); 414 SlotIndex End = getInstructionIndex(Killer).getDefIndex(); 415 DEBUG({ 416 errs() << " Removing [" << Start << "," << End << "] from: "; 417 interval.print(errs(), tri_); 418 errs() << "\n"; 419 }); 420 interval.removeRange(Start, End); 421 assert(interval.ranges.size() == 1 && 422 "Newly discovered PHI interval has >1 ranges."); 423 MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); 424 VNI->addKill(indexes_->getTerminatorGap(killMBB)); 425 VNI->setHasPHIKill(true); 426 DEBUG({ 427 errs() << " RESULT: "; 428 interval.print(errs(), tri_); 429 }); 430 431 // Replace the interval with one of a NEW value number. Note that this 432 // value number isn't actually defined by an instruction, weird huh? :) 433 LiveRange LR(Start, End, 434 interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true), 435 0, false, VNInfoAllocator)); 436 LR.valno->setIsPHIDef(true); 437 DEBUG(errs() << " replace range with " << LR); 438 interval.addRange(LR); 439 LR.valno->addKill(End); 440 DEBUG({ 441 errs() << " RESULT: "; 442 interval.print(errs(), tri_); 443 }); 444 } 445 446 // In the case of PHI elimination, each variable definition is only 447 // live until the end of the block. We've already taken care of the 448 // rest of the live range. 449 SlotIndex defIndex = MIIdx.getDefIndex(); 450 if (MO.isEarlyClobber()) 451 defIndex = MIIdx.getUseIndex(); 452 453 VNInfo *ValNo; 454 MachineInstr *CopyMI = NULL; 455 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 456 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 457 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 458 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 459 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 460 CopyMI = mi; 461 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 462 463 SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex(); 464 LiveRange LR(defIndex, killIndex, ValNo); 465 interval.addRange(LR); 466 ValNo->addKill(indexes_->getTerminatorGap(mbb)); 467 ValNo->setHasPHIKill(true); 468 DEBUG(errs() << " +" << LR); 469 } 470 } 471 472 DEBUG(errs() << '\n'); 473} 474 475void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 476 MachineBasicBlock::iterator mi, 477 SlotIndex MIIdx, 478 MachineOperand& MO, 479 LiveInterval &interval, 480 MachineInstr *CopyMI) { 481 // A physical register cannot be live across basic block, so its 482 // lifetime must end somewhere in its defining basic block. 483 DEBUG({ 484 errs() << "\t\tregister: "; 485 printRegName(interval.reg, tri_); 486 }); 487 488 SlotIndex baseIndex = MIIdx; 489 SlotIndex start = baseIndex.getDefIndex(); 490 // Earlyclobbers move back one. 491 if (MO.isEarlyClobber()) 492 start = MIIdx.getUseIndex(); 493 SlotIndex end = start; 494 495 // If it is not used after definition, it is considered dead at 496 // the instruction defining it. Hence its interval is: 497 // [defSlot(def), defSlot(def)+1) 498 // For earlyclobbers, the defSlot was pushed back one; the extra 499 // advance below compensates. 500 if (MO.isDead()) { 501 DEBUG(errs() << " dead"); 502 end = start.getStoreIndex(); 503 goto exit; 504 } 505 506 // If it is not dead on definition, it must be killed by a 507 // subsequent instruction. Hence its interval is: 508 // [defSlot(def), useSlot(kill)+1) 509 baseIndex = baseIndex.getNextIndex(); 510 while (++mi != MBB->end()) { 511 512 if (getInstructionFromIndex(baseIndex) == 0) 513 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 514 515 if (mi->killsRegister(interval.reg, tri_)) { 516 DEBUG(errs() << " killed"); 517 end = baseIndex.getDefIndex(); 518 goto exit; 519 } else { 520 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 521 if (DefIdx != -1) { 522 if (mi->isRegTiedToUseOperand(DefIdx)) { 523 // Two-address instruction. 524 end = baseIndex.getDefIndex(); 525 assert(!mi->getOperand(DefIdx).isEarlyClobber() && 526 "Two address instruction is an early clobber?"); 527 } else { 528 // Another instruction redefines the register before it is ever read. 529 // Then the register is essentially dead at the instruction that defines 530 // it. Hence its interval is: 531 // [defSlot(def), defSlot(def)+1) 532 DEBUG(errs() << " dead"); 533 end = start.getStoreIndex(); 534 } 535 goto exit; 536 } 537 } 538 539 baseIndex = baseIndex.getNextIndex(); 540 } 541 542 // The only case we should have a dead physreg here without a killing or 543 // instruction where we know it's dead is if it is live-in to the function 544 // and never used. Another possible case is the implicit use of the 545 // physical register has been deleted by two-address pass. 546 end = start.getStoreIndex(); 547 548exit: 549 assert(start < end && "did not find end of interval?"); 550 551 // Already exists? Extend old live interval. 552 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 553 bool Extend = OldLR != interval.end(); 554 VNInfo *ValNo = Extend 555 ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 556 if (MO.isEarlyClobber() && Extend) 557 ValNo->setHasRedefByEC(true); 558 LiveRange LR(start, end, ValNo); 559 interval.addRange(LR); 560 LR.valno->addKill(end); 561 DEBUG(errs() << " +" << LR << '\n'); 562} 563 564void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 565 MachineBasicBlock::iterator MI, 566 SlotIndex MIIdx, 567 MachineOperand& MO, 568 unsigned MOIdx) { 569 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 570 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 571 getOrCreateInterval(MO.getReg())); 572 else if (allocatableRegs_[MO.getReg()]) { 573 MachineInstr *CopyMI = NULL; 574 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 575 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 576 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 577 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 578 tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 579 CopyMI = MI; 580 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 581 getOrCreateInterval(MO.getReg()), CopyMI); 582 // Def of a register also defines its sub-registers. 583 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 584 // If MI also modifies the sub-register explicitly, avoid processing it 585 // more than once. Do not pass in TRI here so it checks for exact match. 586 if (!MI->modifiesRegister(*AS)) 587 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 588 getOrCreateInterval(*AS), 0); 589 } 590} 591 592void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 593 SlotIndex MIIdx, 594 LiveInterval &interval, bool isAlias) { 595 DEBUG({ 596 errs() << "\t\tlivein register: "; 597 printRegName(interval.reg, tri_); 598 }); 599 600 // Look for kills, if it reaches a def before it's killed, then it shouldn't 601 // be considered a livein. 602 MachineBasicBlock::iterator mi = MBB->begin(); 603 SlotIndex baseIndex = MIIdx; 604 SlotIndex start = baseIndex; 605 if (getInstructionFromIndex(baseIndex) == 0) 606 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 607 608 SlotIndex end = baseIndex; 609 bool SeenDefUse = false; 610 611 while (mi != MBB->end()) { 612 if (mi->killsRegister(interval.reg, tri_)) { 613 DEBUG(errs() << " killed"); 614 end = baseIndex.getDefIndex(); 615 SeenDefUse = true; 616 break; 617 } else if (mi->modifiesRegister(interval.reg, tri_)) { 618 // Another instruction redefines the register before it is ever read. 619 // Then the register is essentially dead at the instruction that defines 620 // it. Hence its interval is: 621 // [defSlot(def), defSlot(def)+1) 622 DEBUG(errs() << " dead"); 623 end = start.getStoreIndex(); 624 SeenDefUse = true; 625 break; 626 } 627 628 ++mi; 629 if (mi != MBB->end()) { 630 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 631 } 632 } 633 634 // Live-in register might not be used at all. 635 if (!SeenDefUse) { 636 if (isAlias) { 637 DEBUG(errs() << " dead"); 638 end = MIIdx.getStoreIndex(); 639 } else { 640 DEBUG(errs() << " live through"); 641 end = baseIndex; 642 } 643 } 644 645 VNInfo *vni = 646 interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), 647 0, false, VNInfoAllocator); 648 vni->setIsPHIDef(true); 649 LiveRange LR(start, end, vni); 650 651 interval.addRange(LR); 652 LR.valno->addKill(end); 653 DEBUG(errs() << " +" << LR << '\n'); 654} 655 | 403 SlotIndex Start = getMBBStartIdx(Killer->getParent()); 404 SlotIndex End = getInstructionIndex(Killer).getDefIndex(); 405 DEBUG({ 406 errs() << " Removing [" << Start << "," << End << "] from: "; 407 interval.print(errs(), tri_); 408 errs() << "\n"; 409 }); 410 interval.removeRange(Start, End); 411 assert(interval.ranges.size() == 1 && 412 "Newly discovered PHI interval has >1 ranges."); 413 MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); 414 VNI->addKill(indexes_->getTerminatorGap(killMBB)); 415 VNI->setHasPHIKill(true); 416 DEBUG({ 417 errs() << " RESULT: "; 418 interval.print(errs(), tri_); 419 }); 420 421 // Replace the interval with one of a NEW value number. Note that this 422 // value number isn't actually defined by an instruction, weird huh? :) 423 LiveRange LR(Start, End, 424 interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true), 425 0, false, VNInfoAllocator)); 426 LR.valno->setIsPHIDef(true); 427 DEBUG(errs() << " replace range with " << LR); 428 interval.addRange(LR); 429 LR.valno->addKill(End); 430 DEBUG({ 431 errs() << " RESULT: "; 432 interval.print(errs(), tri_); 433 }); 434 } 435 436 // In the case of PHI elimination, each variable definition is only 437 // live until the end of the block. We've already taken care of the 438 // rest of the live range. 439 SlotIndex defIndex = MIIdx.getDefIndex(); 440 if (MO.isEarlyClobber()) 441 defIndex = MIIdx.getUseIndex(); 442 443 VNInfo *ValNo; 444 MachineInstr *CopyMI = NULL; 445 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 446 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 447 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 448 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 449 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 450 CopyMI = mi; 451 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 452 453 SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex(); 454 LiveRange LR(defIndex, killIndex, ValNo); 455 interval.addRange(LR); 456 ValNo->addKill(indexes_->getTerminatorGap(mbb)); 457 ValNo->setHasPHIKill(true); 458 DEBUG(errs() << " +" << LR); 459 } 460 } 461 462 DEBUG(errs() << '\n'); 463} 464 465void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 466 MachineBasicBlock::iterator mi, 467 SlotIndex MIIdx, 468 MachineOperand& MO, 469 LiveInterval &interval, 470 MachineInstr *CopyMI) { 471 // A physical register cannot be live across basic block, so its 472 // lifetime must end somewhere in its defining basic block. 473 DEBUG({ 474 errs() << "\t\tregister: "; 475 printRegName(interval.reg, tri_); 476 }); 477 478 SlotIndex baseIndex = MIIdx; 479 SlotIndex start = baseIndex.getDefIndex(); 480 // Earlyclobbers move back one. 481 if (MO.isEarlyClobber()) 482 start = MIIdx.getUseIndex(); 483 SlotIndex end = start; 484 485 // If it is not used after definition, it is considered dead at 486 // the instruction defining it. Hence its interval is: 487 // [defSlot(def), defSlot(def)+1) 488 // For earlyclobbers, the defSlot was pushed back one; the extra 489 // advance below compensates. 490 if (MO.isDead()) { 491 DEBUG(errs() << " dead"); 492 end = start.getStoreIndex(); 493 goto exit; 494 } 495 496 // If it is not dead on definition, it must be killed by a 497 // subsequent instruction. Hence its interval is: 498 // [defSlot(def), useSlot(kill)+1) 499 baseIndex = baseIndex.getNextIndex(); 500 while (++mi != MBB->end()) { 501 502 if (getInstructionFromIndex(baseIndex) == 0) 503 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 504 505 if (mi->killsRegister(interval.reg, tri_)) { 506 DEBUG(errs() << " killed"); 507 end = baseIndex.getDefIndex(); 508 goto exit; 509 } else { 510 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 511 if (DefIdx != -1) { 512 if (mi->isRegTiedToUseOperand(DefIdx)) { 513 // Two-address instruction. 514 end = baseIndex.getDefIndex(); 515 assert(!mi->getOperand(DefIdx).isEarlyClobber() && 516 "Two address instruction is an early clobber?"); 517 } else { 518 // Another instruction redefines the register before it is ever read. 519 // Then the register is essentially dead at the instruction that defines 520 // it. Hence its interval is: 521 // [defSlot(def), defSlot(def)+1) 522 DEBUG(errs() << " dead"); 523 end = start.getStoreIndex(); 524 } 525 goto exit; 526 } 527 } 528 529 baseIndex = baseIndex.getNextIndex(); 530 } 531 532 // The only case we should have a dead physreg here without a killing or 533 // instruction where we know it's dead is if it is live-in to the function 534 // and never used. Another possible case is the implicit use of the 535 // physical register has been deleted by two-address pass. 536 end = start.getStoreIndex(); 537 538exit: 539 assert(start < end && "did not find end of interval?"); 540 541 // Already exists? Extend old live interval. 542 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 543 bool Extend = OldLR != interval.end(); 544 VNInfo *ValNo = Extend 545 ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 546 if (MO.isEarlyClobber() && Extend) 547 ValNo->setHasRedefByEC(true); 548 LiveRange LR(start, end, ValNo); 549 interval.addRange(LR); 550 LR.valno->addKill(end); 551 DEBUG(errs() << " +" << LR << '\n'); 552} 553 554void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 555 MachineBasicBlock::iterator MI, 556 SlotIndex MIIdx, 557 MachineOperand& MO, 558 unsigned MOIdx) { 559 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 560 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 561 getOrCreateInterval(MO.getReg())); 562 else if (allocatableRegs_[MO.getReg()]) { 563 MachineInstr *CopyMI = NULL; 564 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 565 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 566 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 567 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 568 tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 569 CopyMI = MI; 570 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 571 getOrCreateInterval(MO.getReg()), CopyMI); 572 // Def of a register also defines its sub-registers. 573 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 574 // If MI also modifies the sub-register explicitly, avoid processing it 575 // more than once. Do not pass in TRI here so it checks for exact match. 576 if (!MI->modifiesRegister(*AS)) 577 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 578 getOrCreateInterval(*AS), 0); 579 } 580} 581 582void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 583 SlotIndex MIIdx, 584 LiveInterval &interval, bool isAlias) { 585 DEBUG({ 586 errs() << "\t\tlivein register: "; 587 printRegName(interval.reg, tri_); 588 }); 589 590 // Look for kills, if it reaches a def before it's killed, then it shouldn't 591 // be considered a livein. 592 MachineBasicBlock::iterator mi = MBB->begin(); 593 SlotIndex baseIndex = MIIdx; 594 SlotIndex start = baseIndex; 595 if (getInstructionFromIndex(baseIndex) == 0) 596 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 597 598 SlotIndex end = baseIndex; 599 bool SeenDefUse = false; 600 601 while (mi != MBB->end()) { 602 if (mi->killsRegister(interval.reg, tri_)) { 603 DEBUG(errs() << " killed"); 604 end = baseIndex.getDefIndex(); 605 SeenDefUse = true; 606 break; 607 } else if (mi->modifiesRegister(interval.reg, tri_)) { 608 // Another instruction redefines the register before it is ever read. 609 // Then the register is essentially dead at the instruction that defines 610 // it. Hence its interval is: 611 // [defSlot(def), defSlot(def)+1) 612 DEBUG(errs() << " dead"); 613 end = start.getStoreIndex(); 614 SeenDefUse = true; 615 break; 616 } 617 618 ++mi; 619 if (mi != MBB->end()) { 620 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 621 } 622 } 623 624 // Live-in register might not be used at all. 625 if (!SeenDefUse) { 626 if (isAlias) { 627 DEBUG(errs() << " dead"); 628 end = MIIdx.getStoreIndex(); 629 } else { 630 DEBUG(errs() << " live through"); 631 end = baseIndex; 632 } 633 } 634 635 VNInfo *vni = 636 interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), 637 0, false, VNInfoAllocator); 638 vni->setIsPHIDef(true); 639 LiveRange LR(start, end, vni); 640 641 interval.addRange(LR); 642 LR.valno->addKill(end); 643 DEBUG(errs() << " +" << LR << '\n'); 644} 645 |
656bool LiveIntervals:: 657isSafeAndProfitableToCoalesce(LiveInterval &DstInt, 658 LiveInterval &SrcInt, 659 SmallVector<MachineInstr*,16> &IdentCopies, 660 SmallVector<MachineInstr*,16> &OtherCopies) { 661 unsigned NumIdent = 0; 662 for (MachineRegisterInfo::def_iterator ri = mri_->def_begin(SrcInt.reg), 663 re = mri_->def_end(); ri != re; ++ri) { 664 MachineInstr *MI = &*ri; 665 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 666 if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 667 return false; 668 if (SrcReg != DstInt.reg) { 669 // Non-identity copy - we cannot handle overlapping intervals 670 if (DstInt.liveAt(getInstructionIndex(MI))) 671 return false; 672 OtherCopies.push_back(MI); 673 } else { 674 IdentCopies.push_back(MI); 675 ++NumIdent; 676 } 677 } 678 679 return IdentCopies.size() > OtherCopies.size(); 680} 681 682void LiveIntervals::performEarlyCoalescing() { 683 if (!EarlyCoalescing) 684 return; 685 686 /// Perform early coalescing: eliminate copies which feed into phi joins 687 /// and whose sources are defined by the phi joins. 688 for (unsigned i = 0, e = phiJoinCopies.size(); i != e; ++i) { 689 MachineInstr *Join = phiJoinCopies[i]; 690 if (CoalescingLimit != -1 && (int)numCoalescing == CoalescingLimit) 691 break; 692 693 unsigned PHISrc, PHIDst, SrcSubReg, DstSubReg; 694 bool isMove= tii_->isMoveInstr(*Join, PHISrc, PHIDst, SrcSubReg, DstSubReg); 695#ifndef NDEBUG 696 assert(isMove && "PHI join instruction must be a move!"); 697#else 698 isMove = isMove; 699#endif 700 701 LiveInterval &DstInt = getInterval(PHIDst); 702 LiveInterval &SrcInt = getInterval(PHISrc); 703 SmallVector<MachineInstr*, 16> IdentCopies; 704 SmallVector<MachineInstr*, 16> OtherCopies; 705 if (!isSafeAndProfitableToCoalesce(DstInt, SrcInt, 706 IdentCopies, OtherCopies)) 707 continue; 708 709 DEBUG(errs() << "PHI Join: " << *Join); 710 assert(DstInt.containsOneValue() && "PHI join should have just one val#!"); 711 assert(std::distance(mri_->use_begin(PHISrc), mri_->use_end()) == 1 && 712 "PHI join src should not be used elsewhere"); 713 VNInfo *VNI = DstInt.getValNumInfo(0); 714 715 // Change the non-identity copies to directly target the phi destination. 716 for (unsigned i = 0, e = OtherCopies.size(); i != e; ++i) { 717 MachineInstr *PHICopy = OtherCopies[i]; 718 SlotIndex MIIndex = getInstructionIndex(PHICopy); 719 DEBUG(errs() << "Moving: " << MIIndex << ' ' << *PHICopy); 720 SlotIndex DefIndex = MIIndex.getDefIndex(); 721 LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); 722 SlotIndex StartIndex = SLR->start; 723 SlotIndex EndIndex = SLR->end; 724 725 // Delete val# defined by the now identity copy and add the range from 726 // beginning of the mbb to the end of the range. 727 SrcInt.removeValNo(SLR->valno); 728 DEBUG(errs() << " added range [" << StartIndex << ',' 729 << EndIndex << "] to reg" << DstInt.reg << '\n'); 730 assert (!DstInt.liveAt(StartIndex) && "Cannot coalesce when dst live!"); 731 VNInfo *NewVNI = DstInt.getNextValue(DefIndex, PHICopy, true, 732 VNInfoAllocator); 733 NewVNI->setHasPHIKill(true); 734 DstInt.addRange(LiveRange(StartIndex, EndIndex, NewVNI)); 735 for (unsigned j = 0, ee = PHICopy->getNumOperands(); j != ee; ++j) { 736 MachineOperand &MO = PHICopy->getOperand(j); 737 if (!MO.isReg() || MO.getReg() != PHISrc) 738 continue; 739 MO.setReg(PHIDst); 740 } 741 } 742 743 // Now let's eliminate all the would-be identity copies. 744 for (unsigned i = 0, e = IdentCopies.size(); i != e; ++i) { 745 MachineInstr *PHICopy = IdentCopies[i]; 746 DEBUG(errs() << "Coalescing: " << *PHICopy); 747 748 SlotIndex MIIndex = getInstructionIndex(PHICopy); 749 SlotIndex DefIndex = MIIndex.getDefIndex(); 750 LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); 751 SlotIndex StartIndex = SLR->start; 752 SlotIndex EndIndex = SLR->end; 753 754 // Delete val# defined by the now identity copy and add the range from 755 // beginning of the mbb to the end of the range. 756 SrcInt.removeValNo(SLR->valno); 757 RemoveMachineInstrFromMaps(PHICopy); 758 PHICopy->eraseFromParent(); 759 DEBUG(errs() << " added range [" << StartIndex << ',' 760 << EndIndex << "] to reg" << DstInt.reg << '\n'); 761 DstInt.addRange(LiveRange(StartIndex, EndIndex, VNI)); 762 } 763 764 // Remove the phi join and update the phi block liveness. 765 SlotIndex MIIndex = getInstructionIndex(Join); 766 SlotIndex UseIndex = MIIndex.getUseIndex(); 767 SlotIndex DefIndex = MIIndex.getDefIndex(); 768 LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex); 769 LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex); 770 DLR->valno->setCopy(0); 771 DLR->valno->setIsDefAccurate(false); 772 DstInt.addRange(LiveRange(SLR->start, SLR->end, DLR->valno)); 773 SrcInt.removeRange(SLR->start, SLR->end); 774 assert(SrcInt.empty()); 775 removeInterval(PHISrc); 776 RemoveMachineInstrFromMaps(Join); 777 Join->eraseFromParent(); 778 779 ++numCoalescing; 780 } 781} 782 | |
783/// computeIntervals - computes the live intervals for virtual 784/// registers. for some ordering of the machine instructions [1,N] a 785/// live interval is an interval [i, j) where 1 <= i <= j < N for 786/// which a variable is live 787void LiveIntervals::computeIntervals() { 788 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" 789 << "********** Function: " 790 << ((Value*)mf_->getFunction())->getName() << '\n'); 791 792 SmallVector<unsigned, 8> UndefUses; 793 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 794 MBBI != E; ++MBBI) { 795 MachineBasicBlock *MBB = MBBI; 796 // Track the index of the current machine instr. 797 SlotIndex MIIndex = getMBBStartIdx(MBB); 798 DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 799 800 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 801 802 // Create intervals for live-ins to this BB first. 803 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 804 LE = MBB->livein_end(); LI != LE; ++LI) { 805 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 806 // Multiple live-ins can alias the same register. 807 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 808 if (!hasInterval(*AS)) 809 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 810 true); 811 } 812 813 // Skip over empty initial indices. 814 if (getInstructionFromIndex(MIIndex) == 0) 815 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 816 817 for (; MI != miEnd; ++MI) { 818 DEBUG(errs() << MIIndex << "\t" << *MI); 819 820 // Handle defs. 821 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 822 MachineOperand &MO = MI->getOperand(i); 823 if (!MO.isReg() || !MO.getReg()) 824 continue; 825 826 // handle register defs - build intervals 827 if (MO.isDef()) 828 handleRegisterDef(MBB, MI, MIIndex, MO, i); 829 else if (MO.isUndef()) 830 UndefUses.push_back(MO.getReg()); 831 } 832 833 // Move to the next instr slot. 834 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 835 } 836 } 837 838 // Create empty intervals for registers defined by implicit_def's (except 839 // for those implicit_def that define values which are liveout of their 840 // blocks. 841 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 842 unsigned UndefReg = UndefUses[i]; 843 (void)getOrCreateInterval(UndefReg); 844 } 845} 846 847LiveInterval* LiveIntervals::createInterval(unsigned reg) { 848 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 849 return new LiveInterval(reg, Weight); 850} 851 852/// dupInterval - Duplicate a live interval. The caller is responsible for 853/// managing the allocated memory. 854LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 855 LiveInterval *NewLI = createInterval(li->reg); 856 NewLI->Copy(*li, mri_, getVNInfoAllocator()); 857 return NewLI; 858} 859 860/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 861/// copy field and returns the source register that defines it. 862unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 863 if (!VNI->getCopy()) 864 return 0; 865 866 if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 867 // If it's extracting out of a physical register, return the sub-register. 868 unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 869 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 870 Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 871 return Reg; 872 } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 873 VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 874 return VNI->getCopy()->getOperand(2).getReg(); 875 876 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 877 if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 878 return SrcReg; 879 llvm_unreachable("Unrecognized copy instruction!"); 880 return 0; 881} 882 883//===----------------------------------------------------------------------===// 884// Register allocator hooks. 885// 886 887/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 888/// allow one) virtual register operand, then its uses are implicitly using 889/// the register. Returns the virtual register. 890unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 891 MachineInstr *MI) const { 892 unsigned RegOp = 0; 893 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 894 MachineOperand &MO = MI->getOperand(i); 895 if (!MO.isReg() || !MO.isUse()) 896 continue; 897 unsigned Reg = MO.getReg(); 898 if (Reg == 0 || Reg == li.reg) 899 continue; 900 901 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 902 !allocatableRegs_[Reg]) 903 continue; 904 // FIXME: For now, only remat MI with at most one register operand. 905 assert(!RegOp && 906 "Can't rematerialize instruction with multiple register operand!"); 907 RegOp = MO.getReg(); 908#ifndef NDEBUG 909 break; 910#endif 911 } 912 return RegOp; 913} 914 915/// isValNoAvailableAt - Return true if the val# of the specified interval 916/// which reaches the given instruction also reaches the specified use index. 917bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 918 SlotIndex UseIdx) const { 919 SlotIndex Index = getInstructionIndex(MI); 920 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 921 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 922 return UI != li.end() && UI->valno == ValNo; 923} 924 925/// isReMaterializable - Returns true if the definition MI of the specified 926/// val# of the specified interval is re-materializable. 927bool LiveIntervals::isReMaterializable(const LiveInterval &li, 928 const VNInfo *ValNo, MachineInstr *MI, 929 SmallVectorImpl<LiveInterval*> &SpillIs, 930 bool &isLoad) { 931 if (DisableReMat) 932 return false; 933 934 if (!tii_->isTriviallyReMaterializable(MI, aa_)) 935 return false; 936 937 // Target-specific code can mark an instruction as being rematerializable 938 // if it has one virtual reg use, though it had better be something like 939 // a PIC base register which is likely to be live everywhere. 940 unsigned ImpUse = getReMatImplicitUse(li, MI); 941 if (ImpUse) { 942 const LiveInterval &ImpLi = getInterval(ImpUse); 943 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 944 re = mri_->use_end(); ri != re; ++ri) { 945 MachineInstr *UseMI = &*ri; 946 SlotIndex UseIdx = getInstructionIndex(UseMI); 947 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 948 continue; 949 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 950 return false; 951 } 952 953 // If a register operand of the re-materialized instruction is going to 954 // be spilled next, then it's not legal to re-materialize this instruction. 955 for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 956 if (ImpUse == SpillIs[i]->reg) 957 return false; 958 } 959 return true; 960} 961 962/// isReMaterializable - Returns true if the definition MI of the specified 963/// val# of the specified interval is re-materializable. 964bool LiveIntervals::isReMaterializable(const LiveInterval &li, 965 const VNInfo *ValNo, MachineInstr *MI) { 966 SmallVector<LiveInterval*, 4> Dummy1; 967 bool Dummy2; 968 return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 969} 970 971/// isReMaterializable - Returns true if every definition of MI of every 972/// val# of the specified interval is re-materializable. 973bool LiveIntervals::isReMaterializable(const LiveInterval &li, 974 SmallVectorImpl<LiveInterval*> &SpillIs, 975 bool &isLoad) { 976 isLoad = false; 977 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 978 i != e; ++i) { 979 const VNInfo *VNI = *i; 980 if (VNI->isUnused()) 981 continue; // Dead val#. 982 // Is the def for the val# rematerializable? 983 if (!VNI->isDefAccurate()) 984 return false; 985 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 986 bool DefIsLoad = false; 987 if (!ReMatDefMI || 988 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 989 return false; 990 isLoad |= DefIsLoad; 991 } 992 return true; 993} 994 995/// FilterFoldedOps - Filter out two-address use operands. Return 996/// true if it finds any issue with the operands that ought to prevent 997/// folding. 998static bool FilterFoldedOps(MachineInstr *MI, 999 SmallVector<unsigned, 2> &Ops, 1000 unsigned &MRInfo, 1001 SmallVector<unsigned, 2> &FoldOps) { 1002 MRInfo = 0; 1003 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1004 unsigned OpIdx = Ops[i]; 1005 MachineOperand &MO = MI->getOperand(OpIdx); 1006 // FIXME: fold subreg use. 1007 if (MO.getSubReg()) 1008 return true; 1009 if (MO.isDef()) 1010 MRInfo |= (unsigned)VirtRegMap::isMod; 1011 else { 1012 // Filter out two-address use operand(s). 1013 if (MI->isRegTiedToDefOperand(OpIdx)) { 1014 MRInfo = VirtRegMap::isModRef; 1015 continue; 1016 } 1017 MRInfo |= (unsigned)VirtRegMap::isRef; 1018 } 1019 FoldOps.push_back(OpIdx); 1020 } 1021 return false; 1022} 1023 1024 1025/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 1026/// slot / to reg or any rematerialized load into ith operand of specified 1027/// MI. If it is successul, MI is updated with the newly created MI and 1028/// returns true. 1029bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 1030 VirtRegMap &vrm, MachineInstr *DefMI, 1031 SlotIndex InstrIdx, 1032 SmallVector<unsigned, 2> &Ops, 1033 bool isSS, int Slot, unsigned Reg) { 1034 // If it is an implicit def instruction, just delete it. 1035 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 1036 RemoveMachineInstrFromMaps(MI); 1037 vrm.RemoveMachineInstrFromMaps(MI); 1038 MI->eraseFromParent(); 1039 ++numFolds; 1040 return true; 1041 } 1042 1043 // Filter the list of operand indexes that are to be folded. Abort if 1044 // any operand will prevent folding. 1045 unsigned MRInfo = 0; 1046 SmallVector<unsigned, 2> FoldOps; 1047 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 1048 return false; 1049 1050 // The only time it's safe to fold into a two address instruction is when 1051 // it's folding reload and spill from / into a spill stack slot. 1052 if (DefMI && (MRInfo & VirtRegMap::isMod)) 1053 return false; 1054 1055 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 1056 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 1057 if (fmi) { 1058 // Remember this instruction uses the spill slot. 1059 if (isSS) vrm.addSpillSlotUse(Slot, fmi); 1060 1061 // Attempt to fold the memory reference into the instruction. If 1062 // we can do this, we don't need to insert spill code. 1063 MachineBasicBlock &MBB = *MI->getParent(); 1064 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 1065 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 1066 vrm.transferSpillPts(MI, fmi); 1067 vrm.transferRestorePts(MI, fmi); 1068 vrm.transferEmergencySpills(MI, fmi); 1069 ReplaceMachineInstrInMaps(MI, fmi); 1070 MI = MBB.insert(MBB.erase(MI), fmi); 1071 ++numFolds; 1072 return true; 1073 } 1074 return false; 1075} 1076 1077/// canFoldMemoryOperand - Returns true if the specified load / store 1078/// folding is possible. 1079bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 1080 SmallVector<unsigned, 2> &Ops, 1081 bool ReMat) const { 1082 // Filter the list of operand indexes that are to be folded. Abort if 1083 // any operand will prevent folding. 1084 unsigned MRInfo = 0; 1085 SmallVector<unsigned, 2> FoldOps; 1086 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 1087 return false; 1088 1089 // It's only legal to remat for a use, not a def. 1090 if (ReMat && (MRInfo & VirtRegMap::isMod)) 1091 return false; 1092 1093 return tii_->canFoldMemoryOperand(MI, FoldOps); 1094} 1095 1096bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 1097 LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 1098 1099 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 1100 1101 if (mbb == 0) 1102 return false; 1103 1104 for (++itr; itr != li.ranges.end(); ++itr) { 1105 MachineBasicBlock *mbb2 = 1106 indexes_->getMBBCoveringRange(itr->start, itr->end); 1107 1108 if (mbb2 != mbb) 1109 return false; 1110 } 1111 1112 return true; 1113} 1114 1115/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1116/// interval on to-be re-materialized operands of MI) with new register. 1117void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1118 MachineInstr *MI, unsigned NewVReg, 1119 VirtRegMap &vrm) { 1120 // There is an implicit use. That means one of the other operand is 1121 // being remat'ed and the remat'ed instruction has li.reg as an 1122 // use operand. Make sure we rewrite that as well. 1123 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1124 MachineOperand &MO = MI->getOperand(i); 1125 if (!MO.isReg()) 1126 continue; 1127 unsigned Reg = MO.getReg(); 1128 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1129 continue; 1130 if (!vrm.isReMaterialized(Reg)) 1131 continue; 1132 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 1133 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 1134 if (UseMO) 1135 UseMO->setReg(NewVReg); 1136 } 1137} 1138 1139/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1140/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1141bool LiveIntervals:: 1142rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1143 bool TrySplit, SlotIndex index, SlotIndex end, 1144 MachineInstr *MI, 1145 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1146 unsigned Slot, int LdSlot, 1147 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1148 VirtRegMap &vrm, 1149 const TargetRegisterClass* rc, 1150 SmallVector<int, 4> &ReMatIds, 1151 const MachineLoopInfo *loopInfo, 1152 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1153 DenseMap<unsigned,unsigned> &MBBVRegsMap, 1154 std::vector<LiveInterval*> &NewLIs) { 1155 bool CanFold = false; 1156 RestartInstruction: 1157 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1158 MachineOperand& mop = MI->getOperand(i); 1159 if (!mop.isReg()) 1160 continue; 1161 unsigned Reg = mop.getReg(); 1162 unsigned RegI = Reg; 1163 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1164 continue; 1165 if (Reg != li.reg) 1166 continue; 1167 1168 bool TryFold = !DefIsReMat; 1169 bool FoldSS = true; // Default behavior unless it's a remat. 1170 int FoldSlot = Slot; 1171 if (DefIsReMat) { 1172 // If this is the rematerializable definition MI itself and 1173 // all of its uses are rematerialized, simply delete it. 1174 if (MI == ReMatOrigDefMI && CanDelete) { 1175 DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: " 1176 << MI << '\n'); 1177 RemoveMachineInstrFromMaps(MI); 1178 vrm.RemoveMachineInstrFromMaps(MI); 1179 MI->eraseFromParent(); 1180 break; 1181 } 1182 1183 // If def for this use can't be rematerialized, then try folding. 1184 // If def is rematerializable and it's a load, also try folding. 1185 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1186 if (isLoad) { 1187 // Try fold loads (from stack slot, constant pool, etc.) into uses. 1188 FoldSS = isLoadSS; 1189 FoldSlot = LdSlot; 1190 } 1191 } 1192 1193 // Scan all of the operands of this instruction rewriting operands 1194 // to use NewVReg instead of li.reg as appropriate. We do this for 1195 // two reasons: 1196 // 1197 // 1. If the instr reads the same spilled vreg multiple times, we 1198 // want to reuse the NewVReg. 1199 // 2. If the instr is a two-addr instruction, we are required to 1200 // keep the src/dst regs pinned. 1201 // 1202 // Keep track of whether we replace a use and/or def so that we can 1203 // create the spill interval with the appropriate range. 1204 1205 HasUse = mop.isUse(); 1206 HasDef = mop.isDef(); 1207 SmallVector<unsigned, 2> Ops; 1208 Ops.push_back(i); 1209 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1210 const MachineOperand &MOj = MI->getOperand(j); 1211 if (!MOj.isReg()) 1212 continue; 1213 unsigned RegJ = MOj.getReg(); 1214 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1215 continue; 1216 if (RegJ == RegI) { 1217 Ops.push_back(j); 1218 if (!MOj.isUndef()) { 1219 HasUse |= MOj.isUse(); 1220 HasDef |= MOj.isDef(); 1221 } 1222 } 1223 } 1224 1225 // Create a new virtual register for the spill interval. 1226 // Create the new register now so we can map the fold instruction 1227 // to the new register so when it is unfolded we get the correct 1228 // answer. 1229 bool CreatedNewVReg = false; 1230 if (NewVReg == 0) { 1231 NewVReg = mri_->createVirtualRegister(rc); 1232 vrm.grow(); 1233 CreatedNewVReg = true; 1234 } 1235 1236 if (!TryFold) 1237 CanFold = false; 1238 else { 1239 // Do not fold load / store here if we are splitting. We'll find an 1240 // optimal point to insert a load / store later. 1241 if (!TrySplit) { 1242 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1243 Ops, FoldSS, FoldSlot, NewVReg)) { 1244 // Folding the load/store can completely change the instruction in 1245 // unpredictable ways, rescan it from the beginning. 1246 1247 if (FoldSS) { 1248 // We need to give the new vreg the same stack slot as the 1249 // spilled interval. 1250 vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 1251 } 1252 1253 HasUse = false; 1254 HasDef = false; 1255 CanFold = false; 1256 if (isNotInMIMap(MI)) 1257 break; 1258 goto RestartInstruction; 1259 } 1260 } else { 1261 // We'll try to fold it later if it's profitable. 1262 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1263 } 1264 } 1265 1266 mop.setReg(NewVReg); 1267 if (mop.isImplicit()) 1268 rewriteImplicitOps(li, MI, NewVReg, vrm); 1269 1270 // Reuse NewVReg for other reads. 1271 for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1272 MachineOperand &mopj = MI->getOperand(Ops[j]); 1273 mopj.setReg(NewVReg); 1274 if (mopj.isImplicit()) 1275 rewriteImplicitOps(li, MI, NewVReg, vrm); 1276 } 1277 1278 if (CreatedNewVReg) { 1279 if (DefIsReMat) { 1280 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1281 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 1282 // Each valnum may have its own remat id. 1283 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 1284 } else { 1285 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 1286 } 1287 if (!CanDelete || (HasUse && HasDef)) { 1288 // If this is a two-addr instruction then its use operands are 1289 // rematerializable but its def is not. It should be assigned a 1290 // stack slot. 1291 vrm.assignVirt2StackSlot(NewVReg, Slot); 1292 } 1293 } else { 1294 vrm.assignVirt2StackSlot(NewVReg, Slot); 1295 } 1296 } else if (HasUse && HasDef && 1297 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1298 // If this interval hasn't been assigned a stack slot (because earlier 1299 // def is a deleted remat def), do it now. 1300 assert(Slot != VirtRegMap::NO_STACK_SLOT); 1301 vrm.assignVirt2StackSlot(NewVReg, Slot); 1302 } 1303 1304 // Re-matting an instruction with virtual register use. Add the 1305 // register as an implicit use on the use MI. 1306 if (DefIsReMat && ImpUse) 1307 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1308 1309 // Create a new register interval for this spill / remat. 1310 LiveInterval &nI = getOrCreateInterval(NewVReg); 1311 if (CreatedNewVReg) { 1312 NewLIs.push_back(&nI); 1313 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 1314 if (TrySplit) 1315 vrm.setIsSplitFromReg(NewVReg, li.reg); 1316 } 1317 1318 if (HasUse) { 1319 if (CreatedNewVReg) { 1320 LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 1321 nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 1322 DEBUG(errs() << " +" << LR); 1323 nI.addRange(LR); 1324 } else { 1325 // Extend the split live interval to this def / use. 1326 SlotIndex End = index.getDefIndex(); 1327 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 1328 nI.getValNumInfo(nI.getNumValNums()-1)); 1329 DEBUG(errs() << " +" << LR); 1330 nI.addRange(LR); 1331 } 1332 } 1333 if (HasDef) { 1334 LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1335 nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 1336 DEBUG(errs() << " +" << LR); 1337 nI.addRange(LR); 1338 } 1339 1340 DEBUG({ 1341 errs() << "\t\t\t\tAdded new interval: "; 1342 nI.print(errs(), tri_); 1343 errs() << '\n'; 1344 }); 1345 } 1346 return CanFold; 1347} 1348bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 1349 const VNInfo *VNI, 1350 MachineBasicBlock *MBB, 1351 SlotIndex Idx) const { 1352 SlotIndex End = getMBBEndIdx(MBB); 1353 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1354 if (VNI->kills[j].isPHI()) 1355 continue; 1356 1357 SlotIndex KillIdx = VNI->kills[j]; 1358 if (KillIdx > Idx && KillIdx < End) 1359 return true; 1360 } 1361 return false; 1362} 1363 1364/// RewriteInfo - Keep track of machine instrs that will be rewritten 1365/// during spilling. 1366namespace { 1367 struct RewriteInfo { 1368 SlotIndex Index; 1369 MachineInstr *MI; 1370 bool HasUse; 1371 bool HasDef; 1372 RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d) 1373 : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1374 }; 1375 1376 struct RewriteInfoCompare { 1377 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1378 return LHS.Index < RHS.Index; 1379 } 1380 }; 1381} 1382 1383void LiveIntervals:: 1384rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1385 LiveInterval::Ranges::const_iterator &I, 1386 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1387 unsigned Slot, int LdSlot, 1388 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1389 VirtRegMap &vrm, 1390 const TargetRegisterClass* rc, 1391 SmallVector<int, 4> &ReMatIds, 1392 const MachineLoopInfo *loopInfo, 1393 BitVector &SpillMBBs, 1394 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 1395 BitVector &RestoreMBBs, 1396 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1397 DenseMap<unsigned,unsigned> &MBBVRegsMap, 1398 std::vector<LiveInterval*> &NewLIs) { 1399 bool AllCanFold = true; 1400 unsigned NewVReg = 0; 1401 SlotIndex start = I->start.getBaseIndex(); 1402 SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1403 1404 // First collect all the def / use in this live range that will be rewritten. 1405 // Make sure they are sorted according to instruction index. 1406 std::vector<RewriteInfo> RewriteMIs; 1407 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1408 re = mri_->reg_end(); ri != re; ) { 1409 MachineInstr *MI = &*ri; 1410 MachineOperand &O = ri.getOperand(); 1411 ++ri; 1412 assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1413 SlotIndex index = getInstructionIndex(MI); 1414 if (index < start || index >= end) 1415 continue; 1416 1417 if (O.isUndef()) 1418 // Must be defined by an implicit def. It should not be spilled. Note, 1419 // this is for correctness reason. e.g. 1420 // 8 %reg1024<def> = IMPLICIT_DEF 1421 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 1422 // The live range [12, 14) are not part of the r1024 live interval since 1423 // it's defined by an implicit def. It will not conflicts with live 1424 // interval of r1025. Now suppose both registers are spilled, you can 1425 // easily see a situation where both registers are reloaded before 1426 // the INSERT_SUBREG and both target registers that would overlap. 1427 continue; 1428 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1429 } 1430 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1431 1432 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1433 // Now rewrite the defs and uses. 1434 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1435 RewriteInfo &rwi = RewriteMIs[i]; 1436 ++i; 1437 SlotIndex index = rwi.Index; 1438 bool MIHasUse = rwi.HasUse; 1439 bool MIHasDef = rwi.HasDef; 1440 MachineInstr *MI = rwi.MI; 1441 // If MI def and/or use the same register multiple times, then there 1442 // are multiple entries. 1443 unsigned NumUses = MIHasUse; 1444 while (i != e && RewriteMIs[i].MI == MI) { 1445 assert(RewriteMIs[i].Index == index); 1446 bool isUse = RewriteMIs[i].HasUse; 1447 if (isUse) ++NumUses; 1448 MIHasUse |= isUse; 1449 MIHasDef |= RewriteMIs[i].HasDef; 1450 ++i; 1451 } 1452 MachineBasicBlock *MBB = MI->getParent(); 1453 1454 if (ImpUse && MI != ReMatDefMI) { 1455 // Re-matting an instruction with virtual register use. Update the 1456 // register interval's spill weight to HUGE_VALF to prevent it from 1457 // being spilled. 1458 LiveInterval &ImpLi = getInterval(ImpUse); 1459 ImpLi.weight = HUGE_VALF; 1460 } 1461 1462 unsigned MBBId = MBB->getNumber(); 1463 unsigned ThisVReg = 0; 1464 if (TrySplit) { 1465 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 1466 if (NVI != MBBVRegsMap.end()) { 1467 ThisVReg = NVI->second; 1468 // One common case: 1469 // x = use 1470 // ... 1471 // ... 1472 // def = ... 1473 // = use 1474 // It's better to start a new interval to avoid artifically 1475 // extend the new interval. 1476 if (MIHasDef && !MIHasUse) { 1477 MBBVRegsMap.erase(MBB->getNumber()); 1478 ThisVReg = 0; 1479 } 1480 } 1481 } 1482 1483 bool IsNew = ThisVReg == 0; 1484 if (IsNew) { 1485 // This ends the previous live interval. If all of its def / use 1486 // can be folded, give it a low spill weight. 1487 if (NewVReg && TrySplit && AllCanFold) { 1488 LiveInterval &nI = getOrCreateInterval(NewVReg); 1489 nI.weight /= 10.0F; 1490 } 1491 AllCanFold = true; 1492 } 1493 NewVReg = ThisVReg; 1494 1495 bool HasDef = false; 1496 bool HasUse = false; 1497 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1498 index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1499 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1500 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1501 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 1502 if (!HasDef && !HasUse) 1503 continue; 1504 1505 AllCanFold &= CanFold; 1506 1507 // Update weight of spill interval. 1508 LiveInterval &nI = getOrCreateInterval(NewVReg); 1509 if (!TrySplit) { 1510 // The spill weight is now infinity as it cannot be spilled again. 1511 nI.weight = HUGE_VALF; 1512 continue; 1513 } 1514 1515 // Keep track of the last def and first use in each MBB. 1516 if (HasDef) { 1517 if (MI != ReMatOrigDefMI || !CanDelete) { 1518 bool HasKill = false; 1519 if (!HasUse) 1520 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 1521 else { 1522 // If this is a two-address code, then this index starts a new VNInfo. 1523 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 1524 if (VNI) 1525 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 1526 } 1527 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1528 SpillIdxes.find(MBBId); 1529 if (!HasKill) { 1530 if (SII == SpillIdxes.end()) { 1531 std::vector<SRInfo> S; 1532 S.push_back(SRInfo(index, NewVReg, true)); 1533 SpillIdxes.insert(std::make_pair(MBBId, S)); 1534 } else if (SII->second.back().vreg != NewVReg) { 1535 SII->second.push_back(SRInfo(index, NewVReg, true)); 1536 } else if (index > SII->second.back().index) { 1537 // If there is an earlier def and this is a two-address 1538 // instruction, then it's not possible to fold the store (which 1539 // would also fold the load). 1540 SRInfo &Info = SII->second.back(); 1541 Info.index = index; 1542 Info.canFold = !HasUse; 1543 } 1544 SpillMBBs.set(MBBId); 1545 } else if (SII != SpillIdxes.end() && 1546 SII->second.back().vreg == NewVReg && 1547 index > SII->second.back().index) { 1548 // There is an earlier def that's not killed (must be two-address). 1549 // The spill is no longer needed. 1550 SII->second.pop_back(); 1551 if (SII->second.empty()) { 1552 SpillIdxes.erase(MBBId); 1553 SpillMBBs.reset(MBBId); 1554 } 1555 } 1556 } 1557 } 1558 1559 if (HasUse) { 1560 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1561 SpillIdxes.find(MBBId); 1562 if (SII != SpillIdxes.end() && 1563 SII->second.back().vreg == NewVReg && 1564 index > SII->second.back().index) 1565 // Use(s) following the last def, it's not safe to fold the spill. 1566 SII->second.back().canFold = false; 1567 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 1568 RestoreIdxes.find(MBBId); 1569 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 1570 // If we are splitting live intervals, only fold if it's the first 1571 // use and there isn't another use later in the MBB. 1572 RII->second.back().canFold = false; 1573 else if (IsNew) { 1574 // Only need a reload if there isn't an earlier def / use. 1575 if (RII == RestoreIdxes.end()) { 1576 std::vector<SRInfo> Infos; 1577 Infos.push_back(SRInfo(index, NewVReg, true)); 1578 RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 1579 } else { 1580 RII->second.push_back(SRInfo(index, NewVReg, true)); 1581 } 1582 RestoreMBBs.set(MBBId); 1583 } 1584 } 1585 1586 // Update spill weight. 1587 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1588 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1589 } 1590 1591 if (NewVReg && TrySplit && AllCanFold) { 1592 // If all of its def / use can be folded, give it a low spill weight. 1593 LiveInterval &nI = getOrCreateInterval(NewVReg); 1594 nI.weight /= 10.0F; 1595 } 1596} 1597 1598bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 1599 unsigned vr, BitVector &RestoreMBBs, 1600 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1601 if (!RestoreMBBs[Id]) 1602 return false; 1603 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1604 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1605 if (Restores[i].index == index && 1606 Restores[i].vreg == vr && 1607 Restores[i].canFold) 1608 return true; 1609 return false; 1610} 1611 1612void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 1613 unsigned vr, BitVector &RestoreMBBs, 1614 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1615 if (!RestoreMBBs[Id]) 1616 return; 1617 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1618 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1619 if (Restores[i].index == index && Restores[i].vreg) 1620 Restores[i].index = SlotIndex(); 1621} 1622 1623/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 1624/// spilled and create empty intervals for their uses. 1625void 1626LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 1627 const TargetRegisterClass* rc, 1628 std::vector<LiveInterval*> &NewLIs) { 1629 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1630 re = mri_->reg_end(); ri != re; ) { 1631 MachineOperand &O = ri.getOperand(); 1632 MachineInstr *MI = &*ri; 1633 ++ri; 1634 if (O.isDef()) { 1635 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 1636 "Register def was not rewritten?"); 1637 RemoveMachineInstrFromMaps(MI); 1638 vrm.RemoveMachineInstrFromMaps(MI); 1639 MI->eraseFromParent(); 1640 } else { 1641 // This must be an use of an implicit_def so it's not part of the live 1642 // interval. Create a new empty live interval for it. 1643 // FIXME: Can we simply erase some of the instructions? e.g. Stores? 1644 unsigned NewVReg = mri_->createVirtualRegister(rc); 1645 vrm.grow(); 1646 vrm.setIsImplicitlyDefined(NewVReg); 1647 NewLIs.push_back(&getOrCreateInterval(NewVReg)); 1648 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1649 MachineOperand &MO = MI->getOperand(i); 1650 if (MO.isReg() && MO.getReg() == li.reg) { 1651 MO.setReg(NewVReg); 1652 MO.setIsUndef(); 1653 } 1654 } 1655 } 1656 } 1657} 1658 1659std::vector<LiveInterval*> LiveIntervals:: 1660addIntervalsForSpillsFast(const LiveInterval &li, 1661 const MachineLoopInfo *loopInfo, 1662 VirtRegMap &vrm) { 1663 unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1664 1665 std::vector<LiveInterval*> added; 1666 1667 assert(li.weight != HUGE_VALF && 1668 "attempt to spill already spilled interval!"); 1669 1670 DEBUG({ 1671 errs() << "\t\t\t\tadding intervals for spills for interval: "; 1672 li.dump(); 1673 errs() << '\n'; 1674 }); 1675 1676 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1677 1678 MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1679 while (RI != mri_->reg_end()) { 1680 MachineInstr* MI = &*RI; 1681 1682 SmallVector<unsigned, 2> Indices; 1683 bool HasUse = false; 1684 bool HasDef = false; 1685 1686 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1687 MachineOperand& mop = MI->getOperand(i); 1688 if (!mop.isReg() || mop.getReg() != li.reg) continue; 1689 1690 HasUse |= MI->getOperand(i).isUse(); 1691 HasDef |= MI->getOperand(i).isDef(); 1692 1693 Indices.push_back(i); 1694 } 1695 1696 if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1697 Indices, true, slot, li.reg)) { 1698 unsigned NewVReg = mri_->createVirtualRegister(rc); 1699 vrm.grow(); 1700 vrm.assignVirt2StackSlot(NewVReg, slot); 1701 1702 // create a new register for this spill 1703 LiveInterval &nI = getOrCreateInterval(NewVReg); 1704 1705 // the spill weight is now infinity as it 1706 // cannot be spilled again 1707 nI.weight = HUGE_VALF; 1708 1709 // Rewrite register operands to use the new vreg. 1710 for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1711 E = Indices.end(); I != E; ++I) { 1712 MI->getOperand(*I).setReg(NewVReg); 1713 1714 if (MI->getOperand(*I).isUse()) 1715 MI->getOperand(*I).setIsKill(true); 1716 } 1717 1718 // Fill in the new live interval. 1719 SlotIndex index = getInstructionIndex(MI); 1720 if (HasUse) { 1721 LiveRange LR(index.getLoadIndex(), index.getUseIndex(), 1722 nI.getNextValue(SlotIndex(), 0, false, 1723 getVNInfoAllocator())); 1724 DEBUG(errs() << " +" << LR); 1725 nI.addRange(LR); 1726 vrm.addRestorePoint(NewVReg, MI); 1727 } 1728 if (HasDef) { 1729 LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1730 nI.getNextValue(SlotIndex(), 0, false, 1731 getVNInfoAllocator())); 1732 DEBUG(errs() << " +" << LR); 1733 nI.addRange(LR); 1734 vrm.addSpillPoint(NewVReg, true, MI); 1735 } 1736 1737 added.push_back(&nI); 1738 1739 DEBUG({ 1740 errs() << "\t\t\t\tadded new interval: "; 1741 nI.dump(); 1742 errs() << '\n'; 1743 }); 1744 } 1745 1746 1747 RI = mri_->reg_begin(li.reg); 1748 } 1749 1750 return added; 1751} 1752 1753std::vector<LiveInterval*> LiveIntervals:: 1754addIntervalsForSpills(const LiveInterval &li, 1755 SmallVectorImpl<LiveInterval*> &SpillIs, 1756 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1757 1758 if (EnableFastSpilling) 1759 return addIntervalsForSpillsFast(li, loopInfo, vrm); 1760 1761 assert(li.weight != HUGE_VALF && 1762 "attempt to spill already spilled interval!"); 1763 1764 DEBUG({ 1765 errs() << "\t\t\t\tadding intervals for spills for interval: "; 1766 li.print(errs(), tri_); 1767 errs() << '\n'; 1768 }); 1769 1770 // Each bit specify whether a spill is required in the MBB. 1771 BitVector SpillMBBs(mf_->getNumBlockIDs()); 1772 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 1773 BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1774 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1775 DenseMap<unsigned,unsigned> MBBVRegsMap; 1776 std::vector<LiveInterval*> NewLIs; 1777 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1778 1779 unsigned NumValNums = li.getNumValNums(); 1780 SmallVector<MachineInstr*, 4> ReMatDefs; 1781 ReMatDefs.resize(NumValNums, NULL); 1782 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1783 ReMatOrigDefs.resize(NumValNums, NULL); 1784 SmallVector<int, 4> ReMatIds; 1785 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1786 BitVector ReMatDelete(NumValNums); 1787 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1788 1789 // Spilling a split live interval. It cannot be split any further. Also, 1790 // it's also guaranteed to be a single val# / range interval. 1791 if (vrm.getPreSplitReg(li.reg)) { 1792 vrm.setIsSplitFromReg(li.reg, 0); 1793 // Unset the split kill marker on the last use. 1794 SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1795 if (KillIdx != SlotIndex()) { 1796 MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1797 assert(KillMI && "Last use disappeared?"); 1798 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1799 assert(KillOp != -1 && "Last use disappeared?"); 1800 KillMI->getOperand(KillOp).setIsKill(false); 1801 } 1802 vrm.removeKillPoint(li.reg); 1803 bool DefIsReMat = vrm.isReMaterialized(li.reg); 1804 Slot = vrm.getStackSlot(li.reg); 1805 assert(Slot != VirtRegMap::MAX_STACK_SLOT); 1806 MachineInstr *ReMatDefMI = DefIsReMat ? 1807 vrm.getReMaterializedMI(li.reg) : NULL; 1808 int LdSlot = 0; 1809 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1810 bool isLoad = isLoadSS || 1811 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 1812 bool IsFirstRange = true; 1813 for (LiveInterval::Ranges::const_iterator 1814 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1815 // If this is a split live interval with multiple ranges, it means there 1816 // are two-address instructions that re-defined the value. Only the 1817 // first def can be rematerialized! 1818 if (IsFirstRange) { 1819 // Note ReMatOrigDefMI has already been deleted. 1820 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 1821 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1822 false, vrm, rc, ReMatIds, loopInfo, 1823 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1824 MBBVRegsMap, NewLIs); 1825 } else { 1826 rewriteInstructionsForSpills(li, false, I, NULL, 0, 1827 Slot, 0, false, false, false, 1828 false, vrm, rc, ReMatIds, loopInfo, 1829 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1830 MBBVRegsMap, NewLIs); 1831 } 1832 IsFirstRange = false; 1833 } 1834 1835 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1836 return NewLIs; 1837 } 1838 1839 bool TrySplit = !intervalIsInOneMBB(li); 1840 if (TrySplit) 1841 ++numSplits; 1842 bool NeedStackSlot = false; 1843 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1844 i != e; ++i) { 1845 const VNInfo *VNI = *i; 1846 unsigned VN = VNI->id; 1847 if (VNI->isUnused()) 1848 continue; // Dead val#. 1849 // Is the def for the val# rematerializable? 1850 MachineInstr *ReMatDefMI = VNI->isDefAccurate() 1851 ? getInstructionFromIndex(VNI->def) : 0; 1852 bool dummy; 1853 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1854 // Remember how to remat the def of this val#. 1855 ReMatOrigDefs[VN] = ReMatDefMI; 1856 // Original def may be modified so we have to make a copy here. 1857 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1858 CloneMIs.push_back(Clone); 1859 ReMatDefs[VN] = Clone; 1860 1861 bool CanDelete = true; 1862 if (VNI->hasPHIKill()) { 1863 // A kill is a phi node, not all of its uses can be rematerialized. 1864 // It must not be deleted. 1865 CanDelete = false; 1866 // Need a stack slot if there is any live range where uses cannot be 1867 // rematerialized. 1868 NeedStackSlot = true; 1869 } 1870 if (CanDelete) 1871 ReMatDelete.set(VN); 1872 } else { 1873 // Need a stack slot if there is any live range where uses cannot be 1874 // rematerialized. 1875 NeedStackSlot = true; 1876 } 1877 } 1878 1879 // One stack slot per live interval. 1880 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1881 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1882 Slot = vrm.assignVirt2StackSlot(li.reg); 1883 1884 // This case only occurs when the prealloc splitter has already assigned 1885 // a stack slot to this vreg. 1886 else 1887 Slot = vrm.getStackSlot(li.reg); 1888 } 1889 1890 // Create new intervals and rewrite defs and uses. 1891 for (LiveInterval::Ranges::const_iterator 1892 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1893 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 1894 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 1895 bool DefIsReMat = ReMatDefMI != NULL; 1896 bool CanDelete = ReMatDelete[I->valno->id]; 1897 int LdSlot = 0; 1898 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1899 bool isLoad = isLoadSS || 1900 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 1901 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 1902 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1903 CanDelete, vrm, rc, ReMatIds, loopInfo, 1904 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1905 MBBVRegsMap, NewLIs); 1906 } 1907 1908 // Insert spills / restores if we are splitting. 1909 if (!TrySplit) { 1910 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1911 return NewLIs; 1912 } 1913 1914 SmallPtrSet<LiveInterval*, 4> AddedKill; 1915 SmallVector<unsigned, 2> Ops; 1916 if (NeedStackSlot) { 1917 int Id = SpillMBBs.find_first(); 1918 while (Id != -1) { 1919 std::vector<SRInfo> &spills = SpillIdxes[Id]; 1920 for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1921 SlotIndex index = spills[i].index; 1922 unsigned VReg = spills[i].vreg; 1923 LiveInterval &nI = getOrCreateInterval(VReg); 1924 bool isReMat = vrm.isReMaterialized(VReg); 1925 MachineInstr *MI = getInstructionFromIndex(index); 1926 bool CanFold = false; 1927 bool FoundUse = false; 1928 Ops.clear(); 1929 if (spills[i].canFold) { 1930 CanFold = true; 1931 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1932 MachineOperand &MO = MI->getOperand(j); 1933 if (!MO.isReg() || MO.getReg() != VReg) 1934 continue; 1935 1936 Ops.push_back(j); 1937 if (MO.isDef()) 1938 continue; 1939 if (isReMat || 1940 (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1941 RestoreMBBs, RestoreIdxes))) { 1942 // MI has two-address uses of the same register. If the use 1943 // isn't the first and only use in the BB, then we can't fold 1944 // it. FIXME: Move this to rewriteInstructionsForSpills. 1945 CanFold = false; 1946 break; 1947 } 1948 FoundUse = true; 1949 } 1950 } 1951 // Fold the store into the def if possible. 1952 bool Folded = false; 1953 if (CanFold && !Ops.empty()) { 1954 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1955 Folded = true; 1956 if (FoundUse) { 1957 // Also folded uses, do not issue a load. 1958 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1959 nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1960 } 1961 nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1962 } 1963 } 1964 1965 // Otherwise tell the spiller to issue a spill. 1966 if (!Folded) { 1967 LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1968 bool isKill = LR->end == index.getStoreIndex(); 1969 if (!MI->registerDefIsDead(nI.reg)) 1970 // No need to spill a dead def. 1971 vrm.addSpillPoint(VReg, isKill, MI); 1972 if (isKill) 1973 AddedKill.insert(&nI); 1974 } 1975 } 1976 Id = SpillMBBs.find_next(Id); 1977 } 1978 } 1979 1980 int Id = RestoreMBBs.find_first(); 1981 while (Id != -1) { 1982 std::vector<SRInfo> &restores = RestoreIdxes[Id]; 1983 for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1984 SlotIndex index = restores[i].index; 1985 if (index == SlotIndex()) 1986 continue; 1987 unsigned VReg = restores[i].vreg; 1988 LiveInterval &nI = getOrCreateInterval(VReg); 1989 bool isReMat = vrm.isReMaterialized(VReg); 1990 MachineInstr *MI = getInstructionFromIndex(index); 1991 bool CanFold = false; 1992 Ops.clear(); 1993 if (restores[i].canFold) { 1994 CanFold = true; 1995 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1996 MachineOperand &MO = MI->getOperand(j); 1997 if (!MO.isReg() || MO.getReg() != VReg) 1998 continue; 1999 2000 if (MO.isDef()) { 2001 // If this restore were to be folded, it would have been folded 2002 // already. 2003 CanFold = false; 2004 break; 2005 } 2006 Ops.push_back(j); 2007 } 2008 } 2009 2010 // Fold the load into the use if possible. 2011 bool Folded = false; 2012 if (CanFold && !Ops.empty()) { 2013 if (!isReMat) 2014 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 2015 else { 2016 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 2017 int LdSlot = 0; 2018 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 2019 // If the rematerializable def is a load, also try to fold it. 2020 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 2021 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 2022 Ops, isLoadSS, LdSlot, VReg); 2023 if (!Folded) { 2024 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 2025 if (ImpUse) { 2026 // Re-matting an instruction with virtual register use. Add the 2027 // register as an implicit use on the use MI and update the register 2028 // interval's spill weight to HUGE_VALF to prevent it from being 2029 // spilled. 2030 LiveInterval &ImpLi = getInterval(ImpUse); 2031 ImpLi.weight = HUGE_VALF; 2032 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 2033 } 2034 } 2035 } 2036 } 2037 // If folding is not possible / failed, then tell the spiller to issue a 2038 // load / rematerialization for us. 2039 if (Folded) 2040 nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 2041 else 2042 vrm.addRestorePoint(VReg, MI); 2043 } 2044 Id = RestoreMBBs.find_next(Id); 2045 } 2046 2047 // Finalize intervals: add kills, finalize spill weights, and filter out 2048 // dead intervals. 2049 std::vector<LiveInterval*> RetNewLIs; 2050 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2051 LiveInterval *LI = NewLIs[i]; 2052 if (!LI->empty()) { 2053 LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI); 2054 if (!AddedKill.count(LI)) { 2055 LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2056 SlotIndex LastUseIdx = LR->end.getBaseIndex(); 2057 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 2058 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2059 assert(UseIdx != -1); 2060 if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 2061 LastUse->getOperand(UseIdx).setIsKill(); 2062 vrm.addKillPoint(LI->reg, LastUseIdx); 2063 } 2064 } 2065 RetNewLIs.push_back(LI); 2066 } 2067 } 2068 2069 handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2070 return RetNewLIs; 2071} 2072 2073/// hasAllocatableSuperReg - Return true if the specified physical register has 2074/// any super register that's allocatable. 2075bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2076 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2077 if (allocatableRegs_[*AS] && hasInterval(*AS)) 2078 return true; 2079 return false; 2080} 2081 2082/// getRepresentativeReg - Find the largest super register of the specified 2083/// physical register. 2084unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2085 // Find the largest super-register that is allocatable. 2086 unsigned BestReg = Reg; 2087 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2088 unsigned SuperReg = *AS; 2089 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2090 BestReg = SuperReg; 2091 break; 2092 } 2093 } 2094 return BestReg; 2095} 2096 2097/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2098/// specified interval that conflicts with the specified physical register. 2099unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2100 unsigned PhysReg) const { 2101 unsigned NumConflicts = 0; 2102 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2103 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2104 E = mri_->reg_end(); I != E; ++I) { 2105 MachineOperand &O = I.getOperand(); 2106 MachineInstr *MI = O.getParent(); 2107 SlotIndex Index = getInstructionIndex(MI); 2108 if (pli.liveAt(Index)) 2109 ++NumConflicts; 2110 } 2111 return NumConflicts; 2112} 2113 2114/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 2115/// around all defs and uses of the specified interval. Return true if it 2116/// was able to cut its interval. 2117bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2118 unsigned PhysReg, VirtRegMap &vrm) { 2119 unsigned SpillReg = getRepresentativeReg(PhysReg); 2120 2121 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2122 // If there are registers which alias PhysReg, but which are not a 2123 // sub-register of the chosen representative super register. Assert 2124 // since we can't handle it yet. 2125 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2126 tri_->isSuperRegister(*AS, SpillReg)); 2127 2128 bool Cut = false; 2129 SmallVector<unsigned, 4> PRegs; 2130 if (hasInterval(SpillReg)) 2131 PRegs.push_back(SpillReg); 2132 else { 2133 SmallSet<unsigned, 4> Added; 2134 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) 2135 if (Added.insert(*AS) && hasInterval(*AS)) { 2136 PRegs.push_back(*AS); 2137 for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS) 2138 Added.insert(*ASS); 2139 } 2140 } 2141 2142 SmallPtrSet<MachineInstr*, 8> SeenMIs; 2143 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2144 E = mri_->reg_end(); I != E; ++I) { 2145 MachineOperand &O = I.getOperand(); 2146 MachineInstr *MI = O.getParent(); 2147 if (SeenMIs.count(MI)) 2148 continue; 2149 SeenMIs.insert(MI); 2150 SlotIndex Index = getInstructionIndex(MI); 2151 for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 2152 unsigned PReg = PRegs[i]; 2153 LiveInterval &pli = getInterval(PReg); 2154 if (!pli.liveAt(Index)) 2155 continue; 2156 vrm.addEmergencySpill(PReg, MI); 2157 SlotIndex StartIdx = Index.getLoadIndex(); 2158 SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 2159 if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 2160 pli.removeRange(StartIdx, EndIdx); 2161 Cut = true; 2162 } else { 2163 std::string msg; 2164 raw_string_ostream Msg(msg); 2165 Msg << "Ran out of registers during register allocation!"; 2166 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 2167 Msg << "\nPlease check your inline asm statement for invalid " 2168 << "constraints:\n"; 2169 MI->print(Msg, tm_); 2170 } 2171 llvm_report_error(Msg.str()); 2172 } 2173 for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) { 2174 if (!hasInterval(*AS)) 2175 continue; 2176 LiveInterval &spli = getInterval(*AS); 2177 if (spli.liveAt(Index)) 2178 spli.removeRange(Index.getLoadIndex(), 2179 Index.getNextIndex().getBaseIndex()); 2180 } 2181 } 2182 } 2183 return Cut; 2184} 2185 2186LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2187 MachineInstr* startInst) { 2188 LiveInterval& Interval = getOrCreateInterval(reg); 2189 VNInfo* VN = Interval.getNextValue( 2190 SlotIndex(getInstructionIndex(startInst).getDefIndex()), 2191 startInst, true, getVNInfoAllocator()); 2192 VN->setHasPHIKill(true); 2193 VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent())); 2194 LiveRange LR( 2195 SlotIndex(getInstructionIndex(startInst).getDefIndex()), 2196 getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN); 2197 Interval.addRange(LR); 2198 2199 return LR; 2200} 2201 | 646/// computeIntervals - computes the live intervals for virtual 647/// registers. for some ordering of the machine instructions [1,N] a 648/// live interval is an interval [i, j) where 1 <= i <= j < N for 649/// which a variable is live 650void LiveIntervals::computeIntervals() { 651 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" 652 << "********** Function: " 653 << ((Value*)mf_->getFunction())->getName() << '\n'); 654 655 SmallVector<unsigned, 8> UndefUses; 656 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 657 MBBI != E; ++MBBI) { 658 MachineBasicBlock *MBB = MBBI; 659 // Track the index of the current machine instr. 660 SlotIndex MIIndex = getMBBStartIdx(MBB); 661 DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 662 663 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 664 665 // Create intervals for live-ins to this BB first. 666 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 667 LE = MBB->livein_end(); LI != LE; ++LI) { 668 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 669 // Multiple live-ins can alias the same register. 670 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 671 if (!hasInterval(*AS)) 672 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 673 true); 674 } 675 676 // Skip over empty initial indices. 677 if (getInstructionFromIndex(MIIndex) == 0) 678 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 679 680 for (; MI != miEnd; ++MI) { 681 DEBUG(errs() << MIIndex << "\t" << *MI); 682 683 // Handle defs. 684 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 685 MachineOperand &MO = MI->getOperand(i); 686 if (!MO.isReg() || !MO.getReg()) 687 continue; 688 689 // handle register defs - build intervals 690 if (MO.isDef()) 691 handleRegisterDef(MBB, MI, MIIndex, MO, i); 692 else if (MO.isUndef()) 693 UndefUses.push_back(MO.getReg()); 694 } 695 696 // Move to the next instr slot. 697 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 698 } 699 } 700 701 // Create empty intervals for registers defined by implicit_def's (except 702 // for those implicit_def that define values which are liveout of their 703 // blocks. 704 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 705 unsigned UndefReg = UndefUses[i]; 706 (void)getOrCreateInterval(UndefReg); 707 } 708} 709 710LiveInterval* LiveIntervals::createInterval(unsigned reg) { 711 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 712 return new LiveInterval(reg, Weight); 713} 714 715/// dupInterval - Duplicate a live interval. The caller is responsible for 716/// managing the allocated memory. 717LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 718 LiveInterval *NewLI = createInterval(li->reg); 719 NewLI->Copy(*li, mri_, getVNInfoAllocator()); 720 return NewLI; 721} 722 723/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 724/// copy field and returns the source register that defines it. 725unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 726 if (!VNI->getCopy()) 727 return 0; 728 729 if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 730 // If it's extracting out of a physical register, return the sub-register. 731 unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 732 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 733 Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 734 return Reg; 735 } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 736 VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 737 return VNI->getCopy()->getOperand(2).getReg(); 738 739 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 740 if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 741 return SrcReg; 742 llvm_unreachable("Unrecognized copy instruction!"); 743 return 0; 744} 745 746//===----------------------------------------------------------------------===// 747// Register allocator hooks. 748// 749 750/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 751/// allow one) virtual register operand, then its uses are implicitly using 752/// the register. Returns the virtual register. 753unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 754 MachineInstr *MI) const { 755 unsigned RegOp = 0; 756 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 757 MachineOperand &MO = MI->getOperand(i); 758 if (!MO.isReg() || !MO.isUse()) 759 continue; 760 unsigned Reg = MO.getReg(); 761 if (Reg == 0 || Reg == li.reg) 762 continue; 763 764 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 765 !allocatableRegs_[Reg]) 766 continue; 767 // FIXME: For now, only remat MI with at most one register operand. 768 assert(!RegOp && 769 "Can't rematerialize instruction with multiple register operand!"); 770 RegOp = MO.getReg(); 771#ifndef NDEBUG 772 break; 773#endif 774 } 775 return RegOp; 776} 777 778/// isValNoAvailableAt - Return true if the val# of the specified interval 779/// which reaches the given instruction also reaches the specified use index. 780bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 781 SlotIndex UseIdx) const { 782 SlotIndex Index = getInstructionIndex(MI); 783 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 784 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 785 return UI != li.end() && UI->valno == ValNo; 786} 787 788/// isReMaterializable - Returns true if the definition MI of the specified 789/// val# of the specified interval is re-materializable. 790bool LiveIntervals::isReMaterializable(const LiveInterval &li, 791 const VNInfo *ValNo, MachineInstr *MI, 792 SmallVectorImpl<LiveInterval*> &SpillIs, 793 bool &isLoad) { 794 if (DisableReMat) 795 return false; 796 797 if (!tii_->isTriviallyReMaterializable(MI, aa_)) 798 return false; 799 800 // Target-specific code can mark an instruction as being rematerializable 801 // if it has one virtual reg use, though it had better be something like 802 // a PIC base register which is likely to be live everywhere. 803 unsigned ImpUse = getReMatImplicitUse(li, MI); 804 if (ImpUse) { 805 const LiveInterval &ImpLi = getInterval(ImpUse); 806 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 807 re = mri_->use_end(); ri != re; ++ri) { 808 MachineInstr *UseMI = &*ri; 809 SlotIndex UseIdx = getInstructionIndex(UseMI); 810 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 811 continue; 812 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 813 return false; 814 } 815 816 // If a register operand of the re-materialized instruction is going to 817 // be spilled next, then it's not legal to re-materialize this instruction. 818 for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 819 if (ImpUse == SpillIs[i]->reg) 820 return false; 821 } 822 return true; 823} 824 825/// isReMaterializable - Returns true if the definition MI of the specified 826/// val# of the specified interval is re-materializable. 827bool LiveIntervals::isReMaterializable(const LiveInterval &li, 828 const VNInfo *ValNo, MachineInstr *MI) { 829 SmallVector<LiveInterval*, 4> Dummy1; 830 bool Dummy2; 831 return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 832} 833 834/// isReMaterializable - Returns true if every definition of MI of every 835/// val# of the specified interval is re-materializable. 836bool LiveIntervals::isReMaterializable(const LiveInterval &li, 837 SmallVectorImpl<LiveInterval*> &SpillIs, 838 bool &isLoad) { 839 isLoad = false; 840 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 841 i != e; ++i) { 842 const VNInfo *VNI = *i; 843 if (VNI->isUnused()) 844 continue; // Dead val#. 845 // Is the def for the val# rematerializable? 846 if (!VNI->isDefAccurate()) 847 return false; 848 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 849 bool DefIsLoad = false; 850 if (!ReMatDefMI || 851 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 852 return false; 853 isLoad |= DefIsLoad; 854 } 855 return true; 856} 857 858/// FilterFoldedOps - Filter out two-address use operands. Return 859/// true if it finds any issue with the operands that ought to prevent 860/// folding. 861static bool FilterFoldedOps(MachineInstr *MI, 862 SmallVector<unsigned, 2> &Ops, 863 unsigned &MRInfo, 864 SmallVector<unsigned, 2> &FoldOps) { 865 MRInfo = 0; 866 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 867 unsigned OpIdx = Ops[i]; 868 MachineOperand &MO = MI->getOperand(OpIdx); 869 // FIXME: fold subreg use. 870 if (MO.getSubReg()) 871 return true; 872 if (MO.isDef()) 873 MRInfo |= (unsigned)VirtRegMap::isMod; 874 else { 875 // Filter out two-address use operand(s). 876 if (MI->isRegTiedToDefOperand(OpIdx)) { 877 MRInfo = VirtRegMap::isModRef; 878 continue; 879 } 880 MRInfo |= (unsigned)VirtRegMap::isRef; 881 } 882 FoldOps.push_back(OpIdx); 883 } 884 return false; 885} 886 887 888/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 889/// slot / to reg or any rematerialized load into ith operand of specified 890/// MI. If it is successul, MI is updated with the newly created MI and 891/// returns true. 892bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 893 VirtRegMap &vrm, MachineInstr *DefMI, 894 SlotIndex InstrIdx, 895 SmallVector<unsigned, 2> &Ops, 896 bool isSS, int Slot, unsigned Reg) { 897 // If it is an implicit def instruction, just delete it. 898 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 899 RemoveMachineInstrFromMaps(MI); 900 vrm.RemoveMachineInstrFromMaps(MI); 901 MI->eraseFromParent(); 902 ++numFolds; 903 return true; 904 } 905 906 // Filter the list of operand indexes that are to be folded. Abort if 907 // any operand will prevent folding. 908 unsigned MRInfo = 0; 909 SmallVector<unsigned, 2> FoldOps; 910 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 911 return false; 912 913 // The only time it's safe to fold into a two address instruction is when 914 // it's folding reload and spill from / into a spill stack slot. 915 if (DefMI && (MRInfo & VirtRegMap::isMod)) 916 return false; 917 918 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 919 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 920 if (fmi) { 921 // Remember this instruction uses the spill slot. 922 if (isSS) vrm.addSpillSlotUse(Slot, fmi); 923 924 // Attempt to fold the memory reference into the instruction. If 925 // we can do this, we don't need to insert spill code. 926 MachineBasicBlock &MBB = *MI->getParent(); 927 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 928 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 929 vrm.transferSpillPts(MI, fmi); 930 vrm.transferRestorePts(MI, fmi); 931 vrm.transferEmergencySpills(MI, fmi); 932 ReplaceMachineInstrInMaps(MI, fmi); 933 MI = MBB.insert(MBB.erase(MI), fmi); 934 ++numFolds; 935 return true; 936 } 937 return false; 938} 939 940/// canFoldMemoryOperand - Returns true if the specified load / store 941/// folding is possible. 942bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 943 SmallVector<unsigned, 2> &Ops, 944 bool ReMat) const { 945 // Filter the list of operand indexes that are to be folded. Abort if 946 // any operand will prevent folding. 947 unsigned MRInfo = 0; 948 SmallVector<unsigned, 2> FoldOps; 949 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 950 return false; 951 952 // It's only legal to remat for a use, not a def. 953 if (ReMat && (MRInfo & VirtRegMap::isMod)) 954 return false; 955 956 return tii_->canFoldMemoryOperand(MI, FoldOps); 957} 958 959bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 960 LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 961 962 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 963 964 if (mbb == 0) 965 return false; 966 967 for (++itr; itr != li.ranges.end(); ++itr) { 968 MachineBasicBlock *mbb2 = 969 indexes_->getMBBCoveringRange(itr->start, itr->end); 970 971 if (mbb2 != mbb) 972 return false; 973 } 974 975 return true; 976} 977 978/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 979/// interval on to-be re-materialized operands of MI) with new register. 980void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 981 MachineInstr *MI, unsigned NewVReg, 982 VirtRegMap &vrm) { 983 // There is an implicit use. That means one of the other operand is 984 // being remat'ed and the remat'ed instruction has li.reg as an 985 // use operand. Make sure we rewrite that as well. 986 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 987 MachineOperand &MO = MI->getOperand(i); 988 if (!MO.isReg()) 989 continue; 990 unsigned Reg = MO.getReg(); 991 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 992 continue; 993 if (!vrm.isReMaterialized(Reg)) 994 continue; 995 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 996 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 997 if (UseMO) 998 UseMO->setReg(NewVReg); 999 } 1000} 1001 1002/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1003/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1004bool LiveIntervals:: 1005rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1006 bool TrySplit, SlotIndex index, SlotIndex end, 1007 MachineInstr *MI, 1008 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1009 unsigned Slot, int LdSlot, 1010 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1011 VirtRegMap &vrm, 1012 const TargetRegisterClass* rc, 1013 SmallVector<int, 4> &ReMatIds, 1014 const MachineLoopInfo *loopInfo, 1015 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1016 DenseMap<unsigned,unsigned> &MBBVRegsMap, 1017 std::vector<LiveInterval*> &NewLIs) { 1018 bool CanFold = false; 1019 RestartInstruction: 1020 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1021 MachineOperand& mop = MI->getOperand(i); 1022 if (!mop.isReg()) 1023 continue; 1024 unsigned Reg = mop.getReg(); 1025 unsigned RegI = Reg; 1026 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1027 continue; 1028 if (Reg != li.reg) 1029 continue; 1030 1031 bool TryFold = !DefIsReMat; 1032 bool FoldSS = true; // Default behavior unless it's a remat. 1033 int FoldSlot = Slot; 1034 if (DefIsReMat) { 1035 // If this is the rematerializable definition MI itself and 1036 // all of its uses are rematerialized, simply delete it. 1037 if (MI == ReMatOrigDefMI && CanDelete) { 1038 DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: " 1039 << MI << '\n'); 1040 RemoveMachineInstrFromMaps(MI); 1041 vrm.RemoveMachineInstrFromMaps(MI); 1042 MI->eraseFromParent(); 1043 break; 1044 } 1045 1046 // If def for this use can't be rematerialized, then try folding. 1047 // If def is rematerializable and it's a load, also try folding. 1048 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1049 if (isLoad) { 1050 // Try fold loads (from stack slot, constant pool, etc.) into uses. 1051 FoldSS = isLoadSS; 1052 FoldSlot = LdSlot; 1053 } 1054 } 1055 1056 // Scan all of the operands of this instruction rewriting operands 1057 // to use NewVReg instead of li.reg as appropriate. We do this for 1058 // two reasons: 1059 // 1060 // 1. If the instr reads the same spilled vreg multiple times, we 1061 // want to reuse the NewVReg. 1062 // 2. If the instr is a two-addr instruction, we are required to 1063 // keep the src/dst regs pinned. 1064 // 1065 // Keep track of whether we replace a use and/or def so that we can 1066 // create the spill interval with the appropriate range. 1067 1068 HasUse = mop.isUse(); 1069 HasDef = mop.isDef(); 1070 SmallVector<unsigned, 2> Ops; 1071 Ops.push_back(i); 1072 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1073 const MachineOperand &MOj = MI->getOperand(j); 1074 if (!MOj.isReg()) 1075 continue; 1076 unsigned RegJ = MOj.getReg(); 1077 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1078 continue; 1079 if (RegJ == RegI) { 1080 Ops.push_back(j); 1081 if (!MOj.isUndef()) { 1082 HasUse |= MOj.isUse(); 1083 HasDef |= MOj.isDef(); 1084 } 1085 } 1086 } 1087 1088 // Create a new virtual register for the spill interval. 1089 // Create the new register now so we can map the fold instruction 1090 // to the new register so when it is unfolded we get the correct 1091 // answer. 1092 bool CreatedNewVReg = false; 1093 if (NewVReg == 0) { 1094 NewVReg = mri_->createVirtualRegister(rc); 1095 vrm.grow(); 1096 CreatedNewVReg = true; 1097 } 1098 1099 if (!TryFold) 1100 CanFold = false; 1101 else { 1102 // Do not fold load / store here if we are splitting. We'll find an 1103 // optimal point to insert a load / store later. 1104 if (!TrySplit) { 1105 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1106 Ops, FoldSS, FoldSlot, NewVReg)) { 1107 // Folding the load/store can completely change the instruction in 1108 // unpredictable ways, rescan it from the beginning. 1109 1110 if (FoldSS) { 1111 // We need to give the new vreg the same stack slot as the 1112 // spilled interval. 1113 vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 1114 } 1115 1116 HasUse = false; 1117 HasDef = false; 1118 CanFold = false; 1119 if (isNotInMIMap(MI)) 1120 break; 1121 goto RestartInstruction; 1122 } 1123 } else { 1124 // We'll try to fold it later if it's profitable. 1125 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1126 } 1127 } 1128 1129 mop.setReg(NewVReg); 1130 if (mop.isImplicit()) 1131 rewriteImplicitOps(li, MI, NewVReg, vrm); 1132 1133 // Reuse NewVReg for other reads. 1134 for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1135 MachineOperand &mopj = MI->getOperand(Ops[j]); 1136 mopj.setReg(NewVReg); 1137 if (mopj.isImplicit()) 1138 rewriteImplicitOps(li, MI, NewVReg, vrm); 1139 } 1140 1141 if (CreatedNewVReg) { 1142 if (DefIsReMat) { 1143 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1144 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 1145 // Each valnum may have its own remat id. 1146 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 1147 } else { 1148 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 1149 } 1150 if (!CanDelete || (HasUse && HasDef)) { 1151 // If this is a two-addr instruction then its use operands are 1152 // rematerializable but its def is not. It should be assigned a 1153 // stack slot. 1154 vrm.assignVirt2StackSlot(NewVReg, Slot); 1155 } 1156 } else { 1157 vrm.assignVirt2StackSlot(NewVReg, Slot); 1158 } 1159 } else if (HasUse && HasDef && 1160 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1161 // If this interval hasn't been assigned a stack slot (because earlier 1162 // def is a deleted remat def), do it now. 1163 assert(Slot != VirtRegMap::NO_STACK_SLOT); 1164 vrm.assignVirt2StackSlot(NewVReg, Slot); 1165 } 1166 1167 // Re-matting an instruction with virtual register use. Add the 1168 // register as an implicit use on the use MI. 1169 if (DefIsReMat && ImpUse) 1170 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1171 1172 // Create a new register interval for this spill / remat. 1173 LiveInterval &nI = getOrCreateInterval(NewVReg); 1174 if (CreatedNewVReg) { 1175 NewLIs.push_back(&nI); 1176 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 1177 if (TrySplit) 1178 vrm.setIsSplitFromReg(NewVReg, li.reg); 1179 } 1180 1181 if (HasUse) { 1182 if (CreatedNewVReg) { 1183 LiveRange LR(index.getLoadIndex(), index.getDefIndex(), 1184 nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 1185 DEBUG(errs() << " +" << LR); 1186 nI.addRange(LR); 1187 } else { 1188 // Extend the split live interval to this def / use. 1189 SlotIndex End = index.getDefIndex(); 1190 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 1191 nI.getValNumInfo(nI.getNumValNums()-1)); 1192 DEBUG(errs() << " +" << LR); 1193 nI.addRange(LR); 1194 } 1195 } 1196 if (HasDef) { 1197 LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1198 nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); 1199 DEBUG(errs() << " +" << LR); 1200 nI.addRange(LR); 1201 } 1202 1203 DEBUG({ 1204 errs() << "\t\t\t\tAdded new interval: "; 1205 nI.print(errs(), tri_); 1206 errs() << '\n'; 1207 }); 1208 } 1209 return CanFold; 1210} 1211bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 1212 const VNInfo *VNI, 1213 MachineBasicBlock *MBB, 1214 SlotIndex Idx) const { 1215 SlotIndex End = getMBBEndIdx(MBB); 1216 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1217 if (VNI->kills[j].isPHI()) 1218 continue; 1219 1220 SlotIndex KillIdx = VNI->kills[j]; 1221 if (KillIdx > Idx && KillIdx < End) 1222 return true; 1223 } 1224 return false; 1225} 1226 1227/// RewriteInfo - Keep track of machine instrs that will be rewritten 1228/// during spilling. 1229namespace { 1230 struct RewriteInfo { 1231 SlotIndex Index; 1232 MachineInstr *MI; 1233 bool HasUse; 1234 bool HasDef; 1235 RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d) 1236 : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1237 }; 1238 1239 struct RewriteInfoCompare { 1240 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1241 return LHS.Index < RHS.Index; 1242 } 1243 }; 1244} 1245 1246void LiveIntervals:: 1247rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1248 LiveInterval::Ranges::const_iterator &I, 1249 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1250 unsigned Slot, int LdSlot, 1251 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1252 VirtRegMap &vrm, 1253 const TargetRegisterClass* rc, 1254 SmallVector<int, 4> &ReMatIds, 1255 const MachineLoopInfo *loopInfo, 1256 BitVector &SpillMBBs, 1257 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 1258 BitVector &RestoreMBBs, 1259 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1260 DenseMap<unsigned,unsigned> &MBBVRegsMap, 1261 std::vector<LiveInterval*> &NewLIs) { 1262 bool AllCanFold = true; 1263 unsigned NewVReg = 0; 1264 SlotIndex start = I->start.getBaseIndex(); 1265 SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); 1266 1267 // First collect all the def / use in this live range that will be rewritten. 1268 // Make sure they are sorted according to instruction index. 1269 std::vector<RewriteInfo> RewriteMIs; 1270 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1271 re = mri_->reg_end(); ri != re; ) { 1272 MachineInstr *MI = &*ri; 1273 MachineOperand &O = ri.getOperand(); 1274 ++ri; 1275 assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1276 SlotIndex index = getInstructionIndex(MI); 1277 if (index < start || index >= end) 1278 continue; 1279 1280 if (O.isUndef()) 1281 // Must be defined by an implicit def. It should not be spilled. Note, 1282 // this is for correctness reason. e.g. 1283 // 8 %reg1024<def> = IMPLICIT_DEF 1284 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 1285 // The live range [12, 14) are not part of the r1024 live interval since 1286 // it's defined by an implicit def. It will not conflicts with live 1287 // interval of r1025. Now suppose both registers are spilled, you can 1288 // easily see a situation where both registers are reloaded before 1289 // the INSERT_SUBREG and both target registers that would overlap. 1290 continue; 1291 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1292 } 1293 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1294 1295 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1296 // Now rewrite the defs and uses. 1297 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1298 RewriteInfo &rwi = RewriteMIs[i]; 1299 ++i; 1300 SlotIndex index = rwi.Index; 1301 bool MIHasUse = rwi.HasUse; 1302 bool MIHasDef = rwi.HasDef; 1303 MachineInstr *MI = rwi.MI; 1304 // If MI def and/or use the same register multiple times, then there 1305 // are multiple entries. 1306 unsigned NumUses = MIHasUse; 1307 while (i != e && RewriteMIs[i].MI == MI) { 1308 assert(RewriteMIs[i].Index == index); 1309 bool isUse = RewriteMIs[i].HasUse; 1310 if (isUse) ++NumUses; 1311 MIHasUse |= isUse; 1312 MIHasDef |= RewriteMIs[i].HasDef; 1313 ++i; 1314 } 1315 MachineBasicBlock *MBB = MI->getParent(); 1316 1317 if (ImpUse && MI != ReMatDefMI) { 1318 // Re-matting an instruction with virtual register use. Update the 1319 // register interval's spill weight to HUGE_VALF to prevent it from 1320 // being spilled. 1321 LiveInterval &ImpLi = getInterval(ImpUse); 1322 ImpLi.weight = HUGE_VALF; 1323 } 1324 1325 unsigned MBBId = MBB->getNumber(); 1326 unsigned ThisVReg = 0; 1327 if (TrySplit) { 1328 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 1329 if (NVI != MBBVRegsMap.end()) { 1330 ThisVReg = NVI->second; 1331 // One common case: 1332 // x = use 1333 // ... 1334 // ... 1335 // def = ... 1336 // = use 1337 // It's better to start a new interval to avoid artifically 1338 // extend the new interval. 1339 if (MIHasDef && !MIHasUse) { 1340 MBBVRegsMap.erase(MBB->getNumber()); 1341 ThisVReg = 0; 1342 } 1343 } 1344 } 1345 1346 bool IsNew = ThisVReg == 0; 1347 if (IsNew) { 1348 // This ends the previous live interval. If all of its def / use 1349 // can be folded, give it a low spill weight. 1350 if (NewVReg && TrySplit && AllCanFold) { 1351 LiveInterval &nI = getOrCreateInterval(NewVReg); 1352 nI.weight /= 10.0F; 1353 } 1354 AllCanFold = true; 1355 } 1356 NewVReg = ThisVReg; 1357 1358 bool HasDef = false; 1359 bool HasUse = false; 1360 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1361 index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1362 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1363 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1364 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 1365 if (!HasDef && !HasUse) 1366 continue; 1367 1368 AllCanFold &= CanFold; 1369 1370 // Update weight of spill interval. 1371 LiveInterval &nI = getOrCreateInterval(NewVReg); 1372 if (!TrySplit) { 1373 // The spill weight is now infinity as it cannot be spilled again. 1374 nI.weight = HUGE_VALF; 1375 continue; 1376 } 1377 1378 // Keep track of the last def and first use in each MBB. 1379 if (HasDef) { 1380 if (MI != ReMatOrigDefMI || !CanDelete) { 1381 bool HasKill = false; 1382 if (!HasUse) 1383 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex()); 1384 else { 1385 // If this is a two-address code, then this index starts a new VNInfo. 1386 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex()); 1387 if (VNI) 1388 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex()); 1389 } 1390 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1391 SpillIdxes.find(MBBId); 1392 if (!HasKill) { 1393 if (SII == SpillIdxes.end()) { 1394 std::vector<SRInfo> S; 1395 S.push_back(SRInfo(index, NewVReg, true)); 1396 SpillIdxes.insert(std::make_pair(MBBId, S)); 1397 } else if (SII->second.back().vreg != NewVReg) { 1398 SII->second.push_back(SRInfo(index, NewVReg, true)); 1399 } else if (index > SII->second.back().index) { 1400 // If there is an earlier def and this is a two-address 1401 // instruction, then it's not possible to fold the store (which 1402 // would also fold the load). 1403 SRInfo &Info = SII->second.back(); 1404 Info.index = index; 1405 Info.canFold = !HasUse; 1406 } 1407 SpillMBBs.set(MBBId); 1408 } else if (SII != SpillIdxes.end() && 1409 SII->second.back().vreg == NewVReg && 1410 index > SII->second.back().index) { 1411 // There is an earlier def that's not killed (must be two-address). 1412 // The spill is no longer needed. 1413 SII->second.pop_back(); 1414 if (SII->second.empty()) { 1415 SpillIdxes.erase(MBBId); 1416 SpillMBBs.reset(MBBId); 1417 } 1418 } 1419 } 1420 } 1421 1422 if (HasUse) { 1423 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1424 SpillIdxes.find(MBBId); 1425 if (SII != SpillIdxes.end() && 1426 SII->second.back().vreg == NewVReg && 1427 index > SII->second.back().index) 1428 // Use(s) following the last def, it's not safe to fold the spill. 1429 SII->second.back().canFold = false; 1430 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 1431 RestoreIdxes.find(MBBId); 1432 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 1433 // If we are splitting live intervals, only fold if it's the first 1434 // use and there isn't another use later in the MBB. 1435 RII->second.back().canFold = false; 1436 else if (IsNew) { 1437 // Only need a reload if there isn't an earlier def / use. 1438 if (RII == RestoreIdxes.end()) { 1439 std::vector<SRInfo> Infos; 1440 Infos.push_back(SRInfo(index, NewVReg, true)); 1441 RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 1442 } else { 1443 RII->second.push_back(SRInfo(index, NewVReg, true)); 1444 } 1445 RestoreMBBs.set(MBBId); 1446 } 1447 } 1448 1449 // Update spill weight. 1450 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1451 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1452 } 1453 1454 if (NewVReg && TrySplit && AllCanFold) { 1455 // If all of its def / use can be folded, give it a low spill weight. 1456 LiveInterval &nI = getOrCreateInterval(NewVReg); 1457 nI.weight /= 10.0F; 1458 } 1459} 1460 1461bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index, 1462 unsigned vr, BitVector &RestoreMBBs, 1463 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1464 if (!RestoreMBBs[Id]) 1465 return false; 1466 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1467 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1468 if (Restores[i].index == index && 1469 Restores[i].vreg == vr && 1470 Restores[i].canFold) 1471 return true; 1472 return false; 1473} 1474 1475void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index, 1476 unsigned vr, BitVector &RestoreMBBs, 1477 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1478 if (!RestoreMBBs[Id]) 1479 return; 1480 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1481 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1482 if (Restores[i].index == index && Restores[i].vreg) 1483 Restores[i].index = SlotIndex(); 1484} 1485 1486/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 1487/// spilled and create empty intervals for their uses. 1488void 1489LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 1490 const TargetRegisterClass* rc, 1491 std::vector<LiveInterval*> &NewLIs) { 1492 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1493 re = mri_->reg_end(); ri != re; ) { 1494 MachineOperand &O = ri.getOperand(); 1495 MachineInstr *MI = &*ri; 1496 ++ri; 1497 if (O.isDef()) { 1498 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 1499 "Register def was not rewritten?"); 1500 RemoveMachineInstrFromMaps(MI); 1501 vrm.RemoveMachineInstrFromMaps(MI); 1502 MI->eraseFromParent(); 1503 } else { 1504 // This must be an use of an implicit_def so it's not part of the live 1505 // interval. Create a new empty live interval for it. 1506 // FIXME: Can we simply erase some of the instructions? e.g. Stores? 1507 unsigned NewVReg = mri_->createVirtualRegister(rc); 1508 vrm.grow(); 1509 vrm.setIsImplicitlyDefined(NewVReg); 1510 NewLIs.push_back(&getOrCreateInterval(NewVReg)); 1511 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1512 MachineOperand &MO = MI->getOperand(i); 1513 if (MO.isReg() && MO.getReg() == li.reg) { 1514 MO.setReg(NewVReg); 1515 MO.setIsUndef(); 1516 } 1517 } 1518 } 1519 } 1520} 1521 1522std::vector<LiveInterval*> LiveIntervals:: 1523addIntervalsForSpillsFast(const LiveInterval &li, 1524 const MachineLoopInfo *loopInfo, 1525 VirtRegMap &vrm) { 1526 unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1527 1528 std::vector<LiveInterval*> added; 1529 1530 assert(li.weight != HUGE_VALF && 1531 "attempt to spill already spilled interval!"); 1532 1533 DEBUG({ 1534 errs() << "\t\t\t\tadding intervals for spills for interval: "; 1535 li.dump(); 1536 errs() << '\n'; 1537 }); 1538 1539 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1540 1541 MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1542 while (RI != mri_->reg_end()) { 1543 MachineInstr* MI = &*RI; 1544 1545 SmallVector<unsigned, 2> Indices; 1546 bool HasUse = false; 1547 bool HasDef = false; 1548 1549 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1550 MachineOperand& mop = MI->getOperand(i); 1551 if (!mop.isReg() || mop.getReg() != li.reg) continue; 1552 1553 HasUse |= MI->getOperand(i).isUse(); 1554 HasDef |= MI->getOperand(i).isDef(); 1555 1556 Indices.push_back(i); 1557 } 1558 1559 if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1560 Indices, true, slot, li.reg)) { 1561 unsigned NewVReg = mri_->createVirtualRegister(rc); 1562 vrm.grow(); 1563 vrm.assignVirt2StackSlot(NewVReg, slot); 1564 1565 // create a new register for this spill 1566 LiveInterval &nI = getOrCreateInterval(NewVReg); 1567 1568 // the spill weight is now infinity as it 1569 // cannot be spilled again 1570 nI.weight = HUGE_VALF; 1571 1572 // Rewrite register operands to use the new vreg. 1573 for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1574 E = Indices.end(); I != E; ++I) { 1575 MI->getOperand(*I).setReg(NewVReg); 1576 1577 if (MI->getOperand(*I).isUse()) 1578 MI->getOperand(*I).setIsKill(true); 1579 } 1580 1581 // Fill in the new live interval. 1582 SlotIndex index = getInstructionIndex(MI); 1583 if (HasUse) { 1584 LiveRange LR(index.getLoadIndex(), index.getUseIndex(), 1585 nI.getNextValue(SlotIndex(), 0, false, 1586 getVNInfoAllocator())); 1587 DEBUG(errs() << " +" << LR); 1588 nI.addRange(LR); 1589 vrm.addRestorePoint(NewVReg, MI); 1590 } 1591 if (HasDef) { 1592 LiveRange LR(index.getDefIndex(), index.getStoreIndex(), 1593 nI.getNextValue(SlotIndex(), 0, false, 1594 getVNInfoAllocator())); 1595 DEBUG(errs() << " +" << LR); 1596 nI.addRange(LR); 1597 vrm.addSpillPoint(NewVReg, true, MI); 1598 } 1599 1600 added.push_back(&nI); 1601 1602 DEBUG({ 1603 errs() << "\t\t\t\tadded new interval: "; 1604 nI.dump(); 1605 errs() << '\n'; 1606 }); 1607 } 1608 1609 1610 RI = mri_->reg_begin(li.reg); 1611 } 1612 1613 return added; 1614} 1615 1616std::vector<LiveInterval*> LiveIntervals:: 1617addIntervalsForSpills(const LiveInterval &li, 1618 SmallVectorImpl<LiveInterval*> &SpillIs, 1619 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1620 1621 if (EnableFastSpilling) 1622 return addIntervalsForSpillsFast(li, loopInfo, vrm); 1623 1624 assert(li.weight != HUGE_VALF && 1625 "attempt to spill already spilled interval!"); 1626 1627 DEBUG({ 1628 errs() << "\t\t\t\tadding intervals for spills for interval: "; 1629 li.print(errs(), tri_); 1630 errs() << '\n'; 1631 }); 1632 1633 // Each bit specify whether a spill is required in the MBB. 1634 BitVector SpillMBBs(mf_->getNumBlockIDs()); 1635 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 1636 BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1637 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1638 DenseMap<unsigned,unsigned> MBBVRegsMap; 1639 std::vector<LiveInterval*> NewLIs; 1640 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1641 1642 unsigned NumValNums = li.getNumValNums(); 1643 SmallVector<MachineInstr*, 4> ReMatDefs; 1644 ReMatDefs.resize(NumValNums, NULL); 1645 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1646 ReMatOrigDefs.resize(NumValNums, NULL); 1647 SmallVector<int, 4> ReMatIds; 1648 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1649 BitVector ReMatDelete(NumValNums); 1650 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1651 1652 // Spilling a split live interval. It cannot be split any further. Also, 1653 // it's also guaranteed to be a single val# / range interval. 1654 if (vrm.getPreSplitReg(li.reg)) { 1655 vrm.setIsSplitFromReg(li.reg, 0); 1656 // Unset the split kill marker on the last use. 1657 SlotIndex KillIdx = vrm.getKillPoint(li.reg); 1658 if (KillIdx != SlotIndex()) { 1659 MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1660 assert(KillMI && "Last use disappeared?"); 1661 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1662 assert(KillOp != -1 && "Last use disappeared?"); 1663 KillMI->getOperand(KillOp).setIsKill(false); 1664 } 1665 vrm.removeKillPoint(li.reg); 1666 bool DefIsReMat = vrm.isReMaterialized(li.reg); 1667 Slot = vrm.getStackSlot(li.reg); 1668 assert(Slot != VirtRegMap::MAX_STACK_SLOT); 1669 MachineInstr *ReMatDefMI = DefIsReMat ? 1670 vrm.getReMaterializedMI(li.reg) : NULL; 1671 int LdSlot = 0; 1672 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1673 bool isLoad = isLoadSS || 1674 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 1675 bool IsFirstRange = true; 1676 for (LiveInterval::Ranges::const_iterator 1677 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1678 // If this is a split live interval with multiple ranges, it means there 1679 // are two-address instructions that re-defined the value. Only the 1680 // first def can be rematerialized! 1681 if (IsFirstRange) { 1682 // Note ReMatOrigDefMI has already been deleted. 1683 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 1684 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1685 false, vrm, rc, ReMatIds, loopInfo, 1686 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1687 MBBVRegsMap, NewLIs); 1688 } else { 1689 rewriteInstructionsForSpills(li, false, I, NULL, 0, 1690 Slot, 0, false, false, false, 1691 false, vrm, rc, ReMatIds, loopInfo, 1692 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1693 MBBVRegsMap, NewLIs); 1694 } 1695 IsFirstRange = false; 1696 } 1697 1698 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1699 return NewLIs; 1700 } 1701 1702 bool TrySplit = !intervalIsInOneMBB(li); 1703 if (TrySplit) 1704 ++numSplits; 1705 bool NeedStackSlot = false; 1706 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1707 i != e; ++i) { 1708 const VNInfo *VNI = *i; 1709 unsigned VN = VNI->id; 1710 if (VNI->isUnused()) 1711 continue; // Dead val#. 1712 // Is the def for the val# rematerializable? 1713 MachineInstr *ReMatDefMI = VNI->isDefAccurate() 1714 ? getInstructionFromIndex(VNI->def) : 0; 1715 bool dummy; 1716 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1717 // Remember how to remat the def of this val#. 1718 ReMatOrigDefs[VN] = ReMatDefMI; 1719 // Original def may be modified so we have to make a copy here. 1720 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 1721 CloneMIs.push_back(Clone); 1722 ReMatDefs[VN] = Clone; 1723 1724 bool CanDelete = true; 1725 if (VNI->hasPHIKill()) { 1726 // A kill is a phi node, not all of its uses can be rematerialized. 1727 // It must not be deleted. 1728 CanDelete = false; 1729 // Need a stack slot if there is any live range where uses cannot be 1730 // rematerialized. 1731 NeedStackSlot = true; 1732 } 1733 if (CanDelete) 1734 ReMatDelete.set(VN); 1735 } else { 1736 // Need a stack slot if there is any live range where uses cannot be 1737 // rematerialized. 1738 NeedStackSlot = true; 1739 } 1740 } 1741 1742 // One stack slot per live interval. 1743 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1744 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 1745 Slot = vrm.assignVirt2StackSlot(li.reg); 1746 1747 // This case only occurs when the prealloc splitter has already assigned 1748 // a stack slot to this vreg. 1749 else 1750 Slot = vrm.getStackSlot(li.reg); 1751 } 1752 1753 // Create new intervals and rewrite defs and uses. 1754 for (LiveInterval::Ranges::const_iterator 1755 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1756 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 1757 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 1758 bool DefIsReMat = ReMatDefMI != NULL; 1759 bool CanDelete = ReMatDelete[I->valno->id]; 1760 int LdSlot = 0; 1761 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1762 bool isLoad = isLoadSS || 1763 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 1764 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 1765 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1766 CanDelete, vrm, rc, ReMatIds, loopInfo, 1767 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1768 MBBVRegsMap, NewLIs); 1769 } 1770 1771 // Insert spills / restores if we are splitting. 1772 if (!TrySplit) { 1773 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1774 return NewLIs; 1775 } 1776 1777 SmallPtrSet<LiveInterval*, 4> AddedKill; 1778 SmallVector<unsigned, 2> Ops; 1779 if (NeedStackSlot) { 1780 int Id = SpillMBBs.find_first(); 1781 while (Id != -1) { 1782 std::vector<SRInfo> &spills = SpillIdxes[Id]; 1783 for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1784 SlotIndex index = spills[i].index; 1785 unsigned VReg = spills[i].vreg; 1786 LiveInterval &nI = getOrCreateInterval(VReg); 1787 bool isReMat = vrm.isReMaterialized(VReg); 1788 MachineInstr *MI = getInstructionFromIndex(index); 1789 bool CanFold = false; 1790 bool FoundUse = false; 1791 Ops.clear(); 1792 if (spills[i].canFold) { 1793 CanFold = true; 1794 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1795 MachineOperand &MO = MI->getOperand(j); 1796 if (!MO.isReg() || MO.getReg() != VReg) 1797 continue; 1798 1799 Ops.push_back(j); 1800 if (MO.isDef()) 1801 continue; 1802 if (isReMat || 1803 (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1804 RestoreMBBs, RestoreIdxes))) { 1805 // MI has two-address uses of the same register. If the use 1806 // isn't the first and only use in the BB, then we can't fold 1807 // it. FIXME: Move this to rewriteInstructionsForSpills. 1808 CanFold = false; 1809 break; 1810 } 1811 FoundUse = true; 1812 } 1813 } 1814 // Fold the store into the def if possible. 1815 bool Folded = false; 1816 if (CanFold && !Ops.empty()) { 1817 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1818 Folded = true; 1819 if (FoundUse) { 1820 // Also folded uses, do not issue a load. 1821 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1822 nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1823 } 1824 nI.removeRange(index.getDefIndex(), index.getStoreIndex()); 1825 } 1826 } 1827 1828 // Otherwise tell the spiller to issue a spill. 1829 if (!Folded) { 1830 LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1831 bool isKill = LR->end == index.getStoreIndex(); 1832 if (!MI->registerDefIsDead(nI.reg)) 1833 // No need to spill a dead def. 1834 vrm.addSpillPoint(VReg, isKill, MI); 1835 if (isKill) 1836 AddedKill.insert(&nI); 1837 } 1838 } 1839 Id = SpillMBBs.find_next(Id); 1840 } 1841 } 1842 1843 int Id = RestoreMBBs.find_first(); 1844 while (Id != -1) { 1845 std::vector<SRInfo> &restores = RestoreIdxes[Id]; 1846 for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1847 SlotIndex index = restores[i].index; 1848 if (index == SlotIndex()) 1849 continue; 1850 unsigned VReg = restores[i].vreg; 1851 LiveInterval &nI = getOrCreateInterval(VReg); 1852 bool isReMat = vrm.isReMaterialized(VReg); 1853 MachineInstr *MI = getInstructionFromIndex(index); 1854 bool CanFold = false; 1855 Ops.clear(); 1856 if (restores[i].canFold) { 1857 CanFold = true; 1858 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1859 MachineOperand &MO = MI->getOperand(j); 1860 if (!MO.isReg() || MO.getReg() != VReg) 1861 continue; 1862 1863 if (MO.isDef()) { 1864 // If this restore were to be folded, it would have been folded 1865 // already. 1866 CanFold = false; 1867 break; 1868 } 1869 Ops.push_back(j); 1870 } 1871 } 1872 1873 // Fold the load into the use if possible. 1874 bool Folded = false; 1875 if (CanFold && !Ops.empty()) { 1876 if (!isReMat) 1877 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1878 else { 1879 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 1880 int LdSlot = 0; 1881 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1882 // If the rematerializable def is a load, also try to fold it. 1883 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 1884 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1885 Ops, isLoadSS, LdSlot, VReg); 1886 if (!Folded) { 1887 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1888 if (ImpUse) { 1889 // Re-matting an instruction with virtual register use. Add the 1890 // register as an implicit use on the use MI and update the register 1891 // interval's spill weight to HUGE_VALF to prevent it from being 1892 // spilled. 1893 LiveInterval &ImpLi = getInterval(ImpUse); 1894 ImpLi.weight = HUGE_VALF; 1895 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1896 } 1897 } 1898 } 1899 } 1900 // If folding is not possible / failed, then tell the spiller to issue a 1901 // load / rematerialization for us. 1902 if (Folded) 1903 nI.removeRange(index.getLoadIndex(), index.getDefIndex()); 1904 else 1905 vrm.addRestorePoint(VReg, MI); 1906 } 1907 Id = RestoreMBBs.find_next(Id); 1908 } 1909 1910 // Finalize intervals: add kills, finalize spill weights, and filter out 1911 // dead intervals. 1912 std::vector<LiveInterval*> RetNewLIs; 1913 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1914 LiveInterval *LI = NewLIs[i]; 1915 if (!LI->empty()) { 1916 LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI); 1917 if (!AddedKill.count(LI)) { 1918 LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1919 SlotIndex LastUseIdx = LR->end.getBaseIndex(); 1920 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 1921 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1922 assert(UseIdx != -1); 1923 if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 1924 LastUse->getOperand(UseIdx).setIsKill(); 1925 vrm.addKillPoint(LI->reg, LastUseIdx); 1926 } 1927 } 1928 RetNewLIs.push_back(LI); 1929 } 1930 } 1931 1932 handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1933 return RetNewLIs; 1934} 1935 1936/// hasAllocatableSuperReg - Return true if the specified physical register has 1937/// any super register that's allocatable. 1938bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1939 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1940 if (allocatableRegs_[*AS] && hasInterval(*AS)) 1941 return true; 1942 return false; 1943} 1944 1945/// getRepresentativeReg - Find the largest super register of the specified 1946/// physical register. 1947unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1948 // Find the largest super-register that is allocatable. 1949 unsigned BestReg = Reg; 1950 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1951 unsigned SuperReg = *AS; 1952 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1953 BestReg = SuperReg; 1954 break; 1955 } 1956 } 1957 return BestReg; 1958} 1959 1960/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1961/// specified interval that conflicts with the specified physical register. 1962unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1963 unsigned PhysReg) const { 1964 unsigned NumConflicts = 0; 1965 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1966 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1967 E = mri_->reg_end(); I != E; ++I) { 1968 MachineOperand &O = I.getOperand(); 1969 MachineInstr *MI = O.getParent(); 1970 SlotIndex Index = getInstructionIndex(MI); 1971 if (pli.liveAt(Index)) 1972 ++NumConflicts; 1973 } 1974 return NumConflicts; 1975} 1976 1977/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 1978/// around all defs and uses of the specified interval. Return true if it 1979/// was able to cut its interval. 1980bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1981 unsigned PhysReg, VirtRegMap &vrm) { 1982 unsigned SpillReg = getRepresentativeReg(PhysReg); 1983 1984 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1985 // If there are registers which alias PhysReg, but which are not a 1986 // sub-register of the chosen representative super register. Assert 1987 // since we can't handle it yet. 1988 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 1989 tri_->isSuperRegister(*AS, SpillReg)); 1990 1991 bool Cut = false; 1992 SmallVector<unsigned, 4> PRegs; 1993 if (hasInterval(SpillReg)) 1994 PRegs.push_back(SpillReg); 1995 else { 1996 SmallSet<unsigned, 4> Added; 1997 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) 1998 if (Added.insert(*AS) && hasInterval(*AS)) { 1999 PRegs.push_back(*AS); 2000 for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS) 2001 Added.insert(*ASS); 2002 } 2003 } 2004 2005 SmallPtrSet<MachineInstr*, 8> SeenMIs; 2006 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2007 E = mri_->reg_end(); I != E; ++I) { 2008 MachineOperand &O = I.getOperand(); 2009 MachineInstr *MI = O.getParent(); 2010 if (SeenMIs.count(MI)) 2011 continue; 2012 SeenMIs.insert(MI); 2013 SlotIndex Index = getInstructionIndex(MI); 2014 for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { 2015 unsigned PReg = PRegs[i]; 2016 LiveInterval &pli = getInterval(PReg); 2017 if (!pli.liveAt(Index)) 2018 continue; 2019 vrm.addEmergencySpill(PReg, MI); 2020 SlotIndex StartIdx = Index.getLoadIndex(); 2021 SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); 2022 if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 2023 pli.removeRange(StartIdx, EndIdx); 2024 Cut = true; 2025 } else { 2026 std::string msg; 2027 raw_string_ostream Msg(msg); 2028 Msg << "Ran out of registers during register allocation!"; 2029 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 2030 Msg << "\nPlease check your inline asm statement for invalid " 2031 << "constraints:\n"; 2032 MI->print(Msg, tm_); 2033 } 2034 llvm_report_error(Msg.str()); 2035 } 2036 for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) { 2037 if (!hasInterval(*AS)) 2038 continue; 2039 LiveInterval &spli = getInterval(*AS); 2040 if (spli.liveAt(Index)) 2041 spli.removeRange(Index.getLoadIndex(), 2042 Index.getNextIndex().getBaseIndex()); 2043 } 2044 } 2045 } 2046 return Cut; 2047} 2048 2049LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2050 MachineInstr* startInst) { 2051 LiveInterval& Interval = getOrCreateInterval(reg); 2052 VNInfo* VN = Interval.getNextValue( 2053 SlotIndex(getInstructionIndex(startInst).getDefIndex()), 2054 startInst, true, getVNInfoAllocator()); 2055 VN->setHasPHIKill(true); 2056 VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent())); 2057 LiveRange LR( 2058 SlotIndex(getInstructionIndex(startInst).getDefIndex()), 2059 getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN); 2060 Interval.addRange(LR); 2061 2062 return LR; 2063} 2064 |