LLVM 19.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 (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {
284 if (!MRI->reg_empty(Reg))
285 LICalc->createDeadDefs(LR, Reg);
286 // A register unit is considered reserved if all its roots and all their
287 // super registers are reserved.
288 if (!MRI->isReserved(Reg))
289 IsRootReserved = false;
290 }
291 IsReserved |= IsRootReserved;
292 }
293 assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
294 "reserved computation mismatch");
295
296 // Now extend LR to reach all uses.
297 // Ignore uses of reserved registers. We only track defs of those.
298 if (!IsReserved) {
299 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
300 for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {
301 if (!MRI->reg_empty(Reg))
302 LICalc->extendToUses(LR, Reg);
303 }
304 }
305 }
306
307 // Flush the segment set to the segment vector.
309 LR.flushSegmentSet();
310}
311
312/// Precompute the live ranges of any register units that are live-in to an ABI
313/// block somewhere. Register values can appear without a corresponding def when
314/// entering the entry block or a landing pad.
315void LiveIntervals::computeLiveInRegUnits() {
316 RegUnitRanges.resize(TRI->getNumRegUnits());
317 LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
318
319 // Keep track of the live range sets allocated.
320 SmallVector<unsigned, 8> NewRanges;
321
322 // Check all basic blocks for live-ins.
323 for (const MachineBasicBlock &MBB : *MF) {
324 // We only care about ABI blocks: Entry + landing pads.
325 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
326 continue;
327
328 // Create phi-defs at Begin for all live-in registers.
329 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
330 LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
331 for (const auto &LI : MBB.liveins()) {
332 for (MCRegUnit Unit : TRI->regunits(LI.PhysReg)) {
333 LiveRange *LR = RegUnitRanges[Unit];
334 if (!LR) {
335 // Use segment set to speed-up initial computation of the live range.
336 LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
337 NewRanges.push_back(Unit);
338 }
339 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
340 (void)VNI;
341 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
342 }
343 }
344 LLVM_DEBUG(dbgs() << '\n');
345 }
346 LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
347
348 // Compute the 'normal' part of the ranges.
349 for (unsigned Unit : NewRanges)
350 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
351}
352
355 for (VNInfo *VNI : VNIs) {
356 if (VNI->isUnused())
357 continue;
358 SlotIndex Def = VNI->def;
359 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
360 }
361}
362
363void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
364 ShrinkToUsesWorkList &WorkList,
365 Register Reg, LaneBitmask LaneMask) {
366 // Keep track of the PHIs that are in use.
368 // Blocks that have already been added to WorkList as live-out.
370
371 auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
372 -> const LiveRange& {
373 if (M.none())
374 return I;
375 for (const LiveInterval::SubRange &SR : I.subranges()) {
376 if ((SR.LaneMask & M).any()) {
377 assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
378 return SR;
379 }
380 }
381 llvm_unreachable("Subrange for mask not found");
382 };
383
384 const LiveInterval &LI = getInterval(Reg);
385 const LiveRange &OldRange = getSubRange(LI, LaneMask);
386
387 // Extend intervals to reach all uses in WorkList.
388 while (!WorkList.empty()) {
389 SlotIndex Idx = WorkList.back().first;
390 VNInfo *VNI = WorkList.back().second;
391 WorkList.pop_back();
392 const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
393 SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
394
395 // Extend the live range for VNI to be live at Idx.
396 if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
397 assert(ExtVNI == VNI && "Unexpected existing value number");
398 (void)ExtVNI;
399 // Is this a PHIDef we haven't seen before?
400 if (!VNI->isPHIDef() || VNI->def != BlockStart ||
401 !UsedPHIs.insert(VNI).second)
402 continue;
403 // The PHI is live, make sure the predecessors are live-out.
404 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
405 if (!LiveOut.insert(Pred).second)
406 continue;
407 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
408 // A predecessor is not required to have a live-out value for a PHI.
409 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
410 WorkList.push_back(std::make_pair(Stop, PVNI));
411 }
412 continue;
413 }
414
415 // VNI is live-in to MBB.
416 LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
417 Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
418
419 // Make sure VNI is live-out from the predecessors.
420 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
421 if (!LiveOut.insert(Pred).second)
422 continue;
423 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
424 if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
425 assert(OldVNI == VNI && "Wrong value out of predecessor");
426 (void)OldVNI;
427 WorkList.push_back(std::make_pair(Stop, VNI));
428 } else {
429#ifndef NDEBUG
430 // There was no old VNI. Verify that Stop is jointly dominated
431 // by <undef>s for this live range.
432 assert(LaneMask.any() &&
433 "Missing value out of predecessor for main range");
435 LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
436 assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
437 "Missing value out of predecessor for subrange");
438#endif
439 }
440 }
441 }
442}
443
446 LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
447 assert(li->reg().isVirtual() && "Can only shrink virtual registers");
448
449 // Shrink subregister live ranges.
450 bool NeedsCleanup = false;
451 for (LiveInterval::SubRange &S : li->subranges()) {
452 shrinkToUses(S, li->reg());
453 if (S.empty())
454 NeedsCleanup = true;
455 }
456 if (NeedsCleanup)
458
459 // Find all the values used, including PHI kills.
460 ShrinkToUsesWorkList WorkList;
461
462 // Visit all instructions reading li->reg().
463 Register Reg = li->reg();
464 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
465 if (UseMI.isDebugInstr() || !UseMI.readsVirtualRegister(Reg))
466 continue;
468 LiveQueryResult LRQ = li->Query(Idx);
469 VNInfo *VNI = LRQ.valueIn();
470 if (!VNI) {
471 // This shouldn't happen: readsVirtualRegister returns true, but there is
472 // no live value. It is likely caused by a target getting <undef> flags
473 // wrong.
475 dbgs() << Idx << '\t' << UseMI
476 << "Warning: Instr claims to read non-existent value in "
477 << *li << '\n');
478 continue;
479 }
480 // Special case: An early-clobber tied operand reads and writes the
481 // register one slot early.
482 if (VNInfo *DefVNI = LRQ.valueDefined())
483 Idx = DefVNI->def;
484
485 WorkList.push_back(std::make_pair(Idx, VNI));
486 }
487
488 // Create new live ranges with only minimal live segments per def.
489 LiveRange NewLR;
490 createSegmentsForValues(NewLR, li->vnis());
491 extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
492
493 // Move the trimmed segments back.
494 li->segments.swap(NewLR.segments);
495
496 // Handle dead values.
497 bool CanSeparate = computeDeadValues(*li, dead);
498 LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
499 return CanSeparate;
500}
501
502bool LiveIntervals::computeDeadValues(LiveInterval &LI,
504 bool MayHaveSplitComponents = false;
505
506 for (VNInfo *VNI : LI.valnos) {
507 if (VNI->isUnused())
508 continue;
509 SlotIndex Def = VNI->def;
511 assert(I != LI.end() && "Missing segment for VNI");
512
513 // Is the register live before? Otherwise we may have to add a read-undef
514 // flag for subregister defs.
515 Register VReg = LI.reg();
516 if (MRI->shouldTrackSubRegLiveness(VReg)) {
517 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
519 MI->setRegisterDefReadUndef(VReg);
520 }
521 }
522
523 if (I->end != Def.getDeadSlot())
524 continue;
525 if (VNI->isPHIDef()) {
526 // This is a dead PHI. Remove it.
527 VNI->markUnused();
528 LI.removeSegment(I);
529 LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
530 } else {
531 // This is a dead def. Make sure the instruction knows.
533 assert(MI && "No instruction defining live value");
534 MI->addRegisterDead(LI.reg(), TRI);
535
536 if (dead && MI->allDefsAreDead()) {
537 LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
538 dead->push_back(MI);
539 }
540 }
541 MayHaveSplitComponents = true;
542 }
543 return MayHaveSplitComponents;
544}
545
547 LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
548 assert(Reg.isVirtual() && "Can only shrink virtual registers");
549 // Find all the values used, including PHI kills.
550 ShrinkToUsesWorkList WorkList;
551
552 // Visit all instructions reading Reg.
553 SlotIndex LastIdx;
554 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
555 // Skip "undef" uses.
556 if (!MO.readsReg())
557 continue;
558 // Maybe the operand is for a subregister we don't care about.
559 unsigned SubReg = MO.getSubReg();
560 if (SubReg != 0) {
562 if ((LaneMask & SR.LaneMask).none())
563 continue;
564 }
565 // We only need to visit each instruction once.
566 MachineInstr *UseMI = MO.getParent();
568 if (Idx == LastIdx)
569 continue;
570 LastIdx = Idx;
571
572 LiveQueryResult LRQ = SR.Query(Idx);
573 VNInfo *VNI = LRQ.valueIn();
574 // For Subranges it is possible that only undef values are left in that
575 // part of the subregister, so there is no real liverange at the use
576 if (!VNI)
577 continue;
578
579 // Special case: An early-clobber tied operand reads and writes the
580 // register one slot early.
581 if (VNInfo *DefVNI = LRQ.valueDefined())
582 Idx = DefVNI->def;
583
584 WorkList.push_back(std::make_pair(Idx, VNI));
585 }
586
587 // Create a new live ranges with only minimal live segments per def.
588 LiveRange NewLR;
589 createSegmentsForValues(NewLR, SR.vnis());
590 extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
591
592 // Move the trimmed ranges back.
593 SR.segments.swap(NewLR.segments);
594
595 // Remove dead PHI value numbers
596 for (VNInfo *VNI : SR.valnos) {
597 if (VNI->isUnused())
598 continue;
599 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
600 assert(Segment != nullptr && "Missing segment for VNI");
601 if (Segment->end != VNI->def.getDeadSlot())
602 continue;
603 if (VNI->isPHIDef()) {
604 // This is a dead PHI. Remove it.
605 LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
606 << " may separate interval\n");
607 VNI->markUnused();
608 SR.removeSegment(*Segment);
609 }
610 }
611
612 LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
613}
614
616 ArrayRef<SlotIndex> Indices,
617 ArrayRef<SlotIndex> Undefs) {
618 assert(LICalc && "LICalc not initialized.");
619 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
620 for (SlotIndex Idx : Indices)
621 LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
622}
623
625 SmallVectorImpl<SlotIndex> *EndPoints) {
626 LiveQueryResult LRQ = LR.Query(Kill);
627 VNInfo *VNI = LRQ.valueOutOrDead();
628 if (!VNI)
629 return;
630
631 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
632 SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
633
634 // If VNI isn't live out from KillMBB, the value is trivially pruned.
635 if (LRQ.endPoint() < MBBEnd) {
636 LR.removeSegment(Kill, LRQ.endPoint());
637 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
638 return;
639 }
640
641 // VNI is live out of KillMBB.
642 LR.removeSegment(Kill, MBBEnd);
643 if (EndPoints) EndPoints->push_back(MBBEnd);
644
645 // Find all blocks that are reachable from KillMBB without leaving VNI's live
646 // range. It is possible that KillMBB itself is reachable, so start a DFS
647 // from each successor.
649 VisitedTy Visited;
650 for (MachineBasicBlock *Succ : KillMBB->successors()) {
652 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
653 I != E;) {
655
656 // Check if VNI is live in to MBB.
657 SlotIndex MBBStart, MBBEnd;
658 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
659 LiveQueryResult LRQ = LR.Query(MBBStart);
660 if (LRQ.valueIn() != VNI) {
661 // This block isn't part of the VNI segment. Prune the search.
662 I.skipChildren();
663 continue;
664 }
665
666 // Prune the search if VNI is killed in MBB.
667 if (LRQ.endPoint() < MBBEnd) {
668 LR.removeSegment(MBBStart, LRQ.endPoint());
669 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
670 I.skipChildren();
671 continue;
672 }
673
674 // VNI is live through MBB.
675 LR.removeSegment(MBBStart, MBBEnd);
676 if (EndPoints) EndPoints->push_back(MBBEnd);
677 ++I;
678 }
679 }
680}
681
682//===----------------------------------------------------------------------===//
683// Register allocator hooks.
684//
685
687 // Keep track of regunit ranges.
689
690 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
692 if (MRI->reg_nodbg_empty(Reg))
693 continue;
694 const LiveInterval &LI = getInterval(Reg);
695 if (LI.empty())
696 continue;
697
698 // Target may have not allocated this yet.
699 Register PhysReg = VRM->getPhys(Reg);
700 if (!PhysReg)
701 continue;
702
703 // Find the regunit intervals for the assigned register. They may overlap
704 // the virtual register live range, cancelling any kills.
705 RU.clear();
706 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
707 const LiveRange &RURange = getRegUnit(Unit);
708 if (RURange.empty())
709 continue;
710 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
711 }
712 // Every instruction that kills Reg corresponds to a segment range end
713 // point.
714 for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
715 ++RI) {
716 // A block index indicates an MBB edge.
717 if (RI->end.isBlock())
718 continue;
720 if (!MI)
721 continue;
722
723 // Check if any of the regunits are live beyond the end of RI. That could
724 // happen when a physreg is defined as a copy of a virtreg:
725 //
726 // %eax = COPY %5
727 // FOO %5 <--- MI, cancel kill because %eax is live.
728 // BAR killed %eax
729 //
730 // There should be no kill flag on FOO when %5 is rewritten as %eax.
731 for (auto &RUP : RU) {
732 const LiveRange &RURange = *RUP.first;
733 LiveRange::const_iterator &I = RUP.second;
734 if (I == RURange.end())
735 continue;
736 I = RURange.advanceTo(I, RI->end);
737 if (I == RURange.end() || I->start >= RI->end)
738 continue;
739 // I is overlapping RI.
740 goto CancelKill;
741 }
742
743 if (MRI->subRegLivenessEnabled()) {
744 // When reading a partial undefined value we must not add a kill flag.
745 // The regalloc might have used the undef lane for something else.
746 // Example:
747 // %1 = ... ; R32: %1
748 // %2:high16 = ... ; R64: %2
749 // = read killed %2 ; R64: %2
750 // = read %1 ; R32: %1
751 // The <kill> flag is correct for %2, but the register allocator may
752 // assign R0L to %1, and R0 to %2 because the low 32bits of R0
753 // are actually never written by %2. After assignment the <kill>
754 // flag at the read instruction is invalid.
755 LaneBitmask DefinedLanesMask;
756 if (LI.hasSubRanges()) {
757 // Compute a mask of lanes that are defined.
758 DefinedLanesMask = LaneBitmask::getNone();
759 for (const LiveInterval::SubRange &SR : LI.subranges())
760 for (const LiveRange::Segment &Segment : SR.segments) {
761 if (Segment.start >= RI->end)
762 break;
763 if (Segment.end == RI->end) {
764 DefinedLanesMask |= SR.LaneMask;
765 break;
766 }
767 }
768 } else
769 DefinedLanesMask = LaneBitmask::getAll();
770
771 bool IsFullWrite = false;
772 for (const MachineOperand &MO : MI->operands()) {
773 if (!MO.isReg() || MO.getReg() != Reg)
774 continue;
775 if (MO.isUse()) {
776 // Reading any undefined lanes?
777 unsigned SubReg = MO.getSubReg();
779 : MRI->getMaxLaneMaskForVReg(Reg);
780 if ((UseMask & ~DefinedLanesMask).any())
781 goto CancelKill;
782 } else if (MO.getSubReg() == 0) {
783 // Writing to the full register?
784 assert(MO.isDef());
785 IsFullWrite = true;
786 }
787 }
788
789 // If an instruction writes to a subregister, a new segment starts in
790 // the LiveInterval. But as this is only overriding part of the register
791 // adding kill-flags is not correct here after registers have been
792 // assigned.
793 if (!IsFullWrite) {
794 // Next segment has to be adjacent in the subregister write case.
795 LiveRange::const_iterator N = std::next(RI);
796 if (N != LI.end() && N->start == RI->end)
797 goto CancelKill;
798 }
799 }
800
801 MI->addRegisterKilled(Reg, nullptr);
802 continue;
803CancelKill:
804 MI->clearRegisterKills(Reg, nullptr);
805 }
806 }
807}
808
811 assert(!LI.empty() && "LiveInterval is empty.");
812
813 // A local live range must be fully contained inside the block, meaning it is
814 // defined and killed at instructions, not at block boundaries. It is not
815 // live in or out of any block.
816 //
817 // It is technically possible to have a PHI-defined live range identical to a
818 // single block, but we are going to return false in that case.
819
820 SlotIndex Start = LI.beginIndex();
821 if (Start.isBlock())
822 return nullptr;
823
824 SlotIndex Stop = LI.endIndex();
825 if (Stop.isBlock())
826 return nullptr;
827
828 // getMBBFromIndex doesn't need to search the MBB table when both indexes
829 // belong to proper instructions.
830 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
831 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
832 return MBB1 == MBB2 ? MBB1 : nullptr;
833}
834
835bool
836LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
837 for (const VNInfo *PHI : LI.valnos) {
838 if (PHI->isUnused() || !PHI->isPHIDef())
839 continue;
840 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
841 // Conservatively return true instead of scanning huge predecessor lists.
842 if (PHIMBB->pred_size() > 100)
843 return true;
844 for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
845 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
846 return true;
847 }
848 return false;
849}
850
851float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
852 const MachineBlockFrequencyInfo *MBFI,
853 const MachineInstr &MI) {
854 return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
855}
856
857float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
858 const MachineBlockFrequencyInfo *MBFI,
859 const MachineBasicBlock *MBB) {
860 return (isDef + isUse) * MBFI->getBlockFreqRelativeToEntryBlock(MBB);
861}
862
866 VNInfo *VN = Interval.getNextValue(
867 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
869 LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
870 getMBBEndIdx(startInst.getParent()), VN);
871 Interval.addSegment(S);
872
873 return S;
874}
875
876//===----------------------------------------------------------------------===//
877// Register mask functions
878//===----------------------------------------------------------------------===//
879/// Check whether use of reg in MI is live-through. Live-through means that
880/// the value is alive on exit from Machine instruction. The example of such
881/// use is a deopt value in statepoint instruction.
882static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg) {
883 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
884 return false;
887 return false;
888 for (unsigned Idx = SO.getNumDeoptArgsIdx(), E = SO.getNumGCPtrIdx(); Idx < E;
889 ++Idx) {
890 const MachineOperand &MO = MI->getOperand(Idx);
891 if (MO.isReg() && MO.getReg() == Reg)
892 return true;
893 }
894 return false;
895}
896
898 BitVector &UsableRegs) {
899 if (LI.empty())
900 return false;
901 LiveInterval::const_iterator LiveI = LI.begin(), LiveE = LI.end();
902
903 // Use a smaller arrays for local live ranges.
909 } else {
910 Slots = getRegMaskSlots();
911 Bits = getRegMaskBits();
912 }
913
914 // We are going to enumerate all the register mask slots contained in LI.
915 // Start with a binary search of RegMaskSlots to find a starting point.
916 ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);
917 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
918
919 // No slots in range, LI begins after the last call.
920 if (SlotI == SlotE)
921 return false;
922
923 bool Found = false;
924 // Utility to union regmasks.
925 auto unionBitMask = [&](unsigned Idx) {
926 if (!Found) {
927 // This is the first overlap. Initialize UsableRegs to all ones.
928 UsableRegs.clear();
929 UsableRegs.resize(TRI->getNumRegs(), true);
930 Found = true;
931 }
932 // Remove usable registers clobbered by this mask.
933 UsableRegs.clearBitsNotInMask(Bits[Idx]);
934 };
935 while (true) {
936 assert(*SlotI >= LiveI->start);
937 // Loop over all slots overlapping this segment.
938 while (*SlotI < LiveI->end) {
939 // *SlotI overlaps LI. Collect mask bits.
940 unionBitMask(SlotI - Slots.begin());
941 if (++SlotI == SlotE)
942 return Found;
943 }
944 // If segment ends with live-through use we need to collect its regmask.
945 if (*SlotI == LiveI->end)
947 if (hasLiveThroughUse(MI, LI.reg()))
948 unionBitMask(SlotI++ - Slots.begin());
949 // *SlotI is beyond the current LI segment.
950 // Special advance implementation to not miss next LiveI->end.
951 if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.endIndex())
952 return Found;
953 while (LiveI->end < *SlotI)
954 ++LiveI;
955 // Advance SlotI until it overlaps.
956 while (*SlotI < LiveI->start)
957 if (++SlotI == SlotE)
958 return Found;
959 }
960}
961
962//===----------------------------------------------------------------------===//
963// IntervalUpdate class.
964//===----------------------------------------------------------------------===//
965
966/// Toolkit used by handleMove to trim or extend live intervals.
968private:
969 LiveIntervals& LIS;
971 const TargetRegisterInfo& TRI;
972 SlotIndex OldIdx;
973 SlotIndex NewIdx;
975 bool UpdateFlags;
976
977public:
979 const TargetRegisterInfo& TRI,
980 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
981 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
982 UpdateFlags(UpdateFlags) {}
983
984 // FIXME: UpdateFlags is a workaround that creates live intervals for all
985 // physregs, even those that aren't needed for regalloc, in order to update
986 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
987 // flags, and postRA passes will use a live register utility instead.
988 LiveRange *getRegUnitLI(unsigned Unit) {
989 if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
990 return &LIS.getRegUnit(Unit);
991 return LIS.getCachedRegUnit(Unit);
992 }
993
994 /// Update all live ranges touched by MI, assuming a move from OldIdx to
995 /// NewIdx.
997 LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
998 << *MI);
999 bool hasRegMask = false;
1000 for (MachineOperand &MO : MI->operands()) {
1001 if (MO.isRegMask())
1002 hasRegMask = true;
1003 if (!MO.isReg())
1004 continue;
1005 if (MO.isUse()) {
1006 if (!MO.readsReg())
1007 continue;
1008 // Aggressively clear all kill flags.
1009 // They are reinserted by VirtRegRewriter.
1010 MO.setIsKill(false);
1011 }
1012
1013 Register Reg = MO.getReg();
1014 if (!Reg)
1015 continue;
1016 if (Reg.isVirtual()) {
1017 LiveInterval &LI = LIS.getInterval(Reg);
1018 if (LI.hasSubRanges()) {
1019 unsigned SubReg = MO.getSubReg();
1020 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
1021 : MRI.getMaxLaneMaskForVReg(Reg);
1022 for (LiveInterval::SubRange &S : LI.subranges()) {
1023 if ((S.LaneMask & LaneMask).none())
1024 continue;
1025 updateRange(S, Reg, S.LaneMask);
1026 }
1027 }
1028 updateRange(LI, Reg, LaneBitmask::getNone());
1029 // If main range has a hole and we are moving a subrange use across
1030 // the hole updateRange() cannot properly handle it since it only
1031 // gets the LiveRange and not the whole LiveInterval. As a result
1032 // we may end up with a main range not covering all subranges.
1033 // This is extremely rare case, so let's check and reconstruct the
1034 // main range.
1035 if (LI.hasSubRanges()) {
1036 unsigned SubReg = MO.getSubReg();
1037 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
1038 : MRI.getMaxLaneMaskForVReg(Reg);
1039 for (LiveInterval::SubRange &S : LI.subranges()) {
1040 if ((S.LaneMask & LaneMask).none() || LI.covers(S))
1041 continue;
1042 LI.clear();
1044 break;
1045 }
1046 }
1047
1048 continue;
1049 }
1050
1051 // For physregs, only update the regunits that actually have a
1052 // precomputed live range.
1053 for (MCRegUnit Unit : TRI.regunits(Reg.asMCReg()))
1054 if (LiveRange *LR = getRegUnitLI(Unit))
1055 updateRange(*LR, Unit, LaneBitmask::getNone());
1056 }
1057 if (hasRegMask)
1058 updateRegMaskSlots();
1059 }
1060
1061private:
1062 /// Update a single live range, assuming an instruction has been moved from
1063 /// OldIdx to NewIdx.
1064 void updateRange(LiveRange &LR, Register Reg, LaneBitmask LaneMask) {
1065 if (!Updated.insert(&LR).second)
1066 return;
1067 LLVM_DEBUG({
1068 dbgs() << " ";
1069 if (Reg.isVirtual()) {
1070 dbgs() << printReg(Reg);
1071 if (LaneMask.any())
1072 dbgs() << " L" << PrintLaneMask(LaneMask);
1073 } else {
1074 dbgs() << printRegUnit(Reg, &TRI);
1075 }
1076 dbgs() << ":\t" << LR << '\n';
1077 });
1078 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1079 handleMoveDown(LR);
1080 else
1081 handleMoveUp(LR, Reg, LaneMask);
1082 LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');
1083 LR.verify();
1084 }
1085
1086 /// Update LR to reflect an instruction has been moved downwards from OldIdx
1087 /// to NewIdx (OldIdx < NewIdx).
1088 void handleMoveDown(LiveRange &LR) {
1089 LiveRange::iterator E = LR.end();
1090 // Segment going into OldIdx.
1091 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1092
1093 // No value live before or after OldIdx? Nothing to do.
1094 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1095 return;
1096
1097 LiveRange::iterator OldIdxOut;
1098 // Do we have a value live-in to OldIdx?
1099 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1100 // If the live-in value already extends to NewIdx, there is nothing to do.
1101 if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1102 return;
1103 // Aggressively remove all kill flags from the old kill point.
1104 // Kill flags shouldn't be used while live intervals exist, they will be
1105 // reinserted by VirtRegRewriter.
1106 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1107 for (MachineOperand &MOP : mi_bundle_ops(*KillMI))
1108 if (MOP.isReg() && MOP.isUse())
1109 MOP.setIsKill(false);
1110
1111 // Is there a def before NewIdx which is not OldIdx?
1112 LiveRange::iterator Next = std::next(OldIdxIn);
1113 if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
1114 SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1115 // If we are here then OldIdx was just a use but not a def. We only have
1116 // to ensure liveness extends to NewIdx.
1117 LiveRange::iterator NewIdxIn =
1118 LR.advanceTo(Next, NewIdx.getBaseIndex());
1119 // Extend the segment before NewIdx if necessary.
1120 if (NewIdxIn == E ||
1121 !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
1122 LiveRange::iterator Prev = std::prev(NewIdxIn);
1123 Prev->end = NewIdx.getRegSlot();
1124 }
1125 // Extend OldIdxIn.
1126 OldIdxIn->end = Next->start;
1127 return;
1128 }
1129
1130 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1131 // invalid by overlapping ranges.
1132 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1133 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1134 // If this was not a kill, then there was no def and we're done.
1135 if (!isKill)
1136 return;
1137
1138 // Did we have a Def at OldIdx?
1139 OldIdxOut = Next;
1140 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1141 return;
1142 } else {
1143 OldIdxOut = OldIdxIn;
1144 }
1145
1146 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1147 // to the segment starting there.
1148 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1149 "No def?");
1150 VNInfo *OldIdxVNI = OldIdxOut->valno;
1151 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1152
1153 // If the defined value extends beyond NewIdx, just move the beginning
1154 // of the segment to NewIdx.
1155 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1156 if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1157 OldIdxVNI->def = NewIdxDef;
1158 OldIdxOut->start = OldIdxVNI->def;
1159 return;
1160 }
1161
1162 // If we are here then we have a Definition at OldIdx which ends before
1163 // NewIdx.
1164
1165 // Is there an existing Def at NewIdx?
1166 LiveRange::iterator AfterNewIdx
1167 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1168 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1169 if (!OldIdxDefIsDead &&
1170 SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
1171 // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1172 VNInfo *DefVNI;
1173 if (OldIdxOut != LR.begin() &&
1174 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1175 OldIdxOut->start)) {
1176 // There is no gap between OldIdxOut and its predecessor anymore,
1177 // merge them.
1178 LiveRange::iterator IPrev = std::prev(OldIdxOut);
1179 DefVNI = OldIdxVNI;
1180 IPrev->end = OldIdxOut->end;
1181 } else {
1182 // The value is live in to OldIdx
1183 LiveRange::iterator INext = std::next(OldIdxOut);
1184 assert(INext != E && "Must have following segment");
1185 // We merge OldIdxOut and its successor. As we're dealing with subreg
1186 // reordering, there is always a successor to OldIdxOut in the same BB
1187 // We don't need INext->valno anymore and will reuse for the new segment
1188 // we create later.
1189 DefVNI = OldIdxVNI;
1190 INext->start = OldIdxOut->end;
1191 INext->valno->def = INext->start;
1192 }
1193 // If NewIdx is behind the last segment, extend that and append a new one.
1194 if (AfterNewIdx == E) {
1195 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1196 // one position.
1197 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1198 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1199 std::copy(std::next(OldIdxOut), E, OldIdxOut);
1200 // The last segment is undefined now, reuse it for a dead def.
1201 LiveRange::iterator NewSegment = std::prev(E);
1202 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1203 DefVNI);
1204 DefVNI->def = NewIdxDef;
1205
1206 LiveRange::iterator Prev = std::prev(NewSegment);
1207 Prev->end = NewIdxDef;
1208 } else {
1209 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1210 // one position.
1211 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1212 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1213 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1214 LiveRange::iterator Prev = std::prev(AfterNewIdx);
1215 // We have two cases:
1216 if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1217 // Case 1: NewIdx is inside a liverange. Split this liverange at
1218 // NewIdxDef into the segment "Prev" followed by "NewSegment".
1219 LiveRange::iterator NewSegment = AfterNewIdx;
1220 *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1221 Prev->valno->def = NewIdxDef;
1222
1223 *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1224 DefVNI->def = Prev->start;
1225 } else {
1226 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1227 // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1228 *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1229 DefVNI->def = NewIdxDef;
1230 assert(DefVNI != AfterNewIdx->valno);
1231 }
1232 }
1233 return;
1234 }
1235
1236 if (AfterNewIdx != E &&
1237 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
1238 // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1239 // that value.
1240 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1241 LR.removeValNo(OldIdxVNI);
1242 } else {
1243 // There was no existing def at NewIdx. We need to create a dead def
1244 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1245 // a new segment at the place where we want to construct the dead def.
1246 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1247 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1248 assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1249 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1250 // We can reuse OldIdxVNI now.
1251 LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1252 VNInfo *NewSegmentVNI = OldIdxVNI;
1253 NewSegmentVNI->def = NewIdxDef;
1254 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1255 NewSegmentVNI);
1256 }
1257 }
1258
1259 /// Update LR to reflect an instruction has been moved upwards from OldIdx
1260 /// to NewIdx (NewIdx < OldIdx).
1261 void handleMoveUp(LiveRange &LR, Register Reg, LaneBitmask LaneMask) {
1262 LiveRange::iterator E = LR.end();
1263 // Segment going into OldIdx.
1264 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1265
1266 // No value live before or after OldIdx? Nothing to do.
1267 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1268 return;
1269
1270 LiveRange::iterator OldIdxOut;
1271 // Do we have a value live-in to OldIdx?
1272 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1273 // If the live-in value isn't killed here, then we have no Def at
1274 // OldIdx, moreover the value must be live at NewIdx so there is nothing
1275 // to do.
1276 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1277 if (!isKill)
1278 return;
1279
1280 // At this point we have to move OldIdxIn->end back to the nearest
1281 // previous use or (dead-)def but no further than NewIdx.
1282 SlotIndex DefBeforeOldIdx
1283 = std::max(OldIdxIn->start.getDeadSlot(),
1284 NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1285 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1286
1287 // Did we have a Def at OldIdx? If not we are done now.
1288 OldIdxOut = std::next(OldIdxIn);
1289 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1290 return;
1291 } else {
1292 OldIdxOut = OldIdxIn;
1293 OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
1294 }
1295
1296 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1297 // to the segment starting there.
1298 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1299 "No def?");
1300 VNInfo *OldIdxVNI = OldIdxOut->valno;
1301 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1302 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1303
1304 // Is there an existing def at NewIdx?
1305 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1306 LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1307 if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1308 assert(NewIdxOut->valno != OldIdxVNI &&
1309 "Same value defined more than once?");
1310 // If OldIdx was a dead def remove it.
1311 if (!OldIdxDefIsDead) {
1312 // Remove segment starting at NewIdx and move begin of OldIdxOut to
1313 // NewIdx so it can take its place.
1314 OldIdxVNI->def = NewIdxDef;
1315 OldIdxOut->start = NewIdxDef;
1316 LR.removeValNo(NewIdxOut->valno);
1317 } else {
1318 // Simply remove the dead def at OldIdx.
1319 LR.removeValNo(OldIdxVNI);
1320 }
1321 } else {
1322 // Previously nothing was live after NewIdx, so all we have to do now is
1323 // move the begin of OldIdxOut to NewIdx.
1324 if (!OldIdxDefIsDead) {
1325 // Do we have any intermediate Defs between OldIdx and NewIdx?
1326 if (OldIdxIn != E &&
1327 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1328 // OldIdx is not a dead def and NewIdx is before predecessor start.
1329 LiveRange::iterator NewIdxIn = NewIdxOut;
1330 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1331 const SlotIndex SplitPos = NewIdxDef;
1332 OldIdxVNI = OldIdxIn->valno;
1333
1334 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1335 LiveRange::iterator Prev = std::prev(OldIdxIn);
1336 if (OldIdxIn != LR.begin() &&
1337 SlotIndex::isEarlierInstr(NewIdx, Prev->end)) {
1338 // If the segment before OldIdx read a value defined earlier than
1339 // NewIdx, the moved instruction also reads and forwards that
1340 // value. Extend the lifetime of the new def point.
1341
1342 // Extend to where the previous range started, unless there is
1343 // another redef first.
1344 NewDefEndPoint = std::min(OldIdxIn->start,
1345 std::next(NewIdxOut)->start);
1346 }
1347
1348 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1349 OldIdxOut->valno->def = OldIdxIn->start;
1350 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1351 OldIdxOut->valno);
1352 // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1353 // We Slide [NewIdxIn, OldIdxIn) down one position.
1354 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1355 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1356 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1357 // NewIdxIn is now considered undef so we can reuse it for the moved
1358 // value.
1359 LiveRange::iterator NewSegment = NewIdxIn;
1360 LiveRange::iterator Next = std::next(NewSegment);
1361 if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1362 // There is no gap between NewSegment and its predecessor.
1363 *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1364 Next->valno);
1365
1366 *Next = LiveRange::Segment(SplitPos, NewDefEndPoint, OldIdxVNI);
1367 Next->valno->def = SplitPos;
1368 } else {
1369 // There is a gap between NewSegment and its predecessor
1370 // Value becomes live in.
1371 *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1372 NewSegment->valno->def = SplitPos;
1373 }
1374 } else {
1375 // Leave the end point of a live def.
1376 OldIdxOut->start = NewIdxDef;
1377 OldIdxVNI->def = NewIdxDef;
1378 if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
1379 OldIdxIn->end = NewIdxDef;
1380 }
1381 } else if (OldIdxIn != E
1382 && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)
1383 && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {
1384 // OldIdxVNI is a dead def that has been moved into the middle of
1385 // another value in LR. That can happen when LR is a whole register,
1386 // but the dead def is a write to a subreg that is dead at NewIdx.
1387 // The dead def may have been moved across other values
1388 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1389 // down one position.
1390 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1391 // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1392 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1393 // Modify the segment at NewIdxOut and the following segment to meet at
1394 // the point of the dead def, with the following segment getting
1395 // OldIdxVNI as its value number.
1396 *NewIdxOut = LiveRange::Segment(
1397 NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
1398 *(NewIdxOut + 1) = LiveRange::Segment(
1399 NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1400 OldIdxVNI->def = NewIdxDef;
1401 // Modify subsequent segments to be defined by the moved def OldIdxVNI.
1402 for (auto *Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)
1403 Idx->valno = OldIdxVNI;
1404 // Aggressively remove all dead flags from the former dead definition.
1405 // Kill/dead flags shouldn't be used while live intervals exist; they
1406 // will be reinserted by VirtRegRewriter.
1407 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
1408 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1409 if (MO->isReg() && !MO->isUse())
1410 MO->setIsDead(false);
1411 } else {
1412 // OldIdxVNI is a dead def. It may have been moved across other values
1413 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1414 // down one position.
1415 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1416 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1417 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1418 // OldIdxVNI can be reused now to build a new dead def segment.
1419 LiveRange::iterator NewSegment = NewIdxOut;
1420 VNInfo *NewSegmentVNI = OldIdxVNI;
1421 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1422 NewSegmentVNI);
1423 NewSegmentVNI->def = NewIdxDef;
1424 }
1425 }
1426 }
1427
1428 void updateRegMaskSlots() {
1430 llvm::lower_bound(LIS.RegMaskSlots, OldIdx);
1431 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1432 "No RegMask at OldIdx.");
1433 *RI = NewIdx.getRegSlot();
1434 assert((RI == LIS.RegMaskSlots.begin() ||
1435 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1436 "Cannot move regmask instruction above another call");
1437 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1438 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1439 "Cannot move regmask instruction below another call");
1440 }
1441
1442 // Return the last use of reg between NewIdx and OldIdx.
1443 SlotIndex findLastUseBefore(SlotIndex Before, Register Reg,
1444 LaneBitmask LaneMask) {
1445 if (Reg.isVirtual()) {
1446 SlotIndex LastUse = Before;
1447 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1448 if (MO.isUndef())
1449 continue;
1450 unsigned SubReg = MO.getSubReg();
1451 if (SubReg != 0 && LaneMask.any()
1452 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1453 continue;
1454
1455 const MachineInstr &MI = *MO.getParent();
1457 if (InstSlot > LastUse && InstSlot < OldIdx)
1458 LastUse = InstSlot.getRegSlot();
1459 }
1460 return LastUse;
1461 }
1462
1463 // This is a regunit interval, so scanning the use list could be very
1464 // expensive. Scan upwards from OldIdx instead.
1465 assert(Before < OldIdx && "Expected upwards move");
1466 SlotIndexes *Indexes = LIS.getSlotIndexes();
1468
1469 // OldIdx may not correspond to an instruction any longer, so set MII to
1470 // point to the next instruction after OldIdx, or MBB->end().
1472 if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1473 Indexes->getNextNonNullIndex(OldIdx)))
1474 if (MI->getParent() == MBB)
1475 MII = MI;
1476
1478 while (MII != Begin) {
1479 if ((--MII)->isDebugOrPseudoInstr())
1480 continue;
1481 SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1482
1483 // Stop searching when Before is reached.
1485 return Before;
1486
1487 // Check if MII uses Reg.
1488 for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
1489 if (MO->isReg() && !MO->isUndef() && MO->getReg().isPhysical() &&
1490 TRI.hasRegUnit(MO->getReg(), Reg))
1491 return Idx.getRegSlot();
1492 }
1493 // Didn't reach Before. It must be the first instruction in the block.
1494 return Before;
1495 }
1496};
1497
1499 // It is fine to move a bundle as a whole, but not an individual instruction
1500 // inside it.
1501 assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) &&
1502 "Cannot move instruction in bundle");
1503 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1505 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1506 assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1507 OldIndex < getMBBEndIdx(MI.getParent()) &&
1508 "Cannot handle moves across basic block boundaries.");
1509
1510 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1511 HME.updateAllRanges(&MI);
1512}
1513
1515 bool UpdateFlags) {
1516 assert((BundleStart.getOpcode() == TargetOpcode::BUNDLE) &&
1517 "Bundle start is not a bundle");
1519 const SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(BundleStart);
1520 auto BundleEnd = getBundleEnd(BundleStart.getIterator());
1521
1522 auto I = BundleStart.getIterator();
1523 I++;
1524 while (I != BundleEnd) {
1525 if (!Indexes->hasIndex(*I))
1526 continue;
1527 SlotIndex OldIndex = Indexes->getInstructionIndex(*I, true);
1528 ToProcess.push_back(OldIndex);
1529 Indexes->removeMachineInstrFromMaps(*I, true);
1530 I++;
1531 }
1532 for (SlotIndex OldIndex : ToProcess) {
1533 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1534 HME.updateAllRanges(&BundleStart);
1535 }
1536
1537 // Fix up dead defs
1538 const SlotIndex Index = getInstructionIndex(BundleStart);
1539 for (unsigned Idx = 0, E = BundleStart.getNumOperands(); Idx != E; ++Idx) {
1540 MachineOperand &MO = BundleStart.getOperand(Idx);
1541 if (!MO.isReg())
1542 continue;
1543 Register Reg = MO.getReg();
1544 if (Reg.isVirtual() && hasInterval(Reg) && !MO.isUndef()) {
1545 LiveInterval &LI = getInterval(Reg);
1546 LiveQueryResult LRQ = LI.Query(Index);
1547 if (LRQ.isDeadDef())
1548 MO.setIsDead();
1549 }
1550 }
1551}
1552
1553void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1555 const SlotIndex EndIdx, LiveRange &LR,
1556 const Register Reg,
1557 LaneBitmask LaneMask) {
1558 LiveInterval::iterator LII = LR.find(EndIdx);
1559 SlotIndex lastUseIdx;
1560 if (LII != LR.end() && LII->start < EndIdx) {
1561 lastUseIdx = LII->end;
1562 } else if (LII == LR.begin()) {
1563 // We may not have a liverange at all if this is a subregister untouched
1564 // between \p Begin and \p End.
1565 } else {
1566 --LII;
1567 }
1568
1569 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1570 --I;
1571 MachineInstr &MI = *I;
1572 if (MI.isDebugOrPseudoInstr())
1573 continue;
1574
1575 SlotIndex instrIdx = getInstructionIndex(MI);
1576 bool isStartValid = getInstructionFromIndex(LII->start);
1577 bool isEndValid = getInstructionFromIndex(LII->end);
1578
1579 // FIXME: This doesn't currently handle early-clobber or multiple removed
1580 // defs inside of the region to repair.
1581 for (const MachineOperand &MO : MI.operands()) {
1582 if (!MO.isReg() || MO.getReg() != Reg)
1583 continue;
1584
1585 unsigned SubReg = MO.getSubReg();
1586 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1587 if ((Mask & LaneMask).none())
1588 continue;
1589
1590 if (MO.isDef()) {
1591 if (!isStartValid) {
1592 if (LII->end.isDead()) {
1593 LII = LR.removeSegment(LII, true);
1594 if (LII != LR.begin())
1595 --LII;
1596 } else {
1597 LII->start = instrIdx.getRegSlot();
1598 LII->valno->def = instrIdx.getRegSlot();
1599 if (MO.getSubReg() && !MO.isUndef())
1600 lastUseIdx = instrIdx.getRegSlot();
1601 else
1602 lastUseIdx = SlotIndex();
1603 continue;
1604 }
1605 }
1606
1607 if (!lastUseIdx.isValid()) {
1608 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1609 LiveRange::Segment S(instrIdx.getRegSlot(),
1610 instrIdx.getDeadSlot(), VNI);
1611 LII = LR.addSegment(S);
1612 } else if (LII->start != instrIdx.getRegSlot()) {
1613 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1614 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1615 LII = LR.addSegment(S);
1616 }
1617
1618 if (MO.getSubReg() && !MO.isUndef())
1619 lastUseIdx = instrIdx.getRegSlot();
1620 else
1621 lastUseIdx = SlotIndex();
1622 } else if (MO.isUse()) {
1623 // FIXME: This should probably be handled outside of this branch,
1624 // either as part of the def case (for defs inside of the region) or
1625 // after the loop over the region.
1626 if (!isEndValid && !LII->end.isBlock())
1627 LII->end = instrIdx.getRegSlot();
1628 if (!lastUseIdx.isValid())
1629 lastUseIdx = instrIdx.getRegSlot();
1630 }
1631 }
1632 }
1633
1634 bool isStartValid = getInstructionFromIndex(LII->start);
1635 if (!isStartValid && LII->end.isDead())
1636 LR.removeSegment(*LII, true);
1637}
1638
1639void
1643 ArrayRef<Register> OrigRegs) {
1644 // Find anchor points, which are at the beginning/end of blocks or at
1645 // instructions that already have indexes.
1646 while (Begin != MBB->begin() && !Indexes->hasIndex(*std::prev(Begin)))
1647 --Begin;
1648 while (End != MBB->end() && !Indexes->hasIndex(*End))
1649 ++End;
1650
1651 SlotIndex EndIdx;
1652 if (End == MBB->end())
1653 EndIdx = getMBBEndIdx(MBB).getPrevSlot();
1654 else
1655 EndIdx = getInstructionIndex(*End);
1656
1657 Indexes->repairIndexesInRange(MBB, Begin, End);
1658
1659 // Make sure a live interval exists for all register operands in the range.
1660 SmallVector<Register> RegsToRepair(OrigRegs.begin(), OrigRegs.end());
1661 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1662 --I;
1663 MachineInstr &MI = *I;
1664 if (MI.isDebugOrPseudoInstr())
1665 continue;
1666 for (const MachineOperand &MO : MI.operands()) {
1667 if (MO.isReg() && MO.getReg().isVirtual()) {
1668 Register Reg = MO.getReg();
1669 if (MO.getSubReg() && hasInterval(Reg) &&
1670 MRI->shouldTrackSubRegLiveness(Reg)) {
1671 LiveInterval &LI = getInterval(Reg);
1672 if (!LI.hasSubRanges()) {
1673 // If the new instructions refer to subregs but the old instructions
1674 // did not, throw away any old live interval so it will be
1675 // recomputed with subranges.
1676 removeInterval(Reg);
1677 } else if (MO.isDef()) {
1678 // Similarly if a subreg def has no precise subrange match then
1679 // assume we need to recompute all subranges.
1680 unsigned SubReg = MO.getSubReg();
1681 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1682 if (llvm::none_of(LI.subranges(),
1683 [Mask](LiveInterval::SubRange &SR) {
1684 return SR.LaneMask == Mask;
1685 })) {
1686 removeInterval(Reg);
1687 }
1688 }
1689 }
1690 if (!hasInterval(Reg)) {
1692 // Don't bother to repair a freshly calculated live interval.
1693 llvm::erase(RegsToRepair, Reg);
1694 }
1695 }
1696 }
1697 }
1698
1699 for (Register Reg : RegsToRepair) {
1700 if (!Reg.isVirtual())
1701 continue;
1702
1703 LiveInterval &LI = getInterval(Reg);
1704 // FIXME: Should we support undefs that gain defs?
1705 if (!LI.hasAtLeastOneValue())
1706 continue;
1707
1708 for (LiveInterval::SubRange &S : LI.subranges())
1709 repairOldRegInRange(Begin, End, EndIdx, S, Reg, S.LaneMask);
1711
1712 repairOldRegInRange(Begin, End, EndIdx, LI, Reg);
1713 }
1714}
1715
1717 for (MCRegUnit Unit : TRI->regunits(Reg)) {
1718 if (LiveRange *LR = getCachedRegUnit(Unit))
1719 if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1720 LR->removeValNo(VNI);
1721 }
1722}
1723
1725 // LI may not have the main range computed yet, but its subranges may
1726 // be present.
1727 VNInfo *VNI = LI.getVNInfoAt(Pos);
1728 if (VNI != nullptr) {
1729 assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1730 LI.removeValNo(VNI);
1731 }
1732
1733 // Also remove the value defined in subranges.
1734 for (LiveInterval::SubRange &S : LI.subranges()) {
1735 if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1736 if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1737 S.removeValNo(SVNI);
1738 }
1740}
1741
1744 ConnectedVNInfoEqClasses ConEQ(*this);
1745 unsigned NumComp = ConEQ.Classify(LI);
1746 if (NumComp <= 1)
1747 return;
1748 LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
1749 Register Reg = LI.reg();
1750 for (unsigned I = 1; I < NumComp; ++I) {
1751 Register NewVReg = MRI->cloneVirtualRegister(Reg);
1752 LiveInterval &NewLI = createEmptyInterval(NewVReg);
1753 SplitLIs.push_back(&NewLI);
1754 }
1755 ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1756}
1757
1759 assert(LICalc && "LICalc not initialized.");
1760 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1762}
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:529
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.
bool End
Definition: ELF_riscv.cpp:480
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:293
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:269
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:154
iterator begin() const
Definition: ArrayRef.h:153
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:341
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:335
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:725
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...
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:694
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Register reg() const
Definition: LiveInterval.h:718
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:810
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:782
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().
LiveInterval & getOrCreateEmptyInterval(Register Reg)
Return an existing interval for Reg.
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:542
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
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
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 interval from this live range.
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.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
iterator_range< MCSuperRegIterator > superregs_inclusive(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, including Reg.
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:33
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...
double 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:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:544
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:547
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:554
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
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:95
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:179
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
Definition: SlotIndexes.h:212
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:245
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:185
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:133
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:191
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:227
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
Definition: SlotIndexes.h:275
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:240
SlotIndexes pass.
Definition: SlotIndexes.h:300
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late=false)
Insert the given machine instruction into the mapping.
Definition: SlotIndexes.h:523
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:507
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:441
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:462
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
Definition: SlotIndexes.h:395
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:371
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:452
bool hasIndex(const MachineInstr &instr) const
Returns true if the given machine instr is mapped to an index, otherwise returns false.
Definition: SlotIndexes.h:366
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:389
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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:586
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:981
typename SuperClass::iterator iterator
Definition: SmallVector.h:590
void resize(size_type N)
Definition: SmallVector.h:651
void push_back(const T &Elt)
Definition: SmallVector.h:426
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:299
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:109
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:121
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
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.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2068
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)
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1745
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:1963
@ 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