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