LLVM 24.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"
21#include "llvm/ADT/Statistic.h"
34#include "llvm/CodeGen/Passes.h"
40#include "llvm/Config/llvm-config.h"
42#include "llvm/IR/Statepoint.h"
44#include "llvm/MC/LaneBitmask.h"
46#include "llvm/Pass.h"
49#include "llvm/Support/Debug.h"
52#include <algorithm>
53#include <cassert>
54#include <cstdint>
55#include <iterator>
56#include <tuple>
57#include <utility>
58
59using namespace llvm;
60
61#define DEBUG_TYPE "regalloc"
62
63STATISTIC(NumUnreferencedIntervals,
64 "Number of intervals removed for unreferenced virtual registers");
65
66AnalysisKey LiveIntervalsAnalysis::Key;
67
71 auto Res = Result(MF, MFAM.getResult<SlotIndexesAnalysis>(MF),
73 LLVM_DEBUG(Res.dump());
74 return Res;
75}
76
80 OS << "Live intervals for machine function: " << MF.getName() << ":\n";
83}
84
88 "Live Interval Analysis", false, false)
92 "Live Interval Analysis", false, true)
93
95 LIS.Indexes = &getAnalysis<SlotIndexesWrapperPass>().getSI();
96 LIS.DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
97 LIS.analyze(MF);
99 return false;
100}
101
102#ifndef NDEBUG
104 "precompute-phys-liveness", cl::Hidden,
105 cl::desc("Eagerly compute live intervals for all physreg units."));
106#else
107static bool EnablePrecomputePhysRegs = false;
108#endif // NDEBUG
109
119
122
124
126 MachineFunction &MF, const PreservedAnalyses &PA,
127 MachineFunctionAnalysisManager::Invalidator &Inv) {
128 auto PAC = PA.getChecker<LiveIntervalsAnalysis>();
129
130 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<MachineFunction>>())
131 return true;
132
133 // LiveIntervals holds pointers to these results, so check for their
134 // invalidation.
135 return Inv.invalidate<SlotIndexesAnalysis>(MF, PA) ||
136 Inv.invalidate<MachineDominatorTreeAnalysis>(MF, PA);
137}
138
139void LiveIntervals::clear() {
140 // Free the live intervals themselves.
141 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i) {
142 if (LiveInterval *LI = VirtRegIntervals[Register::index2VirtReg(i)])
143 LI->~LiveInterval();
144 }
145 VirtRegIntervals.clear();
146 RegMaskSlots.clear();
147 RegMaskBits.clear();
148 RegMaskBlocks.clear();
149 ShrinkBlocks.clear();
150
151 for (LiveRange *LR : RegUnitRanges) {
152 if (LR)
153 LR->~LiveRange();
154 }
155 RegUnitRanges.clear();
156
157 IntervalRecycler.clear(RangeAllocator);
158 RegUnitRangeRecycler.clear(RangeAllocator);
159 RangeAllocator.Reset();
160
161 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
162 VNInfoAllocator.Reset();
163}
164
165void LiveIntervals::analyze(MachineFunction &fn) {
166 MF = &fn;
167 MRI = &MF->getRegInfo();
168 TRI = MF->getSubtarget().getRegisterInfo();
169 TII = MF->getSubtarget().getInstrInfo();
170
171 if (!LICalc)
172 LICalc = std::make_unique<LiveIntervalCalc>();
173
174 // Allocate space for all virtual registers.
175 VirtRegIntervals.resize(MRI->getNumVirtRegs());
176 ShrinkBlocks.assign(MF->getNumBlockIDs(), {});
177
178 computeVirtRegs();
179 computeRegMasks();
180 computeLiveInRegUnits();
181
183 // For stress testing, precompute live ranges of all physical register
184 // units, including reserved registers.
185 for (MCRegUnit Unit : TRI->regunits())
186 getRegUnit(Unit);
187 }
188}
189
191 unsigned Removed = 0;
192 for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) {
194 if (hasInterval(Reg) && MRI->reg_empty(Reg)) {
195 removeInterval(Reg);
196 ++Removed;
197 }
198 }
199 NumUnreferencedIntervals += Removed;
200 return Removed;
201}
202
204 OS << "********** INTERVALS **********\n";
205
206 // Dump the regunits.
207 for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
208 if (LiveRange *LR = RegUnitRanges[Unit])
209 OS << printRegUnit(static_cast<MCRegUnit>(Unit), TRI) << ' ' << *LR
210 << '\n';
211
212 // Dump the virtregs.
213 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
215 if (hasInterval(Reg))
216 OS << getInterval(Reg) << '\n';
217 }
218
219 OS << "RegMasks:";
220 for (SlotIndex Idx : RegMaskSlots)
221 OS << ' ' << Idx;
222 OS << '\n';
223
224 printInstrs(OS);
225}
226
227void LiveIntervals::printInstrs(raw_ostream &OS) const {
228 OS << "********** MACHINEINSTRS **********\n";
229 MF->print(OS, Indexes);
230}
231
232#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
233LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
234 printInstrs(dbgs());
235}
236#endif
237
238#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
240#endif
241
242LiveInterval *LiveIntervals::createInterval(Register reg) {
243 float Weight = reg.isPhysical() ? huge_valf : 0.0F;
244 return new (IntervalRecycler.Allocate(RangeAllocator))
245 LiveInterval(reg, Weight);
246}
247
248LiveRange *LiveIntervals::createRegUnitRange() {
249 return new (RegUnitRangeRecycler.Allocate(RangeAllocator)) LiveRange();
250}
251
252/// Compute the live interval of a virtual register, based on defs and uses.
253bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
254 assert(LICalc && "LICalc not initialized.");
255 assert(LI.empty() && "Should only compute empty intervals.");
256 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
257 LICalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg()));
258 return computeDeadValues(LI, nullptr);
259}
260
261void LiveIntervals::computeVirtRegs() {
262 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
264 if (MRI->reg_nodbg_empty(Reg))
265 continue;
266 LiveInterval &LI = createEmptyInterval(Reg);
267 bool NeedSplit = computeVirtRegInterval(LI);
268 if (NeedSplit) {
270 splitSeparateComponents(LI, SplitLIs);
271 }
272 }
273}
274
275void LiveIntervals::computeRegMasks() {
276 RegMaskBlocks.resize(MF->getNumBlockIDs());
277
278 // Find all instructions with regmask operands.
279 for (const MachineBasicBlock &MBB : *MF) {
280 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
281 RMB.first = RegMaskSlots.size();
282
283 // Some block starts, such as EH funclets, create masks.
284 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
285 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
286 RegMaskBits.push_back(Mask);
287 }
288
289 // Unwinders may clobber additional registers.
290 // FIXME: This functionality can possibly be merged into
291 // MachineBasicBlock::getBeginClobberMask().
292 if (MBB.isEHPad())
293 if (auto *Mask = TRI->getCustomEHPadPreservedMask(*MBB.getParent())) {
294 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
295 RegMaskBits.push_back(Mask);
296 }
297
298 for (const MachineInstr &MI : MBB) {
299 for (const MachineOperand &MO : MI.operands()) {
300 if (!MO.isRegMask())
301 continue;
302 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
303 RegMaskBits.push_back(MO.getRegMask());
304 }
305 }
306
307 // Some block ends, such as funclet returns, create masks. Put the mask on
308 // the last instruction of the block, because MBB slot index intervals are
309 // half-open.
310 if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
311 assert(!MBB.empty() && "empty return block?");
312 RegMaskSlots.push_back(
313 Indexes->getInstructionIndex(MBB.back()).getRegSlot());
314 RegMaskBits.push_back(Mask);
315 }
316
317 // Compute the number of register mask instructions in this block.
318 RMB.second = RegMaskSlots.size() - RMB.first;
319 }
320}
321
322void LiveIntervals::reassignRegMaskSlots(MachineBasicBlock &Orig,
323 MachineBasicBlock &SplitBB) {
324 assert(&Orig != &SplitBB && "expected distinct blocks");
325 std::pair<unsigned, unsigned> &OrigRMB = RegMaskBlocks[Orig.getNumber()];
326 std::pair<unsigned, unsigned> &SplitRMB = RegMaskBlocks[SplitBB.getNumber()];
327
328 // RegMaskSlots is sorted, so the slots that moved are those at or after
329 // SplitBB's start index.
330 ArrayRef<SlotIndex> OrigSlots =
331 getRegMaskSlots().slice(OrigRMB.first, OrigRMB.second);
332 unsigned KeptCount = llvm::lower_bound(OrigSlots, getMBBStartIdx(&SplitBB)) -
333 OrigSlots.begin();
334 if (KeptCount == OrigRMB.second)
335 return; // No regmask slots moved into SplitBB.
336
337 SplitRMB.first = OrigRMB.first + KeptCount;
338 SplitRMB.second = OrigRMB.second - KeptCount;
339 OrigRMB.second = KeptCount;
340}
341
342void LiveIntervals::insertMBBInMapsImpl(
343 MachineBasicBlock *MBB, [[maybe_unused]] bool AssumeRegMaskEmpty) {
344#ifdef EXPENSIVE_CHECKS
345 assert((!AssumeRegMaskEmpty ||
346 none_of(*MBB,
347 [](const MachineInstr &MI) {
348 return any_of(MI.operands(), [](const MachineOperand &MO) {
349 return MO.isRegMask();
350 });
351 })) &&
352 "insertMBBInMaps expects a block with no regmask operands; use "
353 "LiveIntervals::splitAt() to split a block containing calls");
354#endif
355 Indexes->insertMBBInMaps(MBB);
356 assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() &&
357 "Blocks must be added in order.");
358 RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0));
359 ShrinkBlocks.emplace_back();
360}
361
362//===----------------------------------------------------------------------===//
363// Register Unit Liveness
364//===----------------------------------------------------------------------===//
365//
366// Fixed interference typically comes from ABI boundaries: Function arguments
367// and return values are passed in fixed registers, and so are exception
368// pointers entering landing pads. Certain instructions require values to be
369// present in specific registers. That is also represented through fixed
370// interference.
371//
372
373/// Compute the live range of a register unit, based on the uses and defs of
374/// aliasing registers. The range should be empty, or contain only dead
375/// phi-defs from ABI blocks.
376void LiveIntervals::computeRegUnitRange(LiveRange &LR, MCRegUnit Unit) {
377 assert(LICalc && "LICalc not initialized.");
378 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
379
380 // The physregs aliasing Unit are the roots and their super-registers.
381 // Create all values as dead defs before extending to uses. Note that roots
382 // may share super-registers. That's OK because createDeadDef() is
383 // idempotent. It is very rare for a register unit to have multiple roots, so
384 // uniquing super-registers is probably not worthwhile.
385 bool IsReserved = false;
387 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
388 bool IsRootReserved = true;
389 for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {
390 for (const MachineOperand &MO : MRI->def_operands(Reg))
391 DefIdxs.push_back(Indexes->getInstructionIndex(*MO.getParent())
392 .getRegSlot(MO.isEarlyClobber()));
393 // A register unit is considered reserved if all its roots and all their
394 // super registers are reserved.
395 if (!MRI->isReserved(Reg))
396 IsRootReserved = false;
397 }
398 IsReserved |= IsRootReserved;
399 }
400 assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
401 "reserved computation mismatch");
402
403 llvm::sort(DefIdxs);
404 for (SlotIndex DefIdx : DefIdxs)
405 LR.createDeadDef(DefIdx, VNInfoAllocator);
406
407 // Now extend LR to reach all uses.
408 // Ignore uses of reserved registers. We only track defs of those.
409 if (!IsReserved) {
410 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
411 for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {
412 if (!MRI->reg_empty(Reg))
413 LICalc->extendToUses(LR, Reg);
414 }
415 }
416 }
417}
418
419/// Precompute the live ranges of any register units that are live-in to an ABI
420/// block somewhere. Register values can appear without a corresponding def when
421/// entering the entry block or a landing pad.
422void LiveIntervals::computeLiveInRegUnits() {
423 RegUnitRanges.resize(TRI->getNumRegUnits());
424 LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
425
426 // Keep track of the live range sets allocated.
428
429 // Check all basic blocks for live-ins.
430 for (const MachineBasicBlock &MBB : *MF) {
431 // We only care about ABI blocks: Entry + landing pads.
432 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
433 continue;
434
435 // Create phi-defs at Begin for all live-in registers.
436 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
437 LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
438 for (const auto &LI : MBB.liveins()) {
439 for (MCRegUnit Unit : TRI->regunits(LI.PhysReg)) {
440 LiveRange *LR = RegUnitRanges[static_cast<unsigned>(Unit)];
441 if (!LR) {
442 LR = RegUnitRanges[static_cast<unsigned>(Unit)] =
443 createRegUnitRange();
444 NewRanges.push_back(Unit);
445 }
446 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
447 (void)VNI;
448 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
449 }
450 }
451 LLVM_DEBUG(dbgs() << '\n');
452 }
453 LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
454
455 // Compute the 'normal' part of the ranges.
456 for (MCRegUnit Unit : NewRanges)
457 computeRegUnitRange(*RegUnitRanges[static_cast<unsigned>(Unit)], Unit);
458}
459
462 for (VNInfo *VNI : VNIs) {
463 if (VNI->isUnused())
464 continue;
465 SlotIndex Def = VNI->def;
466 LR.segments.push_back(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
467 }
468
470 [](const LiveRange::Segment &A, const LiveRange::Segment &B) {
471 return A.start < B.start;
472 });
473}
474
475void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
476 ShrinkToUsesWorkList &WorkList,
477 Register Reg, LaneBitmask LaneMask) {
478 // Keep track of the PHIs that are in use.
479 SmallPtrSet<VNInfo*, 8> UsedPHIs;
480 // Start a new tag; entries from earlier calls are now stale.
481 if (++ShrinkTag == 0) {
482 ShrinkBlocks.assign(ShrinkBlocks.size(), {});
483 ShrinkTag = 1;
484 }
485
486 auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
487 -> const LiveRange& {
488 if (M.none())
489 return I;
490 for (const LiveInterval::SubRange &SR : I.subranges()) {
491 if ((SR.LaneMask & M).any()) {
492 assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
493 return SR;
494 }
495 }
496 llvm_unreachable("Subrange for mask not found");
497 };
498
499 const LiveInterval &LI = getInterval(Reg);
500 const LiveRange &OldRange = getSubRange(LI, LaneMask);
501
502 // Live-in segments are found in worklist order, so collect them (at most one
503 // per block) and add them all at the end.
505
506 // Extend intervals to reach all uses in WorkList.
507 while (!WorkList.empty()) {
508 SlotIndex Idx = WorkList.back().first;
509 VNInfo *VNI = WorkList.back().second;
510 WorkList.pop_back();
511 const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
512 SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
513
514 // Extend the live range for VNI to be live at Idx. Segments only holds def
515 // segments during the walk, and none extend past their block.
517 Segments, [Idx](const LiveRange::Segment &S) { return S.start < Idx; });
518 if (Def != Segments.begin() && (--Def)->start >= BlockStart) {
519 assert(Def->valno == VNI && "Unexpected existing value number");
520 Def->end = std::max(Def->end, Idx);
521 // Is this a PHIDef we haven't seen before?
522 if (!VNI->isPHIDef() || VNI->def != BlockStart ||
523 !UsedPHIs.insert(VNI).second)
524 continue;
525 // The PHI is live, make sure the predecessors are live-out.
526 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
527 unsigned &Tag = ShrinkBlocks[Pred->getNumber()].LiveOutTag;
528 if (Tag == ShrinkTag)
529 continue;
530 Tag = ShrinkTag;
531 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
532 // A predecessor is not required to have a live-out value for a PHI.
533 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
534 WorkList.push_back(std::make_pair(Stop, PVNI));
535 }
536 continue;
537 }
538
539 ShrinkBlockState &BS = ShrinkBlocks[MBB->getNumber()];
540 if (BS.LiveInTag == ShrinkTag) {
541 LiveRange::Segment &S = LiveIns[BS.LiveIn];
542 assert(S.valno == VNI && "Unexpected existing value number");
543 S.end = std::max(S.end, Idx);
544 continue;
545 }
546
547 BS.LiveInTag = ShrinkTag;
548 BS.LiveIn = LiveIns.size();
549
550 // VNI is live-in to MBB.
551 LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
552 LiveIns.push_back(LiveRange::Segment(BlockStart, Idx, VNI));
553
554 // Make sure VNI is live-out from the predecessors.
555 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
556 unsigned &Tag = ShrinkBlocks[Pred->getNumber()].LiveOutTag;
557 if (Tag == ShrinkTag)
558 continue;
559 Tag = ShrinkTag;
560 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
561 if (VNInfo *OldVNI =
562 LaneMask.none() ? VNI : OldRange.getVNInfoBefore(Stop)) {
563 assert(OldVNI == VNI && "Wrong value out of predecessor");
564 (void)OldVNI;
565 WorkList.push_back(std::make_pair(Stop, VNI));
566 } else {
567#ifndef NDEBUG
568 // There was no old VNI. Verify that Stop is jointly dominated
569 // by <undef>s for this live range.
571 LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
572 assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
573 "Missing value out of predecessor for subrange");
574#endif
575 }
576 }
577 }
578
579 llvm::sort(LiveIns,
580 [](const LiveRange::Segment &A, const LiveRange::Segment &B) {
581 return A.start < B.start;
582 });
583 Segments.addSegments(LiveIns);
584}
585
588 LaneBitmask SubRangeMask) {
589 LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
590 assert(li->reg().isVirtual() && "Can only shrink virtual registers");
591
592 // Shrink subregister live ranges.
593 if (li->hasSubRanges() && SubRangeMask.any()) {
594 SubRangeUseList Uses;
595 collectSubRangeUses(li->reg(), Uses);
596 bool NeedsCleanup = false;
597 for (LiveInterval::SubRange &S : li->subranges()) {
598 if ((S.LaneMask & SubRangeMask).none())
599 continue;
600 shrinkSubRangeToUses(S, li->reg(), Uses);
601 if (S.empty())
602 NeedsCleanup = true;
603 }
604
605 if (NeedsCleanup)
607 }
608
609 // Find all the values used, including PHI kills.
610 ShrinkToUsesWorkList WorkList;
611
612 // Visit all instructions reading li->reg().
613 Register Reg = li->reg();
614 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
615 if (UseMI.isDebugInstr() || !UseMI.readsVirtualRegister(Reg))
616 continue;
618 LiveQueryResult LRQ = li->Query(Idx);
619 VNInfo *VNI = LRQ.valueIn();
620 if (!VNI) {
621 // This shouldn't happen: readsVirtualRegister returns true, but there is
622 // no live value. It is likely caused by a target getting <undef> flags
623 // wrong.
625 dbgs() << Idx << '\t' << UseMI
626 << "Warning: Instr claims to read non-existent value in "
627 << *li << '\n');
628 continue;
629 }
630 // Special case: An early-clobber tied operand reads and writes the
631 // register one slot early.
632 if (VNInfo *DefVNI = LRQ.valueDefined())
633 Idx = DefVNI->def;
634
635 WorkList.push_back(std::make_pair(Idx, VNI));
636 }
637
638 // Create new live ranges with only minimal live segments per def.
639 LiveRange NewLR;
640 createSegmentsForValues(NewLR, li->vnis());
641 extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
642
643 // Move the trimmed segments back.
644 li->segments.swap(NewLR.segments);
645
646 // Handle dead values.
647 bool CanSeparate = computeDeadValues(*li, dead);
648 LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
649 return CanSeparate;
650}
651
652bool LiveIntervals::computeDeadValues(LiveInterval &LI,
654 bool MayHaveSplitComponents = false;
655
656 for (VNInfo *VNI : LI.valnos) {
657 if (VNI->isUnused())
658 continue;
659 SlotIndex Def = VNI->def;
661 assert(I != LI.end() && "Missing segment for VNI");
662
663 // Is the register live before? Otherwise we may have to add a read-undef
664 // flag for subregister defs.
665 Register VReg = LI.reg();
666 if (MRI->shouldTrackSubRegLiveness(VReg)) {
667 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
669 MI->setRegisterDefReadUndef(VReg);
670 }
671 }
672
673 if (I->end != Def.getDeadSlot())
674 continue;
675 if (VNI->isPHIDef()) {
676 // This is a dead PHI. Remove it.
677 VNI->markUnused();
678 LI.removeSegment(I);
679 LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
680 } else {
681 // This is a dead def. Make sure the instruction knows.
682 MachineInstr *MI = getInstructionFromIndex(Def);
683 assert(MI && "No instruction defining live value");
684 MI->addRegisterDead(LI.reg(), TRI);
685
686 if (dead && MI->allDefsAreDead()) {
687 LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
688 dead->push_back(MI);
689 }
690 }
691 MayHaveSplitComponents = true;
692 }
693 return MayHaveSplitComponents;
694}
695
697 SubRangeUseList Uses;
698 collectSubRangeUses(Reg, Uses);
699 shrinkSubRangeToUses(SR, Reg, Uses);
700}
701
702void LiveIntervals::collectSubRangeUses(Register Reg,
703 SubRangeUseList &Uses) const {
704 for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
705 // Skip "undef" uses.
706 if (!MO.readsReg())
707 continue;
708 unsigned SubReg = MO.getSubReg();
709 LaneBitmask LaneMask =
710 SubReg ? TRI->getSubRegIndexLaneMask(SubReg) : LaneBitmask::getAll();
711 // Merge adjacent operands of the same instruction.
712 SlotIndex Idx = getInstructionIndex(*MO.getParent()).getRegSlot();
713 if (!Uses.empty() && Uses.back().first == Idx) {
714 Uses.back().second |= LaneMask;
715 continue;
716 }
717 Uses.emplace_back(Idx, LaneMask);
718 }
719}
720
721void LiveIntervals::shrinkSubRangeToUses(LiveInterval::SubRange &SR,
724 LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
725 assert(Reg.isVirtual() && "Can only shrink virtual registers");
726 // Find all the values used, including PHI kills.
727 ShrinkToUsesWorkList WorkList;
728
729 for (const SubRangeUse &Use : Uses) {
730 // Maybe the instruction only reads subregisters we don't care about.
731 if ((Use.second & SR.LaneMask).none())
732 continue;
733
734 SlotIndex Idx = Use.first;
735 LiveQueryResult LRQ = SR.Query(Idx);
736 VNInfo *VNI = LRQ.valueIn();
737 // For Subranges it is possible that only undef values are left in that
738 // part of the subregister, so there is no real liverange at the use
739 if (!VNI)
740 continue;
741
742 // Special case: An early-clobber tied operand reads and writes the
743 // register one slot early.
744 if (VNInfo *DefVNI = LRQ.valueDefined())
745 Idx = DefVNI->def;
746
747 WorkList.push_back(std::make_pair(Idx, VNI));
748 }
749
750 // Create a new live ranges with only minimal live segments per def.
751 LiveRange NewLR;
752 createSegmentsForValues(NewLR, SR.vnis());
753 extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
754
755 // Move the trimmed ranges back.
756 SR.segments.swap(NewLR.segments);
757
758 // Remove dead PHI value numbers
759 for (VNInfo *VNI : SR.valnos) {
760 if (VNI->isUnused())
761 continue;
762 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
763 assert(Segment != nullptr && "Missing segment for VNI");
764 if (Segment->end != VNI->def.getDeadSlot())
765 continue;
766 if (VNI->isPHIDef()) {
767 // This is a dead PHI. Remove it.
768 LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
769 << " may separate interval\n");
770 VNI->markUnused();
771 SR.removeSegment(*Segment);
772 }
773 }
774
775 LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
776}
777
779 ArrayRef<SlotIndex> Indices,
780 ArrayRef<SlotIndex> Undefs) {
781 assert(LICalc && "LICalc not initialized.");
782 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
783 for (SlotIndex Idx : Indices)
784 LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
785}
786
788 SmallVectorImpl<SlotIndex> *EndPoints) {
789 LiveQueryResult LRQ = LR.Query(Kill);
790 // LR may have liveness reachable from early clobber slot, which may be
791 // only live-in instead of live-out of the instruction.
792 // For example, LR =[1r, 3r), Kill = 3e, we have to prune [3e, 3r) of LR.
793 VNInfo *VNI = LRQ.valueOutOrDead() ? LRQ.valueOutOrDead() : LRQ.valueIn();
794 if (!VNI)
795 return;
796
797 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
798 SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
799
800 // If VNI isn't live out from KillMBB, the value is trivially pruned.
801 if (LRQ.endPoint() < MBBEnd) {
802 LR.removeSegment(Kill, LRQ.endPoint());
803 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
804 return;
805 }
806
807 // VNI is live out of KillMBB.
808 LR.removeSegment(Kill, MBBEnd);
809 if (EndPoints) EndPoints->push_back(MBBEnd);
810
811 // Find all blocks that are reachable from KillMBB without leaving VNI's live
812 // range. It is possible that KillMBB itself is reachable, so start a DFS
813 // from each successor.
815 VisitedTy Visited;
816 for (MachineBasicBlock *Succ : KillMBB->successors()) {
818 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
819 I != E;) {
821
822 // Check if VNI is live in to MBB.
823 SlotIndex MBBStart, MBBEnd;
824 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
825 LiveQueryResult LRQ = LR.Query(MBBStart);
826 if (LRQ.valueIn() != VNI) {
827 // This block isn't part of the VNI segment. Prune the search.
828 I.skipChildren();
829 continue;
830 }
831
832 // Prune the search if VNI is killed in MBB.
833 if (LRQ.endPoint() < MBBEnd) {
834 LR.removeSegment(MBBStart, LRQ.endPoint());
835 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
836 I.skipChildren();
837 continue;
838 }
839
840 // VNI is live through MBB.
841 LR.removeSegment(MBBStart, MBBEnd);
842 if (EndPoints) EndPoints->push_back(MBBEnd);
843 ++I;
844 }
845 }
846}
847
848//===----------------------------------------------------------------------===//
849// Register allocator hooks.
850//
851
853 // Keep track of regunit ranges.
855
856 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
858 if (MRI->reg_nodbg_empty(Reg))
859 continue;
860 const LiveInterval &LI = getInterval(Reg);
861 if (LI.empty())
862 continue;
863
864 // Target may have not allocated this yet.
865 Register PhysReg = VRM->getPhys(Reg);
866 if (!PhysReg)
867 continue;
868
869 // Find the regunit intervals for the assigned register. They may overlap
870 // the virtual register live range, cancelling any kills.
871 RU.clear();
872 LaneBitmask ArtificialLanes;
873 for (MCRegUnitMaskIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
874 auto [Unit, Bitmask] = *UI;
875 // Record lane mask for all artificial RegUnits for this physreg.
876 if (TRI->isArtificialRegUnit(Unit))
877 ArtificialLanes |= Bitmask;
878 const LiveRange &RURange = getRegUnit(Unit);
879 if (RURange.empty())
880 continue;
881 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
882 }
883 // Every instruction that kills Reg corresponds to a segment range end
884 // point.
885 for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
886 ++RI) {
887 // A block index indicates an MBB edge.
888 if (RI->end.isBlock())
889 continue;
891 if (!MI)
892 continue;
893
894 // Check if any of the regunits are live beyond the end of RI. That could
895 // happen when a physreg is defined as a copy of a virtreg:
896 //
897 // %eax = COPY %5
898 // FOO %5 <--- MI, cancel kill because %eax is live.
899 // BAR killed %eax
900 //
901 // There should be no kill flag on FOO when %5 is rewritten as %eax.
902 for (auto &RUP : RU) {
903 const LiveRange &RURange = *RUP.first;
904 LiveRange::const_iterator &I = RUP.second;
905 if (I == RURange.end())
906 continue;
907 I = RURange.advanceTo(I, RI->end);
908 if (I == RURange.end() || I->start >= RI->end)
909 continue;
910 // I is overlapping RI.
911 goto CancelKill;
912 }
913
914 if (MRI->subRegLivenessEnabled()) {
915 // When reading a partial undefined value we must not add a kill flag.
916 // The regalloc might have used the undef lane for something else.
917 // Example:
918 // %1 = ... ; R32: %1
919 // %2:high16 = ... ; R64: %2
920 // = read killed %2 ; R64: %2
921 // = read %1 ; R32: %1
922 // The <kill> flag is correct for %2, but the register allocator may
923 // assign R0L to %1, and R0 to %2 because the low 32bits of R0
924 // are actually never written by %2. After assignment the <kill>
925 // flag at the read instruction is invalid.
926 LaneBitmask DefinedLanesMask;
927 if (LI.hasSubRanges()) {
928 // Compute a mask of lanes that are defined.
929 // Artificial regunits are not independently allocatable so the
930 // register allocator cannot have used them to represent any other
931 // values. That's why we mark them as 'defined' here, as this
932 // otherwise prevents kill flags from being added.
933 DefinedLanesMask = ArtificialLanes;
934 for (const LiveInterval::SubRange &SR : LI.subranges())
935 for (const LiveRange::Segment &Segment : SR.segments) {
936 if (Segment.start >= RI->end)
937 break;
938 if (Segment.end == RI->end) {
939 DefinedLanesMask |= SR.LaneMask;
940 break;
941 }
942 }
943 } else
944 DefinedLanesMask = LaneBitmask::getAll();
945
946 bool IsFullWrite = false;
947 for (const MachineOperand &MO : MI->operands()) {
948 if (!MO.isReg() || MO.getReg() != Reg)
949 continue;
950 if (MO.isUse()) {
951 // Reading any undefined lanes?
952 unsigned SubReg = MO.getSubReg();
953 LaneBitmask UseMask = SubReg ? TRI->getSubRegIndexLaneMask(SubReg)
954 : MRI->getMaxLaneMaskForVReg(Reg);
955 if ((UseMask & ~DefinedLanesMask).any())
956 goto CancelKill;
957 } else if (MO.getSubReg() == 0) {
958 // Writing to the full register?
959 assert(MO.isDef());
960 IsFullWrite = true;
961 }
962 }
963
964 // If an instruction writes to a subregister, a new segment starts in
965 // the LiveInterval. But as this is only overriding part of the register
966 // adding kill-flags is not correct here after registers have been
967 // assigned.
968 if (!IsFullWrite) {
969 // Next segment has to be adjacent in the subregister write case.
970 LiveRange::const_iterator N = std::next(RI);
971 if (N != LI.end() && N->start == RI->end)
972 goto CancelKill;
973 }
974 }
975
976 MI->addRegisterKilled(Reg, nullptr);
977 continue;
978CancelKill:
979 MI->clearRegisterKills(Reg, nullptr);
980 }
981 }
982}
983
986 assert(!LI.empty() && "LiveInterval is empty.");
987
988 // A local live range must be fully contained inside the block, meaning it is
989 // defined and killed at instructions, not at block boundaries. It is not
990 // live in or out of any block.
991 //
992 // It is technically possible to have a PHI-defined live range identical to a
993 // single block, but we are going to return false in that case.
994
995 SlotIndex Start = LI.beginIndex();
996 if (Start.isBlock())
997 return nullptr;
998
999 SlotIndex Stop = LI.endIndex();
1000 if (Stop.isBlock())
1001 return nullptr;
1002
1003 // getMBBFromIndex doesn't need to search the MBB table when both indexes
1004 // belong to proper instructions.
1005 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
1006 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
1007 return MBB1 == MBB2 ? MBB1 : nullptr;
1008}
1009
1010bool
1011LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
1012 for (const VNInfo *PHI : LI.valnos) {
1013 if (PHI->isUnused() || !PHI->isPHIDef())
1014 continue;
1015 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
1016 // Conservatively return true instead of scanning huge predecessor lists.
1017 if (PHIMBB->pred_size() > 100)
1018 return true;
1019 for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
1020 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
1021 return true;
1022 }
1023 return false;
1024}
1025
1026float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
1027 const MachineBlockFrequencyInfo *MBFI,
1028 const MachineInstr &MI,
1029 ProfileSummaryInfo *PSI) {
1030 return getSpillWeight(isDef, isUse, MBFI, MI.getParent(), PSI);
1031}
1032
1033float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
1034 const MachineBlockFrequencyInfo *MBFI,
1035 const MachineBasicBlock *MBB,
1036 ProfileSummaryInfo *PSI) {
1037 const auto *MF = MBB->getParent();
1038 return getSpillWeight(isDef, isUse, MBFI, MBB,
1039 PSI && llvm::shouldOptimizeForSize(MF, PSI, MBFI));
1040}
1041
1042float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
1043 const MachineBlockFrequencyInfo *MBFI,
1044 const MachineInstr &MI, bool OptForSize) {
1045 return getSpillWeight(isDef, isUse, MBFI, MI.getParent(), OptForSize);
1046}
1047
1048float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
1049 const MachineBlockFrequencyInfo *MBFI,
1050 const MachineBasicBlock *MBB,
1051 bool OptForSize) {
1052 float Weight = isDef + isUse;
1053 // When optimizing for size we only consider the codesize impact of spilling
1054 // the register, not the runtime impact.
1055 if (OptForSize)
1056 return Weight;
1057 return Weight * MBFI->getBlockFreqRelativeToEntryBlock(MBB);
1058}
1059
1063 VNInfo *VN = Interval.getNextValue(
1064 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
1066 LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
1067 getMBBEndIdx(startInst.getParent()), VN);
1068 Interval.addSegment(S);
1069
1070 return S;
1071}
1072
1073//===----------------------------------------------------------------------===//
1074// Register mask functions
1075//===----------------------------------------------------------------------===//
1076/// Check whether use of reg in MI is live-through. Live-through means that
1077/// the value is alive on exit from Machine instruction. The example of such
1078/// use is a deopt value in statepoint instruction.
1080 if (MI->getOpcode() != TargetOpcode::STATEPOINT)
1081 return false;
1082 StatepointOpers SO(MI);
1084 return false;
1085 for (unsigned Idx = SO.getNumDeoptArgsIdx(), E = SO.getNumGCPtrIdx(); Idx < E;
1086 ++Idx) {
1087 const MachineOperand &MO = MI->getOperand(Idx);
1088 if (MO.isReg() && MO.getReg() == Reg)
1089 return true;
1090 }
1091 return false;
1092}
1093
1095 BitVector &UsableRegs) {
1096 if (LI.empty())
1097 return false;
1098 LiveInterval::const_iterator LiveI = LI.begin(), LiveE = LI.end();
1099
1100 // Use a smaller arrays for local live ranges.
1101 ArrayRef<SlotIndex> Slots;
1104 Slots = getRegMaskSlotsInBlock(MBB->getNumber());
1105 Bits = getRegMaskBitsInBlock(MBB->getNumber());
1106 } else {
1107 Slots = getRegMaskSlots();
1108 Bits = getRegMaskBits();
1109 }
1110
1111 // We are going to enumerate all the register mask slots contained in LI.
1112 // Start with a binary search of RegMaskSlots to find a starting point.
1113 ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);
1114 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
1115
1116 // No slots in range, LI begins after the last call.
1117 if (SlotI == SlotE)
1118 return false;
1119
1120 bool Found = false;
1121 // Utility to union regmasks.
1122 auto unionBitMask = [&](unsigned Idx) {
1123 if (!Found) {
1124 // This is the first overlap. Initialize UsableRegs to all ones.
1125 UsableRegs.clear();
1126 UsableRegs.resize(TRI->getNumRegs(), true);
1127 Found = true;
1128 }
1129 // Remove usable registers clobbered by this mask.
1130 UsableRegs.clearBitsNotInMask(Bits[Idx]);
1131 };
1132 while (true) {
1133 assert(*SlotI >= LiveI->start);
1134 // Loop over all slots overlapping this segment.
1135 while (*SlotI < LiveI->end) {
1136 // *SlotI overlaps LI. Collect mask bits.
1137 unionBitMask(SlotI - Slots.begin());
1138 if (++SlotI == SlotE)
1139 return Found;
1140 }
1141 // If segment ends with live-through use we need to collect its regmask.
1142 if (*SlotI == LiveI->end)
1144 if (hasLiveThroughUse(MI, LI.reg()))
1145 unionBitMask(SlotI++ - Slots.begin());
1146 // *SlotI is beyond the current LI segment.
1147 // Special advance implementation to not miss next LiveI->end.
1148 if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.endIndex())
1149 return Found;
1150 while (LiveI->end < *SlotI)
1151 ++LiveI;
1152 // Advance SlotI until it overlaps.
1153 while (*SlotI < LiveI->start)
1154 if (++SlotI == SlotE)
1155 return Found;
1156 }
1157}
1158
1159//===----------------------------------------------------------------------===//
1160// IntervalUpdate class.
1161//===----------------------------------------------------------------------===//
1162
1163/// Toolkit used by handleMove to trim or extend live intervals.
1165private:
1166 LiveIntervals& LIS;
1167 const MachineRegisterInfo& MRI;
1168 const TargetRegisterInfo& TRI;
1169 SlotIndex OldIdx;
1170 SlotIndex NewIdx;
1172 bool UpdateFlags;
1173
1174public:
1175 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
1176 const TargetRegisterInfo& TRI,
1177 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
1178 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
1179 UpdateFlags(UpdateFlags) {}
1180
1181 // FIXME: UpdateFlags is a workaround that creates live intervals for all
1182 // physregs, even those that aren't needed for regalloc, in order to update
1183 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
1184 // flags, and postRA passes will use a live register utility instead.
1185 LiveRange *getRegUnitLI(MCRegUnit Unit) {
1186 if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
1187 return &LIS.getRegUnit(Unit);
1188 return LIS.getCachedRegUnit(Unit);
1189 }
1190
1191 /// Update all live ranges touched by MI, assuming a move from OldIdx to
1192 /// NewIdx.
1194 LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
1195 << *MI);
1196 bool hasRegMask = false;
1197 for (MachineOperand &MO : MI->operands()) {
1198 if (MO.isRegMask())
1199 hasRegMask = true;
1200 if (!MO.isReg())
1201 continue;
1202 if (MO.isUse()) {
1203 if (!MO.readsReg())
1204 continue;
1205 // Aggressively clear all kill flags.
1206 // They are reinserted by VirtRegRewriter.
1207 MO.setIsKill(false);
1208 }
1209
1210 Register Reg = MO.getReg();
1211 if (!Reg)
1212 continue;
1213 if (Reg.isVirtual()) {
1214 LiveInterval &LI = LIS.getInterval(Reg);
1215 if (LI.hasSubRanges()) {
1216 unsigned SubReg = MO.getSubReg();
1217 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
1218 : MRI.getMaxLaneMaskForVReg(Reg);
1219 for (LiveInterval::SubRange &S : LI.subranges()) {
1220 if ((S.LaneMask & LaneMask).none())
1221 continue;
1222 updateRange(S, VirtRegOrUnit(Reg), S.LaneMask);
1223 }
1224 }
1225 updateRange(LI, VirtRegOrUnit(Reg), LaneBitmask::getNone());
1226 // If main range has a hole and we are moving a subrange use across
1227 // the hole updateRange() cannot properly handle it since it only
1228 // gets the LiveRange and not the whole LiveInterval. As a result
1229 // we may end up with a main range not covering all subranges.
1230 // This is extremely rare case, so let's check and reconstruct the
1231 // main range.
1232 if (LI.hasSubRanges()) {
1233 unsigned SubReg = MO.getSubReg();
1234 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
1235 : MRI.getMaxLaneMaskForVReg(Reg);
1236 for (LiveInterval::SubRange &S : LI.subranges()) {
1237 if ((S.LaneMask & LaneMask).none() || LI.covers(S))
1238 continue;
1239 LI.clear();
1240 LIS.constructMainRangeFromSubranges(LI);
1241 break;
1242 }
1243 }
1244
1245 continue;
1246 }
1247
1248 // For physregs, only update the regunits that actually have a
1249 // precomputed live range.
1250 for (MCRegUnit Unit : TRI.regunits(Reg.asMCReg()))
1251 if (LiveRange *LR = getRegUnitLI(Unit))
1252 updateRange(*LR, VirtRegOrUnit(Unit), LaneBitmask::getNone());
1253 }
1254 if (hasRegMask)
1255 updateRegMaskSlots();
1256 }
1257
1258private:
1259 /// Update a single live range, assuming an instruction has been moved from
1260 /// OldIdx to NewIdx.
1261 void updateRange(LiveRange &LR, VirtRegOrUnit VRegOrUnit,
1262 LaneBitmask LaneMask) {
1263 if (!Updated.insert(&LR).second)
1264 return;
1265 LLVM_DEBUG({
1266 dbgs() << " ";
1267 if (VRegOrUnit.isVirtualReg()) {
1268 dbgs() << printReg(VRegOrUnit.asVirtualReg());
1269 if (LaneMask.any())
1270 dbgs() << " L" << PrintLaneMask(LaneMask);
1271 } else {
1272 dbgs() << printRegUnit(VRegOrUnit.asMCRegUnit(), &TRI);
1273 }
1274 dbgs() << ":\t" << LR << '\n';
1275 });
1276 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1277 handleMoveDown(LR);
1278 else
1279 handleMoveUp(LR, VRegOrUnit, LaneMask);
1280 LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');
1281 assert(LR.verify());
1282 }
1283
1284 /// Update LR to reflect an instruction has been moved downwards from OldIdx
1285 /// to NewIdx (OldIdx < NewIdx).
1286 void handleMoveDown(LiveRange &LR) {
1287 LiveRange::iterator E = LR.end();
1288 // Segment going into OldIdx.
1289 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1290
1291 // No value live before or after OldIdx? Nothing to do.
1292 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1293 return;
1294
1295 LiveRange::iterator OldIdxOut;
1296 // Do we have a value live-in to OldIdx?
1297 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1298 // If the live-in value already extends to NewIdx, there is nothing to do.
1299 if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1300 return;
1301 // Aggressively remove all kill flags from the old kill point.
1302 // Kill flags shouldn't be used while live intervals exist, they will be
1303 // reinserted by VirtRegRewriter.
1304 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1305 for (MachineOperand &MOP : mi_bundle_ops(*KillMI))
1306 if (MOP.isReg() && MOP.isUse())
1307 MOP.setIsKill(false);
1308
1309 // Is there a def before NewIdx which is not OldIdx?
1310 LiveRange::iterator Next = std::next(OldIdxIn);
1311 if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
1312 SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1313 // If we are here then OldIdx was just a use but not a def. We only have
1314 // to ensure liveness extends to NewIdx.
1315 LiveRange::iterator NewIdxIn =
1316 LR.advanceTo(Next, NewIdx.getBaseIndex());
1317 // Extend the segment before NewIdx if necessary.
1318 if (NewIdxIn == E ||
1319 !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
1320 LiveRange::iterator Prev = std::prev(NewIdxIn);
1321 Prev->end = NewIdx.getRegSlot();
1322 }
1323 // Extend OldIdxIn.
1324 OldIdxIn->end = Next->start;
1325 return;
1326 }
1327
1328 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1329 // invalid by overlapping ranges.
1330 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1331 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1332 // If this was not a kill, then there was no def and we're done.
1333 if (!isKill)
1334 return;
1335
1336 // Did we have a Def at OldIdx?
1337 OldIdxOut = Next;
1338 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1339 return;
1340 } else {
1341 OldIdxOut = OldIdxIn;
1342 }
1343
1344 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1345 // to the segment starting there.
1346 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1347 "No def?");
1348 VNInfo *OldIdxVNI = OldIdxOut->valno;
1349 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1350
1351 // If the defined value extends beyond NewIdx, just move the beginning
1352 // of the segment to NewIdx.
1353 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1354 if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1355 OldIdxVNI->def = NewIdxDef;
1356 OldIdxOut->start = OldIdxVNI->def;
1357 return;
1358 }
1359
1360 // If we are here then we have a Definition at OldIdx which ends before
1361 // NewIdx.
1362
1363 // Is there an existing Def at NewIdx?
1364 LiveRange::iterator AfterNewIdx
1365 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1366 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1367 if (!OldIdxDefIsDead &&
1368 SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
1369 // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1370 VNInfo *DefVNI;
1371 if (OldIdxOut != LR.begin() &&
1372 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1373 OldIdxOut->start)) {
1374 // There is no gap between OldIdxOut and its predecessor anymore,
1375 // merge them.
1376 LiveRange::iterator IPrev = std::prev(OldIdxOut);
1377 DefVNI = OldIdxVNI;
1378 IPrev->end = OldIdxOut->end;
1379 } else {
1380 // The value is live in to OldIdx
1381 LiveRange::iterator INext = std::next(OldIdxOut);
1382 assert(INext != E && "Must have following segment");
1383 // We merge OldIdxOut and its successor. As we're dealing with subreg
1384 // reordering, there is always a successor to OldIdxOut in the same BB
1385 // We don't need INext->valno anymore and will reuse for the new segment
1386 // we create later.
1387 DefVNI = OldIdxVNI;
1388 INext->start = OldIdxOut->end;
1389 INext->valno->def = INext->start;
1390 }
1391 // If NewIdx is behind the last segment, extend that and append a new one.
1392 if (AfterNewIdx == E) {
1393 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1394 // one position.
1395 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1396 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1397 std::copy(std::next(OldIdxOut), E, OldIdxOut);
1398 // The last segment is undefined now, reuse it for a dead def.
1399 LiveRange::iterator NewSegment = std::prev(E);
1400 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1401 DefVNI);
1402 DefVNI->def = NewIdxDef;
1403
1404 LiveRange::iterator Prev = std::prev(NewSegment);
1405 Prev->end = NewIdxDef;
1406 } else {
1407 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1408 // one position.
1409 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1410 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1411 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1412 LiveRange::iterator Prev = std::prev(AfterNewIdx);
1413 // We have two cases:
1414 if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1415 // Case 1: NewIdx is inside a liverange. Split this liverange at
1416 // NewIdxDef into the segment "Prev" followed by "NewSegment".
1417 LiveRange::iterator NewSegment = AfterNewIdx;
1418 *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1419 Prev->valno->def = NewIdxDef;
1420
1421 *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1422 DefVNI->def = Prev->start;
1423 } else {
1424 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1425 // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1426 *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1427 DefVNI->def = NewIdxDef;
1428 assert(DefVNI != AfterNewIdx->valno);
1429 }
1430 }
1431 return;
1432 }
1433
1434 if (AfterNewIdx != E &&
1435 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
1436 // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1437 // that value.
1438 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1439 LR.removeValNo(OldIdxVNI);
1440 } else {
1441 // There was no existing def at NewIdx. We need to create a dead def
1442 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1443 // a new segment at the place where we want to construct the dead def.
1444 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1445 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1446 assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1447 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1448 // We can reuse OldIdxVNI now.
1449 LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1450 VNInfo *NewSegmentVNI = OldIdxVNI;
1451 NewSegmentVNI->def = NewIdxDef;
1452 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1453 NewSegmentVNI);
1454 }
1455 }
1456
1457 /// Update LR to reflect an instruction has been moved upwards from OldIdx
1458 /// to NewIdx (NewIdx < OldIdx).
1459 void handleMoveUp(LiveRange &LR, VirtRegOrUnit VRegOrUnit,
1460 LaneBitmask LaneMask) {
1461 LiveRange::iterator E = LR.end();
1462 // Segment going into OldIdx.
1463 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1464
1465 // No value live before or after OldIdx? Nothing to do.
1466 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
1467 return;
1468
1469 LiveRange::iterator OldIdxOut;
1470 // Do we have a value live-in to OldIdx?
1471 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1472 // If the live-in value isn't killed here, then we have no Def at
1473 // OldIdx, moreover the value must be live at NewIdx so there is nothing
1474 // to do.
1475 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1476 if (!isKill)
1477 return;
1478
1479 // At this point we have to move OldIdxIn->end back to the nearest
1480 // previous use or (dead-)def but no further than NewIdx.
1481 SlotIndex DefBeforeOldIdx
1482 = std::max(OldIdxIn->start.getDeadSlot(),
1483 NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1484 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, VRegOrUnit, LaneMask);
1485
1486 // Did we have a Def at OldIdx? If not we are done now.
1487 OldIdxOut = std::next(OldIdxIn);
1488 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
1489 return;
1490 } else {
1491 OldIdxOut = OldIdxIn;
1492 OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
1493 }
1494
1495 // If we are here then there is a Definition at OldIdx. OldIdxOut points
1496 // to the segment starting there.
1497 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1498 "No def?");
1499 VNInfo *OldIdxVNI = OldIdxOut->valno;
1500 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1501 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1502
1503 // Is there an existing def at NewIdx?
1504 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1505 LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1506 if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1507 assert(NewIdxOut->valno != OldIdxVNI &&
1508 "Same value defined more than once?");
1509 // If OldIdx was a dead def remove it.
1510 if (!OldIdxDefIsDead) {
1511 // Remove segment starting at NewIdx and move begin of OldIdxOut to
1512 // NewIdx so it can take its place.
1513 OldIdxVNI->def = NewIdxDef;
1514 OldIdxOut->start = NewIdxDef;
1515 LR.removeValNo(NewIdxOut->valno);
1516 } else {
1517 // Simply remove the dead def at OldIdx.
1518 LR.removeValNo(OldIdxVNI);
1519 }
1520 } else {
1521 // Previously nothing was live after NewIdx, so all we have to do now is
1522 // move the begin of OldIdxOut to NewIdx.
1523 if (!OldIdxDefIsDead) {
1524 // Do we have any intermediate Defs between OldIdx and NewIdx?
1525 if (OldIdxIn != E &&
1526 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
1527 // OldIdx is not a dead def and NewIdx is before predecessor start.
1528 LiveRange::iterator NewIdxIn = NewIdxOut;
1529 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1530 const SlotIndex SplitPos = NewIdxDef;
1531 OldIdxVNI = OldIdxIn->valno;
1532
1533 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;
1534 LiveRange::iterator Prev = std::prev(OldIdxIn);
1535 if (OldIdxIn != LR.begin() &&
1536 SlotIndex::isEarlierInstr(NewIdx, Prev->end)) {
1537 // If the segment before OldIdx read a value defined earlier than
1538 // NewIdx, the moved instruction also reads and forwards that
1539 // value. Extend the lifetime of the new def point.
1540
1541 // Extend to where the previous range started, unless there is
1542 // another redef first.
1543 NewDefEndPoint = std::min(OldIdxIn->start,
1544 std::next(NewIdxOut)->start);
1545 }
1546
1547 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1548 OldIdxOut->valno->def = OldIdxIn->start;
1549 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1550 OldIdxOut->valno);
1551 // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1552 // We Slide [NewIdxIn, OldIdxIn) down one position.
1553 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1554 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1555 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1556 // NewIdxIn is now considered undef so we can reuse it for the moved
1557 // value.
1558 LiveRange::iterator NewSegment = NewIdxIn;
1559 LiveRange::iterator Next = std::next(NewSegment);
1560 if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1561 // There is no gap between NewSegment and its predecessor.
1562 *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1563 Next->valno);
1564
1565 *Next = LiveRange::Segment(SplitPos, NewDefEndPoint, OldIdxVNI);
1566 Next->valno->def = SplitPos;
1567 } else {
1568 // There is a gap between NewSegment and its predecessor
1569 // Value becomes live in.
1570 *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1571 NewSegment->valno->def = SplitPos;
1572 }
1573 } else {
1574 // Leave the end point of a live def.
1575 OldIdxOut->start = NewIdxDef;
1576 OldIdxVNI->def = NewIdxDef;
1577 if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
1578 OldIdxIn->end = NewIdxDef;
1579 }
1580 } else if (OldIdxIn != E
1581 && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)
1582 && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {
1583 // OldIdxVNI is a dead def that has been moved into the middle of
1584 // another value in LR. That can happen when LR is a whole register,
1585 // but the dead def is a write to a subreg that is dead at NewIdx.
1586 // The dead def may have been moved across other values
1587 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1588 // down one position.
1589 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1590 // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1591 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1592 // Modify the segment at NewIdxOut and the following segment to meet at
1593 // the point of the dead def, with the following segment getting
1594 // OldIdxVNI as its value number.
1595 *NewIdxOut = LiveRange::Segment(
1596 NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
1597 *(NewIdxOut + 1) = LiveRange::Segment(
1598 NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1599 OldIdxVNI->def = NewIdxDef;
1600 // Retag the segments that were shifted down from [NewIdxOut + 2,
1601 // OldIdxOut]. Retagging can make a segment touch another segment with
1602 // the same value number, so merge as we go. Stop at the original end
1603 // slot instead of using a segment count because merging may erase
1604 // segments.
1605 const SlotIndex RetagEnd = OldIdxOut->end;
1606 for (LiveRange::iterator Idx = NewIdxOut + 2;
1607 Idx != LR.end() && Idx->start < RetagEnd;) {
1608 Idx->valno = OldIdxVNI;
1609 Idx = std::next(LR.mergeAdjacentSegments(Idx));
1610 }
1611 // Aggressively remove all dead flags from the former dead definition.
1612 // Kill/dead flags shouldn't be used while live intervals exist; they
1613 // will be reinserted by VirtRegRewriter.
1614 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
1615 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
1616 if (MO->isReg() && !MO->isUse())
1617 MO->setIsDead(false);
1618 } else {
1619 // OldIdxVNI is a dead def. It may have been moved across other values
1620 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1621 // down one position.
1622 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1623 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1624 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1625 // OldIdxVNI can be reused now to build a new dead def segment.
1626 LiveRange::iterator NewSegment = NewIdxOut;
1627 VNInfo *NewSegmentVNI = OldIdxVNI;
1628 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1629 NewSegmentVNI);
1630 NewSegmentVNI->def = NewIdxDef;
1631 }
1632 }
1633 }
1634
1635 void updateRegMaskSlots() {
1637 llvm::lower_bound(LIS.RegMaskSlots, OldIdx);
1638 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1639 "No RegMask at OldIdx.");
1640 *RI = NewIdx.getRegSlot();
1641 assert((RI == LIS.RegMaskSlots.begin() ||
1642 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1643 "Cannot move regmask instruction above another call");
1644 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1645 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1646 "Cannot move regmask instruction below another call");
1647 }
1648
1649 // Return the last use of reg between NewIdx and OldIdx.
1650 SlotIndex findLastUseBefore(SlotIndex Before, VirtRegOrUnit VRegOrUnit,
1651 LaneBitmask LaneMask) {
1652 if (VRegOrUnit.isVirtualReg()) {
1653 SlotIndex LastUse = Before;
1654 for (MachineOperand &MO :
1655 MRI.use_nodbg_operands(VRegOrUnit.asVirtualReg())) {
1656 if (MO.isUndef())
1657 continue;
1658 unsigned SubReg = MO.getSubReg();
1659 if (SubReg != 0 && LaneMask.any()
1660 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
1661 continue;
1662
1663 const MachineInstr &MI = *MO.getParent();
1664 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1665 if (InstSlot > LastUse && InstSlot < OldIdx)
1666 LastUse = InstSlot.getRegSlot();
1667 }
1668 return LastUse;
1669 }
1670
1671 // This is a regunit interval, so scanning the use list could be very
1672 // expensive. Scan upwards from OldIdx instead.
1673 assert(Before < OldIdx && "Expected upwards move");
1674 SlotIndexes *Indexes = LIS.getSlotIndexes();
1675 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
1676
1677 // OldIdx may not correspond to an instruction any longer, so set MII to
1678 // point to the next instruction after OldIdx, or MBB->end().
1680 if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1681 Indexes->getNextNonNullIndex(OldIdx)))
1682 if (MI->getParent() == MBB)
1683 MII = MI;
1684
1686 while (MII != Begin) {
1687 if ((--MII)->isDebugOrPseudoInstr())
1688 continue;
1689 SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1690
1691 // Stop searching when Before is reached.
1692 if (!SlotIndex::isEarlierInstr(Before, Idx))
1693 return Before;
1694
1695 // Check if MII uses Reg.
1696 for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
1697 if (MO->isReg() && !MO->isUndef() && MO->getReg().isPhysical() &&
1698 TRI.hasRegUnit(MO->getReg(), VRegOrUnit.asMCRegUnit()))
1699 return Idx.getRegSlot();
1700 }
1701 // Didn't reach Before. It must be the first instruction in the block.
1702 return Before;
1703 }
1704};
1705
1707 // It is fine to move a bundle as a whole, but not an individual instruction
1708 // inside it.
1709 assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) &&
1710 "Cannot move instruction in bundle");
1711 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1712 Indexes->removeMachineInstrFromMaps(MI);
1713 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1714 assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1715 OldIndex < getMBBEndIdx(MI.getParent()) &&
1716 "Cannot handle moves across basic block boundaries.");
1717
1718 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1719 HME.updateAllRanges(&MI);
1720}
1721
1723 bool UpdateFlags) {
1724 assert((BundleStart.getOpcode() == TargetOpcode::BUNDLE) &&
1725 "Bundle start is not a bundle");
1727 const SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(BundleStart);
1728 auto BundleEnd = getBundleEnd(BundleStart.getIterator());
1729
1730 auto I = BundleStart.getIterator();
1731 I++;
1732 while (I != BundleEnd) {
1733 if (!Indexes->hasIndex(*I))
1734 continue;
1735 SlotIndex OldIndex = Indexes->getInstructionIndex(*I, true);
1736 ToProcess.push_back(OldIndex);
1737 Indexes->removeMachineInstrFromMaps(*I, true);
1738 I++;
1739 }
1740 for (SlotIndex OldIndex : ToProcess) {
1741 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1742 HME.updateAllRanges(&BundleStart);
1743 }
1744
1745 // Fix up dead defs
1746 const SlotIndex Index = getInstructionIndex(BundleStart);
1747 for (MachineOperand &MO : BundleStart.operands()) {
1748 if (!MO.isReg())
1749 continue;
1750 Register Reg = MO.getReg();
1751 if (Reg.isVirtual() && hasInterval(Reg) && !MO.isUndef()) {
1752 LiveInterval &LI = getInterval(Reg);
1753 LiveQueryResult LRQ = LI.Query(Index);
1754 if (LRQ.isDeadDef())
1755 MO.setIsDead();
1756 }
1757 }
1758}
1759
1760void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1762 const SlotIndex EndIdx, LiveRange &LR,
1763 const Register Reg,
1764 LaneBitmask LaneMask) {
1765 LiveInterval::iterator LII = LR.find(EndIdx);
1766 SlotIndex lastUseIdx;
1767 if (LII != LR.end() && LII->start < EndIdx) {
1768 lastUseIdx = LII->end;
1769 } else if (LII == LR.begin()) {
1770 // We may not have a liverange at all if this is a subregister untouched
1771 // between \p Begin and \p End.
1772 } else {
1773 --LII;
1774 }
1775
1776 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1777 --I;
1778 MachineInstr &MI = *I;
1779 if (MI.isDebugOrPseudoInstr())
1780 continue;
1781
1782 SlotIndex instrIdx = getInstructionIndex(MI);
1783 bool isStartValid = getInstructionFromIndex(LII->start);
1784 bool isEndValid = getInstructionFromIndex(LII->end);
1785
1786 // FIXME: This doesn't currently handle early-clobber or multiple removed
1787 // defs inside of the region to repair.
1788 for (const MachineOperand &MO : MI.operands()) {
1789 if (!MO.isReg() || MO.getReg() != Reg)
1790 continue;
1791
1792 unsigned SubReg = MO.getSubReg();
1793 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1794 if ((Mask & LaneMask).none())
1795 continue;
1796
1797 if (MO.isDef()) {
1798 if (!isStartValid) {
1799 if (LII->end.isDead()) {
1800 LII = LR.removeSegment(LII, true);
1801 if (LII != LR.begin())
1802 --LII;
1803 } else {
1804 LII->start = instrIdx.getRegSlot();
1805 LII->valno->def = instrIdx.getRegSlot();
1806 if (MO.getSubReg() && !MO.isUndef())
1807 lastUseIdx = instrIdx.getRegSlot();
1808 else
1809 lastUseIdx = SlotIndex();
1810 continue;
1811 }
1812 }
1813
1814 if (!lastUseIdx.isValid()) {
1815 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1816 LiveRange::Segment S(instrIdx.getRegSlot(),
1817 instrIdx.getDeadSlot(), VNI);
1818 LII = LR.addSegment(S);
1819 } else if (LII->start != instrIdx.getRegSlot()) {
1820 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1821 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1822 LII = LR.addSegment(S);
1823 }
1824
1825 if (MO.getSubReg() && !MO.isUndef())
1826 lastUseIdx = instrIdx.getRegSlot();
1827 else
1828 lastUseIdx = SlotIndex();
1829 } else if (MO.isUse()) {
1830 // FIXME: This should probably be handled outside of this branch,
1831 // either as part of the def case (for defs inside of the region) or
1832 // after the loop over the region.
1833 if (!isEndValid && !LII->end.isBlock())
1834 LII->end = instrIdx.getRegSlot();
1835 if (!lastUseIdx.isValid())
1836 lastUseIdx = instrIdx.getRegSlot();
1837 }
1838 }
1839 }
1840
1841 bool isStartValid = getInstructionFromIndex(LII->start);
1842 if (!isStartValid && LII->end.isDead())
1843 LR.removeSegment(*LII, true);
1844}
1845
1846void
1850 ArrayRef<Register> OrigRegs) {
1851 // Find anchor points, which are at the beginning/end of blocks or at
1852 // instructions that already have indexes.
1853 while (Begin != MBB->begin() && !Indexes->hasIndex(*std::prev(Begin)))
1854 --Begin;
1855 while (End != MBB->end() && !Indexes->hasIndex(*End))
1856 ++End;
1857
1858 SlotIndex EndIdx;
1859 if (End == MBB->end())
1860 EndIdx = getMBBEndIdx(MBB).getPrevSlot();
1861 else
1862 EndIdx = getInstructionIndex(*End);
1863
1864 Indexes->repairIndexesInRange(MBB, Begin, End);
1865
1866 // Make sure a live interval exists for all register operands in the range.
1867 SmallVector<Register> RegsToRepair(OrigRegs);
1868 for (MachineBasicBlock::iterator I = End; I != Begin;) {
1869 --I;
1870 MachineInstr &MI = *I;
1871 if (MI.isDebugOrPseudoInstr())
1872 continue;
1873 for (const MachineOperand &MO : MI.operands()) {
1874 if (MO.isReg() && MO.getReg().isVirtual()) {
1875 Register Reg = MO.getReg();
1876 if (MO.getSubReg() && hasInterval(Reg) &&
1877 MRI->shouldTrackSubRegLiveness(Reg)) {
1878 LiveInterval &LI = getInterval(Reg);
1879 if (!LI.hasSubRanges()) {
1880 // If the new instructions refer to subregs but the old instructions
1881 // did not, throw away any old live interval so it will be
1882 // recomputed with subranges.
1883 removeInterval(Reg);
1884 } else if (MO.isDef()) {
1885 // Similarly if a subreg def has no precise subrange match then
1886 // assume we need to recompute all subranges.
1887 unsigned SubReg = MO.getSubReg();
1888 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1889 if (llvm::none_of(LI.subranges(),
1890 [Mask](LiveInterval::SubRange &SR) {
1891 return SR.LaneMask == Mask;
1892 })) {
1893 removeInterval(Reg);
1894 }
1895 }
1896 }
1897 if (!hasInterval(Reg)) {
1899 // Don't bother to repair a freshly calculated live interval.
1900 llvm::erase(RegsToRepair, Reg);
1901 }
1902 }
1903 }
1904 }
1905
1906 for (Register Reg : RegsToRepair) {
1907 if (!Reg.isVirtual())
1908 continue;
1909
1910 LiveInterval &LI = getInterval(Reg);
1911 // FIXME: Should we support undefs that gain defs?
1912 if (!LI.hasAtLeastOneValue())
1913 continue;
1914
1915 for (LiveInterval::SubRange &S : LI.subranges())
1916 repairOldRegInRange(Begin, End, EndIdx, S, Reg, S.LaneMask);
1918
1919 repairOldRegInRange(Begin, End, EndIdx, LI, Reg);
1920 }
1921}
1922
1924 for (MCRegUnit Unit : TRI->regunits(Reg)) {
1925 if (LiveRange *LR = getCachedRegUnit(Unit))
1926 if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1927 LR->removeValNo(VNI);
1928 }
1929}
1930
1932 // LI may not have the main range computed yet, but its subranges may
1933 // be present.
1934 VNInfo *VNI = LI.getVNInfoAt(Pos);
1935 if (VNI != nullptr) {
1936 assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1937 LI.removeValNo(VNI);
1938 }
1939
1940 // Also remove the value defined in subranges.
1941 for (LiveInterval::SubRange &S : LI.subranges()) {
1942 if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1943 if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1944 S.removeValNo(SVNI);
1945 }
1947}
1948
1951 ConnectedVNInfoEqClasses ConEQ(*this);
1952 unsigned NumComp = ConEQ.Classify(LI);
1953 if (NumComp <= 1)
1954 return;
1955 LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
1956 Register Reg = LI.reg();
1957 for (unsigned I = 1; I < NumComp; ++I) {
1958 Register NewVReg = MRI->cloneVirtualRegister(Reg);
1959 LiveInterval &NewLI = createEmptyInterval(NewVReg);
1960 SplitLIs.push_back(&NewLI);
1961 }
1962 ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1963}
1964
1966 assert(LICalc && "LICalc not initialized.");
1967 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1968 LICalc->constructMainRangeFromSubranges(LI);
1969}
MachineInstrBuilder & UseMI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
Rewrite undef for PHI
MachineBasicBlock & MBB
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:690
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.
static cl::opt< bool > EnablePrecomputePhysRegs("precompute-phys-liveness", cl::Hidden, cl::desc("Eagerly compute live intervals for all physreg units."))
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)
#define I(x, y, z)
Definition MD5.cpp:57
Register Reg
Register const TargetRegisterInfo * TRI
std::pair< uint64_t, uint64_t > Interval
Promote Memory to Register
Definition Mem2Reg.cpp:110
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
MachineRegisterInfo & MRI
Remove Loads Into Fake Uses
SI Optimize VGPR LiveRange
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
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)
LiveRange * getRegUnitLI(MCRegUnit Unit)
void updateAllRanges(MachineInstr *MI)
Update all live ranges touched by MI, assuming a move from OldIdx to NewIdx.
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
Definition Analysis.h:50
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
LLVM_ABI AnalysisUsage & addRequiredTransitiveID(char &ID)
Definition Pass.cpp:304
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:280
AnalysisUsage & addRequiredTransitive()
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
iterator end() const
Definition ArrayRef.h:130
const_pointer iterator
Definition ArrayRef.h:47
iterator begin() const
Definition ArrayRef.h:129
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
Definition BitVector.h:356
void clear()
Removes all bits from the bitvector.
Definition BitVector.h:350
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Clear a bit in this vector for every '0' bit in Mask.
Definition BitVector.h:761
ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a LiveInterval into equivalence cl...
LLVM_ABI void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI)
Distribute values in LI into a separate LiveIntervals for each connected component.
LLVM_ABI unsigned Classify(const LiveRange &LR)
Classify the values in LR into connected components.
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
LLVM_ABI void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
Register reg() const
bool hasSubRanges() const
Returns true if subregister liveness information is available.
iterator_range< subrange_iterator > subranges()
LLVM_ABI 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 ...
LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LLVM_ABI 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.
LLVM_ABI bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
LLVM_ABI 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...
LLVM_ABI 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
LLVM_ABI unsigned removeUnreferencedIntervals()
Remove intervals for virtual registers no instruction refers to any more.
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.
LLVM_ABI 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.
LLVM_ABI bool invalidate(MachineFunction &MF, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &Inv)
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.
static LLVM_ABI float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI, ProfileSummaryInfo *PSI=nullptr)
Calculate the spill weight to assign to a single instruction.
ArrayRef< SlotIndex > getRegMaskSlots() const
Returns a sorted array of slot indices of all instructions with register mask operands.
ArrayRef< SlotIndex > getRegMaskSlotsInBlock(unsigned MBBNum) const
Returns a sorted array of slot indices of all instructions with register mask operands in the basic b...
LiveInterval & getInterval(Register Reg)
friend class LiveIntervalsAnalysis
LLVM_ABI 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.
LLVM_ABI void handleMoveIntoNewBundle(MachineInstr &BundleStart, bool UpdateFlags=false)
Update intervals of operands of all instructions in the newly created bundle specified by BundleStart...
LiveRange & getRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit.
LLVM_ABI bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr, LaneBitmask SubRangeMask=LaneBitmask::getAll())
After removing some uses of a register, shrink its live range to just the remaining uses.
LLVM_ABI MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
LiveRange * getCachedRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LLVM_ABI void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
LLVM_ABI 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.
LLVM_ABI void constructMainRangeFromSubranges(LiveInterval &LI)
For live interval LI with correct SubRanges construct matching information for the main live range.
LiveInterval & createEmptyInterval(Register Reg)
Interval creation.
LLVM_ABI void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
LLVM_ABI void dump() const
LLVM_ABI void print(raw_ostream &O) const
Implement the dump method.
LLVM_ABI void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
LLVM_ABI 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)
Result of a LiveRange query.
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
bool isDeadDef() const
Return true if this instruction has a dead def.
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
static LLVM_ABI 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...
This class represents the liveness of a register, stack slot, etc.
LLVM_ABI iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments::iterator iterator
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
iterator_range< vni_iterator > vnis()
Segments::const_iterator const_iterator
LLVM_ABI VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
LLVM_ABI iterator mergeAdjacentSegments(iterator I)
Merge the segment pointed to by I with its immediate neighbors when they use the same value number an...
LLVM_ABI 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,...
LLVM_ABI void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
bool empty() const
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...
bool verify() const
Walk the range and assert if any invariants fail to hold.
iterator begin()
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
VNInfoList valnos
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
bool hasAtLeastOneValue() const
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
LLVM_ABI void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
LLVM_ABI iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
Wrapper class representing physical registers. Should be passed by value.
Definition MCRegister.h:41
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...
LLVM_ABI 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()
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI 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.
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
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.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
mop_range operands()
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition Analysis.h:276
Analysis providing profile information.
Wrapper class representing virtual and physical registers.
Definition Register.h:20
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition Register.h:72
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition Register.h:83
SlotIndex - An opaque wrapper around machine indexes.
Definition SlotIndexes.h:70
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
bool isBlock() const
isBlock - Returns true if this is a block boundary slot.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
bool isValid() const
Returns true if this is a valid index.
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
SlotIndex getNextNonNullIndex(SlotIndex Index)
Returns the next non-null index, if one exists.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void swap(SmallVectorImpl &RHS)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
pointer data()
Return a pointer to the vector's buffer, even if empty().
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
MI-level Statepoint operands.
Definition StackMaps.h:159
unsigned getNumDeoptArgsIdx() const
Get index of Number Deopt Arguments operand.
Definition StackMaps.h:200
uint64_t getFlags() const
Return the statepoint flags.
Definition StackMaps.h:223
LLVM_ABI unsigned getNumGCPtrIdx()
Get index of number of GC pointers.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
VNInfo - Value Number Information.
void markUnused()
Mark this value as unused.
bool isUnused() const
Returns true if this value is unused.
unsigned id
The ID number of this value.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
MCRegister getPhys(Register virtReg) const
returns the physical register mapped to the specified virtual register
Definition VirtRegMap.h:91
Wrapper class representing a virtual register or register unit.
Definition Register.h:175
constexpr bool isVirtualReg() const
Definition Register.h:191
constexpr MCRegUnit asMCRegUnit() const
Definition Register.h:195
constexpr Register asVirtualReg() const
Definition Register.h:200
self_iterator getIterator()
Definition ilist_node.h:123
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:53
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.
NodeAddr< DefNode * > Def
Definition RDFGraph.h:384
NodeAddr< UseNode * > Use
Definition RDFGraph.h:385
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
@ Kill
The last use of a register.
LLVM_ABI char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition STLExtras.h:2145
LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
Definition LaneBitmask.h:92
LLVM_ABI Printable printRegUnit(MCRegUnit Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition STLExtras.h:2216
LLVM_ABI char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1652
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
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:1769
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
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:2068
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition MCRegister.h:21
ArrayRef(const T &OneElt) -> ArrayRef< T >
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
Definition Statepoint.h:49
iterator_range< MIBundleOperands > mi_bundle_ops(MachineInstr &MI)
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
Definition InstrProf.h:147
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
LLVM_ABI 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.
LLVM_ABI char & LiveIntervalsID
LiveIntervals - This analysis keeps track of the live ranges of virtual and physical registers.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
#define N
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
static constexpr LaneBitmask getAll()
Definition LaneBitmask.h:82
constexpr bool none() const
Definition LaneBitmask.h:52
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.