LiveIntervalAnalysis.cpp revision 34e85d0307e3c17e5061622dccf8a20e5457b099
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 "llvm/Value.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/CodeGen/LiveVariables.h" 23#include "llvm/CodeGen/MachineInstr.h" 24#include "llvm/CodeGen/MachineLoopInfo.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/CodeGen/Passes.h" 27#include "llvm/CodeGen/ProcessImplicitDefs.h" 28#include "llvm/Target/TargetRegisterInfo.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/Support/ErrorHandling.h" 34#include "llvm/Support/raw_ostream.h" 35#include "llvm/ADT/Statistic.h" 36#include "llvm/ADT/STLExtras.h" 37#include <algorithm> 38#include <limits> 39#include <cmath> 40using namespace llvm; 41 42// Hidden options for help debugging. 43static cl::opt<bool> DisableReMat("disable-rematerialization", 44 cl::init(false), cl::Hidden); 45 46STATISTIC(numIntervals , "Number of original intervals"); 47 48char LiveIntervals::ID = 0; 49INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 50 "Live Interval Analysis", false, false) 51INITIALIZE_PASS_DEPENDENCY(LiveVariables) 52INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 53INITIALIZE_PASS_DEPENDENCY(PHIElimination) 54INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 55INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs) 56INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 57INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 58INITIALIZE_PASS_END(LiveIntervals, "liveintervals", 59 "Live Interval Analysis", false, false) 60 61void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 62 AU.setPreservesCFG(); 63 AU.addRequired<AliasAnalysis>(); 64 AU.addPreserved<AliasAnalysis>(); 65 AU.addRequired<LiveVariables>(); 66 AU.addPreserved<LiveVariables>(); 67 AU.addRequired<MachineLoopInfo>(); 68 AU.addPreserved<MachineLoopInfo>(); 69 AU.addPreservedID(MachineDominatorsID); 70 71 if (!StrongPHIElim) { 72 AU.addPreservedID(PHIEliminationID); 73 AU.addRequiredID(PHIEliminationID); 74 } 75 76 AU.addRequiredID(TwoAddressInstructionPassID); 77 AU.addPreserved<ProcessImplicitDefs>(); 78 AU.addRequired<ProcessImplicitDefs>(); 79 AU.addPreserved<SlotIndexes>(); 80 AU.addRequiredTransitive<SlotIndexes>(); 81 MachineFunctionPass::getAnalysisUsage(AU); 82} 83 84void LiveIntervals::releaseMemory() { 85 // Free the live intervals themselves. 86 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 87 E = r2iMap_.end(); I != E; ++I) 88 delete I->second; 89 90 r2iMap_.clear(); 91 RegMaskSlots.clear(); 92 RegMaskBits.clear(); 93 RegMaskBlocks.clear(); 94 95 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 96 VNInfoAllocator.Reset(); 97} 98 99/// runOnMachineFunction - Register allocate the whole function 100/// 101bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 102 mf_ = &fn; 103 mri_ = &mf_->getRegInfo(); 104 tm_ = &fn.getTarget(); 105 tri_ = tm_->getRegisterInfo(); 106 tii_ = tm_->getInstrInfo(); 107 aa_ = &getAnalysis<AliasAnalysis>(); 108 lv_ = &getAnalysis<LiveVariables>(); 109 indexes_ = &getAnalysis<SlotIndexes>(); 110 allocatableRegs_ = tri_->getAllocatableSet(fn); 111 112 computeIntervals(); 113 114 numIntervals += getNumIntervals(); 115 116 DEBUG(dump()); 117 return true; 118} 119 120/// print - Implement the dump method. 121void LiveIntervals::print(raw_ostream &OS, const Module* ) const { 122 OS << "********** INTERVALS **********\n"; 123 for (const_iterator I = begin(), E = end(); I != E; ++I) { 124 I->second->print(OS, tri_); 125 OS << "\n"; 126 } 127 128 printInstrs(OS); 129} 130 131void LiveIntervals::printInstrs(raw_ostream &OS) const { 132 OS << "********** MACHINEINSTRS **********\n"; 133 mf_->print(OS, indexes_); 134} 135 136void LiveIntervals::dumpInstrs() const { 137 printInstrs(dbgs()); 138} 139 140static 141bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 142 unsigned Reg = MI.getOperand(MOIdx).getReg(); 143 for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 144 const MachineOperand &MO = MI.getOperand(i); 145 if (!MO.isReg()) 146 continue; 147 if (MO.getReg() == Reg && MO.isDef()) { 148 assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 149 MI.getOperand(MOIdx).getSubReg() && 150 (MO.getSubReg() || MO.isImplicit())); 151 return true; 152 } 153 } 154 return false; 155} 156 157/// isPartialRedef - Return true if the specified def at the specific index is 158/// partially re-defining the specified live interval. A common case of this is 159/// a definition of the sub-register. 160bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 161 LiveInterval &interval) { 162 if (!MO.getSubReg() || MO.isEarlyClobber()) 163 return false; 164 165 SlotIndex RedefIndex = MIIdx.getRegSlot(); 166 const LiveRange *OldLR = 167 interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 168 MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 169 if (DefMI != 0) { 170 return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 171 } 172 return false; 173} 174 175void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 176 MachineBasicBlock::iterator mi, 177 SlotIndex MIIdx, 178 MachineOperand& MO, 179 unsigned MOIdx, 180 LiveInterval &interval) { 181 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 182 183 // Virtual registers may be defined multiple times (due to phi 184 // elimination and 2-addr elimination). Much of what we do only has to be 185 // done once for the vreg. We use an empty interval to detect the first 186 // time we see a vreg. 187 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 188 if (interval.empty()) { 189 // Get the Idx of the defining instructions. 190 SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 191 192 // Make sure the first definition is not a partial redefinition. Add an 193 // <imp-def> of the full register. 194 // FIXME: LiveIntervals shouldn't modify the code like this. Whoever 195 // created the machine instruction should annotate it with <undef> flags 196 // as needed. Then we can simply assert here. The REG_SEQUENCE lowering 197 // is the main suspect. 198 if (MO.getSubReg()) { 199 mi->addRegisterDefined(interval.reg); 200 // Mark all defs of interval.reg on this instruction as reading <undef>. 201 for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) { 202 MachineOperand &MO2 = mi->getOperand(i); 203 if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg()) 204 MO2.setIsUndef(); 205 } 206 } 207 208 VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 209 assert(ValNo->id == 0 && "First value in interval is not 0?"); 210 211 // Loop over all of the blocks that the vreg is defined in. There are 212 // two cases we have to handle here. The most common case is a vreg 213 // whose lifetime is contained within a basic block. In this case there 214 // will be a single kill, in MBB, which comes after the definition. 215 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 216 // FIXME: what about dead vars? 217 SlotIndex killIdx; 218 if (vi.Kills[0] != mi) 219 killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); 220 else 221 killIdx = defIndex.getDeadSlot(); 222 223 // If the kill happens after the definition, we have an intra-block 224 // live range. 225 if (killIdx > defIndex) { 226 assert(vi.AliveBlocks.empty() && 227 "Shouldn't be alive across any blocks!"); 228 LiveRange LR(defIndex, killIdx, ValNo); 229 interval.addRange(LR); 230 DEBUG(dbgs() << " +" << LR << "\n"); 231 return; 232 } 233 } 234 235 // The other case we handle is when a virtual register lives to the end 236 // of the defining block, potentially live across some blocks, then is 237 // live into some number of blocks, but gets killed. Start by adding a 238 // range that goes from this definition to the end of the defining block. 239 LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 240 DEBUG(dbgs() << " +" << NewLR); 241 interval.addRange(NewLR); 242 243 bool PHIJoin = lv_->isPHIJoin(interval.reg); 244 245 if (PHIJoin) { 246 // A phi join register is killed at the end of the MBB and revived as a new 247 // valno in the killing blocks. 248 assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 249 DEBUG(dbgs() << " phi-join"); 250 ValNo->setHasPHIKill(true); 251 } else { 252 // Iterate over all of the blocks that the variable is completely 253 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 254 // live interval. 255 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 256 E = vi.AliveBlocks.end(); I != E; ++I) { 257 MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 258 LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 259 interval.addRange(LR); 260 DEBUG(dbgs() << " +" << LR); 261 } 262 } 263 264 // Finally, this virtual register is live from the start of any killing 265 // block to the 'use' slot of the killing instruction. 266 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 267 MachineInstr *Kill = vi.Kills[i]; 268 SlotIndex Start = getMBBStartIdx(Kill->getParent()); 269 SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); 270 271 // Create interval with one of a NEW value number. Note that this value 272 // number isn't actually defined by an instruction, weird huh? :) 273 if (PHIJoin) { 274 assert(getInstructionFromIndex(Start) == 0 && 275 "PHI def index points at actual instruction."); 276 ValNo = interval.getNextValue(Start, VNInfoAllocator); 277 ValNo->setIsPHIDef(true); 278 } 279 LiveRange LR(Start, killIdx, ValNo); 280 interval.addRange(LR); 281 DEBUG(dbgs() << " +" << LR); 282 } 283 284 } else { 285 if (MultipleDefsBySameMI(*mi, MOIdx)) 286 // Multiple defs of the same virtual register by the same instruction. 287 // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 288 // This is likely due to elimination of REG_SEQUENCE instructions. Return 289 // here since there is nothing to do. 290 return; 291 292 // If this is the second time we see a virtual register definition, it 293 // must be due to phi elimination or two addr elimination. If this is 294 // the result of two address elimination, then the vreg is one of the 295 // def-and-use register operand. 296 297 // It may also be partial redef like this: 298 // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 299 // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 300 bool PartReDef = isPartialRedef(MIIdx, MO, interval); 301 if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 302 // If this is a two-address definition, then we have already processed 303 // the live range. The only problem is that we didn't realize there 304 // are actually two values in the live interval. Because of this we 305 // need to take the LiveRegion that defines this register and split it 306 // into two values. 307 SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 308 309 const LiveRange *OldLR = 310 interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 311 VNInfo *OldValNo = OldLR->valno; 312 SlotIndex DefIndex = OldValNo->def.getRegSlot(); 313 314 // Delete the previous value, which should be short and continuous, 315 // because the 2-addr copy must be in the same MBB as the redef. 316 interval.removeRange(DefIndex, RedefIndex); 317 318 // The new value number (#1) is defined by the instruction we claimed 319 // defined value #0. 320 VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 321 322 // Value#0 is now defined by the 2-addr instruction. 323 OldValNo->def = RedefIndex; 324 325 // Add the new live interval which replaces the range for the input copy. 326 LiveRange LR(DefIndex, RedefIndex, ValNo); 327 DEBUG(dbgs() << " replace range with " << LR); 328 interval.addRange(LR); 329 330 // If this redefinition is dead, we need to add a dummy unit live 331 // range covering the def slot. 332 if (MO.isDead()) 333 interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), 334 OldValNo)); 335 336 DEBUG({ 337 dbgs() << " RESULT: "; 338 interval.print(dbgs(), tri_); 339 }); 340 } else if (lv_->isPHIJoin(interval.reg)) { 341 // In the case of PHI elimination, each variable definition is only 342 // live until the end of the block. We've already taken care of the 343 // rest of the live range. 344 345 SlotIndex defIndex = MIIdx.getRegSlot(); 346 if (MO.isEarlyClobber()) 347 defIndex = MIIdx.getRegSlot(true); 348 349 VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 350 351 SlotIndex killIndex = getMBBEndIdx(mbb); 352 LiveRange LR(defIndex, killIndex, ValNo); 353 interval.addRange(LR); 354 ValNo->setHasPHIKill(true); 355 DEBUG(dbgs() << " phi-join +" << LR); 356 } else { 357 llvm_unreachable("Multiply defined register"); 358 } 359 } 360 361 DEBUG(dbgs() << '\n'); 362} 363 364void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 365 MachineBasicBlock::iterator mi, 366 SlotIndex MIIdx, 367 MachineOperand& MO, 368 LiveInterval &interval) { 369 // A physical register cannot be live across basic block, so its 370 // lifetime must end somewhere in its defining basic block. 371 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 372 373 SlotIndex baseIndex = MIIdx; 374 SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber()); 375 SlotIndex end = start; 376 377 // If it is not used after definition, it is considered dead at 378 // the instruction defining it. Hence its interval is: 379 // [defSlot(def), defSlot(def)+1) 380 // For earlyclobbers, the defSlot was pushed back one; the extra 381 // advance below compensates. 382 if (MO.isDead()) { 383 DEBUG(dbgs() << " dead"); 384 end = start.getDeadSlot(); 385 goto exit; 386 } 387 388 // If it is not dead on definition, it must be killed by a 389 // subsequent instruction. Hence its interval is: 390 // [defSlot(def), useSlot(kill)+1) 391 baseIndex = baseIndex.getNextIndex(); 392 while (++mi != MBB->end()) { 393 394 if (mi->isDebugValue()) 395 continue; 396 if (getInstructionFromIndex(baseIndex) == 0) 397 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 398 399 if (mi->killsRegister(interval.reg, tri_)) { 400 DEBUG(dbgs() << " killed"); 401 end = baseIndex.getRegSlot(); 402 goto exit; 403 } else { 404 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 405 if (DefIdx != -1) { 406 if (mi->isRegTiedToUseOperand(DefIdx)) { 407 // Two-address instruction. 408 end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber()); 409 } else { 410 // Another instruction redefines the register before it is ever read. 411 // Then the register is essentially dead at the instruction that 412 // defines it. Hence its interval is: 413 // [defSlot(def), defSlot(def)+1) 414 DEBUG(dbgs() << " dead"); 415 end = start.getDeadSlot(); 416 } 417 goto exit; 418 } 419 } 420 421 baseIndex = baseIndex.getNextIndex(); 422 } 423 424 // The only case we should have a dead physreg here without a killing or 425 // instruction where we know it's dead is if it is live-in to the function 426 // and never used. Another possible case is the implicit use of the 427 // physical register has been deleted by two-address pass. 428 end = start.getDeadSlot(); 429 430exit: 431 assert(start < end && "did not find end of interval?"); 432 433 // Already exists? Extend old live interval. 434 VNInfo *ValNo = interval.getVNInfoAt(start); 435 bool Extend = ValNo != 0; 436 if (!Extend) 437 ValNo = interval.getNextValue(start, VNInfoAllocator); 438 LiveRange LR(start, end, ValNo); 439 interval.addRange(LR); 440 DEBUG(dbgs() << " +" << LR << '\n'); 441} 442 443void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 444 MachineBasicBlock::iterator MI, 445 SlotIndex MIIdx, 446 MachineOperand& MO, 447 unsigned MOIdx) { 448 if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 449 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 450 getOrCreateInterval(MO.getReg())); 451 else 452 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 453 getOrCreateInterval(MO.getReg())); 454} 455 456void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 457 SlotIndex MIIdx, 458 LiveInterval &interval, bool isAlias) { 459 DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 460 461 // Look for kills, if it reaches a def before it's killed, then it shouldn't 462 // be considered a livein. 463 MachineBasicBlock::iterator mi = MBB->begin(); 464 MachineBasicBlock::iterator E = MBB->end(); 465 // Skip over DBG_VALUE at the start of the MBB. 466 if (mi != E && mi->isDebugValue()) { 467 while (++mi != E && mi->isDebugValue()) 468 ; 469 if (mi == E) 470 // MBB is empty except for DBG_VALUE's. 471 return; 472 } 473 474 SlotIndex baseIndex = MIIdx; 475 SlotIndex start = baseIndex; 476 if (getInstructionFromIndex(baseIndex) == 0) 477 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 478 479 SlotIndex end = baseIndex; 480 bool SeenDefUse = false; 481 482 while (mi != E) { 483 if (mi->killsRegister(interval.reg, tri_)) { 484 DEBUG(dbgs() << " killed"); 485 end = baseIndex.getRegSlot(); 486 SeenDefUse = true; 487 break; 488 } else if (mi->definesRegister(interval.reg, tri_)) { 489 // Another instruction redefines the register before it is ever read. 490 // Then the register is essentially dead at the instruction that defines 491 // it. Hence its interval is: 492 // [defSlot(def), defSlot(def)+1) 493 DEBUG(dbgs() << " dead"); 494 end = start.getDeadSlot(); 495 SeenDefUse = true; 496 break; 497 } 498 499 while (++mi != E && mi->isDebugValue()) 500 // Skip over DBG_VALUE. 501 ; 502 if (mi != E) 503 baseIndex = indexes_->getNextNonNullIndex(baseIndex); 504 } 505 506 // Live-in register might not be used at all. 507 if (!SeenDefUse) { 508 if (isAlias) { 509 DEBUG(dbgs() << " dead"); 510 end = MIIdx.getDeadSlot(); 511 } else { 512 DEBUG(dbgs() << " live through"); 513 end = getMBBEndIdx(MBB); 514 } 515 } 516 517 SlotIndex defIdx = getMBBStartIdx(MBB); 518 assert(getInstructionFromIndex(defIdx) == 0 && 519 "PHI def index points at actual instruction."); 520 VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator); 521 vni->setIsPHIDef(true); 522 LiveRange LR(start, end, vni); 523 524 interval.addRange(LR); 525 DEBUG(dbgs() << " +" << LR << '\n'); 526} 527 528/// computeIntervals - computes the live intervals for virtual 529/// registers. for some ordering of the machine instructions [1,N] a 530/// live interval is an interval [i, j) where 1 <= i <= j < N for 531/// which a variable is live 532void LiveIntervals::computeIntervals() { 533 DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 534 << "********** Function: " 535 << ((Value*)mf_->getFunction())->getName() << '\n'); 536 537 RegMaskBlocks.resize(mf_->getNumBlockIDs()); 538 539 SmallVector<unsigned, 8> UndefUses; 540 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 541 MBBI != E; ++MBBI) { 542 MachineBasicBlock *MBB = MBBI; 543 RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); 544 545 if (MBB->empty()) 546 continue; 547 548 // Track the index of the current machine instr. 549 SlotIndex MIIndex = getMBBStartIdx(MBB); 550 DEBUG(dbgs() << "BB#" << MBB->getNumber() 551 << ":\t\t# derived from " << MBB->getName() << "\n"); 552 553 // Create intervals for live-ins to this BB first. 554 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 555 LE = MBB->livein_end(); LI != LE; ++LI) { 556 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 557 } 558 559 // Skip over empty initial indices. 560 if (getInstructionFromIndex(MIIndex) == 0) 561 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 562 563 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 564 MI != miEnd; ++MI) { 565 DEBUG(dbgs() << MIIndex << "\t" << *MI); 566 if (MI->isDebugValue()) 567 continue; 568 assert(indexes_->getInstructionFromIndex(MIIndex) == MI && 569 "Lost SlotIndex synchronization"); 570 571 // Handle defs. 572 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 573 MachineOperand &MO = MI->getOperand(i); 574 575 // Collect register masks. 576 if (MO.isRegMask()) { 577 RegMaskSlots.push_back(MIIndex.getRegSlot()); 578 RegMaskBits.push_back(MO.getRegMask()); 579 continue; 580 } 581 582 if (!MO.isReg() || !MO.getReg()) 583 continue; 584 585 // handle register defs - build intervals 586 if (MO.isDef()) 587 handleRegisterDef(MBB, MI, MIIndex, MO, i); 588 else if (MO.isUndef()) 589 UndefUses.push_back(MO.getReg()); 590 } 591 592 // Move to the next instr slot. 593 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 594 } 595 596 // Compute the number of register mask instructions in this block. 597 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; 598 RMB.second = RegMaskSlots.size() - RMB.first;; 599 } 600 601 // Create empty intervals for registers defined by implicit_def's (except 602 // for those implicit_def that define values which are liveout of their 603 // blocks. 604 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 605 unsigned UndefReg = UndefUses[i]; 606 (void)getOrCreateInterval(UndefReg); 607 } 608} 609 610LiveInterval* LiveIntervals::createInterval(unsigned reg) { 611 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 612 return new LiveInterval(reg, Weight); 613} 614 615/// dupInterval - Duplicate a live interval. The caller is responsible for 616/// managing the allocated memory. 617LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 618 LiveInterval *NewLI = createInterval(li->reg); 619 NewLI->Copy(*li, mri_, getVNInfoAllocator()); 620 return NewLI; 621} 622 623/// shrinkToUses - After removing some uses of a register, shrink its live 624/// range to just the remaining uses. This method does not compute reaching 625/// defs for new uses, and it doesn't remove dead defs. 626bool LiveIntervals::shrinkToUses(LiveInterval *li, 627 SmallVectorImpl<MachineInstr*> *dead) { 628 DEBUG(dbgs() << "Shrink: " << *li << '\n'); 629 assert(TargetRegisterInfo::isVirtualRegister(li->reg) 630 && "Can only shrink virtual registers"); 631 // Find all the values used, including PHI kills. 632 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 633 634 // Blocks that have already been added to WorkList as live-out. 635 SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 636 637 // Visit all instructions reading li->reg. 638 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 639 MachineInstr *UseMI = I.skipInstruction();) { 640 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 641 continue; 642 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 643 // Note: This intentionally picks up the wrong VNI in case of an EC redef. 644 // See below. 645 VNInfo *VNI = li->getVNInfoBefore(Idx); 646 if (!VNI) { 647 // This shouldn't happen: readsVirtualRegister returns true, but there is 648 // no live value. It is likely caused by a target getting <undef> flags 649 // wrong. 650 DEBUG(dbgs() << Idx << '\t' << *UseMI 651 << "Warning: Instr claims to read non-existent value in " 652 << *li << '\n'); 653 continue; 654 } 655 // Special case: An early-clobber tied operand reads and writes the 656 // register one slot early. The getVNInfoBefore call above would have 657 // picked up the value defined by UseMI. Adjust the kill slot and value. 658 if (SlotIndex::isSameInstr(VNI->def, Idx)) { 659 Idx = VNI->def; 660 VNI = li->getVNInfoBefore(Idx); 661 assert(VNI && "Early-clobber tied value not available"); 662 } 663 WorkList.push_back(std::make_pair(Idx, VNI)); 664 } 665 666 // Create a new live interval with only minimal live segments per def. 667 LiveInterval NewLI(li->reg, 0); 668 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 669 I != E; ++I) { 670 VNInfo *VNI = *I; 671 if (VNI->isUnused()) 672 continue; 673 NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); 674 } 675 676 // Keep track of the PHIs that are in use. 677 SmallPtrSet<VNInfo*, 8> UsedPHIs; 678 679 // Extend intervals to reach all uses in WorkList. 680 while (!WorkList.empty()) { 681 SlotIndex Idx = WorkList.back().first; 682 VNInfo *VNI = WorkList.back().second; 683 WorkList.pop_back(); 684 const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 685 SlotIndex BlockStart = getMBBStartIdx(MBB); 686 687 // Extend the live range for VNI to be live at Idx. 688 if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 689 (void)ExtVNI; 690 assert(ExtVNI == VNI && "Unexpected existing value number"); 691 // Is this a PHIDef we haven't seen before? 692 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 693 continue; 694 // The PHI is live, make sure the predecessors are live-out. 695 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 696 PE = MBB->pred_end(); PI != PE; ++PI) { 697 if (!LiveOut.insert(*PI)) 698 continue; 699 SlotIndex Stop = getMBBEndIdx(*PI); 700 // A predecessor is not required to have a live-out value for a PHI. 701 if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 702 WorkList.push_back(std::make_pair(Stop, PVNI)); 703 } 704 continue; 705 } 706 707 // VNI is live-in to MBB. 708 DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 709 NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); 710 711 // Make sure VNI is live-out from the predecessors. 712 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 713 PE = MBB->pred_end(); PI != PE; ++PI) { 714 if (!LiveOut.insert(*PI)) 715 continue; 716 SlotIndex Stop = getMBBEndIdx(*PI); 717 assert(li->getVNInfoBefore(Stop) == VNI && 718 "Wrong value out of predecessor"); 719 WorkList.push_back(std::make_pair(Stop, VNI)); 720 } 721 } 722 723 // Handle dead values. 724 bool CanSeparate = false; 725 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 726 I != E; ++I) { 727 VNInfo *VNI = *I; 728 if (VNI->isUnused()) 729 continue; 730 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 731 assert(LII != NewLI.end() && "Missing live range for PHI"); 732 if (LII->end != VNI->def.getDeadSlot()) 733 continue; 734 if (VNI->isPHIDef()) { 735 // This is a dead PHI. Remove it. 736 VNI->setIsUnused(true); 737 NewLI.removeRange(*LII); 738 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 739 CanSeparate = true; 740 } else { 741 // This is a dead def. Make sure the instruction knows. 742 MachineInstr *MI = getInstructionFromIndex(VNI->def); 743 assert(MI && "No instruction defining live value"); 744 MI->addRegisterDead(li->reg, tri_); 745 if (dead && MI->allDefsAreDead()) { 746 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 747 dead->push_back(MI); 748 } 749 } 750 } 751 752 // Move the trimmed ranges back. 753 li->ranges.swap(NewLI.ranges); 754 DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 755 return CanSeparate; 756} 757 758 759//===----------------------------------------------------------------------===// 760// Register allocator hooks. 761// 762 763void LiveIntervals::addKillFlags() { 764 for (iterator I = begin(), E = end(); I != E; ++I) { 765 unsigned Reg = I->first; 766 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 767 continue; 768 if (mri_->reg_nodbg_empty(Reg)) 769 continue; 770 LiveInterval *LI = I->second; 771 772 // Every instruction that kills Reg corresponds to a live range end point. 773 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 774 ++RI) { 775 // A block index indicates an MBB edge. 776 if (RI->end.isBlock()) 777 continue; 778 MachineInstr *MI = getInstructionFromIndex(RI->end); 779 if (!MI) 780 continue; 781 MI->addRegisterKilled(Reg, NULL); 782 } 783 } 784} 785 786#ifndef NDEBUG 787static bool intervalRangesSane(const LiveInterval& li) { 788 if (li.empty()) { 789 return true; 790 } 791 792 SlotIndex lastEnd = li.begin()->start; 793 for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end(); 794 lrItr != lrEnd; ++lrItr) { 795 const LiveRange& lr = *lrItr; 796 if (lastEnd > lr.start || lr.start >= lr.end) 797 return false; 798 lastEnd = lr.end; 799 } 800 801 return true; 802} 803#endif 804 805template <typename DefSetT> 806static void handleMoveDefs(LiveIntervals& lis, SlotIndex origIdx, 807 SlotIndex miIdx, const DefSetT& defs) { 808 for (typename DefSetT::const_iterator defItr = defs.begin(), 809 defEnd = defs.end(); 810 defItr != defEnd; ++defItr) { 811 unsigned def = *defItr; 812 LiveInterval& li = lis.getInterval(def); 813 LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot()); 814 assert(lr != 0 && "No range for def?"); 815 lr->start = miIdx.getRegSlot(); 816 lr->valno->def = miIdx.getRegSlot(); 817 assert(intervalRangesSane(li) && "Broke live interval moving def."); 818 } 819} 820 821template <typename DeadDefSetT> 822static void handleMoveDeadDefs(LiveIntervals& lis, SlotIndex origIdx, 823 SlotIndex miIdx, const DeadDefSetT& deadDefs) { 824 for (typename DeadDefSetT::const_iterator deadDefItr = deadDefs.begin(), 825 deadDefEnd = deadDefs.end(); 826 deadDefItr != deadDefEnd; ++deadDefItr) { 827 unsigned deadDef = *deadDefItr; 828 LiveInterval& li = lis.getInterval(deadDef); 829 LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot()); 830 assert(lr != 0 && "No range for dead def?"); 831 assert(lr->start == origIdx.getRegSlot() && "Bad dead range start?"); 832 assert(lr->end == origIdx.getDeadSlot() && "Bad dead range end?"); 833 assert(lr->valno->def == origIdx.getRegSlot() && "Bad dead valno def."); 834 LiveRange t(*lr); 835 t.start = miIdx.getRegSlot(); 836 t.valno->def = miIdx.getRegSlot(); 837 t.end = miIdx.getDeadSlot(); 838 li.removeRange(*lr); 839 li.addRange(t); 840 assert(intervalRangesSane(li) && "Broke live interval moving dead def."); 841 } 842} 843 844template <typename ECSetT> 845static void handleMoveECs(LiveIntervals& lis, SlotIndex origIdx, 846 SlotIndex miIdx, const ECSetT& ecs) { 847 for (typename ECSetT::const_iterator ecItr = ecs.begin(), ecEnd = ecs.end(); 848 ecItr != ecEnd; ++ecItr) { 849 unsigned ec = *ecItr; 850 LiveInterval& li = lis.getInterval(ec); 851 LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot(true)); 852 assert(lr != 0 && "No range for early clobber?"); 853 assert(lr->start == origIdx.getRegSlot(true) && "Bad EC range start?"); 854 assert(lr->end == origIdx.getRegSlot() && "Bad EC range end."); 855 assert(lr->valno->def == origIdx.getRegSlot(true) && "Bad EC valno def."); 856 LiveRange t(*lr); 857 t.start = miIdx.getRegSlot(true); 858 t.valno->def = miIdx.getRegSlot(true); 859 t.end = miIdx.getRegSlot(); 860 li.removeRange(*lr); 861 li.addRange(t); 862 assert(intervalRangesSane(li) && "Broke live interval moving EC."); 863 } 864} 865 866static void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newIdx, 867 LiveIntervals& lis, 868 const TargetRegisterInfo& tri) { 869 MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx); 870 MachineInstr* newKillMI = lis.getInstructionFromIndex(newIdx); 871 assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill."); 872 assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill."); 873 oldKillMI->clearRegisterKills(reg, &tri); 874 newKillMI->addRegisterKilled(reg, &tri); 875} 876 877template <typename UseSetT> 878static void handleMoveUses(const MachineBasicBlock *mbb, 879 const MachineRegisterInfo& mri, 880 const TargetRegisterInfo& tri, 881 const BitVector& reservedRegs, LiveIntervals &lis, 882 SlotIndex origIdx, SlotIndex miIdx, 883 const UseSetT &uses) { 884 bool movingUp = miIdx < origIdx; 885 for (typename UseSetT::const_iterator usesItr = uses.begin(), 886 usesEnd = uses.end(); 887 usesItr != usesEnd; ++usesItr) { 888 unsigned use = *usesItr; 889 if (!lis.hasInterval(use)) 890 continue; 891 if (TargetRegisterInfo::isPhysicalRegister(use) && reservedRegs.test(use)) 892 continue; 893 LiveInterval& li = lis.getInterval(use); 894 LiveRange* lr = li.getLiveRangeBefore(origIdx.getRegSlot()); 895 assert(lr != 0 && "No range for use?"); 896 bool liveThrough = lr->end > origIdx.getRegSlot(); 897 898 if (movingUp) { 899 // If moving up and liveThrough - nothing to do. 900 // If not live through we need to extend the range to the last use 901 // between the old location and the new one. 902 if (!liveThrough) { 903 SlotIndex lastUseInRange = miIdx.getRegSlot(); 904 for (MachineRegisterInfo::use_iterator useI = mri.use_begin(use), 905 useE = mri.use_end(); 906 useI != useE; ++useI) { 907 const MachineInstr* mopI = &*useI; 908 const MachineOperand& mop = useI.getOperand(); 909 SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI); 910 SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber()); 911 if (opSlot > lastUseInRange && opSlot < origIdx) 912 lastUseInRange = opSlot; 913 } 914 915 // If we found a new instr endpoint update the kill flags. 916 if (lastUseInRange != miIdx.getRegSlot()) 917 moveKillFlags(use, miIdx, lastUseInRange, lis, tri); 918 919 // Fix up the range end. 920 lr->end = lastUseInRange; 921 } 922 } else { 923 // Moving down is easy - the existing live range end tells us where 924 // the last kill is. 925 if (!liveThrough) { 926 // Easy fix - just update the range endpoint. 927 lr->end = miIdx.getRegSlot(); 928 } else { 929 bool liveOut = lr->end >= lis.getSlotIndexes()->getMBBEndIdx(mbb); 930 if (!liveOut && miIdx.getRegSlot() > lr->end) { 931 moveKillFlags(use, lr->end, miIdx, lis, tri); 932 lr->end = miIdx.getRegSlot(); 933 } 934 } 935 } 936 assert(intervalRangesSane(li) && "Broke live interval moving use."); 937 } 938} 939 940void LiveIntervals::moveInstr(MachineBasicBlock::iterator insertPt, 941 MachineInstr *mi) { 942 MachineBasicBlock* mbb = mi->getParent(); 943 assert((insertPt == mbb->end() || insertPt->getParent() == mbb) && 944 "Cannot handle moves across basic block boundaries."); 945 assert(&*insertPt != mi && "No-op move requested?"); 946 assert(!mi->isBundled() && "Can't handle bundled instructions yet."); 947 948 // Grab the original instruction index. 949 SlotIndex origIdx = indexes_->getInstructionIndex(mi); 950 951 // Move the machine instr and obtain its new index. 952 indexes_->removeMachineInstrFromMaps(mi); 953 mbb->splice(insertPt, mbb, mi); 954 SlotIndex miIdx = indexes_->insertMachineInstrInMaps(mi); 955 956 // Pick the direction. 957 bool movingUp = miIdx < origIdx; 958 959 // Collect the operands. 960 DenseSet<unsigned> uses, defs, deadDefs, ecs; 961 for (MachineInstr::mop_iterator mopItr = mi->operands_begin(), 962 mopEnd = mi->operands_end(); 963 mopItr != mopEnd; ++mopItr) { 964 const MachineOperand& mop = *mopItr; 965 966 if (!mop.isReg() || mop.getReg() == 0) 967 continue; 968 unsigned reg = mop.getReg(); 969 970 if (mop.readsReg() && !ecs.count(reg)) { 971 uses.insert(reg); 972 } 973 if (mop.isDef()) { 974 if (mop.isDead()) { 975 assert(!defs.count(reg) && "Can't mix defs with dead-defs."); 976 deadDefs.insert(reg); 977 } else if (mop.isEarlyClobber()) { 978 uses.erase(reg); 979 ecs.insert(reg); 980 } else { 981 assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs."); 982 defs.insert(reg); 983 } 984 } 985 } 986 987 BitVector reservedRegs(tri_->getReservedRegs(*mbb->getParent())); 988 989 if (movingUp) { 990 handleMoveUses(mbb, *mri_, *tri_, reservedRegs, *this, origIdx, miIdx, uses); 991 handleMoveECs(*this, origIdx, miIdx, ecs); 992 handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs); 993 handleMoveDefs(*this, origIdx, miIdx, defs); 994 } else { 995 handleMoveDefs(*this, origIdx, miIdx, defs); 996 handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs); 997 handleMoveECs(*this, origIdx, miIdx, ecs); 998 handleMoveUses(mbb, *mri_, *tri_, reservedRegs, *this, origIdx, miIdx, uses); 999 } 1000} 1001 1002/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 1003/// allow one) virtual register operand, then its uses are implicitly using 1004/// the register. Returns the virtual register. 1005unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 1006 MachineInstr *MI) const { 1007 unsigned RegOp = 0; 1008 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1009 MachineOperand &MO = MI->getOperand(i); 1010 if (!MO.isReg() || !MO.isUse()) 1011 continue; 1012 unsigned Reg = MO.getReg(); 1013 if (Reg == 0 || Reg == li.reg) 1014 continue; 1015 1016 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 1017 !allocatableRegs_[Reg]) 1018 continue; 1019 RegOp = MO.getReg(); 1020 break; // Found vreg operand - leave the loop. 1021 } 1022 return RegOp; 1023} 1024 1025/// isValNoAvailableAt - Return true if the val# of the specified interval 1026/// which reaches the given instruction also reaches the specified use index. 1027bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 1028 SlotIndex UseIdx) const { 1029 VNInfo *UValNo = li.getVNInfoAt(UseIdx); 1030 return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 1031} 1032 1033/// isReMaterializable - Returns true if the definition MI of the specified 1034/// val# of the specified interval is re-materializable. 1035bool 1036LiveIntervals::isReMaterializable(const LiveInterval &li, 1037 const VNInfo *ValNo, MachineInstr *MI, 1038 const SmallVectorImpl<LiveInterval*> *SpillIs, 1039 bool &isLoad) { 1040 if (DisableReMat) 1041 return false; 1042 1043 if (!tii_->isTriviallyReMaterializable(MI, aa_)) 1044 return false; 1045 1046 // Target-specific code can mark an instruction as being rematerializable 1047 // if it has one virtual reg use, though it had better be something like 1048 // a PIC base register which is likely to be live everywhere. 1049 unsigned ImpUse = getReMatImplicitUse(li, MI); 1050 if (ImpUse) { 1051 const LiveInterval &ImpLi = getInterval(ImpUse); 1052 for (MachineRegisterInfo::use_nodbg_iterator 1053 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 1054 ri != re; ++ri) { 1055 MachineInstr *UseMI = &*ri; 1056 SlotIndex UseIdx = getInstructionIndex(UseMI); 1057 if (li.getVNInfoAt(UseIdx) != ValNo) 1058 continue; 1059 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 1060 return false; 1061 } 1062 1063 // If a register operand of the re-materialized instruction is going to 1064 // be spilled next, then it's not legal to re-materialize this instruction. 1065 if (SpillIs) 1066 for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 1067 if (ImpUse == (*SpillIs)[i]->reg) 1068 return false; 1069 } 1070 return true; 1071} 1072 1073/// isReMaterializable - Returns true if every definition of MI of every 1074/// val# of the specified interval is re-materializable. 1075bool 1076LiveIntervals::isReMaterializable(const LiveInterval &li, 1077 const SmallVectorImpl<LiveInterval*> *SpillIs, 1078 bool &isLoad) { 1079 isLoad = false; 1080 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1081 i != e; ++i) { 1082 const VNInfo *VNI = *i; 1083 if (VNI->isUnused()) 1084 continue; // Dead val#. 1085 // Is the def for the val# rematerializable? 1086 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 1087 if (!ReMatDefMI) 1088 return false; 1089 bool DefIsLoad = false; 1090 if (!ReMatDefMI || 1091 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 1092 return false; 1093 isLoad |= DefIsLoad; 1094 } 1095 return true; 1096} 1097 1098MachineBasicBlock* 1099LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 1100 // A local live range must be fully contained inside the block, meaning it is 1101 // defined and killed at instructions, not at block boundaries. It is not 1102 // live in or or out of any block. 1103 // 1104 // It is technically possible to have a PHI-defined live range identical to a 1105 // single block, but we are going to return false in that case. 1106 1107 SlotIndex Start = LI.beginIndex(); 1108 if (Start.isBlock()) 1109 return NULL; 1110 1111 SlotIndex Stop = LI.endIndex(); 1112 if (Stop.isBlock()) 1113 return NULL; 1114 1115 // getMBBFromIndex doesn't need to search the MBB table when both indexes 1116 // belong to proper instructions. 1117 MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start); 1118 MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop); 1119 return MBB1 == MBB2 ? MBB1 : NULL; 1120} 1121 1122float 1123LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 1124 // Limit the loop depth ridiculousness. 1125 if (loopDepth > 200) 1126 loopDepth = 200; 1127 1128 // The loop depth is used to roughly estimate the number of times the 1129 // instruction is executed. Something like 10^d is simple, but will quickly 1130 // overflow a float. This expression behaves like 10^d for small d, but is 1131 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 1132 // headroom before overflow. 1133 // By the way, powf() might be unavailable here. For consistency, 1134 // We may take pow(double,double). 1135 float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 1136 1137 return (isDef + isUse) * lc; 1138} 1139 1140LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 1141 MachineInstr* startInst) { 1142 LiveInterval& Interval = getOrCreateInterval(reg); 1143 VNInfo* VN = Interval.getNextValue( 1144 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 1145 getVNInfoAllocator()); 1146 VN->setHasPHIKill(true); 1147 LiveRange LR( 1148 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 1149 getMBBEndIdx(startInst->getParent()), VN); 1150 Interval.addRange(LR); 1151 1152 return LR; 1153} 1154 1155 1156//===----------------------------------------------------------------------===// 1157// Register mask functions 1158//===----------------------------------------------------------------------===// 1159 1160bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 1161 BitVector &UsableRegs) { 1162 if (LI.empty()) 1163 return false; 1164 1165 // We are going to enumerate all the register mask slots contained in LI. 1166 // Start with a binary search of RegMaskSlots to find a starting point. 1167 LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 1168 ArrayRef<SlotIndex> Slots = getRegMaskSlots(); 1169 ArrayRef<SlotIndex>::iterator SlotI = 1170 std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 1171 ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 1172 1173 // No slots in range, LI begins after the last call. 1174 if (SlotI == SlotE) 1175 return false; 1176 1177 bool Found = false; 1178 for (;;) { 1179 assert(*SlotI >= LiveI->start); 1180 // Loop over all slots overlapping this segment. 1181 while (*SlotI < LiveI->end) { 1182 // *SlotI overlaps LI. Collect mask bits. 1183 if (!Found) { 1184 // This is the first overlap. Initialize UsableRegs to all ones. 1185 UsableRegs.clear(); 1186 UsableRegs.resize(tri_->getNumRegs(), true); 1187 Found = true; 1188 } 1189 // Remove usable registers clobbered by this mask. 1190 UsableRegs.clearBitsNotInMask(RegMaskBits[SlotI-Slots.begin()]); 1191 if (++SlotI == SlotE) 1192 return Found; 1193 } 1194 // *SlotI is beyond the current LI segment. 1195 LiveI = LI.advanceTo(LiveI, *SlotI); 1196 if (LiveI == LiveE) 1197 return Found; 1198 // Advance SlotI until it overlaps. 1199 while (*SlotI < LiveI->start) 1200 if (++SlotI == SlotE) 1201 return Found; 1202 } 1203} 1204