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 "regalloc"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "LiveRangeCalc.h"
21 #include "llvm/ADT/DenseSet.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/CodeGen/LiveVariables.h"
25 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
26 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 #include "llvm/CodeGen/Passes.h"
30 #include "llvm/CodeGen/VirtRegMap.h"
31 #include "llvm/IR/Value.h"
32 #include "llvm/Support/BlockFrequency.h"
33 #include "llvm/Support/CommandLine.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/ErrorHandling.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include "llvm/Target/TargetInstrInfo.h"
38 #include "llvm/Target/TargetMachine.h"
39 #include "llvm/Target/TargetRegisterInfo.h"
45 char LiveIntervals::ID = 0;
46 char &llvm::LiveIntervalsID = LiveIntervals::ID;
47 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
48 "Live Interval Analysis", false, false)
49 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
50 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
51 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
52 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
53 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
54 "Live Interval Analysis", false, false)
57 static cl::opt<bool> EnablePrecomputePhysRegs(
58 "precompute-phys-liveness", cl::Hidden,
59 cl::desc("Eagerly compute live intervals for all physreg units."));
61 static bool EnablePrecomputePhysRegs = false;
64 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
66 AU.addRequired<AliasAnalysis>();
67 AU.addPreserved<AliasAnalysis>();
68 // LiveVariables isn't really required by this analysis, it is only required
69 // here to make sure it is live during TwoAddressInstructionPass and
70 // PHIElimination. This is temporary.
71 AU.addRequired<LiveVariables>();
72 AU.addPreserved<LiveVariables>();
73 AU.addPreservedID(MachineLoopInfoID);
74 AU.addRequiredTransitiveID(MachineDominatorsID);
75 AU.addPreservedID(MachineDominatorsID);
76 AU.addPreserved<SlotIndexes>();
77 AU.addRequiredTransitive<SlotIndexes>();
78 MachineFunctionPass::getAnalysisUsage(AU);
81 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
82 DomTree(nullptr), LRCalc(nullptr) {
83 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
86 LiveIntervals::~LiveIntervals() {
90 void LiveIntervals::releaseMemory() {
91 // Free the live intervals themselves.
92 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
93 delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
94 VirtRegIntervals.clear();
97 RegMaskBlocks.clear();
99 for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
100 delete RegUnitRanges[i];
101 RegUnitRanges.clear();
103 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
104 VNInfoAllocator.Reset();
107 /// runOnMachineFunction - calculates LiveIntervals
109 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
111 MRI = &MF->getRegInfo();
112 TM = &fn.getTarget();
113 TRI = TM->getRegisterInfo();
114 TII = TM->getInstrInfo();
115 AA = &getAnalysis<AliasAnalysis>();
116 Indexes = &getAnalysis<SlotIndexes>();
117 DomTree = &getAnalysis<MachineDominatorTree>();
119 LRCalc = new LiveRangeCalc();
121 // Allocate space for all virtual registers.
122 VirtRegIntervals.resize(MRI->getNumVirtRegs());
126 computeLiveInRegUnits();
128 if (EnablePrecomputePhysRegs) {
129 // For stress testing, precompute live ranges of all physical register
130 // units, including reserved registers.
131 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
138 /// print - Implement the dump method.
139 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
140 OS << "********** INTERVALS **********\n";
142 // Dump the regunits.
143 for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i)
144 if (LiveRange *LR = RegUnitRanges[i])
145 OS << PrintRegUnit(i, TRI) << ' ' << *LR << '\n';
147 // Dump the virtregs.
148 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
149 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
150 if (hasInterval(Reg))
151 OS << getInterval(Reg) << '\n';
155 for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i)
156 OS << ' ' << RegMaskSlots[i];
162 void LiveIntervals::printInstrs(raw_ostream &OS) const {
163 OS << "********** MACHINEINSTRS **********\n";
164 MF->print(OS, Indexes);
167 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
168 void LiveIntervals::dumpInstrs() const {
173 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
174 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
175 llvm::huge_valf : 0.0F;
176 return new LiveInterval(reg, Weight);
180 /// computeVirtRegInterval - Compute the live interval of a virtual register,
181 /// based on defs and uses.
182 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
183 assert(LRCalc && "LRCalc not initialized.");
184 assert(LI.empty() && "Should only compute empty intervals.");
185 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
186 LRCalc->createDeadDefs(LI);
187 LRCalc->extendToUses(LI);
190 void LiveIntervals::computeVirtRegs() {
191 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
192 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
193 if (MRI->reg_nodbg_empty(Reg))
195 createAndComputeVirtRegInterval(Reg);
199 void LiveIntervals::computeRegMasks() {
200 RegMaskBlocks.resize(MF->getNumBlockIDs());
202 // Find all instructions with regmask operands.
203 for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
205 MachineBasicBlock *MBB = MBBI;
206 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
207 RMB.first = RegMaskSlots.size();
208 for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
210 for (MIOperands MO(MI); MO.isValid(); ++MO) {
211 if (!MO->isRegMask())
213 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
214 RegMaskBits.push_back(MO->getRegMask());
216 // Compute the number of register mask instructions in this block.
217 RMB.second = RegMaskSlots.size() - RMB.first;
221 //===----------------------------------------------------------------------===//
222 // Register Unit Liveness
223 //===----------------------------------------------------------------------===//
225 // Fixed interference typically comes from ABI boundaries: Function arguments
226 // and return values are passed in fixed registers, and so are exception
227 // pointers entering landing pads. Certain instructions require values to be
228 // present in specific registers. That is also represented through fixed
232 /// computeRegUnitInterval - Compute the live range of a register unit, based
233 /// on the uses and defs of aliasing registers. The range should be empty,
234 /// or contain only dead phi-defs from ABI blocks.
235 void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
236 assert(LRCalc && "LRCalc not initialized.");
237 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
239 // The physregs aliasing Unit are the roots and their super-registers.
240 // Create all values as dead defs before extending to uses. Note that roots
241 // may share super-registers. That's OK because createDeadDefs() is
242 // idempotent. It is very rare for a register unit to have multiple roots, so
243 // uniquing super-registers is probably not worthwhile.
244 for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
245 for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
246 Supers.isValid(); ++Supers) {
247 if (!MRI->reg_empty(*Supers))
248 LRCalc->createDeadDefs(LR, *Supers);
252 // Now extend LR to reach all uses.
253 // Ignore uses of reserved registers. We only track defs of those.
254 for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
255 for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
256 Supers.isValid(); ++Supers) {
257 unsigned Reg = *Supers;
258 if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
259 LRCalc->extendToUses(LR, Reg);
265 /// computeLiveInRegUnits - Precompute the live ranges of any register units
266 /// that are live-in to an ABI block somewhere. Register values can appear
267 /// without a corresponding def when entering the entry block or a landing pad.
269 void LiveIntervals::computeLiveInRegUnits() {
270 RegUnitRanges.resize(TRI->getNumRegUnits());
271 DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
273 // Keep track of the live range sets allocated.
274 SmallVector<unsigned, 8> NewRanges;
276 // Check all basic blocks for live-ins.
277 for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
279 const MachineBasicBlock *MBB = MFI;
281 // We only care about ABI blocks: Entry + landing pads.
282 if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
285 // Create phi-defs at Begin for all live-in registers.
286 SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
287 DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
288 for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
289 LIE = MBB->livein_end(); LII != LIE; ++LII) {
290 for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
291 unsigned Unit = *Units;
292 LiveRange *LR = RegUnitRanges[Unit];
294 LR = RegUnitRanges[Unit] = new LiveRange();
295 NewRanges.push_back(Unit);
297 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
299 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
302 DEBUG(dbgs() << '\n');
304 DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
306 // Compute the 'normal' part of the ranges.
307 for (unsigned i = 0, e = NewRanges.size(); i != e; ++i) {
308 unsigned Unit = NewRanges[i];
309 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
314 /// shrinkToUses - After removing some uses of a register, shrink its live
315 /// range to just the remaining uses. This method does not compute reaching
316 /// defs for new uses, and it doesn't remove dead defs.
317 bool LiveIntervals::shrinkToUses(LiveInterval *li,
318 SmallVectorImpl<MachineInstr*> *dead) {
319 DEBUG(dbgs() << "Shrink: " << *li << '\n');
320 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
321 && "Can only shrink virtual registers");
322 // Find all the values used, including PHI kills.
323 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
325 // Blocks that have already been added to WorkList as live-out.
326 SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
328 // Visit all instructions reading li->reg.
329 for (MachineRegisterInfo::reg_instr_iterator
330 I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end();
332 MachineInstr *UseMI = &*(I++);
333 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
335 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
336 LiveQueryResult LRQ = li->Query(Idx);
337 VNInfo *VNI = LRQ.valueIn();
339 // This shouldn't happen: readsVirtualRegister returns true, but there is
340 // no live value. It is likely caused by a target getting <undef> flags
342 DEBUG(dbgs() << Idx << '\t' << *UseMI
343 << "Warning: Instr claims to read non-existent value in "
347 // Special case: An early-clobber tied operand reads and writes the
348 // register one slot early.
349 if (VNInfo *DefVNI = LRQ.valueDefined())
352 WorkList.push_back(std::make_pair(Idx, VNI));
355 // Create new live ranges with only minimal live segments per def.
357 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
362 NewLR.addSegment(LiveRange::Segment(VNI->def, VNI->def.getDeadSlot(), VNI));
365 // Keep track of the PHIs that are in use.
366 SmallPtrSet<VNInfo*, 8> UsedPHIs;
368 // Extend intervals to reach all uses in WorkList.
369 while (!WorkList.empty()) {
370 SlotIndex Idx = WorkList.back().first;
371 VNInfo *VNI = WorkList.back().second;
373 const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
374 SlotIndex BlockStart = getMBBStartIdx(MBB);
376 // Extend the live range for VNI to be live at Idx.
377 if (VNInfo *ExtVNI = NewLR.extendInBlock(BlockStart, Idx)) {
379 assert(ExtVNI == VNI && "Unexpected existing value number");
380 // Is this a PHIDef we haven't seen before?
381 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
383 // The PHI is live, make sure the predecessors are live-out.
384 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
385 PE = MBB->pred_end(); PI != PE; ++PI) {
386 if (!LiveOut.insert(*PI))
388 SlotIndex Stop = getMBBEndIdx(*PI);
389 // A predecessor is not required to have a live-out value for a PHI.
390 if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
391 WorkList.push_back(std::make_pair(Stop, PVNI));
396 // VNI is live-in to MBB.
397 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
398 NewLR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
400 // Make sure VNI is live-out from the predecessors.
401 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
402 PE = MBB->pred_end(); PI != PE; ++PI) {
403 if (!LiveOut.insert(*PI))
405 SlotIndex Stop = getMBBEndIdx(*PI);
406 assert(li->getVNInfoBefore(Stop) == VNI &&
407 "Wrong value out of predecessor");
408 WorkList.push_back(std::make_pair(Stop, VNI));
412 // Handle dead values.
413 bool CanSeparate = false;
414 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
419 LiveRange::iterator LRI = NewLR.FindSegmentContaining(VNI->def);
420 assert(LRI != NewLR.end() && "Missing segment for PHI");
421 if (LRI->end != VNI->def.getDeadSlot())
423 if (VNI->isPHIDef()) {
424 // This is a dead PHI. Remove it.
426 NewLR.removeSegment(LRI->start, LRI->end);
427 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
430 // This is a dead def. Make sure the instruction knows.
431 MachineInstr *MI = getInstructionFromIndex(VNI->def);
432 assert(MI && "No instruction defining live value");
433 MI->addRegisterDead(li->reg, TRI);
434 if (dead && MI->allDefsAreDead()) {
435 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
441 // Move the trimmed segments back.
442 li->segments.swap(NewLR.segments);
443 DEBUG(dbgs() << "Shrunk: " << *li << '\n');
447 void LiveIntervals::extendToIndices(LiveRange &LR,
448 ArrayRef<SlotIndex> Indices) {
449 assert(LRCalc && "LRCalc not initialized.");
450 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
451 for (unsigned i = 0, e = Indices.size(); i != e; ++i)
452 LRCalc->extend(LR, Indices[i]);
455 void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
456 SmallVectorImpl<SlotIndex> *EndPoints) {
457 LiveQueryResult LRQ = LI->Query(Kill);
458 VNInfo *VNI = LRQ.valueOut();
462 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
463 SlotIndex MBBStart, MBBEnd;
464 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB);
466 // If VNI isn't live out from KillMBB, the value is trivially pruned.
467 if (LRQ.endPoint() < MBBEnd) {
468 LI->removeSegment(Kill, LRQ.endPoint());
469 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
473 // VNI is live out of KillMBB.
474 LI->removeSegment(Kill, MBBEnd);
475 if (EndPoints) EndPoints->push_back(MBBEnd);
477 // Find all blocks that are reachable from KillMBB without leaving VNI's live
478 // range. It is possible that KillMBB itself is reachable, so start a DFS
479 // from each successor.
480 typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy;
482 for (MachineBasicBlock::succ_iterator
483 SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end();
484 SuccI != SuccE; ++SuccI) {
485 for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
486 I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited);
488 MachineBasicBlock *MBB = *I;
490 // Check if VNI is live in to MBB.
491 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
492 LiveQueryResult LRQ = LI->Query(MBBStart);
493 if (LRQ.valueIn() != VNI) {
494 // This block isn't part of the VNI segment. Prune the search.
499 // Prune the search if VNI is killed in MBB.
500 if (LRQ.endPoint() < MBBEnd) {
501 LI->removeSegment(MBBStart, LRQ.endPoint());
502 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
507 // VNI is live through MBB.
508 LI->removeSegment(MBBStart, MBBEnd);
509 if (EndPoints) EndPoints->push_back(MBBEnd);
515 //===----------------------------------------------------------------------===//
516 // Register allocator hooks.
519 void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
520 // Keep track of regunit ranges.
521 SmallVector<std::pair<LiveRange*, LiveRange::iterator>, 8> RU;
523 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
524 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
525 if (MRI->reg_nodbg_empty(Reg))
527 LiveInterval *LI = &getInterval(Reg);
531 // Find the regunit intervals for the assigned register. They may overlap
532 // the virtual register live range, cancelling any kills.
534 for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
536 LiveRange &RURanges = getRegUnit(*Units);
537 if (RURanges.empty())
539 RU.push_back(std::make_pair(&RURanges, RURanges.find(LI->begin()->end)));
542 // Every instruction that kills Reg corresponds to a segment range end
544 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
546 // A block index indicates an MBB edge.
547 if (RI->end.isBlock())
549 MachineInstr *MI = getInstructionFromIndex(RI->end);
553 // Check if any of the regunits are live beyond the end of RI. That could
554 // happen when a physreg is defined as a copy of a virtreg:
556 // %EAX = COPY %vreg5
557 // FOO %vreg5 <--- MI, cancel kill because %EAX is live.
560 // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
561 bool CancelKill = false;
562 for (unsigned u = 0, e = RU.size(); u != e; ++u) {
563 LiveRange &RRanges = *RU[u].first;
564 LiveRange::iterator &I = RU[u].second;
565 if (I == RRanges.end())
567 I = RRanges.advanceTo(I, RI->end);
568 if (I == RRanges.end() || I->start >= RI->end)
570 // I is overlapping RI.
575 MI->clearRegisterKills(Reg, nullptr);
577 MI->addRegisterKilled(Reg, nullptr);
583 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
584 // A local live range must be fully contained inside the block, meaning it is
585 // defined and killed at instructions, not at block boundaries. It is not
586 // live in or or out of any block.
588 // It is technically possible to have a PHI-defined live range identical to a
589 // single block, but we are going to return false in that case.
591 SlotIndex Start = LI.beginIndex();
595 SlotIndex Stop = LI.endIndex();
599 // getMBBFromIndex doesn't need to search the MBB table when both indexes
600 // belong to proper instructions.
601 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
602 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
603 return MBB1 == MBB2 ? MBB1 : nullptr;
607 LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
608 for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
610 const VNInfo *PHI = *I;
611 if (PHI->isUnused() || !PHI->isPHIDef())
613 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
614 // Conservatively return true instead of scanning huge predecessor lists.
615 if (PHIMBB->pred_size() > 100)
617 for (MachineBasicBlock::const_pred_iterator
618 PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI)
619 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
626 LiveIntervals::getSpillWeight(bool isDef, bool isUse,
627 const MachineBlockFrequencyInfo *MBFI,
628 const MachineInstr *MI) {
629 BlockFrequency Freq = MBFI->getBlockFreq(MI->getParent());
630 const float Scale = 1.0f / MBFI->getEntryFreq();
631 return (isDef + isUse) * (Freq.getFrequency() * Scale);
635 LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr* startInst) {
636 LiveInterval& Interval = createEmptyInterval(reg);
637 VNInfo* VN = Interval.getNextValue(
638 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
639 getVNInfoAllocator());
640 LiveRange::Segment S(
641 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
642 getMBBEndIdx(startInst->getParent()), VN);
643 Interval.addSegment(S);
649 //===----------------------------------------------------------------------===//
650 // Register mask functions
651 //===----------------------------------------------------------------------===//
653 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
654 BitVector &UsableRegs) {
657 LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
659 // Use a smaller arrays for local live ranges.
660 ArrayRef<SlotIndex> Slots;
661 ArrayRef<const uint32_t*> Bits;
662 if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
663 Slots = getRegMaskSlotsInBlock(MBB->getNumber());
664 Bits = getRegMaskBitsInBlock(MBB->getNumber());
666 Slots = getRegMaskSlots();
667 Bits = getRegMaskBits();
670 // We are going to enumerate all the register mask slots contained in LI.
671 // Start with a binary search of RegMaskSlots to find a starting point.
672 ArrayRef<SlotIndex>::iterator SlotI =
673 std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
674 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
676 // No slots in range, LI begins after the last call.
682 assert(*SlotI >= LiveI->start);
683 // Loop over all slots overlapping this segment.
684 while (*SlotI < LiveI->end) {
685 // *SlotI overlaps LI. Collect mask bits.
687 // This is the first overlap. Initialize UsableRegs to all ones.
689 UsableRegs.resize(TRI->getNumRegs(), true);
692 // Remove usable registers clobbered by this mask.
693 UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
694 if (++SlotI == SlotE)
697 // *SlotI is beyond the current LI segment.
698 LiveI = LI.advanceTo(LiveI, *SlotI);
701 // Advance SlotI until it overlaps.
702 while (*SlotI < LiveI->start)
703 if (++SlotI == SlotE)
708 //===----------------------------------------------------------------------===//
709 // IntervalUpdate class.
710 //===----------------------------------------------------------------------===//
712 // HMEditor is a toolkit used by handleMove to trim or extend live intervals.
713 class LiveIntervals::HMEditor {
716 const MachineRegisterInfo& MRI;
717 const TargetRegisterInfo& TRI;
720 SmallPtrSet<LiveRange*, 8> Updated;
724 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
725 const TargetRegisterInfo& TRI,
726 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
727 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
728 UpdateFlags(UpdateFlags) {}
730 // FIXME: UpdateFlags is a workaround that creates live intervals for all
731 // physregs, even those that aren't needed for regalloc, in order to update
732 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
733 // flags, and postRA passes will use a live register utility instead.
734 LiveRange *getRegUnitLI(unsigned Unit) {
736 return &LIS.getRegUnit(Unit);
737 return LIS.getCachedRegUnit(Unit);
740 /// Update all live ranges touched by MI, assuming a move from OldIdx to
742 void updateAllRanges(MachineInstr *MI) {
743 DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
744 bool hasRegMask = false;
745 for (MIOperands MO(MI); MO.isValid(); ++MO) {
750 // Aggressively clear all kill flags.
751 // They are reinserted by VirtRegRewriter.
753 MO->setIsKill(false);
755 unsigned Reg = MO->getReg();
758 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
759 LiveInterval &LI = LIS.getInterval(Reg);
760 updateRange(LI, Reg);
764 // For physregs, only update the regunits that actually have a
765 // precomputed live range.
766 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
767 if (LiveRange *LR = getRegUnitLI(*Units))
768 updateRange(*LR, *Units);
771 updateRegMaskSlots();
775 /// Update a single live range, assuming an instruction has been moved from
776 /// OldIdx to NewIdx.
777 void updateRange(LiveRange &LR, unsigned Reg) {
778 if (!Updated.insert(&LR))
782 if (TargetRegisterInfo::isVirtualRegister(Reg))
783 dbgs() << PrintReg(Reg);
785 dbgs() << PrintRegUnit(Reg, &TRI);
786 dbgs() << ":\t" << LR << '\n';
788 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
791 handleMoveUp(LR, Reg);
792 DEBUG(dbgs() << " -->\t" << LR << '\n');
796 /// Update LR to reflect an instruction has been moved downwards from OldIdx
799 /// 1. Live def at OldIdx:
800 /// Move def to NewIdx, assert endpoint after NewIdx.
802 /// 2. Live def at OldIdx, killed at NewIdx:
803 /// Change to dead def at NewIdx.
804 /// (Happens when bundling def+kill together).
806 /// 3. Dead def at OldIdx:
807 /// Move def to NewIdx, possibly across another live value.
809 /// 4. Def at OldIdx AND at NewIdx:
810 /// Remove segment [OldIdx;NewIdx) and value defined at OldIdx.
811 /// (Happens when bundling multiple defs together).
813 /// 5. Value read at OldIdx, killed before NewIdx:
814 /// Extend kill to NewIdx.
816 void handleMoveDown(LiveRange &LR) {
817 // First look for a kill at OldIdx.
818 LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
819 LiveRange::iterator E = LR.end();
820 // Is LR even live at OldIdx?
821 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
824 // Handle a live-in value.
825 if (!SlotIndex::isSameInstr(I->start, OldIdx)) {
826 bool isKill = SlotIndex::isSameInstr(OldIdx, I->end);
827 // If the live-in value already extends to NewIdx, there is nothing to do.
828 if (!SlotIndex::isEarlierInstr(I->end, NewIdx))
830 // Aggressively remove all kill flags from the old kill point.
831 // Kill flags shouldn't be used while live intervals exist, they will be
832 // reinserted by VirtRegRewriter.
833 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end))
834 for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO)
835 if (MO->isReg() && MO->isUse())
836 MO->setIsKill(false);
837 // Adjust I->end to reach NewIdx. This may temporarily make LR invalid by
838 // overlapping ranges. Case 5 above.
839 I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
840 // If this was a kill, there may also be a def. Otherwise we're done.
846 // Check for a def at OldIdx.
847 if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start))
849 // We have a def at OldIdx.
850 VNInfo *DefVNI = I->valno;
851 assert(DefVNI->def == I->start && "Inconsistent def");
852 DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
853 // If the defined value extends beyond NewIdx, just move the def down.
854 // This is case 1 above.
855 if (SlotIndex::isEarlierInstr(NewIdx, I->end)) {
856 I->start = DefVNI->def;
859 // The remaining possibilities are now:
860 // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx).
861 // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot().
862 // In either case, it is possible that there is an existing def at NewIdx.
863 assert((I->end == OldIdx.getDeadSlot() ||
864 SlotIndex::isSameInstr(I->end, NewIdx)) &&
865 "Cannot move def below kill");
866 LiveRange::iterator NewI = LR.advanceTo(I, NewIdx.getRegSlot());
867 if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
868 // There is an existing def at NewIdx, case 4 above. The def at OldIdx is
869 // coalesced into that value.
870 assert(NewI->valno != DefVNI && "Multiple defs of value?");
871 LR.removeValNo(DefVNI);
874 // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx.
875 // If the def at OldIdx was dead, we allow it to be moved across other LR
876 // values. The new range should be placed immediately before NewI, move any
877 // intermediate ranges up.
878 assert(NewI != I && "Inconsistent iterators");
879 std::copy(std::next(I), NewI, I);
881 = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
884 /// Update LR to reflect an instruction has been moved upwards from OldIdx
887 /// 1. Live def at OldIdx:
888 /// Hoist def to NewIdx.
890 /// 2. Dead def at OldIdx:
891 /// Hoist def+end to NewIdx, possibly move across other values.
893 /// 3. Dead def at OldIdx AND existing def at NewIdx:
894 /// Remove value defined at OldIdx, coalescing it with existing value.
896 /// 4. Live def at OldIdx AND existing def at NewIdx:
897 /// Remove value defined at NewIdx, hoist OldIdx def to NewIdx.
898 /// (Happens when bundling multiple defs together).
900 /// 5. Value killed at OldIdx:
901 /// Hoist kill to NewIdx, then scan for last kill between NewIdx and
904 void handleMoveUp(LiveRange &LR, unsigned Reg) {
905 // First look for a kill at OldIdx.
906 LiveRange::iterator I = LR.find(OldIdx.getBaseIndex());
907 LiveRange::iterator E = LR.end();
908 // Is LR even live at OldIdx?
909 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
912 // Handle a live-in value.
913 if (!SlotIndex::isSameInstr(I->start, OldIdx)) {
914 // If the live-in value isn't killed here, there is nothing to do.
915 if (!SlotIndex::isSameInstr(OldIdx, I->end))
917 // Adjust I->end to end at NewIdx. If we are hoisting a kill above
918 // another use, we need to search for that use. Case 5 above.
919 I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
921 // If OldIdx also defines a value, there couldn't have been another use.
922 if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
923 // No def, search for the new kill.
924 // This can never be an early clobber kill since there is no def.
925 std::prev(I)->end = findLastUseBefore(Reg).getRegSlot();
930 // Now deal with the def at OldIdx.
931 assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?");
932 VNInfo *DefVNI = I->valno;
933 assert(DefVNI->def == I->start && "Inconsistent def");
934 DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
936 // Check for an existing def at NewIdx.
937 LiveRange::iterator NewI = LR.find(NewIdx.getRegSlot());
938 if (SlotIndex::isSameInstr(NewI->start, NewIdx)) {
939 assert(NewI->valno != DefVNI && "Same value defined more than once?");
940 // There is an existing def at NewIdx.
941 if (I->end.isDead()) {
942 // Case 3: Remove the dead def at OldIdx.
943 LR.removeValNo(DefVNI);
946 // Case 4: Replace def at NewIdx with live def at OldIdx.
947 I->start = DefVNI->def;
948 LR.removeValNo(NewI->valno);
952 // There is no existing def at NewIdx. Hoist DefVNI.
953 if (!I->end.isDead()) {
954 // Leave the end point of a live def.
955 I->start = DefVNI->def;
959 // DefVNI is a dead def. It may have been moved across other values in LR,
960 // so move I up to NewI. Slide [NewI;I) down one position.
961 std::copy_backward(NewI, I, std::next(I));
962 *NewI = LiveRange::Segment(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
965 void updateRegMaskSlots() {
966 SmallVectorImpl<SlotIndex>::iterator RI =
967 std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
969 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
970 "No RegMask at OldIdx.");
971 *RI = NewIdx.getRegSlot();
972 assert((RI == LIS.RegMaskSlots.begin() ||
973 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
974 "Cannot move regmask instruction above another call");
975 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
976 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
977 "Cannot move regmask instruction below another call");
980 // Return the last use of reg between NewIdx and OldIdx.
981 SlotIndex findLastUseBefore(unsigned Reg) {
983 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
984 SlotIndex LastUse = NewIdx;
985 for (MachineRegisterInfo::use_instr_nodbg_iterator
986 UI = MRI.use_instr_nodbg_begin(Reg),
987 UE = MRI.use_instr_nodbg_end();
989 const MachineInstr* MI = &*UI;
990 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
991 if (InstSlot > LastUse && InstSlot < OldIdx)
997 // This is a regunit interval, so scanning the use list could be very
998 // expensive. Scan upwards from OldIdx instead.
999 assert(NewIdx < OldIdx && "Expected upwards move");
1000 SlotIndexes *Indexes = LIS.getSlotIndexes();
1001 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx);
1003 // OldIdx may not correspond to an instruction any longer, so set MII to
1004 // point to the next instruction after OldIdx, or MBB->end().
1005 MachineBasicBlock::iterator MII = MBB->end();
1006 if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1007 Indexes->getNextNonNullIndex(OldIdx)))
1008 if (MI->getParent() == MBB)
1011 MachineBasicBlock::iterator Begin = MBB->begin();
1012 while (MII != Begin) {
1013 if ((--MII)->isDebugValue())
1015 SlotIndex Idx = Indexes->getInstructionIndex(MII);
1017 // Stop searching when NewIdx is reached.
1018 if (!SlotIndex::isEarlierInstr(NewIdx, Idx))
1021 // Check if MII uses Reg.
1022 for (MIBundleOperands MO(MII); MO.isValid(); ++MO)
1024 TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
1025 TRI.hasRegUnit(MO->getReg(), Reg))
1028 // Didn't reach NewIdx. It must be the first instruction in the block.
1033 void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) {
1034 assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
1035 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1036 Indexes->removeMachineInstrFromMaps(MI);
1037 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1038 assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
1039 OldIndex < getMBBEndIdx(MI->getParent()) &&
1040 "Cannot handle moves across basic block boundaries.");
1042 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1043 HME.updateAllRanges(MI);
1046 void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
1047 MachineInstr* BundleStart,
1049 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1050 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1051 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1052 HME.updateAllRanges(MI);
1056 LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
1057 MachineBasicBlock::iterator Begin,
1058 MachineBasicBlock::iterator End,
1059 ArrayRef<unsigned> OrigRegs) {
1060 // Find anchor points, which are at the beginning/end of blocks or at
1061 // instructions that already have indexes.
1062 while (Begin != MBB->begin() && !Indexes->hasIndex(Begin))
1064 while (End != MBB->end() && !Indexes->hasIndex(End))
1068 if (End == MBB->end())
1069 endIdx = getMBBEndIdx(MBB).getPrevSlot();
1071 endIdx = getInstructionIndex(End);
1073 Indexes->repairIndexesInRange(MBB, Begin, End);
1075 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1077 MachineInstr *MI = I;
1078 if (MI->isDebugValue())
1080 for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1081 MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1083 TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
1084 !hasInterval(MOI->getReg())) {
1085 createAndComputeVirtRegInterval(MOI->getReg());
1090 for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) {
1091 unsigned Reg = OrigRegs[i];
1092 if (!TargetRegisterInfo::isVirtualRegister(Reg))
1095 LiveInterval &LI = getInterval(Reg);
1096 // FIXME: Should we support undefs that gain defs?
1097 if (!LI.hasAtLeastOneValue())
1100 LiveInterval::iterator LII = LI.find(endIdx);
1101 SlotIndex lastUseIdx;
1102 if (LII != LI.end() && LII->start < endIdx)
1103 lastUseIdx = LII->end;
1107 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1109 MachineInstr *MI = I;
1110 if (MI->isDebugValue())
1113 SlotIndex instrIdx = getInstructionIndex(MI);
1114 bool isStartValid = getInstructionFromIndex(LII->start);
1115 bool isEndValid = getInstructionFromIndex(LII->end);
1117 // FIXME: This doesn't currently handle early-clobber or multiple removed
1118 // defs inside of the region to repair.
1119 for (MachineInstr::mop_iterator OI = MI->operands_begin(),
1120 OE = MI->operands_end(); OI != OE; ++OI) {
1121 const MachineOperand &MO = *OI;
1122 if (!MO.isReg() || MO.getReg() != Reg)
1126 if (!isStartValid) {
1127 if (LII->end.isDead()) {
1128 SlotIndex prevStart;
1129 if (LII != LI.begin())
1130 prevStart = std::prev(LII)->start;
1132 // FIXME: This could be more efficient if there was a
1133 // removeSegment method that returned an iterator.
1134 LI.removeSegment(*LII, true);
1135 if (prevStart.isValid())
1136 LII = LI.find(prevStart);
1140 LII->start = instrIdx.getRegSlot();
1141 LII->valno->def = instrIdx.getRegSlot();
1142 if (MO.getSubReg() && !MO.isUndef())
1143 lastUseIdx = instrIdx.getRegSlot();
1145 lastUseIdx = SlotIndex();
1150 if (!lastUseIdx.isValid()) {
1151 VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
1153 LiveRange::Segment S(instrIdx.getRegSlot(),
1154 instrIdx.getDeadSlot(), VNI);
1155 LII = LI.addSegment(S);
1156 } else if (LII->start != instrIdx.getRegSlot()) {
1157 VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
1159 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1160 LII = LI.addSegment(S);
1163 if (MO.getSubReg() && !MO.isUndef())
1164 lastUseIdx = instrIdx.getRegSlot();
1166 lastUseIdx = SlotIndex();
1167 } else if (MO.isUse()) {
1168 // FIXME: This should probably be handled outside of this branch,
1169 // either as part of the def case (for defs inside of the region) or
1170 // after the loop over the region.
1171 if (!isEndValid && !LII->end.isBlock())
1172 LII->end = instrIdx.getRegSlot();
1173 if (!lastUseIdx.isValid())
1174 lastUseIdx = instrIdx.getRegSlot();