Lines Matching +full:early +full:- +full:to +full:- +full:mid
1 //===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
31 #include "llvm/Config/llvm-config.h"
49 EnableLoopIVHeuristic("enable-split-loopiv-heuristic",
58 //===----------------------------------------------------------------------===//
60 //===----------------------------------------------------------------------===//
76 if (SMBB->isEHPad()) { in computeLastInsertPoint()
79 } else if (SMBB->isInlineAsmBrIndirectTarget()) in computeLastInsertPoint()
93 // instruction. If there is no such instruction, we don't need to do in computeLastInsertPoint()
110 // back to the call that may throw. in computeLastInsertPoint()
126 if (SlotIndex::isSameInstr(VNI->def, LIP.second)) in computeLastInsertPoint()
128 if (I->getOpcode() == TargetOpcode::STATEPOINT) in computeLastInsertPoint()
132 // really be live-in to the landing pad. This can happen if the landing pad in computeLastInsertPoint()
134 if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd) in computeLastInsertPoint()
137 // Value is properly live-in to the landing pad. in computeLastInsertPoint()
151 //===----------------------------------------------------------------------===//
153 //===----------------------------------------------------------------------===//
167 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
172 // slots for early clobbers. in analyzeUses()
173 for (const VNInfo *VNI : CurLI->valnos) in analyzeUses()
174 if (!VNI->isPHIDef() && !VNI->isUnused()) in analyzeUses()
175 UseSlots.push_back(VNI->def); in analyzeUses()
177 // Get use slots form the use-def chain. in analyzeUses()
179 for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg())) in analyzeUses()
186 // That is what we want for early clobbers. in analyzeUses()
190 // Compute per-live block info. in analyzeUses()
198 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
203 if (CurLI->empty()) in calcLiveBlockInfo()
206 LiveInterval::const_iterator LVI = CurLI->begin(); in calcLiveBlockInfo()
207 LiveInterval::const_iterator LVE = CurLI->end(); in calcLiveBlockInfo()
215 LIS.getMBBFromIndex(LVI->start)->getIterator(); in calcLiveBlockInfo()
220 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); in calcLiveBlockInfo()
224 // mid-block. in calcLiveBlockInfo()
227 ThroughBlocks.set(BI.MBB->getNumber()); in calcLiveBlockInfo()
228 // The range shouldn't end mid-block if there are no uses. This shouldn't in calcLiveBlockInfo()
230 assert(LVI->end >= Stop && "range ends mid block with no uses"); in calcLiveBlockInfo()
237 BI.LastInstr = UseI[-1]; in calcLiveBlockInfo()
241 BI.LiveIn = LVI->start <= Start; in calcLiveBlockInfo()
245 assert(LVI->start == LVI->valno->def && "Dangling Segment start"); in calcLiveBlockInfo()
246 assert(LVI->start == BI.FirstInstr && "First instr should be a def"); in calcLiveBlockInfo()
252 while (LVI->end < Stop) { in calcLiveBlockInfo()
253 SlotIndex LastStop = LVI->end; in calcLiveBlockInfo()
254 if (++LVI == LVE || LVI->start >= Stop) { in calcLiveBlockInfo()
260 if (LastStop < LVI->start) { in calcLiveBlockInfo()
262 // live-in snippet and the live-out snippet. in calcLiveBlockInfo()
265 // Push the Live-in part. in calcLiveBlockInfo()
270 // Set up BI for the live-out part. in calcLiveBlockInfo()
273 BI.FirstInstr = BI.FirstDef = LVI->start; in calcLiveBlockInfo()
277 assert(LVI->start == LVI->valno->def && "Dangling Segment start"); in calcLiveBlockInfo()
279 BI.FirstDef = LVI->start; in calcLiveBlockInfo()
284 // LVI is now at LVE or LVI->end >= Stop. in calcLiveBlockInfo()
289 // Live segment ends exactly at Stop. Move to the next segment. in calcLiveBlockInfo()
290 if (LVI->end == Stop && ++LVI == LVE) in calcLiveBlockInfo()
294 if (LVI->start < Stop) in calcLiveBlockInfo()
297 MFI = LIS.getMBBFromIndex(LVI->start)->getIterator(); in calcLiveBlockInfo()
304 L->isLoopLatch(BI.MBB); in calcLiveBlockInfo()
311 if (cli->empty()) in countLiveBlocks()
314 LiveInterval::iterator LVI = li->begin(); in countLiveBlocks()
315 LiveInterval::iterator LVE = li->end(); in countLiveBlocks()
320 LIS.getMBBFromIndex(LVI->start)->getIterator(); in countLiveBlocks()
324 LVI = li->advanceTo(LVI, Stop); in countLiveBlocks()
330 } while (Stop <= LVI->start); in countLiveBlocks()
335 Register OrigReg = VRM.getOriginal(CurLI->reg()); in isOriginalEndpoint()
341 if (I != Orig.end() && I->start <= Idx) in isOriginalEndpoint()
342 return I->start == Idx; in isOriginalEndpoint()
345 return I != Orig.begin() && (--I)->end == Idx; in isOriginalEndpoint()
354 //===----------------------------------------------------------------------===//
356 //===----------------------------------------------------------------------===//
381 Edit->anyRematerializable(); in reset()
397 /// Find a subrange corresponding to the exact lane mask @p LM in the live
398 /// interval @p LI. The interval @p LI is assumed to contain such a subrange.
399 /// This function is used to find corresponding subranges between the
418 /// Find a subrange corresponding to the lane mask @p LM, or a superset of it,
419 /// in the live interval @p LI. The interval @p LI is assumed to contain such
420 /// a subrange. This function is used to find corresponding subranges between
436 SlotIndex Def = VNI->def; in addDeadDef()
439 // to only update the subranges for which the original subranges had in addDeadDef()
442 auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent()); in addDeadDef()
444 if (PV != nullptr && PV->def == Def) in addDeadDef()
449 // copy. Since rematerialization can regenerate a definition of a sub- in addDeadDef()
450 // register, we need to check which subranges need to be updated. in addDeadDef()
454 for (const MachineOperand &DefOp : DefMI->defs()) { in addDeadDef()
477 assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); in defValue()
478 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); in defValue()
481 VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); in defValue()
483 bool Force = LI->hasSubRanges(); in defValue()
487 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP)); in defValue()
495 if (VNInfo *OldVNI = InsP.first->second.getPointer()) { in defValue()
498 // No longer a simple mapping. Switch to a complex mapping. If the in defValue()
500 InsP.first->second = ValueForcePair(nullptr, Force); in defValue()
521 addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false); in forceRecompute()
541 CopyMI->bundleWithPred(); in buildSingleSubRegCopy()
559 // Only a subset of lanes needs to be copied. The following is a simple in buildCopy()
560 // heuristic to construct a sequence of COPYs. We could add a target in buildCopy()
561 // specific callback if this turns out to be suboptimal. in buildCopy()
562 LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx)); in buildCopy()
564 // First pass: Try to find a perfectly matching subregister index. If none in buildCopy()
573 report_fatal_error("Impossible to implement partial COPY"); in buildCopy()
596 LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); in defFromParent()
598 // We may be trying to avoid interference that ends at a deleted instruction, in defFromParent()
599 // so always begin RegIdx 0 early and all others late. in defFromParent()
602 // Attempt cheap-as-a-copy rematerialization. in defFromParent()
603 Register Original = VRM.getOriginal(Edit->get(RegIdx)); in defFromParent()
607 Register Reg = LI->reg(); in defFromParent()
611 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); in defFromParent()
612 if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) { in defFromParent()
613 Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late); in defFromParent()
637 Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx); in defFromParent()
648 if (Edit->empty()) in openIntv()
649 Edit->createEmptyInterval(); in openIntv()
652 OpenIdx = Edit->size(); in openIntv()
653 Edit->createEmptyInterval(); in openIntv()
659 assert(Idx < Edit->size() && "Can only select previously opened interval"); in selectIntv()
660 LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n'); in selectIntv()
668 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); in enterIntvBefore()
673 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); in enterIntvBefore()
677 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); in enterIntvBefore()
678 return VNI->def; in enterIntvBefore()
685 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); in enterIntvAfter()
690 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); in enterIntvAfter()
694 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), in enterIntvAfter()
696 return VNI->def; in enterIntvAfter()
705 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); in enterIntvAtEnd()
713 // just selected starts at that def. For this case to exist, the def in enterIntvAtEnd()
719 ParentVNI = Edit->getParent().getVNInfoAt(Last); in enterIntvAtEnd()
721 // undef use --> undef tied def in enterIntvAtEnd()
727 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id); in enterIntvAtEnd()
730 RegAssign.insert(VNI->def, End, OpenIdx); in enterIntvAtEnd()
732 return VNI->def; in enterIntvAtEnd()
735 /// useIntv - indicate that all instructions in MBB should use OpenLI.
753 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); in leaveIntvAfter()
758 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); in leaveIntvAfter()
764 // value. The inserted COPY is not a kill, and we don't need to recompute in leaveIntvAfter()
765 // the source live range. The spiller also won't try to hoist this copy. in leaveIntvAfter()
766 if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && in leaveIntvAfter()
767 MI->readsVirtualRegister(Edit->getReg())) { in leaveIntvAfter()
769 defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); in leaveIntvAfter()
773 VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), in leaveIntvAfter()
775 return VNI->def; in leaveIntvAfter()
784 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); in leaveIntvBefore()
789 LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); in leaveIntvBefore()
793 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); in leaveIntvBefore()
794 return VNI->def; in leaveIntvBefore()
803 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); in leaveIntvAtTop()
810 Register Reg = LIS.getInterval(Edit->get(RegIdx)).reg(); in leaveIntvAtTop()
813 RegAssign.insert(Start, VNI->def, OpenIdx); in leaveIntvAtTop()
815 return VNI->def; in leaveIntvAtTop()
826 const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); in overlapIntv()
827 assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && in overlapIntv()
836 // If the last use is tied to a def, we can't mark it as live for the in overlapIntv()
838 // to end up in two different intervals. in overlapIntv()
840 if (hasTiedUseOf(*MI, Edit->getReg())) { in overlapIntv()
841 LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n"); in overlapIntv()
850 //===----------------------------------------------------------------------===//
852 //===----------------------------------------------------------------------===//
855 LiveInterval *LI = &LIS.getInterval(Edit->get(0)); in removeBackCopies()
856 LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); in removeBackCopies()
861 SlotIndex Def = C->def; in removeBackCopies()
863 assert(MI && "No instruction for back-copy"); in removeBackCopies()
865 MachineBasicBlock *MBB = MI->getParent(); in removeBackCopies()
868 do AtBegin = MBBI == MBB->begin(); in removeBackCopies()
869 while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr()); in removeBackCopies()
874 MI->eraseFromParent(); in removeBackCopies()
876 // Adjust RegAssign if a register assignment is killed at Def. We want to in removeBackCopies()
885 // We could hoist back-copy right after another back-copy. As a result in removeBackCopies()
886 // MMBI points to copy instruction which is actually dead now. in removeBackCopies()
887 // We cannot set its stop to MBBI which will be the same as start and in removeBackCopies()
891 if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg()) || in removeBackCopies()
895 forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def)); in removeBackCopies()
897 LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); in removeBackCopies()
930 // We'll never be able to exit the DefLoop. in findShallowDominator()
939 unsigned Depth = Loop->getLoopDepth(); in findShallowDominator()
948 // Leave loop by going to the immediate dominator of the loop header. in findShallowDominator()
950 MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); in findShallowDominator()
956 MBB = IDom->getBlock(); in findShallowDominator()
962 LiveInterval *LI = &LIS.getInterval(Edit->get(0)); in computeRedundantBackCopies()
963 const LiveInterval *Parent = &Edit->getParent(); in computeRedundantBackCopies()
964 SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums()); in computeRedundantBackCopies()
968 for (VNInfo *VNI : LI->valnos) { in computeRedundantBackCopies()
969 if (VNI->isUnused()) in computeRedundantBackCopies()
971 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); in computeRedundantBackCopies()
972 EqualVNs[ParentVNI->id].insert(VNI); in computeRedundantBackCopies()
976 // redundant VNIs to BackCopies. in computeRedundantBackCopies()
977 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { in computeRedundantBackCopies()
978 const VNInfo *ParentVNI = Parent->getValNumInfo(i); in computeRedundantBackCopies()
979 if (!NotToHoistSet.count(ParentVNI->id)) in computeRedundantBackCopies()
981 SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin(); in computeRedundantBackCopies()
983 for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) { in computeRedundantBackCopies()
985 for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) { in computeRedundantBackCopies()
989 MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def); in computeRedundantBackCopies()
990 MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def); in computeRedundantBackCopies()
992 DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1)); in computeRedundantBackCopies()
1008 /// For SM_Size mode, find a common dominator for all the back-copies for
1009 /// the same ParentVNI and hoist the backcopies to the dominator BB.
1011 /// to do the hoisting, simply remove the dominated backcopies for the same
1015 LiveInterval *LI = &LIS.getInterval(Edit->get(0)); in hoistCopies()
1016 const LiveInterval *Parent = &Edit->getParent(); in hoistCopies()
1018 // Track the nearest common dominator for all back-copies for each ParentVNI, in hoistCopies()
1019 // indexed by ParentVNI->id. in hoistCopies()
1021 SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); in hoistCopies()
1022 // The total cost of all the back-copies for each ParentVNI. in hoistCopies()
1023 SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums()); in hoistCopies()
1024 // The ParentVNI->id set for which hoisting back-copies are not beneficial in hoistCopies()
1029 // back-copies. If a single back-copy dominates, put it in DomPair.second. in hoistCopies()
1030 for (VNInfo *VNI : LI->valnos) { in hoistCopies()
1031 if (VNI->isUnused()) in hoistCopies()
1033 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); in hoistCopies()
1036 // Don't hoist remats. The complement is probably going to disappear in hoistCopies()
1038 if (Edit->didRematerialize(ParentVNI)) in hoistCopies()
1041 MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); in hoistCopies()
1043 DomPair &Dom = NearestDom[ParentVNI->id]; in hoistCopies()
1048 if (VNI->def == ParentVNI->def) { in hoistCopies()
1049 LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); in hoistCopies()
1050 Dom = DomPair(ValMBB, VNI->def); in hoistCopies()
1053 // Skip the singly mapped values. There is nothing to gain from hoisting a in hoistCopies()
1054 // single back-copy. in hoistCopies()
1055 if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { in hoistCopies()
1056 LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); in hoistCopies()
1062 Dom = DomPair(ValMBB, VNI->def); in hoistCopies()
1065 if (!Dom.second.isValid() || VNI->def < Dom.second) in hoistCopies()
1066 Dom.second = VNI->def; in hoistCopies()
1073 Dom = DomPair(ValMBB, VNI->def); in hoistCopies()
1075 // None dominate. Hoist to common dominator, need new def. in hoistCopies()
1077 Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB); in hoistCopies()
1080 LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' in hoistCopies()
1081 << VNI->def << " for parent " << ParentVNI->id << '@' in hoistCopies()
1082 << ParentVNI->def << " hoist to " in hoistCopies()
1088 for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { in hoistCopies()
1093 const VNInfo *ParentVNI = Parent->getValNumInfo(i); in hoistCopies()
1094 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); in hoistCopies()
1098 MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) { in hoistCopies()
1099 NotToHoistSet.insert(ParentVNI->id); in hoistCopies()
1103 if (LSP <= ParentVNI->def) { in hoistCopies()
1104 NotToHoistSet.insert(ParentVNI->id); in hoistCopies()
1108 SA.getLastSplitPointIter(Dom.first))->def; in hoistCopies()
1111 // Remove redundant back-copies that are now known to be dominated by another in hoistCopies()
1114 for (VNInfo *VNI : LI->valnos) { in hoistCopies()
1115 if (VNI->isUnused()) in hoistCopies()
1117 VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); in hoistCopies()
1118 const DomPair &Dom = NearestDom[ParentVNI->id]; in hoistCopies()
1119 if (!Dom.first || Dom.second == VNI->def || in hoistCopies()
1120 NotToHoistSet.count(ParentVNI->id)) in hoistCopies()
1126 // If it is not beneficial to hoist all the BackCopies, simply remove in hoistCopies()
1134 /// transferValues - Transfer all possible values to the new live ranges.
1139 for (const LiveRange::Segment &S : Edit->getParent()) { in transferValues()
1161 // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. in transferValues()
1163 << printReg(Edit->get(RegIdx)) << ')'); in transferValues()
1164 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); in transferValues()
1167 ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); in transferValues()
1169 LLVM_DEBUG(dbgs() << ':' << VNI->id); in transferValues()
1186 // so the live range is accurate. Add live-in blocks in [Start;End) to the in transferValues()
1188 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); in transferValues()
1190 std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB); in transferValues()
1192 // The first block may be live-in, or it may have its own def. in transferValues()
1196 LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB)); in transferValues()
1197 // MBB has its own def. Is it also live-out? in transferValues()
1201 // Skip to the next block for live-in. in transferValues()
1206 // Handle the live-in blocks covered by [Start;End). in transferValues()
1207 assert(Start <= BlockStart && "Expected live-in block"); in transferValues()
1211 if (BlockStart == ParentVNI->def) { in transferValues()
1212 // This block has the def of a parent PHI, so it isn't live-in. in transferValues()
1213 assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); in transferValues()
1217 LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well. in transferValues()
1219 // This block needs a live-in value. The last block covered may not in transferValues()
1220 // be live-out. in transferValues()
1224 // Live-through, and we don't know the value. in transferValues()
1248 if (Seg->end != Def.getDeadSlot()) in removeDeadSegment()
1261 // The predecessor may not have a live-out value. That is OK, like an in extendPHIRange()
1263 const LiveInterval &PLI = Edit->getParent(); in extendPHIRange()
1264 // Need the cast because the inputs to ?: would otherwise be deemed in extendPHIRange()
1274 // Extend live ranges to be live-out for successor PHI values. in extendPHIKillRanges()
1277 // remove it. Otherwise, extend the live interval to reach the end indexes in extendPHIKillRanges()
1280 const LiveInterval &ParentLI = Edit->getParent(); in extendPHIKillRanges()
1282 if (V->isUnused() || !V->isPHIDef()) in extendPHIKillRanges()
1285 unsigned RegIdx = RegAssign.lookup(V->def); in extendPHIKillRanges()
1286 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); in extendPHIKillRanges()
1288 MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); in extendPHIKillRanges()
1289 if (!removeDeadSegment(V->def, LI)) in extendPHIKillRanges()
1298 if (V->isUnused() || !V->isPHIDef()) in extendPHIKillRanges()
1300 unsigned RegIdx = RegAssign.lookup(V->def); in extendPHIKillRanges()
1301 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); in extendPHIKillRanges()
1303 if (removeDeadSegment(V->def, S)) in extendPHIKillRanges()
1306 MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); in extendPHIKillRanges()
1316 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
1330 llvm::make_early_inc_range(MRI.reg_operands(Edit->getReg()))) { in rewriteAssigned()
1333 if (MI->isDebugValue()) { in rewriteAssigned()
1340 // which register we choose. When the use operand is tied to a def, we must in rewriteAssigned()
1346 // Rewrite to the mapped register at Idx. in rewriteAssigned()
1348 LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); in rewriteAssigned()
1350 LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent()) in rewriteAssigned()
1353 // Extend liveness to Idx if the instruction reads reg. in rewriteAssigned()
1361 // We may want to extend a live range for a partial redef, or for a use in rewriteAssigned()
1362 // tied to an early clobber. in rewriteAssigned()
1363 if (!Edit->getParent().liveAt(Idx.getPrevSlot())) in rewriteAssigned()
1369 // We want to extend a live range into `e` slot rather than `r` slot if in rewriteAssigned()
1370 // tied-def is early clobber, because the `e` slot already contained in rewriteAssigned()
1371 // in the live range of early-clobber tied-def operand, give an example in rewriteAssigned()
1374 // 16 early-clobber %0 = Op %0 (tied-def 0), ... in rewriteAssigned()
1378 // The point we want to extend is 0d to 16e not 16r in this case, but if in rewriteAssigned()
1382 unsigned DefOpIdx = MI->findTiedOperandIdx(OpIdx); in rewriteAssigned()
1383 const MachineOperand &DefOp = MI->getOperand(DefOpIdx); in rewriteAssigned()
1392 // We have to delay extending subranges until we have seen all operands in rewriteAssigned()
1393 // defining the register. This is because a <def,read-undef> operand in rewriteAssigned()
1405 LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx)); in rewriteAssigned()
1417 // %0:subreg_hireg<def,read-undef> = ... in rewriteAssigned()
1444 for (const LiveRange::Segment &S : LI->segments) { in deleteRematVictims()
1446 if (S.end != S.valno->def.getDeadSlot()) in deleteRematVictims()
1448 if (S.valno->isPHIDef()) in deleteRematVictims()
1450 MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); in deleteRematVictims()
1452 MI->addRegisterDead(LI->reg(), &TRI); in deleteRematVictims()
1454 if (!MI->allDefsAreDead()) in deleteRematVictims()
1465 Edit->eliminateDeadDefs(Dead, std::nullopt); in deleteRematVictims()
1469 // Fast-path for common case. in forceRecomputeVNI()
1471 for (unsigned I = 0, E = Edit->size(); I != E; ++I) in forceRecomputeVNI()
1482 const LiveInterval &ParentLI = Edit->getParent(); in forceRecomputeVNI()
1487 for (unsigned I = 0, E = Edit->size(); I != E; ++I) in forceRecomputeVNI()
1506 // At this point, the live intervals in Edit contain VNInfos corresponding to in finish()
1510 for (const VNInfo *ParentVNI : Edit->getParent().valnos) { in finish()
1511 if (ParentVNI->isUnused()) in finish()
1513 unsigned RegIdx = RegAssign.lookup(ParentVNI->def); in finish()
1514 defValue(RegIdx, ParentVNI, ParentVNI->def, true); in finish()
1516 // Force rematted values to be recomputed everywhere. in finish()
1518 if (Edit->didRematerialize(ParentVNI)) in finish()
1522 // Hoist back-copies to the complement interval when in spill mode. in finish()
1525 // Leave all back-copies as is. in finish()
1548 // Get rid of unused values and set phi-kill flags. in finish()
1555 // Provide a reverse mapping from original indices to Edit ranges. in finish()
1557 auto Seq = llvm::seq<unsigned>(0, Edit->size()); in finish()
1558 LRMap->assign(Seq.begin(), Seq.end()); in finish()
1563 for (unsigned i = 0, e = Edit->size(); i != e; ++i) { in finish()
1565 Register VReg = Edit->get(i); in finish()
1571 VRM.setIsSplitFromReg(SplitLI->reg(), Original); in finish()
1573 // The new intervals all map back to i. in finish()
1575 LRMap->resize(Edit->size(), i); in finish()
1579 Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI); in finish()
1581 assert(!LRMap || LRMap->size() == Edit->size()); in finish()
1584 //===----------------------------------------------------------------------===//
1586 //===----------------------------------------------------------------------===//
1596 // Splitting a live-through range always makes progress. in shouldSplitSingleBlock()
1601 bool copyLike = TII.isCopyInstr(*MI) || MI->isSubregToReg(); in shouldSplitSingleBlock()
1623 //===----------------------------------------------------------------------===//
1625 //===----------------------------------------------------------------------===//
1628 // global algorithm to decide intervals for CFG edges. They will insert split
1638 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); in splitLiveThroughBlock()
1641 << ") intf " << LeaveBefore << '-' << EnterAfter in splitLiveThroughBlock()
1642 << ", live-through " << IntvIn << " -> " << IntvOut); in splitLiveThroughBlock()
1656 // |-----------| Live through. in splitLiveThroughBlock()
1657 // -____________ Spill on entry. in splitLiveThroughBlock()
1670 // |-----------| Live through. in splitLiveThroughBlock()
1671 // ___________-- Reload on exit. in splitLiveThroughBlock()
1683 // |-----------| Live through. in splitLiveThroughBlock()
1684 // ------------- Straight through, same intv, no interference. in splitLiveThroughBlock()
1699 // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. in splitLiveThroughBlock()
1700 // |-----------| Live through. in splitLiveThroughBlock()
1701 // ------======= Switch intervals between interference. in splitLiveThroughBlock()
1721 // |-----------| Live through. in splitLiveThroughBlock()
1722 // ==---------== Switch intervals before/after interference. in splitLiveThroughBlock()
1740 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); in splitRegInBlock()
1743 << Stop << "), uses " << BI.FirstInstr << '-' in splitRegInBlock()
1744 << BI.LastInstr << ", reg-in " << IntvIn in splitRegInBlock()
1746 << (BI.LiveOut ? ", stack-out" : ", killed in block")); in splitRegInBlock()
1749 assert(BI.LiveIn && "Must be live-in"); in splitRegInBlock()
1756 // |---o---x | Killed in block. in splitRegInBlock()
1769 // |---o---o---| Live-out on stack. in splitRegInBlock()
1773 // |---o---o--o| Live-out on stack, late last use. in splitRegInBlock()
1774 // ============ Copy to stack after LSP, overlap IntvIn. in splitRegInBlock()
1775 // \_____ Stack interval is live-out. in splitRegInBlock()
1794 // The interference is overlapping somewhere we wanted to use IntvIn. That in splitRegInBlock()
1795 // means we need to create a local interval that can be allocated a in splitRegInBlock()
1804 // |---o---o---| Live-out on stack. in splitRegInBlock()
1805 // =====----____ Leave IntvIn before interference, then spill. in splitRegInBlock()
1807 SlotIndex To = leaveIntvAfter(BI.LastInstr); in splitRegInBlock() local
1809 useIntv(From, To); in splitRegInBlock()
1817 // |---o---o--o| Live-out on stack, late last use. in splitRegInBlock()
1818 // =====------- Copy to stack before LSP, overlap LocalIntv. in splitRegInBlock()
1819 // \_____ Stack interval is live-out. in splitRegInBlock()
1821 SlotIndex To = leaveIntvBefore(LSP); in splitRegInBlock() local
1822 overlapIntv(To, BI.LastInstr); in splitRegInBlock()
1823 SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); in splitRegInBlock()
1824 useIntv(From, To); in splitRegInBlock()
1833 std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); in splitRegOutBlock()
1836 << Stop << "), uses " << BI.FirstInstr << '-' in splitRegOutBlock()
1837 << BI.LastInstr << ", reg-out " << IntvOut in splitRegOutBlock()
1839 << (BI.LiveIn ? ", stack-in" : ", defined in block")); in splitRegOutBlock()
1844 assert(BI.LiveOut && "Must be live-out"); in splitRegOutBlock()
1851 // | o---o---| Defined in block. in splitRegOutBlock()
1863 // |---o---o---| Live-through, stack-in. in splitRegOutBlock()
1873 // The interference is overlapping somewhere we wanted to use IntvOut. That in splitRegOutBlock()
1874 // means we need to create a local interval that can be allocated a in splitRegOutBlock()
1879 // |---o---o---| Live-through, stack-in. in splitRegOutBlock()
1880 // ____---====== Create local interval for interference range. in splitRegOutBlock()
1894 << "uses " << FirstInstr << " to " << LastInstr << ", " in print()