1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
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/CodeGen/LiveVariables.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/CodeGen/MachineInstr.h"
25 #include "llvm/CodeGen/Passes.h"
26 #include "llvm/CodeGen/SSARegMap.h"
27 #include "llvm/Target/MRegisterInfo.h"
28 #include "llvm/Target/TargetInstrInfo.h"
29 #include "llvm/Target/TargetMachine.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/ADT/STLExtras.h"
39 // Hidden options for help debugging.
40 cl::opt<bool> DisableReMat("disable-rematerialization",
41 cl::init(false), cl::Hidden);
44 STATISTIC(numIntervals, "Number of original intervals");
45 STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
46 STATISTIC(numFolded , "Number of loads/stores folded into instructions");
48 char LiveIntervals::ID = 0;
50 RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
53 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
54 AU.addPreserved<LiveVariables>();
55 AU.addRequired<LiveVariables>();
56 AU.addPreservedID(PHIEliminationID);
57 AU.addRequiredID(PHIEliminationID);
58 AU.addRequiredID(TwoAddressInstructionPassID);
59 MachineFunctionPass::getAnalysisUsage(AU);
62 void LiveIntervals::releaseMemory() {
67 // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
68 VNInfoAllocator.Reset();
69 for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
74 inline bool operator<(unsigned V, const IdxMBBPair &IM) {
78 inline bool operator<(const IdxMBBPair &IM, unsigned V) {
82 struct Idx2MBBCompare {
83 bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
84 return LHS.first < RHS.first;
89 /// runOnMachineFunction - Register allocate the whole function
91 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
93 tm_ = &fn.getTarget();
94 mri_ = tm_->getRegisterInfo();
95 tii_ = tm_->getInstrInfo();
96 lv_ = &getAnalysis<LiveVariables>();
97 allocatableRegs_ = mri_->getAllocatableSet(fn);
99 // Number MachineInstrs and MachineBasicBlocks.
100 // Initialize MBB indexes to a sentinal.
101 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
103 unsigned MIIndex = 0;
104 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
106 unsigned StartIdx = MIIndex;
108 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
110 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
111 assert(inserted && "multiple MachineInstr -> index mappings");
112 i2miMap_.push_back(I);
113 MIIndex += InstrSlots::NUM;
116 // Set the MBB2IdxMap entry for this MBB.
117 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
118 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
120 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
124 numIntervals += getNumIntervals();
126 DOUT << "********** INTERVALS **********\n";
127 for (iterator I = begin(), E = end(); I != E; ++I) {
128 I->second.print(DOUT, mri_);
132 numIntervalsAfter += getNumIntervals();
137 /// print - Implement the dump method.
138 void LiveIntervals::print(std::ostream &O, const Module* ) const {
139 O << "********** INTERVALS **********\n";
140 for (const_iterator I = begin(), E = end(); I != E; ++I) {
141 I->second.print(DOUT, mri_);
145 O << "********** MACHINEINSTRS **********\n";
146 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
147 mbbi != mbbe; ++mbbi) {
148 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
149 for (MachineBasicBlock::iterator mii = mbbi->begin(),
150 mie = mbbi->end(); mii != mie; ++mii) {
151 O << getInstructionIndex(mii) << '\t' << *mii;
156 /// isReMaterializable - Returns true if the definition MI of the specified
157 /// val# of the specified interval is re-materializable.
158 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
159 const VNInfo *ValNo, MachineInstr *MI) {
163 if (tii_->isTriviallyReMaterializable(MI))
167 if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
168 !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
171 // This is a load from fixed stack slot. It can be rematerialized unless it's
172 // re-defined by a two-address instruction.
173 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
175 const VNInfo *VNI = *i;
178 unsigned DefIdx = VNI->def;
180 continue; // Dead val#.
181 MachineInstr *DefMI = (DefIdx == ~0u)
182 ? NULL : getInstructionFromIndex(DefIdx);
183 if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg))
189 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
190 /// slot / to reg or any rematerialized load into ith operand of specified
191 /// MI. If it is successul, MI is updated with the newly created MI and
193 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
195 unsigned index, unsigned i,
196 bool isSS, int slot, unsigned reg) {
197 MachineInstr *fmi = isSS
198 ? mri_->foldMemoryOperand(MI, i, slot)
199 : mri_->foldMemoryOperand(MI, i, DefMI);
201 // Attempt to fold the memory reference into the instruction. If
202 // we can do this, we don't need to insert spill code.
204 lv_->instructionChanged(MI, fmi);
205 MachineBasicBlock &MBB = *MI->getParent();
206 vrm.virtFolded(reg, MI, i, fmi);
208 i2miMap_[index/InstrSlots::NUM] = fmi;
209 mi2iMap_[fmi] = index;
210 MI = MBB.insert(MBB.erase(MI), fmi);
217 std::vector<LiveInterval*> LiveIntervals::
218 addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
219 // since this is called after the analysis is done we don't know if
220 // LiveVariables is available
221 lv_ = getAnalysisToUpdate<LiveVariables>();
223 std::vector<LiveInterval*> added;
225 assert(li.weight != HUGE_VALF &&
226 "attempt to spill already spilled interval!");
228 DOUT << "\t\t\t\tadding intervals for spills for interval: ";
229 li.print(DOUT, mri_);
232 SSARegMap *RegMap = mf_->getSSARegMap();
233 const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
235 unsigned NumValNums = li.getNumValNums();
236 SmallVector<MachineInstr*, 4> ReMatDefs;
237 ReMatDefs.resize(NumValNums, NULL);
238 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
239 ReMatOrigDefs.resize(NumValNums, NULL);
240 SmallVector<int, 4> ReMatIds;
241 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
242 BitVector ReMatDelete(NumValNums);
243 unsigned slot = VirtRegMap::MAX_STACK_SLOT;
245 bool NeedStackSlot = false;
246 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
248 const VNInfo *VNI = *i;
249 unsigned VN = VNI->id;
250 unsigned DefIdx = VNI->def;
252 continue; // Dead val#.
253 // Is the def for the val# rematerializable?
254 MachineInstr *DefMI = (DefIdx == ~0u)
255 ? NULL : getInstructionFromIndex(DefIdx);
256 if (DefMI && isReMaterializable(li, VNI, DefMI)) {
257 // Remember how to remat the def of this val#.
258 ReMatOrigDefs[VN] = DefMI;
259 // Original def may be modified so we have to make a copy here. vrm must
261 ReMatDefs[VN] = DefMI = DefMI->clone();
262 vrm.setVirtIsReMaterialized(reg, DefMI);
264 bool CanDelete = true;
265 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
266 unsigned KillIdx = VNI->kills[j];
267 MachineInstr *KillMI = (KillIdx & 1)
268 ? NULL : getInstructionFromIndex(KillIdx);
269 // Kill is a phi node, not all of its uses can be rematerialized.
270 // It must not be deleted.
273 // Need a stack slot if there is any live range where uses cannot be
275 NeedStackSlot = true;
283 // Need a stack slot if there is any live range where uses cannot be
285 NeedStackSlot = true;
289 // One stack slot per live interval.
291 slot = vrm.assignVirt2StackSlot(reg);
293 for (LiveInterval::Ranges::const_iterator
294 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
295 MachineInstr *DefMI = ReMatDefs[I->valno->id];
296 MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id];
297 bool DefIsReMat = DefMI != NULL;
298 bool CanDelete = ReMatDelete[I->valno->id];
300 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot);
301 bool isLoad = isLoadSS ||
302 (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
303 unsigned index = getBaseIndex(I->start);
304 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
305 for (; index != end; index += InstrSlots::NUM) {
306 // skip deleted instructions
307 while (index != end && !getInstructionFromIndex(index))
308 index += InstrSlots::NUM;
309 if (index == end) break;
311 MachineInstr *MI = getInstructionFromIndex(index);
314 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
315 MachineOperand& mop = MI->getOperand(i);
316 if (!mop.isRegister())
318 unsigned Reg = mop.getReg();
320 if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
322 bool isSubReg = RegMap->isSubRegister(Reg);
325 SubIdx = RegMap->getSubRegisterIndex(Reg);
326 Reg = RegMap->getSuperRegister(Reg);
331 bool TryFold = !DefIsReMat;
335 // If this is the rematerializable definition MI itself and
336 // all of its uses are rematerialized, simply delete it.
337 if (MI == OrigDefMI && CanDelete) {
338 RemoveMachineInstrFromMaps(MI);
339 MI->eraseFromParent();
343 // If def for this use can't be rematerialized, then try folding.
344 TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad));
346 // Try fold loads (from stack slot, constant pool, etc.) into uses.
352 // FIXME: fold subreg use
353 if (!isSubReg && TryFold &&
354 tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg))
355 // Folding the load/store can completely change the instruction in
356 // unpredictable ways, rescan it from the beginning.
357 goto RestartInstruction;
359 // Create a new virtual register for the spill interval.
360 unsigned NewVReg = RegMap->createVirtualRegister(rc);
362 RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx);
364 // Scan all of the operands of this instruction rewriting operands
365 // to use NewVReg instead of li.reg as appropriate. We do this for
368 // 1. If the instr reads the same spilled vreg multiple times, we
369 // want to reuse the NewVReg.
370 // 2. If the instr is a two-addr instruction, we are required to
371 // keep the src/dst regs pinned.
373 // Keep track of whether we replace a use and/or def so that we can
374 // create the spill interval with the appropriate range.
377 bool HasUse = mop.isUse();
378 bool HasDef = mop.isDef();
379 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
380 if (!MI->getOperand(j).isRegister())
382 unsigned RegJ = MI->getOperand(j).getReg();
383 if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ))
386 MI->getOperand(j).setReg(NewVReg);
387 HasUse |= MI->getOperand(j).isUse();
388 HasDef |= MI->getOperand(j).isDef();
394 vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
395 if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) {
396 // Each valnum may have its own remat id.
397 ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg);
399 vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]);
401 if (!CanDelete || (HasUse && HasDef)) {
402 // If this is a two-addr instruction then its use operands are
403 // rematerializable but its def is not. It should be assigned a
405 vrm.assignVirt2StackSlot(NewVReg, slot);
408 vrm.assignVirt2StackSlot(NewVReg, slot);
411 // create a new register interval for this spill / remat.
412 LiveInterval &nI = getOrCreateInterval(NewVReg);
415 // the spill weight is now infinity as it
416 // cannot be spilled again
417 nI.weight = HUGE_VALF;
420 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
421 nI.getNextValue(~0U, 0, VNInfoAllocator));
426 LiveRange LR(getDefIndex(index), getStoreIndex(index),
427 nI.getNextValue(~0U, 0, VNInfoAllocator));
432 added.push_back(&nI);
434 // update live variables if it is available
436 lv_->addVirtualRegisterKilled(NewVReg, MI);
438 DOUT << "\t\t\t\tadded new interval: ";
439 nI.print(DOUT, mri_);
448 /// conflictsWithPhysRegDef - Returns true if the specified register
449 /// is defined during the duration of the specified interval.
450 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
451 VirtRegMap &vrm, unsigned reg) {
452 for (LiveInterval::Ranges::const_iterator
453 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
454 for (unsigned index = getBaseIndex(I->start),
455 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
456 index += InstrSlots::NUM) {
457 // skip deleted instructions
458 while (index != end && !getInstructionFromIndex(index))
459 index += InstrSlots::NUM;
460 if (index == end) break;
462 MachineInstr *MI = getInstructionFromIndex(index);
463 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
464 MachineOperand& mop = MI->getOperand(i);
465 if (!mop.isRegister() || !mop.isDef())
467 unsigned PhysReg = mop.getReg();
470 if (MRegisterInfo::isVirtualRegister(PhysReg))
471 PhysReg = vrm.getPhys(PhysReg);
472 if (PhysReg && mri_->regsOverlap(PhysReg, reg))
481 void LiveIntervals::printRegName(unsigned reg) const {
482 if (MRegisterInfo::isPhysicalRegister(reg))
483 cerr << mri_->getName(reg);
485 cerr << "%reg" << reg;
488 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
489 MachineBasicBlock::iterator mi,
491 LiveInterval &interval) {
492 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
493 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
495 // Virtual registers may be defined multiple times (due to phi
496 // elimination and 2-addr elimination). Much of what we do only has to be
497 // done once for the vreg. We use an empty interval to detect the first
498 // time we see a vreg.
499 if (interval.empty()) {
500 // Get the Idx of the defining instructions.
501 unsigned defIndex = getDefIndex(MIIdx);
503 unsigned SrcReg, DstReg;
504 if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
505 ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
506 else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
507 ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
510 ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
512 assert(ValNo->id == 0 && "First value in interval is not 0?");
514 // Loop over all of the blocks that the vreg is defined in. There are
515 // two cases we have to handle here. The most common case is a vreg
516 // whose lifetime is contained within a basic block. In this case there
517 // will be a single kill, in MBB, which comes after the definition.
518 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
519 // FIXME: what about dead vars?
521 if (vi.Kills[0] != mi)
522 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
524 killIdx = defIndex+1;
526 // If the kill happens after the definition, we have an intra-block
528 if (killIdx > defIndex) {
529 assert(vi.AliveBlocks.none() &&
530 "Shouldn't be alive across any blocks!");
531 LiveRange LR(defIndex, killIdx, ValNo);
532 interval.addRange(LR);
533 DOUT << " +" << LR << "\n";
534 interval.addKill(ValNo, killIdx);
539 // The other case we handle is when a virtual register lives to the end
540 // of the defining block, potentially live across some blocks, then is
541 // live into some number of blocks, but gets killed. Start by adding a
542 // range that goes from this definition to the end of the defining block.
543 LiveRange NewLR(defIndex,
544 getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
546 DOUT << " +" << NewLR;
547 interval.addRange(NewLR);
549 // Iterate over all of the blocks that the variable is completely
550 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
552 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
553 if (vi.AliveBlocks[i]) {
554 MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
556 LiveRange LR(getMBBStartIdx(i),
557 getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
559 interval.addRange(LR);
565 // Finally, this virtual register is live from the start of any killing
566 // block to the 'use' slot of the killing instruction.
567 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
568 MachineInstr *Kill = vi.Kills[i];
569 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
570 LiveRange LR(getMBBStartIdx(Kill->getParent()),
572 interval.addRange(LR);
573 interval.addKill(ValNo, killIdx);
578 // If this is the second time we see a virtual register definition, it
579 // must be due to phi elimination or two addr elimination. If this is
580 // the result of two address elimination, then the vreg is one of the
581 // def-and-use register operand.
582 if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
583 // If this is a two-address definition, then we have already processed
584 // the live range. The only problem is that we didn't realize there
585 // are actually two values in the live interval. Because of this we
586 // need to take the LiveRegion that defines this register and split it
588 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
589 unsigned RedefIndex = getDefIndex(MIIdx);
591 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
592 VNInfo *OldValNo = OldLR->valno;
593 unsigned OldEnd = OldLR->end;
595 // Delete the initial value, which should be short and continuous,
596 // because the 2-addr copy must be in the same MBB as the redef.
597 interval.removeRange(DefIndex, RedefIndex);
599 // Two-address vregs should always only be redefined once. This means
600 // that at this point, there should be exactly one value number in it.
601 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
603 // The new value number (#1) is defined by the instruction we claimed
605 VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
606 interval.copyValNumInfo(ValNo, OldValNo);
608 // Value#0 is now defined by the 2-addr instruction.
609 OldValNo->def = RedefIndex;
612 // Add the new live interval which replaces the range for the input copy.
613 LiveRange LR(DefIndex, RedefIndex, ValNo);
614 DOUT << " replace range with " << LR;
615 interval.addRange(LR);
616 interval.addKill(ValNo, RedefIndex);
617 interval.removeKills(ValNo, RedefIndex, OldEnd);
619 // If this redefinition is dead, we need to add a dummy unit live
620 // range covering the def slot.
621 if (lv_->RegisterDefIsDead(mi, interval.reg))
622 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
625 interval.print(DOUT, mri_);
628 // Otherwise, this must be because of phi elimination. If this is the
629 // first redefinition of the vreg that we have seen, go back and change
630 // the live range in the PHI block to be a different value number.
631 if (interval.containsOneValue()) {
632 assert(vi.Kills.size() == 1 &&
633 "PHI elimination vreg should have one kill, the PHI itself!");
635 // Remove the old range that we now know has an incorrect number.
636 VNInfo *VNI = interval.getValNumInfo(0);
637 MachineInstr *Killer = vi.Kills[0];
638 unsigned Start = getMBBStartIdx(Killer->getParent());
639 unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
640 DOUT << " Removing [" << Start << "," << End << "] from: ";
641 interval.print(DOUT, mri_); DOUT << "\n";
642 interval.removeRange(Start, End);
643 interval.addKill(VNI, Start+1); // odd # means phi node
644 DOUT << " RESULT: "; interval.print(DOUT, mri_);
646 // Replace the interval with one of a NEW value number. Note that this
647 // value number isn't actually defined by an instruction, weird huh? :)
648 LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
649 DOUT << " replace range with " << LR;
650 interval.addRange(LR);
651 interval.addKill(LR.valno, End);
652 DOUT << " RESULT: "; interval.print(DOUT, mri_);
655 // In the case of PHI elimination, each variable definition is only
656 // live until the end of the block. We've already taken care of the
657 // rest of the live range.
658 unsigned defIndex = getDefIndex(MIIdx);
661 unsigned SrcReg, DstReg;
662 if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
663 ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
664 else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
665 ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
668 ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
670 unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
671 LiveRange LR(defIndex, killIndex, ValNo);
672 interval.addRange(LR);
673 interval.addKill(ValNo, killIndex-1); // odd # means phi node
681 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
682 MachineBasicBlock::iterator mi,
684 LiveInterval &interval,
686 // A physical register cannot be live across basic block, so its
687 // lifetime must end somewhere in its defining basic block.
688 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
690 unsigned baseIndex = MIIdx;
691 unsigned start = getDefIndex(baseIndex);
692 unsigned end = start;
694 // If it is not used after definition, it is considered dead at
695 // the instruction defining it. Hence its interval is:
696 // [defSlot(def), defSlot(def)+1)
697 if (lv_->RegisterDefIsDead(mi, interval.reg)) {
699 end = getDefIndex(start) + 1;
703 // If it is not dead on definition, it must be killed by a
704 // subsequent instruction. Hence its interval is:
705 // [defSlot(def), useSlot(kill)+1)
706 while (++mi != MBB->end()) {
707 baseIndex += InstrSlots::NUM;
708 if (lv_->KillsRegister(mi, interval.reg)) {
710 end = getUseIndex(baseIndex) + 1;
712 } else if (lv_->ModifiesRegister(mi, interval.reg)) {
713 // Another instruction redefines the register before it is ever read.
714 // Then the register is essentially dead at the instruction that defines
715 // it. Hence its interval is:
716 // [defSlot(def), defSlot(def)+1)
718 end = getDefIndex(start) + 1;
723 // The only case we should have a dead physreg here without a killing or
724 // instruction where we know it's dead is if it is live-in to the function
726 assert(!SrcReg && "physreg was not killed in defining block!");
727 end = getDefIndex(start) + 1; // It's dead.
730 assert(start < end && "did not find end of interval?");
732 // Already exists? Extend old live interval.
733 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
734 VNInfo *ValNo = (OldLR != interval.end())
735 ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
736 LiveRange LR(start, end, ValNo);
737 interval.addRange(LR);
738 interval.addKill(LR.valno, end);
739 DOUT << " +" << LR << '\n';
742 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
743 MachineBasicBlock::iterator MI,
746 if (MRegisterInfo::isVirtualRegister(reg))
747 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
748 else if (allocatableRegs_[reg]) {
749 unsigned SrcReg, DstReg;
750 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
751 SrcReg = MI->getOperand(1).getReg();
752 else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
754 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
755 // Def of a register also defines its sub-registers.
756 for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
757 // Avoid processing some defs more than once.
758 if (!MI->findRegisterDefOperand(*AS))
759 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
763 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
765 LiveInterval &interval, bool isAlias) {
766 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
768 // Look for kills, if it reaches a def before it's killed, then it shouldn't
769 // be considered a livein.
770 MachineBasicBlock::iterator mi = MBB->begin();
771 unsigned baseIndex = MIIdx;
772 unsigned start = baseIndex;
773 unsigned end = start;
774 while (mi != MBB->end()) {
775 if (lv_->KillsRegister(mi, interval.reg)) {
777 end = getUseIndex(baseIndex) + 1;
779 } else if (lv_->ModifiesRegister(mi, interval.reg)) {
780 // Another instruction redefines the register before it is ever read.
781 // Then the register is essentially dead at the instruction that defines
782 // it. Hence its interval is:
783 // [defSlot(def), defSlot(def)+1)
785 end = getDefIndex(start) + 1;
789 baseIndex += InstrSlots::NUM;
794 // Live-in register might not be used at all.
798 end = getDefIndex(MIIdx) + 1;
800 DOUT << " live through";
805 LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
806 interval.addRange(LR);
807 interval.addKill(LR.valno, end);
808 DOUT << " +" << LR << '\n';
811 /// computeIntervals - computes the live intervals for virtual
812 /// registers. for some ordering of the machine instructions [1,N] a
813 /// live interval is an interval [i, j) where 1 <= i <= j < N for
814 /// which a variable is live
815 void LiveIntervals::computeIntervals() {
816 DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
817 << "********** Function: "
818 << ((Value*)mf_->getFunction())->getName() << '\n';
819 // Track the index of the current machine instr.
820 unsigned MIIndex = 0;
821 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
823 MachineBasicBlock *MBB = MBBI;
824 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
826 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
828 // Create intervals for live-ins to this BB first.
829 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
830 LE = MBB->livein_end(); LI != LE; ++LI) {
831 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
832 // Multiple live-ins can alias the same register.
833 for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
834 if (!hasInterval(*AS))
835 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
839 for (; MI != miEnd; ++MI) {
840 DOUT << MIIndex << "\t" << *MI;
843 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
844 MachineOperand &MO = MI->getOperand(i);
845 // handle register defs - build intervals
846 if (MO.isRegister() && MO.getReg() && MO.isDef())
847 handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
850 MIIndex += InstrSlots::NUM;
855 bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
856 SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
857 std::vector<IdxMBBPair>::const_iterator I =
858 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
861 while (I != Idx2MBBMap.end()) {
862 if (LR.end <= I->first)
864 MBBs.push_back(I->second);
872 LiveInterval LiveIntervals::createInterval(unsigned reg) {
873 float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
875 return LiveInterval(reg, Weight);