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