1824 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file This file implements the LiveInterval analysis pass which is used10/// by the Linear Scan Register allocator. This pass linearizes the11/// basic blocks of the function in DFS order and computes live intervals for12/// each virtual and physical register.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/CodeGen/LiveIntervals.h"17#include "llvm/ADT/ArrayRef.h"18#include "llvm/ADT/DepthFirstIterator.h"19#include "llvm/ADT/SmallPtrSet.h"20#include "llvm/ADT/SmallVector.h"21#include "llvm/ADT/iterator_range.h"22#include "llvm/CodeGen/LiveInterval.h"23#include "llvm/CodeGen/LiveIntervalCalc.h"24#include "llvm/CodeGen/LiveVariables.h"25#include "llvm/CodeGen/MachineBasicBlock.h"26#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"27#include "llvm/CodeGen/MachineDominators.h"28#include "llvm/CodeGen/MachineFunction.h"29#include "llvm/CodeGen/MachineInstr.h"30#include "llvm/CodeGen/MachineInstrBundle.h"31#include "llvm/CodeGen/MachineOperand.h"32#include "llvm/CodeGen/MachineRegisterInfo.h"33#include "llvm/CodeGen/MachineSizeOpts.h"34#include "llvm/CodeGen/Passes.h"35#include "llvm/CodeGen/SlotIndexes.h"36#include "llvm/CodeGen/StackMaps.h"37#include "llvm/CodeGen/TargetRegisterInfo.h"38#include "llvm/CodeGen/TargetSubtargetInfo.h"39#include "llvm/CodeGen/VirtRegMap.h"40#include "llvm/Config/llvm-config.h"41#include "llvm/IR/ProfileSummary.h"42#include "llvm/IR/Statepoint.h"43#include "llvm/MC/LaneBitmask.h"44#include "llvm/MC/MCRegisterInfo.h"45#include "llvm/Pass.h"46#include "llvm/Support/CommandLine.h"47#include "llvm/Support/Compiler.h"48#include "llvm/Support/Debug.h"49#include "llvm/Support/MathExtras.h"50#include "llvm/Support/raw_ostream.h"51#include <algorithm>52#include <cassert>53#include <cstdint>54#include <iterator>55#include <tuple>56#include <utility>57 58using namespace llvm;59 60#define DEBUG_TYPE "regalloc"61 62AnalysisKey LiveIntervalsAnalysis::Key;63 64LiveIntervalsAnalysis::Result65LiveIntervalsAnalysis::run(MachineFunction &MF,66 MachineFunctionAnalysisManager &MFAM) {67 return Result(MF, MFAM.getResult<SlotIndexesAnalysis>(MF),68 MFAM.getResult<MachineDominatorTreeAnalysis>(MF));69}70 71PreservedAnalyses72LiveIntervalsPrinterPass::run(MachineFunction &MF,73 MachineFunctionAnalysisManager &MFAM) {74 OS << "Live intervals for machine function: " << MF.getName() << ":\n";75 MFAM.getResult<LiveIntervalsAnalysis>(MF).print(OS);76 return PreservedAnalyses::all();77}78 79char LiveIntervalsWrapperPass::ID = 0;80char &llvm::LiveIntervalsID = LiveIntervalsWrapperPass::ID;81INITIALIZE_PASS_BEGIN(LiveIntervalsWrapperPass, "liveintervals",82 "Live Interval Analysis", false, false)83INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)84INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)85INITIALIZE_PASS_END(LiveIntervalsWrapperPass, "liveintervals",86 "Live Interval Analysis", false, true)87 88bool LiveIntervalsWrapperPass::runOnMachineFunction(MachineFunction &MF) {89 LIS.Indexes = &getAnalysis<SlotIndexesWrapperPass>().getSI();90 LIS.DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();91 LIS.analyze(MF);92 LLVM_DEBUG(dump());93 return false;94}95 96#ifndef NDEBUG97static cl::opt<bool> EnablePrecomputePhysRegs(98 "precompute-phys-liveness", cl::Hidden,99 cl::desc("Eagerly compute live intervals for all physreg units."));100#else101static bool EnablePrecomputePhysRegs = false;102#endif // NDEBUG103 104cl::opt<bool> llvm::UseSegmentSetForPhysRegs(105 "use-segment-set-for-physregs", cl::Hidden, cl::init(true),106 cl::desc(107 "Use segment set for the computation of the live ranges of physregs."));108 109void LiveIntervalsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {110 AU.setPreservesCFG();111 AU.addPreserved<LiveVariablesWrapperPass>();112 AU.addPreservedID(MachineLoopInfoID);113 AU.addRequiredTransitiveID(MachineDominatorsID);114 AU.addPreservedID(MachineDominatorsID);115 AU.addPreserved<SlotIndexesWrapperPass>();116 AU.addRequiredTransitive<SlotIndexesWrapperPass>();117 MachineFunctionPass::getAnalysisUsage(AU);118}119 120LiveIntervalsWrapperPass::LiveIntervalsWrapperPass() : MachineFunctionPass(ID) {121 initializeLiveIntervalsWrapperPassPass(*PassRegistry::getPassRegistry());122}123 124LiveIntervals::~LiveIntervals() { clear(); }125 126bool LiveIntervals::invalidate(127 MachineFunction &MF, const PreservedAnalyses &PA,128 MachineFunctionAnalysisManager::Invalidator &Inv) {129 auto PAC = PA.getChecker<LiveIntervalsAnalysis>();130 131 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<MachineFunction>>())132 return true;133 134 // LiveIntervals holds pointers to these results, so check for their135 // invalidation.136 return Inv.invalidate<SlotIndexesAnalysis>(MF, PA) ||137 Inv.invalidate<MachineDominatorTreeAnalysis>(MF, PA);138}139 140void LiveIntervals::clear() {141 // Free the live intervals themselves.142 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)143 delete VirtRegIntervals[Register::index2VirtReg(i)];144 VirtRegIntervals.clear();145 RegMaskSlots.clear();146 RegMaskBits.clear();147 RegMaskBlocks.clear();148 149 for (LiveRange *LR : RegUnitRanges)150 delete LR;151 RegUnitRanges.clear();152 153 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.154 VNInfoAllocator.Reset();155}156 157void LiveIntervals::analyze(MachineFunction &fn) {158 MF = &fn;159 MRI = &MF->getRegInfo();160 TRI = MF->getSubtarget().getRegisterInfo();161 TII = MF->getSubtarget().getInstrInfo();162 163 if (!LICalc)164 LICalc = std::make_unique<LiveIntervalCalc>();165 166 // Allocate space for all virtual registers.167 VirtRegIntervals.resize(MRI->getNumVirtRegs());168 169 computeVirtRegs();170 computeRegMasks();171 computeLiveInRegUnits();172 173 if (EnablePrecomputePhysRegs) {174 // For stress testing, precompute live ranges of all physical register175 // units, including reserved registers.176 for (MCRegUnit Unit : TRI->regunits())177 getRegUnit(Unit);178 }179}180 181void LiveIntervals::print(raw_ostream &OS) const {182 OS << "********** INTERVALS **********\n";183 184 // Dump the regunits.185 for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)186 if (LiveRange *LR = RegUnitRanges[Unit])187 OS << printRegUnit(static_cast<MCRegUnit>(Unit), TRI) << ' ' << *LR188 << '\n';189 190 // Dump the virtregs.191 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {192 Register Reg = Register::index2VirtReg(i);193 if (hasInterval(Reg))194 OS << getInterval(Reg) << '\n';195 }196 197 OS << "RegMasks:";198 for (SlotIndex Idx : RegMaskSlots)199 OS << ' ' << Idx;200 OS << '\n';201 202 printInstrs(OS);203}204 205void LiveIntervals::printInstrs(raw_ostream &OS) const {206 OS << "********** MACHINEINSTRS **********\n";207 MF->print(OS, Indexes);208}209 210#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)211LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {212 printInstrs(dbgs());213}214#endif215 216#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)217LLVM_DUMP_METHOD void LiveIntervals::dump() const { print(dbgs()); }218#endif219 220LiveInterval *LiveIntervals::createInterval(Register reg) {221 float Weight = reg.isPhysical() ? huge_valf : 0.0F;222 return new LiveInterval(reg, Weight);223}224 225/// Compute the live interval of a virtual register, based on defs and uses.226bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {227 assert(LICalc && "LICalc not initialized.");228 assert(LI.empty() && "Should only compute empty intervals.");229 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());230 LICalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg()));231 return computeDeadValues(LI, nullptr);232}233 234void LiveIntervals::computeVirtRegs() {235 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {236 Register Reg = Register::index2VirtReg(i);237 if (MRI->reg_nodbg_empty(Reg))238 continue;239 LiveInterval &LI = createEmptyInterval(Reg);240 bool NeedSplit = computeVirtRegInterval(LI);241 if (NeedSplit) {242 SmallVector<LiveInterval*, 8> SplitLIs;243 splitSeparateComponents(LI, SplitLIs);244 }245 }246}247 248void LiveIntervals::computeRegMasks() {249 RegMaskBlocks.resize(MF->getNumBlockIDs());250 251 // Find all instructions with regmask operands.252 for (const MachineBasicBlock &MBB : *MF) {253 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];254 RMB.first = RegMaskSlots.size();255 256 // Some block starts, such as EH funclets, create masks.257 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {258 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));259 RegMaskBits.push_back(Mask);260 }261 262 // Unwinders may clobber additional registers.263 // FIXME: This functionality can possibly be merged into264 // MachineBasicBlock::getBeginClobberMask().265 if (MBB.isEHPad())266 if (auto *Mask = TRI->getCustomEHPadPreservedMask(*MBB.getParent())) {267 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));268 RegMaskBits.push_back(Mask);269 }270 271 for (const MachineInstr &MI : MBB) {272 for (const MachineOperand &MO : MI.operands()) {273 if (!MO.isRegMask())274 continue;275 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());276 RegMaskBits.push_back(MO.getRegMask());277 }278 }279 280 // Some block ends, such as funclet returns, create masks. Put the mask on281 // the last instruction of the block, because MBB slot index intervals are282 // half-open.283 if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {284 assert(!MBB.empty() && "empty return block?");285 RegMaskSlots.push_back(286 Indexes->getInstructionIndex(MBB.back()).getRegSlot());287 RegMaskBits.push_back(Mask);288 }289 290 // Compute the number of register mask instructions in this block.291 RMB.second = RegMaskSlots.size() - RMB.first;292 }293}294 295//===----------------------------------------------------------------------===//296// Register Unit Liveness297//===----------------------------------------------------------------------===//298//299// Fixed interference typically comes from ABI boundaries: Function arguments300// and return values are passed in fixed registers, and so are exception301// pointers entering landing pads. Certain instructions require values to be302// present in specific registers. That is also represented through fixed303// interference.304//305 306/// Compute the live range of a register unit, based on the uses and defs of307/// aliasing registers. The range should be empty, or contain only dead308/// phi-defs from ABI blocks.309void LiveIntervals::computeRegUnitRange(LiveRange &LR, MCRegUnit Unit) {310 assert(LICalc && "LICalc not initialized.");311 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());312 313 // The physregs aliasing Unit are the roots and their super-registers.314 // Create all values as dead defs before extending to uses. Note that roots315 // may share super-registers. That's OK because createDeadDefs() is316 // idempotent. It is very rare for a register unit to have multiple roots, so317 // uniquing super-registers is probably not worthwhile.318 bool IsReserved = false;319 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {320 bool IsRootReserved = true;321 for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {322 if (!MRI->reg_empty(Reg))323 LICalc->createDeadDefs(LR, Reg);324 // A register unit is considered reserved if all its roots and all their325 // super registers are reserved.326 if (!MRI->isReserved(Reg))327 IsRootReserved = false;328 }329 IsReserved |= IsRootReserved;330 }331 assert(IsReserved == MRI->isReservedRegUnit(Unit) &&332 "reserved computation mismatch");333 334 // Now extend LR to reach all uses.335 // Ignore uses of reserved registers. We only track defs of those.336 if (!IsReserved) {337 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {338 for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {339 if (!MRI->reg_empty(Reg))340 LICalc->extendToUses(LR, Reg);341 }342 }343 }344 345 // Flush the segment set to the segment vector.346 if (UseSegmentSetForPhysRegs)347 LR.flushSegmentSet();348}349 350/// Precompute the live ranges of any register units that are live-in to an ABI351/// block somewhere. Register values can appear without a corresponding def when352/// entering the entry block or a landing pad.353void LiveIntervals::computeLiveInRegUnits() {354 RegUnitRanges.resize(TRI->getNumRegUnits());355 LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");356 357 // Keep track of the live range sets allocated.358 SmallVector<MCRegUnit, 8> NewRanges;359 360 // Check all basic blocks for live-ins.361 for (const MachineBasicBlock &MBB : *MF) {362 // We only care about ABI blocks: Entry + landing pads.363 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())364 continue;365 366 // Create phi-defs at Begin for all live-in registers.367 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);368 LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));369 for (const auto &LI : MBB.liveins()) {370 for (MCRegUnit Unit : TRI->regunits(LI.PhysReg)) {371 LiveRange *LR = RegUnitRanges[static_cast<unsigned>(Unit)];372 if (!LR) {373 // Use segment set to speed-up initial computation of the live range.374 LR = RegUnitRanges[static_cast<unsigned>(Unit)] =375 new LiveRange(UseSegmentSetForPhysRegs);376 NewRanges.push_back(Unit);377 }378 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());379 (void)VNI;380 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);381 }382 }383 LLVM_DEBUG(dbgs() << '\n');384 }385 LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");386 387 // Compute the 'normal' part of the ranges.388 for (MCRegUnit Unit : NewRanges)389 computeRegUnitRange(*RegUnitRanges[static_cast<unsigned>(Unit)], Unit);390}391 392static void createSegmentsForValues(LiveRange &LR,393 iterator_range<LiveInterval::vni_iterator> VNIs) {394 for (VNInfo *VNI : VNIs) {395 if (VNI->isUnused())396 continue;397 SlotIndex Def = VNI->def;398 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));399 }400}401 402void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,403 ShrinkToUsesWorkList &WorkList,404 Register Reg, LaneBitmask LaneMask) {405 // Keep track of the PHIs that are in use.406 SmallPtrSet<VNInfo*, 8> UsedPHIs;407 // Blocks that have already been added to WorkList as live-out.408 SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;409 410 auto getSubRange = [](const LiveInterval &I, LaneBitmask M)411 -> const LiveRange& {412 if (M.none())413 return I;414 for (const LiveInterval::SubRange &SR : I.subranges()) {415 if ((SR.LaneMask & M).any()) {416 assert(SR.LaneMask == M && "Expecting lane masks to match exactly");417 return SR;418 }419 }420 llvm_unreachable("Subrange for mask not found");421 };422 423 const LiveInterval &LI = getInterval(Reg);424 const LiveRange &OldRange = getSubRange(LI, LaneMask);425 426 // Extend intervals to reach all uses in WorkList.427 while (!WorkList.empty()) {428 SlotIndex Idx = WorkList.back().first;429 VNInfo *VNI = WorkList.back().second;430 WorkList.pop_back();431 const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());432 SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);433 434 // Extend the live range for VNI to be live at Idx.435 if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {436 assert(ExtVNI == VNI && "Unexpected existing value number");437 (void)ExtVNI;438 // Is this a PHIDef we haven't seen before?439 if (!VNI->isPHIDef() || VNI->def != BlockStart ||440 !UsedPHIs.insert(VNI).second)441 continue;442 // The PHI is live, make sure the predecessors are live-out.443 for (const MachineBasicBlock *Pred : MBB->predecessors()) {444 if (!LiveOut.insert(Pred).second)445 continue;446 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);447 // A predecessor is not required to have a live-out value for a PHI.448 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))449 WorkList.push_back(std::make_pair(Stop, PVNI));450 }451 continue;452 }453 454 // VNI is live-in to MBB.455 LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');456 Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));457 458 // Make sure VNI is live-out from the predecessors.459 for (const MachineBasicBlock *Pred : MBB->predecessors()) {460 if (!LiveOut.insert(Pred).second)461 continue;462 SlotIndex Stop = Indexes->getMBBEndIdx(Pred);463 if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {464 assert(OldVNI == VNI && "Wrong value out of predecessor");465 (void)OldVNI;466 WorkList.push_back(std::make_pair(Stop, VNI));467 } else {468#ifndef NDEBUG469 // There was no old VNI. Verify that Stop is jointly dominated470 // by <undef>s for this live range.471 assert(LaneMask.any() &&472 "Missing value out of predecessor for main range");473 SmallVector<SlotIndex,8> Undefs;474 LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);475 assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&476 "Missing value out of predecessor for subrange");477#endif478 }479 }480 }481}482 483bool LiveIntervals::shrinkToUses(LiveInterval *li,484 SmallVectorImpl<MachineInstr*> *dead) {485 LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');486 assert(li->reg().isVirtual() && "Can only shrink virtual registers");487 488 // Shrink subregister live ranges.489 bool NeedsCleanup = false;490 for (LiveInterval::SubRange &S : li->subranges()) {491 shrinkToUses(S, li->reg());492 if (S.empty())493 NeedsCleanup = true;494 }495 if (NeedsCleanup)496 li->removeEmptySubRanges();497 498 // Find all the values used, including PHI kills.499 ShrinkToUsesWorkList WorkList;500 501 // Visit all instructions reading li->reg().502 Register Reg = li->reg();503 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {504 if (UseMI.isDebugInstr() || !UseMI.readsVirtualRegister(Reg))505 continue;506 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();507 LiveQueryResult LRQ = li->Query(Idx);508 VNInfo *VNI = LRQ.valueIn();509 if (!VNI) {510 // This shouldn't happen: readsVirtualRegister returns true, but there is511 // no live value. It is likely caused by a target getting <undef> flags512 // wrong.513 LLVM_DEBUG(514 dbgs() << Idx << '\t' << UseMI515 << "Warning: Instr claims to read non-existent value in "516 << *li << '\n');517 continue;518 }519 // Special case: An early-clobber tied operand reads and writes the520 // register one slot early.521 if (VNInfo *DefVNI = LRQ.valueDefined())522 Idx = DefVNI->def;523 524 WorkList.push_back(std::make_pair(Idx, VNI));525 }526 527 // Create new live ranges with only minimal live segments per def.528 LiveRange NewLR;529 createSegmentsForValues(NewLR, li->vnis());530 extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());531 532 // Move the trimmed segments back.533 li->segments.swap(NewLR.segments);534 535 // Handle dead values.536 bool CanSeparate = computeDeadValues(*li, dead);537 LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');538 return CanSeparate;539}540 541bool LiveIntervals::computeDeadValues(LiveInterval &LI,542 SmallVectorImpl<MachineInstr*> *dead) {543 bool MayHaveSplitComponents = false;544 545 for (VNInfo *VNI : LI.valnos) {546 if (VNI->isUnused())547 continue;548 SlotIndex Def = VNI->def;549 LiveRange::iterator I = LI.FindSegmentContaining(Def);550 assert(I != LI.end() && "Missing segment for VNI");551 552 // Is the register live before? Otherwise we may have to add a read-undef553 // flag for subregister defs.554 Register VReg = LI.reg();555 if (MRI->shouldTrackSubRegLiveness(VReg)) {556 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {557 MachineInstr *MI = getInstructionFromIndex(Def);558 MI->setRegisterDefReadUndef(VReg);559 }560 }561 562 if (I->end != Def.getDeadSlot())563 continue;564 if (VNI->isPHIDef()) {565 // This is a dead PHI. Remove it.566 VNI->markUnused();567 LI.removeSegment(I);568 LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");569 } else {570 // This is a dead def. Make sure the instruction knows.571 MachineInstr *MI = getInstructionFromIndex(Def);572 assert(MI && "No instruction defining live value");573 MI->addRegisterDead(LI.reg(), TRI);574 575 if (dead && MI->allDefsAreDead()) {576 LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);577 dead->push_back(MI);578 }579 }580 MayHaveSplitComponents = true;581 }582 return MayHaveSplitComponents;583}584 585void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, Register Reg) {586 LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');587 assert(Reg.isVirtual() && "Can only shrink virtual registers");588 // Find all the values used, including PHI kills.589 ShrinkToUsesWorkList WorkList;590 591 // Visit all instructions reading Reg.592 SlotIndex LastIdx;593 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {594 // Skip "undef" uses.595 if (!MO.readsReg())596 continue;597 // Maybe the operand is for a subregister we don't care about.598 unsigned SubReg = MO.getSubReg();599 if (SubReg != 0) {600 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);601 if ((LaneMask & SR.LaneMask).none())602 continue;603 }604 // We only need to visit each instruction once.605 MachineInstr *UseMI = MO.getParent();606 SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();607 if (Idx == LastIdx)608 continue;609 LastIdx = Idx;610 611 LiveQueryResult LRQ = SR.Query(Idx);612 VNInfo *VNI = LRQ.valueIn();613 // For Subranges it is possible that only undef values are left in that614 // part of the subregister, so there is no real liverange at the use615 if (!VNI)616 continue;617 618 // Special case: An early-clobber tied operand reads and writes the619 // register one slot early.620 if (VNInfo *DefVNI = LRQ.valueDefined())621 Idx = DefVNI->def;622 623 WorkList.push_back(std::make_pair(Idx, VNI));624 }625 626 // Create a new live ranges with only minimal live segments per def.627 LiveRange NewLR;628 createSegmentsForValues(NewLR, SR.vnis());629 extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);630 631 // Move the trimmed ranges back.632 SR.segments.swap(NewLR.segments);633 634 // Remove dead PHI value numbers635 for (VNInfo *VNI : SR.valnos) {636 if (VNI->isUnused())637 continue;638 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);639 assert(Segment != nullptr && "Missing segment for VNI");640 if (Segment->end != VNI->def.getDeadSlot())641 continue;642 if (VNI->isPHIDef()) {643 // This is a dead PHI. Remove it.644 LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def645 << " may separate interval\n");646 VNI->markUnused();647 SR.removeSegment(*Segment);648 }649 }650 651 LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');652}653 654void LiveIntervals::extendToIndices(LiveRange &LR,655 ArrayRef<SlotIndex> Indices,656 ArrayRef<SlotIndex> Undefs) {657 assert(LICalc && "LICalc not initialized.");658 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());659 for (SlotIndex Idx : Indices)660 LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);661}662 663void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,664 SmallVectorImpl<SlotIndex> *EndPoints) {665 LiveQueryResult LRQ = LR.Query(Kill);666 // LR may have liveness reachable from early clobber slot, which may be667 // only live-in instead of live-out of the instruction.668 // For example, LR =[1r, 3r), Kill = 3e, we have to prune [3e, 3r) of LR.669 VNInfo *VNI = LRQ.valueOutOrDead() ? LRQ.valueOutOrDead() : LRQ.valueIn();670 if (!VNI)671 return;672 673 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);674 SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);675 676 // If VNI isn't live out from KillMBB, the value is trivially pruned.677 if (LRQ.endPoint() < MBBEnd) {678 LR.removeSegment(Kill, LRQ.endPoint());679 if (EndPoints) EndPoints->push_back(LRQ.endPoint());680 return;681 }682 683 // VNI is live out of KillMBB.684 LR.removeSegment(Kill, MBBEnd);685 if (EndPoints) EndPoints->push_back(MBBEnd);686 687 // Find all blocks that are reachable from KillMBB without leaving VNI's live688 // range. It is possible that KillMBB itself is reachable, so start a DFS689 // from each successor.690 using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;691 VisitedTy Visited;692 for (MachineBasicBlock *Succ : KillMBB->successors()) {693 for (df_ext_iterator<MachineBasicBlock*, VisitedTy>694 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);695 I != E;) {696 MachineBasicBlock *MBB = *I;697 698 // Check if VNI is live in to MBB.699 SlotIndex MBBStart, MBBEnd;700 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);701 LiveQueryResult LRQ = LR.Query(MBBStart);702 if (LRQ.valueIn() != VNI) {703 // This block isn't part of the VNI segment. Prune the search.704 I.skipChildren();705 continue;706 }707 708 // Prune the search if VNI is killed in MBB.709 if (LRQ.endPoint() < MBBEnd) {710 LR.removeSegment(MBBStart, LRQ.endPoint());711 if (EndPoints) EndPoints->push_back(LRQ.endPoint());712 I.skipChildren();713 continue;714 }715 716 // VNI is live through MBB.717 LR.removeSegment(MBBStart, MBBEnd);718 if (EndPoints) EndPoints->push_back(MBBEnd);719 ++I;720 }721 }722}723 724//===----------------------------------------------------------------------===//725// Register allocator hooks.726//727 728void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {729 // Keep track of regunit ranges.730 SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;731 732 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {733 Register Reg = Register::index2VirtReg(i);734 if (MRI->reg_nodbg_empty(Reg))735 continue;736 const LiveInterval &LI = getInterval(Reg);737 if (LI.empty())738 continue;739 740 // Target may have not allocated this yet.741 Register PhysReg = VRM->getPhys(Reg);742 if (!PhysReg)743 continue;744 745 // Find the regunit intervals for the assigned register. They may overlap746 // the virtual register live range, cancelling any kills.747 RU.clear();748 LaneBitmask ArtificialLanes;749 for (MCRegUnitMaskIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {750 auto [Unit, Bitmask] = *UI;751 // Record lane mask for all artificial RegUnits for this physreg.752 if (TRI->isArtificialRegUnit(Unit))753 ArtificialLanes |= Bitmask;754 const LiveRange &RURange = getRegUnit(Unit);755 if (RURange.empty())756 continue;757 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));758 }759 // Every instruction that kills Reg corresponds to a segment range end760 // point.761 for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;762 ++RI) {763 // A block index indicates an MBB edge.764 if (RI->end.isBlock())765 continue;766 MachineInstr *MI = getInstructionFromIndex(RI->end);767 if (!MI)768 continue;769 770 // Check if any of the regunits are live beyond the end of RI. That could771 // happen when a physreg is defined as a copy of a virtreg:772 //773 // %eax = COPY %5774 // FOO %5 <--- MI, cancel kill because %eax is live.775 // BAR killed %eax776 //777 // There should be no kill flag on FOO when %5 is rewritten as %eax.778 for (auto &RUP : RU) {779 const LiveRange &RURange = *RUP.first;780 LiveRange::const_iterator &I = RUP.second;781 if (I == RURange.end())782 continue;783 I = RURange.advanceTo(I, RI->end);784 if (I == RURange.end() || I->start >= RI->end)785 continue;786 // I is overlapping RI.787 goto CancelKill;788 }789 790 if (MRI->subRegLivenessEnabled()) {791 // When reading a partial undefined value we must not add a kill flag.792 // The regalloc might have used the undef lane for something else.793 // Example:794 // %1 = ... ; R32: %1795 // %2:high16 = ... ; R64: %2796 // = read killed %2 ; R64: %2797 // = read %1 ; R32: %1798 // The <kill> flag is correct for %2, but the register allocator may799 // assign R0L to %1, and R0 to %2 because the low 32bits of R0800 // are actually never written by %2. After assignment the <kill>801 // flag at the read instruction is invalid.802 LaneBitmask DefinedLanesMask;803 if (LI.hasSubRanges()) {804 // Compute a mask of lanes that are defined.805 // Artificial regunits are not independently allocatable so the806 // register allocator cannot have used them to represent any other807 // values. That's why we mark them as 'defined' here, as this808 // otherwise prevents kill flags from being added.809 DefinedLanesMask = ArtificialLanes;810 for (const LiveInterval::SubRange &SR : LI.subranges())811 for (const LiveRange::Segment &Segment : SR.segments) {812 if (Segment.start >= RI->end)813 break;814 if (Segment.end == RI->end) {815 DefinedLanesMask |= SR.LaneMask;816 break;817 }818 }819 } else820 DefinedLanesMask = LaneBitmask::getAll();821 822 bool IsFullWrite = false;823 for (const MachineOperand &MO : MI->operands()) {824 if (!MO.isReg() || MO.getReg() != Reg)825 continue;826 if (MO.isUse()) {827 // Reading any undefined lanes?828 unsigned SubReg = MO.getSubReg();829 LaneBitmask UseMask = SubReg ? TRI->getSubRegIndexLaneMask(SubReg)830 : MRI->getMaxLaneMaskForVReg(Reg);831 if ((UseMask & ~DefinedLanesMask).any())832 goto CancelKill;833 } else if (MO.getSubReg() == 0) {834 // Writing to the full register?835 assert(MO.isDef());836 IsFullWrite = true;837 }838 }839 840 // If an instruction writes to a subregister, a new segment starts in841 // the LiveInterval. But as this is only overriding part of the register842 // adding kill-flags is not correct here after registers have been843 // assigned.844 if (!IsFullWrite) {845 // Next segment has to be adjacent in the subregister write case.846 LiveRange::const_iterator N = std::next(RI);847 if (N != LI.end() && N->start == RI->end)848 goto CancelKill;849 }850 }851 852 MI->addRegisterKilled(Reg, nullptr);853 continue;854CancelKill:855 MI->clearRegisterKills(Reg, nullptr);856 }857 }858}859 860MachineBasicBlock*861LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {862 assert(!LI.empty() && "LiveInterval is empty.");863 864 // A local live range must be fully contained inside the block, meaning it is865 // defined and killed at instructions, not at block boundaries. It is not866 // live in or out of any block.867 //868 // It is technically possible to have a PHI-defined live range identical to a869 // single block, but we are going to return false in that case.870 871 SlotIndex Start = LI.beginIndex();872 if (Start.isBlock())873 return nullptr;874 875 SlotIndex Stop = LI.endIndex();876 if (Stop.isBlock())877 return nullptr;878 879 // getMBBFromIndex doesn't need to search the MBB table when both indexes880 // belong to proper instructions.881 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);882 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);883 return MBB1 == MBB2 ? MBB1 : nullptr;884}885 886bool887LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {888 for (const VNInfo *PHI : LI.valnos) {889 if (PHI->isUnused() || !PHI->isPHIDef())890 continue;891 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);892 // Conservatively return true instead of scanning huge predecessor lists.893 if (PHIMBB->pred_size() > 100)894 return true;895 for (const MachineBasicBlock *Pred : PHIMBB->predecessors())896 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))897 return true;898 }899 return false;900}901 902float LiveIntervals::getSpillWeight(bool isDef, bool isUse,903 const MachineBlockFrequencyInfo *MBFI,904 const MachineInstr &MI,905 ProfileSummaryInfo *PSI) {906 return getSpillWeight(isDef, isUse, MBFI, MI.getParent(), PSI);907}908 909float LiveIntervals::getSpillWeight(bool isDef, bool isUse,910 const MachineBlockFrequencyInfo *MBFI,911 const MachineBasicBlock *MBB,912 ProfileSummaryInfo *PSI) {913 float Weight = isDef + isUse;914 const auto *MF = MBB->getParent();915 // When optimizing for size we only consider the codesize impact of spilling916 // the register, not the runtime impact.917 if (PSI && llvm::shouldOptimizeForSize(MF, PSI, MBFI))918 return Weight;919 return Weight * MBFI->getBlockFreqRelativeToEntryBlock(MBB);920}921 922LiveRange::Segment923LiveIntervals::addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst) {924 LiveInterval &Interval = getOrCreateEmptyInterval(Reg);925 VNInfo *VN = Interval.getNextValue(926 SlotIndex(getInstructionIndex(startInst).getRegSlot()),927 getVNInfoAllocator());928 LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),929 getMBBEndIdx(startInst.getParent()), VN);930 Interval.addSegment(S);931 932 return S;933}934 935//===----------------------------------------------------------------------===//936// Register mask functions937//===----------------------------------------------------------------------===//938/// Check whether use of reg in MI is live-through. Live-through means that939/// the value is alive on exit from Machine instruction. The example of such940/// use is a deopt value in statepoint instruction.941static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg) {942 if (MI->getOpcode() != TargetOpcode::STATEPOINT)943 return false;944 StatepointOpers SO(MI);945 if (SO.getFlags() & (uint64_t)StatepointFlags::DeoptLiveIn)946 return false;947 for (unsigned Idx = SO.getNumDeoptArgsIdx(), E = SO.getNumGCPtrIdx(); Idx < E;948 ++Idx) {949 const MachineOperand &MO = MI->getOperand(Idx);950 if (MO.isReg() && MO.getReg() == Reg)951 return true;952 }953 return false;954}955 956bool LiveIntervals::checkRegMaskInterference(const LiveInterval &LI,957 BitVector &UsableRegs) {958 if (LI.empty())959 return false;960 LiveInterval::const_iterator LiveI = LI.begin(), LiveE = LI.end();961 962 // Use a smaller arrays for local live ranges.963 ArrayRef<SlotIndex> Slots;964 ArrayRef<const uint32_t*> Bits;965 if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {966 Slots = getRegMaskSlotsInBlock(MBB->getNumber());967 Bits = getRegMaskBitsInBlock(MBB->getNumber());968 } else {969 Slots = getRegMaskSlots();970 Bits = getRegMaskBits();971 }972 973 // We are going to enumerate all the register mask slots contained in LI.974 // Start with a binary search of RegMaskSlots to find a starting point.975 ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);976 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();977 978 // No slots in range, LI begins after the last call.979 if (SlotI == SlotE)980 return false;981 982 bool Found = false;983 // Utility to union regmasks.984 auto unionBitMask = [&](unsigned Idx) {985 if (!Found) {986 // This is the first overlap. Initialize UsableRegs to all ones.987 UsableRegs.clear();988 UsableRegs.resize(TRI->getNumRegs(), true);989 Found = true;990 }991 // Remove usable registers clobbered by this mask.992 UsableRegs.clearBitsNotInMask(Bits[Idx]);993 };994 while (true) {995 assert(*SlotI >= LiveI->start);996 // Loop over all slots overlapping this segment.997 while (*SlotI < LiveI->end) {998 // *SlotI overlaps LI. Collect mask bits.999 unionBitMask(SlotI - Slots.begin());1000 if (++SlotI == SlotE)1001 return Found;1002 }1003 // If segment ends with live-through use we need to collect its regmask.1004 if (*SlotI == LiveI->end)1005 if (MachineInstr *MI = getInstructionFromIndex(*SlotI))1006 if (hasLiveThroughUse(MI, LI.reg()))1007 unionBitMask(SlotI++ - Slots.begin());1008 // *SlotI is beyond the current LI segment.1009 // Special advance implementation to not miss next LiveI->end.1010 if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.endIndex())1011 return Found;1012 while (LiveI->end < *SlotI)1013 ++LiveI;1014 // Advance SlotI until it overlaps.1015 while (*SlotI < LiveI->start)1016 if (++SlotI == SlotE)1017 return Found;1018 }1019}1020 1021//===----------------------------------------------------------------------===//1022// IntervalUpdate class.1023//===----------------------------------------------------------------------===//1024 1025/// Toolkit used by handleMove to trim or extend live intervals.1026class LiveIntervals::HMEditor {1027private:1028 LiveIntervals& LIS;1029 const MachineRegisterInfo& MRI;1030 const TargetRegisterInfo& TRI;1031 SlotIndex OldIdx;1032 SlotIndex NewIdx;1033 SmallPtrSet<LiveRange*, 8> Updated;1034 bool UpdateFlags;1035 1036public:1037 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,1038 const TargetRegisterInfo& TRI,1039 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)1040 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),1041 UpdateFlags(UpdateFlags) {}1042 1043 // FIXME: UpdateFlags is a workaround that creates live intervals for all1044 // physregs, even those that aren't needed for regalloc, in order to update1045 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill1046 // flags, and postRA passes will use a live register utility instead.1047 LiveRange *getRegUnitLI(MCRegUnit Unit) {1048 if (UpdateFlags && !MRI.isReservedRegUnit(Unit))1049 return &LIS.getRegUnit(Unit);1050 return LIS.getCachedRegUnit(Unit);1051 }1052 1053 /// Update all live ranges touched by MI, assuming a move from OldIdx to1054 /// NewIdx.1055 void updateAllRanges(MachineInstr *MI) {1056 LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "1057 << *MI);1058 bool hasRegMask = false;1059 for (MachineOperand &MO : MI->operands()) {1060 if (MO.isRegMask())1061 hasRegMask = true;1062 if (!MO.isReg())1063 continue;1064 if (MO.isUse()) {1065 if (!MO.readsReg())1066 continue;1067 // Aggressively clear all kill flags.1068 // They are reinserted by VirtRegRewriter.1069 MO.setIsKill(false);1070 }1071 1072 Register Reg = MO.getReg();1073 if (!Reg)1074 continue;1075 if (Reg.isVirtual()) {1076 LiveInterval &LI = LIS.getInterval(Reg);1077 if (LI.hasSubRanges()) {1078 unsigned SubReg = MO.getSubReg();1079 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)1080 : MRI.getMaxLaneMaskForVReg(Reg);1081 for (LiveInterval::SubRange &S : LI.subranges()) {1082 if ((S.LaneMask & LaneMask).none())1083 continue;1084 updateRange(S, VirtRegOrUnit(Reg), S.LaneMask);1085 }1086 }1087 updateRange(LI, VirtRegOrUnit(Reg), LaneBitmask::getNone());1088 // If main range has a hole and we are moving a subrange use across1089 // the hole updateRange() cannot properly handle it since it only1090 // gets the LiveRange and not the whole LiveInterval. As a result1091 // we may end up with a main range not covering all subranges.1092 // This is extremely rare case, so let's check and reconstruct the1093 // main range.1094 if (LI.hasSubRanges()) {1095 unsigned SubReg = MO.getSubReg();1096 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)1097 : MRI.getMaxLaneMaskForVReg(Reg);1098 for (LiveInterval::SubRange &S : LI.subranges()) {1099 if ((S.LaneMask & LaneMask).none() || LI.covers(S))1100 continue;1101 LI.clear();1102 LIS.constructMainRangeFromSubranges(LI);1103 break;1104 }1105 }1106 1107 continue;1108 }1109 1110 // For physregs, only update the regunits that actually have a1111 // precomputed live range.1112 for (MCRegUnit Unit : TRI.regunits(Reg.asMCReg()))1113 if (LiveRange *LR = getRegUnitLI(Unit))1114 updateRange(*LR, VirtRegOrUnit(Unit), LaneBitmask::getNone());1115 }1116 if (hasRegMask)1117 updateRegMaskSlots();1118 }1119 1120private:1121 /// Update a single live range, assuming an instruction has been moved from1122 /// OldIdx to NewIdx.1123 void updateRange(LiveRange &LR, VirtRegOrUnit VRegOrUnit,1124 LaneBitmask LaneMask) {1125 if (!Updated.insert(&LR).second)1126 return;1127 LLVM_DEBUG({1128 dbgs() << " ";1129 if (VRegOrUnit.isVirtualReg()) {1130 dbgs() << printReg(VRegOrUnit.asVirtualReg());1131 if (LaneMask.any())1132 dbgs() << " L" << PrintLaneMask(LaneMask);1133 } else {1134 dbgs() << printRegUnit(VRegOrUnit.asMCRegUnit(), &TRI);1135 }1136 dbgs() << ":\t" << LR << '\n';1137 });1138 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))1139 handleMoveDown(LR);1140 else1141 handleMoveUp(LR, VRegOrUnit, LaneMask);1142 LLVM_DEBUG(dbgs() << " -->\t" << LR << '\n');1143 assert(LR.verify());1144 }1145 1146 /// Update LR to reflect an instruction has been moved downwards from OldIdx1147 /// to NewIdx (OldIdx < NewIdx).1148 void handleMoveDown(LiveRange &LR) {1149 LiveRange::iterator E = LR.end();1150 // Segment going into OldIdx.1151 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());1152 1153 // No value live before or after OldIdx? Nothing to do.1154 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))1155 return;1156 1157 LiveRange::iterator OldIdxOut;1158 // Do we have a value live-in to OldIdx?1159 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {1160 // If the live-in value already extends to NewIdx, there is nothing to do.1161 if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))1162 return;1163 // Aggressively remove all kill flags from the old kill point.1164 // Kill flags shouldn't be used while live intervals exist, they will be1165 // reinserted by VirtRegRewriter.1166 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))1167 for (MachineOperand &MOP : mi_bundle_ops(*KillMI))1168 if (MOP.isReg() && MOP.isUse())1169 MOP.setIsKill(false);1170 1171 // Is there a def before NewIdx which is not OldIdx?1172 LiveRange::iterator Next = std::next(OldIdxIn);1173 if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&1174 SlotIndex::isEarlierInstr(Next->start, NewIdx)) {1175 // If we are here then OldIdx was just a use but not a def. We only have1176 // to ensure liveness extends to NewIdx.1177 LiveRange::iterator NewIdxIn =1178 LR.advanceTo(Next, NewIdx.getBaseIndex());1179 // Extend the segment before NewIdx if necessary.1180 if (NewIdxIn == E ||1181 !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {1182 LiveRange::iterator Prev = std::prev(NewIdxIn);1183 Prev->end = NewIdx.getRegSlot();1184 }1185 // Extend OldIdxIn.1186 OldIdxIn->end = Next->start;1187 return;1188 }1189 1190 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR1191 // invalid by overlapping ranges.1192 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);1193 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());1194 // If this was not a kill, then there was no def and we're done.1195 if (!isKill)1196 return;1197 1198 // Did we have a Def at OldIdx?1199 OldIdxOut = Next;1200 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))1201 return;1202 } else {1203 OldIdxOut = OldIdxIn;1204 }1205 1206 // If we are here then there is a Definition at OldIdx. OldIdxOut points1207 // to the segment starting there.1208 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&1209 "No def?");1210 VNInfo *OldIdxVNI = OldIdxOut->valno;1211 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");1212 1213 // If the defined value extends beyond NewIdx, just move the beginning1214 // of the segment to NewIdx.1215 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());1216 if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {1217 OldIdxVNI->def = NewIdxDef;1218 OldIdxOut->start = OldIdxVNI->def;1219 return;1220 }1221 1222 // If we are here then we have a Definition at OldIdx which ends before1223 // NewIdx.1224 1225 // Is there an existing Def at NewIdx?1226 LiveRange::iterator AfterNewIdx1227 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());1228 bool OldIdxDefIsDead = OldIdxOut->end.isDead();1229 if (!OldIdxDefIsDead &&1230 SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {1231 // OldIdx is not a dead def, and NewIdxDef is inside a new interval.1232 VNInfo *DefVNI;1233 if (OldIdxOut != LR.begin() &&1234 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,1235 OldIdxOut->start)) {1236 // There is no gap between OldIdxOut and its predecessor anymore,1237 // merge them.1238 LiveRange::iterator IPrev = std::prev(OldIdxOut);1239 DefVNI = OldIdxVNI;1240 IPrev->end = OldIdxOut->end;1241 } else {1242 // The value is live in to OldIdx1243 LiveRange::iterator INext = std::next(OldIdxOut);1244 assert(INext != E && "Must have following segment");1245 // We merge OldIdxOut and its successor. As we're dealing with subreg1246 // reordering, there is always a successor to OldIdxOut in the same BB1247 // We don't need INext->valno anymore and will reuse for the new segment1248 // we create later.1249 DefVNI = OldIdxVNI;1250 INext->start = OldIdxOut->end;1251 INext->valno->def = INext->start;1252 }1253 // If NewIdx is behind the last segment, extend that and append a new one.1254 if (AfterNewIdx == E) {1255 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up1256 // one position.1257 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end1258 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end1259 std::copy(std::next(OldIdxOut), E, OldIdxOut);1260 // The last segment is undefined now, reuse it for a dead def.1261 LiveRange::iterator NewSegment = std::prev(E);1262 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),1263 DefVNI);1264 DefVNI->def = NewIdxDef;1265 1266 LiveRange::iterator Prev = std::prev(NewSegment);1267 Prev->end = NewIdxDef;1268 } else {1269 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up1270 // one position.1271 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|1272 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|1273 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);1274 LiveRange::iterator Prev = std::prev(AfterNewIdx);1275 // We have two cases:1276 if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {1277 // Case 1: NewIdx is inside a liverange. Split this liverange at1278 // NewIdxDef into the segment "Prev" followed by "NewSegment".1279 LiveRange::iterator NewSegment = AfterNewIdx;1280 *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);1281 Prev->valno->def = NewIdxDef;1282 1283 *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);1284 DefVNI->def = Prev->start;1285 } else {1286 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and1287 // turn Prev into a segment from NewIdx to AfterNewIdx->start.1288 *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);1289 DefVNI->def = NewIdxDef;1290 assert(DefVNI != AfterNewIdx->valno);1291 }1292 }1293 return;1294 }1295 1296 if (AfterNewIdx != E &&1297 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {1298 // There is an existing def at NewIdx. The def at OldIdx is coalesced into1299 // that value.1300 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");1301 LR.removeValNo(OldIdxVNI);1302 } else {1303 // There was no existing def at NewIdx. We need to create a dead def1304 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees1305 // a new segment at the place where we want to construct the dead def.1306 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|1307 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|1308 assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");1309 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);1310 // We can reuse OldIdxVNI now.1311 LiveRange::iterator NewSegment = std::prev(AfterNewIdx);1312 VNInfo *NewSegmentVNI = OldIdxVNI;1313 NewSegmentVNI->def = NewIdxDef;1314 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),1315 NewSegmentVNI);1316 }1317 }1318 1319 /// Update LR to reflect an instruction has been moved upwards from OldIdx1320 /// to NewIdx (NewIdx < OldIdx).1321 void handleMoveUp(LiveRange &LR, VirtRegOrUnit VRegOrUnit,1322 LaneBitmask LaneMask) {1323 LiveRange::iterator E = LR.end();1324 // Segment going into OldIdx.1325 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());1326 1327 // No value live before or after OldIdx? Nothing to do.1328 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))1329 return;1330 1331 LiveRange::iterator OldIdxOut;1332 // Do we have a value live-in to OldIdx?1333 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {1334 // If the live-in value isn't killed here, then we have no Def at1335 // OldIdx, moreover the value must be live at NewIdx so there is nothing1336 // to do.1337 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);1338 if (!isKill)1339 return;1340 1341 // At this point we have to move OldIdxIn->end back to the nearest1342 // previous use or (dead-)def but no further than NewIdx.1343 SlotIndex DefBeforeOldIdx1344 = std::max(OldIdxIn->start.getDeadSlot(),1345 NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));1346 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, VRegOrUnit, LaneMask);1347 1348 // Did we have a Def at OldIdx? If not we are done now.1349 OldIdxOut = std::next(OldIdxIn);1350 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))1351 return;1352 } else {1353 OldIdxOut = OldIdxIn;1354 OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;1355 }1356 1357 // If we are here then there is a Definition at OldIdx. OldIdxOut points1358 // to the segment starting there.1359 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&1360 "No def?");1361 VNInfo *OldIdxVNI = OldIdxOut->valno;1362 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");1363 bool OldIdxDefIsDead = OldIdxOut->end.isDead();1364 1365 // Is there an existing def at NewIdx?1366 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());1367 LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());1368 if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {1369 assert(NewIdxOut->valno != OldIdxVNI &&1370 "Same value defined more than once?");1371 // If OldIdx was a dead def remove it.1372 if (!OldIdxDefIsDead) {1373 // Remove segment starting at NewIdx and move begin of OldIdxOut to1374 // NewIdx so it can take its place.1375 OldIdxVNI->def = NewIdxDef;1376 OldIdxOut->start = NewIdxDef;1377 LR.removeValNo(NewIdxOut->valno);1378 } else {1379 // Simply remove the dead def at OldIdx.1380 LR.removeValNo(OldIdxVNI);1381 }1382 } else {1383 // Previously nothing was live after NewIdx, so all we have to do now is1384 // move the begin of OldIdxOut to NewIdx.1385 if (!OldIdxDefIsDead) {1386 // Do we have any intermediate Defs between OldIdx and NewIdx?1387 if (OldIdxIn != E &&1388 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {1389 // OldIdx is not a dead def and NewIdx is before predecessor start.1390 LiveRange::iterator NewIdxIn = NewIdxOut;1391 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));1392 const SlotIndex SplitPos = NewIdxDef;1393 OldIdxVNI = OldIdxIn->valno;1394 1395 SlotIndex NewDefEndPoint = std::next(NewIdxIn)->end;1396 LiveRange::iterator Prev = std::prev(OldIdxIn);1397 if (OldIdxIn != LR.begin() &&1398 SlotIndex::isEarlierInstr(NewIdx, Prev->end)) {1399 // If the segment before OldIdx read a value defined earlier than1400 // NewIdx, the moved instruction also reads and forwards that1401 // value. Extend the lifetime of the new def point.1402 1403 // Extend to where the previous range started, unless there is1404 // another redef first.1405 NewDefEndPoint = std::min(OldIdxIn->start,1406 std::next(NewIdxOut)->start);1407 }1408 1409 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.1410 OldIdxOut->valno->def = OldIdxIn->start;1411 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,1412 OldIdxOut->valno);1413 // OldIdxIn and OldIdxVNI are now undef and can be overridden.1414 // We Slide [NewIdxIn, OldIdxIn) down one position.1415 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|1416 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|1417 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);1418 // NewIdxIn is now considered undef so we can reuse it for the moved1419 // value.1420 LiveRange::iterator NewSegment = NewIdxIn;1421 LiveRange::iterator Next = std::next(NewSegment);1422 if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {1423 // There is no gap between NewSegment and its predecessor.1424 *NewSegment = LiveRange::Segment(Next->start, SplitPos,1425 Next->valno);1426 1427 *Next = LiveRange::Segment(SplitPos, NewDefEndPoint, OldIdxVNI);1428 Next->valno->def = SplitPos;1429 } else {1430 // There is a gap between NewSegment and its predecessor1431 // Value becomes live in.1432 *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);1433 NewSegment->valno->def = SplitPos;1434 }1435 } else {1436 // Leave the end point of a live def.1437 OldIdxOut->start = NewIdxDef;1438 OldIdxVNI->def = NewIdxDef;1439 if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))1440 OldIdxIn->end = NewIdxDef;1441 }1442 } else if (OldIdxIn != E1443 && SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)1444 && SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)) {1445 // OldIdxVNI is a dead def that has been moved into the middle of1446 // another value in LR. That can happen when LR is a whole register,1447 // but the dead def is a write to a subreg that is dead at NewIdx.1448 // The dead def may have been moved across other values1449 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)1450 // down one position.1451 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |1452 // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|1453 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));1454 // Modify the segment at NewIdxOut and the following segment to meet at1455 // the point of the dead def, with the following segment getting1456 // OldIdxVNI as its value number.1457 *NewIdxOut = LiveRange::Segment(1458 NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);1459 *(NewIdxOut + 1) = LiveRange::Segment(1460 NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);1461 OldIdxVNI->def = NewIdxDef;1462 // Modify subsequent segments to be defined by the moved def OldIdxVNI.1463 for (auto *Idx = NewIdxOut + 2; Idx <= OldIdxOut; ++Idx)1464 Idx->valno = OldIdxVNI;1465 // Aggressively remove all dead flags from the former dead definition.1466 // Kill/dead flags shouldn't be used while live intervals exist; they1467 // will be reinserted by VirtRegRewriter.1468 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))1469 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)1470 if (MO->isReg() && !MO->isUse())1471 MO->setIsDead(false);1472 } else {1473 // OldIdxVNI is a dead def. It may have been moved across other values1474 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)1475 // down one position.1476 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |1477 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|1478 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));1479 // OldIdxVNI can be reused now to build a new dead def segment.1480 LiveRange::iterator NewSegment = NewIdxOut;1481 VNInfo *NewSegmentVNI = OldIdxVNI;1482 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),1483 NewSegmentVNI);1484 NewSegmentVNI->def = NewIdxDef;1485 }1486 }1487 }1488 1489 void updateRegMaskSlots() {1490 SmallVectorImpl<SlotIndex>::iterator RI =1491 llvm::lower_bound(LIS.RegMaskSlots, OldIdx);1492 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&1493 "No RegMask at OldIdx.");1494 *RI = NewIdx.getRegSlot();1495 assert((RI == LIS.RegMaskSlots.begin() ||1496 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&1497 "Cannot move regmask instruction above another call");1498 assert((std::next(RI) == LIS.RegMaskSlots.end() ||1499 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&1500 "Cannot move regmask instruction below another call");1501 }1502 1503 // Return the last use of reg between NewIdx and OldIdx.1504 SlotIndex findLastUseBefore(SlotIndex Before, VirtRegOrUnit VRegOrUnit,1505 LaneBitmask LaneMask) {1506 if (VRegOrUnit.isVirtualReg()) {1507 SlotIndex LastUse = Before;1508 for (MachineOperand &MO :1509 MRI.use_nodbg_operands(VRegOrUnit.asVirtualReg())) {1510 if (MO.isUndef())1511 continue;1512 unsigned SubReg = MO.getSubReg();1513 if (SubReg != 0 && LaneMask.any()1514 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())1515 continue;1516 1517 const MachineInstr &MI = *MO.getParent();1518 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);1519 if (InstSlot > LastUse && InstSlot < OldIdx)1520 LastUse = InstSlot.getRegSlot();1521 }1522 return LastUse;1523 }1524 1525 // This is a regunit interval, so scanning the use list could be very1526 // expensive. Scan upwards from OldIdx instead.1527 assert(Before < OldIdx && "Expected upwards move");1528 SlotIndexes *Indexes = LIS.getSlotIndexes();1529 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);1530 1531 // OldIdx may not correspond to an instruction any longer, so set MII to1532 // point to the next instruction after OldIdx, or MBB->end().1533 MachineBasicBlock::iterator MII = MBB->end();1534 if (MachineInstr *MI = Indexes->getInstructionFromIndex(1535 Indexes->getNextNonNullIndex(OldIdx)))1536 if (MI->getParent() == MBB)1537 MII = MI;1538 1539 MachineBasicBlock::iterator Begin = MBB->begin();1540 while (MII != Begin) {1541 if ((--MII)->isDebugOrPseudoInstr())1542 continue;1543 SlotIndex Idx = Indexes->getInstructionIndex(*MII);1544 1545 // Stop searching when Before is reached.1546 if (!SlotIndex::isEarlierInstr(Before, Idx))1547 return Before;1548 1549 // Check if MII uses Reg.1550 for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)1551 if (MO->isReg() && !MO->isUndef() && MO->getReg().isPhysical() &&1552 TRI.hasRegUnit(MO->getReg(), VRegOrUnit.asMCRegUnit()))1553 return Idx.getRegSlot();1554 }1555 // Didn't reach Before. It must be the first instruction in the block.1556 return Before;1557 }1558};1559 1560void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {1561 // It is fine to move a bundle as a whole, but not an individual instruction1562 // inside it.1563 assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) &&1564 "Cannot move instruction in bundle");1565 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);1566 Indexes->removeMachineInstrFromMaps(MI);1567 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);1568 assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&1569 OldIndex < getMBBEndIdx(MI.getParent()) &&1570 "Cannot handle moves across basic block boundaries.");1571 1572 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);1573 HME.updateAllRanges(&MI);1574}1575 1576void LiveIntervals::handleMoveIntoNewBundle(MachineInstr &BundleStart,1577 bool UpdateFlags) {1578 assert((BundleStart.getOpcode() == TargetOpcode::BUNDLE) &&1579 "Bundle start is not a bundle");1580 SmallVector<SlotIndex, 16> ToProcess;1581 const SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(BundleStart);1582 auto BundleEnd = getBundleEnd(BundleStart.getIterator());1583 1584 auto I = BundleStart.getIterator();1585 I++;1586 while (I != BundleEnd) {1587 if (!Indexes->hasIndex(*I))1588 continue;1589 SlotIndex OldIndex = Indexes->getInstructionIndex(*I, true);1590 ToProcess.push_back(OldIndex);1591 Indexes->removeMachineInstrFromMaps(*I, true);1592 I++;1593 }1594 for (SlotIndex OldIndex : ToProcess) {1595 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);1596 HME.updateAllRanges(&BundleStart);1597 }1598 1599 // Fix up dead defs1600 const SlotIndex Index = getInstructionIndex(BundleStart);1601 for (MachineOperand &MO : BundleStart.operands()) {1602 if (!MO.isReg())1603 continue;1604 Register Reg = MO.getReg();1605 if (Reg.isVirtual() && hasInterval(Reg) && !MO.isUndef()) {1606 LiveInterval &LI = getInterval(Reg);1607 LiveQueryResult LRQ = LI.Query(Index);1608 if (LRQ.isDeadDef())1609 MO.setIsDead();1610 }1611 }1612}1613 1614void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,1615 const MachineBasicBlock::iterator End,1616 const SlotIndex EndIdx, LiveRange &LR,1617 const Register Reg,1618 LaneBitmask LaneMask) {1619 LiveInterval::iterator LII = LR.find(EndIdx);1620 SlotIndex lastUseIdx;1621 if (LII != LR.end() && LII->start < EndIdx) {1622 lastUseIdx = LII->end;1623 } else if (LII == LR.begin()) {1624 // We may not have a liverange at all if this is a subregister untouched1625 // between \p Begin and \p End.1626 } else {1627 --LII;1628 }1629 1630 for (MachineBasicBlock::iterator I = End; I != Begin;) {1631 --I;1632 MachineInstr &MI = *I;1633 if (MI.isDebugOrPseudoInstr())1634 continue;1635 1636 SlotIndex instrIdx = getInstructionIndex(MI);1637 bool isStartValid = getInstructionFromIndex(LII->start);1638 bool isEndValid = getInstructionFromIndex(LII->end);1639 1640 // FIXME: This doesn't currently handle early-clobber or multiple removed1641 // defs inside of the region to repair.1642 for (const MachineOperand &MO : MI.operands()) {1643 if (!MO.isReg() || MO.getReg() != Reg)1644 continue;1645 1646 unsigned SubReg = MO.getSubReg();1647 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);1648 if ((Mask & LaneMask).none())1649 continue;1650 1651 if (MO.isDef()) {1652 if (!isStartValid) {1653 if (LII->end.isDead()) {1654 LII = LR.removeSegment(LII, true);1655 if (LII != LR.begin())1656 --LII;1657 } else {1658 LII->start = instrIdx.getRegSlot();1659 LII->valno->def = instrIdx.getRegSlot();1660 if (MO.getSubReg() && !MO.isUndef())1661 lastUseIdx = instrIdx.getRegSlot();1662 else1663 lastUseIdx = SlotIndex();1664 continue;1665 }1666 }1667 1668 if (!lastUseIdx.isValid()) {1669 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);1670 LiveRange::Segment S(instrIdx.getRegSlot(),1671 instrIdx.getDeadSlot(), VNI);1672 LII = LR.addSegment(S);1673 } else if (LII->start != instrIdx.getRegSlot()) {1674 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);1675 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);1676 LII = LR.addSegment(S);1677 }1678 1679 if (MO.getSubReg() && !MO.isUndef())1680 lastUseIdx = instrIdx.getRegSlot();1681 else1682 lastUseIdx = SlotIndex();1683 } else if (MO.isUse()) {1684 // FIXME: This should probably be handled outside of this branch,1685 // either as part of the def case (for defs inside of the region) or1686 // after the loop over the region.1687 if (!isEndValid && !LII->end.isBlock())1688 LII->end = instrIdx.getRegSlot();1689 if (!lastUseIdx.isValid())1690 lastUseIdx = instrIdx.getRegSlot();1691 }1692 }1693 }1694 1695 bool isStartValid = getInstructionFromIndex(LII->start);1696 if (!isStartValid && LII->end.isDead())1697 LR.removeSegment(*LII, true);1698}1699 1700void1701LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,1702 MachineBasicBlock::iterator Begin,1703 MachineBasicBlock::iterator End,1704 ArrayRef<Register> OrigRegs) {1705 // Find anchor points, which are at the beginning/end of blocks or at1706 // instructions that already have indexes.1707 while (Begin != MBB->begin() && !Indexes->hasIndex(*std::prev(Begin)))1708 --Begin;1709 while (End != MBB->end() && !Indexes->hasIndex(*End))1710 ++End;1711 1712 SlotIndex EndIdx;1713 if (End == MBB->end())1714 EndIdx = getMBBEndIdx(MBB).getPrevSlot();1715 else1716 EndIdx = getInstructionIndex(*End);1717 1718 Indexes->repairIndexesInRange(MBB, Begin, End);1719 1720 // Make sure a live interval exists for all register operands in the range.1721 SmallVector<Register> RegsToRepair(OrigRegs);1722 for (MachineBasicBlock::iterator I = End; I != Begin;) {1723 --I;1724 MachineInstr &MI = *I;1725 if (MI.isDebugOrPseudoInstr())1726 continue;1727 for (const MachineOperand &MO : MI.operands()) {1728 if (MO.isReg() && MO.getReg().isVirtual()) {1729 Register Reg = MO.getReg();1730 if (MO.getSubReg() && hasInterval(Reg) &&1731 MRI->shouldTrackSubRegLiveness(Reg)) {1732 LiveInterval &LI = getInterval(Reg);1733 if (!LI.hasSubRanges()) {1734 // If the new instructions refer to subregs but the old instructions1735 // did not, throw away any old live interval so it will be1736 // recomputed with subranges.1737 removeInterval(Reg);1738 } else if (MO.isDef()) {1739 // Similarly if a subreg def has no precise subrange match then1740 // assume we need to recompute all subranges.1741 unsigned SubReg = MO.getSubReg();1742 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);1743 if (llvm::none_of(LI.subranges(),1744 [Mask](LiveInterval::SubRange &SR) {1745 return SR.LaneMask == Mask;1746 })) {1747 removeInterval(Reg);1748 }1749 }1750 }1751 if (!hasInterval(Reg)) {1752 createAndComputeVirtRegInterval(Reg);1753 // Don't bother to repair a freshly calculated live interval.1754 llvm::erase(RegsToRepair, Reg);1755 }1756 }1757 }1758 }1759 1760 for (Register Reg : RegsToRepair) {1761 if (!Reg.isVirtual())1762 continue;1763 1764 LiveInterval &LI = getInterval(Reg);1765 // FIXME: Should we support undefs that gain defs?1766 if (!LI.hasAtLeastOneValue())1767 continue;1768 1769 for (LiveInterval::SubRange &S : LI.subranges())1770 repairOldRegInRange(Begin, End, EndIdx, S, Reg, S.LaneMask);1771 LI.removeEmptySubRanges();1772 1773 repairOldRegInRange(Begin, End, EndIdx, LI, Reg);1774 }1775}1776 1777void LiveIntervals::removePhysRegDefAt(MCRegister Reg, SlotIndex Pos) {1778 for (MCRegUnit Unit : TRI->regunits(Reg)) {1779 if (LiveRange *LR = getCachedRegUnit(Unit))1780 if (VNInfo *VNI = LR->getVNInfoAt(Pos))1781 LR->removeValNo(VNI);1782 }1783}1784 1785void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {1786 // LI may not have the main range computed yet, but its subranges may1787 // be present.1788 VNInfo *VNI = LI.getVNInfoAt(Pos);1789 if (VNI != nullptr) {1790 assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());1791 LI.removeValNo(VNI);1792 }1793 1794 // Also remove the value defined in subranges.1795 for (LiveInterval::SubRange &S : LI.subranges()) {1796 if (VNInfo *SVNI = S.getVNInfoAt(Pos))1797 if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())1798 S.removeValNo(SVNI);1799 }1800 LI.removeEmptySubRanges();1801}1802 1803void LiveIntervals::splitSeparateComponents(LiveInterval &LI,1804 SmallVectorImpl<LiveInterval*> &SplitLIs) {1805 ConnectedVNInfoEqClasses ConEQ(*this);1806 unsigned NumComp = ConEQ.Classify(LI);1807 if (NumComp <= 1)1808 return;1809 LLVM_DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');1810 Register Reg = LI.reg();1811 for (unsigned I = 1; I < NumComp; ++I) {1812 Register NewVReg = MRI->cloneVirtualRegister(Reg);1813 LiveInterval &NewLI = createEmptyInterval(NewVReg);1814 SplitLIs.push_back(&NewLI);1815 }1816 ConEQ.Distribute(LI, SplitLIs.data(), *MRI);1817}1818 1819void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {1820 assert(LICalc && "LICalc not initialized.");1821 LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());1822 LICalc->constructMainRangeFromSubranges(LI);1823}1824