Lines Matching +full:csr +full:- +full:2 +full:l
1 //===- RegAllocGreedy.cpp - greedy register allocator ---------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
86 "split-spill-mode", cl::Hidden,
94 LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
99 "lcr-max-interf", cl::Hidden,
105 "exhaustive-register-search", cl::NotHidden,
111 "enable-deferred-spilling", cl::Hidden,
120 CSRFirstTimeCost("regalloc-csr-first-time-cost",
121 cl::desc("Cost for first time use of callee-saved register."),
125 "grow-region-complexity-budget",
131 "greedy-regclass-priority-trumps-globalness",
138 "greedy-reverse-local-assignment",
144 "split-threshold-for-reg-with-hint",
230 //===----------------------------------------------------------------------===//
232 //===----------------------------------------------------------------------===//
235 LiveInterval &LI = LIS->getInterval(VirtReg); in LRE_CanEraseVirtReg()
236 if (VRM->hasPhys(VirtReg)) { in LRE_CanEraseVirtReg()
237 Matrix->unassign(LI); in LRE_CanEraseVirtReg()
243 // Nonetheless, clear the live-range so that the debug in LRE_CanEraseVirtReg()
250 if (!VRM->hasPhys(VirtReg)) in LRE_WillShrinkVirtReg()
254 LiveInterval &LI = LIS->getInterval(VirtReg); in LRE_WillShrinkVirtReg()
255 Matrix->unassign(LI); in LRE_WillShrinkVirtReg()
260 ExtraInfo->LRE_DidCloneVirtReg(New, Old); in LRE_DidCloneVirtReg()
287 const Register Reg = LI->reg(); in enqueue()
290 auto Stage = ExtraInfo->getOrInitStage(Reg); in enqueue()
293 ExtraInfo->setStage(Reg, Stage); in enqueue()
296 unsigned Ret = PriorityAdvisor->getPriority(*LI); in enqueue()
298 // The virtual register number is a tie breaker for same-sized ranges. in enqueue()
323 const TargetRegisterClass &RC = *MRI->getRegClass(Reg); in getPriority()
327 (2 * RegClassInfo.getNumAllocatableRegs(&RC))); in getPriority()
331 LIS->intervalIsInOneMBB(LI)) { in getPriority()
336 Prio = LI.beginIndex().getApproxInstrDistance(Indexes->getLastIndex()); in getPriority()
341 Prio = Indexes->getZeroIndex().getApproxInstrDistance(LI.endIndex()); in getPriority()
344 // Allocate global and split ranges in long->short order. Long ranges that in getPriority()
355 // 29-25 AllocPriority in getPriority()
359 // 28-24 AllocPriority in getPriority()
360 // 0-23 Size/Instr distance in getPriority()
375 if (VRM->hasKnownPreference(Reg)) in getPriority()
387 LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second); in dequeue()
392 //===----------------------------------------------------------------------===//
394 //===----------------------------------------------------------------------===//
396 /// tryAssign - Try to assign VirtReg to an available register.
404 if (!Matrix->checkInterference(VirtReg, *I)) { in tryAssign()
418 if (Register Hint = MRI->getSimpleHint(VirtReg.reg())) in tryAssign()
423 if (EvictAdvisor->canEvictHintInterference(VirtReg, PhysHint, in tryAssign()
451 //===----------------------------------------------------------------------===//
453 //===----------------------------------------------------------------------===//
459 LiveIntervalUnion::Query SubQ(VirtReg, Matrix->getLiveUnions()[Unit]); in canReassign()
468 if (none_of(TRI->regunits(Reg), HasRegUnitInterference)) { in canReassign()
478 /// evictInterference - Evict any interferring registers that prevent VirtReg
487 unsigned Cascade = ExtraInfo->getOrAssignNewCascade(VirtReg.reg()); in evictInterference()
494 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { in evictInterference()
495 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, Unit); in evictInterference()
507 if (!VRM->hasPhys(Intf->reg())) in evictInterference()
510 Matrix->unassign(*Intf); in evictInterference()
511 assert((ExtraInfo->getCascade(Intf->reg()) < Cascade || in evictInterference()
512 VirtReg.isSpillable() < Intf->isSpillable()) && in evictInterference()
514 ExtraInfo->setCascade(Intf->reg(), Cascade); in evictInterference()
516 NewVRegs.push_back(Intf->reg()); in evictInterference()
523 MCRegister CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg); in isUnusedCalleeSavedReg() local
524 if (!CSR) in isUnusedCalleeSavedReg()
527 return !Matrix->isPhysRegUsed(PhysReg); in isUnusedCalleeSavedReg()
538 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg()); in getOrderLimit()
541 LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = " in getOrderLimit()
561 // The first use of a callee-saved register in a function has cost 1. in canAllocatePhysReg()
562 // Don't start using a CSR when the CostPerUseLimit is low. in canAllocatePhysReg()
565 dbgs() << printReg(PhysReg, TRI) << " would clobber CSR " in canAllocatePhysReg()
573 /// tryEvict - Try to evict all interferences for a physreg.
585 MCRegister BestPhys = EvictAdvisor->tryFindEvictionCandidate( in tryEvict()
592 //===----------------------------------------------------------------------===//
594 //===----------------------------------------------------------------------===//
596 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
603 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); in addSplitConstraints()
612 BC.Number = BI.MBB->getNumber(); in addSplitConstraints()
616 !LIS->getInstructionFromIndex(BI.LastInstr)->isImplicitDef()) in addSplitConstraints()
627 // Interference for the live-in value. in addSplitConstraints()
629 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) { in addSplitConstraints()
643 SA->getFirstSplitPoint(BC.Number))) in addSplitConstraints()
647 // Interference for the live-out value. in addSplitConstraints()
649 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) { in addSplitConstraints()
661 while (Ins--) in addSplitConstraints()
662 StaticCost += SpillPlacer->getBlockFrequency(BC.Number); in addSplitConstraints()
666 // Add constraints for use-blocks. Note that these are the only constraints in addSplitConstraints()
668 SpillPlacer->addConstraints(SplitConstraints); in addSplitConstraints()
669 return SpillPlacer->scanActiveBundles(); in addSplitConstraints()
672 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
673 /// live-through blocks in Blocks.
688 SpillPlacer->addLinks(ArrayRef(TBS, T)); in addThroughConstraints()
698 MachineBasicBlock *MBB = MF->getBlockNumbered(Number); in addThroughConstraints()
699 auto FirstNonDebugInstr = MBB->getFirstNonDebugInstr(); in addThroughConstraints()
700 if (FirstNonDebugInstr != MBB->end() && in addThroughConstraints()
701 SlotIndex::isEarlierInstr(LIS->getInstructionIndex(*FirstNonDebugInstr), in addThroughConstraints()
702 SA->getFirstSplitPoint(Number))) in addThroughConstraints()
704 // Interference for the live-in value. in addThroughConstraints()
705 if (Intf.first() <= Indexes->getMBBStartIdx(Number)) in addThroughConstraints()
710 // Interference for the live-out value. in addThroughConstraints()
711 if (Intf.last() >= SA->getLastSplitPoint(Number)) in addThroughConstraints()
717 SpillPlacer->addConstraints(ArrayRef(BCS, B)); in addThroughConstraints()
722 SpillPlacer->addConstraints(ArrayRef(BCS, B)); in addThroughConstraints()
723 SpillPlacer->addLinks(ArrayRef(TBS, T)); in addThroughConstraints()
729 BitVector Todo = SA->getThroughBlocks(); in growRegion()
738 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive(); in growRegion()
742 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle); in growRegion()
746 Budget -= Blocks.size(); in growRegion()
775 if (SA->looksLikeLoopIV() && NewBlocks.size() >= 2) { in growRegion()
777 // loop-internal blocks. If the block is indeed a header, don't make in growRegion()
779 // Header<->Latch. in growRegion()
780 MachineLoop *L = Loops->getLoopFor(MF->getBlockNumbered(NewBlocks[0])); in growRegion() local
781 if (L && L->getHeader()->getNumber() == (int)NewBlocks[0] && in growRegion()
783 return L == Loops->getLoopFor(MF->getBlockNumbered(Block)); in growRegion()
788 SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true); in growRegion()
793 SpillPlacer->iterate(); in growRegion()
799 /// calcCompactRegion - Compute the set of edge bundles that should be live
802 /// regions formed by removing all the live-through blocks from the live range.
808 if (!SA->getNumThroughBlocks()) in calcCompactRegion()
818 SpillPlacer->prepare(Cand.LiveBundles); in calcCompactRegion()
832 SpillPlacer->finish(); in calcCompactRegion()
847 /// calcSpillCost - Compute how expensive it would be to split the live range in
851 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); in calcSpillCost()
853 unsigned Number = BI.MBB->getNumber(); in calcSpillCost()
854 // We normally only need one spill instruction - a load or a store. in calcSpillCost()
855 Cost += SpillPlacer->getBlockFrequency(Number); in calcSpillCost()
859 Cost += SpillPlacer->getBlockFrequency(Number); in calcSpillCost()
864 /// calcGlobalSplitCost - Return the global split cost of following the split
872 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); in calcGlobalSplitCost()
876 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)]; in calcGlobalSplitCost()
877 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)]; in calcGlobalSplitCost()
886 while (Ins--) in calcGlobalSplitCost()
887 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number); in calcGlobalSplitCost()
891 bool RegIn = LiveBundles[Bundles->getBundle(Number, false)]; in calcGlobalSplitCost()
892 bool RegOut = LiveBundles[Bundles->getBundle(Number, true)]; in calcGlobalSplitCost()
899 GlobalCost += SpillPlacer->getBlockFrequency(Number); in calcGlobalSplitCost()
900 GlobalCost += SpillPlacer->getBlockFrequency(Number); in calcGlobalSplitCost()
904 // live-in / stack-out or stack-in live-out. in calcGlobalSplitCost()
905 GlobalCost += SpillPlacer->getBlockFrequency(Number); in calcGlobalSplitCost()
910 /// splitAroundRegion - Split the current live range around the regions
915 /// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor
931 // Isolate even single instructions when dealing with a proper sub-class. in splitAroundRegion()
934 Register Reg = SA->getParent().reg(); in splitAroundRegion()
935 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); in splitAroundRegion()
938 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); in splitAroundRegion()
940 unsigned Number = BI.MBB->getNumber(); in splitAroundRegion()
944 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)]; in splitAroundRegion()
953 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)]; in splitAroundRegion()
965 if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) in splitAroundRegion()
966 SE->splitSingleBlock(BI); in splitAroundRegion()
971 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); in splitAroundRegion()
973 SE->splitRegInBlock(BI, IntvIn, IntfIn); in splitAroundRegion()
975 SE->splitRegOutBlock(BI, IntvOut, IntfOut); in splitAroundRegion()
978 // Handle live-through blocks. The relevant live-through blocks are stored in in splitAroundRegion()
981 BitVector Todo = SA->getThroughBlocks(); in splitAroundRegion()
992 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)]; in splitAroundRegion()
1000 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)]; in splitAroundRegion()
1009 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut); in splitAroundRegion()
1016 SE->finish(&IntvMap); in splitAroundRegion()
1017 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); in splitAroundRegion()
1019 unsigned OrigBlocks = SA->getNumLiveBlocks(); in splitAroundRegion()
1022 // - Remainder intervals should not be split again. in splitAroundRegion()
1023 // - Candidate intervals can be assigned to Cand.PhysReg. in splitAroundRegion()
1024 // - Block-local splits are candidates for local splitting. in splitAroundRegion()
1025 // - DCE leftovers should go back on the queue. in splitAroundRegion()
1027 const LiveInterval &Reg = LIS->getInterval(LREdit.get(I)); in splitAroundRegion()
1030 if (ExtraInfo->getOrInitStage(Reg.reg()) != RS_New) in splitAroundRegion()
1036 ExtraInfo->setStage(Reg, RS_Spill); in splitAroundRegion()
1043 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) { in splitAroundRegion()
1047 ExtraInfo->setStage(Reg, RS_Split2); in splitAroundRegion()
1057 MF->verify(this, "After splitting live range around region"); in splitAroundRegion()
1063 if (!TRI->shouldRegionSplitForVirtReg(*MF, VirtReg)) in tryRegionSplit()
1076 // No benefit from the compact region, our fallback will be per-block in tryRegionSplit()
1113 --NumCands; in calculateRegionSplitCostAroundReg()
1124 SpillPlacer->prepare(Cand.LiveBundles); in calculateRegionSplitCostAroundReg()
1147 SpillPlacer->finish(); in calculateRegionSplitCostAroundReg()
1179 if (IgnoreCSR && EvictAdvisor->isUnusedCalleeSavedReg(PhysReg)) in calculateRegionSplitCost()
1195 SE->reset(LREdit, SplitSpillMode); in doRegionSplit()
1198 BundleCand.assign(Bundles->getNumBundles(), NoCand); in doRegionSplit()
1205 Cand.IntvIdx = SE->openIntv(); in doRegionSplit()
1218 Cand.IntvIdx = SE->openIntv(); in doRegionSplit()
1238 if (MF->getFunction().hasOptSize()) in trySplitAroundHintReg()
1242 if (ExtraInfo->getStage(VirtReg) >= RS_Split2) in trySplitAroundHintReg()
1251 for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) { in trySplitAroundHintReg()
1252 if (!TII->isFullCopyInstr(Instr)) in trySplitAroundHintReg()
1260 if (VirtReg.liveAt(LIS->getInstructionIndex(Instr).getRegSlot())) in trySplitAroundHintReg()
1264 OtherReg.isPhysical() ? OtherReg.asMCReg() : VRM->getPhys(OtherReg); in trySplitAroundHintReg()
1266 Cost += MBFI->getBlockFreq(Instr.getParent()); in trySplitAroundHintReg()
1277 SA->analyze(&VirtReg); in trySplitAroundHintReg()
1286 //===----------------------------------------------------------------------===//
1287 // Per-Block Splitting
1288 //===----------------------------------------------------------------------===//
1290 /// tryBlockSplit - Split a global live range around every block with uses. This
1296 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed"); in tryBlockSplit()
1298 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg)); in tryBlockSplit()
1300 SE->reset(LREdit, SplitSpillMode); in tryBlockSplit()
1301 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks(); in tryBlockSplit()
1303 if (SA->shouldSplitSingleBlock(BI, SingleInstrs)) in tryBlockSplit()
1304 SE->splitSingleBlock(BI); in tryBlockSplit()
1312 SE->finish(&IntvMap); in tryBlockSplit()
1315 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS); in tryBlockSplit()
1320 const LiveInterval &LI = LIS->getInterval(LREdit.get(I)); in tryBlockSplit()
1321 if (ExtraInfo->getOrInitStage(LI.reg()) == RS_New && IntvMap[I] == 0) in tryBlockSplit()
1322 ExtraInfo->setStage(LI, RS_Spill); in tryBlockSplit()
1326 MF->verify(this, "After splitting live range around basic blocks"); in tryBlockSplit()
1330 //===----------------------------------------------------------------------===//
1331 // Per-Instruction Splitting
1332 //===----------------------------------------------------------------------===//
1343 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI, in getNumAllocatableRegsForConstraints()
1359 const MachineOperand &MO = MI->getOperand(OpIdx); in getInstReadLaneMask()
1385 // Early check the common case. Beware of the semi-formed bundles SplitKit in readsLaneSubset()
1388 auto DestSrc = TII->isCopyInstr(*MI); in readsLaneSubset()
1389 if (DestSrc && !MI->isBundled() && in readsLaneSubset()
1390 DestSrc->Destination->getSubReg() == DestSrc->Source->getSubReg()) in readsLaneSubset()
1404 return (ReadMask & ~(LiveAtMask & TRI->getCoveringLanes())).any(); in readsLaneSubset()
1407 /// tryInstructionSplit - Split a live range around individual instructions.
1417 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg()); in tryInstructionSplit()
1418 // There is no point to this if there are no larger sub-classes. in tryInstructionSplit()
1430 SE->reset(LREdit, SplitEditor::SM_Size); in tryInstructionSplit()
1432 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); in tryInstructionSplit()
1440 TRI->getLargestLegalSuperClass(CurRC, *MF); in tryInstructionSplit()
1443 // Split around every non-copy instruction if this split will relax in tryInstructionSplit()
1448 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Use)) { in tryInstructionSplit()
1449 if (TII->isFullCopyInstr(*MI) || in tryInstructionSplit()
1461 SE->openIntv(); in tryInstructionSplit()
1462 SlotIndex SegStart = SE->enterIntvBefore(Use); in tryInstructionSplit()
1463 SlotIndex SegStop = SE->leaveIntvAfter(Use); in tryInstructionSplit()
1464 SE->useIntv(SegStart, SegStop); in tryInstructionSplit()
1473 SE->finish(&IntvMap); in tryInstructionSplit()
1474 DebugVars->splitRegister(VirtReg.reg(), LREdit.regs(), *LIS); in tryInstructionSplit()
1476 ExtraInfo->setStage(LREdit.begin(), LREdit.end(), RS_Spill); in tryInstructionSplit()
1480 //===----------------------------------------------------------------------===//
1482 //===----------------------------------------------------------------------===//
1484 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
1485 /// in order to use PhysReg between two entries in SA->UseSlots.
1491 assert(SA->getUseBlocks().size() == 1 && "Not a local interval"); in calcGapWeights()
1492 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); in calcGapWeights()
1493 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); in calcGapWeights()
1494 const unsigned NumGaps = Uses.size()-1; in calcGapWeights()
1505 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { in calcGapWeights()
1506 if (!Matrix->query(const_cast<LiveInterval &>(SA->getParent()), Unit) in calcGapWeights()
1518 Matrix->getLiveUnions()[Unit].find(StartIdx); in calcGapWeights()
1528 const float weight = IntI.value()->weight(); in calcGapWeights()
1540 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { in calcGapWeights()
1541 const LiveRange &LR = LIS->getRegUnit(Unit); in calcGapWeights()
1546 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) { in calcGapWeights()
1547 while (Uses[Gap+1].getBoundaryIndex() < I->start) in calcGapWeights()
1555 if (Uses[Gap+1].getBaseIndex() >= I->end) in calcGapWeights()
1564 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1572 if (SA->getUseBlocks().size() != 1) in tryLocalSplit()
1575 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front(); in tryLocalSplit()
1577 // Note that it is possible to have an interval that is live-in or live-out in tryLocalSplit()
1578 // while only covering a single block - A phi-def can use undef values from in tryLocalSplit()
1579 // predecessors, and the block could be a single-block loop. in tryLocalSplit()
1584 ArrayRef<SlotIndex> Uses = SA->getUseSlots(); in tryLocalSplit()
1585 if (Uses.size() <= 2) in tryLocalSplit()
1587 const unsigned NumGaps = Uses.size()-1; in tryLocalSplit()
1599 if (Matrix->checkRegMaskInterference(VirtReg)) { in tryLocalSplit()
1601 ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber()); in tryLocalSplit()
1605 llvm::lower_bound(RMS, Uses.front().getRegSlot()) - RMS.begin(); in tryLocalSplit()
1616 LLVM_DEBUG(dbgs() << ' ' << RMS[RI] << ':' << Uses[I] << '-' in tryLocalSplit()
1631 // split 2+3 (including the COPY), and we want to allow that. in tryLocalSplit()
1637 // 2. Require progress be made for ranges with getStage() == RS_Split2. All in tryLocalSplit()
1642 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent in tryLocalSplit()
1645 bool ProgressRequired = ExtraInfo->getStage(VirtReg) >= RS_Split2; in tryLocalSplit()
1653 SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() * in tryLocalSplit()
1654 (1.0f / MBFI->getEntryFreq().getFrequency()); in tryLocalSplit()
1664 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg)) in tryLocalSplit()
1674 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]). in tryLocalSplit()
1684 << '-' << Uses[SplitAfter] << " I=" << MaxGap); in tryLocalSplit()
1695 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter; in tryLocalSplit()
1702 // register. Conservatively assume there are no read-modify-write in tryLocalSplit()
1716 float Diff = EstWeight - MaxGap; in tryLocalSplit()
1731 if (GapWeight[SplitBefore - 1] >= MaxGap) { in tryLocalSplit()
1756 LLVM_DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] << '-' in tryLocalSplit()
1758 << (BestAfter - BestBefore + 1) << " instrs\n"); in tryLocalSplit()
1761 SE->reset(LREdit); in tryLocalSplit()
1763 SE->openIntv(); in tryLocalSplit()
1764 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]); in tryLocalSplit()
1765 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]); in tryLocalSplit()
1766 SE->useIntv(SegStart, SegStop); in tryLocalSplit()
1768 SE->finish(&IntvMap); in tryLocalSplit()
1769 DebugVars->splitRegister(VirtReg.reg(), LREdit.regs(), *LIS); in tryLocalSplit()
1775 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter; in tryLocalSplit()
1777 LLVM_DEBUG(dbgs() << "Tagging non-progress ranges:"); in tryLocalSplit()
1781 ExtraInfo->setStage(LIS->getInterval(LREdit.get(I)), RS_Split2); in tryLocalSplit()
1791 //===----------------------------------------------------------------------===//
1793 //===----------------------------------------------------------------------===//
1795 /// trySplit - Try to split VirtReg or one of its interferences, making it
1802 if (ExtraInfo->getStage(VirtReg) >= RS_Spill) in trySplit()
1806 if (LIS->intervalIsInOneMBB(VirtReg)) { in trySplit()
1809 SA->analyze(&VirtReg); in trySplit()
1819 SA->analyze(&VirtReg); in trySplit()
1824 if (ExtraInfo->getStage(VirtReg) < RS_Split2) { in trySplit()
1834 //===----------------------------------------------------------------------===//
1836 //===----------------------------------------------------------------------===//
1840 for (const MachineOperand &MO : MRI->def_operands(reg)) in hasTiedDef()
1859 /// mayRecolorAllInterferences - Check if the virtual registers that
1870 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg()); in mayRecolorAllInterferences()
1872 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { in mayRecolorAllInterferences()
1873 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, Unit); in mayRecolorAllInterferences()
1895 if (((ExtraInfo->getStage(*Intf) == RS_Done && in mayRecolorAllInterferences()
1896 MRI->getRegClass(Intf->reg()) == CurRC && in mayRecolorAllInterferences()
1899 !hasTiedDef(MRI, Intf->reg()))) || in mayRecolorAllInterferences()
1900 FixedRegisters.count(Intf->reg())) { in mayRecolorAllInterferences()
1911 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
1917 /// be last-chance-recolored again during this recoloring "session".
1960 if (!TRI->shouldUseLastChanceRecoloringForVirtReg(*MF, VirtReg)) in tryLastChanceRecoloring()
1968 assert((ExtraInfo->getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) && in tryLastChanceRecoloring()
1997 if (Matrix->checkInterference(VirtReg, PhysReg) > in tryLastChanceRecoloring()
2018 Register ItVirtReg = RC->reg(); in tryLastChanceRecoloring()
2020 assert(VRM->hasPhys(ItVirtReg) && in tryLastChanceRecoloring()
2024 RecolorStack.push_back(std::make_pair(RC, VRM->getPhys(ItVirtReg))); in tryLastChanceRecoloring()
2027 Matrix->unassign(*RC); in tryLastChanceRecoloring()
2033 Matrix->assign(VirtReg, PhysReg); in tryLastChanceRecoloring()
2046 Matrix->unassign(VirtReg); in tryLastChanceRecoloring()
2055 Matrix->unassign(VirtReg); in tryLastChanceRecoloring()
2062 if (RecoloringCandidates.count(&LIS->getInterval(R))) in tryLastChanceRecoloring()
2071 // reassigning, since sub-recolorings may have conflicted with the registers in tryLastChanceRecoloring()
2073 for (ssize_t I = RecolorStack.size() - 1; I >= EntryStackSize; --I) { in tryLastChanceRecoloring()
2078 if (VRM->hasPhys(LI->reg())) in tryLastChanceRecoloring()
2079 Matrix->unassign(*LI); in tryLastChanceRecoloring()
2086 if (!LI->empty() && !MRI->reg_nodbg_empty(LI->reg())) in tryLastChanceRecoloring()
2087 Matrix->assign(*LI, PhysReg); in tryLastChanceRecoloring()
2098 /// tryRecoloringCandidates - Try to assign a new color to every register
2116 // When splitting happens, the live-range may actually be empty. in tryRecoloringCandidates()
2120 if (PhysReg == ~0u || (!PhysReg && !LI->empty())) in tryRecoloringCandidates()
2124 assert(LI->empty() && "Only empty live-range do not require a register"); in tryRecoloringCandidates()
2132 Matrix->assign(*LI, PhysReg); in tryRecoloringCandidates()
2133 FixedRegisters.insert(LI->reg()); in tryRecoloringCandidates()
2138 //===----------------------------------------------------------------------===//
2140 //===----------------------------------------------------------------------===//
2145 LLVMContext &Ctx = MF->getFunction().getContext(); in selectOrSplit()
2154 "reached. Use -fexhaustive-register-search to skip " in selectOrSplit()
2158 "recoloring reached. Use -fexhaustive-register-search " in selectOrSplit()
2163 "-fexhaustive-register-search to skip cutoffs"); in selectOrSplit()
2168 /// Using a CSR for the first time has a cost because it causes push|pop
2170 /// range can have lower cost than using the CSR for the first time;
2172 /// the CSR for the first time. Returns the physical register if we decide
2173 /// to use the CSR; otherwise return 0.
2177 if (ExtraInfo->getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) { in tryAssignCSRFirstTime()
2178 // We choose spill over using the CSR for the first time if the spill cost in tryAssignCSRFirstTime()
2180 SA->analyze(&VirtReg); in tryAssignCSRFirstTime()
2185 // we will not use a callee-saved register in tryEvict. in tryAssignCSRFirstTime()
2189 if (ExtraInfo->getStage(VirtReg) < RS_Split) { in tryAssignCSRFirstTime()
2190 // We choose pre-splitting over using the CSR for the first time if in tryAssignCSRFirstTime()
2192 SA->analyze(&VirtReg); in tryAssignCSRFirstTime()
2198 // Use the CSR if we can't find a region split below CSRCost. in tryAssignCSRFirstTime()
2201 // Perform the actual pre-splitting. in tryAssignCSRFirstTime()
2214 // We use the larger one out of the command-line option and the value report in initializeCSRCost()
2217 std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost())); in initializeCSRCost()
2221 // Raw cost is relative to Entry == 2^14; scale it appropriately. in initializeCSRCost()
2222 uint64_t ActualEntry = MBFI->getEntryFreq().getFrequency(); in initializeCSRCost()
2234 // Can't use BranchProbability in general, since it takes 32-bit numbers. in initializeCSRCost()
2243 for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) { in collectHintInfo()
2244 if (!TII->isFullCopyInstr(Instr)) in collectHintInfo()
2255 OtherReg.isPhysical() ? OtherReg.asMCReg() : VRM->getPhys(OtherReg); in collectHintInfo()
2257 Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg, in collectHintInfo()
2276 /// all the live ranges that are copy-related with \p VirtReg.
2277 /// The recoloring is then propagated to all the live-ranges that have
2281 /// frequencies of the non-identity copies it would introduce with the old
2285 // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted in tryHintRecoloring()
2286 // some register and PhysReg may be available for the other live-ranges. in tryHintRecoloring()
2288 SmallVector<unsigned, 2> RecoloringCandidates; in tryHintRecoloring()
2291 MCRegister PhysReg = VRM->getPhys(Reg); in tryHintRecoloring()
2292 // Start the recoloring algorithm from the input live-interval, then in tryHintRecoloring()
2293 // it will propagate to the ones that are copy-related with it. in tryHintRecoloring()
2308 if (!VRM->hasPhys(Reg)) { in tryHintRecoloring()
2316 LiveInterval &LI = LIS->getInterval(Reg); in tryHintRecoloring()
2317 MCRegister CurrPhys = VRM->getPhys(Reg); in tryHintRecoloring()
2320 if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) || in tryHintRecoloring()
2321 Matrix->checkInterference(LI, PhysReg))) in tryHintRecoloring()
2330 // Check if recoloring the live-range will increase the cost of the in tryHintRecoloring()
2331 // non-identity copies. in tryHintRecoloring()
2347 // Recolor the live-range. in tryHintRecoloring()
2348 Matrix->unassign(LI); in tryHintRecoloring()
2349 Matrix->assign(LI, PhysReg); in tryHintRecoloring()
2351 // Push all copy-related live-ranges to keep reconciling the broken in tryHintRecoloring()
2362 /// freed up a register for a larger live-range.
2395 /// getting rid of 2 copies.
2398 assert(LI->reg().isVirtual() && in tryHintsRecoloring()
2402 if (!VRM->hasPhys(LI->reg())) in tryHintsRecoloring()
2423 EvictAdvisor->isUnusedCalleeSavedReg(PhysReg) && NewVRegs.empty()) { in selectOrSplitImpl()
2427 // Return now if we decide to use a CSR or create new vregs due to in selectOrSplitImpl()
2428 // pre-splitting. in selectOrSplitImpl()
2437 LiveRangeStage Stage = ExtraInfo->getStage(VirtReg); in selectOrSplitImpl()
2439 << ExtraInfo->getCascade(VirtReg.reg()) << '\n'); in selectOrSplitImpl()
2448 Register Hint = MRI->getSimpleHint(VirtReg.reg()); in selectOrSplitImpl()
2453 // copy-related live-ranges. in selectOrSplitImpl()
2465 ExtraInfo->setStage(VirtReg, RS_Split); in selectOrSplitImpl()
2475 if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) in selectOrSplitImpl()
2488 TRI->shouldUseDeferredSpillingForVirtReg(*MF, VirtReg)) && in selectOrSplitImpl()
2489 ExtraInfo->getStage(VirtReg) < RS_Memory) { in selectOrSplitImpl()
2494 ExtraInfo->setStage(VirtReg, RS_Memory); in selectOrSplitImpl()
2502 ExtraInfo->setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done); in selectOrSplitImpl()
2507 DebugVars->splitRegister(VirtReg.reg(), LRE.regs(), *LIS); in selectOrSplitImpl()
2510 MF->verify(this, "After spilling"); in selectOrSplitImpl()
2549 const MachineFrameInfo &MFI = MF->getFrameInfo(); in computeStats()
2554 A->getPseudoValue())->getFrameIndex()); in computeStats()
2562 auto DestSrc = TII->isCopyInstr(MI); in computeStats()
2564 const MachineOperand &Dest = *DestSrc->Destination; in computeStats()
2565 const MachineOperand &Src = *DestSrc->Source; in computeStats()
2571 SrcReg = VRM->getPhys(SrcReg); in computeStats()
2573 SrcReg = TRI->getSubReg(SrcReg, Src.getSubReg()); in computeStats()
2576 DestReg = VRM->getPhys(DestReg); in computeStats()
2578 DestReg = TRI->getSubReg(DestReg, Dest.getSubReg()); in computeStats()
2586 SmallVector<const MachineMemOperand *, 2> Accesses; in computeStats()
2587 if (TII->isLoadFromStackSlot(MI, FI) && MFI.isSpillSlotObjectIndex(FI)) { in computeStats()
2591 if (TII->isStoreToStackSlot(MI, FI) && MFI.isSpillSlotObjectIndex(FI)) { in computeStats()
2595 if (TII->hasLoadFromStackSlot(MI, Accesses) && in computeStats()
2603 TII->getPatchpointUnfoldableRange(MI); in computeStats()
2623 if (TII->hasStoreToStackSlot(MI, Accesses) && in computeStats()
2630 float RelFreq = MBFI->getBlockFreqRelativeToEntryBlock(&MBB); in computeStats()
2639 RAGreedy::RAGreedyStats RAGreedy::reportStats(MachineLoop *L) { in reportStats() argument
2643 for (MachineLoop *SubLoop : *L) in reportStats()
2646 for (MachineBasicBlock *MBB : L->getBlocks()) in reportStats()
2648 if (Loops->getLoopFor(MBB) == L) in reportStats()
2654 ORE->emit([&]() { in reportStats()
2656 L->getStartLoc(), L->getHeader()); in reportStats()
2666 if (!ORE->allowExtraAnalysis(DEBUG_TYPE)) in reportStats()
2669 for (MachineLoop *L : *Loops) in reportStats()
2670 Stats.add(reportStats(L)); in reportStats()
2671 // Process non-loop blocks. in reportStats()
2673 if (!Loops->getLoopFor(&MBB)) in reportStats()
2678 ORE->emit([&]() { in reportStats()
2680 if (auto *SP = MF->getFunction().getSubprogram()) in reportStats()
2681 Loc = DILocation::get(SP->getContext(), SP->getLine(), 1, SP); in reportStats()
2683 &MF->front()); in reportStats()
2692 for (unsigned I = 0, E = MRI->getNumVirtRegs(); I != E; ++I) { in hasVirtRegAlloc()
2694 if (MRI->reg_nodbg_empty(Reg)) in hasVirtRegAlloc()
2696 const TargetRegisterClass *RC = MRI->getRegClass(Reg); in hasVirtRegAlloc()
2711 TII = MF->getSubtarget().getInstrInfo(); in runOnMachineFunction()
2714 MF->verify(this, "Before greedy register allocator"); in runOnMachineFunction()
2728 Indexes->packIndexes(); in runOnMachineFunction()
2739 RegCosts = TRI->getRegisterCosts(*MF); in runOnMachineFunction()
2743 : TRI->regClassPriorityTrumpsGlobalness(*MF); in runOnMachineFunction()
2747 : TRI->reverseLocalAssignment(); in runOnMachineFunction()
2758 VRAI->calculateSpillWeightsAndHints(); in runOnMachineFunction()
2760 LLVM_DEBUG(LIS->dump()); in runOnMachineFunction()
2765 IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI); in runOnMachineFunction()
2773 MF->verify(this, "Before post optimization"); in runOnMachineFunction()