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