LiveIntervalAnalysis.cpp revision b1aa5e43a2976caed47e21d31823a48bf8324000
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 LiveRangeQuery LRQ(*li, 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 a new live interval with only minimal live segments per def. 352 LiveInterval NewLI(li->reg, 0); 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 NewLI.addRange(LiveRange(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 = NewLI.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 NewLI.addRange(LiveRange(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 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 416 assert(LII != NewLI.end() && "Missing live range for PHI"); 417 if (LII->end != VNI->def.getDeadSlot()) 418 continue; 419 if (VNI->isPHIDef()) { 420 // This is a dead PHI. Remove it. 421 VNI->markUnused(); 422 NewLI.removeRange(*LII); 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 ranges back. 438 li->ranges.swap(NewLI.ranges); 439 DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 440 return CanSeparate; 441} 442 443void LiveIntervals::extendToIndices(LiveInterval *LI, 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(LI, Indices[i]); 449} 450 451void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill, 452 SmallVectorImpl<SlotIndex> *EndPoints) { 453 LiveRangeQuery LRQ(*LI, 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->removeRange(Kill, LRQ.endPoint()); 465 if (EndPoints) EndPoints->push_back(LRQ.endPoint()); 466 return; 467 } 468 469 // VNI is live out of KillMBB. 470 LI->removeRange(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 LiveRangeQuery LRQ(*LI, MBBStart); 489 if (LRQ.valueIn() != VNI) { 490 // This block isn't part of the VNI live range. 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->removeRange(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->removeRange(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 live range end point. 539 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 540 ++RI) { 541 // A block index indicates an MBB edge. 542 if (RI->end.isBlock()) 543 continue; 544 MachineInstr *MI = getInstructionFromIndex(RI->end); 545 if (!MI) 546 continue; 547 548 // Check if any of the regunits are live beyond the end of RI. That could 549 // happen when a physreg is defined as a copy of a virtreg: 550 // 551 // %EAX = COPY %vreg5 552 // FOO %vreg5 <--- MI, cancel kill because %EAX is live. 553 // BAR %EAX<kill> 554 // 555 // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX. 556 bool CancelKill = false; 557 for (unsigned u = 0, e = RU.size(); u != e; ++u) { 558 LiveInterval *RInt = RU[u].first; 559 LiveInterval::iterator &I = RU[u].second; 560 if (I == RInt->end()) 561 continue; 562 I = RInt->advanceTo(I, RI->end); 563 if (I == RInt->end() || I->start >= RI->end) 564 continue; 565 // I is overlapping RI. 566 CancelKill = true; 567 break; 568 } 569 if (CancelKill) 570 MI->clearRegisterKills(Reg, NULL); 571 else 572 MI->addRegisterKilled(Reg, NULL); 573 } 574 } 575} 576 577MachineBasicBlock* 578LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 579 // A local live range must be fully contained inside the block, meaning it is 580 // defined and killed at instructions, not at block boundaries. It is not 581 // live in or or out of any block. 582 // 583 // It is technically possible to have a PHI-defined live range identical to a 584 // single block, but we are going to return false in that case. 585 586 SlotIndex Start = LI.beginIndex(); 587 if (Start.isBlock()) 588 return NULL; 589 590 SlotIndex Stop = LI.endIndex(); 591 if (Stop.isBlock()) 592 return NULL; 593 594 // getMBBFromIndex doesn't need to search the MBB table when both indexes 595 // belong to proper instructions. 596 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start); 597 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop); 598 return MBB1 == MBB2 ? MBB1 : NULL; 599} 600 601bool 602LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { 603 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); 604 I != E; ++I) { 605 const VNInfo *PHI = *I; 606 if (PHI->isUnused() || !PHI->isPHIDef()) 607 continue; 608 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); 609 // Conservatively return true instead of scanning huge predecessor lists. 610 if (PHIMBB->pred_size() > 100) 611 return true; 612 for (MachineBasicBlock::const_pred_iterator 613 PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI) 614 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI))) 615 return true; 616 } 617 return false; 618} 619 620float 621LiveIntervals::getSpillWeight(bool isDef, bool isUse, BlockFrequency freq) { 622 const float Scale = 1.0f / BlockFrequency::getEntryFrequency(); 623 return (isDef + isUse) * (freq.getFrequency() * Scale); 624} 625 626LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 627 MachineInstr* startInst) { 628 LiveInterval& Interval = createEmptyInterval(reg); 629 VNInfo* VN = Interval.getNextValue( 630 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 631 getVNInfoAllocator()); 632 LiveRange LR( 633 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 634 getMBBEndIdx(startInst->getParent()), VN); 635 Interval.addRange(LR); 636 637 return LR; 638} 639 640 641//===----------------------------------------------------------------------===// 642// Register mask functions 643//===----------------------------------------------------------------------===// 644 645bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 646 BitVector &UsableRegs) { 647 if (LI.empty()) 648 return false; 649 LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 650 651 // Use a smaller arrays for local live ranges. 652 ArrayRef<SlotIndex> Slots; 653 ArrayRef<const uint32_t*> Bits; 654 if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 655 Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 656 Bits = getRegMaskBitsInBlock(MBB->getNumber()); 657 } else { 658 Slots = getRegMaskSlots(); 659 Bits = getRegMaskBits(); 660 } 661 662 // We are going to enumerate all the register mask slots contained in LI. 663 // Start with a binary search of RegMaskSlots to find a starting point. 664 ArrayRef<SlotIndex>::iterator SlotI = 665 std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 666 ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 667 668 // No slots in range, LI begins after the last call. 669 if (SlotI == SlotE) 670 return false; 671 672 bool Found = false; 673 for (;;) { 674 assert(*SlotI >= LiveI->start); 675 // Loop over all slots overlapping this segment. 676 while (*SlotI < LiveI->end) { 677 // *SlotI overlaps LI. Collect mask bits. 678 if (!Found) { 679 // This is the first overlap. Initialize UsableRegs to all ones. 680 UsableRegs.clear(); 681 UsableRegs.resize(TRI->getNumRegs(), true); 682 Found = true; 683 } 684 // Remove usable registers clobbered by this mask. 685 UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 686 if (++SlotI == SlotE) 687 return Found; 688 } 689 // *SlotI is beyond the current LI segment. 690 LiveI = LI.advanceTo(LiveI, *SlotI); 691 if (LiveI == LiveE) 692 return Found; 693 // Advance SlotI until it overlaps. 694 while (*SlotI < LiveI->start) 695 if (++SlotI == SlotE) 696 return Found; 697 } 698} 699 700//===----------------------------------------------------------------------===// 701// IntervalUpdate class. 702//===----------------------------------------------------------------------===// 703 704// HMEditor is a toolkit used by handleMove to trim or extend live intervals. 705class LiveIntervals::HMEditor { 706private: 707 LiveIntervals& LIS; 708 const MachineRegisterInfo& MRI; 709 const TargetRegisterInfo& TRI; 710 SlotIndex OldIdx; 711 SlotIndex NewIdx; 712 SmallPtrSet<LiveInterval*, 8> Updated; 713 bool UpdateFlags; 714 715public: 716 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 717 const TargetRegisterInfo& TRI, 718 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags) 719 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx), 720 UpdateFlags(UpdateFlags) {} 721 722 // FIXME: UpdateFlags is a workaround that creates live intervals for all 723 // physregs, even those that aren't needed for regalloc, in order to update 724 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill 725 // flags, and postRA passes will use a live register utility instead. 726 LiveInterval *getRegUnitLI(unsigned Unit) { 727 if (UpdateFlags) 728 return &LIS.getRegUnit(Unit); 729 return LIS.getCachedRegUnit(Unit); 730 } 731 732 /// Update all live ranges touched by MI, assuming a move from OldIdx to 733 /// NewIdx. 734 void updateAllRanges(MachineInstr *MI) { 735 DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI); 736 bool hasRegMask = false; 737 for (MIOperands MO(MI); MO.isValid(); ++MO) { 738 if (MO->isRegMask()) 739 hasRegMask = true; 740 if (!MO->isReg()) 741 continue; 742 // Aggressively clear all kill flags. 743 // They are reinserted by VirtRegRewriter. 744 if (MO->isUse()) 745 MO->setIsKill(false); 746 747 unsigned Reg = MO->getReg(); 748 if (!Reg) 749 continue; 750 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 751 updateRange(LIS.getInterval(Reg)); 752 continue; 753 } 754 755 // For physregs, only update the regunits that actually have a 756 // precomputed live range. 757 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) 758 if (LiveInterval *LI = getRegUnitLI(*Units)) 759 updateRange(*LI); 760 } 761 if (hasRegMask) 762 updateRegMaskSlots(); 763 } 764 765private: 766 /// Update a single live range, assuming an instruction has been moved from 767 /// OldIdx to NewIdx. 768 void updateRange(LiveInterval &LI) { 769 if (!Updated.insert(&LI)) 770 return; 771 DEBUG({ 772 dbgs() << " "; 773 if (TargetRegisterInfo::isVirtualRegister(LI.reg)) 774 dbgs() << PrintReg(LI.reg); 775 else 776 dbgs() << PrintRegUnit(LI.reg, &TRI); 777 dbgs() << ":\t" << LI << '\n'; 778 }); 779 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx)) 780 handleMoveDown(LI); 781 else 782 handleMoveUp(LI); 783 DEBUG(dbgs() << " -->\t" << LI << '\n'); 784 LI.verify(); 785 } 786 787 /// Update LI to reflect an instruction has been moved downwards from OldIdx 788 /// to NewIdx. 789 /// 790 /// 1. Live def at OldIdx: 791 /// Move def to NewIdx, assert endpoint after NewIdx. 792 /// 793 /// 2. Live def at OldIdx, killed at NewIdx: 794 /// Change to dead def at NewIdx. 795 /// (Happens when bundling def+kill together). 796 /// 797 /// 3. Dead def at OldIdx: 798 /// Move def to NewIdx, possibly across another live value. 799 /// 800 /// 4. Def at OldIdx AND at NewIdx: 801 /// Remove live range [OldIdx;NewIdx) and value defined at OldIdx. 802 /// (Happens when bundling multiple defs together). 803 /// 804 /// 5. Value read at OldIdx, killed before NewIdx: 805 /// Extend kill to NewIdx. 806 /// 807 void handleMoveDown(LiveInterval &LI) { 808 // First look for a kill at OldIdx. 809 LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex()); 810 LiveInterval::iterator E = LI.end(); 811 // Is LI even live at OldIdx? 812 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 813 return; 814 815 // Handle a live-in value. 816 if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 817 bool isKill = SlotIndex::isSameInstr(OldIdx, I->end); 818 // If the live-in value already extends to NewIdx, there is nothing to do. 819 if (!SlotIndex::isEarlierInstr(I->end, NewIdx)) 820 return; 821 // Aggressively remove all kill flags from the old kill point. 822 // Kill flags shouldn't be used while live intervals exist, they will be 823 // reinserted by VirtRegRewriter. 824 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end)) 825 for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO) 826 if (MO->isReg() && MO->isUse()) 827 MO->setIsKill(false); 828 // Adjust I->end to reach NewIdx. This may temporarily make LI invalid by 829 // overlapping ranges. Case 5 above. 830 I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 831 // If this was a kill, there may also be a def. Otherwise we're done. 832 if (!isKill) 833 return; 834 ++I; 835 } 836 837 // Check for a def at OldIdx. 838 if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start)) 839 return; 840 // We have a def at OldIdx. 841 VNInfo *DefVNI = I->valno; 842 assert(DefVNI->def == I->start && "Inconsistent def"); 843 DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 844 // If the defined value extends beyond NewIdx, just move the def down. 845 // This is case 1 above. 846 if (SlotIndex::isEarlierInstr(NewIdx, I->end)) { 847 I->start = DefVNI->def; 848 return; 849 } 850 // The remaining possibilities are now: 851 // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx). 852 // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot(). 853 // In either case, it is possible that there is an existing def at NewIdx. 854 assert((I->end == OldIdx.getDeadSlot() || 855 SlotIndex::isSameInstr(I->end, NewIdx)) && 856 "Cannot move def below kill"); 857 LiveInterval::iterator NewI = LI.advanceTo(I, NewIdx.getRegSlot()); 858 if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) { 859 // There is an existing def at NewIdx, case 4 above. The def at OldIdx is 860 // coalesced into that value. 861 assert(NewI->valno != DefVNI && "Multiple defs of value?"); 862 LI.removeValNo(DefVNI); 863 return; 864 } 865 // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx. 866 // If the def at OldIdx was dead, we allow it to be moved across other LI 867 // values. The new range should be placed immediately before NewI, move any 868 // intermediate ranges up. 869 assert(NewI != I && "Inconsistent iterators"); 870 std::copy(llvm::next(I), NewI, I); 871 *llvm::prior(NewI) = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 872 } 873 874 /// Update LI to reflect an instruction has been moved upwards from OldIdx 875 /// to NewIdx. 876 /// 877 /// 1. Live def at OldIdx: 878 /// Hoist def to NewIdx. 879 /// 880 /// 2. Dead def at OldIdx: 881 /// Hoist def+end to NewIdx, possibly move across other values. 882 /// 883 /// 3. Dead def at OldIdx AND existing def at NewIdx: 884 /// Remove value defined at OldIdx, coalescing it with existing value. 885 /// 886 /// 4. Live def at OldIdx AND existing def at NewIdx: 887 /// Remove value defined at NewIdx, hoist OldIdx def to NewIdx. 888 /// (Happens when bundling multiple defs together). 889 /// 890 /// 5. Value killed at OldIdx: 891 /// Hoist kill to NewIdx, then scan for last kill between NewIdx and 892 /// OldIdx. 893 /// 894 void handleMoveUp(LiveInterval &LI) { 895 // First look for a kill at OldIdx. 896 LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex()); 897 LiveInterval::iterator E = LI.end(); 898 // Is LI even live at OldIdx? 899 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start)) 900 return; 901 902 // Handle a live-in value. 903 if (!SlotIndex::isSameInstr(I->start, OldIdx)) { 904 // If the live-in value isn't killed here, there is nothing to do. 905 if (!SlotIndex::isSameInstr(OldIdx, I->end)) 906 return; 907 // Adjust I->end to end at NewIdx. If we are hoisting a kill above 908 // another use, we need to search for that use. Case 5 above. 909 I->end = NewIdx.getRegSlot(I->end.isEarlyClobber()); 910 ++I; 911 // If OldIdx also defines a value, there couldn't have been another use. 912 if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) { 913 // No def, search for the new kill. 914 // This can never be an early clobber kill since there is no def. 915 llvm::prior(I)->end = findLastUseBefore(LI.reg).getRegSlot(); 916 return; 917 } 918 } 919 920 // Now deal with the def at OldIdx. 921 assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?"); 922 VNInfo *DefVNI = I->valno; 923 assert(DefVNI->def == I->start && "Inconsistent def"); 924 DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber()); 925 926 // Check for an existing def at NewIdx. 927 LiveInterval::iterator NewI = LI.find(NewIdx.getRegSlot()); 928 if (SlotIndex::isSameInstr(NewI->start, NewIdx)) { 929 assert(NewI->valno != DefVNI && "Same value defined more than once?"); 930 // There is an existing def at NewIdx. 931 if (I->end.isDead()) { 932 // Case 3: Remove the dead def at OldIdx. 933 LI.removeValNo(DefVNI); 934 return; 935 } 936 // Case 4: Replace def at NewIdx with live def at OldIdx. 937 I->start = DefVNI->def; 938 LI.removeValNo(NewI->valno); 939 return; 940 } 941 942 // There is no existing def at NewIdx. Hoist DefVNI. 943 if (!I->end.isDead()) { 944 // Leave the end point of a live def. 945 I->start = DefVNI->def; 946 return; 947 } 948 949 // DefVNI is a dead def. It may have been moved across other values in LI, 950 // so move I up to NewI. Slide [NewI;I) down one position. 951 std::copy_backward(NewI, I, llvm::next(I)); 952 *NewI = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI); 953 } 954 955 void updateRegMaskSlots() { 956 SmallVectorImpl<SlotIndex>::iterator RI = 957 std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), 958 OldIdx); 959 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() && 960 "No RegMask at OldIdx."); 961 *RI = NewIdx.getRegSlot(); 962 assert((RI == LIS.RegMaskSlots.begin() || 963 SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) && 964 "Cannot move regmask instruction above another call"); 965 assert((llvm::next(RI) == LIS.RegMaskSlots.end() || 966 SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) && 967 "Cannot move regmask instruction below another call"); 968 } 969 970 // Return the last use of reg between NewIdx and OldIdx. 971 SlotIndex findLastUseBefore(unsigned Reg) { 972 973 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 974 SlotIndex LastUse = NewIdx; 975 for (MachineRegisterInfo::use_nodbg_iterator 976 UI = MRI.use_nodbg_begin(Reg), 977 UE = MRI.use_nodbg_end(); 978 UI != UE; UI.skipInstruction()) { 979 const MachineInstr* MI = &*UI; 980 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 981 if (InstSlot > LastUse && InstSlot < OldIdx) 982 LastUse = InstSlot; 983 } 984 return LastUse; 985 } 986 987 // This is a regunit interval, so scanning the use list could be very 988 // expensive. Scan upwards from OldIdx instead. 989 assert(NewIdx < OldIdx && "Expected upwards move"); 990 SlotIndexes *Indexes = LIS.getSlotIndexes(); 991 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx); 992 993 // OldIdx may not correspond to an instruction any longer, so set MII to 994 // point to the next instruction after OldIdx, or MBB->end(). 995 MachineBasicBlock::iterator MII = MBB->end(); 996 if (MachineInstr *MI = Indexes->getInstructionFromIndex( 997 Indexes->getNextNonNullIndex(OldIdx))) 998 if (MI->getParent() == MBB) 999 MII = MI; 1000 1001 MachineBasicBlock::iterator Begin = MBB->begin(); 1002 while (MII != Begin) { 1003 if ((--MII)->isDebugValue()) 1004 continue; 1005 SlotIndex Idx = Indexes->getInstructionIndex(MII); 1006 1007 // Stop searching when NewIdx is reached. 1008 if (!SlotIndex::isEarlierInstr(NewIdx, Idx)) 1009 return NewIdx; 1010 1011 // Check if MII uses Reg. 1012 for (MIBundleOperands MO(MII); MO.isValid(); ++MO) 1013 if (MO->isReg() && 1014 TargetRegisterInfo::isPhysicalRegister(MO->getReg()) && 1015 TRI.hasRegUnit(MO->getReg(), Reg)) 1016 return Idx; 1017 } 1018 // Didn't reach NewIdx. It must be the first instruction in the block. 1019 return NewIdx; 1020 } 1021}; 1022 1023void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) { 1024 assert(!MI->isBundled() && "Can't handle bundled instructions yet."); 1025 SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1026 Indexes->removeMachineInstrFromMaps(MI); 1027 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI); 1028 assert(getMBBStartIdx(MI->getParent()) <= OldIndex && 1029 OldIndex < getMBBEndIdx(MI->getParent()) && 1030 "Cannot handle moves across basic block boundaries."); 1031 1032 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1033 HME.updateAllRanges(MI); 1034} 1035 1036void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, 1037 MachineInstr* BundleStart, 1038 bool UpdateFlags) { 1039 SlotIndex OldIndex = Indexes->getInstructionIndex(MI); 1040 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart); 1041 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags); 1042 HME.updateAllRanges(MI); 1043} 1044 1045void 1046LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, 1047 MachineBasicBlock::iterator Begin, 1048 MachineBasicBlock::iterator End, 1049 ArrayRef<unsigned> OrigRegs) { 1050 // Find anchor points, which are at the beginning/end of blocks or at 1051 // instructions that already have indexes. 1052 while (Begin != MBB->begin() && !Indexes->hasIndex(Begin)) 1053 --Begin; 1054 while (End != MBB->end() && !Indexes->hasIndex(End)) 1055 ++End; 1056 1057 SlotIndex endIdx; 1058 if (End == MBB->end()) 1059 endIdx = getMBBEndIdx(MBB).getPrevSlot(); 1060 else 1061 endIdx = getInstructionIndex(End); 1062 1063 Indexes->repairIndexesInRange(MBB, Begin, End); 1064 1065 for (MachineBasicBlock::iterator I = End; I != Begin;) { 1066 --I; 1067 MachineInstr *MI = I; 1068 if (MI->isDebugValue()) 1069 continue; 1070 for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), 1071 MOE = MI->operands_end(); MOI != MOE; ++MOI) { 1072 if (MOI->isReg() && 1073 TargetRegisterInfo::isVirtualRegister(MOI->getReg()) && 1074 !hasInterval(MOI->getReg())) { 1075 createAndComputeVirtRegInterval(MOI->getReg()); 1076 } 1077 } 1078 } 1079 1080 for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) { 1081 unsigned Reg = OrigRegs[i]; 1082 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1083 continue; 1084 1085 LiveInterval &LI = getInterval(Reg); 1086 // FIXME: Should we support undefs that gain defs? 1087 if (!LI.hasAtLeastOneValue()) 1088 continue; 1089 1090 LiveInterval::iterator LII = LI.find(endIdx); 1091 SlotIndex lastUseIdx; 1092 if (LII != LI.end() && LII->start < endIdx) 1093 lastUseIdx = LII->end; 1094 else 1095 --LII; 1096 1097 for (MachineBasicBlock::iterator I = End; I != Begin;) { 1098 --I; 1099 MachineInstr *MI = I; 1100 if (MI->isDebugValue()) 1101 continue; 1102 1103 SlotIndex instrIdx = getInstructionIndex(MI); 1104 bool isStartValid = getInstructionFromIndex(LII->start); 1105 bool isEndValid = getInstructionFromIndex(LII->end); 1106 1107 // FIXME: This doesn't currently handle early-clobber or multiple removed 1108 // defs inside of the region to repair. 1109 for (MachineInstr::mop_iterator OI = MI->operands_begin(), 1110 OE = MI->operands_end(); OI != OE; ++OI) { 1111 const MachineOperand &MO = *OI; 1112 if (!MO.isReg() || MO.getReg() != Reg) 1113 continue; 1114 1115 if (MO.isDef()) { 1116 if (!isStartValid) { 1117 if (LII->end.isDead()) { 1118 SlotIndex prevStart; 1119 if (LII != LI.begin()) 1120 prevStart = llvm::prior(LII)->start; 1121 1122 // FIXME: This could be more efficient if there was a removeRange 1123 // method that returned an iterator. 1124 LI.removeRange(*LII, true); 1125 if (prevStart.isValid()) 1126 LII = LI.find(prevStart); 1127 else 1128 LII = LI.begin(); 1129 } else { 1130 LII->start = instrIdx.getRegSlot(); 1131 LII->valno->def = instrIdx.getRegSlot(); 1132 if (MO.getSubReg() && !MO.isUndef()) 1133 lastUseIdx = instrIdx.getRegSlot(); 1134 else 1135 lastUseIdx = SlotIndex(); 1136 continue; 1137 } 1138 } 1139 1140 if (!lastUseIdx.isValid()) { 1141 VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), 1142 VNInfoAllocator); 1143 LiveRange LR(instrIdx.getRegSlot(), instrIdx.getDeadSlot(), VNI); 1144 LII = LI.addRange(LR); 1145 } else if (LII->start != instrIdx.getRegSlot()) { 1146 VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(), 1147 VNInfoAllocator); 1148 LiveRange LR(instrIdx.getRegSlot(), lastUseIdx, VNI); 1149 LII = LI.addRange(LR); 1150 } 1151 1152 if (MO.getSubReg() && !MO.isUndef()) 1153 lastUseIdx = instrIdx.getRegSlot(); 1154 else 1155 lastUseIdx = SlotIndex(); 1156 } else if (MO.isUse()) { 1157 // FIXME: This should probably be handled outside of this branch, 1158 // either as part of the def case (for defs inside of the region) or 1159 // after the loop over the region. 1160 if (!isEndValid && !LII->end.isBlock()) 1161 LII->end = instrIdx.getRegSlot(); 1162 if (!lastUseIdx.isValid()) 1163 lastUseIdx = instrIdx.getRegSlot(); 1164 } 1165 } 1166 } 1167 } 1168} 1169