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