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