LiveIntervalAnalysis.cpp revision d062bf740651c35ed3ee80b66b02d8363fd14a3a
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/MachineRegisterInfo.h" 29#include "llvm/CodeGen/Passes.h" 30#include "llvm/CodeGen/PseudoSourceValue.h" 31#include "llvm/Target/TargetRegisterInfo.h" 32#include "llvm/Target/TargetInstrInfo.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/Target/TargetOptions.h" 35#include "llvm/Support/CommandLine.h" 36#include "llvm/Support/Debug.h" 37#include "llvm/Support/ErrorHandling.h" 38#include "llvm/Support/raw_ostream.h" 39#include "llvm/ADT/DepthFirstIterator.h" 40#include "llvm/ADT/SmallSet.h" 41#include "llvm/ADT/Statistic.h" 42#include "llvm/ADT/STLExtras.h" 43#include <algorithm> 44#include <limits> 45#include <cmath> 46using namespace llvm; 47 48// Hidden options for help debugging. 49static cl::opt<bool> DisableReMat("disable-rematerialization", 50 cl::init(false), cl::Hidden); 51 52static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden); 53 54static cl::opt<bool> EnableFastSpilling("fast-spill", 55 cl::init(false), cl::Hidden); 56 57static cl::opt<bool> EarlyCoalescing("early-coalescing", cl::init(false)); 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"); 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 MachineFunctionPass::getAnalysisUsage(AU); 86} 87 88void LiveIntervals::releaseMemory() { 89 // Free the live intervals themselves. 90 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 91 E = r2iMap_.end(); I != E; ++I) 92 delete I->second; 93 94 MBB2IdxMap.clear(); 95 Idx2MBBMap.clear(); 96 mi2iMap_.clear(); 97 i2miMap_.clear(); 98 r2iMap_.clear(); 99 terminatorGaps.clear(); 100 phiJoinCopies.clear(); 101 102 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 103 VNInfoAllocator.Reset(); 104 while (!CloneMIs.empty()) { 105 MachineInstr *MI = CloneMIs.back(); 106 CloneMIs.pop_back(); 107 mf_->DeleteMachineInstr(MI); 108 } 109} 110 111static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg, 112 unsigned OpIdx, const TargetInstrInfo *tii_){ 113 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 114 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 115 Reg == SrcReg) 116 return true; 117 118 if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 119 return true; 120 if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 121 return true; 122 return false; 123} 124 125/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure 126/// there is one implicit_def for each use. Add isUndef marker to 127/// implicit_def defs and their uses. 128void LiveIntervals::processImplicitDefs() { 129 SmallSet<unsigned, 8> ImpDefRegs; 130 SmallVector<MachineInstr*, 8> ImpDefMIs; 131 MachineBasicBlock *Entry = mf_->begin(); 132 SmallPtrSet<MachineBasicBlock*,16> Visited; 133 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 134 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 135 DFI != E; ++DFI) { 136 MachineBasicBlock *MBB = *DFI; 137 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 138 I != E; ) { 139 MachineInstr *MI = &*I; 140 ++I; 141 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 142 unsigned Reg = MI->getOperand(0).getReg(); 143 ImpDefRegs.insert(Reg); 144 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 145 for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS) 146 ImpDefRegs.insert(*SS); 147 } 148 ImpDefMIs.push_back(MI); 149 continue; 150 } 151 152 if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) { 153 MachineOperand &MO = MI->getOperand(2); 154 if (ImpDefRegs.count(MO.getReg())) { 155 // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2 156 // This is an identity copy, eliminate it now. 157 if (MO.isKill()) { 158 LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg()); 159 vi.removeKill(MI); 160 } 161 MI->eraseFromParent(); 162 continue; 163 } 164 } 165 166 bool ChangedToImpDef = false; 167 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 168 MachineOperand& MO = MI->getOperand(i); 169 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) 170 continue; 171 unsigned Reg = MO.getReg(); 172 if (!Reg) 173 continue; 174 if (!ImpDefRegs.count(Reg)) 175 continue; 176 // Use is a copy, just turn it into an implicit_def. 177 if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) { 178 bool isKill = MO.isKill(); 179 MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 180 for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 181 MI->RemoveOperand(j); 182 if (isKill) { 183 ImpDefRegs.erase(Reg); 184 LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg); 185 vi.removeKill(MI); 186 } 187 ChangedToImpDef = true; 188 break; 189 } 190 191 MO.setIsUndef(); 192 if (MO.isKill() || MI->isRegTiedToDefOperand(i)) { 193 // Make sure other uses of 194 for (unsigned j = i+1; j != e; ++j) { 195 MachineOperand &MOJ = MI->getOperand(j); 196 if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg) 197 MOJ.setIsUndef(); 198 } 199 ImpDefRegs.erase(Reg); 200 } 201 } 202 203 if (ChangedToImpDef) { 204 // Backtrack to process this new implicit_def. 205 --I; 206 } else { 207 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 208 MachineOperand& MO = MI->getOperand(i); 209 if (!MO.isReg() || !MO.isDef()) 210 continue; 211 ImpDefRegs.erase(MO.getReg()); 212 } 213 } 214 } 215 216 // Any outstanding liveout implicit_def's? 217 for (unsigned i = 0, e = ImpDefMIs.size(); i != e; ++i) { 218 MachineInstr *MI = ImpDefMIs[i]; 219 unsigned Reg = MI->getOperand(0).getReg(); 220 if (TargetRegisterInfo::isPhysicalRegister(Reg) || 221 !ImpDefRegs.count(Reg)) { 222 // Delete all "local" implicit_def's. That include those which define 223 // physical registers since they cannot be liveout. 224 MI->eraseFromParent(); 225 continue; 226 } 227 228 // If there are multiple defs of the same register and at least one 229 // is not an implicit_def, do not insert implicit_def's before the 230 // uses. 231 bool Skip = false; 232 for (MachineRegisterInfo::def_iterator DI = mri_->def_begin(Reg), 233 DE = mri_->def_end(); DI != DE; ++DI) { 234 if (DI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { 235 Skip = true; 236 break; 237 } 238 } 239 if (Skip) 240 continue; 241 242 // The only implicit_def which we want to keep are those that are live 243 // out of its block. 244 MI->eraseFromParent(); 245 246 for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), 247 UE = mri_->use_end(); UI != UE; ) { 248 MachineOperand &RMO = UI.getOperand(); 249 MachineInstr *RMI = &*UI; 250 ++UI; 251 MachineBasicBlock *RMBB = RMI->getParent(); 252 if (RMBB == MBB) 253 continue; 254 255 // Turn a copy use into an implicit_def. 256 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 257 if (tii_->isMoveInstr(*RMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 258 Reg == SrcReg) { 259 RMI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF)); 260 for (int j = RMI->getNumOperands() - 1, ee = 0; j > ee; --j) 261 RMI->RemoveOperand(j); 262 continue; 263 } 264 265 const TargetRegisterClass* RC = mri_->getRegClass(Reg); 266 unsigned NewVReg = mri_->createVirtualRegister(RC); 267 RMO.setReg(NewVReg); 268 RMO.setIsUndef(); 269 RMO.setIsKill(); 270 } 271 } 272 ImpDefRegs.clear(); 273 ImpDefMIs.clear(); 274 } 275} 276 277 278void LiveIntervals::computeNumbering() { 279 Index2MiMap OldI2MI = i2miMap_; 280 std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; 281 282 Idx2MBBMap.clear(); 283 MBB2IdxMap.clear(); 284 mi2iMap_.clear(); 285 i2miMap_.clear(); 286 terminatorGaps.clear(); 287 phiJoinCopies.clear(); 288 289 FunctionSize = 0; 290 291 // Number MachineInstrs and MachineBasicBlocks. 292 // Initialize MBB indexes to a sentinal. 293 MBB2IdxMap.resize(mf_->getNumBlockIDs(), 294 std::make_pair(MachineInstrIndex(),MachineInstrIndex())); 295 296 MachineInstrIndex MIIndex; 297 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 298 MBB != E; ++MBB) { 299 MachineInstrIndex StartIdx = MIIndex; 300 301 // Insert an empty slot at the beginning of each block. 302 MIIndex = getNextIndex(MIIndex); 303 i2miMap_.push_back(0); 304 305 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 306 I != E; ++I) { 307 308 if (I == MBB->getFirstTerminator()) { 309 // Leave a gap for before terminators, this is where we will point 310 // PHI kills. 311 MachineInstrIndex tGap(true, MIIndex); 312 bool inserted = 313 terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second; 314 assert(inserted && 315 "Multiple 'first' terminators encountered during numbering."); 316 inserted = inserted; // Avoid compiler warning if assertions turned off. 317 i2miMap_.push_back(0); 318 319 MIIndex = getNextIndex(MIIndex); 320 } 321 322 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 323 assert(inserted && "multiple MachineInstr -> index mappings"); 324 inserted = true; 325 i2miMap_.push_back(I); 326 MIIndex = getNextIndex(MIIndex); 327 FunctionSize++; 328 329 // Insert max(1, numdefs) empty slots after every instruction. 330 unsigned Slots = I->getDesc().getNumDefs(); 331 if (Slots == 0) 332 Slots = 1; 333 while (Slots--) { 334 MIIndex = getNextIndex(MIIndex); 335 i2miMap_.push_back(0); 336 } 337 338 } 339 340 if (MBB->getFirstTerminator() == MBB->end()) { 341 // Leave a gap for before terminators, this is where we will point 342 // PHI kills. 343 MachineInstrIndex tGap(true, MIIndex); 344 bool inserted = 345 terminatorGaps.insert(std::make_pair(&*MBB, tGap)).second; 346 assert(inserted && 347 "Multiple 'first' terminators encountered during numbering."); 348 inserted = inserted; // Avoid compiler warning if assertions turned off. 349 i2miMap_.push_back(0); 350 351 MIIndex = getNextIndex(MIIndex); 352 } 353 354 // Set the MBB2IdxMap entry for this MBB. 355 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, getPrevSlot(MIIndex)); 356 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 357 } 358 359 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 360 361 if (!OldI2MI.empty()) 362 for (iterator OI = begin(), OE = end(); OI != OE; ++OI) { 363 for (LiveInterval::iterator LI = OI->second->begin(), 364 LE = OI->second->end(); LI != LE; ++LI) { 365 366 // Remap the start index of the live range to the corresponding new 367 // number, or our best guess at what it _should_ correspond to if the 368 // original instruction has been erased. This is either the following 369 // instruction or its predecessor. 370 unsigned index = LI->start.getVecIndex(); 371 MachineInstrIndex::Slot offset = LI->start.getSlot(); 372 if (LI->start.isLoad()) { 373 std::vector<IdxMBBPair>::const_iterator I = 374 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); 375 // Take the pair containing the index 376 std::vector<IdxMBBPair>::const_iterator J = 377 (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 378 379 LI->start = getMBBStartIdx(J->second); 380 } else { 381 LI->start = MachineInstrIndex( 382 MachineInstrIndex(mi2iMap_[OldI2MI[index]]), 383 (MachineInstrIndex::Slot)offset); 384 } 385 386 // Remap the ending index in the same way that we remapped the start, 387 // except for the final step where we always map to the immediately 388 // following instruction. 389 index = (getPrevSlot(LI->end)).getVecIndex(); 390 offset = LI->end.getSlot(); 391 if (LI->end.isLoad()) { 392 // VReg dies at end of block. 393 std::vector<IdxMBBPair>::const_iterator I = 394 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); 395 --I; 396 397 LI->end = getNextSlot(getMBBEndIdx(I->second)); 398 } else { 399 unsigned idx = index; 400 while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 401 402 if (index != OldI2MI.size()) 403 LI->end = 404 MachineInstrIndex(mi2iMap_[OldI2MI[index]], 405 (idx == index ? offset : MachineInstrIndex::LOAD)); 406 else 407 LI->end = 408 MachineInstrIndex(MachineInstrIndex::NUM * i2miMap_.size()); 409 } 410 } 411 412 for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), 413 VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 414 VNInfo* vni = *VNI; 415 416 // Remap the VNInfo def index, which works the same as the 417 // start indices above. VN's with special sentinel defs 418 // don't need to be remapped. 419 if (vni->isDefAccurate() && !vni->isUnused()) { 420 unsigned index = vni->def.getVecIndex(); 421 MachineInstrIndex::Slot offset = vni->def.getSlot(); 422 if (vni->def.isLoad()) { 423 std::vector<IdxMBBPair>::const_iterator I = 424 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); 425 // Take the pair containing the index 426 std::vector<IdxMBBPair>::const_iterator J = 427 (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 428 429 vni->def = getMBBStartIdx(J->second); 430 } else { 431 vni->def = MachineInstrIndex(mi2iMap_[OldI2MI[index]], offset); 432 } 433 } 434 435 // Remap the VNInfo kill indices, which works the same as 436 // the end indices above. 437 for (size_t i = 0; i < vni->kills.size(); ++i) { 438 unsigned index = getPrevSlot(vni->kills[i]).getVecIndex(); 439 MachineInstrIndex::Slot offset = vni->kills[i].getSlot(); 440 441 if (vni->kills[i].isLoad()) { 442 assert("Value killed at a load slot."); 443 /*std::vector<IdxMBBPair>::const_iterator I = 444 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); 445 --I; 446 447 vni->kills[i] = getMBBEndIdx(I->second);*/ 448 } else { 449 if (vni->kills[i].isPHIIndex()) { 450 std::vector<IdxMBBPair>::const_iterator I = 451 std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); 452 --I; 453 vni->kills[i] = terminatorGaps[I->second]; 454 } else { 455 assert(OldI2MI[index] != 0 && 456 "Kill refers to instruction not present in index maps."); 457 vni->kills[i] = MachineInstrIndex(mi2iMap_[OldI2MI[index]], offset); 458 } 459 460 /* 461 unsigned idx = index; 462 while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 463 464 if (index != OldI2MI.size()) 465 vni->kills[i] = mi2iMap_[OldI2MI[index]] + 466 (idx == index ? offset : 0); 467 else 468 vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); 469 */ 470 } 471 } 472 } 473 } 474} 475 476void LiveIntervals::scaleNumbering(int factor) { 477 // Need to 478 // * scale MBB begin and end points 479 // * scale all ranges. 480 // * Update VNI structures. 481 // * Scale instruction numberings 482 483 // Scale the MBB indices. 484 Idx2MBBMap.clear(); 485 for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end(); 486 MBB != MBBE; ++MBB) { 487 std::pair<MachineInstrIndex, MachineInstrIndex> &mbbIndices = MBB2IdxMap[MBB->getNumber()]; 488 mbbIndices.first = mbbIndices.first.scale(factor); 489 mbbIndices.second = mbbIndices.second.scale(factor); 490 Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); 491 } 492 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 493 494 // Scale terminator gaps. 495 for (DenseMap<MachineBasicBlock*, MachineInstrIndex>::iterator 496 TGI = terminatorGaps.begin(), TGE = terminatorGaps.end(); 497 TGI != TGE; ++TGI) { 498 terminatorGaps[TGI->first] = TGI->second.scale(factor); 499 } 500 501 // Scale the intervals. 502 for (iterator LI = begin(), LE = end(); LI != LE; ++LI) { 503 LI->second->scaleNumbering(factor); 504 } 505 506 // Scale MachineInstrs. 507 Mi2IndexMap oldmi2iMap = mi2iMap_; 508 MachineInstrIndex highestSlot; 509 for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end(); 510 MI != ME; ++MI) { 511 MachineInstrIndex newSlot = MI->second.scale(factor); 512 mi2iMap_[MI->first] = newSlot; 513 highestSlot = std::max(highestSlot, newSlot); 514 } 515 516 unsigned highestVIndex = highestSlot.getVecIndex(); 517 i2miMap_.clear(); 518 i2miMap_.resize(highestVIndex + 1); 519 for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end(); 520 MI != ME; ++MI) { 521 i2miMap_[MI->second.getVecIndex()] = const_cast<MachineInstr *>(MI->first); 522 } 523 524} 525 526 527/// runOnMachineFunction - Register allocate the whole function 528/// 529bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 530 mf_ = &fn; 531 mri_ = &mf_->getRegInfo(); 532 tm_ = &fn.getTarget(); 533 tri_ = tm_->getRegisterInfo(); 534 tii_ = tm_->getInstrInfo(); 535 aa_ = &getAnalysis<AliasAnalysis>(); 536 lv_ = &getAnalysis<LiveVariables>(); 537 allocatableRegs_ = tri_->getAllocatableSet(fn); 538 539 processImplicitDefs(); 540 computeNumbering(); 541 computeIntervals(); 542 performEarlyCoalescing(); 543 544 numIntervals += getNumIntervals(); 545 546 DEBUG(dump()); 547 return true; 548} 549 550/// print - Implement the dump method. 551void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 552 OS << "********** INTERVALS **********\n"; 553 for (const_iterator I = begin(), E = end(); I != E; ++I) { 554 I->second->print(OS, tri_); 555 OS << "\n"; 556 } 557 558 printInstrs(OS); 559} 560 561void LiveIntervals::printInstrs(raw_ostream &OS) const { 562 OS << "********** MACHINEINSTRS **********\n"; 563 564 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 565 mbbi != mbbe; ++mbbi) { 566 OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 567 for (MachineBasicBlock::iterator mii = mbbi->begin(), 568 mie = mbbi->end(); mii != mie; ++mii) { 569 OS << getInstructionIndex(mii) << '\t' << *mii; 570 } 571 } 572} 573 574void LiveIntervals::dumpInstrs() const { 575 printInstrs(errs()); 576} 577 578/// conflictsWithPhysRegDef - Returns true if the specified register 579/// is defined during the duration of the specified interval. 580bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 581 VirtRegMap &vrm, unsigned reg) { 582 for (LiveInterval::Ranges::const_iterator 583 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 584 for (MachineInstrIndex index = getBaseIndex(I->start), 585 end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end; 586 index = getNextIndex(index)) { 587 // skip deleted instructions 588 while (index != end && !getInstructionFromIndex(index)) 589 index = getNextIndex(index); 590 if (index == end) break; 591 592 MachineInstr *MI = getInstructionFromIndex(index); 593 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 594 if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 595 if (SrcReg == li.reg || DstReg == li.reg) 596 continue; 597 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 598 MachineOperand& mop = MI->getOperand(i); 599 if (!mop.isReg()) 600 continue; 601 unsigned PhysReg = mop.getReg(); 602 if (PhysReg == 0 || PhysReg == li.reg) 603 continue; 604 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 605 if (!vrm.hasPhys(PhysReg)) 606 continue; 607 PhysReg = vrm.getPhys(PhysReg); 608 } 609 if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 610 return true; 611 } 612 } 613 } 614 615 return false; 616} 617 618/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except 619/// it can check use as well. 620bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, 621 unsigned Reg, bool CheckUse, 622 SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 623 for (LiveInterval::Ranges::const_iterator 624 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 625 for (MachineInstrIndex index = getBaseIndex(I->start), 626 end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); index != end; 627 index = getNextIndex(index)) { 628 // Skip deleted instructions. 629 MachineInstr *MI = 0; 630 while (index != end) { 631 MI = getInstructionFromIndex(index); 632 if (MI) 633 break; 634 index = getNextIndex(index); 635 } 636 if (index == end) break; 637 638 if (JoinedCopies.count(MI)) 639 continue; 640 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 641 MachineOperand& MO = MI->getOperand(i); 642 if (!MO.isReg()) 643 continue; 644 if (MO.isUse() && !CheckUse) 645 continue; 646 unsigned PhysReg = MO.getReg(); 647 if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 648 continue; 649 if (tri_->isSubRegister(Reg, PhysReg)) 650 return true; 651 } 652 } 653 } 654 655 return false; 656} 657 658#ifndef NDEBUG 659static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { 660 if (TargetRegisterInfo::isPhysicalRegister(reg)) 661 errs() << tri_->getName(reg); 662 else 663 errs() << "%reg" << reg; 664} 665#endif 666 667void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 668 MachineBasicBlock::iterator mi, 669 MachineInstrIndex MIIdx, 670 MachineOperand& MO, 671 unsigned MOIdx, 672 LiveInterval &interval) { 673 DEBUG({ 674 errs() << "\t\tregister: "; 675 printRegName(interval.reg, tri_); 676 }); 677 678 // Virtual registers may be defined multiple times (due to phi 679 // elimination and 2-addr elimination). Much of what we do only has to be 680 // done once for the vreg. We use an empty interval to detect the first 681 // time we see a vreg. 682 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 683 if (interval.empty()) { 684 // Get the Idx of the defining instructions. 685 MachineInstrIndex defIndex = getDefIndex(MIIdx); 686 // Earlyclobbers move back one, so that they overlap the live range 687 // of inputs. 688 if (MO.isEarlyClobber()) 689 defIndex = getUseIndex(MIIdx); 690 VNInfo *ValNo; 691 MachineInstr *CopyMI = NULL; 692 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 693 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 694 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 695 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 696 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 697 CopyMI = mi; 698 // Earlyclobbers move back one. 699 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 700 701 assert(ValNo->id == 0 && "First value in interval is not 0?"); 702 703 // Loop over all of the blocks that the vreg is defined in. There are 704 // two cases we have to handle here. The most common case is a vreg 705 // whose lifetime is contained within a basic block. In this case there 706 // will be a single kill, in MBB, which comes after the definition. 707 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 708 // FIXME: what about dead vars? 709 MachineInstrIndex killIdx; 710 if (vi.Kills[0] != mi) 711 killIdx = getNextSlot(getUseIndex(getInstructionIndex(vi.Kills[0]))); 712 else if (MO.isEarlyClobber()) 713 // Earlyclobbers that die in this instruction move up one extra, to 714 // compensate for having the starting point moved back one. This 715 // gets them to overlap the live range of other outputs. 716 killIdx = getNextSlot(getNextSlot(defIndex)); 717 else 718 killIdx = getNextSlot(defIndex); 719 720 // If the kill happens after the definition, we have an intra-block 721 // live range. 722 if (killIdx > defIndex) { 723 assert(vi.AliveBlocks.empty() && 724 "Shouldn't be alive across any blocks!"); 725 LiveRange LR(defIndex, killIdx, ValNo); 726 interval.addRange(LR); 727 DEBUG(errs() << " +" << LR << "\n"); 728 ValNo->addKill(killIdx); 729 return; 730 } 731 } 732 733 // The other case we handle is when a virtual register lives to the end 734 // of the defining block, potentially live across some blocks, then is 735 // live into some number of blocks, but gets killed. Start by adding a 736 // range that goes from this definition to the end of the defining block. 737 LiveRange NewLR(defIndex, getNextSlot(getMBBEndIdx(mbb)), ValNo); 738 DEBUG(errs() << " +" << NewLR); 739 interval.addRange(NewLR); 740 741 // Iterate over all of the blocks that the variable is completely 742 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 743 // live interval. 744 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 745 E = vi.AliveBlocks.end(); I != E; ++I) { 746 LiveRange LR(getMBBStartIdx(*I), 747 getNextSlot(getMBBEndIdx(*I)), // MBB ends at -1. 748 ValNo); 749 interval.addRange(LR); 750 DEBUG(errs() << " +" << LR); 751 } 752 753 // Finally, this virtual register is live from the start of any killing 754 // block to the 'use' slot of the killing instruction. 755 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 756 MachineInstr *Kill = vi.Kills[i]; 757 MachineInstrIndex killIdx = 758 getNextSlot(getUseIndex(getInstructionIndex(Kill))); 759 LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); 760 interval.addRange(LR); 761 ValNo->addKill(killIdx); 762 DEBUG(errs() << " +" << LR); 763 } 764 765 } else { 766 // If this is the second time we see a virtual register definition, it 767 // must be due to phi elimination or two addr elimination. If this is 768 // the result of two address elimination, then the vreg is one of the 769 // def-and-use register operand. 770 if (mi->isRegTiedToUseOperand(MOIdx)) { 771 // If this is a two-address definition, then we have already processed 772 // the live range. The only problem is that we didn't realize there 773 // are actually two values in the live interval. Because of this we 774 // need to take the LiveRegion that defines this register and split it 775 // into two values. 776 assert(interval.containsOneValue()); 777 MachineInstrIndex DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 778 MachineInstrIndex RedefIndex = getDefIndex(MIIdx); 779 if (MO.isEarlyClobber()) 780 RedefIndex = getUseIndex(MIIdx); 781 782 const LiveRange *OldLR = 783 interval.getLiveRangeContaining(getPrevSlot(RedefIndex)); 784 VNInfo *OldValNo = OldLR->valno; 785 786 // Delete the initial value, which should be short and continuous, 787 // because the 2-addr copy must be in the same MBB as the redef. 788 interval.removeRange(DefIndex, RedefIndex); 789 790 // Two-address vregs should always only be redefined once. This means 791 // that at this point, there should be exactly one value number in it. 792 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 793 794 // The new value number (#1) is defined by the instruction we claimed 795 // defined value #0. 796 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), 797 false, // update at * 798 VNInfoAllocator); 799 ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 800 801 // Value#0 is now defined by the 2-addr instruction. 802 OldValNo->def = RedefIndex; 803 OldValNo->setCopy(0); 804 if (MO.isEarlyClobber()) 805 OldValNo->setHasRedefByEC(true); 806 807 // Add the new live interval which replaces the range for the input copy. 808 LiveRange LR(DefIndex, RedefIndex, ValNo); 809 DEBUG(errs() << " replace range with " << LR); 810 interval.addRange(LR); 811 ValNo->addKill(RedefIndex); 812 813 // If this redefinition is dead, we need to add a dummy unit live 814 // range covering the def slot. 815 if (MO.isDead()) 816 interval.addRange( 817 LiveRange(RedefIndex, MO.isEarlyClobber() ? 818 getNextSlot(getNextSlot(RedefIndex)) : 819 getNextSlot(RedefIndex), OldValNo)); 820 821 DEBUG({ 822 errs() << " RESULT: "; 823 interval.print(errs(), tri_); 824 }); 825 } else { 826 // Otherwise, this must be because of phi elimination. If this is the 827 // first redefinition of the vreg that we have seen, go back and change 828 // the live range in the PHI block to be a different value number. 829 if (interval.containsOneValue()) { 830 // Remove the old range that we now know has an incorrect number. 831 VNInfo *VNI = interval.getValNumInfo(0); 832 MachineInstr *Killer = vi.Kills[0]; 833 phiJoinCopies.push_back(Killer); 834 MachineInstrIndex Start = getMBBStartIdx(Killer->getParent()); 835 MachineInstrIndex End = 836 getNextSlot(getUseIndex(getInstructionIndex(Killer))); 837 DEBUG({ 838 errs() << " Removing [" << Start << "," << End << "] from: "; 839 interval.print(errs(), tri_); 840 errs() << "\n"; 841 }); 842 interval.removeRange(Start, End); 843 assert(interval.ranges.size() == 1 && 844 "Newly discovered PHI interval has >1 ranges."); 845 MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); 846 VNI->addKill(terminatorGaps[killMBB]); 847 VNI->setHasPHIKill(true); 848 DEBUG({ 849 errs() << " RESULT: "; 850 interval.print(errs(), tri_); 851 }); 852 853 // Replace the interval with one of a NEW value number. Note that this 854 // value number isn't actually defined by an instruction, weird huh? :) 855 LiveRange LR(Start, End, 856 interval.getNextValue(MachineInstrIndex(mbb->getNumber()), 857 0, false, VNInfoAllocator)); 858 LR.valno->setIsPHIDef(true); 859 DEBUG(errs() << " replace range with " << LR); 860 interval.addRange(LR); 861 LR.valno->addKill(End); 862 DEBUG({ 863 errs() << " RESULT: "; 864 interval.print(errs(), tri_); 865 }); 866 } 867 868 // In the case of PHI elimination, each variable definition is only 869 // live until the end of the block. We've already taken care of the 870 // rest of the live range. 871 MachineInstrIndex defIndex = getDefIndex(MIIdx); 872 if (MO.isEarlyClobber()) 873 defIndex = getUseIndex(MIIdx); 874 875 VNInfo *ValNo; 876 MachineInstr *CopyMI = NULL; 877 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 878 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 879 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 880 mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 881 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 882 CopyMI = mi; 883 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 884 885 MachineInstrIndex killIndex = getNextSlot(getMBBEndIdx(mbb)); 886 LiveRange LR(defIndex, killIndex, ValNo); 887 interval.addRange(LR); 888 ValNo->addKill(terminatorGaps[mbb]); 889 ValNo->setHasPHIKill(true); 890 DEBUG(errs() << " +" << LR); 891 } 892 } 893 894 DEBUG(errs() << '\n'); 895} 896 897void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 898 MachineBasicBlock::iterator mi, 899 MachineInstrIndex MIIdx, 900 MachineOperand& MO, 901 LiveInterval &interval, 902 MachineInstr *CopyMI) { 903 // A physical register cannot be live across basic block, so its 904 // lifetime must end somewhere in its defining basic block. 905 DEBUG({ 906 errs() << "\t\tregister: "; 907 printRegName(interval.reg, tri_); 908 }); 909 910 MachineInstrIndex baseIndex = MIIdx; 911 MachineInstrIndex start = getDefIndex(baseIndex); 912 // Earlyclobbers move back one. 913 if (MO.isEarlyClobber()) 914 start = getUseIndex(MIIdx); 915 MachineInstrIndex end = start; 916 917 // If it is not used after definition, it is considered dead at 918 // the instruction defining it. Hence its interval is: 919 // [defSlot(def), defSlot(def)+1) 920 // For earlyclobbers, the defSlot was pushed back one; the extra 921 // advance below compensates. 922 if (MO.isDead()) { 923 DEBUG(errs() << " dead"); 924 if (MO.isEarlyClobber()) 925 end = getNextSlot(getNextSlot(start)); 926 else 927 end = getNextSlot(start); 928 goto exit; 929 } 930 931 // If it is not dead on definition, it must be killed by a 932 // subsequent instruction. Hence its interval is: 933 // [defSlot(def), useSlot(kill)+1) 934 baseIndex = getNextIndex(baseIndex); 935 while (++mi != MBB->end()) { 936 while (baseIndex.getVecIndex() < i2miMap_.size() && 937 getInstructionFromIndex(baseIndex) == 0) 938 baseIndex = getNextIndex(baseIndex); 939 if (mi->killsRegister(interval.reg, tri_)) { 940 DEBUG(errs() << " killed"); 941 end = getNextSlot(getUseIndex(baseIndex)); 942 goto exit; 943 } else { 944 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 945 if (DefIdx != -1) { 946 if (mi->isRegTiedToUseOperand(DefIdx)) { 947 // Two-address instruction. 948 end = getDefIndex(baseIndex); 949 if (mi->getOperand(DefIdx).isEarlyClobber()) 950 end = getUseIndex(baseIndex); 951 } else { 952 // Another instruction redefines the register before it is ever read. 953 // Then the register is essentially dead at the instruction that defines 954 // it. Hence its interval is: 955 // [defSlot(def), defSlot(def)+1) 956 DEBUG(errs() << " dead"); 957 end = getNextSlot(start); 958 } 959 goto exit; 960 } 961 } 962 963 baseIndex = getNextIndex(baseIndex); 964 } 965 966 // The only case we should have a dead physreg here without a killing or 967 // instruction where we know it's dead is if it is live-in to the function 968 // and never used. Another possible case is the implicit use of the 969 // physical register has been deleted by two-address pass. 970 end = getNextSlot(start); 971 972exit: 973 assert(start < end && "did not find end of interval?"); 974 975 // Already exists? Extend old live interval. 976 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 977 bool Extend = OldLR != interval.end(); 978 VNInfo *ValNo = Extend 979 ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 980 if (MO.isEarlyClobber() && Extend) 981 ValNo->setHasRedefByEC(true); 982 LiveRange LR(start, end, ValNo); 983 interval.addRange(LR); 984 LR.valno->addKill(end); 985 DEBUG(errs() << " +" << LR << '\n'); 986} 987 988void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 989 MachineBasicBlock::iterator MI, 990 MachineInstrIndex MIIdx, 991 MachineOperand& MO, 992 unsigned MOIdx) { 993 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 994 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 995 getOrCreateInterval(MO.getReg())); 996 else if (allocatableRegs_[MO.getReg()]) { 997 MachineInstr *CopyMI = NULL; 998 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 999 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 1000 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 1001 MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 1002 tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 1003 CopyMI = MI; 1004 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 1005 getOrCreateInterval(MO.getReg()), CopyMI); 1006 // Def of a register also defines its sub-registers. 1007 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 1008 // If MI also modifies the sub-register explicitly, avoid processing it 1009 // more than once. Do not pass in TRI here so it checks for exact match. 1010 if (!MI->modifiesRegister(*AS)) 1011 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 1012 getOrCreateInterval(*AS), 0); 1013 } 1014} 1015 1016void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 1017 MachineInstrIndex MIIdx, 1018 LiveInterval &interval, bool isAlias) { 1019 DEBUG({ 1020 errs() << "\t\tlivein register: "; 1021 printRegName(interval.reg, tri_); 1022 }); 1023 1024 // Look for kills, if it reaches a def before it's killed, then it shouldn't 1025 // be considered a livein. 1026 MachineBasicBlock::iterator mi = MBB->begin(); 1027 MachineInstrIndex baseIndex = MIIdx; 1028 MachineInstrIndex start = baseIndex; 1029 while (baseIndex.getVecIndex() < i2miMap_.size() && 1030 getInstructionFromIndex(baseIndex) == 0) 1031 baseIndex = getNextIndex(baseIndex); 1032 MachineInstrIndex end = baseIndex; 1033 bool SeenDefUse = false; 1034 1035 while (mi != MBB->end()) { 1036 if (mi->killsRegister(interval.reg, tri_)) { 1037 DEBUG(errs() << " killed"); 1038 end = getNextSlot(getUseIndex(baseIndex)); 1039 SeenDefUse = true; 1040 break; 1041 } else if (mi->modifiesRegister(interval.reg, tri_)) { 1042 // Another instruction redefines the register before it is ever read. 1043 // Then the register is essentially dead at the instruction that defines 1044 // it. Hence its interval is: 1045 // [defSlot(def), defSlot(def)+1) 1046 DEBUG(errs() << " dead"); 1047 end = getNextSlot(getDefIndex(start)); 1048 SeenDefUse = true; 1049 break; 1050 } 1051 1052 baseIndex = getNextIndex(baseIndex); 1053 ++mi; 1054 if (mi != MBB->end()) { 1055 while (baseIndex.getVecIndex() < i2miMap_.size() && 1056 getInstructionFromIndex(baseIndex) == 0) 1057 baseIndex = getNextIndex(baseIndex); 1058 } 1059 } 1060 1061 // Live-in register might not be used at all. 1062 if (!SeenDefUse) { 1063 if (isAlias) { 1064 DEBUG(errs() << " dead"); 1065 end = getNextSlot(getDefIndex(MIIdx)); 1066 } else { 1067 DEBUG(errs() << " live through"); 1068 end = baseIndex; 1069 } 1070 } 1071 1072 VNInfo *vni = 1073 interval.getNextValue(MachineInstrIndex(MBB->getNumber()), 1074 0, false, VNInfoAllocator); 1075 vni->setIsPHIDef(true); 1076 LiveRange LR(start, end, vni); 1077 1078 interval.addRange(LR); 1079 LR.valno->addKill(end); 1080 DEBUG(errs() << " +" << LR << '\n'); 1081} 1082 1083bool 1084LiveIntervals::isProfitableToCoalesce(LiveInterval &DstInt, LiveInterval &SrcInt, 1085 SmallVector<MachineInstr*,16> &IdentCopies, 1086 SmallVector<MachineInstr*,16> &OtherCopies) { 1087 bool HaveConflict = false; 1088 unsigned NumIdent = 0; 1089 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(SrcInt.reg), 1090 re = mri_->reg_end(); ri != re; ++ri) { 1091 MachineOperand &O = ri.getOperand(); 1092 if (!O.isDef()) 1093 continue; 1094 1095 MachineInstr *MI = &*ri; 1096 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 1097 if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 1098 return false; 1099 if (SrcReg != DstInt.reg) { 1100 OtherCopies.push_back(MI); 1101 HaveConflict |= DstInt.liveAt(getInstructionIndex(MI)); 1102 } else { 1103 IdentCopies.push_back(MI); 1104 ++NumIdent; 1105 } 1106 } 1107 1108 if (!HaveConflict) 1109 return false; // Let coalescer handle it 1110 return IdentCopies.size() > OtherCopies.size(); 1111} 1112 1113void LiveIntervals::performEarlyCoalescing() { 1114 if (!EarlyCoalescing) 1115 return; 1116 1117 /// Perform early coalescing: eliminate copies which feed into phi joins 1118 /// and whose sources are defined by the phi joins. 1119 for (unsigned i = 0, e = phiJoinCopies.size(); i != e; ++i) { 1120 MachineInstr *Join = phiJoinCopies[i]; 1121 if (CoalescingLimit != -1 && (int)numCoalescing == CoalescingLimit) 1122 break; 1123 1124 unsigned PHISrc, PHIDst, SrcSubReg, DstSubReg; 1125 bool isMove= tii_->isMoveInstr(*Join, PHISrc, PHIDst, SrcSubReg, DstSubReg); 1126#ifndef NDEBUG 1127 assert(isMove && "PHI join instruction must be a move!"); 1128#else 1129 isMove = isMove; 1130#endif 1131 1132 LiveInterval &DstInt = getInterval(PHIDst); 1133 LiveInterval &SrcInt = getInterval(PHISrc); 1134 SmallVector<MachineInstr*, 16> IdentCopies; 1135 SmallVector<MachineInstr*, 16> OtherCopies; 1136 if (!isProfitableToCoalesce(DstInt, SrcInt, IdentCopies, OtherCopies)) 1137 continue; 1138 1139 DEBUG(errs() << "PHI Join: " << *Join); 1140 assert(DstInt.containsOneValue() && "PHI join should have just one val#!"); 1141 VNInfo *VNI = DstInt.getValNumInfo(0); 1142 1143 // Change the non-identity copies to directly target the phi destination. 1144 for (unsigned i = 0, e = OtherCopies.size(); i != e; ++i) { 1145 MachineInstr *PHICopy = OtherCopies[i]; 1146 DEBUG(errs() << "Moving: " << *PHICopy); 1147 1148 MachineInstrIndex MIIndex = getInstructionIndex(PHICopy); 1149 MachineInstrIndex DefIndex = getDefIndex(MIIndex); 1150 LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); 1151 MachineInstrIndex StartIndex = SLR->start; 1152 MachineInstrIndex EndIndex = SLR->end; 1153 1154 // Delete val# defined by the now identity copy and add the range from 1155 // beginning of the mbb to the end of the range. 1156 SrcInt.removeValNo(SLR->valno); 1157 DEBUG(errs() << " added range [" << StartIndex << ',' 1158 << EndIndex << "] to reg" << DstInt.reg << '\n'); 1159 if (DstInt.liveAt(StartIndex)) 1160 DstInt.removeRange(StartIndex, EndIndex); 1161 VNInfo *NewVNI = DstInt.getNextValue(DefIndex, PHICopy, true, 1162 VNInfoAllocator); 1163 NewVNI->setHasPHIKill(true); 1164 DstInt.addRange(LiveRange(StartIndex, EndIndex, NewVNI)); 1165 for (unsigned j = 0, ee = PHICopy->getNumOperands(); j != ee; ++j) { 1166 MachineOperand &MO = PHICopy->getOperand(j); 1167 if (!MO.isReg() || MO.getReg() != PHISrc) 1168 continue; 1169 MO.setReg(PHIDst); 1170 } 1171 } 1172 1173 // Now let's eliminate all the would-be identity copies. 1174 for (unsigned i = 0, e = IdentCopies.size(); i != e; ++i) { 1175 MachineInstr *PHICopy = IdentCopies[i]; 1176 DEBUG(errs() << "Coalescing: " << *PHICopy); 1177 1178 MachineInstrIndex MIIndex = getInstructionIndex(PHICopy); 1179 MachineInstrIndex DefIndex = getDefIndex(MIIndex); 1180 LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); 1181 MachineInstrIndex StartIndex = SLR->start; 1182 MachineInstrIndex EndIndex = SLR->end; 1183 1184 // Delete val# defined by the now identity copy and add the range from 1185 // beginning of the mbb to the end of the range. 1186 SrcInt.removeValNo(SLR->valno); 1187 RemoveMachineInstrFromMaps(PHICopy); 1188 PHICopy->eraseFromParent(); 1189 DEBUG(errs() << " added range [" << StartIndex << ',' 1190 << EndIndex << "] to reg" << DstInt.reg << '\n'); 1191 DstInt.addRange(LiveRange(StartIndex, EndIndex, VNI)); 1192 } 1193 1194 // Remove the phi join and update the phi block liveness. 1195 MachineInstrIndex MIIndex = getInstructionIndex(Join); 1196 MachineInstrIndex UseIndex = getUseIndex(MIIndex); 1197 MachineInstrIndex DefIndex = getDefIndex(MIIndex); 1198 LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex); 1199 LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex); 1200 DLR->valno->setCopy(0); 1201 DLR->valno->setIsDefAccurate(false); 1202 DstInt.addRange(LiveRange(SLR->start, SLR->end, DLR->valno)); 1203 SrcInt.removeRange(SLR->start, SLR->end); 1204 assert(SrcInt.empty()); 1205 removeInterval(PHISrc); 1206 RemoveMachineInstrFromMaps(Join); 1207 Join->eraseFromParent(); 1208 1209 ++numCoalescing; 1210 } 1211} 1212 1213/// computeIntervals - computes the live intervals for virtual 1214/// registers. for some ordering of the machine instructions [1,N] a 1215/// live interval is an interval [i, j) where 1 <= i <= j < N for 1216/// which a variable is live 1217void LiveIntervals::computeIntervals() { 1218 DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" 1219 << "********** Function: " 1220 << ((Value*)mf_->getFunction())->getName() << '\n'); 1221 1222 SmallVector<unsigned, 8> UndefUses; 1223 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 1224 MBBI != E; ++MBBI) { 1225 MachineBasicBlock *MBB = MBBI; 1226 // Track the index of the current machine instr. 1227 MachineInstrIndex MIIndex = getMBBStartIdx(MBB); 1228 DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 1229 1230 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 1231 1232 // Create intervals for live-ins to this BB first. 1233 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 1234 LE = MBB->livein_end(); LI != LE; ++LI) { 1235 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 1236 // Multiple live-ins can alias the same register. 1237 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 1238 if (!hasInterval(*AS)) 1239 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 1240 true); 1241 } 1242 1243 // Skip over empty initial indices. 1244 while (MIIndex.getVecIndex() < i2miMap_.size() && 1245 getInstructionFromIndex(MIIndex) == 0) 1246 MIIndex = getNextIndex(MIIndex); 1247 1248 for (; MI != miEnd; ++MI) { 1249 DEBUG(errs() << MIIndex << "\t" << *MI); 1250 1251 // Handle defs. 1252 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 1253 MachineOperand &MO = MI->getOperand(i); 1254 if (!MO.isReg() || !MO.getReg()) 1255 continue; 1256 1257 // handle register defs - build intervals 1258 if (MO.isDef()) 1259 handleRegisterDef(MBB, MI, MIIndex, MO, i); 1260 else if (MO.isUndef()) 1261 UndefUses.push_back(MO.getReg()); 1262 } 1263 1264 // Skip over the empty slots after each instruction. 1265 unsigned Slots = MI->getDesc().getNumDefs(); 1266 if (Slots == 0) 1267 Slots = 1; 1268 1269 while (Slots--) 1270 MIIndex = getNextIndex(MIIndex); 1271 1272 // Skip over empty indices. 1273 while (MIIndex.getVecIndex() < i2miMap_.size() && 1274 getInstructionFromIndex(MIIndex) == 0) 1275 MIIndex = getNextIndex(MIIndex); 1276 } 1277 } 1278 1279 // Create empty intervals for registers defined by implicit_def's (except 1280 // for those implicit_def that define values which are liveout of their 1281 // blocks. 1282 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 1283 unsigned UndefReg = UndefUses[i]; 1284 (void)getOrCreateInterval(UndefReg); 1285 } 1286} 1287 1288bool LiveIntervals::findLiveInMBBs( 1289 MachineInstrIndex Start, MachineInstrIndex End, 1290 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 1291 std::vector<IdxMBBPair>::const_iterator I = 1292 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 1293 1294 bool ResVal = false; 1295 while (I != Idx2MBBMap.end()) { 1296 if (I->first >= End) 1297 break; 1298 MBBs.push_back(I->second); 1299 ResVal = true; 1300 ++I; 1301 } 1302 return ResVal; 1303} 1304 1305bool LiveIntervals::findReachableMBBs( 1306 MachineInstrIndex Start, MachineInstrIndex End, 1307 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 1308 std::vector<IdxMBBPair>::const_iterator I = 1309 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 1310 1311 bool ResVal = false; 1312 while (I != Idx2MBBMap.end()) { 1313 if (I->first > End) 1314 break; 1315 MachineBasicBlock *MBB = I->second; 1316 if (getMBBEndIdx(MBB) > End) 1317 break; 1318 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 1319 SE = MBB->succ_end(); SI != SE; ++SI) 1320 MBBs.push_back(*SI); 1321 ResVal = true; 1322 ++I; 1323 } 1324 return ResVal; 1325} 1326 1327LiveInterval* LiveIntervals::createInterval(unsigned reg) { 1328 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 1329 return new LiveInterval(reg, Weight); 1330} 1331 1332/// dupInterval - Duplicate a live interval. The caller is responsible for 1333/// managing the allocated memory. 1334LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 1335 LiveInterval *NewLI = createInterval(li->reg); 1336 NewLI->Copy(*li, mri_, getVNInfoAllocator()); 1337 return NewLI; 1338} 1339 1340/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 1341/// copy field and returns the source register that defines it. 1342unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 1343 if (!VNI->getCopy()) 1344 return 0; 1345 1346 if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 1347 // If it's extracting out of a physical register, return the sub-register. 1348 unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); 1349 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 1350 Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); 1351 return Reg; 1352 } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 1353 VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 1354 return VNI->getCopy()->getOperand(2).getReg(); 1355 1356 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 1357 if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) 1358 return SrcReg; 1359 llvm_unreachable("Unrecognized copy instruction!"); 1360 return 0; 1361} 1362 1363//===----------------------------------------------------------------------===// 1364// Register allocator hooks. 1365// 1366 1367/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 1368/// allow one) virtual register operand, then its uses are implicitly using 1369/// the register. Returns the virtual register. 1370unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 1371 MachineInstr *MI) const { 1372 unsigned RegOp = 0; 1373 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1374 MachineOperand &MO = MI->getOperand(i); 1375 if (!MO.isReg() || !MO.isUse()) 1376 continue; 1377 unsigned Reg = MO.getReg(); 1378 if (Reg == 0 || Reg == li.reg) 1379 continue; 1380 1381 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 1382 !allocatableRegs_[Reg]) 1383 continue; 1384 // FIXME: For now, only remat MI with at most one register operand. 1385 assert(!RegOp && 1386 "Can't rematerialize instruction with multiple register operand!"); 1387 RegOp = MO.getReg(); 1388#ifndef NDEBUG 1389 break; 1390#endif 1391 } 1392 return RegOp; 1393} 1394 1395/// isValNoAvailableAt - Return true if the val# of the specified interval 1396/// which reaches the given instruction also reaches the specified use index. 1397bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 1398 MachineInstrIndex UseIdx) const { 1399 MachineInstrIndex Index = getInstructionIndex(MI); 1400 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 1401 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 1402 return UI != li.end() && UI->valno == ValNo; 1403} 1404 1405/// isReMaterializable - Returns true if the definition MI of the specified 1406/// val# of the specified interval is re-materializable. 1407bool LiveIntervals::isReMaterializable(const LiveInterval &li, 1408 const VNInfo *ValNo, MachineInstr *MI, 1409 SmallVectorImpl<LiveInterval*> &SpillIs, 1410 bool &isLoad) { 1411 if (DisableReMat) 1412 return false; 1413 1414 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 1415 return true; 1416 1417 int FrameIdx = 0; 1418 if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 1419 mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 1420 // FIXME: Let target specific isReallyTriviallyReMaterializable determines 1421 // this but remember this is not safe to fold into a two-address 1422 // instruction. 1423 // This is a load from fixed stack slot. It can be rematerialized. 1424 return true; 1425 1426 // If the target-specific rules don't identify an instruction as 1427 // being trivially rematerializable, use some target-independent 1428 // rules. 1429 if (!MI->getDesc().isRematerializable() || 1430 !tii_->isTriviallyReMaterializable(MI)) { 1431 if (!EnableAggressiveRemat) 1432 return false; 1433 1434 // If the instruction accesses memory but the memoperands have been lost, 1435 // we can't analyze it. 1436 const TargetInstrDesc &TID = MI->getDesc(); 1437 if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) 1438 return false; 1439 1440 // Avoid instructions obviously unsafe for remat. 1441 if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) 1442 return false; 1443 1444 // If the instruction accesses memory and the memory could be non-constant, 1445 // assume the instruction is not rematerializable. 1446 for (std::list<MachineMemOperand>::const_iterator 1447 I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ 1448 const MachineMemOperand &MMO = *I; 1449 if (MMO.isVolatile() || MMO.isStore()) 1450 return false; 1451 const Value *V = MMO.getValue(); 1452 if (!V) 1453 return false; 1454 if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 1455 if (!PSV->isConstant(mf_->getFrameInfo())) 1456 return false; 1457 } else if (!aa_->pointsToConstantMemory(V)) 1458 return false; 1459 } 1460 1461 // If any of the registers accessed are non-constant, conservatively assume 1462 // the instruction is not rematerializable. 1463 unsigned ImpUse = 0; 1464 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1465 const MachineOperand &MO = MI->getOperand(i); 1466 if (MO.isReg()) { 1467 unsigned Reg = MO.getReg(); 1468 if (Reg == 0) 1469 continue; 1470 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 1471 return false; 1472 1473 // Only allow one def, and that in the first operand. 1474 if (MO.isDef() != (i == 0)) 1475 return false; 1476 1477 // Only allow constant-valued registers. 1478 bool IsLiveIn = mri_->isLiveIn(Reg); 1479 MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), 1480 E = mri_->def_end(); 1481 1482 // For the def, it should be the only def of that register. 1483 if (MO.isDef() && (next(I) != E || IsLiveIn)) 1484 return false; 1485 1486 if (MO.isUse()) { 1487 // Only allow one use other register use, as that's all the 1488 // remat mechanisms support currently. 1489 if (Reg != li.reg) { 1490 if (ImpUse == 0) 1491 ImpUse = Reg; 1492 else if (Reg != ImpUse) 1493 return false; 1494 } 1495 // For the use, there should be only one associated def. 1496 if (I != E && (next(I) != E || IsLiveIn)) 1497 return false; 1498 } 1499 } 1500 } 1501 } 1502 1503 unsigned ImpUse = getReMatImplicitUse(li, MI); 1504 if (ImpUse) { 1505 const LiveInterval &ImpLi = getInterval(ImpUse); 1506 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 1507 re = mri_->use_end(); ri != re; ++ri) { 1508 MachineInstr *UseMI = &*ri; 1509 MachineInstrIndex UseIdx = getInstructionIndex(UseMI); 1510 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 1511 continue; 1512 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 1513 return false; 1514 } 1515 1516 // If a register operand of the re-materialized instruction is going to 1517 // be spilled next, then it's not legal to re-materialize this instruction. 1518 for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 1519 if (ImpUse == SpillIs[i]->reg) 1520 return false; 1521 } 1522 return true; 1523} 1524 1525/// isReMaterializable - Returns true if the definition MI of the specified 1526/// val# of the specified interval is re-materializable. 1527bool LiveIntervals::isReMaterializable(const LiveInterval &li, 1528 const VNInfo *ValNo, MachineInstr *MI) { 1529 SmallVector<LiveInterval*, 4> Dummy1; 1530 bool Dummy2; 1531 return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 1532} 1533 1534/// isReMaterializable - Returns true if every definition of MI of every 1535/// val# of the specified interval is re-materializable. 1536bool LiveIntervals::isReMaterializable(const LiveInterval &li, 1537 SmallVectorImpl<LiveInterval*> &SpillIs, 1538 bool &isLoad) { 1539 isLoad = false; 1540 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1541 i != e; ++i) { 1542 const VNInfo *VNI = *i; 1543 if (VNI->isUnused()) 1544 continue; // Dead val#. 1545 // Is the def for the val# rematerializable? 1546 if (!VNI->isDefAccurate()) 1547 return false; 1548 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 1549 bool DefIsLoad = false; 1550 if (!ReMatDefMI || 1551 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 1552 return false; 1553 isLoad |= DefIsLoad; 1554 } 1555 return true; 1556} 1557 1558/// FilterFoldedOps - Filter out two-address use operands. Return 1559/// true if it finds any issue with the operands that ought to prevent 1560/// folding. 1561static bool FilterFoldedOps(MachineInstr *MI, 1562 SmallVector<unsigned, 2> &Ops, 1563 unsigned &MRInfo, 1564 SmallVector<unsigned, 2> &FoldOps) { 1565 MRInfo = 0; 1566 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1567 unsigned OpIdx = Ops[i]; 1568 MachineOperand &MO = MI->getOperand(OpIdx); 1569 // FIXME: fold subreg use. 1570 if (MO.getSubReg()) 1571 return true; 1572 if (MO.isDef()) 1573 MRInfo |= (unsigned)VirtRegMap::isMod; 1574 else { 1575 // Filter out two-address use operand(s). 1576 if (MI->isRegTiedToDefOperand(OpIdx)) { 1577 MRInfo = VirtRegMap::isModRef; 1578 continue; 1579 } 1580 MRInfo |= (unsigned)VirtRegMap::isRef; 1581 } 1582 FoldOps.push_back(OpIdx); 1583 } 1584 return false; 1585} 1586 1587 1588/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 1589/// slot / to reg or any rematerialized load into ith operand of specified 1590/// MI. If it is successul, MI is updated with the newly created MI and 1591/// returns true. 1592bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 1593 VirtRegMap &vrm, MachineInstr *DefMI, 1594 MachineInstrIndex InstrIdx, 1595 SmallVector<unsigned, 2> &Ops, 1596 bool isSS, int Slot, unsigned Reg) { 1597 // If it is an implicit def instruction, just delete it. 1598 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 1599 RemoveMachineInstrFromMaps(MI); 1600 vrm.RemoveMachineInstrFromMaps(MI); 1601 MI->eraseFromParent(); 1602 ++numFolds; 1603 return true; 1604 } 1605 1606 // Filter the list of operand indexes that are to be folded. Abort if 1607 // any operand will prevent folding. 1608 unsigned MRInfo = 0; 1609 SmallVector<unsigned, 2> FoldOps; 1610 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 1611 return false; 1612 1613 // The only time it's safe to fold into a two address instruction is when 1614 // it's folding reload and spill from / into a spill stack slot. 1615 if (DefMI && (MRInfo & VirtRegMap::isMod)) 1616 return false; 1617 1618 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 1619 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 1620 if (fmi) { 1621 // Remember this instruction uses the spill slot. 1622 if (isSS) vrm.addSpillSlotUse(Slot, fmi); 1623 1624 // Attempt to fold the memory reference into the instruction. If 1625 // we can do this, we don't need to insert spill code. 1626 MachineBasicBlock &MBB = *MI->getParent(); 1627 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 1628 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 1629 vrm.transferSpillPts(MI, fmi); 1630 vrm.transferRestorePts(MI, fmi); 1631 vrm.transferEmergencySpills(MI, fmi); 1632 mi2iMap_.erase(MI); 1633 i2miMap_[InstrIdx.getVecIndex()] = fmi; 1634 mi2iMap_[fmi] = InstrIdx; 1635 MI = MBB.insert(MBB.erase(MI), fmi); 1636 ++numFolds; 1637 return true; 1638 } 1639 return false; 1640} 1641 1642/// canFoldMemoryOperand - Returns true if the specified load / store 1643/// folding is possible. 1644bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 1645 SmallVector<unsigned, 2> &Ops, 1646 bool ReMat) const { 1647 // Filter the list of operand indexes that are to be folded. Abort if 1648 // any operand will prevent folding. 1649 unsigned MRInfo = 0; 1650 SmallVector<unsigned, 2> FoldOps; 1651 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 1652 return false; 1653 1654 // It's only legal to remat for a use, not a def. 1655 if (ReMat && (MRInfo & VirtRegMap::isMod)) 1656 return false; 1657 1658 return tii_->canFoldMemoryOperand(MI, FoldOps); 1659} 1660 1661bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 1662 SmallPtrSet<MachineBasicBlock*, 4> MBBs; 1663 for (LiveInterval::Ranges::const_iterator 1664 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1665 std::vector<IdxMBBPair>::const_iterator II = 1666 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 1667 if (II == Idx2MBBMap.end()) 1668 continue; 1669 if (I->end > II->first) // crossing a MBB. 1670 return false; 1671 MBBs.insert(II->second); 1672 if (MBBs.size() > 1) 1673 return false; 1674 } 1675 return true; 1676} 1677 1678/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1679/// interval on to-be re-materialized operands of MI) with new register. 1680void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1681 MachineInstr *MI, unsigned NewVReg, 1682 VirtRegMap &vrm) { 1683 // There is an implicit use. That means one of the other operand is 1684 // being remat'ed and the remat'ed instruction has li.reg as an 1685 // use operand. Make sure we rewrite that as well. 1686 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1687 MachineOperand &MO = MI->getOperand(i); 1688 if (!MO.isReg()) 1689 continue; 1690 unsigned Reg = MO.getReg(); 1691 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1692 continue; 1693 if (!vrm.isReMaterialized(Reg)) 1694 continue; 1695 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 1696 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 1697 if (UseMO) 1698 UseMO->setReg(NewVReg); 1699 } 1700} 1701 1702/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1703/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1704bool LiveIntervals:: 1705rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1706 bool TrySplit, MachineInstrIndex index, MachineInstrIndex end, 1707 MachineInstr *MI, 1708 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1709 unsigned Slot, int LdSlot, 1710 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1711 VirtRegMap &vrm, 1712 const TargetRegisterClass* rc, 1713 SmallVector<int, 4> &ReMatIds, 1714 const MachineLoopInfo *loopInfo, 1715 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1716 DenseMap<unsigned,unsigned> &MBBVRegsMap, 1717 std::vector<LiveInterval*> &NewLIs) { 1718 bool CanFold = false; 1719 RestartInstruction: 1720 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1721 MachineOperand& mop = MI->getOperand(i); 1722 if (!mop.isReg()) 1723 continue; 1724 unsigned Reg = mop.getReg(); 1725 unsigned RegI = Reg; 1726 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1727 continue; 1728 if (Reg != li.reg) 1729 continue; 1730 1731 bool TryFold = !DefIsReMat; 1732 bool FoldSS = true; // Default behavior unless it's a remat. 1733 int FoldSlot = Slot; 1734 if (DefIsReMat) { 1735 // If this is the rematerializable definition MI itself and 1736 // all of its uses are rematerialized, simply delete it. 1737 if (MI == ReMatOrigDefMI && CanDelete) { 1738 DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: " 1739 << MI << '\n'); 1740 RemoveMachineInstrFromMaps(MI); 1741 vrm.RemoveMachineInstrFromMaps(MI); 1742 MI->eraseFromParent(); 1743 break; 1744 } 1745 1746 // If def for this use can't be rematerialized, then try folding. 1747 // If def is rematerializable and it's a load, also try folding. 1748 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1749 if (isLoad) { 1750 // Try fold loads (from stack slot, constant pool, etc.) into uses. 1751 FoldSS = isLoadSS; 1752 FoldSlot = LdSlot; 1753 } 1754 } 1755 1756 // Scan all of the operands of this instruction rewriting operands 1757 // to use NewVReg instead of li.reg as appropriate. We do this for 1758 // two reasons: 1759 // 1760 // 1. If the instr reads the same spilled vreg multiple times, we 1761 // want to reuse the NewVReg. 1762 // 2. If the instr is a two-addr instruction, we are required to 1763 // keep the src/dst regs pinned. 1764 // 1765 // Keep track of whether we replace a use and/or def so that we can 1766 // create the spill interval with the appropriate range. 1767 1768 HasUse = mop.isUse(); 1769 HasDef = mop.isDef(); 1770 SmallVector<unsigned, 2> Ops; 1771 Ops.push_back(i); 1772 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1773 const MachineOperand &MOj = MI->getOperand(j); 1774 if (!MOj.isReg()) 1775 continue; 1776 unsigned RegJ = MOj.getReg(); 1777 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1778 continue; 1779 if (RegJ == RegI) { 1780 Ops.push_back(j); 1781 if (!MOj.isUndef()) { 1782 HasUse |= MOj.isUse(); 1783 HasDef |= MOj.isDef(); 1784 } 1785 } 1786 } 1787 1788 // Create a new virtual register for the spill interval. 1789 // Create the new register now so we can map the fold instruction 1790 // to the new register so when it is unfolded we get the correct 1791 // answer. 1792 bool CreatedNewVReg = false; 1793 if (NewVReg == 0) { 1794 NewVReg = mri_->createVirtualRegister(rc); 1795 vrm.grow(); 1796 CreatedNewVReg = true; 1797 } 1798 1799 if (!TryFold) 1800 CanFold = false; 1801 else { 1802 // Do not fold load / store here if we are splitting. We'll find an 1803 // optimal point to insert a load / store later. 1804 if (!TrySplit) { 1805 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1806 Ops, FoldSS, FoldSlot, NewVReg)) { 1807 // Folding the load/store can completely change the instruction in 1808 // unpredictable ways, rescan it from the beginning. 1809 1810 if (FoldSS) { 1811 // We need to give the new vreg the same stack slot as the 1812 // spilled interval. 1813 vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 1814 } 1815 1816 HasUse = false; 1817 HasDef = false; 1818 CanFold = false; 1819 if (isNotInMIMap(MI)) 1820 break; 1821 goto RestartInstruction; 1822 } 1823 } else { 1824 // We'll try to fold it later if it's profitable. 1825 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1826 } 1827 } 1828 1829 mop.setReg(NewVReg); 1830 if (mop.isImplicit()) 1831 rewriteImplicitOps(li, MI, NewVReg, vrm); 1832 1833 // Reuse NewVReg for other reads. 1834 for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1835 MachineOperand &mopj = MI->getOperand(Ops[j]); 1836 mopj.setReg(NewVReg); 1837 if (mopj.isImplicit()) 1838 rewriteImplicitOps(li, MI, NewVReg, vrm); 1839 } 1840 1841 if (CreatedNewVReg) { 1842 if (DefIsReMat) { 1843 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); 1844 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 1845 // Each valnum may have its own remat id. 1846 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 1847 } else { 1848 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 1849 } 1850 if (!CanDelete || (HasUse && HasDef)) { 1851 // If this is a two-addr instruction then its use operands are 1852 // rematerializable but its def is not. It should be assigned a 1853 // stack slot. 1854 vrm.assignVirt2StackSlot(NewVReg, Slot); 1855 } 1856 } else { 1857 vrm.assignVirt2StackSlot(NewVReg, Slot); 1858 } 1859 } else if (HasUse && HasDef && 1860 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1861 // If this interval hasn't been assigned a stack slot (because earlier 1862 // def is a deleted remat def), do it now. 1863 assert(Slot != VirtRegMap::NO_STACK_SLOT); 1864 vrm.assignVirt2StackSlot(NewVReg, Slot); 1865 } 1866 1867 // Re-matting an instruction with virtual register use. Add the 1868 // register as an implicit use on the use MI. 1869 if (DefIsReMat && ImpUse) 1870 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1871 1872 // Create a new register interval for this spill / remat. 1873 LiveInterval &nI = getOrCreateInterval(NewVReg); 1874 if (CreatedNewVReg) { 1875 NewLIs.push_back(&nI); 1876 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 1877 if (TrySplit) 1878 vrm.setIsSplitFromReg(NewVReg, li.reg); 1879 } 1880 1881 if (HasUse) { 1882 if (CreatedNewVReg) { 1883 LiveRange LR(getLoadIndex(index), getNextSlot(getUseIndex(index)), 1884 nI.getNextValue(MachineInstrIndex(), 0, false, 1885 VNInfoAllocator)); 1886 DEBUG(errs() << " +" << LR); 1887 nI.addRange(LR); 1888 } else { 1889 // Extend the split live interval to this def / use. 1890 MachineInstrIndex End = getNextSlot(getUseIndex(index)); 1891 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 1892 nI.getValNumInfo(nI.getNumValNums()-1)); 1893 DEBUG(errs() << " +" << LR); 1894 nI.addRange(LR); 1895 } 1896 } 1897 if (HasDef) { 1898 LiveRange LR(getDefIndex(index), getStoreIndex(index), 1899 nI.getNextValue(MachineInstrIndex(), 0, false, 1900 VNInfoAllocator)); 1901 DEBUG(errs() << " +" << LR); 1902 nI.addRange(LR); 1903 } 1904 1905 DEBUG({ 1906 errs() << "\t\t\t\tAdded new interval: "; 1907 nI.print(errs(), tri_); 1908 errs() << '\n'; 1909 }); 1910 } 1911 return CanFold; 1912} 1913bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 1914 const VNInfo *VNI, 1915 MachineBasicBlock *MBB, 1916 MachineInstrIndex Idx) const { 1917 MachineInstrIndex End = getMBBEndIdx(MBB); 1918 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1919 if (VNI->kills[j].isPHIIndex()) 1920 continue; 1921 1922 MachineInstrIndex KillIdx = VNI->kills[j]; 1923 if (KillIdx > Idx && KillIdx < End) 1924 return true; 1925 } 1926 return false; 1927} 1928 1929/// RewriteInfo - Keep track of machine instrs that will be rewritten 1930/// during spilling. 1931namespace { 1932 struct RewriteInfo { 1933 MachineInstrIndex Index; 1934 MachineInstr *MI; 1935 bool HasUse; 1936 bool HasDef; 1937 RewriteInfo(MachineInstrIndex i, MachineInstr *mi, bool u, bool d) 1938 : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1939 }; 1940 1941 struct RewriteInfoCompare { 1942 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1943 return LHS.Index < RHS.Index; 1944 } 1945 }; 1946} 1947 1948void LiveIntervals:: 1949rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1950 LiveInterval::Ranges::const_iterator &I, 1951 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1952 unsigned Slot, int LdSlot, 1953 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1954 VirtRegMap &vrm, 1955 const TargetRegisterClass* rc, 1956 SmallVector<int, 4> &ReMatIds, 1957 const MachineLoopInfo *loopInfo, 1958 BitVector &SpillMBBs, 1959 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 1960 BitVector &RestoreMBBs, 1961 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1962 DenseMap<unsigned,unsigned> &MBBVRegsMap, 1963 std::vector<LiveInterval*> &NewLIs) { 1964 bool AllCanFold = true; 1965 unsigned NewVReg = 0; 1966 MachineInstrIndex start = getBaseIndex(I->start); 1967 MachineInstrIndex end = getNextIndex(getBaseIndex(getPrevSlot(I->end))); 1968 1969 // First collect all the def / use in this live range that will be rewritten. 1970 // Make sure they are sorted according to instruction index. 1971 std::vector<RewriteInfo> RewriteMIs; 1972 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1973 re = mri_->reg_end(); ri != re; ) { 1974 MachineInstr *MI = &*ri; 1975 MachineOperand &O = ri.getOperand(); 1976 ++ri; 1977 assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1978 MachineInstrIndex index = getInstructionIndex(MI); 1979 if (index < start || index >= end) 1980 continue; 1981 1982 if (O.isUndef()) 1983 // Must be defined by an implicit def. It should not be spilled. Note, 1984 // this is for correctness reason. e.g. 1985 // 8 %reg1024<def> = IMPLICIT_DEF 1986 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 1987 // The live range [12, 14) are not part of the r1024 live interval since 1988 // it's defined by an implicit def. It will not conflicts with live 1989 // interval of r1025. Now suppose both registers are spilled, you can 1990 // easily see a situation where both registers are reloaded before 1991 // the INSERT_SUBREG and both target registers that would overlap. 1992 continue; 1993 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1994 } 1995 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1996 1997 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1998 // Now rewrite the defs and uses. 1999 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 2000 RewriteInfo &rwi = RewriteMIs[i]; 2001 ++i; 2002 MachineInstrIndex index = rwi.Index; 2003 bool MIHasUse = rwi.HasUse; 2004 bool MIHasDef = rwi.HasDef; 2005 MachineInstr *MI = rwi.MI; 2006 // If MI def and/or use the same register multiple times, then there 2007 // are multiple entries. 2008 unsigned NumUses = MIHasUse; 2009 while (i != e && RewriteMIs[i].MI == MI) { 2010 assert(RewriteMIs[i].Index == index); 2011 bool isUse = RewriteMIs[i].HasUse; 2012 if (isUse) ++NumUses; 2013 MIHasUse |= isUse; 2014 MIHasDef |= RewriteMIs[i].HasDef; 2015 ++i; 2016 } 2017 MachineBasicBlock *MBB = MI->getParent(); 2018 2019 if (ImpUse && MI != ReMatDefMI) { 2020 // Re-matting an instruction with virtual register use. Update the 2021 // register interval's spill weight to HUGE_VALF to prevent it from 2022 // being spilled. 2023 LiveInterval &ImpLi = getInterval(ImpUse); 2024 ImpLi.weight = HUGE_VALF; 2025 } 2026 2027 unsigned MBBId = MBB->getNumber(); 2028 unsigned ThisVReg = 0; 2029 if (TrySplit) { 2030 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 2031 if (NVI != MBBVRegsMap.end()) { 2032 ThisVReg = NVI->second; 2033 // One common case: 2034 // x = use 2035 // ... 2036 // ... 2037 // def = ... 2038 // = use 2039 // It's better to start a new interval to avoid artifically 2040 // extend the new interval. 2041 if (MIHasDef && !MIHasUse) { 2042 MBBVRegsMap.erase(MBB->getNumber()); 2043 ThisVReg = 0; 2044 } 2045 } 2046 } 2047 2048 bool IsNew = ThisVReg == 0; 2049 if (IsNew) { 2050 // This ends the previous live interval. If all of its def / use 2051 // can be folded, give it a low spill weight. 2052 if (NewVReg && TrySplit && AllCanFold) { 2053 LiveInterval &nI = getOrCreateInterval(NewVReg); 2054 nI.weight /= 10.0F; 2055 } 2056 AllCanFold = true; 2057 } 2058 NewVReg = ThisVReg; 2059 2060 bool HasDef = false; 2061 bool HasUse = false; 2062 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 2063 index, end, MI, ReMatOrigDefMI, ReMatDefMI, 2064 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 2065 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 2066 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 2067 if (!HasDef && !HasUse) 2068 continue; 2069 2070 AllCanFold &= CanFold; 2071 2072 // Update weight of spill interval. 2073 LiveInterval &nI = getOrCreateInterval(NewVReg); 2074 if (!TrySplit) { 2075 // The spill weight is now infinity as it cannot be spilled again. 2076 nI.weight = HUGE_VALF; 2077 continue; 2078 } 2079 2080 // Keep track of the last def and first use in each MBB. 2081 if (HasDef) { 2082 if (MI != ReMatOrigDefMI || !CanDelete) { 2083 bool HasKill = false; 2084 if (!HasUse) 2085 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 2086 else { 2087 // If this is a two-address code, then this index starts a new VNInfo. 2088 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(getDefIndex(index)); 2089 if (VNI) 2090 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 2091 } 2092 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 2093 SpillIdxes.find(MBBId); 2094 if (!HasKill) { 2095 if (SII == SpillIdxes.end()) { 2096 std::vector<SRInfo> S; 2097 S.push_back(SRInfo(index, NewVReg, true)); 2098 SpillIdxes.insert(std::make_pair(MBBId, S)); 2099 } else if (SII->second.back().vreg != NewVReg) { 2100 SII->second.push_back(SRInfo(index, NewVReg, true)); 2101 } else if (index > SII->second.back().index) { 2102 // If there is an earlier def and this is a two-address 2103 // instruction, then it's not possible to fold the store (which 2104 // would also fold the load). 2105 SRInfo &Info = SII->second.back(); 2106 Info.index = index; 2107 Info.canFold = !HasUse; 2108 } 2109 SpillMBBs.set(MBBId); 2110 } else if (SII != SpillIdxes.end() && 2111 SII->second.back().vreg == NewVReg && 2112 index > SII->second.back().index) { 2113 // There is an earlier def that's not killed (must be two-address). 2114 // The spill is no longer needed. 2115 SII->second.pop_back(); 2116 if (SII->second.empty()) { 2117 SpillIdxes.erase(MBBId); 2118 SpillMBBs.reset(MBBId); 2119 } 2120 } 2121 } 2122 } 2123 2124 if (HasUse) { 2125 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 2126 SpillIdxes.find(MBBId); 2127 if (SII != SpillIdxes.end() && 2128 SII->second.back().vreg == NewVReg && 2129 index > SII->second.back().index) 2130 // Use(s) following the last def, it's not safe to fold the spill. 2131 SII->second.back().canFold = false; 2132 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 2133 RestoreIdxes.find(MBBId); 2134 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 2135 // If we are splitting live intervals, only fold if it's the first 2136 // use and there isn't another use later in the MBB. 2137 RII->second.back().canFold = false; 2138 else if (IsNew) { 2139 // Only need a reload if there isn't an earlier def / use. 2140 if (RII == RestoreIdxes.end()) { 2141 std::vector<SRInfo> Infos; 2142 Infos.push_back(SRInfo(index, NewVReg, true)); 2143 RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 2144 } else { 2145 RII->second.push_back(SRInfo(index, NewVReg, true)); 2146 } 2147 RestoreMBBs.set(MBBId); 2148 } 2149 } 2150 2151 // Update spill weight. 2152 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 2153 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 2154 } 2155 2156 if (NewVReg && TrySplit && AllCanFold) { 2157 // If all of its def / use can be folded, give it a low spill weight. 2158 LiveInterval &nI = getOrCreateInterval(NewVReg); 2159 nI.weight /= 10.0F; 2160 } 2161} 2162 2163bool LiveIntervals::alsoFoldARestore(int Id, MachineInstrIndex index, 2164 unsigned vr, BitVector &RestoreMBBs, 2165 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 2166 if (!RestoreMBBs[Id]) 2167 return false; 2168 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 2169 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 2170 if (Restores[i].index == index && 2171 Restores[i].vreg == vr && 2172 Restores[i].canFold) 2173 return true; 2174 return false; 2175} 2176 2177void LiveIntervals::eraseRestoreInfo(int Id, MachineInstrIndex index, 2178 unsigned vr, BitVector &RestoreMBBs, 2179 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 2180 if (!RestoreMBBs[Id]) 2181 return; 2182 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 2183 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 2184 if (Restores[i].index == index && Restores[i].vreg) 2185 Restores[i].index = MachineInstrIndex(); 2186} 2187 2188/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 2189/// spilled and create empty intervals for their uses. 2190void 2191LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 2192 const TargetRegisterClass* rc, 2193 std::vector<LiveInterval*> &NewLIs) { 2194 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 2195 re = mri_->reg_end(); ri != re; ) { 2196 MachineOperand &O = ri.getOperand(); 2197 MachineInstr *MI = &*ri; 2198 ++ri; 2199 if (O.isDef()) { 2200 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 2201 "Register def was not rewritten?"); 2202 RemoveMachineInstrFromMaps(MI); 2203 vrm.RemoveMachineInstrFromMaps(MI); 2204 MI->eraseFromParent(); 2205 } else { 2206 // This must be an use of an implicit_def so it's not part of the live 2207 // interval. Create a new empty live interval for it. 2208 // FIXME: Can we simply erase some of the instructions? e.g. Stores? 2209 unsigned NewVReg = mri_->createVirtualRegister(rc); 2210 vrm.grow(); 2211 vrm.setIsImplicitlyDefined(NewVReg); 2212 NewLIs.push_back(&getOrCreateInterval(NewVReg)); 2213 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 2214 MachineOperand &MO = MI->getOperand(i); 2215 if (MO.isReg() && MO.getReg() == li.reg) { 2216 MO.setReg(NewVReg); 2217 MO.setIsUndef(); 2218 } 2219 } 2220 } 2221 } 2222} 2223 2224std::vector<LiveInterval*> LiveIntervals:: 2225addIntervalsForSpillsFast(const LiveInterval &li, 2226 const MachineLoopInfo *loopInfo, 2227 VirtRegMap &vrm) { 2228 unsigned slot = vrm.assignVirt2StackSlot(li.reg); 2229 2230 std::vector<LiveInterval*> added; 2231 2232 assert(li.weight != HUGE_VALF && 2233 "attempt to spill already spilled interval!"); 2234 2235 DEBUG({ 2236 errs() << "\t\t\t\tadding intervals for spills for interval: "; 2237 li.dump(); 2238 errs() << '\n'; 2239 }); 2240 2241 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 2242 2243 MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 2244 while (RI != mri_->reg_end()) { 2245 MachineInstr* MI = &*RI; 2246 2247 SmallVector<unsigned, 2> Indices; 2248 bool HasUse = false; 2249 bool HasDef = false; 2250 2251 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 2252 MachineOperand& mop = MI->getOperand(i); 2253 if (!mop.isReg() || mop.getReg() != li.reg) continue; 2254 2255 HasUse |= MI->getOperand(i).isUse(); 2256 HasDef |= MI->getOperand(i).isDef(); 2257 2258 Indices.push_back(i); 2259 } 2260 2261 if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 2262 Indices, true, slot, li.reg)) { 2263 unsigned NewVReg = mri_->createVirtualRegister(rc); 2264 vrm.grow(); 2265 vrm.assignVirt2StackSlot(NewVReg, slot); 2266 2267 // create a new register for this spill 2268 LiveInterval &nI = getOrCreateInterval(NewVReg); 2269 2270 // the spill weight is now infinity as it 2271 // cannot be spilled again 2272 nI.weight = HUGE_VALF; 2273 2274 // Rewrite register operands to use the new vreg. 2275 for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 2276 E = Indices.end(); I != E; ++I) { 2277 MI->getOperand(*I).setReg(NewVReg); 2278 2279 if (MI->getOperand(*I).isUse()) 2280 MI->getOperand(*I).setIsKill(true); 2281 } 2282 2283 // Fill in the new live interval. 2284 MachineInstrIndex index = getInstructionIndex(MI); 2285 if (HasUse) { 2286 LiveRange LR(getLoadIndex(index), getUseIndex(index), 2287 nI.getNextValue(MachineInstrIndex(), 0, false, 2288 getVNInfoAllocator())); 2289 DEBUG(errs() << " +" << LR); 2290 nI.addRange(LR); 2291 vrm.addRestorePoint(NewVReg, MI); 2292 } 2293 if (HasDef) { 2294 LiveRange LR(getDefIndex(index), getStoreIndex(index), 2295 nI.getNextValue(MachineInstrIndex(), 0, false, 2296 getVNInfoAllocator())); 2297 DEBUG(errs() << " +" << LR); 2298 nI.addRange(LR); 2299 vrm.addSpillPoint(NewVReg, true, MI); 2300 } 2301 2302 added.push_back(&nI); 2303 2304 DEBUG({ 2305 errs() << "\t\t\t\tadded new interval: "; 2306 nI.dump(); 2307 errs() << '\n'; 2308 }); 2309 } 2310 2311 2312 RI = mri_->reg_begin(li.reg); 2313 } 2314 2315 return added; 2316} 2317 2318std::vector<LiveInterval*> LiveIntervals:: 2319addIntervalsForSpills(const LiveInterval &li, 2320 SmallVectorImpl<LiveInterval*> &SpillIs, 2321 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 2322 2323 if (EnableFastSpilling) 2324 return addIntervalsForSpillsFast(li, loopInfo, vrm); 2325 2326 assert(li.weight != HUGE_VALF && 2327 "attempt to spill already spilled interval!"); 2328 2329 DEBUG({ 2330 errs() << "\t\t\t\tadding intervals for spills for interval: "; 2331 li.print(errs(), tri_); 2332 errs() << '\n'; 2333 }); 2334 2335 // Each bit specify whether a spill is required in the MBB. 2336 BitVector SpillMBBs(mf_->getNumBlockIDs()); 2337 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 2338 BitVector RestoreMBBs(mf_->getNumBlockIDs()); 2339 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 2340 DenseMap<unsigned,unsigned> MBBVRegsMap; 2341 std::vector<LiveInterval*> NewLIs; 2342 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 2343 2344 unsigned NumValNums = li.getNumValNums(); 2345 SmallVector<MachineInstr*, 4> ReMatDefs; 2346 ReMatDefs.resize(NumValNums, NULL); 2347 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 2348 ReMatOrigDefs.resize(NumValNums, NULL); 2349 SmallVector<int, 4> ReMatIds; 2350 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 2351 BitVector ReMatDelete(NumValNums); 2352 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 2353 2354 // Spilling a split live interval. It cannot be split any further. Also, 2355 // it's also guaranteed to be a single val# / range interval. 2356 if (vrm.getPreSplitReg(li.reg)) { 2357 vrm.setIsSplitFromReg(li.reg, 0); 2358 // Unset the split kill marker on the last use. 2359 MachineInstrIndex KillIdx = vrm.getKillPoint(li.reg); 2360 if (KillIdx != MachineInstrIndex()) { 2361 MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 2362 assert(KillMI && "Last use disappeared?"); 2363 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 2364 assert(KillOp != -1 && "Last use disappeared?"); 2365 KillMI->getOperand(KillOp).setIsKill(false); 2366 } 2367 vrm.removeKillPoint(li.reg); 2368 bool DefIsReMat = vrm.isReMaterialized(li.reg); 2369 Slot = vrm.getStackSlot(li.reg); 2370 assert(Slot != VirtRegMap::MAX_STACK_SLOT); 2371 MachineInstr *ReMatDefMI = DefIsReMat ? 2372 vrm.getReMaterializedMI(li.reg) : NULL; 2373 int LdSlot = 0; 2374 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 2375 bool isLoad = isLoadSS || 2376 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 2377 bool IsFirstRange = true; 2378 for (LiveInterval::Ranges::const_iterator 2379 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 2380 // If this is a split live interval with multiple ranges, it means there 2381 // are two-address instructions that re-defined the value. Only the 2382 // first def can be rematerialized! 2383 if (IsFirstRange) { 2384 // Note ReMatOrigDefMI has already been deleted. 2385 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 2386 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 2387 false, vrm, rc, ReMatIds, loopInfo, 2388 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 2389 MBBVRegsMap, NewLIs); 2390 } else { 2391 rewriteInstructionsForSpills(li, false, I, NULL, 0, 2392 Slot, 0, false, false, false, 2393 false, vrm, rc, ReMatIds, loopInfo, 2394 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 2395 MBBVRegsMap, NewLIs); 2396 } 2397 IsFirstRange = false; 2398 } 2399 2400 handleSpilledImpDefs(li, vrm, rc, NewLIs); 2401 return NewLIs; 2402 } 2403 2404 bool TrySplit = !intervalIsInOneMBB(li); 2405 if (TrySplit) 2406 ++numSplits; 2407 bool NeedStackSlot = false; 2408 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 2409 i != e; ++i) { 2410 const VNInfo *VNI = *i; 2411 unsigned VN = VNI->id; 2412 if (VNI->isUnused()) 2413 continue; // Dead val#. 2414 // Is the def for the val# rematerializable? 2415 MachineInstr *ReMatDefMI = VNI->isDefAccurate() 2416 ? getInstructionFromIndex(VNI->def) : 0; 2417 bool dummy; 2418 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 2419 // Remember how to remat the def of this val#. 2420 ReMatOrigDefs[VN] = ReMatDefMI; 2421 // Original def may be modified so we have to make a copy here. 2422 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 2423 CloneMIs.push_back(Clone); 2424 ReMatDefs[VN] = Clone; 2425 2426 bool CanDelete = true; 2427 if (VNI->hasPHIKill()) { 2428 // A kill is a phi node, not all of its uses can be rematerialized. 2429 // It must not be deleted. 2430 CanDelete = false; 2431 // Need a stack slot if there is any live range where uses cannot be 2432 // rematerialized. 2433 NeedStackSlot = true; 2434 } 2435 if (CanDelete) 2436 ReMatDelete.set(VN); 2437 } else { 2438 // Need a stack slot if there is any live range where uses cannot be 2439 // rematerialized. 2440 NeedStackSlot = true; 2441 } 2442 } 2443 2444 // One stack slot per live interval. 2445 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 2446 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 2447 Slot = vrm.assignVirt2StackSlot(li.reg); 2448 2449 // This case only occurs when the prealloc splitter has already assigned 2450 // a stack slot to this vreg. 2451 else 2452 Slot = vrm.getStackSlot(li.reg); 2453 } 2454 2455 // Create new intervals and rewrite defs and uses. 2456 for (LiveInterval::Ranges::const_iterator 2457 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 2458 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 2459 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 2460 bool DefIsReMat = ReMatDefMI != NULL; 2461 bool CanDelete = ReMatDelete[I->valno->id]; 2462 int LdSlot = 0; 2463 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 2464 bool isLoad = isLoadSS || 2465 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 2466 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 2467 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 2468 CanDelete, vrm, rc, ReMatIds, loopInfo, 2469 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 2470 MBBVRegsMap, NewLIs); 2471 } 2472 2473 // Insert spills / restores if we are splitting. 2474 if (!TrySplit) { 2475 handleSpilledImpDefs(li, vrm, rc, NewLIs); 2476 return NewLIs; 2477 } 2478 2479 SmallPtrSet<LiveInterval*, 4> AddedKill; 2480 SmallVector<unsigned, 2> Ops; 2481 if (NeedStackSlot) { 2482 int Id = SpillMBBs.find_first(); 2483 while (Id != -1) { 2484 std::vector<SRInfo> &spills = SpillIdxes[Id]; 2485 for (unsigned i = 0, e = spills.size(); i != e; ++i) { 2486 MachineInstrIndex index = spills[i].index; 2487 unsigned VReg = spills[i].vreg; 2488 LiveInterval &nI = getOrCreateInterval(VReg); 2489 bool isReMat = vrm.isReMaterialized(VReg); 2490 MachineInstr *MI = getInstructionFromIndex(index); 2491 bool CanFold = false; 2492 bool FoundUse = false; 2493 Ops.clear(); 2494 if (spills[i].canFold) { 2495 CanFold = true; 2496 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 2497 MachineOperand &MO = MI->getOperand(j); 2498 if (!MO.isReg() || MO.getReg() != VReg) 2499 continue; 2500 2501 Ops.push_back(j); 2502 if (MO.isDef()) 2503 continue; 2504 if (isReMat || 2505 (!FoundUse && !alsoFoldARestore(Id, index, VReg, 2506 RestoreMBBs, RestoreIdxes))) { 2507 // MI has two-address uses of the same register. If the use 2508 // isn't the first and only use in the BB, then we can't fold 2509 // it. FIXME: Move this to rewriteInstructionsForSpills. 2510 CanFold = false; 2511 break; 2512 } 2513 FoundUse = true; 2514 } 2515 } 2516 // Fold the store into the def if possible. 2517 bool Folded = false; 2518 if (CanFold && !Ops.empty()) { 2519 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 2520 Folded = true; 2521 if (FoundUse) { 2522 // Also folded uses, do not issue a load. 2523 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 2524 nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index))); 2525 } 2526 nI.removeRange(getDefIndex(index), getStoreIndex(index)); 2527 } 2528 } 2529 2530 // Otherwise tell the spiller to issue a spill. 2531 if (!Folded) { 2532 LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 2533 bool isKill = LR->end == getStoreIndex(index); 2534 if (!MI->registerDefIsDead(nI.reg)) 2535 // No need to spill a dead def. 2536 vrm.addSpillPoint(VReg, isKill, MI); 2537 if (isKill) 2538 AddedKill.insert(&nI); 2539 } 2540 } 2541 Id = SpillMBBs.find_next(Id); 2542 } 2543 } 2544 2545 int Id = RestoreMBBs.find_first(); 2546 while (Id != -1) { 2547 std::vector<SRInfo> &restores = RestoreIdxes[Id]; 2548 for (unsigned i = 0, e = restores.size(); i != e; ++i) { 2549 MachineInstrIndex index = restores[i].index; 2550 if (index == MachineInstrIndex()) 2551 continue; 2552 unsigned VReg = restores[i].vreg; 2553 LiveInterval &nI = getOrCreateInterval(VReg); 2554 bool isReMat = vrm.isReMaterialized(VReg); 2555 MachineInstr *MI = getInstructionFromIndex(index); 2556 bool CanFold = false; 2557 Ops.clear(); 2558 if (restores[i].canFold) { 2559 CanFold = true; 2560 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 2561 MachineOperand &MO = MI->getOperand(j); 2562 if (!MO.isReg() || MO.getReg() != VReg) 2563 continue; 2564 2565 if (MO.isDef()) { 2566 // If this restore were to be folded, it would have been folded 2567 // already. 2568 CanFold = false; 2569 break; 2570 } 2571 Ops.push_back(j); 2572 } 2573 } 2574 2575 // Fold the load into the use if possible. 2576 bool Folded = false; 2577 if (CanFold && !Ops.empty()) { 2578 if (!isReMat) 2579 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 2580 else { 2581 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 2582 int LdSlot = 0; 2583 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 2584 // If the rematerializable def is a load, also try to fold it. 2585 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 2586 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 2587 Ops, isLoadSS, LdSlot, VReg); 2588 if (!Folded) { 2589 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 2590 if (ImpUse) { 2591 // Re-matting an instruction with virtual register use. Add the 2592 // register as an implicit use on the use MI and update the register 2593 // interval's spill weight to HUGE_VALF to prevent it from being 2594 // spilled. 2595 LiveInterval &ImpLi = getInterval(ImpUse); 2596 ImpLi.weight = HUGE_VALF; 2597 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 2598 } 2599 } 2600 } 2601 } 2602 // If folding is not possible / failed, then tell the spiller to issue a 2603 // load / rematerialization for us. 2604 if (Folded) 2605 nI.removeRange(getLoadIndex(index), getNextSlot(getUseIndex(index))); 2606 else 2607 vrm.addRestorePoint(VReg, MI); 2608 } 2609 Id = RestoreMBBs.find_next(Id); 2610 } 2611 2612 // Finalize intervals: add kills, finalize spill weights, and filter out 2613 // dead intervals. 2614 std::vector<LiveInterval*> RetNewLIs; 2615 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2616 LiveInterval *LI = NewLIs[i]; 2617 if (!LI->empty()) { 2618 LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); 2619 if (!AddedKill.count(LI)) { 2620 LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2621 MachineInstrIndex LastUseIdx = getBaseIndex(LR->end); 2622 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 2623 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2624 assert(UseIdx != -1); 2625 if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 2626 LastUse->getOperand(UseIdx).setIsKill(); 2627 vrm.addKillPoint(LI->reg, LastUseIdx); 2628 } 2629 } 2630 RetNewLIs.push_back(LI); 2631 } 2632 } 2633 2634 handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2635 return RetNewLIs; 2636} 2637 2638/// hasAllocatableSuperReg - Return true if the specified physical register has 2639/// any super register that's allocatable. 2640bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2641 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2642 if (allocatableRegs_[*AS] && hasInterval(*AS)) 2643 return true; 2644 return false; 2645} 2646 2647/// getRepresentativeReg - Find the largest super register of the specified 2648/// physical register. 2649unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2650 // Find the largest super-register that is allocatable. 2651 unsigned BestReg = Reg; 2652 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2653 unsigned SuperReg = *AS; 2654 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2655 BestReg = SuperReg; 2656 break; 2657 } 2658 } 2659 return BestReg; 2660} 2661 2662/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2663/// specified interval that conflicts with the specified physical register. 2664unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2665 unsigned PhysReg) const { 2666 unsigned NumConflicts = 0; 2667 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2668 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2669 E = mri_->reg_end(); I != E; ++I) { 2670 MachineOperand &O = I.getOperand(); 2671 MachineInstr *MI = O.getParent(); 2672 MachineInstrIndex Index = getInstructionIndex(MI); 2673 if (pli.liveAt(Index)) 2674 ++NumConflicts; 2675 } 2676 return NumConflicts; 2677} 2678 2679/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 2680/// around all defs and uses of the specified interval. Return true if it 2681/// was able to cut its interval. 2682bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2683 unsigned PhysReg, VirtRegMap &vrm) { 2684 unsigned SpillReg = getRepresentativeReg(PhysReg); 2685 2686 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2687 // If there are registers which alias PhysReg, but which are not a 2688 // sub-register of the chosen representative super register. Assert 2689 // since we can't handle it yet. 2690 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2691 tri_->isSuperRegister(*AS, SpillReg)); 2692 2693 bool Cut = false; 2694 LiveInterval &pli = getInterval(SpillReg); 2695 SmallPtrSet<MachineInstr*, 8> SeenMIs; 2696 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2697 E = mri_->reg_end(); I != E; ++I) { 2698 MachineOperand &O = I.getOperand(); 2699 MachineInstr *MI = O.getParent(); 2700 if (SeenMIs.count(MI)) 2701 continue; 2702 SeenMIs.insert(MI); 2703 MachineInstrIndex Index = getInstructionIndex(MI); 2704 if (pli.liveAt(Index)) { 2705 vrm.addEmergencySpill(SpillReg, MI); 2706 MachineInstrIndex StartIdx = getLoadIndex(Index); 2707 MachineInstrIndex EndIdx = getNextSlot(getStoreIndex(Index)); 2708 if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 2709 pli.removeRange(StartIdx, EndIdx); 2710 Cut = true; 2711 } else { 2712 std::string msg; 2713 raw_string_ostream Msg(msg); 2714 Msg << "Ran out of registers during register allocation!"; 2715 if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 2716 Msg << "\nPlease check your inline asm statement for invalid " 2717 << "constraints:\n"; 2718 MI->print(Msg, tm_); 2719 } 2720 llvm_report_error(Msg.str()); 2721 } 2722 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 2723 if (!hasInterval(*AS)) 2724 continue; 2725 LiveInterval &spli = getInterval(*AS); 2726 if (spli.liveAt(Index)) 2727 spli.removeRange(getLoadIndex(Index), getNextSlot(getStoreIndex(Index))); 2728 } 2729 } 2730 } 2731 return Cut; 2732} 2733 2734LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2735 MachineInstr* startInst) { 2736 LiveInterval& Interval = getOrCreateInterval(reg); 2737 VNInfo* VN = Interval.getNextValue( 2738 MachineInstrIndex(getInstructionIndex(startInst), MachineInstrIndex::DEF), 2739 startInst, true, getVNInfoAllocator()); 2740 VN->setHasPHIKill(true); 2741 VN->kills.push_back(terminatorGaps[startInst->getParent()]); 2742 LiveRange LR( 2743 MachineInstrIndex(getInstructionIndex(startInst), MachineInstrIndex::DEF), 2744 getNextSlot(getMBBEndIdx(startInst->getParent())), VN); 2745 Interval.addRange(LR); 2746 2747 return LR; 2748} 2749 2750