LiveIntervalAnalysis.cpp revision 58a3685916e2badd7fdec557641b056c1540c0c3
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 } 586 587 // Skip over empty initial indices. 588 if (getInstructionFromIndex(MIIndex) == 0) 589 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 590 591 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 592 MI != miEnd; ++MI) { 593 DEBUG(dbgs() << MIIndex << "\t" << *MI); 594 if (MI->isDebugValue()) 595 continue; 596 597 // Handle defs. 598 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 599 MachineOperand &MO = MI->getOperand(i); 600 if (!MO.isReg() || !MO.getReg()) 601 continue; 602 603 // handle register defs - build intervals 604 if (MO.isDef()) 605 handleRegisterDef(MBB, MI, MIIndex, MO, i); 606 else if (MO.isUndef()) 607 UndefUses.push_back(MO.getReg()); 608 } 609 610 // Move to the next instr slot. 611 MIIndex = indexes_->getNextNonNullIndex(MIIndex); 612 } 613 } 614 615 // Create empty intervals for registers defined by implicit_def's (except 616 // for those implicit_def that define values which are liveout of their 617 // blocks. 618 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 619 unsigned UndefReg = UndefUses[i]; 620 (void)getOrCreateInterval(UndefReg); 621 } 622} 623 624LiveInterval* LiveIntervals::createInterval(unsigned reg) { 625 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 626 return new LiveInterval(reg, Weight); 627} 628 629/// dupInterval - Duplicate a live interval. The caller is responsible for 630/// managing the allocated memory. 631LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 632 LiveInterval *NewLI = createInterval(li->reg); 633 NewLI->Copy(*li, mri_, getVNInfoAllocator()); 634 return NewLI; 635} 636 637/// shrinkToUses - After removing some uses of a register, shrink its live 638/// range to just the remaining uses. This method does not compute reaching 639/// defs for new uses, and it doesn't remove dead defs. 640bool LiveIntervals::shrinkToUses(LiveInterval *li, 641 SmallVectorImpl<MachineInstr*> *dead) { 642 DEBUG(dbgs() << "Shrink: " << *li << '\n'); 643 assert(TargetRegisterInfo::isVirtualRegister(li->reg) 644 && "Can only shrink virtual registers"); 645 // Find all the values used, including PHI kills. 646 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 647 648 // Blocks that have already been added to WorkList as live-out. 649 SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 650 651 // Visit all instructions reading li->reg. 652 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 653 MachineInstr *UseMI = I.skipInstruction();) { 654 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 655 continue; 656 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 657 // Note: This intentionally picks up the wrong VNI in case of an EC redef. 658 // See below. 659 VNInfo *VNI = li->getVNInfoBefore(Idx); 660 if (!VNI) { 661 // This shouldn't happen: readsVirtualRegister returns true, but there is 662 // no live value. It is likely caused by a target getting <undef> flags 663 // wrong. 664 DEBUG(dbgs() << Idx << '\t' << *UseMI 665 << "Warning: Instr claims to read non-existent value in " 666 << *li << '\n'); 667 continue; 668 } 669 // Special case: An early-clobber tied operand reads and writes the 670 // register one slot early. The getVNInfoBefore call above would have 671 // picked up the value defined by UseMI. Adjust the kill slot and value. 672 if (SlotIndex::isSameInstr(VNI->def, Idx)) { 673 Idx = VNI->def; 674 VNI = li->getVNInfoBefore(Idx); 675 assert(VNI && "Early-clobber tied value not available"); 676 } 677 WorkList.push_back(std::make_pair(Idx, VNI)); 678 } 679 680 // Create a new live interval with only minimal live segments per def. 681 LiveInterval NewLI(li->reg, 0); 682 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 683 I != E; ++I) { 684 VNInfo *VNI = *I; 685 if (VNI->isUnused()) 686 continue; 687 NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); 688 } 689 690 // Keep track of the PHIs that are in use. 691 SmallPtrSet<VNInfo*, 8> UsedPHIs; 692 693 // Extend intervals to reach all uses in WorkList. 694 while (!WorkList.empty()) { 695 SlotIndex Idx = WorkList.back().first; 696 VNInfo *VNI = WorkList.back().second; 697 WorkList.pop_back(); 698 const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 699 SlotIndex BlockStart = getMBBStartIdx(MBB); 700 701 // Extend the live range for VNI to be live at Idx. 702 if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 703 (void)ExtVNI; 704 assert(ExtVNI == VNI && "Unexpected existing value number"); 705 // Is this a PHIDef we haven't seen before? 706 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 707 continue; 708 // The PHI is live, make sure the predecessors are live-out. 709 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 710 PE = MBB->pred_end(); PI != PE; ++PI) { 711 if (!LiveOut.insert(*PI)) 712 continue; 713 SlotIndex Stop = getMBBEndIdx(*PI); 714 // A predecessor is not required to have a live-out value for a PHI. 715 if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 716 WorkList.push_back(std::make_pair(Stop, PVNI)); 717 } 718 continue; 719 } 720 721 // VNI is live-in to MBB. 722 DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 723 NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); 724 725 // Make sure VNI is live-out from the predecessors. 726 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 727 PE = MBB->pred_end(); PI != PE; ++PI) { 728 if (!LiveOut.insert(*PI)) 729 continue; 730 SlotIndex Stop = getMBBEndIdx(*PI); 731 assert(li->getVNInfoBefore(Stop) == VNI && 732 "Wrong value out of predecessor"); 733 WorkList.push_back(std::make_pair(Stop, VNI)); 734 } 735 } 736 737 // Handle dead values. 738 bool CanSeparate = false; 739 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 740 I != E; ++I) { 741 VNInfo *VNI = *I; 742 if (VNI->isUnused()) 743 continue; 744 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 745 assert(LII != NewLI.end() && "Missing live range for PHI"); 746 if (LII->end != VNI->def.getDeadSlot()) 747 continue; 748 if (VNI->isPHIDef()) { 749 // This is a dead PHI. Remove it. 750 VNI->setIsUnused(true); 751 NewLI.removeRange(*LII); 752 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 753 CanSeparate = true; 754 } else { 755 // This is a dead def. Make sure the instruction knows. 756 MachineInstr *MI = getInstructionFromIndex(VNI->def); 757 assert(MI && "No instruction defining live value"); 758 MI->addRegisterDead(li->reg, tri_); 759 if (dead && MI->allDefsAreDead()) { 760 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 761 dead->push_back(MI); 762 } 763 } 764 } 765 766 // Move the trimmed ranges back. 767 li->ranges.swap(NewLI.ranges); 768 DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 769 return CanSeparate; 770} 771 772 773//===----------------------------------------------------------------------===// 774// Register allocator hooks. 775// 776 777void LiveIntervals::addKillFlags() { 778 for (iterator I = begin(), E = end(); I != E; ++I) { 779 unsigned Reg = I->first; 780 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 781 continue; 782 if (mri_->reg_nodbg_empty(Reg)) 783 continue; 784 LiveInterval *LI = I->second; 785 786 // Every instruction that kills Reg corresponds to a live range end point. 787 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 788 ++RI) { 789 // A block index indicates an MBB edge. 790 if (RI->end.isBlock()) 791 continue; 792 MachineInstr *MI = getInstructionFromIndex(RI->end); 793 if (!MI) 794 continue; 795 MI->addRegisterKilled(Reg, NULL); 796 } 797 } 798} 799 800/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 801/// allow one) virtual register operand, then its uses are implicitly using 802/// the register. Returns the virtual register. 803unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 804 MachineInstr *MI) const { 805 unsigned RegOp = 0; 806 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 807 MachineOperand &MO = MI->getOperand(i); 808 if (!MO.isReg() || !MO.isUse()) 809 continue; 810 unsigned Reg = MO.getReg(); 811 if (Reg == 0 || Reg == li.reg) 812 continue; 813 814 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 815 !allocatableRegs_[Reg]) 816 continue; 817 RegOp = MO.getReg(); 818 break; // Found vreg operand - leave the loop. 819 } 820 return RegOp; 821} 822 823/// isValNoAvailableAt - Return true if the val# of the specified interval 824/// which reaches the given instruction also reaches the specified use index. 825bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 826 SlotIndex UseIdx) const { 827 VNInfo *UValNo = li.getVNInfoAt(UseIdx); 828 return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 829} 830 831/// isReMaterializable - Returns true if the definition MI of the specified 832/// val# of the specified interval is re-materializable. 833bool 834LiveIntervals::isReMaterializable(const LiveInterval &li, 835 const VNInfo *ValNo, MachineInstr *MI, 836 const SmallVectorImpl<LiveInterval*> *SpillIs, 837 bool &isLoad) { 838 if (DisableReMat) 839 return false; 840 841 if (!tii_->isTriviallyReMaterializable(MI, aa_)) 842 return false; 843 844 // Target-specific code can mark an instruction as being rematerializable 845 // if it has one virtual reg use, though it had better be something like 846 // a PIC base register which is likely to be live everywhere. 847 unsigned ImpUse = getReMatImplicitUse(li, MI); 848 if (ImpUse) { 849 const LiveInterval &ImpLi = getInterval(ImpUse); 850 for (MachineRegisterInfo::use_nodbg_iterator 851 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 852 ri != re; ++ri) { 853 MachineInstr *UseMI = &*ri; 854 SlotIndex UseIdx = getInstructionIndex(UseMI); 855 if (li.getVNInfoAt(UseIdx) != ValNo) 856 continue; 857 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 858 return false; 859 } 860 861 // If a register operand of the re-materialized instruction is going to 862 // be spilled next, then it's not legal to re-materialize this instruction. 863 if (SpillIs) 864 for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 865 if (ImpUse == (*SpillIs)[i]->reg) 866 return false; 867 } 868 return true; 869} 870 871/// isReMaterializable - Returns true if every definition of MI of every 872/// val# of the specified interval is re-materializable. 873bool 874LiveIntervals::isReMaterializable(const LiveInterval &li, 875 const SmallVectorImpl<LiveInterval*> *SpillIs, 876 bool &isLoad) { 877 isLoad = false; 878 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 879 i != e; ++i) { 880 const VNInfo *VNI = *i; 881 if (VNI->isUnused()) 882 continue; // Dead val#. 883 // Is the def for the val# rematerializable? 884 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 885 if (!ReMatDefMI) 886 return false; 887 bool DefIsLoad = false; 888 if (!ReMatDefMI || 889 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 890 return false; 891 isLoad |= DefIsLoad; 892 } 893 return true; 894} 895 896bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 897 LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 898 899 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 900 901 if (mbb == 0) 902 return false; 903 904 for (++itr; itr != li.ranges.end(); ++itr) { 905 MachineBasicBlock *mbb2 = 906 indexes_->getMBBCoveringRange(itr->start, itr->end); 907 908 if (mbb2 != mbb) 909 return false; 910 } 911 912 return true; 913} 914 915float 916LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 917 // Limit the loop depth ridiculousness. 918 if (loopDepth > 200) 919 loopDepth = 200; 920 921 // The loop depth is used to roughly estimate the number of times the 922 // instruction is executed. Something like 10^d is simple, but will quickly 923 // overflow a float. This expression behaves like 10^d for small d, but is 924 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 925 // headroom before overflow. 926 // By the way, powf() might be unavailable here. For consistency, 927 // We may take pow(double,double). 928 float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 929 930 return (isDef + isUse) * lc; 931} 932 933LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 934 MachineInstr* startInst) { 935 LiveInterval& Interval = getOrCreateInterval(reg); 936 VNInfo* VN = Interval.getNextValue( 937 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 938 startInst, getVNInfoAllocator()); 939 VN->setHasPHIKill(true); 940 LiveRange LR( 941 SlotIndex(getInstructionIndex(startInst).getRegSlot()), 942 getMBBEndIdx(startInst->getParent()), VN); 943 Interval.addRange(LR); 944 945 return LR; 946} 947 948