66#define DEBUG_TYPE "machine-sink"
70 cl::desc(
"Split critical edges during machine sinking"),
75 cl::desc(
"Use block frequency info to find successors to sink"),
79 "machine-sink-split-probability-threshold",
81 "Percentage threshold for splitting single-instruction critical edge. "
82 "If the branch threshold is higher than this threshold, we allow "
83 "speculative execution of up to 1 instruction to avoid branching to "
84 "splitted critical edge"),
88 "machine-sink-load-instrs-threshold",
89 cl::desc(
"Do not try to find alias store for a load if there is a in-path "
90 "block whose instruction number is higher than this threshold."),
94 "machine-sink-load-blocks-threshold",
95 cl::desc(
"Do not try to find alias store for a load if the block number in "
96 "the straight line is higher than this threshold."),
101 cl::desc(
"Sink instructions into cycles to avoid "
106 "machine-sink-cycle-limit",
108 "The maximum number of instructions considered for cycle sinking."),
111STATISTIC(NumSunk,
"Number of machine instructions sunk");
112STATISTIC(NumCycleSunk,
"Number of machine instructions sunk into a cycle");
115STATISTIC(NumPostRACopySink,
"Number of copies sunk after RA");
154 using AllSuccsCache =
168 using SinkItem = std::pair<MachineInstr *, MachineBasicBlock *>;
187 CachedRegisterPressure;
189 bool EnableSinkAndFold;
216 CEBCandidates.
clear();
217 CEMergeCandidates.
clear();
247 AllSuccsCache &AllSuccessors);
257 bool &LocalUse)
const;
260 AllSuccsCache &AllSuccessors);
272 AllSuccsCache &AllSuccessors);
281 AllSuccsCache &AllSuccessors)
const;
284 bool UseCache =
true);
286 bool registerPressureSetExceedsLimit(
unsigned NRegs,
295char MachineSinking::ID = 0;
320 if (!
TII->isBasicBlockPrologue(*PI))
322 for (
auto &MO :
MI.operands()) {
329 if (
Reg.isPhysical() &&
330 (
TII->isIgnorableUse(MO) || (
MRI &&
MRI->isConstantPhysReg(
Reg))))
332 if (PI->modifiesRegister(
Reg,
TRI))
335 if (PI->readsRegister(
Reg,
TRI))
338 auto *DefOp = PI->findRegisterDefOperand(
Reg,
TRI,
false,
true);
339 if (DefOp && !DefOp->isDead())
348bool MachineSinking::PerformTrivialForwardCoalescing(
MachineInstr &
MI,
356 !
MRI->hasOneNonDBGUse(SrcReg))
369 MRI->replaceRegWith(DstReg, SrcReg);
370 MI.eraseFromParent();
374 MRI->clearKillFlags(SrcReg);
382 if (
MI.isCopy() ||
MI.mayLoadOrStore() ||
383 MI.getOpcode() == TargetOpcode::REG_SEQUENCE)
391 bool SawStore =
true;
392 if (!
MI.isSafeToMove(SawStore))
397 if (
MI.isConvergent())
407 if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||
408 MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||
409 MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())
418 if (
Reg.isVirtual()) {
428 else if (UsedRegB == 0)
435 if (
Reg.isPhysical() && MO.isUse() &&
436 (
MRI->isConstantPhysReg(
Reg) ||
TII->isIgnorableUse(MO)))
446 using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;
452 UsedRegA == 0 ? nullptr :
MRI->getRegClass(UsedRegA);
454 UsedRegB == 0 ? nullptr :
MRI->getRegClass(UsedRegB);
457 while (!Worklist.
empty()) {
483 if (!
TII->canFoldIntoAddrMode(UseInst,
Reg,
MI, AM))
500 if (RCA ==
nullptr) {
505 unsigned NRegs = !!RCA + !!RCB;
511 if (RCB ==
nullptr) {
512 if (registerPressureSetExceedsLimit(NRegs, RCA,
MBB))
514 }
else if (registerPressureSetExceedsLimit(1, RCA,
MBB) ||
515 registerPressureSetExceedsLimit(1, RCB,
MBB)) {
525 if (SinkInto.
empty())
529 for (
auto &[SinkDst, MaybeAM] : SinkInto) {
533 if (SinkDst->isCopy()) {
546 Register DstReg = SinkDst->getOperand(0).getReg();
547 TII->reMaterialize(*SinkDst->getParent(), InsertPt, DstReg, 0,
MI, *
TRI);
548 New = &*std::prev(InsertPt);
549 if (!
New->getDebugLoc())
550 New->setDebugLoc(SinkDst->getDebugLoc());
556 MRI->clearKillFlags(UsedRegA);
558 MRI->clearKillFlags(UsedRegB);
561 New =
TII->emitLdStWithAddr(*SinkDst, MaybeAM);
567 MRI->clearKillFlags(R);
569 MRI->clearKillFlags(R);
573 if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
574 StoreInstrCache.clear();
575 SinkDst->eraseFromParent();
583 while (!Worklist.
empty()) {
587 assert((
U->isCopy() ||
U->isDebugInstr()) &&
588 "Only debug uses and copies must remain");
590 Worklist.
push_back(
U->getOperand(0).getReg());
599 I->eraseFromParent();
606 MI.eraseFromParent();
614bool MachineSinking::AllUsesDominatedByBlock(
Register Reg,
618 bool &LocalUse)
const {
619 assert(
Reg.isVirtual() &&
"Only makes sense for vregs");
622 if (
MRI->use_nodbg_empty(
Reg))
640 MachineInstr *UseInst = MO.getParent();
641 unsigned OpNo = MO.getOperandNo();
642 MachineBasicBlock *UseBlock = UseInst->getParent();
643 return UseBlock == MBB && UseInst->isPHI() &&
644 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
653 unsigned OpNo = &MO - &UseInst->
getOperand(0);
655 if (UseInst->
isPHI()) {
659 }
else if (UseBlock == DefMBB) {
675 assert(
MI.mayLoad() &&
"Expected MI that loads!");
679 if (
MI.memoperands_empty())
684 if (PSV->isGOT() || PSV->isConstantPool())
690void MachineSinking::FindCycleSinkCandidates(
693 for (
auto &
MI : *BB) {
695 if (
MI.isMetaInstruction()) {
696 LLVM_DEBUG(
dbgs() <<
"CycleSink: not sinking meta instruction\n");
700 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction not a candidate for this "
705 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction is not cycle invariant\n");
708 bool DontMoveAcrossStore =
true;
709 if (!
MI.isSafeToMove(DontMoveAcrossStore)) {
710 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction not safe to move.\n");
714 LLVM_DEBUG(
dbgs() <<
"CycleSink: Dont sink GOT or constant pool loads\n");
717 if (
MI.isConvergent())
726 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction added as candidate.\n");
738 TII = STI->getInstrInfo();
739 TRI = STI->getRegisterInfo();
741 DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
742 PDT = &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
743 CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
744 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
746 ? &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI()
748 MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
749 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
750 RegClassInfo.runOnMachineFunction(MF);
754 bool EverMadeChange =
false;
757 bool MadeChange =
false;
760 CEBCandidates.clear();
761 CEMergeCandidates.clear();
768 MachineDomTreeUpdater::UpdateStrategy::Lazy);
769 for (
const auto &Pair : ToSplit) {
771 Pair.first->SplitCriticalEdge(Pair.second, *
this,
nullptr, &MDTU);
772 if (NewSucc !=
nullptr) {
778 MBFI->onEdgeSplit(*Pair.first, *NewSucc, *MBPI);
782 CI->splitCriticalEdge(Pair.first, Pair.second, NewSucc);
789 EverMadeChange =
true;
794 SchedModel.init(STI);
795 bool HasHighPressure;
799 enum CycleSinkStage { COPY, LOW_LATENCY, AGGRESSIVE, END };
800 for (
unsigned Stage = CycleSinkStage::COPY; Stage != CycleSinkStage::END;
801 ++Stage, SunkInstrs.
clear()) {
802 HasHighPressure =
false;
804 for (
auto *
Cycle : Cycles) {
811 FindCycleSinkCandidates(
Cycle, Preheader, Candidates);
820 if (Stage == CycleSinkStage::COPY) {
823 <<
"CycleSink: Limit reached of instructions to "
834 if (Stage == CycleSinkStage::LOW_LATENCY &&
835 !
TII->hasLowDefLatency(SchedModel, *
I, 0))
838 if (!aggressivelySinkIntoCycle(
Cycle, *
I, SunkInstrs))
840 EverMadeChange =
true;
845 if (!HasHighPressure)
846 HasHighPressure = registerPressureExceedsLimit(*Preheader);
848 if (!HasHighPressure)
853 HasStoreCache.clear();
854 StoreInstrCache.clear();
857 for (
auto I : RegsToClearKillFlags)
858 MRI->clearKillFlags(
I);
859 RegsToClearKillFlags.clear();
861 return EverMadeChange;
874 bool MadeChange =
false;
877 AllSuccsCache AllSuccessors;
882 bool ProcessedBegin, SawStore =
false;
892 if (
MI.isDebugOrPseudoInstr() ||
MI.isFakeUse()) {
893 if (
MI.isDebugValue())
898 if (EnableSinkAndFold && PerformSinkAndFold(
MI, &
MBB)) {
907 if (PerformTrivialForwardCoalescing(
MI, &
MBB)) {
918 }
while (!ProcessedBegin);
920 SeenDbgUsers.clear();
923 CachedRegisterPressure.clear();
930 assert(
MI.isDebugValue() &&
"Expected DBG_VALUE for processing");
933 MI.getDebugLoc()->getInlinedAt());
934 bool SeenBefore = SeenDbgVars.contains(Var);
938 SeenDbgUsers[MO.
getReg()].push_back(SeenDbgUser(&
MI, SeenBefore));
942 SeenDbgVars.insert(Var);
945bool MachineSinking::isWorthBreakingCriticalEdge(
953 if (!CEBCandidates.insert(std::make_pair(
From, To)).second)
964 for (
const auto &MO :
MI.all_defs()) {
969 auto Key = std::make_pair(SrcReg, To);
970 auto Res = CEMergeCandidates.try_emplace(Key,
From);
975 DeferredFromBlock = Res.first->second;
980 if (
From->isSuccessor(To) &&
981 MBPI->getEdgeProbability(
From, To) <=
995 if (
Reg.isPhysical())
1001 if (
MRI->hasOneNonDBGUse(
Reg)) {
1014 return TII->shouldBreakCriticalEdgeToSink(
MI);
1020 bool BreakPHIEdge) {
1029 if (FromCycle == ToCycle && FromCycle &&
1072 if (!BreakPHIEdge) {
1074 if (Pred != FromBB && !DT->
dominates(ToBB, Pred))
1084 bool BreakPHIEdge) {
1087 if (isWorthBreakingCriticalEdge(
MI, FromBB, ToBB, DeferredFromBB)) {
1090 if ((!DeferredFromBB ||
1091 ToSplit.count(std::make_pair(DeferredFromBB, ToBB)) ||
1092 isLegalToBreakCriticalEdge(
MI, DeferredFromBB, ToBB, BreakPHIEdge)) &&
1093 isLegalToBreakCriticalEdge(
MI, FromBB, ToBB, BreakPHIEdge)) {
1094 ToSplit.
insert(std::make_pair(FromBB, ToBB));
1096 ToSplit.insert(std::make_pair(DeferredFromBB, ToBB));
1104std::vector<unsigned> &
1112 auto RP = CachedRegisterPressure.find(&
MBB);
1113 if (UseCache && RP != CachedRegisterPressure.end())
1125 MII != MIE; --MII) {
1127 if (
MI.isDebugInstr() ||
MI.isPseudoProbe())
1131 RPTracker.recedeSkipDebugValues();
1132 assert(&*RPTracker.getPos() == &
MI &&
"RPTracker sync error!");
1133 RPTracker.recede(RegOpers);
1136 RPTracker.closeRegion();
1138 if (RP != CachedRegisterPressure.end()) {
1139 CachedRegisterPressure[&
MBB] = RPTracker.getPressure().MaxSetPressure;
1140 return CachedRegisterPressure[&
MBB];
1143 auto It = CachedRegisterPressure.insert(
1144 std::make_pair(&
MBB, RPTracker.getPressure().MaxSetPressure));
1145 return It.first->second;
1148bool MachineSinking::registerPressureSetExceedsLimit(
1151 unsigned Weight = NRegs *
TRI->getRegClassWeight(RC).RegWeight;
1152 const int *PS =
TRI->getRegClassPressureSets(RC);
1153 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(
MBB);
1154 for (; *PS != -1; PS++)
1155 if (Weight + BBRegisterPressure[*PS] >=
1156 RegClassInfo.getRegPressureSetLimit(*PS))
1162bool MachineSinking::registerPressureExceedsLimit(
1164 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(
MBB,
false);
1166 for (
unsigned PS = 0; PS < BBRegisterPressure.size(); ++PS) {
1167 if (BBRegisterPressure[PS] >=
1180 AllSuccsCache &AllSuccessors) {
1181 assert(SuccToSinkTo &&
"Invalid SinkTo Candidate BB");
1183 if (
MBB == SuccToSinkTo)
1187 if (!PDT->dominates(SuccToSinkTo,
MBB))
1192 if (CI->getCycleDepth(
MBB) > CI->getCycleDepth(SuccToSinkTo))
1196 bool NonPHIUse =
false;
1199 if (UseBlock == SuccToSinkTo && !UseInst.
isPHI())
1207 bool BreakPHIEdge =
false;
1210 FindSuccToSinkTo(
MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1211 return isProfitableToSinkTo(
Reg,
MI, SuccToSinkTo, MBB2, AllSuccessors);
1230 if (
Reg.isPhysical()) {
1233 !
TII->isIgnorableUse(MO))
1241 bool LocalUse =
false;
1242 if (!AllUsesDominatedByBlock(
Reg, SuccToSinkTo,
MBB, BreakPHIEdge,
1260 if (registerPressureSetExceedsLimit(1,
MRI->getRegClass(
Reg),
1262 LLVM_DEBUG(
dbgs() <<
"register pressure exceed limit, not profitable.");
1278 AllSuccsCache &AllSuccessors)
const {
1280 auto Succs = AllSuccessors.find(
MBB);
1281 if (Succs != AllSuccessors.end())
1282 return Succs->second;
1295 if (DTChild->getIDom()->getBlock() ==
MI.getParent() &&
1298 AllSuccs.push_back(DTChild->getBlock());
1304 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
1305 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
1307 (!LHSFreq && !RHSFreq))
1308 return CI->getCycleDepth(L) < CI->getCycleDepth(R);
1309 return LHSFreq < RHSFreq;
1312 auto it = AllSuccessors.insert(std::make_pair(
MBB, AllSuccs));
1314 return it.first->second;
1321 AllSuccsCache &AllSuccessors) {
1322 assert(
MBB &&
"Invalid MachineBasicBlock!");
1338 if (
Reg.isPhysical()) {
1343 if (!
MRI->isConstantPhysReg(
Reg) && !
TII->isIgnorableUse(MO))
1345 }
else if (!MO.
isDead()) {
1355 if (!
TII->isSafeToMoveRegClassDefs(
MRI->getRegClass(
Reg)))
1363 bool LocalUse =
false;
1364 if (!AllUsesDominatedByBlock(
Reg, SuccToSinkTo,
MBB, BreakPHIEdge,
1376 GetAllSortedSuccessors(
MI,
MBB, AllSuccessors)) {
1377 bool LocalUse =
false;
1378 if (AllUsesDominatedByBlock(
Reg, SuccBlock,
MBB, BreakPHIEdge,
1380 SuccToSinkTo = SuccBlock;
1391 if (!isProfitableToSinkTo(
Reg,
MI,
MBB, SuccToSinkTo, AllSuccessors))
1398 if (
MBB == SuccToSinkTo)
1403 if (SuccToSinkTo && SuccToSinkTo->
isEHPad())
1413 if (SuccToSinkTo && !
TII->isSafeToSink(
MI, SuccToSinkTo, CI))
1416 return SuccToSinkTo;
1431 auto *
MBB =
MI.getParent();
1436 auto *PredBB = PredMBB->getBasicBlock();
1442 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
1447 bool OffsetIsScalable;
1448 if (!
TII->getMemOperandWithOffset(
MI, BaseOp,
Offset, OffsetIsScalable,
TRI))
1451 if (!BaseOp->
isReg())
1454 if (!(
MI.mayLoad() && !
MI.isPredicable()))
1457 MachineBranchPredicate MBP;
1458 if (
TII->analyzeBranchPredicate(*PredMBB, MBP,
false))
1461 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1462 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1463 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1464 MBP.LHS.getReg() == BaseOp->
getReg();
1481 auto CopyOperands =
TII.isCopyInstr(SinkInst);
1484 SrcMO = CopyOperands->Source;
1485 DstMO = CopyOperands->Destination;
1488 bool PostRA =
MRI.getNumVirtRegs() == 0;
1496 bool arePhysRegs = !
Reg.isVirtual();
1497 if (arePhysRegs != PostRA)
1504 if (DbgMO.getSubReg() != SrcMO->
getSubReg() ||
1505 DbgMO.getSubReg() != DstMO->getSubReg())
1511 if (PostRA &&
Reg != DstMO->getReg())
1515 DbgMO.setReg(SrcMO->
getReg());
1521using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
1529 if (!SuccToSinkTo.
empty() && InsertPos != SuccToSinkTo.
end())
1531 InsertPos->getDebugLoc()));
1537 SuccToSinkTo.
splice(InsertPos, ParentBlock,
MI,
1544 for (
const auto &DbgValueToSink : DbgValuesToSink) {
1547 SuccToSinkTo.
insert(InsertPos, NewDbgMI);
1549 bool PropagatedAllSunkOps =
true;
1550 for (
unsigned Reg : DbgValueToSink.second) {
1553 PropagatedAllSunkOps =
false;
1558 if (!PropagatedAllSunkOps)
1572 auto BlockPair = std::make_pair(
From, To);
1576 if (
auto It = HasStoreCache.find(BlockPair); It != HasStoreCache.end())
1579 if (
auto It = StoreInstrCache.find(BlockPair); It != StoreInstrCache.end())
1581 return I->mayAlias(AA, MI, false);
1584 bool SawStore =
false;
1585 bool HasAliasedStore =
false;
1594 if (BB == To || BB ==
From)
1598 if (HandledBlocks.
count(BB))
1601 HandledBlocks.
insert(BB);
1603 if (PDT->dominates(To, BB)) {
1604 if (!HandledDomBlocks.
count(BB))
1605 HandledDomBlocks.
insert(BB);
1611 for (
auto *DomBB : HandledDomBlocks) {
1612 if (DomBB != BB && DT->
dominates(DomBB, BB))
1613 HasStoreCache[std::make_pair(DomBB, To)] =
true;
1614 else if (DomBB != BB && DT->
dominates(BB, DomBB))
1615 HasStoreCache[std::make_pair(
From, DomBB)] =
true;
1617 HasStoreCache[BlockPair] =
true;
1624 if (
I.isCall() ||
I.hasOrderedMemoryRef()) {
1625 for (
auto *DomBB : HandledDomBlocks) {
1626 if (DomBB != BB && DT->
dominates(DomBB, BB))
1627 HasStoreCache[std::make_pair(DomBB, To)] =
true;
1628 else if (DomBB != BB && DT->
dominates(BB, DomBB))
1629 HasStoreCache[std::make_pair(
From, DomBB)] =
true;
1631 HasStoreCache[BlockPair] =
true;
1641 if (
I.mayAlias(AA,
MI,
false))
1642 HasAliasedStore =
true;
1643 StoreInstrCache[BlockPair].push_back(&
I);
1650 HasStoreCache[BlockPair] =
false;
1651 return HasAliasedStore;
1659bool MachineSinking::aggressivelySinkIntoCycle(
1663 if (
I.getNumDefs() > 1)
1666 LLVM_DEBUG(
dbgs() <<
"AggressiveCycleSink: Finding sink block for: " <<
I);
1675 for (std::pair<RegSubRegPair, MachineInstr *> Entry :
Uses) {
1680 dbgs() <<
"AggressiveCycleSink: Not attempting to sink for PHI.\n");
1684 if (
MI->isPosition() ||
TII->isBasicBlockPrologue(*
MI)) {
1685 LLVM_DEBUG(
dbgs() <<
"AggressiveCycleSink: Use is BasicBlock prologue, "
1691 dbgs() <<
"AggressiveCycleSink: Use not in cycle, can't sink.\n");
1697 SinkItem MapEntry(&
I, SinkBlock);
1699 auto SI = SunkInstrs.
find(MapEntry);
1703 if (SI != SunkInstrs.
end()) {
1704 LLVM_DEBUG(
dbgs() <<
"AggressiveCycleSink: Already sunk to block: "
1711 LLVM_DEBUG(
dbgs() <<
"AggressiveCycleSink: Sinking instruction to block: "
1714 NewMI =
I.getMF()->CloneMachineInstr(&
I);
1717 Register DestReg =
MRI->createVirtualRegister(TRC);
1723 SunkInstrs.
insert({MapEntry, NewMI});
1729 RegsToClearKillFlags.insert(MO.
getReg());
1744 I.eraseFromParent();
1750bool MachineSinking::SinkInstruction(
MachineInstr &
MI,
bool &SawStore,
1751 AllSuccsCache &AllSuccessors) {
1757 if (!
MI.isSafeToMove(SawStore))
1762 if (
MI.isConvergent())
1778 bool BreakPHIEdge =
false;
1781 FindSuccToSinkTo(
MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1792 if (
Reg == 0 || !
Reg.isPhysical())
1798 LLVM_DEBUG(
dbgs() <<
"Sink instr " <<
MI <<
"\tinto block " << *SuccToSinkTo);
1805 bool TryBreak =
false;
1807 MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo,
MI) :
true;
1808 if (!
MI.isSafeToMove(Store)) {
1809 LLVM_DEBUG(
dbgs() <<
" *** NOTE: Won't sink load along critical edge.\n");
1815 if (!TryBreak && !DT->
dominates(ParentBlock, SuccToSinkTo)) {
1821 if (!TryBreak && CI->getCycle(SuccToSinkTo) &&
1822 (!CI->getCycle(SuccToSinkTo)->isReducible() ||
1823 CI->getCycle(SuccToSinkTo)->getHeader() == SuccToSinkTo)) {
1835 bool Status = PostponeSplitCriticalEdge(
MI, ParentBlock, SuccToSinkTo,
1839 "break critical edge\n");
1850 PostponeSplitCriticalEdge(
MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1853 "break critical edge\n");
1862 LLVM_DEBUG(
dbgs() <<
" *** Not sinking: prologue interference\n");
1868 for (
auto &MO :
MI.all_defs()) {
1871 auto It = SeenDbgUsers.find(MO.
getReg());
1872 if (It == SeenDbgUsers.end())
1876 auto &
Users = It->second;
1879 if (
User.getInt()) {
1894 if (
MI.getMF()->getFunction().getSubprogram() &&
MI.isCopy())
1895 SalvageUnsunkDebugUsersOfCopy(
MI, SuccToSinkTo);
1905 RegsToClearKillFlags.insert(MO.
getReg());
1910void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1921 for (
auto &MO :
MI.all_defs()) {
1930 if (
User.getParent() ==
MI.getParent())
1934 "DBG_VALUE user of vreg, but has no operand for it?");
1941 for (
auto *
User : DbgDefUsers) {
1942 for (
auto &
Reg : DbgUseRegs) {
1943 for (
auto &
DbgOp :
User->getDebugOperandsForReg(
Reg)) {
1944 DbgOp.setReg(
MI.getOperand(1).getReg());
1945 DbgOp.setSubReg(
MI.getOperand(1).getSubReg());
2002 MachineFunctionProperties::Property::NoVRegs);
2022char PostRAMachineSinking::ID = 0;
2026 "PostRA Machine Sink",
false,
false)
2041 for (
auto *SI : SinkableBBs) {
2042 if (aliasWithRegsInLiveIn(*SI,
Reg,
TRI)) {
2056 if (!SinkableBBs.
count(SI) && aliasWithRegsInLiveIn(*SI,
Reg,
TRI))
2068 for (
auto DefReg : DefedRegsInCopy) {
2071 if (!BB || (SingleBB && SingleBB != BB))
2082 for (
auto U : UsedOpsInCopy) {
2088 if (UI.killsRegister(SrcReg,
TRI)) {
2089 UI.clearRegisterKills(SrcReg,
TRI);
2103 for (
unsigned DefReg : DefedRegsInCopy)
2106 for (
auto U : UsedOpsInCopy)
2116 bool HasRegDependency =
false;
2117 for (
unsigned i = 0, e =
MI->getNumOperands(); i != e; ++i) {
2126 HasRegDependency =
true;
2135 }
else if (MO.
isUse()) {
2137 HasRegDependency =
true;
2143 return HasRegDependency;
2155 if (!
SI->livein_empty() &&
SI->pred_size() == 1)
2158 if (SinkableBBs.
empty())
2161 bool Changed =
false;
2165 ModifiedRegUnits.clear();
2166 UsedRegUnits.clear();
2167 SeenDbgInstrs.clear();
2177 if (
MI.isDebugValue() && !
MI.isDebugRef()) {
2179 bool IsValid =
true;
2185 ModifiedRegUnits, UsedRegUnits)) {
2192 MIUnits[Unit].push_back(MO.
getReg());
2196 for (
auto &RegOps : MIUnits)
2197 SeenDbgInstrs[RegOps.first].emplace_back(&
MI,
2198 std::move(RegOps.second));
2203 if (
MI.isDebugOrPseudoInstr())
2210 if (!
MI.isCopy() || !
MI.getOperand(0).isRenamable()) {
2218 ModifiedRegUnits, UsedRegUnits)) {
2224 "Unexpect SrcReg or DefReg");
2235 "Unexpected predecessor");
2241 for (
auto &MO :
MI.all_defs()) {
2243 for (
const auto &
MIRegs : SeenDbgInstrs.lookup(Unit)) {
2244 auto &Regs = DbgValsToSinkMap[
MIRegs.first];
2246 Regs.push_back(
Reg);
2250 auto DbgValsToSink = DbgValsToSinkMap.
takeVector();
2259 LLVM_DEBUG(
dbgs() <<
" *** Not sinking: prologue interference\n");
2270 ++NumPostRACopySink;
2279 bool Changed =
false;
2283 ModifiedRegUnits.init(*
TRI);
2284 UsedRegUnits.init(*
TRI);
2286 Changed |= tryToSinkCopy(BB, MF,
TRI,
TII);
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder MachineInstrBuilder & DefMI
BlockVerifier::State From
COFF::MachineTypes Machine
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static const HTTPClientCleanup Cleanup
static Register UseReg(const MachineOperand &MO)
const HexagonInstrInfo * TII
iv Induction Variable Users
static cl::opt< unsigned > SinkLoadInstsPerBlockThreshold("machine-sink-load-instrs-threshold", cl::desc("Do not try to find alias store for a load if there is a in-path " "block whose instruction number is higher than this threshold."), cl::init(2000), cl::Hidden)
static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
static cl::opt< unsigned > SinkIntoCycleLimit("machine-sink-cycle-limit", cl::desc("The maximum number of instructions considered for cycle sinking."), cl::init(50), cl::Hidden)
unsigned const TargetRegisterInfo * TRI
static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, MachineBasicBlock::iterator InsertPos, ArrayRef< MIRegs > DbgValuesToSink)
Sink an instruction and its associated debug instructions.
static cl::opt< bool > SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden)
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI)
Return true if this machine instruction loads from global offset table or constant pool.
static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
Return true if MI is likely to be usable as a memory operation by the implicit null check optimizatio...
static cl::opt< bool > SinkInstsIntoCycle("sink-insts-to-avoid-spills", cl::desc("Sink instructions into cycles to avoid " "register spills"), cl::init(false), cl::Hidden)
static cl::opt< unsigned > SinkLoadBlocksThreshold("machine-sink-load-blocks-threshold", cl::desc("Do not try to find alias store for a load if the block number in " "the straight line is higher than this threshold."), cl::init(20), cl::Hidden)
static bool hasRegisterDependency(MachineInstr *MI, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits)
static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy)
Machine code static false bool blockPrologueInterferes(const MachineBasicBlock *BB, MachineBasicBlock::const_iterator End, const MachineInstr &MI, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, const MachineRegisterInfo *MRI)
Return true if a target defined block prologue instruction interferes with a sink candidate.
static cl::opt< unsigned > SplitEdgeProbabilityThreshold("machine-sink-split-probability-threshold", cl::desc("Percentage threshold for splitting single-instruction critical edge. " "If the branch threshold is higher than this threshold, we allow " "speculative execution of up to 1 instruction to avoid branching to " "splitted critical edge"), cl::init(40), cl::Hidden)
static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI, Register Reg)
If the sunk instruction is a copy, try to forward the copy instead of leaving an 'undef' DBG_VALUE in...
static MachineBasicBlock * getSingleLiveInSuccBB(MachineBasicBlock &CurBB, const SmallPtrSetImpl< MachineBasicBlock * > &SinkableBBs, unsigned Reg, const TargetRegisterInfo *TRI)
static cl::opt< bool > UseBlockFreqInfo("machine-sink-bfi", cl::desc("Use block frequency info to find successors to sink"), cl::init(true), cl::Hidden)
std::pair< MachineInstr *, SmallVector< unsigned, 2 > > MIRegs
This file implements a map that provides insertion order iteration.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This file defines the PointerIntPair class.
Remove Loads Into Fake Uses
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
static bool SinkInstruction(Instruction *Inst, SmallPtrSetImpl< Instruction * > &Stores, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
SinkInstruction - Determine whether it is safe to sink the specified machine instruction out of its c...
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Target-Independent Code Generator Pass Configuration Options pass.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
Identifies a unique instance of a variable.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Base class for the actual dominator tree node.
iterator_range< iterator > children()
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
A possibly irreducible generalization of a Loop.
BlockT * getHeader() const
bool isReducible() const
Whether the cycle is a natural loop.
BlockT * getCyclePreheader() const
Return the preheader block for this cycle.
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
bool isAsCheapAsAMove(const MachineInstr &MI) const override
bool shouldSink(const MachineInstr &MI) const override
A set of register units used to track register liveness.
static void accumulateUsedDefed(const MachineInstr &MI, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
For a machine instruction MI, adds all register units used in UsedRegUnits and defined or clobbered i...
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
instr_iterator instr_begin()
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
void removeLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
unsigned succ_size() const
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
pred_iterator pred_begin()
instr_iterator instr_end()
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Legacy analysis pass which computes a MachineCycleInfo.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Representation of each machine instruction.
static iterator_range< filter_iterator< Operand *, std::function< bool(Operand &Op)> > > getDebugOperandsForReg(Instruction *MI, Register Reg)
Returns a range of all of the operands that correspond to a debug use of Reg.
bool hasDebugOperandForReg(Register Reg) const
Returns whether this debug value has at least one debug operand with the register Reg.
void setDebugValueUndef()
Sets all register debug operands in this debug value instruction to be undef.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
const MachineBasicBlock * getParent() const
bool isCopyLike() const
Return true if the instruction behaves like a copy.
iterator_range< filtered_mop_iterator > all_uses()
Returns an iterator range over all operands that are (explicit or implicit) register uses.
bool isDebugInstr() const
void substituteRegister(Register FromReg, Register ToReg, unsigned SubIdx, const TargetRegisterInfo &RegInfo)
Replace all occurrences of FromReg with ToReg:SubIdx, properly composing subreg indices where necessa...
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
const MachineOperand & getOperand(unsigned i) const
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Register getReg() const
getReg - Returns the register number.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
This class implements a map that also provides access to all stored values in a deterministic order.
VectorType takeVector()
Clear the MapVector and return the underlying vector.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
virtual void releaseMemory()
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
PointerIntPair - This class implements a pair of a pointer and small integer.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
List of registers defined and used by a machine instruction.
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
Wrapper class representing virtual and physical registers.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
A vector that has set insertion semantics.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
Target-Independent Code Generator Pass Configuration Options.
bool getEnableSinkAndFold() const
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
bool hasSuperClassEq(const TargetRegisterClass *RC) const
Returns true if RC is a super-class of or equal to this class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool isCycleInvariant(const MachineCycle *Cycle, MachineInstr &I)
char & MachineSinkingID
MachineSinking - This pass performs sinking on machine instructions.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
char & PostRAMachineSinkingID
This pass perform post-ra machine sink for COPY instructions.
void initializeMachineSinkingPass(PassRegistry &)
iterator_range< df_iterator< T > > depth_first(const T &G)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
TODO: Might pack better if we changed this to a Struct of Arrays, since MachineOperand is width 32,...
Used to describe addressing mode similar to ExtAddrMode in CodeGenPrepare.
RegisterPressure computed within a region of instructions delimited by TopPos and BottomPos.
Represents a predicate at the MachineFunction level.
A pair composed of a register and a sub-register index.