LiveIntervalAnalysis.cpp revision 5f5f3b6333ed5ecaf40699e8cd0b1aba524cbf0f
1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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 "liveintervals" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "VirtRegMap.h" 21#include "llvm/Value.h" 22#include "llvm/Analysis/LoopInfo.h" 23#include "llvm/CodeGen/LiveVariables.h" 24#include "llvm/CodeGen/MachineFrameInfo.h" 25#include "llvm/CodeGen/MachineInstr.h" 26#include "llvm/CodeGen/Passes.h" 27#include "llvm/CodeGen/SSARegMap.h" 28#include "llvm/Target/MRegisterInfo.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/ADT/Statistic.h" 34#include "llvm/ADT/STLExtras.h" 35#include <algorithm> 36#include <cmath> 37using namespace llvm; 38 39namespace { 40 // Hidden options for help debugging. 41 cl::opt<bool> DisableReMat("disable-rematerialization", 42 cl::init(false), cl::Hidden); 43} 44 45STATISTIC(numIntervals, "Number of original intervals"); 46STATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 47STATISTIC(numFolded , "Number of loads/stores folded into instructions"); 48 49char LiveIntervals::ID = 0; 50namespace { 51 RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 52} 53 54void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 55 AU.addPreserved<LiveVariables>(); 56 AU.addRequired<LiveVariables>(); 57 AU.addPreservedID(PHIEliminationID); 58 AU.addRequiredID(PHIEliminationID); 59 AU.addRequiredID(TwoAddressInstructionPassID); 60 AU.addRequired<LoopInfo>(); 61 MachineFunctionPass::getAnalysisUsage(AU); 62} 63 64void LiveIntervals::releaseMemory() { 65 Idx2MBBMap.clear(); 66 mi2iMap_.clear(); 67 i2miMap_.clear(); 68 r2iMap_.clear(); 69 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 70 VNInfoAllocator.Reset(); 71 for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 72 delete ClonedMIs[i]; 73} 74 75namespace llvm { 76 inline bool operator<(unsigned V, const IdxMBBPair &IM) { 77 return V < IM.first; 78 } 79 80 inline bool operator<(const IdxMBBPair &IM, unsigned V) { 81 return IM.first < V; 82 } 83 84 struct Idx2MBBCompare { 85 bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const { 86 return LHS.first < RHS.first; 87 } 88 }; 89} 90 91/// runOnMachineFunction - Register allocate the whole function 92/// 93bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 94 mf_ = &fn; 95 tm_ = &fn.getTarget(); 96 mri_ = tm_->getRegisterInfo(); 97 tii_ = tm_->getInstrInfo(); 98 lv_ = &getAnalysis<LiveVariables>(); 99 allocatableRegs_ = mri_->getAllocatableSet(fn); 100 101 // Number MachineInstrs and MachineBasicBlocks. 102 // Initialize MBB indexes to a sentinal. 103 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 104 105 unsigned MIIndex = 0; 106 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 107 MBB != E; ++MBB) { 108 unsigned StartIdx = MIIndex; 109 110 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 111 I != E; ++I) { 112 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 113 assert(inserted && "multiple MachineInstr -> index mappings"); 114 i2miMap_.push_back(I); 115 MIIndex += InstrSlots::NUM; 116 } 117 118 // Set the MBB2IdxMap entry for this MBB. 119 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 120 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 121 } 122 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 123 124 computeIntervals(); 125 126 numIntervals += getNumIntervals(); 127 128 DOUT << "********** INTERVALS **********\n"; 129 for (iterator I = begin(), E = end(); I != E; ++I) { 130 I->second.print(DOUT, mri_); 131 DOUT << "\n"; 132 } 133 134 numIntervalsAfter += getNumIntervals(); 135 DEBUG(dump()); 136 return true; 137} 138 139/// print - Implement the dump method. 140void LiveIntervals::print(std::ostream &O, const Module* ) const { 141 O << "********** INTERVALS **********\n"; 142 for (const_iterator I = begin(), E = end(); I != E; ++I) { 143 I->second.print(DOUT, mri_); 144 DOUT << "\n"; 145 } 146 147 O << "********** MACHINEINSTRS **********\n"; 148 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 149 mbbi != mbbe; ++mbbi) { 150 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 151 for (MachineBasicBlock::iterator mii = mbbi->begin(), 152 mie = mbbi->end(); mii != mie; ++mii) { 153 O << getInstructionIndex(mii) << '\t' << *mii; 154 } 155 } 156} 157 158/// isReMaterializable - Returns true if the definition MI of the specified 159/// val# of the specified interval is re-materializable. 160bool LiveIntervals::isReMaterializable(const LiveInterval &li, 161 const VNInfo *ValNo, MachineInstr *MI) { 162 if (DisableReMat) 163 return false; 164 165 if (tii_->isTriviallyReMaterializable(MI)) 166 return true; 167 168 int FrameIdx = 0; 169 if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || 170 !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)) 171 return false; 172 173 // This is a load from fixed stack slot. It can be rematerialized unless it's 174 // re-defined by a two-address instruction. 175 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 176 i != e; ++i) { 177 const VNInfo *VNI = *i; 178 if (VNI == ValNo) 179 continue; 180 unsigned DefIdx = VNI->def; 181 if (DefIdx == ~1U) 182 continue; // Dead val#. 183 MachineInstr *DefMI = (DefIdx == ~0u) 184 ? NULL : getInstructionFromIndex(DefIdx); 185 if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) 186 return false; 187 } 188 return true; 189} 190 191/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 192/// slot / to reg or any rematerialized load into ith operand of specified 193/// MI. If it is successul, MI is updated with the newly created MI and 194/// returns true. 195bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, 196 MachineInstr *DefMI, 197 unsigned index, unsigned i, 198 bool isSS, int slot, unsigned reg) { 199 MachineInstr *fmi = isSS 200 ? mri_->foldMemoryOperand(MI, i, slot) 201 : mri_->foldMemoryOperand(MI, i, DefMI); 202 if (fmi) { 203 // Attempt to fold the memory reference into the instruction. If 204 // we can do this, we don't need to insert spill code. 205 if (lv_) 206 lv_->instructionChanged(MI, fmi); 207 MachineBasicBlock &MBB = *MI->getParent(); 208 vrm.virtFolded(reg, MI, i, fmi); 209 mi2iMap_.erase(MI); 210 i2miMap_[index/InstrSlots::NUM] = fmi; 211 mi2iMap_[fmi] = index; 212 MI = MBB.insert(MBB.erase(MI), fmi); 213 ++numFolded; 214 return true; 215 } 216 return false; 217} 218 219std::vector<LiveInterval*> LiveIntervals:: 220addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) { 221 // since this is called after the analysis is done we don't know if 222 // LiveVariables is available 223 lv_ = getAnalysisToUpdate<LiveVariables>(); 224 225 std::vector<LiveInterval*> added; 226 227 assert(li.weight != HUGE_VALF && 228 "attempt to spill already spilled interval!"); 229 230 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 231 li.print(DOUT, mri_); 232 DOUT << '\n'; 233 234 SSARegMap *RegMap = mf_->getSSARegMap(); 235 const TargetRegisterClass* rc = RegMap->getRegClass(li.reg); 236 237 unsigned NumValNums = li.getNumValNums(); 238 SmallVector<MachineInstr*, 4> ReMatDefs; 239 ReMatDefs.resize(NumValNums, NULL); 240 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 241 ReMatOrigDefs.resize(NumValNums, NULL); 242 SmallVector<int, 4> ReMatIds; 243 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 244 BitVector ReMatDelete(NumValNums); 245 unsigned slot = VirtRegMap::MAX_STACK_SLOT; 246 247 bool NeedStackSlot = false; 248 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 249 i != e; ++i) { 250 const VNInfo *VNI = *i; 251 unsigned VN = VNI->id; 252 unsigned DefIdx = VNI->def; 253 if (DefIdx == ~1U) 254 continue; // Dead val#. 255 // Is the def for the val# rematerializable? 256 MachineInstr *DefMI = (DefIdx == ~0u) 257 ? NULL : getInstructionFromIndex(DefIdx); 258 if (DefMI && isReMaterializable(li, VNI, DefMI)) { 259 // Remember how to remat the def of this val#. 260 ReMatOrigDefs[VN] = DefMI; 261 // Original def may be modified so we have to make a copy here. vrm must 262 // delete these! 263 ReMatDefs[VN] = DefMI = DefMI->clone(); 264 vrm.setVirtIsReMaterialized(reg, DefMI); 265 266 bool CanDelete = true; 267 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 268 unsigned KillIdx = VNI->kills[j]; 269 MachineInstr *KillMI = (KillIdx & 1) 270 ? NULL : getInstructionFromIndex(KillIdx); 271 // Kill is a phi node, not all of its uses can be rematerialized. 272 // It must not be deleted. 273 if (!KillMI) { 274 CanDelete = false; 275 // Need a stack slot if there is any live range where uses cannot be 276 // rematerialized. 277 NeedStackSlot = true; 278 break; 279 } 280 } 281 282 if (CanDelete) 283 ReMatDelete.set(VN); 284 } else { 285 // Need a stack slot if there is any live range where uses cannot be 286 // rematerialized. 287 NeedStackSlot = true; 288 } 289 } 290 291 // One stack slot per live interval. 292 if (NeedStackSlot) 293 slot = vrm.assignVirt2StackSlot(reg); 294 295 for (LiveInterval::Ranges::const_iterator 296 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 297 MachineInstr *DefMI = ReMatDefs[I->valno->id]; 298 MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id]; 299 bool DefIsReMat = DefMI != NULL; 300 bool CanDelete = ReMatDelete[I->valno->id]; 301 int LdSlot = 0; 302 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot); 303 bool isLoad = isLoadSS || 304 (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); 305 unsigned index = getBaseIndex(I->start); 306 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 307 for (; index != end; index += InstrSlots::NUM) { 308 // skip deleted instructions 309 while (index != end && !getInstructionFromIndex(index)) 310 index += InstrSlots::NUM; 311 if (index == end) break; 312 313 MachineInstr *MI = getInstructionFromIndex(index); 314 315 RestartInstruction: 316 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 317 MachineOperand& mop = MI->getOperand(i); 318 if (!mop.isRegister()) 319 continue; 320 unsigned Reg = mop.getReg(); 321 if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg)) 322 continue; 323 bool isSubReg = RegMap->isSubRegister(Reg); 324 unsigned SubIdx = 0; 325 if (isSubReg) { 326 SubIdx = RegMap->getSubRegisterIndex(Reg); 327 Reg = RegMap->getSuperRegister(Reg); 328 } 329 if (Reg != li.reg) 330 continue; 331 332 bool TryFold = !DefIsReMat; 333 bool FoldSS = true; 334 int FoldSlot = slot; 335 if (DefIsReMat) { 336 // If this is the rematerializable definition MI itself and 337 // all of its uses are rematerialized, simply delete it. 338 if (MI == OrigDefMI && CanDelete) { 339 RemoveMachineInstrFromMaps(MI); 340 MI->eraseFromParent(); 341 break; 342 } 343 344 // If def for this use can't be rematerialized, then try folding. 345 TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad)); 346 if (isLoad) { 347 // Try fold loads (from stack slot, constant pool, etc.) into uses. 348 FoldSS = isLoadSS; 349 FoldSlot = LdSlot; 350 } 351 } 352 353 // FIXME: fold subreg use 354 if (!isSubReg && TryFold && 355 tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg)) 356 // Folding the load/store can completely change the instruction in 357 // unpredictable ways, rescan it from the beginning. 358 goto RestartInstruction; 359 360 // Create a new virtual register for the spill interval. 361 unsigned NewVReg = RegMap->createVirtualRegister(rc); 362 if (isSubReg) 363 RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx); 364 365 // Scan all of the operands of this instruction rewriting operands 366 // to use NewVReg instead of li.reg as appropriate. We do this for 367 // two reasons: 368 // 369 // 1. If the instr reads the same spilled vreg multiple times, we 370 // want to reuse the NewVReg. 371 // 2. If the instr is a two-addr instruction, we are required to 372 // keep the src/dst regs pinned. 373 // 374 // Keep track of whether we replace a use and/or def so that we can 375 // create the spill interval with the appropriate range. 376 mop.setReg(NewVReg); 377 378 bool HasUse = mop.isUse(); 379 bool HasDef = mop.isDef(); 380 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 381 if (MI->getOperand(j).isRegister() && 382 MI->getOperand(j).getReg() == li.reg) { 383 MI->getOperand(j).setReg(NewVReg); 384 HasUse |= MI->getOperand(j).isUse(); 385 HasDef |= MI->getOperand(j).isDef(); 386 } 387 } 388 389 vrm.grow(); 390 if (DefIsReMat) { 391 vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/); 392 if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) { 393 // Each valnum may have its own remat id. 394 ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg); 395 } else { 396 vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]); 397 } 398 if (!CanDelete || (HasUse && HasDef)) { 399 // If this is a two-addr instruction then its use operands are 400 // rematerializable but its def is not. It should be assigned a 401 // stack slot. 402 vrm.assignVirt2StackSlot(NewVReg, slot); 403 } 404 } else { 405 vrm.assignVirt2StackSlot(NewVReg, slot); 406 } 407 408 // create a new register interval for this spill / remat. 409 LiveInterval &nI = getOrCreateInterval(NewVReg); 410 assert(nI.empty()); 411 412 // the spill weight is now infinity as it 413 // cannot be spilled again 414 nI.weight = HUGE_VALF; 415 416 if (HasUse) { 417 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 418 nI.getNextValue(~0U, 0, VNInfoAllocator)); 419 DOUT << " +" << LR; 420 nI.addRange(LR); 421 } 422 if (HasDef) { 423 LiveRange LR(getDefIndex(index), getStoreIndex(index), 424 nI.getNextValue(~0U, 0, VNInfoAllocator)); 425 DOUT << " +" << LR; 426 nI.addRange(LR); 427 } 428 429 added.push_back(&nI); 430 431 // update live variables if it is available 432 if (lv_) 433 lv_->addVirtualRegisterKilled(NewVReg, MI); 434 435 DOUT << "\t\t\t\tadded new interval: "; 436 nI.print(DOUT, mri_); 437 DOUT << '\n'; 438 } 439 } 440 } 441 442 return added; 443} 444 445/// conflictsWithPhysRegDef - Returns true if the specified register 446/// is defined during the duration of the specified interval. 447bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 448 VirtRegMap &vrm, unsigned reg) { 449 for (LiveInterval::Ranges::const_iterator 450 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 451 for (unsigned index = getBaseIndex(I->start), 452 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 453 index += InstrSlots::NUM) { 454 // skip deleted instructions 455 while (index != end && !getInstructionFromIndex(index)) 456 index += InstrSlots::NUM; 457 if (index == end) break; 458 459 MachineInstr *MI = getInstructionFromIndex(index); 460 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 461 MachineOperand& mop = MI->getOperand(i); 462 if (!mop.isRegister() || !mop.isDef()) 463 continue; 464 unsigned PhysReg = mop.getReg(); 465 if (PhysReg == 0) 466 continue; 467 if (MRegisterInfo::isVirtualRegister(PhysReg)) 468 PhysReg = vrm.getPhys(PhysReg); 469 if (PhysReg && mri_->regsOverlap(PhysReg, reg)) 470 return true; 471 } 472 } 473 } 474 475 return false; 476} 477 478void LiveIntervals::printRegName(unsigned reg) const { 479 if (MRegisterInfo::isPhysicalRegister(reg)) 480 cerr << mri_->getName(reg); 481 else 482 cerr << "%reg" << reg; 483} 484 485void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 486 MachineBasicBlock::iterator mi, 487 unsigned MIIdx, 488 LiveInterval &interval) { 489 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 490 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 491 492 // Virtual registers may be defined multiple times (due to phi 493 // elimination and 2-addr elimination). Much of what we do only has to be 494 // done once for the vreg. We use an empty interval to detect the first 495 // time we see a vreg. 496 if (interval.empty()) { 497 // Get the Idx of the defining instructions. 498 unsigned defIndex = getDefIndex(MIIdx); 499 VNInfo *ValNo; 500 unsigned SrcReg, DstReg; 501 if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) 502 ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); 503 else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 504 ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), 505 VNInfoAllocator); 506 else 507 ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); 508 509 assert(ValNo->id == 0 && "First value in interval is not 0?"); 510 511 // Loop over all of the blocks that the vreg is defined in. There are 512 // two cases we have to handle here. The most common case is a vreg 513 // whose lifetime is contained within a basic block. In this case there 514 // will be a single kill, in MBB, which comes after the definition. 515 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 516 // FIXME: what about dead vars? 517 unsigned killIdx; 518 if (vi.Kills[0] != mi) 519 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 520 else 521 killIdx = defIndex+1; 522 523 // If the kill happens after the definition, we have an intra-block 524 // live range. 525 if (killIdx > defIndex) { 526 assert(vi.AliveBlocks.none() && 527 "Shouldn't be alive across any blocks!"); 528 LiveRange LR(defIndex, killIdx, ValNo); 529 interval.addRange(LR); 530 DOUT << " +" << LR << "\n"; 531 interval.addKill(ValNo, killIdx); 532 return; 533 } 534 } 535 536 // The other case we handle is when a virtual register lives to the end 537 // of the defining block, potentially live across some blocks, then is 538 // live into some number of blocks, but gets killed. Start by adding a 539 // range that goes from this definition to the end of the defining block. 540 LiveRange NewLR(defIndex, 541 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 542 ValNo); 543 DOUT << " +" << NewLR; 544 interval.addRange(NewLR); 545 546 // Iterate over all of the blocks that the variable is completely 547 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 548 // live interval. 549 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 550 if (vi.AliveBlocks[i]) { 551 MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 552 if (!MBB->empty()) { 553 LiveRange LR(getMBBStartIdx(i), 554 getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 555 ValNo); 556 interval.addRange(LR); 557 DOUT << " +" << LR; 558 } 559 } 560 } 561 562 // Finally, this virtual register is live from the start of any killing 563 // block to the 'use' slot of the killing instruction. 564 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 565 MachineInstr *Kill = vi.Kills[i]; 566 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 567 LiveRange LR(getMBBStartIdx(Kill->getParent()), 568 killIdx, ValNo); 569 interval.addRange(LR); 570 interval.addKill(ValNo, killIdx); 571 DOUT << " +" << LR; 572 } 573 574 } else { 575 // If this is the second time we see a virtual register definition, it 576 // must be due to phi elimination or two addr elimination. If this is 577 // the result of two address elimination, then the vreg is one of the 578 // def-and-use register operand. 579 if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 580 // If this is a two-address definition, then we have already processed 581 // the live range. The only problem is that we didn't realize there 582 // are actually two values in the live interval. Because of this we 583 // need to take the LiveRegion that defines this register and split it 584 // into two values. 585 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 586 unsigned RedefIndex = getDefIndex(MIIdx); 587 588 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 589 VNInfo *OldValNo = OldLR->valno; 590 unsigned OldEnd = OldLR->end; 591 592 // Delete the initial value, which should be short and continuous, 593 // because the 2-addr copy must be in the same MBB as the redef. 594 interval.removeRange(DefIndex, RedefIndex); 595 596 // Two-address vregs should always only be redefined once. This means 597 // that at this point, there should be exactly one value number in it. 598 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 599 600 // The new value number (#1) is defined by the instruction we claimed 601 // defined value #0. 602 VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator); 603 interval.copyValNumInfo(ValNo, OldValNo); 604 605 // Value#0 is now defined by the 2-addr instruction. 606 OldValNo->def = RedefIndex; 607 OldValNo->reg = 0; 608 609 // Add the new live interval which replaces the range for the input copy. 610 LiveRange LR(DefIndex, RedefIndex, ValNo); 611 DOUT << " replace range with " << LR; 612 interval.addRange(LR); 613 interval.addKill(ValNo, RedefIndex); 614 interval.removeKills(ValNo, RedefIndex, OldEnd); 615 616 // If this redefinition is dead, we need to add a dummy unit live 617 // range covering the def slot. 618 if (lv_->RegisterDefIsDead(mi, interval.reg)) 619 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 620 621 DOUT << " RESULT: "; 622 interval.print(DOUT, mri_); 623 624 } else { 625 // Otherwise, this must be because of phi elimination. If this is the 626 // first redefinition of the vreg that we have seen, go back and change 627 // the live range in the PHI block to be a different value number. 628 if (interval.containsOneValue()) { 629 assert(vi.Kills.size() == 1 && 630 "PHI elimination vreg should have one kill, the PHI itself!"); 631 632 // Remove the old range that we now know has an incorrect number. 633 VNInfo *VNI = interval.getValNumInfo(0); 634 MachineInstr *Killer = vi.Kills[0]; 635 unsigned Start = getMBBStartIdx(Killer->getParent()); 636 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 637 DOUT << " Removing [" << Start << "," << End << "] from: "; 638 interval.print(DOUT, mri_); DOUT << "\n"; 639 interval.removeRange(Start, End); 640 interval.addKill(VNI, Start+1); // odd # means phi node 641 DOUT << " RESULT: "; interval.print(DOUT, mri_); 642 643 // Replace the interval with one of a NEW value number. Note that this 644 // value number isn't actually defined by an instruction, weird huh? :) 645 LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 646 DOUT << " replace range with " << LR; 647 interval.addRange(LR); 648 interval.addKill(LR.valno, End); 649 DOUT << " RESULT: "; interval.print(DOUT, mri_); 650 } 651 652 // In the case of PHI elimination, each variable definition is only 653 // live until the end of the block. We've already taken care of the 654 // rest of the live range. 655 unsigned defIndex = getDefIndex(MIIdx); 656 657 VNInfo *ValNo; 658 unsigned SrcReg, DstReg; 659 if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) 660 ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); 661 else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 662 ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), 663 VNInfoAllocator); 664 else 665 ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); 666 667 unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 668 LiveRange LR(defIndex, killIndex, ValNo); 669 interval.addRange(LR); 670 interval.addKill(ValNo, killIndex-1); // odd # means phi node 671 DOUT << " +" << LR; 672 } 673 } 674 675 DOUT << '\n'; 676} 677 678void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 679 MachineBasicBlock::iterator mi, 680 unsigned MIIdx, 681 LiveInterval &interval, 682 unsigned SrcReg) { 683 // A physical register cannot be live across basic block, so its 684 // lifetime must end somewhere in its defining basic block. 685 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 686 687 unsigned baseIndex = MIIdx; 688 unsigned start = getDefIndex(baseIndex); 689 unsigned end = start; 690 691 // If it is not used after definition, it is considered dead at 692 // the instruction defining it. Hence its interval is: 693 // [defSlot(def), defSlot(def)+1) 694 if (lv_->RegisterDefIsDead(mi, interval.reg)) { 695 DOUT << " dead"; 696 end = getDefIndex(start) + 1; 697 goto exit; 698 } 699 700 // If it is not dead on definition, it must be killed by a 701 // subsequent instruction. Hence its interval is: 702 // [defSlot(def), useSlot(kill)+1) 703 while (++mi != MBB->end()) { 704 baseIndex += InstrSlots::NUM; 705 if (lv_->KillsRegister(mi, interval.reg)) { 706 DOUT << " killed"; 707 end = getUseIndex(baseIndex) + 1; 708 goto exit; 709 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 710 // Another instruction redefines the register before it is ever read. 711 // Then the register is essentially dead at the instruction that defines 712 // it. Hence its interval is: 713 // [defSlot(def), defSlot(def)+1) 714 DOUT << " dead"; 715 end = getDefIndex(start) + 1; 716 goto exit; 717 } 718 } 719 720 // The only case we should have a dead physreg here without a killing or 721 // instruction where we know it's dead is if it is live-in to the function 722 // and never used. 723 assert(!SrcReg && "physreg was not killed in defining block!"); 724 end = getDefIndex(start) + 1; // It's dead. 725 726exit: 727 assert(start < end && "did not find end of interval?"); 728 729 // Already exists? Extend old live interval. 730 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 731 VNInfo *ValNo = (OldLR != interval.end()) 732 ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator); 733 LiveRange LR(start, end, ValNo); 734 interval.addRange(LR); 735 interval.addKill(LR.valno, end); 736 DOUT << " +" << LR << '\n'; 737} 738 739void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 740 MachineBasicBlock::iterator MI, 741 unsigned MIIdx, 742 unsigned reg) { 743 if (MRegisterInfo::isVirtualRegister(reg)) 744 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 745 else if (allocatableRegs_[reg]) { 746 unsigned SrcReg, DstReg; 747 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 748 SrcReg = MI->getOperand(1).getReg(); 749 else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) 750 SrcReg = 0; 751 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); 752 // Def of a register also defines its sub-registers. 753 for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS) 754 // Avoid processing some defs more than once. 755 if (!MI->findRegisterDefOperand(*AS)) 756 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 757 } 758} 759 760void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 761 unsigned MIIdx, 762 LiveInterval &interval, bool isAlias) { 763 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 764 765 // Look for kills, if it reaches a def before it's killed, then it shouldn't 766 // be considered a livein. 767 MachineBasicBlock::iterator mi = MBB->begin(); 768 unsigned baseIndex = MIIdx; 769 unsigned start = baseIndex; 770 unsigned end = start; 771 while (mi != MBB->end()) { 772 if (lv_->KillsRegister(mi, interval.reg)) { 773 DOUT << " killed"; 774 end = getUseIndex(baseIndex) + 1; 775 goto exit; 776 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 777 // Another instruction redefines the register before it is ever read. 778 // Then the register is essentially dead at the instruction that defines 779 // it. Hence its interval is: 780 // [defSlot(def), defSlot(def)+1) 781 DOUT << " dead"; 782 end = getDefIndex(start) + 1; 783 goto exit; 784 } 785 786 baseIndex += InstrSlots::NUM; 787 ++mi; 788 } 789 790exit: 791 // Live-in register might not be used at all. 792 if (end == MIIdx) { 793 if (isAlias) { 794 DOUT << " dead"; 795 end = getDefIndex(MIIdx) + 1; 796 } else { 797 DOUT << " live through"; 798 end = baseIndex; 799 } 800 } 801 802 LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 803 interval.addRange(LR); 804 interval.addKill(LR.valno, end); 805 DOUT << " +" << LR << '\n'; 806} 807 808/// computeIntervals - computes the live intervals for virtual 809/// registers. for some ordering of the machine instructions [1,N] a 810/// live interval is an interval [i, j) where 1 <= i <= j < N for 811/// which a variable is live 812void LiveIntervals::computeIntervals() { 813 DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 814 << "********** Function: " 815 << ((Value*)mf_->getFunction())->getName() << '\n'; 816 // Track the index of the current machine instr. 817 unsigned MIIndex = 0; 818 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 819 MBBI != E; ++MBBI) { 820 MachineBasicBlock *MBB = MBBI; 821 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 822 823 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 824 825 // Create intervals for live-ins to this BB first. 826 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 827 LE = MBB->livein_end(); LI != LE; ++LI) { 828 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 829 // Multiple live-ins can alias the same register. 830 for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 831 if (!hasInterval(*AS)) 832 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 833 true); 834 } 835 836 for (; MI != miEnd; ++MI) { 837 DOUT << MIIndex << "\t" << *MI; 838 839 // Handle defs. 840 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 841 MachineOperand &MO = MI->getOperand(i); 842 // handle register defs - build intervals 843 if (MO.isRegister() && MO.getReg() && MO.isDef()) 844 handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 845 } 846 847 MIIndex += InstrSlots::NUM; 848 } 849 } 850} 851 852bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 853 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 854 std::vector<IdxMBBPair>::const_iterator I = 855 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 856 857 bool ResVal = false; 858 while (I != Idx2MBBMap.end()) { 859 if (LR.end <= I->first) 860 break; 861 MBBs.push_back(I->second); 862 ResVal = true; 863 ++I; 864 } 865 return ResVal; 866} 867 868 869LiveInterval LiveIntervals::createInterval(unsigned reg) { 870 float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 871 HUGE_VALF : 0.0F; 872 return LiveInterval(reg, Weight); 873} 874