LiveIntervalAnalysis.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
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#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19#include "LiveRangeCalc.h" 20#include "llvm/ADT/DenseSet.h" 21#include "llvm/ADT/STLExtras.h" 22#include "llvm/Analysis/AliasAnalysis.h" 23#include "llvm/CodeGen/LiveVariables.h" 24#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 25#include "llvm/CodeGen/MachineDominators.h" 26#include "llvm/CodeGen/MachineInstr.h" 27#include "llvm/CodeGen/MachineRegisterInfo.h" 28#include "llvm/CodeGen/Passes.h" 29#include "llvm/CodeGen/VirtRegMap.h" 30#include "llvm/IR/Value.h" 31#include "llvm/Support/BlockFrequency.h" 32#include "llvm/Support/CommandLine.h" 33#include "llvm/Support/Debug.h" 34#include "llvm/Support/ErrorHandling.h" 35#include "llvm/Support/raw_ostream.h" 36#include "llvm/Target/TargetInstrInfo.h" 37#include "llvm/Target/TargetMachine.h" 38#include "llvm/Target/TargetRegisterInfo.h" 39#include <algorithm> 40#include <cmath> 41#include <limits> 42using namespace llvm; 43 44#define DEBUG_TYPE "regalloc" 45 46char LiveIntervals::ID = 0; 47char &llvm::LiveIntervalsID = LiveIntervals::ID; 48INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 49 "Live Interval Analysis", false, false) 50INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 51INITIALIZE_PASS_DEPENDENCY(LiveVariables) 52INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 53INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 54INITIALIZE_PASS_END(LiveIntervals, "liveintervals", 55 "Live Interval Analysis", false, false) 56 57#ifndef NDEBUG 58static cl::opt<bool> EnablePrecomputePhysRegs( 59 "precompute-phys-liveness", cl::Hidden, 60 cl::desc("Eagerly compute live intervals for all physreg units.")); 61#else 62static bool EnablePrecomputePhysRegs = false; 63#endif // NDEBUG 64 65void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 66 AU.setPreservesCFG(); 67 AU.addRequired<AliasAnalysis>(); 68 AU.addPreserved<AliasAnalysis>(); 69 // LiveVariables isn't really required by this analysis, it is only required 70 // here to make sure it is live during TwoAddressInstructionPass and 71 // PHIElimination. This is temporary. 72 AU.addRequired<LiveVariables>(); 73 AU.addPreserved<LiveVariables>(); 74 AU.addPreservedID(MachineLoopInfoID); 75 AU.addRequiredTransitiveID(MachineDominatorsID); 76 AU.addPreservedID(MachineDominatorsID); 77 AU.addPreserved<SlotIndexes>(); 78 AU.addRequiredTransitive<SlotIndexes>(); 79 MachineFunctionPass::getAnalysisUsage(AU); 80} 81 82LiveIntervals::LiveIntervals() : MachineFunctionPass(ID), 83 DomTree(nullptr), LRCalc(nullptr) { 84 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 85} 86 87LiveIntervals::~LiveIntervals() { 88 delete LRCalc; 89} 90 91void LiveIntervals::releaseMemory() { 92 // Free the live intervals themselves. 93 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) 94 delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)]; 95 VirtRegIntervals.clear(); 96 RegMaskSlots.clear(); 97 RegMaskBits.clear(); 98 RegMaskBlocks.clear(); 99 100 for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 101 delete RegUnitRanges[i]; 102 RegUnitRanges.clear(); 103 104 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 105 VNInfoAllocator.Reset(); 106} 107 108/// runOnMachineFunction - calculates LiveIntervals 109/// 110bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 111 MF = &fn; 112 MRI = &MF->getRegInfo(); 113 TM = &fn.getTarget(); 114 TRI = TM->getRegisterInfo(); 115 TII = TM->getInstrInfo(); 116 AA = &getAnalysis<AliasAnalysis>(); 117 Indexes = &getAnalysis<SlotIndexes>(); 118 DomTree = &getAnalysis<MachineDominatorTree>(); 119 if (!LRCalc) 120 LRCalc = new LiveRangeCalc(); 121 122 // Allocate space for all virtual registers. 123 VirtRegIntervals.resize(MRI->getNumVirtRegs()); 124 125 computeVirtRegs(); 126 computeRegMasks(); 127 computeLiveInRegUnits(); 128 129 if (EnablePrecomputePhysRegs) { 130 // For stress testing, precompute live ranges of all physical register 131 // units, including reserved registers. 132 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i) 133 getRegUnit(i); 134 } 135 DEBUG(dump()); 136 return true; 137} 138 139/// print - Implement the dump method. 140void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 141 OS << "********** INTERVALS **********\n"; 142 143 // Dump the regunits. 144 for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) 145 if (LiveRange *LR = RegUnitRanges[i]) 146 OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n'; 147 148 // Dump the virtregs. 149 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 150 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 151 if (hasInterval(Reg)) 152 OS << getInterval(Reg) << '\n'; 153 } 154 155 OS << "RegMasks:"; 156 for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i) 157 OS << ' ' << RegMaskSlots[i]; 158 OS << '\n'; 159 160 printInstrs(OS); 161} 162 163void LiveIntervals::printInstrs(raw_ostream &OS) const { 164 OS << "********** MACHINEINSTRS **********\n"; 165 MF->print(OS, Indexes); 166} 167 168#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 169void LiveIntervals::dumpInstrs() const { 170 printInstrs(dbgs()); 171} 172#endif 173 174LiveInterval* LiveIntervals::createInterval(unsigned reg) { 175 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 176 llvm::huge_valf : 0.0F; 177 return new LiveInterval(reg, Weight); 178} 179 180 181/// computeVirtRegInterval - Compute the live interval of a virtual register, 182/// based on defs and uses. 183void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { 184 assert(LRCalc && "LRCalc not initialized."); 185 assert(LI.empty() && "Should only compute empty intervals."); 186 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 187 LRCalc->createDeadDefs(LI); 188 LRCalc->extendToUses(LI); 189} 190 191void LiveIntervals::computeVirtRegs() { 192 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 193 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 194 if (MRI->reg_nodbg_empty(Reg)) 195 continue; 196 createAndComputeVirtRegInterval(Reg); 197 } 198} 199 200void LiveIntervals::computeRegMasks() { 201 RegMaskBlocks.resize(MF->getNumBlockIDs()); 202 203 // Find all instructions with regmask operands. 204 for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); 205 MBBI != E; ++MBBI) { 206 MachineBasicBlock *MBB = MBBI; 207 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; 208 RMB.first = RegMaskSlots.size(); 209 for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end(); 210 MI != ME; ++MI) 211 for (MIOperands MO(MI); MO.isValid(); ++MO) { 212 if (!MO->isRegMask()) 213 continue; 214 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); 215 RegMaskBits.push_back(MO->getRegMask()); 216 } 217 // Compute the number of register mask instructions in this block. 218 RMB.second = RegMaskSlots.size() - RMB.first; 219 } 220} 221 222//===----------------------------------------------------------------------===// 223// Register Unit Liveness 224//===----------------------------------------------------------------------===// 225// 226// Fixed interference typically comes from ABI boundaries: Function arguments 227// and return values are passed in fixed registers, and so are exception 228// pointers entering landing pads. Certain instructions require values to be 229// present in specific registers. That is also represented through fixed 230// interference. 231// 232 233/// computeRegUnitInterval - Compute the live range of a register unit, based 234/// on the uses and defs of aliasing registers. The range should be empty, 235/// or contain only dead phi-defs from ABI blocks. 236void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { 237 assert(LRCalc && "LRCalc not initialized."); 238 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 239 240 // The physregs aliasing Unit are the roots and their super-registers. 241 // Create all values as dead defs before extending to uses. Note that roots 242 // may share super-registers. That's OK because createDeadDefs() is 243 // idempotent. It is very rare for a register unit to have multiple roots, so 244 // uniquing super-registers is probably not worthwhile. 245 for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 246 for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 247 Supers.isValid(); ++Supers) { 248 if (!MRI->reg_empty(*Supers)) 249 LRCalc->createDeadDefs(LR, *Supers); 250 } 251 } 252 253 // Now extend LR to reach all uses. 254 // Ignore uses of reserved registers. We only track defs of those. 255 for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) { 256 for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true); 257 Supers.isValid(); ++Supers) { 258 unsigned Reg = *Supers; 259 if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg)) 260 LRCalc->extendToUses(LR, Reg); 261 } 262 } 263} 264 265 266/// computeLiveInRegUnits - Precompute the live ranges of any register units 267/// that are live-in to an ABI block somewhere. Register values can appear 268/// without a corresponding def when entering the entry block or a landing pad. 269/// 270void LiveIntervals::computeLiveInRegUnits() { 271 RegUnitRanges.resize(TRI->getNumRegUnits()); 272 DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n"); 273 274 // Keep track of the live range sets allocated. 275 SmallVector<unsigned, 8> NewRanges; 276 277 // Check all basic blocks for live-ins. 278 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); 279 MFI != MFE; ++MFI) { 280 const MachineBasicBlock *MBB = MFI; 281 282 // We only care about ABI blocks: Entry + landing pads. 283 if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty()) 284 continue; 285 286 // Create phi-defs at Begin for all live-in registers. 287 SlotIndex Begin = Indexes->getMBBStartIdx(MBB); 288 DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber()); 289 for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(), 290 LIE = MBB->livein_end(); LII != LIE; ++LII) { 291 for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) { 292 unsigned Unit = *Units; 293 LiveRange *LR = RegUnitRanges[Unit]; 294 if (!LR) { 295 LR = RegUnitRanges[Unit] = new LiveRange(); 296 NewRanges.push_back(Unit); 297 } 298 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator()); 299 (void)VNI; 300 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id); 301 } 302 } 303 DEBUG(dbgs() << '\n'); 304 } 305 DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n"); 306 307 // Compute the 'normal' part of the ranges. 308 for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) { 309 unsigned Unit = NewRanges[i]; 310 computeRegUnitRange(*RegUnitRanges[Unit], Unit); 311 } 312} 313 314 315/// shrinkToUses - After removing some uses of a register, shrink its live 316/// range to just the remaining uses. This method does not compute reaching 317/// defs for new uses, and it doesn't remove dead defs. 318bool LiveIntervals::shrinkToUses(LiveInterval *li, 319 SmallVectorImpl<MachineInstr*> *dead) { 320 DEBUG(dbgs() << "Shrink: " << *li << '\n'); 321 assert(TargetRegisterInfo::isVirtualRegister(li->reg) 322 && "Can only shrink virtual registers"); 323 // Find all the values used, including PHI kills. 324 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 325 326 // Blocks that have already been added to WorkList as live-out. 327 SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 328 329 // Visit all instructions reading li->reg. 330 for (MachineRegisterInfo::reg_instr_iterator 331 I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end(); 332 I != E; ) { 333 MachineInstr *UseMI = &*(I++); 334 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 335 continue; 336 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 337 LiveQueryResult LRQ = li->Query(Idx); 338 VNInfo *VNI = LRQ.valueIn(); 339 if (!VNI) { 340 // This shouldn't happen: readsVirtualRegister returns true, but there is 341 // no live value. It is likely caused by a target getting <undef> flags 342 // wrong. 343 DEBUG(dbgs() << Idx << '\t' << *UseMI 344 << "Warning: Instr claims to read non-existent value in " 345 << *li << '\n'); 346 continue; 347 } 348 // Special case: An early-clobber tied operand reads and writes the 349 // register one slot early. 350 if (VNInfo *DefVNI = LRQ.valueDefined()) 351 Idx = DefVNI->def; 352 353 WorkList.push_back(std::make_pair(Idx, VNI)); 354 } 355 356 // Create new live ranges with only minimal live segments per def. 357 LiveRange NewLR; 358 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 359 I != E; ++I) { 360 VNInfo *VNI = *I; 361 if (VNI->isUnused()) 362 continue; 363 NewLR.addSegment(LiveRange::Segment(VNI->def, VNI->def.getDeadSlot(), VNI)); 364 } 365 366 // Keep track of the PHIs that are in use. 367 SmallPtrSet<VNInfo*, 8> UsedPHIs; 368 369 // Extend intervals to reach all uses in WorkList. 370 while (!WorkList.empty()) { 371 SlotIndex Idx = WorkList.back().first; 372 VNInfo *VNI = WorkList.back().second; 373 WorkList.pop_back(); 374 const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 375 SlotIndex BlockStart = getMBBStartIdx(MBB); 376 377 // Extend the live range for VNI to be live at Idx. 378 if (VNInfo *ExtVNI = NewLR.extendInBlock(BlockStart, Idx)) { 379 (void)ExtVNI; 380 assert(ExtVNI == VNI && "Unexpected existing value number"); 381 // Is this a PHIDef we haven't seen before? 382 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 383 continue; 384 // The PHI is live, make sure the predecessors are live-out. 385 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 386 PE = MBB->pred_end(); PI != PE; ++PI) { 387 if (!LiveOut.insert(*PI)) 388 continue; 389 SlotIndex Stop = getMBBEndIdx(*PI); 390 // A predecessor is not required to have a live-out value for a PHI. 391 if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 392 WorkList.push_back(std::make_pair(Stop, PVNI)); 393 } 394 continue; 395 } 396 397 // VNI is live-in to MBB. 398 DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 399 NewLR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI)); 400 401 // Make sure VNI is live-out from the predecessors. 402 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 403 PE = MBB->pred_end(); PI != PE; ++PI) { 404 if (!LiveOut.insert(*PI)) 405 continue; 406 SlotIndex Stop = getMBBEndIdx(*PI); 407 assert(li->getVNInfoBefore(Stop) == VNI && 408 "Wrong value out of predecessor"); 409 WorkList.push_back(std::make_pair(Stop, VNI)); 410 } 411 } 412 413 // Handle dead values. 414 bool CanSeparate = false; 415 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 416 I != E; ++I) { 417 VNInfo *VNI = *I; 418 if (VNI->isUnused()) 419 continue; 420 LiveRange::iterator LRI = NewLR.FindSegmentContaining(VNI->def); 421 assert(LRI != NewLR.end() && "Missing segment for PHI"); 422 if (LRI->end != VNI->def.getDeadSlot()) 423 continue; 424 if (VNI->isPHIDef()) { 425 // This is a dead PHI. Remove it. 426 VNI->markUnused(); 427 NewLR.removeSegment(LRI->start, LRI->end); 428 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 429 CanSeparate = true; 430 } else { 431 // This is a dead def. Make sure the instruction knows. 432 MachineInstr *MI = getInstructionFromIndex(VNI->def); 433 assert(MI && "No instruction defining live value"); 434 MI->addRegisterDead(li->reg, TRI); 435 if (dead && MI->allDefsAreDead()) { 436 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 437 dead->push_back(MI); 438 } 439 } 440 } 441 442 // Move the trimmed segments back. 443 li->segments.swap(NewLR.segments); 444 DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 445 return CanSeparate; 446} 447 448void LiveIntervals::extendToIndices(LiveRange &LR, 449 ArrayRef<SlotIndex> Indices) { 450 assert(LRCalc && "LRCalc not initialized."); 451 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); 452 for (unsigned i = 0, e = Indices.size(); i != e; ++i) 453 LRCalc->extend(LR, Indices[i]); 454} 455 456void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, 457 SmallVectorImpl<SlotIndex> *EndPoints) { 458 LiveQueryResult LRQ = LI->Query(Kill); 459 VNInfo *VNI = LRQ.valueOut(); 460 if (!VNI) 461 return; 462 463 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill); 464 SlotIndex MBBStart, MBBEnd; 465 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB); 466 467 // If VNI isn't live out from KillMBB, the value is trivially pruned. 468 if (LRQ.endPoint() < MBBEnd) { 469 LI->removeSegment(Kill, LRQ.endPoint()); 470 if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 471 return; 472 } 473 474 // VNI is live out of KillMBB. 475 LI->removeSegment(Kill, MBBEnd); 476 if (EndPoints) EndPoints->push_back(MBBEnd); 477 478 // Find all blocks that are reachable from KillMBB without leaving VNI's live 479 // range. It is possible that KillMBB itself is reachable, so start a DFS 480 // from each successor. 481 typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy; 482 VisitedTy Visited; 483 for (MachineBasicBlock::succ_iterator 484 SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end(); 485 SuccI != SuccE; ++SuccI) { 486 for (df_ext_iterator<MachineBasicBlock*, VisitedTy> 487 I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited); 488 I != E;) { 489 MachineBasicBlock *MBB = *I; 490 491 // Check if VNI is live in to MBB. 492 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB); 493 LiveQueryResult LRQ = LI->Query(MBBStart); 494 if (LRQ.valueIn() != VNI) { 495 // This block isn't part of the VNI segment. Prune the search. 496 I.skipChildren(); 497 continue; 498 } 499 500 // Prune the search if VNI is killed in MBB. 501 if (LRQ.endPoint() < MBBEnd) { 502 LI->removeSegment(MBBStart, LRQ.endPoint()); 503 if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 504 I.skipChildren(); 505 continue; 506 } 507 508 // VNI is live through MBB. 509 LI->removeSegment(MBBStart, MBBEnd); 510 if (EndPoints) EndPoints->push_back(MBBEnd); 511 ++I; 512 } 513 } 514} 515 516//===----------------------------------------------------------------------===// 517// Register allocator hooks. 518// 519 520void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { 521 // Keep track of regunit ranges. 522 SmallVector<std::pair<LiveRange*, LiveRange::iterator>, 8> RU; 523 524 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 525 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 526 if (MRI->reg_nodbg_empty(Reg)) 527 continue; 528 LiveInterval *LI = &getInterval(Reg); 529 if (LI->empty()) 530 continue; 531 532 // Find the regunit intervals for the assigned register. They may overlap 533 // the virtual register live range, cancelling any kills. 534 RU.clear(); 535 for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid(); 536 ++Units) { 537 LiveRange &RURanges = getRegUnit(*Units); 538 if (RURanges.empty()) 539 continue; 540 RU.push_back(std::make_pair(&RURanges, RURanges.find(LI->begin()->end))); 541 } 542 543 // Every instruction that kills Reg corresponds to a segment range end 544 // point. 545 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 546 ++RI) { 547 // A block index indicates an MBB edge. 548 if (RI->end.isBlock()) 549 continue; 550 MachineInstr *MI = getInstructionFromIndex(RI->end); 551 if (!MI) 552 continue; 553 554 // Check if any of the regunits are live beyond the end of RI. That could 555 // happen when a physreg is defined as a copy of a virtreg: 556 // 557 // %EAX = COPY %vreg5 558 // FOO %vreg5 <--- MI, cancel kill because %EAX is live. 559 // BAR %EAX<kill> 560 // 561 // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. 562 bool CancelKill = false; 563 for (unsigned u = 0, e = RU.size(); u != e; ++u) { 564 LiveRange &RRanges = *RU[u].first; 565 LiveRange::iterator &I = RU[u].second; 566 if (I == RRanges.end()) 567 continue; 568 I = RRanges.advanceTo(I, RI->end); 569 if (I == RRanges.end() || I->start >= RI->end) 570 continue; 571 // I is overlapping RI. 572 CancelKill = true; 573 break; 574 } 575 if (CancelKill) 576 MI->clearRegisterKills(Reg, nullptr); 577 else 578 MI->addRegisterKilled(Reg, nullptr); 579 } 580 } 581} 582 583MachineBasicBlock* 584LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 585 // A local live range must be fully contained inside the block, meaning it is 586 // defined and killed at instructions, not at block boundaries. It is not 587 // live in or or out of any block. 588 // 589 // It is technically possible to have a PHI-defined live range identical to a 590 // single block, but we are going to return false in that case. 591 592 SlotIndex Start = LI.beginIndex(); 593 if (Start.isBlock()) 594 return nullptr; 595 596 SlotIndex Stop = LI.endIndex(); 597 if (Stop.isBlock()) 598 return nullptr; 599 600 // getMBBFromIndex doesn't need to search the MBB table when both indexes 601 // belong to proper instructions. 602 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); 603 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); 604 return MBB1 == MBB2 ? MBB1 : nullptr; 605} 606 607bool 608LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { 609 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 610 I != E; ++I) { 611 const VNInfo *PHI = *I; 612 if (PHI->isUnused() || !PHI->isPHIDef()) 613 continue; 614 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); 615 // Conservatively return true instead of scanning huge predecessor lists. 616 if (PHIMBB->pred_size() > 100) 617 return true; 618 for (MachineBasicBlock::const_pred_iterator 619 PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) 620 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI))) 621 return true; 622 } 623 return false; 624} 625 626float 627LiveIntervals::getSpillWeight(bool isDef, bool isUse, 628 const MachineBlockFrequencyInfo *MBFI, 629 const MachineInstr *MI) { 630 BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent()); 631 const float Scale = 1.0f / MBFI->getEntryFreq(); 632 return (isDef + isUse) * (Freq.getFrequency() * Scale); 633} 634 635LiveRange::Segment 636LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) { 637 LiveInterval& Interval = createEmptyInterval(reg); 638 VNInfo* VN = Interval.getNextValue( 639 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 640 getVNInfoAllocator()); 641 LiveRange::Segment S( 642 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 643 getMBBEndIdx(startInst->getParent()), VN); 644 Interval.addSegment(S); 645 646 return S; 647} 648 649 650//===----------------------------------------------------------------------===// 651// Register mask functions 652//===----------------------------------------------------------------------===// 653 654bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 655 BitVector &UsableRegs) { 656 if (LI.empty()) 657 return false; 658 LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 659 660 // Use a smaller arrays for local live ranges. 661 ArrayRef<SlotIndex> Slots; 662 ArrayRef<const uint32_t*> Bits; 663 if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 664 Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 665 Bits = getRegMaskBitsInBlock(MBB->getNumber()); 666 } else { 667 Slots = getRegMaskSlots(); 668 Bits = getRegMaskBits(); 669 } 670 671 // We are going to enumerate all the register mask slots contained in LI. 672 // Start with a binary search of RegMaskSlots to find a starting point. 673 ArrayRef<SlotIndex>::iterator SlotI = 674 std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 675 ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 676 677 // No slots in range, LI begins after the last call. 678 if (SlotI == SlotE) 679 return false; 680 681 bool Found = false; 682 for (;;) { 683 assert(*SlotI >= LiveI->start); 684 // Loop over all slots overlapping this segment. 685 while (*SlotI < LiveI->end) { 686 // *SlotI overlaps LI. Collect mask bits. 687 if (!Found) { 688 // This is the first overlap. Initialize UsableRegs to all ones. 689 UsableRegs.clear(); 690 UsableRegs.resize(TRI->getNumRegs(), true); 691 Found = true; 692 } 693 // Remove usable registers clobbered by this mask. 694 UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 695 if (++SlotI == SlotE) 696 return Found; 697 } 698 // *SlotI is beyond the current LI segment. 699 LiveI = LI.advanceTo(LiveI, *SlotI); 700 if (LiveI == LiveE) 701 return Found; 702 // Advance SlotI until it overlaps. 703 while (*SlotI < LiveI->start) 704 if (++SlotI == SlotE) 705 return Found; 706 } 707} 708 709//===----------------------------------------------------------------------===// 710// IntervalUpdate class. 711//===----------------------------------------------------------------------===// 712 713// HMEditor is a toolkit used by handleMove to trim or extend live intervals. 714class LiveIntervals::HMEditor { 715private: 716 LiveIntervals& LIS; 717 const MachineRegisterInfo& MRI; 718 const TargetRegisterInfo& TRI; 719 SlotIndex OldIdx; 720 SlotIndex NewIdx; 721 SmallPtrSet<LiveRange*, 8> Updated; 722 bool UpdateFlags; 723 724public: 725 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 726 const TargetRegisterInfo& TRI, 727 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) 728 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), 729 UpdateFlags(UpdateFlags) {} 730 731 // FIXME: UpdateFlags is a workaround that creates live intervals for all 732 // physregs, even those that aren't needed for regalloc, in order to update 733 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill 734 // flags, and postRA passes will use a live register utility instead. 735 LiveRange *getRegUnitLI(unsigned Unit) { 736 if (UpdateFlags) 737 return &LIS.getRegUnit(Unit); 738 return LIS.getCachedRegUnit(Unit); 739 } 740 741 /// Update all live ranges touched by MI, assuming a move from OldIdx to 742 /// NewIdx. 743 void updateAllRanges(MachineInstr *MI) { 744 DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); 745 bool hasRegMask = false; 746 for (MIOperands MO(MI); MO.isValid(); ++MO) { 747 if (MO->isRegMask()) 748 hasRegMask = true; 749 if (!MO->isReg()) 750 continue; 751 // Aggressively clear all kill flags. 752 // They are reinserted by VirtRegRewriter. 753 if (MO->isUse()) 754 MO->setIsKill(false); 755 756 unsigned Reg = MO->getReg(); 757 if (!Reg) 758 continue; 759 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 760 LiveInterval &LI = LIS.getInterval(Reg); 761 updateRange(LI, Reg); 762 continue; 763 } 764 765 // For physregs, only update the regunits that actually have a 766 // precomputed live range. 767 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) 768 if (LiveRange *LR = getRegUnitLI(*Units)) 769 updateRange(*LR, *Units); 770 } 771 if (hasRegMask) 772 updateRegMaskSlots(); 773 } 774 775private: 776 /// Update a single live range, assuming an instruction has been moved from 777 /// OldIdx to NewIdx. 778 void updateRange(LiveRange &LR, unsigned Reg) { 779 if (!Updated.insert(&LR)) 780 return; 781 DEBUG({ 782 dbgs() << " "; 783 if (TargetRegisterInfo::isVirtualRegister(Reg)) 784 dbgs() << PrintReg(Reg); 785 else 786 dbgs() << PrintRegUnit(Reg, &TRI); 787 dbgs() << ":\t" << LR << '\n'; 788 }); 789 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) 790 handleMoveDown(LR); 791 else 792 handleMoveUp(LR, Reg); 793 DEBUG(dbgs() << " -->\t" << LR << '\n'); 794 LR.verify(); 795 } 796 797 /// Update LR to reflect an instruction has been moved downwards from OldIdx 798 /// to NewIdx. 799 /// 800 /// 1. Live def at OldIdx: 801 /// Move def to NewIdx, assert endpoint after NewIdx. 802 /// 803 /// 2. Live def at OldIdx, killed at NewIdx: 804 /// Change to dead def at NewIdx. 805 /// (Happens when bundling def+kill together). 806 /// 807 /// 3. Dead def at OldIdx: 808 /// Move def to NewIdx, possibly across another live value. 809 /// 810 /// 4. Def at OldIdx AND at NewIdx: 811 /// Remove segment [OldIdx;NewIdx) and value defined at OldIdx. 812 /// (Happens when bundling multiple defs together). 813 /// 814 /// 5. Value read at OldIdx, killed before NewIdx: 815 /// Extend kill to NewIdx. 816 /// 817 void handleMoveDown(LiveRange &LR) { 818 // First look for a kill at OldIdx. 819 LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); 820 LiveRange::iterator E = LR.end(); 821 // Is LR even live at OldIdx? 822 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 823 return; 824 825 // Handle a live-in value. 826 if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 827 bool isKill = SlotIndex::isSameInstr(OldIdx, I->end); 828 // If the live-in value already extends to NewIdx, there is nothing to do. 829 if (!SlotIndex::isEarlierInstr(I->end, NewIdx)) 830 return; 831 // Aggressively remove all kill flags from the old kill point. 832 // Kill flags shouldn't be used while live intervals exist, they will be 833 // reinserted by VirtRegRewriter. 834 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end)) 835 for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) 836 if (MO->isReg() && MO->isUse()) 837 MO->setIsKill(false); 838 // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by 839 // overlapping ranges. Case 5 above. 840 I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 841 // If this was a kill, there may also be a def. Otherwise we're done. 842 if (!isKill) 843 return; 844 ++I; 845 } 846 847 // Check for a def at OldIdx. 848 if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start)) 849 return; 850 // We have a def at OldIdx. 851 VNInfo *DefVNI = I->valno; 852 assert(DefVNI->def == I->start && "Inconsistent def"); 853 DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 854 // If the defined value extends beyond NewIdx, just move the def down. 855 // This is case 1 above. 856 if (SlotIndex::isEarlierInstr(NewIdx, I->end)) { 857 I->start = DefVNI->def; 858 return; 859 } 860 // The remaining possibilities are now: 861 // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx). 862 // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot(). 863 // In either case, it is possible that there is an existing def at NewIdx. 864 assert((I->end == OldIdx.getDeadSlot() || 865 SlotIndex::isSameInstr(I->end, NewIdx)) && 866 "Cannot move def below kill"); 867 LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot()); 868 if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) { 869 // There is an existing def at NewIdx, case 4 above. The def at OldIdx is 870 // coalesced into that value. 871 assert(NewI->valno != DefVNI && "Multiple defs of value?"); 872 LR.removeValNo(DefVNI); 873 return; 874 } 875 // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx. 876 // If the def at OldIdx was dead, we allow it to be moved across other LR 877 // values. The new range should be placed immediately before NewI, move any 878 // intermediate ranges up. 879 assert(NewI != I && "Inconsistent iterators"); 880 std::copy(std::next(I), NewI, I); 881 *std::prev(NewI) 882 = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 883 } 884 885 /// Update LR to reflect an instruction has been moved upwards from OldIdx 886 /// to NewIdx. 887 /// 888 /// 1. Live def at OldIdx: 889 /// Hoist def to NewIdx. 890 /// 891 /// 2. Dead def at OldIdx: 892 /// Hoist def+end to NewIdx, possibly move across other values. 893 /// 894 /// 3. Dead def at OldIdx AND existing def at NewIdx: 895 /// Remove value defined at OldIdx, coalescing it with existing value. 896 /// 897 /// 4. Live def at OldIdx AND existing def at NewIdx: 898 /// Remove value defined at NewIdx, hoist OldIdx def to NewIdx. 899 /// (Happens when bundling multiple defs together). 900 /// 901 /// 5. Value killed at OldIdx: 902 /// Hoist kill to NewIdx, then scan for last kill between NewIdx and 903 /// OldIdx. 904 /// 905 void handleMoveUp(LiveRange &LR, unsigned Reg) { 906 // First look for a kill at OldIdx. 907 LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); 908 LiveRange::iterator E = LR.end(); 909 // Is LR even live at OldIdx? 910 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 911 return; 912 913 // Handle a live-in value. 914 if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 915 // If the live-in value isn't killed here, there is nothing to do. 916 if (!SlotIndex::isSameInstr(OldIdx, I->end)) 917 return; 918 // Adjust I->end to end at NewIdx. If we are hoisting a kill above 919 // another use, we need to search for that use. Case 5 above. 920 I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 921 ++I; 922 // If OldIdx also defines a value, there couldn't have been another use. 923 if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) { 924 // No def, search for the new kill. 925 // This can never be an early clobber kill since there is no def. 926 std::prev(I)->end = findLastUseBefore(Reg).getRegSlot(); 927 return; 928 } 929 } 930 931 // Now deal with the def at OldIdx. 932 assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?"); 933 VNInfo *DefVNI = I->valno; 934 assert(DefVNI->def == I->start && "Inconsistent def"); 935 DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 936 937 // Check for an existing def at NewIdx. 938 LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot()); 939 if (SlotIndex::isSameInstr(NewI->start, NewIdx)) { 940 assert(NewI->valno != DefVNI && "Same value defined more than once?"); 941 // There is an existing def at NewIdx. 942 if (I->end.isDead()) { 943 // Case 3: Remove the dead def at OldIdx. 944 LR.removeValNo(DefVNI); 945 return; 946 } 947 // Case 4: Replace def at NewIdx with live def at OldIdx. 948 I->start = DefVNI->def; 949 LR.removeValNo(NewI->valno); 950 return; 951 } 952 953 // There is no existing def at NewIdx. Hoist DefVNI. 954 if (!I->end.isDead()) { 955 // Leave the end point of a live def. 956 I->start = DefVNI->def; 957 return; 958 } 959 960 // DefVNI is a dead def. It may have been moved across other values in LR, 961 // so move I up to NewI. Slide [NewI;I) down one position. 962 std::copy_backward(NewI, I, std::next(I)); 963 *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 964 } 965 966 void updateRegMaskSlots() { 967 SmallVectorImpl<SlotIndex>::iterator RI = 968 std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), 969 OldIdx); 970 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && 971 "No RegMask at OldIdx."); 972 *RI = NewIdx.getRegSlot(); 973 assert((RI == LIS.RegMaskSlots.begin() || 974 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) && 975 "Cannot move regmask instruction above another call"); 976 assert((std::next(RI) == LIS.RegMaskSlots.end() || 977 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) && 978 "Cannot move regmask instruction below another call"); 979 } 980 981 // Return the last use of reg between NewIdx and OldIdx. 982 SlotIndex findLastUseBefore(unsigned Reg) { 983 984 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 985 SlotIndex LastUse = NewIdx; 986 for (MachineRegisterInfo::use_instr_nodbg_iterator 987 UI = MRI.use_instr_nodbg_begin(Reg), 988 UE = MRI.use_instr_nodbg_end(); 989 UI != UE; ++UI) { 990 const MachineInstr* MI = &*UI; 991 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 992 if (InstSlot > LastUse && InstSlot < OldIdx) 993 LastUse = InstSlot; 994 } 995 return LastUse; 996 } 997 998 // This is a regunit interval, so scanning the use list could be very 999 // expensive. Scan upwards from OldIdx instead. 1000 assert(NewIdx < OldIdx && "Expected upwards move"); 1001 SlotIndexes *Indexes = LIS.getSlotIndexes(); 1002 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); 1003 1004 // OldIdx may not correspond to an instruction any longer, so set MII to 1005 // point to the next instruction after OldIdx, or MBB->end(). 1006 MachineBasicBlock::iterator MII = MBB->end(); 1007 if (MachineInstr *MI = Indexes->getInstructionFromIndex( 1008 Indexes->getNextNonNullIndex(OldIdx))) 1009 if (MI->getParent() == MBB) 1010 MII = MI; 1011 1012 MachineBasicBlock::iterator Begin = MBB->begin(); 1013 while (MII != Begin) { 1014 if ((--MII)->isDebugValue()) 1015 continue; 1016 SlotIndex Idx = Indexes->getInstructionIndex(MII); 1017 1018 // Stop searching when NewIdx is reached. 1019 if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) 1020 return NewIdx; 1021 1022 // Check if MII uses Reg. 1023 for (MIBundleOperands MO(MII); MO.isValid(); ++MO) 1024 if (MO->isReg() && 1025 TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && 1026 TRI.hasRegUnit(MO->getReg(), Reg)) 1027 return Idx; 1028 } 1029 // Didn't reach NewIdx. It must be the first instruction in the block. 1030 return NewIdx; 1031 } 1032}; 1033 1034void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) { 1035 assert(!MI->isBundled() && "Can't handle bundled instructions yet."); 1036 SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1037 Indexes->removeMachineInstrFromMaps(MI); 1038 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); 1039 assert(getMBBStartIdx(MI->getParent()) <= OldIndex && 1040 OldIndex < getMBBEndIdx(MI->getParent()) && 1041 "Cannot handle moves across basic block boundaries."); 1042 1043 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1044 HME.updateAllRanges(MI); 1045} 1046 1047void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, 1048 MachineInstr* BundleStart, 1049 bool UpdateFlags) { 1050 SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1051 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); 1052 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1053 HME.updateAllRanges(MI); 1054} 1055 1056void 1057LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, 1058 MachineBasicBlock::iterator Begin, 1059 MachineBasicBlock::iterator End, 1060 ArrayRef<unsigned> OrigRegs) { 1061 // Find anchor points, which are at the beginning/end of blocks or at 1062 // instructions that already have indexes. 1063 while (Begin != MBB->begin() && !Indexes->hasIndex(Begin)) 1064 --Begin; 1065 while (End != MBB->end() && !Indexes->hasIndex(End)) 1066 ++End; 1067 1068 SlotIndex endIdx; 1069 if (End == MBB->end()) 1070 endIdx = getMBBEndIdx(MBB).getPrevSlot(); 1071 else 1072 endIdx = getInstructionIndex(End); 1073 1074 Indexes->repairIndexesInRange(MBB, Begin, End); 1075 1076 for (MachineBasicBlock::iterator I = End; I != Begin;) { 1077 --I; 1078 MachineInstr *MI = I; 1079 if (MI->isDebugValue()) 1080 continue; 1081 for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), 1082 MOE = MI->operands_end(); MOI != MOE; ++MOI) { 1083 if (MOI->isReg() && 1084 TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && 1085 !hasInterval(MOI->getReg())) { 1086 createAndComputeVirtRegInterval(MOI->getReg()); 1087 } 1088 } 1089 } 1090 1091 for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { 1092 unsigned Reg = OrigRegs[i]; 1093 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1094 continue; 1095 1096 LiveInterval &LI = getInterval(Reg); 1097 // FIXME: Should we support undefs that gain defs? 1098 if (!LI.hasAtLeastOneValue()) 1099 continue; 1100 1101 LiveInterval::iterator LII = LI.find(endIdx); 1102 SlotIndex lastUseIdx; 1103 if (LII != LI.end() && LII->start < endIdx) 1104 lastUseIdx = LII->end; 1105 else 1106 --LII; 1107 1108 for (MachineBasicBlock::iterator I = End; I != Begin;) { 1109 --I; 1110 MachineInstr *MI = I; 1111 if (MI->isDebugValue()) 1112 continue; 1113 1114 SlotIndex instrIdx = getInstructionIndex(MI); 1115 bool isStartValid = getInstructionFromIndex(LII->start); 1116 bool isEndValid = getInstructionFromIndex(LII->end); 1117 1118 // FIXME: This doesn't currently handle early-clobber or multiple removed 1119 // defs inside of the region to repair. 1120 for (MachineInstr::mop_iterator OI = MI->operands_begin(), 1121 OE = MI->operands_end(); OI != OE; ++OI) { 1122 const MachineOperand &MO = *OI; 1123 if (!MO.isReg() || MO.getReg() != Reg) 1124 continue; 1125 1126 if (MO.isDef()) { 1127 if (!isStartValid) { 1128 if (LII->end.isDead()) { 1129 SlotIndex prevStart; 1130 if (LII != LI.begin()) 1131 prevStart = std::prev(LII)->start; 1132 1133 // FIXME: This could be more efficient if there was a 1134 // removeSegment method that returned an iterator. 1135 LI.removeSegment(*LII, true); 1136 if (prevStart.isValid()) 1137 LII = LI.find(prevStart); 1138 else 1139 LII = LI.begin(); 1140 } else { 1141 LII->start = instrIdx.getRegSlot(); 1142 LII->valno->def = instrIdx.getRegSlot(); 1143 if (MO.getSubReg() && !MO.isUndef()) 1144 lastUseIdx = instrIdx.getRegSlot(); 1145 else 1146 lastUseIdx = SlotIndex(); 1147 continue; 1148 } 1149 } 1150 1151 if (!lastUseIdx.isValid()) { 1152 VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), 1153 VNInfoAllocator); 1154 LiveRange::Segment S(instrIdx.getRegSlot(), 1155 instrIdx.getDeadSlot(), VNI); 1156 LII = LI.addSegment(S); 1157 } else if (LII->start != instrIdx.getRegSlot()) { 1158 VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), 1159 VNInfoAllocator); 1160 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI); 1161 LII = LI.addSegment(S); 1162 } 1163 1164 if (MO.getSubReg() && !MO.isUndef()) 1165 lastUseIdx = instrIdx.getRegSlot(); 1166 else 1167 lastUseIdx = SlotIndex(); 1168 } else if (MO.isUse()) { 1169 // FIXME: This should probably be handled outside of this branch, 1170 // either as part of the def case (for defs inside of the region) or 1171 // after the loop over the region. 1172 if (!isEndValid && !LII->end.isBlock()) 1173 LII->end = instrIdx.getRegSlot(); 1174 if (!lastUseIdx.isValid()) 1175 lastUseIdx = instrIdx.getRegSlot(); 1176 } 1177 } 1178 } 1179 } 1180} 1181