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