1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "liveintervals"
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"
50 // Hidden options for help debugging.
51 static cl::opt<bool> DisableReMat("disable-rematerialization",
52 cl::init(false), cl::Hidden);
54 STATISTIC(numIntervals , "Number of original intervals");
56 char LiveIntervals::ID = 0;
57 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
58 "Live Interval Analysis", false, false)
59 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
60 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
61 INITIALIZE_PASS_DEPENDENCY(PHIElimination)
62 INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass)
63 INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs)
64 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
65 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
66 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
67 "Live Interval Analysis", false, false)
69 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
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);
80 AU.addPreservedID(PHIEliminationID);
81 AU.addRequiredID(PHIEliminationID);
84 AU.addRequiredID(TwoAddressInstructionPassID);
85 AU.addPreserved<ProcessImplicitDefs>();
86 AU.addRequired<ProcessImplicitDefs>();
87 AU.addPreserved<SlotIndexes>();
88 AU.addRequiredTransitive<SlotIndexes>();
89 MachineFunctionPass::getAnalysisUsage(AU);
92 void LiveIntervals::releaseMemory() {
93 // Free the live intervals themselves.
94 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
95 E = r2iMap_.end(); I != E; ++I)
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();
105 mf_->DeleteMachineInstr(MI);
109 /// runOnMachineFunction - Register allocate the whole function
111 bool LiveIntervals::runOnMachineFunction(MachineFunction &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);
124 numIntervals += getNumIntervals();
130 /// print - Implement the dump method.
131 void 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_);
141 void LiveIntervals::printInstrs(raw_ostream &OS) const {
142 OS << "********** MACHINEINSTRS **********\n";
143 mf_->print(OS, indexes_);
146 void LiveIntervals::dumpInstrs() const {
151 bool 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);
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()));
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.
170 bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
171 LiveInterval &interval) {
172 if (!MO.getSubReg() || MO.isEarlyClobber())
175 SlotIndex RedefIndex = MIIdx.getDefIndex();
176 const LiveRange *OldLR =
177 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
178 MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
180 return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
185 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
186 MachineBasicBlock::iterator mi,
190 LiveInterval &interval) {
191 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
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.getDefIndex();
201 // Earlyclobbers move back one, so that they overlap the live range
203 if (MO.isEarlyClobber())
204 defIndex = MIIdx.getUseIndex();
206 // Make sure the first definition is not a partial redefinition. Add an
207 // <imp-def> of the full register.
208 // FIXME: LiveIntervals shouldn't modify the code like this. Whoever
209 // created the machine instruction should annotate it with <undef> flags
210 // as needed. Then we can simply assert here. The REG_SEQUENCE lowering
211 // is the main suspect.
212 if (MO.getSubReg()) {
213 mi->addRegisterDefined(interval.reg);
214 // Mark all defs of interval.reg on this instruction as reading <undef>.
215 for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) {
216 MachineOperand &MO2 = mi->getOperand(i);
217 if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg())
222 MachineInstr *CopyMI = NULL;
223 if (mi->isCopyLike()) {
227 VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
228 assert(ValNo->id == 0 && "First value in interval is not 0?");
230 // Loop over all of the blocks that the vreg is defined in. There are
231 // two cases we have to handle here. The most common case is a vreg
232 // whose lifetime is contained within a basic block. In this case there
233 // will be a single kill, in MBB, which comes after the definition.
234 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
235 // FIXME: what about dead vars?
237 if (vi.Kills[0] != mi)
238 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
240 killIdx = defIndex.getStoreIndex();
242 // If the kill happens after the definition, we have an intra-block
244 if (killIdx > defIndex) {
245 assert(vi.AliveBlocks.empty() &&
246 "Shouldn't be alive across any blocks!");
247 LiveRange LR(defIndex, killIdx, ValNo);
248 interval.addRange(LR);
249 DEBUG(dbgs() << " +" << LR << "\n");
254 // The other case we handle is when a virtual register lives to the end
255 // of the defining block, potentially live across some blocks, then is
256 // live into some number of blocks, but gets killed. Start by adding a
257 // range that goes from this definition to the end of the defining block.
258 LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
259 DEBUG(dbgs() << " +" << NewLR);
260 interval.addRange(NewLR);
262 bool PHIJoin = lv_->isPHIJoin(interval.reg);
265 // A phi join register is killed at the end of the MBB and revived as a new
266 // valno in the killing blocks.
267 assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
268 DEBUG(dbgs() << " phi-join");
269 ValNo->setHasPHIKill(true);
271 // Iterate over all of the blocks that the variable is completely
272 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
274 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
275 E = vi.AliveBlocks.end(); I != E; ++I) {
276 MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
277 LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
278 interval.addRange(LR);
279 DEBUG(dbgs() << " +" << LR);
283 // Finally, this virtual register is live from the start of any killing
284 // block to the 'use' slot of the killing instruction.
285 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
286 MachineInstr *Kill = vi.Kills[i];
287 SlotIndex Start = getMBBStartIdx(Kill->getParent());
288 SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
290 // Create interval with one of a NEW value number. Note that this value
291 // number isn't actually defined by an instruction, weird huh? :)
293 assert(getInstructionFromIndex(Start) == 0 &&
294 "PHI def index points at actual instruction.");
295 ValNo = interval.getNextValue(Start, 0, VNInfoAllocator);
296 ValNo->setIsPHIDef(true);
298 LiveRange LR(Start, killIdx, ValNo);
299 interval.addRange(LR);
300 DEBUG(dbgs() << " +" << LR);
304 if (MultipleDefsBySameMI(*mi, MOIdx))
305 // Multiple defs of the same virtual register by the same instruction.
306 // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
307 // This is likely due to elimination of REG_SEQUENCE instructions. Return
308 // here since there is nothing to do.
311 // If this is the second time we see a virtual register definition, it
312 // must be due to phi elimination or two addr elimination. If this is
313 // the result of two address elimination, then the vreg is one of the
314 // def-and-use register operand.
316 // It may also be partial redef like this:
317 // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
318 // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
319 bool PartReDef = isPartialRedef(MIIdx, MO, interval);
320 if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
321 // If this is a two-address definition, then we have already processed
322 // the live range. The only problem is that we didn't realize there
323 // are actually two values in the live interval. Because of this we
324 // need to take the LiveRegion that defines this register and split it
326 SlotIndex RedefIndex = MIIdx.getDefIndex();
327 if (MO.isEarlyClobber())
328 RedefIndex = MIIdx.getUseIndex();
330 const LiveRange *OldLR =
331 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
332 VNInfo *OldValNo = OldLR->valno;
333 SlotIndex DefIndex = OldValNo->def.getDefIndex();
335 // Delete the previous value, which should be short and continuous,
336 // because the 2-addr copy must be in the same MBB as the redef.
337 interval.removeRange(DefIndex, RedefIndex);
339 // The new value number (#1) is defined by the instruction we claimed
341 VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
343 // Value#0 is now defined by the 2-addr instruction.
344 OldValNo->def = RedefIndex;
345 OldValNo->setCopy(0);
347 // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
348 if (PartReDef && mi->isCopyLike())
349 OldValNo->setCopy(&*mi);
351 // Add the new live interval which replaces the range for the input copy.
352 LiveRange LR(DefIndex, RedefIndex, ValNo);
353 DEBUG(dbgs() << " replace range with " << LR);
354 interval.addRange(LR);
356 // If this redefinition is dead, we need to add a dummy unit live
357 // range covering the def slot.
359 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
363 dbgs() << " RESULT: ";
364 interval.print(dbgs(), tri_);
366 } else if (lv_->isPHIJoin(interval.reg)) {
367 // In the case of PHI elimination, each variable definition is only
368 // live until the end of the block. We've already taken care of the
369 // rest of the live range.
371 SlotIndex defIndex = MIIdx.getDefIndex();
372 if (MO.isEarlyClobber())
373 defIndex = MIIdx.getUseIndex();
376 MachineInstr *CopyMI = NULL;
377 if (mi->isCopyLike())
379 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
381 SlotIndex killIndex = getMBBEndIdx(mbb);
382 LiveRange LR(defIndex, killIndex, ValNo);
383 interval.addRange(LR);
384 ValNo->setHasPHIKill(true);
385 DEBUG(dbgs() << " phi-join +" << LR);
387 llvm_unreachable("Multiply defined register");
391 DEBUG(dbgs() << '\n');
394 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
395 MachineBasicBlock::iterator mi,
398 LiveInterval &interval,
399 MachineInstr *CopyMI) {
400 // A physical register cannot be live across basic block, so its
401 // lifetime must end somewhere in its defining basic block.
402 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
404 SlotIndex baseIndex = MIIdx;
405 SlotIndex start = baseIndex.getDefIndex();
406 // Earlyclobbers move back one.
407 if (MO.isEarlyClobber())
408 start = MIIdx.getUseIndex();
409 SlotIndex end = start;
411 // If it is not used after definition, it is considered dead at
412 // the instruction defining it. Hence its interval is:
413 // [defSlot(def), defSlot(def)+1)
414 // For earlyclobbers, the defSlot was pushed back one; the extra
415 // advance below compensates.
417 DEBUG(dbgs() << " dead");
418 end = start.getStoreIndex();
422 // If it is not dead on definition, it must be killed by a
423 // subsequent instruction. Hence its interval is:
424 // [defSlot(def), useSlot(kill)+1)
425 baseIndex = baseIndex.getNextIndex();
426 while (++mi != MBB->end()) {
428 if (mi->isDebugValue())
430 if (getInstructionFromIndex(baseIndex) == 0)
431 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
433 if (mi->killsRegister(interval.reg, tri_)) {
434 DEBUG(dbgs() << " killed");
435 end = baseIndex.getDefIndex();
438 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
440 if (mi->isRegTiedToUseOperand(DefIdx)) {
441 // Two-address instruction.
442 end = baseIndex.getDefIndex();
444 // Another instruction redefines the register before it is ever read.
445 // Then the register is essentially dead at the instruction that
446 // defines it. Hence its interval is:
447 // [defSlot(def), defSlot(def)+1)
448 DEBUG(dbgs() << " dead");
449 end = start.getStoreIndex();
455 baseIndex = baseIndex.getNextIndex();
458 // The only case we should have a dead physreg here without a killing or
459 // instruction where we know it's dead is if it is live-in to the function
460 // and never used. Another possible case is the implicit use of the
461 // physical register has been deleted by two-address pass.
462 end = start.getStoreIndex();
465 assert(start < end && "did not find end of interval?");
467 // Already exists? Extend old live interval.
468 VNInfo *ValNo = interval.getVNInfoAt(start);
469 bool Extend = ValNo != 0;
471 ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
472 if (Extend && MO.isEarlyClobber())
473 ValNo->setHasRedefByEC(true);
474 LiveRange LR(start, end, ValNo);
475 interval.addRange(LR);
476 DEBUG(dbgs() << " +" << LR << '\n');
479 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
480 MachineBasicBlock::iterator MI,
484 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
485 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
486 getOrCreateInterval(MO.getReg()));
488 MachineInstr *CopyMI = NULL;
489 if (MI->isCopyLike())
491 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
492 getOrCreateInterval(MO.getReg()), CopyMI);
496 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
498 LiveInterval &interval, bool isAlias) {
499 DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
501 // Look for kills, if it reaches a def before it's killed, then it shouldn't
502 // be considered a livein.
503 MachineBasicBlock::iterator mi = MBB->begin();
504 MachineBasicBlock::iterator E = MBB->end();
505 // Skip over DBG_VALUE at the start of the MBB.
506 if (mi != E && mi->isDebugValue()) {
507 while (++mi != E && mi->isDebugValue())
510 // MBB is empty except for DBG_VALUE's.
514 SlotIndex baseIndex = MIIdx;
515 SlotIndex start = baseIndex;
516 if (getInstructionFromIndex(baseIndex) == 0)
517 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
519 SlotIndex end = baseIndex;
520 bool SeenDefUse = false;
523 if (mi->killsRegister(interval.reg, tri_)) {
524 DEBUG(dbgs() << " killed");
525 end = baseIndex.getDefIndex();
528 } else if (mi->definesRegister(interval.reg, tri_)) {
529 // Another instruction redefines the register before it is ever read.
530 // Then the register is essentially dead at the instruction that defines
531 // it. Hence its interval is:
532 // [defSlot(def), defSlot(def)+1)
533 DEBUG(dbgs() << " dead");
534 end = start.getStoreIndex();
539 while (++mi != E && mi->isDebugValue())
540 // Skip over DBG_VALUE.
543 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
546 // Live-in register might not be used at all.
549 DEBUG(dbgs() << " dead");
550 end = MIIdx.getStoreIndex();
552 DEBUG(dbgs() << " live through");
553 end = getMBBEndIdx(MBB);
557 SlotIndex defIdx = getMBBStartIdx(MBB);
558 assert(getInstructionFromIndex(defIdx) == 0 &&
559 "PHI def index points at actual instruction.");
561 interval.getNextValue(defIdx, 0, VNInfoAllocator);
562 vni->setIsPHIDef(true);
563 LiveRange LR(start, end, vni);
565 interval.addRange(LR);
566 DEBUG(dbgs() << " +" << LR << '\n');
569 /// computeIntervals - computes the live intervals for virtual
570 /// registers. for some ordering of the machine instructions [1,N] a
571 /// live interval is an interval [i, j) where 1 <= i <= j < N for
572 /// which a variable is live
573 void LiveIntervals::computeIntervals() {
574 DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
575 << "********** Function: "
576 << ((Value*)mf_->getFunction())->getName() << '\n');
578 SmallVector<unsigned, 8> UndefUses;
579 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
581 MachineBasicBlock *MBB = MBBI;
585 // Track the index of the current machine instr.
586 SlotIndex MIIndex = getMBBStartIdx(MBB);
587 DEBUG(dbgs() << "BB#" << MBB->getNumber()
588 << ":\t\t# derived from " << MBB->getName() << "\n");
590 // Create intervals for live-ins to this BB first.
591 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
592 LE = MBB->livein_end(); LI != LE; ++LI) {
593 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
594 // Multiple live-ins can alias the same register.
595 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
596 if (!hasInterval(*AS))
597 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
601 // Skip over empty initial indices.
602 if (getInstructionFromIndex(MIIndex) == 0)
603 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
605 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
607 DEBUG(dbgs() << MIIndex << "\t" << *MI);
608 if (MI->isDebugValue())
612 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
613 MachineOperand &MO = MI->getOperand(i);
614 if (!MO.isReg() || !MO.getReg())
617 // handle register defs - build intervals
619 handleRegisterDef(MBB, MI, MIIndex, MO, i);
620 else if (MO.isUndef())
621 UndefUses.push_back(MO.getReg());
624 // Move to the next instr slot.
625 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
629 // Create empty intervals for registers defined by implicit_def's (except
630 // for those implicit_def that define values which are liveout of their
632 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
633 unsigned UndefReg = UndefUses[i];
634 (void)getOrCreateInterval(UndefReg);
638 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
639 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
640 return new LiveInterval(reg, Weight);
643 /// dupInterval - Duplicate a live interval. The caller is responsible for
644 /// managing the allocated memory.
645 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
646 LiveInterval *NewLI = createInterval(li->reg);
647 NewLI->Copy(*li, mri_, getVNInfoAllocator());
651 /// shrinkToUses - After removing some uses of a register, shrink its live
652 /// range to just the remaining uses. This method does not compute reaching
653 /// defs for new uses, and it doesn't remove dead defs.
654 bool LiveIntervals::shrinkToUses(LiveInterval *li,
655 SmallVectorImpl<MachineInstr*> *dead) {
656 DEBUG(dbgs() << "Shrink: " << *li << '\n');
657 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
658 && "Can't only shrink physical registers");
659 // Find all the values used, including PHI kills.
660 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
662 // Blocks that have already been added to WorkList as live-out.
663 SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
665 // Visit all instructions reading li->reg.
666 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
667 MachineInstr *UseMI = I.skipInstruction();) {
668 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
670 SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex();
671 VNInfo *VNI = li->getVNInfoAt(Idx);
673 // This shouldn't happen: readsVirtualRegister returns true, but there is
674 // no live value. It is likely caused by a target getting <undef> flags
676 DEBUG(dbgs() << Idx << '\t' << *UseMI
677 << "Warning: Instr claims to read non-existent value in "
681 if (VNI->def == Idx) {
682 // Special case: An early-clobber tied operand reads and writes the
683 // register one slot early.
684 Idx = Idx.getPrevSlot();
685 VNI = li->getVNInfoAt(Idx);
686 assert(VNI && "Early-clobber tied value not available");
688 WorkList.push_back(std::make_pair(Idx, VNI));
691 // Create a new live interval with only minimal live segments per def.
692 LiveInterval NewLI(li->reg, 0);
693 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
698 NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
700 // A use tied to an early-clobber def ends at the load slot and isn't caught
701 // above. Catch it here instead. This probably only ever happens for inline
703 if (VNI->def.isUse())
704 if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
705 WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
708 // Keep track of the PHIs that are in use.
709 SmallPtrSet<VNInfo*, 8> UsedPHIs;
711 // Extend intervals to reach all uses in WorkList.
712 while (!WorkList.empty()) {
713 SlotIndex Idx = WorkList.back().first;
714 VNInfo *VNI = WorkList.back().second;
716 const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
717 SlotIndex BlockStart = getMBBStartIdx(MBB);
719 // Extend the live range for VNI to be live at Idx.
720 if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx.getNextSlot())) {
722 assert(ExtVNI == VNI && "Unexpected existing value number");
723 // Is this a PHIDef we haven't seen before?
724 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
726 // The PHI is live, make sure the predecessors are live-out.
727 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
728 PE = MBB->pred_end(); PI != PE; ++PI) {
729 if (!LiveOut.insert(*PI))
731 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
732 // A predecessor is not required to have a live-out value for a PHI.
733 if (VNInfo *PVNI = li->getVNInfoAt(Stop))
734 WorkList.push_back(std::make_pair(Stop, PVNI));
739 // VNI is live-in to MBB.
740 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
741 NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
743 // Make sure VNI is live-out from the predecessors.
744 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
745 PE = MBB->pred_end(); PI != PE; ++PI) {
746 if (!LiveOut.insert(*PI))
748 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
749 assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
750 WorkList.push_back(std::make_pair(Stop, VNI));
754 // Handle dead values.
755 bool CanSeparate = false;
756 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
761 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
762 assert(LII != NewLI.end() && "Missing live range for PHI");
763 if (LII->end != VNI->def.getNextSlot())
765 if (VNI->isPHIDef()) {
766 // This is a dead PHI. Remove it.
767 VNI->setIsUnused(true);
768 NewLI.removeRange(*LII);
769 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
772 // This is a dead def. Make sure the instruction knows.
773 MachineInstr *MI = getInstructionFromIndex(VNI->def);
774 assert(MI && "No instruction defining live value");
775 MI->addRegisterDead(li->reg, tri_);
776 if (dead && MI->allDefsAreDead()) {
777 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
783 // Move the trimmed ranges back.
784 li->ranges.swap(NewLI.ranges);
785 DEBUG(dbgs() << "Shrunk: " << *li << '\n');
790 //===----------------------------------------------------------------------===//
791 // Register allocator hooks.
794 MachineBasicBlock::iterator
795 LiveIntervals::getLastSplitPoint(const LiveInterval &li,
796 MachineBasicBlock *mbb) const {
797 const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
799 // If li is not live into a landing pad, we can insert spill code before the
801 if (!lpad || !isLiveInToMBB(li, lpad))
802 return mbb->getFirstTerminator();
804 // When there is a landing pad, spill code must go before the call instruction
806 MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
809 if (I->getDesc().isCall())
812 // The block contains no calls that can throw, so use the first terminator.
813 return mbb->getFirstTerminator();
816 void LiveIntervals::addKillFlags() {
817 for (iterator I = begin(), E = end(); I != E; ++I) {
818 unsigned Reg = I->first;
819 if (TargetRegisterInfo::isPhysicalRegister(Reg))
821 if (mri_->reg_nodbg_empty(Reg))
823 LiveInterval *LI = I->second;
825 // Every instruction that kills Reg corresponds to a live range end point.
826 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
828 // A LOAD index indicates an MBB edge.
829 if (RI->end.isLoad())
831 MachineInstr *MI = getInstructionFromIndex(RI->end);
834 MI->addRegisterKilled(Reg, NULL);
839 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
840 /// allow one) virtual register operand, then its uses are implicitly using
841 /// the register. Returns the virtual register.
842 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
843 MachineInstr *MI) const {
845 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
846 MachineOperand &MO = MI->getOperand(i);
847 if (!MO.isReg() || !MO.isUse())
849 unsigned Reg = MO.getReg();
850 if (Reg == 0 || Reg == li.reg)
853 if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
854 !allocatableRegs_[Reg])
856 // FIXME: For now, only remat MI with at most one register operand.
858 "Can't rematerialize instruction with multiple register operand!");
867 /// isValNoAvailableAt - Return true if the val# of the specified interval
868 /// which reaches the given instruction also reaches the specified use index.
869 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
870 SlotIndex UseIdx) const {
871 VNInfo *UValNo = li.getVNInfoAt(UseIdx);
872 return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
875 /// isReMaterializable - Returns true if the definition MI of the specified
876 /// val# of the specified interval is re-materializable.
878 LiveIntervals::isReMaterializable(const LiveInterval &li,
879 const VNInfo *ValNo, MachineInstr *MI,
880 const SmallVectorImpl<LiveInterval*> *SpillIs,
885 if (!tii_->isTriviallyReMaterializable(MI, aa_))
888 // Target-specific code can mark an instruction as being rematerializable
889 // if it has one virtual reg use, though it had better be something like
890 // a PIC base register which is likely to be live everywhere.
891 unsigned ImpUse = getReMatImplicitUse(li, MI);
893 const LiveInterval &ImpLi = getInterval(ImpUse);
894 for (MachineRegisterInfo::use_nodbg_iterator
895 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
897 MachineInstr *UseMI = &*ri;
898 SlotIndex UseIdx = getInstructionIndex(UseMI);
899 if (li.getVNInfoAt(UseIdx) != ValNo)
901 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
905 // If a register operand of the re-materialized instruction is going to
906 // be spilled next, then it's not legal to re-materialize this instruction.
908 for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
909 if (ImpUse == (*SpillIs)[i]->reg)
915 /// isReMaterializable - Returns true if every definition of MI of every
916 /// val# of the specified interval is re-materializable.
918 LiveIntervals::isReMaterializable(const LiveInterval &li,
919 const SmallVectorImpl<LiveInterval*> *SpillIs,
922 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
924 const VNInfo *VNI = *i;
926 continue; // Dead val#.
927 // Is the def for the val# rematerializable?
928 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
931 bool DefIsLoad = false;
933 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
940 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
941 LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
943 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
948 for (++itr; itr != li.ranges.end(); ++itr) {
949 MachineBasicBlock *mbb2 =
950 indexes_->getMBBCoveringRange(itr->start, itr->end);
960 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
961 // Limit the loop depth ridiculousness.
965 // The loop depth is used to roughly estimate the number of times the
966 // instruction is executed. Something like 10^d is simple, but will quickly
967 // overflow a float. This expression behaves like 10^d for small d, but is
968 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
969 // headroom before overflow.
970 // By the way, powf() might be unavailable here. For consistency,
971 // We may take pow(double,double).
972 float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
974 return (isDef + isUse) * lc;
977 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
978 MachineInstr* startInst) {
979 LiveInterval& Interval = getOrCreateInterval(reg);
980 VNInfo* VN = Interval.getNextValue(
981 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
982 startInst, getVNInfoAllocator());
983 VN->setHasPHIKill(true);
985 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
986 getMBBEndIdx(startInst->getParent()), VN);
987 Interval.addRange(LR);