LLVM 17.0.0git
LiveIntervals.cpp
Go to the documentation of this file.
1//===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file This file implements the LiveInterval analysis pass which is used
10/// by the Linear Scan Register allocator. This pass linearizes the
11/// basic blocks of the function in DFS order and computes live intervals for
12/// each virtual and physical register.
13//
14//===----------------------------------------------------------------------===//
15
17#include "llvm/ADT/ArrayRef.h"
33#include "llvm/CodeGen/Passes.h"
39#include "llvm/Config/llvm-config.h"
40#include "llvm/IR/Statepoint.h"
41#include "llvm/MC/LaneBitmask.h"
43#include "llvm/Pass.h"
46#include "llvm/Support/Debug.h"
49#include <algorithm>
50#include <cassert>
51#include <cstdint>
52#include <iterator>
53#include <tuple>
54#include <utility>
55
56using namespace llvm;
57
58#define DEBUG_TYPE "regalloc"
59
60char LiveIntervals::ID = 0;
62INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", "Live Interval Analysis",
63 false, false)
68
69#ifndef NDEBUG
71 "precompute-phys-liveness", cl::Hidden,
72 cl::desc("Eagerly compute live intervals for all physreg units."));
73#else
74static bool EnablePrecomputePhysRegs = false;
75#endif // NDEBUG
76
77namespace llvm {
78
80 "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
82 "Use segment set for the computation of the live ranges of physregs."));
83
84} // end namespace llvm
85
87 AU.setPreservesCFG();
95}
96
99}
100
102
104 // Free the live intervals themselves.
105 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
106 delete VirtRegIntervals[Register::index2VirtReg(i)];
107 VirtRegIntervals.clear();
108 RegMaskSlots.clear();
109 RegMaskBits.clear();
110 RegMaskBlocks.clear();
111
112 for (LiveRange *LR : RegUnitRanges)
113 delete LR;
114 RegUnitRanges.clear();
115
116 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
117 VNInfoAllocator.Reset();
118}
119
121 MF = &fn;
122 MRI = &MF->getRegInfo();
123 TRI = MF->getSubtarget().getRegisterInfo();
124 TII = MF->getSubtarget().getInstrInfo();
125 Indexes = &getAnalysis<SlotIndexes>();
126 DomTree = &getAnalysis<MachineDominatorTree>();
127
128 if (!LICalc)
129 LICalc = new LiveIntervalCalc();
130
131 // Allocate space for all virtual registers.
132 VirtRegIntervals.resize(MRI->getNumVirtRegs());
133
134 computeVirtRegs();
135 computeRegMasks();
136 computeLiveInRegUnits();
137
139 // For stress testing, precompute live ranges of all physical register
140 // units, including reserved registers.
141 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
142 getRegUnit(i);
143 }
144 LLVM_DEBUG(dump());
145 return false;
146}
147
149 OS << "********** INTERVALS **********\n";
150
151 // Dump the regunits.
152 for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
153 if (LiveRange *LR = RegUnitRanges[Unit])
154 OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n';
155
156 // Dump the virtregs.
157 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
159 if (hasInterval(Reg))
160 OS << getInterval(Reg) << '\n';
161 }
162
163 OS << "RegMasks:";
164 for (SlotIndex Idx : RegMaskSlots)
165 OS << ' ' << Idx;
166 OS << '\n';
167
168 printInstrs(OS);
169}
170
171void LiveIntervals::printInstrs(raw_ostream &OS) const {
172 OS << "********** MACHINEINSTRS **********\n";
173 MF->print(OS, Indexes);
174}
175
176#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
177LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
178 printInstrs(dbgs());
179}
180#endif
181
182LiveInterval *LiveIntervals::createInterval(Register reg) {
183 float Weight = reg.isPhysical() ? huge_valf : 0.0F;
184 return new LiveInterval(reg, Weight);
185}
186
187/// Compute the live interval of a virtual register, based on defs and uses.
188bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
189 assert(LICalc && "LICalc not initialized.");
190 assert(LI.empty() && "Should only compute empty intervals.");
191 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
192 LICalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg()));
193 return computeDeadValues(LI, nullptr);
194}
195
196void LiveIntervals::computeVirtRegs() {
197 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
199 if (MRI->reg_nodbg_empty(Reg))
200 continue;
202 bool NeedSplit = computeVirtRegInterval(LI);
203 if (NeedSplit) {
205 splitSeparateComponents(LI, SplitLIs);
206 }
207 }
208}
209
210void LiveIntervals::computeRegMasks() {
211 RegMaskBlocks.resize(MF->getNumBlockIDs());
212
213 // Find all instructions with regmask operands.
214 for (const MachineBasicBlock &MBB : *MF) {
215 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
216 RMB.first = RegMaskSlots.size();
217
218 // Some block starts, such as EH funclets, create masks.
219 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
220 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
221 RegMaskBits.push_back(Mask);
222 }
223
224 // Unwinders may clobber additional registers.
225 // FIXME: This functionality can possibly be merged into
226 // MachineBasicBlock::getBeginClobberMask().
227 if (MBB.isEHPad())
228 if (auto *Mask = TRI->getCustomEHPadPreservedMask(*MBB.getParent())) {
229 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
230 RegMaskBits.push_back(Mask);
231 }
232
233 for (const MachineInstr &MI : MBB) {
234 for (const MachineOperand &MO : MI.operands()) {
235 if (!MO.isRegMask())
236 continue;
237 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
238 RegMaskBits.push_back(MO.getRegMask());
239 }
240 }
241
242 // Some block ends, such as funclet returns, create masks. Put the mask on
243 // the last instruction of the block, because MBB slot index intervals are
244 // half-open.
245 if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
246 assert(!MBB.empty() && "empty return block?");
247 RegMaskSlots.push_back(
248 Indexes->getInstructionIndex(MBB.back()).getRegSlot());
249 RegMaskBits.push_back(Mask);
250 }
251
252 // Compute the number of register mask instructions in this block.
253 RMB.second = RegMaskSlots.size() - RMB.first;
254 }
255}
256
257//===----------------------------------------------------------------------===//
258// Register Unit Liveness
259//===----------------------------------------------------------------------===//
260//
261// Fixed interference typically comes from ABI boundaries: Function arguments
262// and return values are passed in fixed registers, and so are exception
263// pointers entering landing pads. Certain instructions require values to be
264// present in specific registers. That is also represented through fixed
265// interference.
266//
267
268/// Compute the live range of a register unit, based on the uses and defs of
269/// aliasing registers. The range should be empty, or contain only dead
270/// phi-defs from ABI blocks.
271void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
272 assert(LICalc && "LICalc not initialized.");
273 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
274
275 // The physregs aliasing Unit are the roots and their super-registers.
276 // Create all values as dead defs before extending to uses. Note that roots
277 // may share super-registers. That's OK because createDeadDefs() is
278 // idempotent. It is very rare for a register unit to have multiple roots, so
279 // uniquing super-registers is probably not worthwhile.
280 bool IsReserved = false;
281 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
282 bool IsRootReserved = true;
283 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
284 Super.isValid(); ++Super) {
285 MCRegister Reg = *Super;
286 if (!MRI->reg_empty(Reg))
287 LICalc->createDeadDefs(LR, Reg);
288 // A register unit is considered reserved if all its roots and all their
289 // super registers are reserved.
290 if (!MRI->isReserved(Reg))
291 IsRootReserved = false;
292 }
293 IsReserved |= IsRootReserved;
294 }
295 assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
296 "reserved computation mismatch");
297
298 // Now extend LR to reach all uses.
299 // Ignore uses of reserved registers. We only track defs of those.
300 if (!IsReserved) {
301 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
302 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
303 Super.isValid(); ++Super) {
304 MCRegister Reg = *Super;
305 if (!MRI->reg_empty(Reg))
306 LICalc->extendToUses(LR, Reg);
307 }
308 }
309 }
310
311 // Flush the segment set to the segment vector.
313 LR.flushSegmentSet();
314}
315
316/// Precompute the live ranges of any register units that are live-in to an ABI
317/// block somewhere. Register values can appear without a corresponding def when
318/// entering the entry block or a landing pad.
319void LiveIntervals::computeLiveInRegUnits() {
320 RegUnitRanges.resize(TRI->getNumRegUnits());
321 LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
322
323 // Keep track of the live range sets allocated.
324 SmallVector<unsigned, 8> NewRanges;
325
326 // Check all basic blocks for live-ins.
327 for (const MachineBasicBlock &MBB : *MF) {
328 // We only care about ABI blocks: Entry + landing pads.
329 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
330 continue;
331
332 // Create phi-defs at Begin for all live-in registers.
333 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
334 LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
335 for (const auto &LI : MBB.liveins()) {
336 for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
337 unsigned Unit = *Units;
338 LiveRange *LR = RegUnitRanges[Unit];
339 if (!LR) {
340 // Use segment set to speed-up initial computation of the live range.
341 LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
342 NewRanges.push_back(Unit);
343 }
344 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
345 (void)VNI;
346 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
347 }
348 }
349 LLVM_DEBUG(dbgs() << '\n');
350 }
351 LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
352
353 // Compute the 'normal' part of the ranges.
354 for (unsigned Unit : NewRanges)
355 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
356}
357
360 for (VNInfo *VNI : VNIs) {
361 if (VNI->isUnused())
362 continue;
363 SlotIndex Def = VNI->def;
364 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
365 }
366}
367
368void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
369 ShrinkToUsesWorkList &WorkList,
370 Register Reg, LaneBitmask LaneMask) {
371 // Keep track of the PHIs that are in use.
373 // Blocks that have already been added to WorkList as live-out.
375
376 auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
377 -> const LiveRange& {
378 if (M.none())
379 return I;
380 for (const LiveInterval::SubRange &SR : I.subranges()) {
381 if ((SR.LaneMask & M).any()) {
382 assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
383 return SR;
384 }
385 }
386 llvm_unreachable("Subrange for mask not found");
387 };
388
389 const LiveInterval &LI = getInterval(Reg);
390 const LiveRange &OldRange = getSubRange(LI, LaneMask);
391
392 // Extend intervals to reach all uses in WorkList.
393 while (!WorkList.empty()) {
394 SlotIndex Idx = WorkList.back().first;
395 VNInfo *VNI = WorkList.back().second;
396 WorkList.pop_back();
397 const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
398 SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
399
400 // Extend the live range for VNI to be live at Idx.
401 if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
402 assert(ExtVNI == VNI && "Unexpected existing value number");
403 (void)ExtVNI;
404 // Is this a PHIDef we haven't seen before?
405 if (!VNI->isPHIDef() || VNI->def != BlockStart ||
406 !UsedPHIs.insert(VNI).second)
407 continue;
408 // The PHI is live, make sure the predecessors are live-out.
409 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
410 if (!LiveOut.insert(Pred).second)
411 continue;
412 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
413 // A predecessor is not required to have a live-out value for a PHI.
414 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
415 WorkList.push_back(std::make_pair(Stop, PVNI));
416 }
417 continue;
418 }
419
420 // VNI is live-in to MBB.
421 LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
422 Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
423
424 // Make sure VNI is live-out from the predecessors.
425 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
426 if (!LiveOut.insert(Pred).second)
427 continue;
428 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
429 if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
430 assert(OldVNI == VNI && "Wrong value out of predecessor");
431 (void)OldVNI;
432 WorkList.push_back(std::make_pair(Stop, VNI));
433 } else {
434#ifndef NDEBUG
435 // There was no old VNI. Verify that Stop is jointly dominated
436 // by <undef>s for this live range.
437 assert(LaneMask.any() &&
438 "Missing value out of predecessor for main range");
440 LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
441 assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
442 "Missing value out of predecessor for subrange");
443#endif
444 }
445 }
446 }
447}
448
451 LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
452 assert(li->reg().isVirtual() && "Can only shrink virtual registers");
453
454 // Shrink subregister live ranges.
455 bool NeedsCleanup = false;
456 for (LiveInterval::SubRange &S : li->subranges()) {
457 shrinkToUses(S, li->reg());
458 if (S.empty())
459 NeedsCleanup = true;
460 }
461 if (NeedsCleanup)
463
464 // Find all the values used, including PHI kills.
465 ShrinkToUsesWorkList WorkList;
466
467 // Visit all instructions reading li->reg().
468 Register Reg = li->reg();
469 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
470 if (UseMI.isDebugInstr() || !UseMI.readsVirtualRegister(Reg))
471 continue;
473 LiveQueryResult LRQ = li->Query(Idx);
474 VNInfo *VNI = LRQ.valueIn();
475 if (!VNI) {
476 // This shouldn't happen: readsVirtualRegister returns true, but there is
477 // no live value. It is likely caused by a target getting <undef> flags
478 // wrong.
480 dbgs() << Idx << '\t' << UseMI
481 << "Warning: Instr claims to read non-existent value in "
482 << *li << '\n');
483 continue;
484 }
485 // Special case: An early-clobber tied operand reads and writes the
486 // register one slot early.
487 if (VNInfo *DefVNI = LRQ.valueDefined())
488 Idx = DefVNI->def;
489
490 WorkList.push_back(std::make_pair(Idx, VNI));
491 }
492
493 // Create new live ranges with only minimal live segments per def.
494 LiveRange NewLR;
495 createSegmentsForValues(NewLR, li->vnis());
496 extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
497
498 // Move the trimmed segments back.
499 li->segments.swap(NewLR.segments);
500
501 // Handle dead values.
502 bool CanSeparate = computeDeadValues(*li, dead);
503 LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
504 return CanSeparate;
505}
506
507bool LiveIntervals::computeDeadValues(LiveInterval &LI,
509 bool MayHaveSplitComponents = false;
510
511 for (VNInfo *VNI : LI.valnos) {
512 if (VNI->isUnused())
513 continue;
514 SlotIndex Def = VNI->def;
516 assert(I != LI.end() && "Missing segment for VNI");
517
518 // Is the register live before? Otherwise we may have to add a read-undef
519 // flag for subregister defs.
520 Register VReg = LI.reg();
521 if (MRI->shouldTrackSubRegLiveness(VReg)) {
522 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
524 MI->setRegisterDefReadUndef(VReg);
525 }
526 }
527
528 if (I->end != Def.getDeadSlot())
529 continue;
530 if (VNI->isPHIDef()) {
531 // This is a dead PHI. Remove it.
532 VNI->markUnused();
533 LI.removeSegment(I);
534 LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
535 } else {
536 // This is a dead def. Make sure the instruction knows.
538 assert(MI && "No instruction defining live value");
539 MI->addRegisterDead(LI.reg(), TRI);
540
541 if (dead && MI->allDefsAreDead()) {
542 LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
543 dead->push_back(MI);
544 }
545 }
546 MayHaveSplitComponents = true;
547 }
548 return MayHaveSplitComponents;
549}
550
552 LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
553 assert(Reg.isVirtual() && "Can only shrink virtual registers");
554 // Find all the values used, including PHI kills.
555 ShrinkToUsesWorkList WorkList;
556
557 // Visit all instructions reading Reg.
558 SlotIndex LastIdx;
559 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
560 // Skip "undef" uses.
561 if (!MO.readsReg())
562 continue;
563 // Maybe the operand is for a subregister we don't care about.
564 unsigned SubReg = MO.getSubReg();
565 if (SubReg != 0) {
567 if ((LaneMask & SR.LaneMask).none())
568 continue;
569 }
570 // We only need to visit each instruction once.
571 MachineInstr *UseMI = MO.getParent();
573 if (Idx == LastIdx)
574 continue;
575 LastIdx = Idx;
576
577 LiveQueryResult LRQ = SR.Query(Idx);
578 VNInfo *VNI = LRQ.valueIn();
579 // For Subranges it is possible that only undef values are left in that
580 // part of the subregister, so there is no real liverange at the use
581 if (!VNI)
582 continue;
583
584 // Special case: An early-clobber tied operand reads and writes the
585 // register one slot early.
586 if (VNInfo *DefVNI = LRQ.valueDefined())
587 Idx = DefVNI->def;
588
589 WorkList.push_back(std::make_pair(Idx, VNI));
590 }
591
592 // Create a new live ranges with only minimal live segments per def.
593 LiveRange NewLR;
594 createSegmentsForValues(NewLR, SR.vnis());
595 extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
596
597 // Move the trimmed ranges back.
598 SR.segments.swap(NewLR.segments);
599
600 // Remove dead PHI value numbers
601 for (VNInfo *VNI : SR.valnos) {
602 if (VNI->isUnused())
603 continue;
604 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
605 assert(Segment != nullptr && "Missing segment for VNI");
606 if (Segment->end != VNI->def.getDeadSlot())
607 continue;
608 if (VNI->isPHIDef()) {
609 // This is a dead PHI. Remove it.
610 LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
611 << " may separate interval\n");
612 VNI->markUnused();
613 SR.removeSegment(*Segment);
614 }
615 }
616
617 LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
618}
619
621 ArrayRef<SlotIndex> Indices,
622 ArrayRef<SlotIndex> Undefs) {
623 assert(LICalc && "LICalc not initialized.");
624 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
625 for (SlotIndex Idx : Indices)
626 LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
627}
628
630 SmallVectorImpl<SlotIndex> *EndPoints) {
631 LiveQueryResult LRQ = LR.Query(Kill);
632 VNInfo *VNI = LRQ.valueOutOrDead();
633 if (!VNI)
634 return;
635
636 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
637 SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
638
639 // If VNI isn't live out from KillMBB, the value is trivially pruned.
640 if (LRQ.endPoint() < MBBEnd) {
641 LR.removeSegment(Kill, LRQ.endPoint());
642 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
643 return;
644 }
645
646 // VNI is live out of KillMBB.
647 LR.removeSegment(Kill, MBBEnd);
648 if (EndPoints) EndPoints->push_back(MBBEnd);
649
650 // Find all blocks that are reachable from KillMBB without leaving VNI's live
651 // range. It is possible that KillMBB itself is reachable, so start a DFS
652 // from each successor.
654 VisitedTy Visited;
655 for (MachineBasicBlock *Succ : KillMBB->successors()) {
657 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
658 I != E;) {
660
661 // Check if VNI is live in to MBB.
662 SlotIndex MBBStart, MBBEnd;
663 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
664 LiveQueryResult LRQ = LR.Query(MBBStart);
665 if (LRQ.valueIn() != VNI) {
666 // This block isn't part of the VNI segment. Prune the search.
667 I.skipChildren();
668 continue;
669 }
670
671 // Prune the search if VNI is killed in MBB.
672 if (LRQ.endPoint() < MBBEnd) {
673 LR.removeSegment(MBBStart, LRQ.endPoint());
674 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
675 I.skipChildren();
676 continue;
677 }
678
679 // VNI is live through MBB.
680 LR.removeSegment(MBBStart, MBBEnd);
681 if (EndPoints) EndPoints->push_back(MBBEnd);
682 ++I;
683 }
684 }
685}
686
687//===----------------------------------------------------------------------===//
688// Register allocator hooks.
689//
690
692 // Keep track of regunit ranges.
694
695 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
697 if (MRI->reg_nodbg_empty(Reg))
698 continue;
699 const LiveInterval &LI = getInterval(Reg);
700 if (LI.empty())
701 continue;
702
703 // Target may have not allocated this yet.
704 Register PhysReg = VRM->getPhys(Reg);
705 if (!PhysReg)
706 continue;
707
708 // Find the regunit intervals for the assigned register. They may overlap
709 // the virtual register live range, cancelling any kills.
710 RU.clear();
711 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid();
712 ++Unit) {
713 const LiveRange &RURange = getRegUnit(*Unit);
714 if (RURange.empty())
715 continue;
716 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
717 }
718 // Every instruction that kills Reg corresponds to a segment range end
719 // point.
720 for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
721 ++RI) {
722 // A block index indicates an MBB edge.
723 if (RI->end.isBlock())
724 continue;
726 if (!MI)
727 continue;
728
729 // Check if any of the regunits are live beyond the end of RI. That could
730 // happen when a physreg is defined as a copy of a virtreg:
731 //
732 // %eax = COPY %5
733 // FOO %5 <--- MI, cancel kill because %eax is live.
734 // BAR killed %eax
735 //
736 // There should be no kill flag on FOO when %5 is rewritten as %eax.
737 for (auto &RUP : RU) {
738 const LiveRange &RURange = *RUP.first;
739 LiveRange::const_iterator &I = RUP.second;
740 if (I == RURange.end())
741 continue;
742 I = RURange.advanceTo(I, RI->end);
743 if (I == RURange.end() || I->start >= RI->end)
744 continue;
745 // I is overlapping RI.
746 goto CancelKill;
747 }
748
749 if (MRI->subRegLivenessEnabled()) {
750 // When reading a partial undefined value we must not add a kill flag.
751 // The regalloc might have used the undef lane for something else.
752 // Example:
753 // %1 = ... ; R32: %1
754 // %2:high16 = ... ; R64: %2
755 // = read killed %2 ; R64: %2
756 // = read %1 ; R32: %1
757 // The <kill> flag is correct for %2, but the register allocator may
758 // assign R0L to %1, and R0 to %2 because the low 32bits of R0
759 // are actually never written by %2. After assignment the <kill>
760 // flag at the read instruction is invalid.
761 LaneBitmask DefinedLanesMask;
762 if (LI.hasSubRanges()) {
763 // Compute a mask of lanes that are defined.
764 DefinedLanesMask = LaneBitmask::getNone();
765 for (const LiveInterval::SubRange &SR : LI.subranges())
766 for (const LiveRange::Segment &Segment : SR.segments) {
767 if (Segment.start >= RI->end)
768 break;
769 if (Segment.end == RI->end) {
770 DefinedLanesMask |= SR.LaneMask;
771 break;
772 }
773 }
774 } else
775 DefinedLanesMask = LaneBitmask::getAll();
776
777 bool IsFullWrite = false;
778 for (const MachineOperand &MO : MI->operands()) {
779 if (!MO.isReg() || MO.getReg() != Reg)
780 continue;
781 if (MO.isUse()) {
782 // Reading any undefined lanes?
783 unsigned SubReg = MO.getSubReg();
785 : MRI->getMaxLaneMaskForVReg(Reg);
786 if ((UseMask & ~DefinedLanesMask).any())
787 goto CancelKill;
788 } else if (MO.getSubReg() == 0) {
789 // Writing to the full register?
790 assert(MO.isDef());
791 IsFullWrite = true;
792 }
793 }
794
795 // If an instruction writes to a subregister, a new segment starts in
796 // the LiveInterval. But as this is only overriding part of the register
797 // adding kill-flags is not correct here after registers have been
798 // assigned.
799 if (!IsFullWrite) {
800 // Next segment has to be adjacent in the subregister write case.
801 LiveRange::const_iterator N = std::next(RI);
802 if (N != LI.end() && N->start == RI->end)
803 goto CancelKill;
804 }
805 }
806
807 MI->addRegisterKilled(Reg, nullptr);
808 continue;
809CancelKill:
810 MI->clearRegisterKills(Reg, nullptr);
811 }
812 }
813}
814
817 assert(!LI.empty() && "LiveInterval is empty.");
818
819 // A local live range must be fully contained inside the block, meaning it is
820 // defined and killed at instructions, not at block boundaries. It is not
821 // live in or out of any block.
822 //
823 // It is technically possible to have a PHI-defined live range identical to a
824 // single block, but we are going to return false in that case.
825
826 SlotIndex Start = LI.beginIndex();
827 if (Start.isBlock())
828 return nullptr;
829
830 SlotIndex Stop = LI.endIndex();
831 if (Stop.isBlock())
832 return nullptr;
833
834 // getMBBFromIndex doesn't need to search the MBB table when both indexes
835 // belong to proper instructions.
836 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
837 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
838 return MBB1 == MBB2 ? MBB1 : nullptr;
839}
840
841bool
842LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
843 for (const VNInfo *PHI : LI.valnos) {
844 if (PHI->isUnused() || !PHI->isPHIDef())
845 continue;
846 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
847 // Conservatively return true instead of scanning huge predecessor lists.
848 if (PHIMBB->pred_size() > 100)
849 return true;
850 for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
851 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
852 return true;
853 }
854 return false;
855}
856
857float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
858 const MachineBlockFrequencyInfo *MBFI,
859 const MachineInstr &MI) {
860 return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
861}
862
863float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
864 const MachineBlockFrequencyInfo *MBFI,
865 const MachineBasicBlock *MBB) {
866 return (isDef + isUse) * MBFI->getBlockFreqRelativeToEntryBlock(MBB);
867}
868
872 VNInfo *VN = Interval.getNextValue(
873 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
875 LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
876 getMBBEndIdx(startInst.getParent()), VN);
877 Interval.addSegment(S);
878
879 return S;
880}
881
882//===----------------------------------------------------------------------===//
883// Register mask functions
884//===----------------------------------------------------------------------===//
885/// Check whether use of reg in MI is live-through. Live-through means that
886/// the value is alive on exit from Machine instruction. The example of such
887/// use is a deopt value in statepoint instruction.
888static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg) {
889 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
890 return false;
893 return false;
894 for (unsigned Idx = SO.getNumDeoptArgsIdx(), E = SO.getNumGCPtrIdx(); Idx < E;
895 ++Idx) {
896 const MachineOperand &MO = MI->getOperand(Idx);
897 if (MO.isReg() && MO.getReg() == Reg)
898 return true;
899 }
900 return false;
901}
902
904 BitVector &UsableRegs) {
905 if (LI.empty())
906 return false;
907 LiveInterval::const_iterator LiveI = LI.begin(), LiveE = LI.end();
908
909 // Use a smaller arrays for local live ranges.
915 } else {
916 Slots = getRegMaskSlots();
917 Bits = getRegMaskBits();
918 }
919
920 // We are going to enumerate all the register mask slots contained in LI.
921 // Start with a binary search of RegMaskSlots to find a starting point.
922 ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);
923 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
924
925 // No slots in range, LI begins after the last call.
926 if (SlotI == SlotE)
927 return false;
928
929 bool Found = false;
930 // Utility to union regmasks.
931 auto unionBitMask = [&](unsigned Idx) {
932 if (!Found) {
933 // This is the first overlap. Initialize UsableRegs to all ones.
934 UsableRegs.clear();
935 UsableRegs.resize(TRI->getNumRegs(), true);
936 Found = true;
937 }
938 // Remove usable registers clobbered by this mask.
939 UsableRegs.clearBitsNotInMask(Bits[Idx]);
940 };
941 while (true) {
942 assert(*SlotI >= LiveI->start);
943 // Loop over all slots overlapping this segment.
944 while (*SlotI < LiveI->end) {
945 // *SlotI overlaps LI. Collect mask bits.
946 unionBitMask(SlotI - Slots.begin());
947 if (++SlotI == SlotE)
948 return Found;
949 }
950 // If segment ends with live-through use we need to collect its regmask.
951 if (*SlotI == LiveI->end)
953 if (hasLiveThroughUse(MI, LI.reg()))
954 unionBitMask(SlotI++ - Slots.begin());
955 // *SlotI is beyond the current LI segment.
956 // Special advance implementation to not miss next LiveI->end.
957 if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.endIndex())
958 return Found;
959 while (LiveI->end < *SlotI)
960 ++LiveI;
961 // Advance SlotI until it overlaps.
962 while (*SlotI < LiveI->start)
963 if (++SlotI == SlotE)
964 return Found;
965 }
966}
967
968//===----------------------------------------------------------------------===//
969// IntervalUpdate class.
970//===----------------------------------------------------------------------===//
971
972/// Toolkit used by handleMove to trim or extend live intervals.
974private:
975 LiveIntervals& LIS;
977 const TargetRegisterInfo& TRI;
978 SlotIndex OldIdx;
979 SlotIndex NewIdx;
981 bool UpdateFlags;
982
983public:
985 const TargetRegisterInfo& TRI,
986 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
987 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
988 UpdateFlags(UpdateFlags) {}
989
990 // FIXME: UpdateFlags is a workaround that creates live intervals for all
991 // physregs, even those that aren't needed for regalloc, in order to update
992 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
993 // flags, and postRA passes will use a live register utility instead.
994 LiveRange *getRegUnitLI(unsigned Unit) {
995 if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
996 return &LIS.getRegUnit(Unit);
997 return LIS.getCachedRegUnit(Unit);
998 }
999
1000 /// Update all live ranges touched by MI, assuming a move from OldIdx to
1001 /// NewIdx.
1003 LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
1004 << *MI);
1005 bool hasRegMask = false;
1006 for (MachineOperand &MO : MI->operands()) {
1007 if (MO.isRegMask())
1008 hasRegMask = true;
1009 if (!MO.isReg())
1010 continue;
1011 if (MO.isUse()) {
1012 if (!MO.readsReg())
1013 continue;
1014 // Aggressively clear all kill flags.
1015 // They are reinserted by VirtRegRewriter.
1016 MO.setIsKill(false);
1017 }
1018
1019 Register Reg = MO.getReg();
1020 if (!Reg)
1021 continue;
1022 if (Reg.isVirtual()) {
1023 LiveInterval &LI = LIS.getInterval(Reg);
1024 if (LI.hasSubRanges()) {
1025 unsigned SubReg = MO.getSubReg();
1026 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
1027 : MRI.getMaxLaneMaskForVReg(Reg);
1028 for (LiveInterval::SubRange &S : LI.subranges()) {
1029 if ((S.LaneMask & LaneMask).none())
1030 continue;
1031 updateRange(S, Reg, S.LaneMask);
1032 }
1033 }
1034 updateRange(LI, Reg, LaneBitmask::getNone());
1035 // If main range has a hole and we are moving a subrange use across
1036 // the hole updateRange() cannot properly handle it since it only
1037 // gets the LiveRange and not the whole LiveInterval. As a result
1038 // we may end up with a main range not covering all subranges.
1039 // This is extremely rare case, so let's check and reconstruct the
1040 // main range.
1041 if (LI.hasSubRanges()) {
1042 unsigned SubReg = MO.getSubReg();
1043 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
1044 : MRI.getMaxLaneMaskForVReg(Reg);
1045 for (LiveInterval::SubRange &S : LI.subranges()) {
1046 if ((S.LaneMask & LaneMask).none() || LI.covers(S))
1047 continue;
1048 LI.clear();
1050 break;
1051 }
1052 }
1053
1054 continue;
1055 }
1056
1057 // For physregs, only update the regunits that actually have a
1058 // precomputed live range.
1059 for (MCRegUnitIterator Units(Reg.asMCReg(), &TRI); Units.isValid();
1060 ++Units)
1061 if (LiveRange *LR = getRegUnitLI(*Units))
1062 updateRange(*LR, *Units, LaneBitmask::getNone());
1063 }
1064 if (hasRegMask)
1065 updateRegMaskSlots();
1066 }
1067
1068private:
1069 /// Update a single live range, assuming an instruction has been moved from
1070 /// OldIdx to NewIdx.
1071 void updateRange(LiveRange &LR, Register Reg, LaneBitmask LaneMask) {
1072 if (!Updated.insert(&LR).second)
1073 return;
1074 LLVM_DEBUG({
1075 dbgs() << " ";
1076 if (Reg.isVirtual()) {
1077 dbgs() << printReg(Reg);
1078 if (LaneMask.any())
1079 dbgs() << " L" << PrintLaneMask(LaneMask);
1080 } else {
1081 dbgs() << printRegUnit(Reg, &TRI);
1082 }
1083 dbgs() << ":\t" << LR << '\n';
1084 });
1085 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1086 handleMoveDown(LR);
1087 else
1088 handleMoveUp(LR, Reg, LaneMask);
1089 LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');
1090 LR.verify();
1091 }
1092
1093 /// Update LR to reflect an instruction has been moved downwards from OldIdx
1094 /// to NewIdx (OldIdx < NewIdx).
1095 void handleMoveDown(LiveRange &LR) {
1096 LiveRange::iterator E = LR.end();
1097 // Segment going into OldIdx.
1098 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1099
1100 // No value live before or after OldIdx? Nothing to do.
1101 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1102 return;
1103
1104 LiveRange::iterator OldIdxOut;
1105 // Do we have a value live-in to OldIdx?
1106 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1107 // If the live-in value already extends to NewIdx, there is nothing to do.
1108 if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1109 return;
1110 // Aggressively remove all kill flags from the old kill point.
1111 // Kill flags shouldn't be used while live intervals exist, they will be
1112 // reinserted by VirtRegRewriter.
1113 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1114 for (MachineOperand &MOP : mi_bundle_ops(*KillMI))
1115 if (MOP.isReg() && MOP.isUse())
1116 MOP.setIsKill(false);
1117
1118 // Is there a def before NewIdx which is not OldIdx?
1119 LiveRange::iterator Next = std::next(OldIdxIn);
1120 if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
1121 SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1122 // If we are here then OldIdx was just a use but not a def. We only have
1123 // to ensure liveness extends to NewIdx.
1124 LiveRange::iterator NewIdxIn =
1125 LR.advanceTo(Next, NewIdx.getBaseIndex());
1126 // Extend the segment before NewIdx if necessary.
1127 if (NewIdxIn == E ||
1128 !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
1129 LiveRange::iterator Prev = std::prev(NewIdxIn);
1130 Prev->end = NewIdx.getRegSlot();
1131 }
1132 // Extend OldIdxIn.
1133 OldIdxIn->end = Next->start;
1134 return;
1135 }
1136
1137 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1138 // invalid by overlapping ranges.
1139 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1140 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1141 // If this was not a kill, then there was no def and we're done.
1142 if (!isKill)
1143 return;
1144
1145 // Did we have a Def at OldIdx?
1146 OldIdxOut = Next;
1147 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1148 return;
1149 } else {
1150 OldIdxOut = OldIdxIn;
1151 }
1152
1153 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1154 // to the segment starting there.
1155 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1156 "No def?");
1157 VNInfo *OldIdxVNI = OldIdxOut->valno;
1158 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1159
1160 // If the defined value extends beyond NewIdx, just move the beginning
1161 // of the segment to NewIdx.
1162 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1163 if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1164 OldIdxVNI->def = NewIdxDef;
1165 OldIdxOut->start = OldIdxVNI->def;
1166 return;
1167 }
1168
1169 // If we are here then we have a Definition at OldIdx which ends before
1170 // NewIdx.
1171
1172 // Is there an existing Def at NewIdx?
1173 LiveRange::iterator AfterNewIdx
1174 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1175 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1176 if (!OldIdxDefIsDead &&
1177 SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
1178 // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1179 VNInfo *DefVNI;
1180 if (OldIdxOut != LR.begin() &&
1181 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1182 OldIdxOut->start)) {
1183 // There is no gap between OldIdxOut and its predecessor anymore,
1184 // merge them.
1185 LiveRange::iterator IPrev = std::prev(OldIdxOut);
1186 DefVNI = OldIdxVNI;
1187 IPrev->end = OldIdxOut->end;
1188 } else {
1189 // The value is live in to OldIdx
1190 LiveRange::iterator INext = std::next(OldIdxOut);
1191 assert(INext != E && "Must have following segment");
1192 // We merge OldIdxOut and its successor. As we're dealing with subreg
1193 // reordering, there is always a successor to OldIdxOut in the same BB
1194 // We don't need INext->valno anymore and will reuse for the new segment
1195 // we create later.
1196 DefVNI = OldIdxVNI;
1197 INext->start = OldIdxOut->end;
1198 INext->valno->def = INext->start;
1199 }
1200 // If NewIdx is behind the last segment, extend that and append a new one.
1201 if (AfterNewIdx == E) {
1202 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1203 // one position.
1204 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1205 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1206 std::copy(std::next(OldIdxOut), E, OldIdxOut);
1207 // The last segment is undefined now, reuse it for a dead def.
1208 LiveRange::iterator NewSegment = std::prev(E);
1209 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1210 DefVNI);
1211 DefVNI->def = NewIdxDef;
1212
1213 LiveRange::iterator Prev = std::prev(NewSegment);
1214 Prev->end = NewIdxDef;
1215 } else {
1216 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1217 // one position.
1218 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1219 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1220 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1221 LiveRange::iterator Prev = std::prev(AfterNewIdx);
1222 // We have two cases:
1223 if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1224 // Case 1: NewIdx is inside a liverange. Split this liverange at
1225 // NewIdxDef into the segment "Prev" followed by "NewSegment".
1226 LiveRange::iterator NewSegment = AfterNewIdx;
1227 *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1228 Prev->valno->def = NewIdxDef;
1229
1230 *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1231 DefVNI->def = Prev->start;
1232 } else {
1233 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1234 // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1235 *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1236 DefVNI->def = NewIdxDef;
1237 assert(DefVNI != AfterNewIdx->valno);
1238 }
1239 }
1240 return;
1241 }
1242
1243 if (AfterNewIdx != E &&
1244 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
1245 // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1246 // that value.
1247 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1248 LR.removeValNo(OldIdxVNI);
1249 } else {
1250 // There was no existing def at NewIdx. We need to create a dead def
1251 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1252 // a new segment at the place where we want to construct the dead def.
1253 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1254 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1255 assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1256 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1257 // We can reuse OldIdxVNI now.
1258 LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1259 VNInfo *NewSegmentVNI = OldIdxVNI;
1260 NewSegmentVNI->def = NewIdxDef;
1261 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1262 NewSegmentVNI);
1263 }
1264 }
1265
1266 /// Update LR to reflect an instruction has been moved upwards from OldIdx
1267 /// to NewIdx (NewIdx < OldIdx).
1268 void handleMoveUp(LiveRange &LR, Register Reg, LaneBitmask LaneMask) {
1269 LiveRange::iterator E = LR.end();
1270 // Segment going into OldIdx.
1271 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1272
1273 // No value live before or after OldIdx? Nothing to do.
1274 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1275 return;
1276
1277 LiveRange::iterator OldIdxOut;
1278 // Do we have a value live-in to OldIdx?
1279 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1280 // If the live-in value isn't killed here, then we have no Def at
1281 // OldIdx, moreover the value must be live at NewIdx so there is nothing
1282 // to do.
1283 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1284 if (!isKill)
1285 return;
1286
1287 // At this point we have to move OldIdxIn->end back to the nearest
1288 // previous use or (dead-)def but no further than NewIdx.
1289 SlotIndex DefBeforeOldIdx
1290 = std::max(OldIdxIn->start.getDeadSlot(),
1291 NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1292 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1293
1294 // Did we have a Def at OldIdx? If not we are done now.
1295 OldIdxOut = std::next(OldIdxIn);
1296 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1297 return;
1298 } else {
1299 OldIdxOut = OldIdxIn;
1300 OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
1301 }
1302
1303 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1304 // to the segment starting there.
1305 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1306 "No def?");
1307 VNInfo *OldIdxVNI = OldIdxOut->valno;
1308 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1309 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1310
1311 // Is there an existing def at NewIdx?
1312 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1313 LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1314 if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1315 assert(NewIdxOut->valno != OldIdxVNI &&
1316 "Same value defined more than once?");
1317 // If OldIdx was a dead def remove it.
1318 if (!OldIdxDefIsDead) {
1319 // Remove segment starting at NewIdx and move begin of OldIdxOut to
1320 // NewIdx so it can take its place.
1321 OldIdxVNI->def = NewIdxDef;
1322 OldIdxOut->start = NewIdxDef;
1323 LR.removeValNo(NewIdxOut->valno);
1324 } else {
1325 // Simply remove the dead def at OldIdx.
1326 LR.removeValNo(OldIdxVNI);
1327 }
1328 } else {
1329 // Previously nothing was live after NewIdx, so all we have to do now is
1330 // move the begin of OldIdxOut to NewIdx.
1331 if (!OldIdxDefIsDead) {
1332 // Do we have any intermediate Defs between OldIdx and NewIdx?
1333 if (OldIdxIn != E &&
1334 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1335 // OldIdx is not a dead def and NewIdx is before predecessor start.
1336 LiveRange::iterator NewIdxIn = NewIdxOut;
1337 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1338 const SlotIndex SplitPos = NewIdxDef;
1339 OldIdxVNI = OldIdxIn->valno;
1340
1341 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1342 LiveRange::iterator Prev = std::prev(OldIdxIn);
1343 if (OldIdxIn != LR.begin() &&
1344 SlotIndex::isEarlierInstr(NewIdx, Prev->end)) {
1345 // If the segment before OldIdx read a value defined earlier than
1346 // NewIdx, the moved instruction also reads and forwards that
1347 // value. Extend the lifetime of the new def point.
1348
1349 // Extend to where the previous range started, unless there is
1350 // another redef first.
1351 NewDefEndPoint = std::min(OldIdxIn->start,
1352 std::next(NewIdxOut)->start);
1353 }
1354
1355 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1356 OldIdxOut->valno->def = OldIdxIn->start;
1357 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1358 OldIdxOut->valno);
1359 // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1360 // We Slide [NewIdxIn, OldIdxIn) down one position.
1361 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1362 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1363 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1364 // NewIdxIn is now considered undef so we can reuse it for the moved
1365 // value.
1366 LiveRange::iterator NewSegment = NewIdxIn;
1367 LiveRange::iterator Next = std::next(NewSegment);
1368 if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1369 // There is no gap between NewSegment and its predecessor.
1370 *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1371 Next->valno);
1372
1373 *Next = LiveRange::Segment(SplitPos, NewDefEndPoint, OldIdxVNI);
1374 Next->valno->def = SplitPos;
1375 } else {
1376 // There is a gap between NewSegment and its predecessor
1377 // Value becomes live in.
1378 *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1379 NewSegment->valno->def = SplitPos;
1380 }
1381 } else {
1382 // Leave the end point of a live def.
1383 OldIdxOut->start = NewIdxDef;
1384 OldIdxVNI->def = NewIdxDef;
1385 if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
1386 OldIdxIn->end = NewIdxDef;
1387 }
1388 } else if (OldIdxIn != E
1389 && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)
1390 && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {
1391 // OldIdxVNI is a dead def that has been moved into the middle of
1392 // another value in LR. That can happen when LR is a whole register,
1393 // but the dead def is a write to a subreg that is dead at NewIdx.
1394 // The dead def may have been moved across other values
1395 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1396 // down one position.
1397 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1398 // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1399 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1400 // Modify the segment at NewIdxOut and the following segment to meet at
1401 // the point of the dead def, with the following segment getting
1402 // OldIdxVNI as its value number.
1403 *NewIdxOut = LiveRange::Segment(
1404 NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
1405 *(NewIdxOut + 1) = LiveRange::Segment(
1406 NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1407 OldIdxVNI->def = NewIdxDef;
1408 // Modify subsequent segments to be defined by the moved def OldIdxVNI.
1409 for (auto *Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)
1410 Idx->valno = OldIdxVNI;
1411 // Aggressively remove all dead flags from the former dead definition.
1412 // Kill/dead flags shouldn't be used while live intervals exist; they
1413 // will be reinserted by VirtRegRewriter.
1414 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
1415 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1416 if (MO->isReg() && !MO->isUse())
1417 MO->setIsDead(false);
1418 } else {
1419 // OldIdxVNI is a dead def. It may have been moved across other values
1420 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1421 // down one position.
1422 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1423 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1424 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1425 // OldIdxVNI can be reused now to build a new dead def segment.
1426 LiveRange::iterator NewSegment = NewIdxOut;
1427 VNInfo *NewSegmentVNI = OldIdxVNI;
1428 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1429 NewSegmentVNI);
1430 NewSegmentVNI->def = NewIdxDef;
1431 }
1432 }
1433 }
1434
1435 void updateRegMaskSlots() {
1437 llvm::lower_bound(LIS.RegMaskSlots, OldIdx);
1438 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1439 "No RegMask at OldIdx.");
1440 *RI = NewIdx.getRegSlot();
1441 assert((RI == LIS.RegMaskSlots.begin() ||
1442 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1443 "Cannot move regmask instruction above another call");
1444 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1445 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1446 "Cannot move regmask instruction below another call");
1447 }
1448
1449 // Return the last use of reg between NewIdx and OldIdx.
1450 SlotIndex findLastUseBefore(SlotIndex Before, Register Reg,
1451 LaneBitmask LaneMask) {
1452 if (Reg.isVirtual()) {
1453 SlotIndex LastUse = Before;
1454 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1455 if (MO.isUndef())
1456 continue;
1457 unsigned SubReg = MO.getSubReg();
1458 if (SubReg != 0 && LaneMask.any()
1459 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1460 continue;
1461
1462 const MachineInstr &MI = *MO.getParent();
1464 if (InstSlot > LastUse && InstSlot < OldIdx)
1465 LastUse = InstSlot.getRegSlot();
1466 }
1467 return LastUse;
1468 }
1469
1470 // This is a regunit interval, so scanning the use list could be very
1471 // expensive. Scan upwards from OldIdx instead.
1472 assert(Before < OldIdx && "Expected upwards move");
1473 SlotIndexes *Indexes = LIS.getSlotIndexes();
1474 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
1475
1476 // OldIdx may not correspond to an instruction any longer, so set MII to
1477 // point to the next instruction after OldIdx, or MBB->end().
1479 if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1480 Indexes->getNextNonNullIndex(OldIdx)))
1481 if (MI->getParent() == MBB)
1482 MII = MI;
1483
1485 while (MII != Begin) {
1486 if ((--MII)->isDebugOrPseudoInstr())
1487 continue;
1488 SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1489
1490 // Stop searching when Before is reached.
1491 if (!SlotIndex::isEarlierInstr(Before, Idx))
1492 return Before;
1493
1494 // Check if MII uses Reg.
1495 for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
1496 if (MO->isReg() && !MO->isUndef() && MO->getReg().isPhysical() &&
1497 TRI.hasRegUnit(MO->getReg(), Reg))
1498 return Idx.getRegSlot();
1499 }
1500 // Didn't reach Before. It must be the first instruction in the block.
1501 return Before;
1502 }
1503};
1504
1506 // It is fine to move a bundle as a whole, but not an individual instruction
1507 // inside it.
1508 assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) &&
1509 "Cannot move instruction in bundle");
1510 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1512 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1513 assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1514 OldIndex < getMBBEndIdx(MI.getParent()) &&
1515 "Cannot handle moves across basic block boundaries.");
1516
1517 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1518 HME.updateAllRanges(&MI);
1519}
1520
1522 bool UpdateFlags) {
1523 assert((BundleStart.getOpcode() == TargetOpcode::BUNDLE) &&
1524 "Bundle start is not a bundle");
1526 const SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(BundleStart);
1527 auto BundleEnd = getBundleEnd(BundleStart.getIterator());
1528
1529 auto I = BundleStart.getIterator();
1530 I++;
1531 while (I != BundleEnd) {
1532 if (!Indexes->hasIndex(*I))
1533 continue;
1534 SlotIndex OldIndex = Indexes->getInstructionIndex(*I, true);
1535 ToProcess.push_back(OldIndex);
1536 Indexes->removeMachineInstrFromMaps(*I, true);
1537 I++;
1538 }
1539 for (SlotIndex OldIndex : ToProcess) {
1540 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1541 HME.updateAllRanges(&BundleStart);
1542 }
1543
1544 // Fix up dead defs
1545 const SlotIndex Index = getInstructionIndex(BundleStart);
1546 for (unsigned Idx = 0, E = BundleStart.getNumOperands(); Idx != E; ++Idx) {
1547 MachineOperand &MO = BundleStart.getOperand(Idx);
1548 if (!MO.isReg())
1549 continue;
1550 Register Reg = MO.getReg();
1551 if (Reg.isVirtual() && hasInterval(Reg) && !MO.isUndef()) {
1552 LiveInterval &LI = getInterval(Reg);
1553 LiveQueryResult LRQ = LI.Query(Index);
1554 if (LRQ.isDeadDef())
1555 MO.setIsDead();
1556 }
1557 }
1558}
1559
1560void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1562 const SlotIndex EndIdx, LiveRange &LR,
1563 const Register Reg,
1564 LaneBitmask LaneMask) {
1565 LiveInterval::iterator LII = LR.find(EndIdx);
1566 SlotIndex lastUseIdx;
1567 if (LII != LR.end() && LII->start < EndIdx) {
1568 lastUseIdx = LII->end;
1569 } else if (LII == LR.begin()) {
1570 // We may not have a liverange at all if this is a subregister untouched
1571 // between \p Begin and \p End.
1572 } else {
1573 --LII;
1574 }
1575
1576 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1577 --I;
1578 MachineInstr &MI = *I;
1579 if (MI.isDebugOrPseudoInstr())
1580 continue;
1581
1582 SlotIndex instrIdx = getInstructionIndex(MI);
1583 bool isStartValid = getInstructionFromIndex(LII->start);
1584 bool isEndValid = getInstructionFromIndex(LII->end);
1585
1586 // FIXME: This doesn't currently handle early-clobber or multiple removed
1587 // defs inside of the region to repair.
1588 for (const MachineOperand &MO : MI.operands()) {
1589 if (!MO.isReg() || MO.getReg() != Reg)
1590 continue;
1591
1592 unsigned SubReg = MO.getSubReg();
1593 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1594 if ((Mask & LaneMask).none())
1595 continue;
1596
1597 if (MO.isDef()) {
1598 if (!isStartValid) {
1599 if (LII->end.isDead()) {
1600 LII = LR.removeSegment(LII, true);
1601 if (LII != LR.begin())
1602 --LII;
1603 } else {
1604 LII->start = instrIdx.getRegSlot();
1605 LII->valno->def = instrIdx.getRegSlot();
1606 if (MO.getSubReg() && !MO.isUndef())
1607 lastUseIdx = instrIdx.getRegSlot();
1608 else
1609 lastUseIdx = SlotIndex();
1610 continue;
1611 }
1612 }
1613
1614 if (!lastUseIdx.isValid()) {
1615 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1616 LiveRange::Segment S(instrIdx.getRegSlot(),
1617 instrIdx.getDeadSlot(), VNI);
1618 LII = LR.addSegment(S);
1619 } else if (LII->start != instrIdx.getRegSlot()) {
1620 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1621 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1622 LII = LR.addSegment(S);
1623 }
1624
1625 if (MO.getSubReg() && !MO.isUndef())
1626 lastUseIdx = instrIdx.getRegSlot();
1627 else
1628 lastUseIdx = SlotIndex();
1629 } else if (MO.isUse()) {
1630 // FIXME: This should probably be handled outside of this branch,
1631 // either as part of the def case (for defs inside of the region) or
1632 // after the loop over the region.
1633 if (!isEndValid && !LII->end.isBlock())
1634 LII->end = instrIdx.getRegSlot();
1635 if (!lastUseIdx.isValid())
1636 lastUseIdx = instrIdx.getRegSlot();
1637 }
1638 }
1639 }
1640
1641 bool isStartValid = getInstructionFromIndex(LII->start);
1642 if (!isStartValid && LII->end.isDead())
1643 LR.removeSegment(*LII, true);
1644}
1645
1646void
1650 ArrayRef<Register> OrigRegs) {
1651 // Find anchor points, which are at the beginning/end of blocks or at
1652 // instructions that already have indexes.
1653 while (Begin != MBB->begin() && !Indexes->hasIndex(*std::prev(Begin)))
1654 --Begin;
1655 while (End != MBB->end() && !Indexes->hasIndex(*End))
1656 ++End;
1657
1658 SlotIndex EndIdx;
1659 if (End == MBB->end())
1660 EndIdx = getMBBEndIdx(MBB).getPrevSlot();
1661 else
1662 EndIdx = getInstructionIndex(*End);
1663
1664 Indexes->repairIndexesInRange(MBB, Begin, End);
1665
1666 // Make sure a live interval exists for all register operands in the range.
1667 SmallVector<Register> RegsToRepair(OrigRegs.begin(), OrigRegs.end());
1668 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1669 --I;
1670 MachineInstr &MI = *I;
1671 if (MI.isDebugOrPseudoInstr())
1672 continue;
1673 for (const MachineOperand &MO : MI.operands()) {
1674 if (MO.isReg() && MO.getReg().isVirtual()) {
1675 Register Reg = MO.getReg();
1676 // If the new instructions refer to subregs but the old instructions did
1677 // not, throw away any old live interval so it will be recomputed with
1678 // subranges.
1679 if (MO.getSubReg() && hasInterval(Reg) &&
1680 !getInterval(Reg).hasSubRanges() &&
1681 MRI->shouldTrackSubRegLiveness(Reg))
1682 removeInterval(Reg);
1683 if (!hasInterval(Reg)) {
1685 // Don't bother to repair a freshly calculated live interval.
1686 erase_value(RegsToRepair, Reg);
1687 }
1688 }
1689 }
1690 }
1691
1692 for (Register Reg : RegsToRepair) {
1693 if (!Reg.isVirtual())
1694 continue;
1695
1696 LiveInterval &LI = getInterval(Reg);
1697 // FIXME: Should we support undefs that gain defs?
1698 if (!LI.hasAtLeastOneValue())
1699 continue;
1700
1701 for (LiveInterval::SubRange &S : LI.subranges())
1702 repairOldRegInRange(Begin, End, EndIdx, S, Reg, S.LaneMask);
1704
1705 repairOldRegInRange(Begin, End, EndIdx, LI, Reg);
1706 }
1707}
1708
1710 for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
1711 if (LiveRange *LR = getCachedRegUnit(*Unit))
1712 if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1713 LR->removeValNo(VNI);
1714 }
1715}
1716
1718 // LI may not have the main range computed yet, but its subranges may
1719 // be present.
1720 VNInfo *VNI = LI.getVNInfoAt(Pos);
1721 if (VNI != nullptr) {
1722 assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1723 LI.removeValNo(VNI);
1724 }
1725
1726 // Also remove the value defined in subranges.
1727 for (LiveInterval::SubRange &S : LI.subranges()) {
1728 if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1729 if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1730 S.removeValNo(SVNI);
1731 }
1733}
1734
1737 ConnectedVNInfoEqClasses ConEQ(*this);
1738 unsigned NumComp = ConEQ.Classify(LI);
1739 if (NumComp <= 1)
1740 return;
1741 LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
1742 Register Reg = LI.reg();
1743 for (unsigned I = 1; I < NumComp; ++I) {
1744 Register NewVReg = MRI->cloneVirtualRegister(Reg);
1745 LiveInterval &NewLI = createEmptyInterval(NewVReg);
1746 SplitLIs.push_back(&NewLI);
1747 }
1748 ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1749}
1750
1752 assert(LICalc && "LICalc not initialized.");
1753 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1755}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineBasicBlock & MBB
Rewrite undef for PHI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
Live Interval static false cl::opt< bool > EnablePrecomputePhysRegs("precompute-phys-liveness", cl::Hidden, cl::desc("Eagerly compute live intervals for all physreg units."))
Live Interval Analysis
static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg)
Check whether use of reg in MI is live-through.
static void createSegmentsForValues(LiveRange &LR, iterator_range< LiveInterval::vni_iterator > VNIs)
liveintervals
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
if(VerifyEach)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Toolkit used by handleMove to trim or extend live intervals.
HMEditor(LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
void updateAllRanges(MachineInstr *MI)
Update all live ranges touched by MI, assuming a move from OldIdx to NewIdx.
LiveRange * getRegUnitLI(unsigned Unit)
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredTransitiveID(char &ID)
Definition: Pass.cpp:289
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
AnalysisUsage & addRequiredTransitive()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:152
iterator begin() const
Definition: ArrayRef.h:151
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:328
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
Definition: BitVector.h:718
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
Definition: LiveInterval.h:998
void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
Definition: Interval.h:36
void createDeadDefs(LiveRange &LR, Register Reg)
createDeadDefs - Create a dead def in LI for every def operand of Reg.
void calculate(LiveInterval &LI, bool TrackSubRegs)
Calculates liveness for the register specified in live interval LI.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
A live range for subregisters.
Definition: LiveInterval.h:693
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Register reg() const
Definition: LiveInterval.h:717
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:803
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:775
void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void repairIntervalsInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, ArrayRef< Register > OrigRegs)
Update live intervals for instructions in a range of iterators.
bool hasInterval(Register Reg) const
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
SlotIndexes * getSlotIndexes() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
ArrayRef< const uint32_t * > getRegMaskBits() const
Returns an array of register mask pointers corresponding to getRegMaskSlots().
void addKillFlags(const VirtRegMap *)
Add kill flags to any instruction that kills a virtual register.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
VNInfo::Allocator & getVNInfoAllocator()
ArrayRef< const uint32_t * > getRegMaskBitsInBlock(unsigned MBBNum) const
Returns an array of mask pointers corresponding to getRegMaskSlotsInBlock(MBBNum).
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
LiveRange & getRegUnit(unsigned Unit)
Return the live range for register unit Unit.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
LiveRange * getCachedRegUnit(unsigned Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LiveInterval & getInterval(Register Reg)
void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl< SlotIndex > *EndPoints)
If LR has a live value at Kill, prune its live range by removing any liveness reachable from Kill.
void removeInterval(Register Reg)
Interval removal.
void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
LiveInterval::Segment addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst)
Given a register and an instruction, adds a live segment from that instruction to the end of its MBB.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
void print(raw_ostream &O, const Module *=nullptr) const override
Implement the dump method.
Result of a LiveRange query.
Definition: LiveInterval.h:90
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
Definition: LiveInterval.h:129
bool isDeadDef() const
Return true if this instruction has a dead def.
Definition: LiveInterval.h:117
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
Definition: LiveInterval.h:105
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
Definition: LiveInterval.h:135
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
Definition: LiveInterval.h:147
static LLVM_ATTRIBUTE_UNUSED bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)
A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:408
iterator_range< vni_iterator > vnis()
Definition: LiveInterval.h:230
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
bool covers(const LiveRange &Other) const
Returns true if all segments of the Other live range are completely covered by this live range.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position,...
Definition: LiveInterval.h:271
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
void verify() const
Walk the range and assert if any invariants fail to hold.
bool empty() const
Definition: LiveInterval.h:382
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:541
iterator end()
Definition: LiveInterval.h:216
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
Definition: LiveInterval.h:429
iterator begin()
Definition: LiveInterval.h:215
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:385
Segments segments
Definition: LiveInterval.h:203
VNInfoList valnos
Definition: LiveInterval.h:204
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:392
bool hasAtLeastOneValue() const
Definition: LiveInterval.h:309
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
Definition: LiveInterval.h:436
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
void flushSegmentSet()
Flush segment set into the regular segment vector.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
MCSuperRegIterator enumerates all super-registers of Reg.
bool isValid() const
isValid - Returns true until all the operands have been visited.
MIBundleOperands - Iterate over all operands in a bundle of machine instructions.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
const uint32_t * getBeginClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the start of this basic block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
const uint32_t * getEndClobberMask(const TargetRegisterInfo *TRI) const
Get the clobber mask for the end of the basic block.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
float getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
Representation of each machine instruction.
Definition: MachineInstr.h:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:516
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setIsDead(bool Val=true)
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level.
iterator_range< reg_instr_iterator > reg_instructions(Register Reg) const
LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
bool isReservedRegUnit(unsigned Unit) const
Returns true when the given register unit is considered reserved.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
bool reg_empty(Register RegNo) const
reg_empty - Return true if there are no instructions using or defining the specified register (it may...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void dump() const
Definition: Pass.cpp:136
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
Definition: SlotIndexes.h:231
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:264
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:204
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:152
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
Definition: SlotIndexes.h:210
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:246
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:294
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:259
SlotIndexes pass.
Definition: SlotIndexes.h:319
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:540
void removeMachineInstrFromMaps(MachineInstr &MI, bool AllowBundled=false)
Removes machine instruction (bundle) MI from the mapping.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:519
void repairIndexesInRange(MachineBasicBlock *MBB, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
Repair indexes after adding and removing instructions.
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:460
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:481
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:414
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:390
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:471
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:385
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:408
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:972
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
void resize(size_type N)
Definition: SmallVector.h:642
void push_back(const T &Elt)
Definition: SmallVector.h:416
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:289
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
MI-level Statepoint operands.
Definition: StackMaps.h:158
unsigned getNumDeoptArgsIdx() const
Get index of Number Deopt Arguments operand.
Definition: StackMaps.h:199
uint64_t getFlags() const
Return the statepoint flags.
Definition: StackMaps.h:222
unsigned getNumGCPtrIdx()
Get index of number of GC pointers.
Definition: StackMaps.cpp:114
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const uint32_t * getCustomEHPadPreservedMask(const MachineFunction &MF) const
Return a register mask for the registers preserved by the unwinder, or nullptr if no custom mask is n...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
void markUnused()
Mark this value as unused.
Definition: LiveInterval.h:84
bool isUnused() const
Returns true if this value is unused.
Definition: LiveInterval.h:81
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
Definition: LiveInterval.h:78
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:105
self_iterator getIterator()
Definition: ilist_node.h:82
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:119
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition: LaneBitmask.h:92
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
Definition: MathExtras.cpp:28
cl::opt< bool > UseSegmentSetForPhysRegs
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:2001
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2084
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
iterator_range< MIBundleOperands > mi_bundle_ops(MachineInstr &MI)
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
void initializeLiveIntervalsPass(PassRegistry &)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
char & LiveIntervalsID
LiveIntervals - This analysis keeps track of the live ranges of virtual and physical registers.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
#define N
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
constexpr bool any() const
Definition: LaneBitmask.h:53
static constexpr LaneBitmask getNone()
Definition: LaneBitmask.h:81
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162