65#define DEBUG_TYPE "machine-sink"
69 cl::desc(
"Split critical edges during machine sinking"),
74 cl::desc(
"Use block frequency info to find successors to sink"),
78 "machine-sink-split-probability-threshold",
80 "Percentage threshold for splitting single-instruction critical edge. "
81 "If the branch threshold is higher than this threshold, we allow "
82 "speculative execution of up to 1 instruction to avoid branching to "
83 "splitted critical edge"),
87 "machine-sink-load-instrs-threshold",
88 cl::desc(
"Do not try to find alias store for a load if there is a in-path "
89 "block whose instruction number is higher than this threshold."),
93 "machine-sink-load-blocks-threshold",
94 cl::desc(
"Do not try to find alias store for a load if the block number in "
95 "the straight line is higher than this threshold."),
100 cl::desc(
"Sink instructions into cycles to avoid "
105 "machine-sink-cycle-limit",
106 cl::desc(
"The maximum number of instructions considered for cycle sinking."),
109STATISTIC(NumSunk,
"Number of machine instructions sunk");
110STATISTIC(NumCycleSunk,
"Number of machine instructions sunk into a cycle");
113STATISTIC(NumPostRACopySink,
"Number of copies sunk after RA");
140 using AllSuccsCache =
171 CachedRegisterPressure;
173 bool EnableSinkAndFold;
199 CEBCandidates.
clear();
229 AllSuccsCache &AllSuccessors);
239 bool &LocalUse)
const;
241 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
250 AllSuccsCache &AllSuccessors);
259 AllSuccsCache &AllSuccessors)
const;
263 bool registerPressureSetExceedsLimit(
unsigned NRegs,
270char MachineSinking::ID = 0;
275 "Machine code sinking",
false,
false)
294 if (!
TII->isBasicBlockPrologue(*PI))
296 for (
auto &MO :
MI.operands()) {
303 if (
Reg.isPhysical() &&
304 (
TII->isIgnorableUse(MO) || (
MRI &&
MRI->isConstantPhysReg(
Reg))))
306 if (PI->modifiesRegister(
Reg,
TRI))
309 if (PI->readsRegister(
Reg,
TRI))
312 auto *DefOp = PI->findRegisterDefOperand(
Reg,
false,
true,
TRI);
313 if (DefOp && !DefOp->isDead())
322bool MachineSinking::PerformTrivialForwardCoalescing(
MachineInstr &
MI,
330 !
MRI->hasOneNonDBGUse(SrcReg))
343 MRI->replaceRegWith(DstReg, SrcReg);
344 MI.eraseFromParent();
348 MRI->clearKillFlags(SrcReg);
356 if (
MI.isCopy() ||
MI.mayLoadOrStore() ||
357 MI.getOpcode() == TargetOpcode::REG_SEQUENCE)
365 bool SawStore =
true;
366 if (!
MI.isSafeToMove(AA, SawStore))
371 if (
MI.isConvergent())
381 if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||
382 MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||
383 MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())
392 if (
Reg.isVirtual()) {
402 else if (UsedRegB == 0)
409 if (
Reg.isPhysical() &&
410 (
MRI->isConstantPhysReg(
Reg) ||
TII->isIgnorableUse(MO)))
420 using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;
426 UsedRegA == 0 ? nullptr :
MRI->getRegClass(UsedRegA);
428 UsedRegB == 0 ? nullptr :
MRI->getRegClass(UsedRegB);
431 while (!Worklist.
empty()) {
457 if (!
TII->canFoldIntoAddrMode(UseInst,
Reg,
MI, AM))
474 if (RCA ==
nullptr) {
479 unsigned NRegs = !!RCA + !!RCB;
485 if (RCB ==
nullptr) {
486 if (registerPressureSetExceedsLimit(NRegs, RCA,
MBB))
488 }
else if (registerPressureSetExceedsLimit(1, RCA,
MBB) ||
489 registerPressureSetExceedsLimit(1, RCB,
MBB)) {
499 if (SinkInto.
empty())
504 MRI->clearKillFlags(UsedRegA);
506 MRI->clearKillFlags(UsedRegB);
508 for (
auto &[SinkDst, MaybeAM] : SinkInto) {
512 if (SinkDst->isCopy()) {
525 Register DstReg = SinkDst->getOperand(0).getReg();
526 TII->reMaterialize(*SinkDst->getParent(), InsertPt, DstReg, 0,
MI, *
TRI);
527 New = &*std::prev(InsertPt);
528 if (!
New->getDebugLoc())
529 New->setDebugLoc(SinkDst->getDebugLoc());
532 New =
TII->emitLdStWithAddr(*SinkDst, MaybeAM);
536 if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
537 StoreInstrCache.
clear();
538 SinkDst->eraseFromParent();
546 while (!Worklist.
empty()) {
550 assert((
U->isCopy() ||
U->isDebugInstr()) &&
551 "Only debug uses and copies must remain");
553 Worklist.
push_back(
U->getOperand(0).getReg());
562 I->eraseFromParent();
569 MI.eraseFromParent();
577bool MachineSinking::AllUsesDominatedByBlock(
Register Reg,
581 bool &LocalUse)
const {
582 assert(
Reg.isVirtual() &&
"Only makes sense for vregs");
585 if (
MRI->use_nodbg_empty(
Reg))
603 MachineInstr *UseInst = MO.getParent();
604 unsigned OpNo = MO.getOperandNo();
605 MachineBasicBlock *UseBlock = UseInst->getParent();
606 return UseBlock == MBB && UseInst->isPHI() &&
607 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
616 unsigned OpNo = &MO - &UseInst->
getOperand(0);
618 if (UseInst->
isPHI()) {
622 }
else if (UseBlock == DefMBB) {
638 assert(
MI.mayLoad() &&
"Expected MI that loads!");
642 if (
MI.memoperands_empty())
647 if (PSV->isGOT() || PSV->isConstantPool())
653void MachineSinking::FindCycleSinkCandidates(
656 for (
auto &
MI : *BB) {
659 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction not a candidate for this "
664 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction is not cycle invariant\n");
667 bool DontMoveAcrossStore =
true;
668 if (!
MI.isSafeToMove(AA, DontMoveAcrossStore)) {
669 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction not safe to move.\n");
673 LLVM_DEBUG(
dbgs() <<
"CycleSink: Dont sink GOT or constant pool loads\n");
676 if (
MI.isConvergent())
685 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction added as candidate.\n");
700 DT = &getAnalysis<MachineDominatorTree>();
701 PDT = &getAnalysis<MachinePostDominatorTree>();
702 CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
703 MBFI =
UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
704 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
705 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
710 bool EverMadeChange =
false;
713 bool MadeChange =
false;
716 CEBCandidates.
clear();
722 for (
const auto &Pair : ToSplit) {
723 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *
this);
724 if (NewSucc !=
nullptr) {
739 if (!MadeChange)
break;
740 EverMadeChange =
true;
746 for (
auto *
Cycle : Cycles) {
753 FindCycleSinkCandidates(
Cycle, Preheader, Candidates);
761 LLVM_DEBUG(
dbgs() <<
"CycleSink: Limit reached of instructions to "
766 if (!SinkIntoCycle(
Cycle, *
I))
768 EverMadeChange =
true;
774 HasStoreCache.
clear();
775 StoreInstrCache.
clear();
778 for (
auto I : RegsToClearKillFlags)
779 MRI->clearKillFlags(
I);
780 RegsToClearKillFlags.clear();
782 return EverMadeChange;
794 bool MadeChange =
false;
797 AllSuccsCache AllSuccessors;
802 bool ProcessedBegin, SawStore =
false;
812 if (
MI.isDebugOrPseudoInstr()) {
813 if (
MI.isDebugValue())
818 if (EnableSinkAndFold && PerformSinkAndFold(
MI, &
MBB)) {
827 if (PerformTrivialForwardCoalescing(
MI, &
MBB)) {
838 }
while (!ProcessedBegin);
840 SeenDbgUsers.
clear();
843 CachedRegisterPressure.
clear();
850 assert(
MI.isDebugValue() &&
"Expected DBG_VALUE for processing");
853 MI.getDebugLoc()->getInlinedAt());
854 bool SeenBefore = SeenDbgVars.
contains(Var);
858 SeenDbgUsers[MO.
getReg()].push_back(SeenDbgUser(&
MI, SeenBefore));
873 if (!CEBCandidates.
insert(std::make_pair(
From, To)).second)
893 if (
Reg.isPhysical())
899 if (
MRI->hasOneNonDBGUse(
Reg)) {
917 if (!isWorthBreakingCriticalEdge(
MI, FromBB, ToBB))
928 if (FromCycle == ToCycle && FromCycle &&
973 if (Pred != FromBB && !DT->
dominates(ToBB, Pred))
977 ToSplit.insert(std::make_pair(FromBB, ToBB));
982std::vector<unsigned> &
988 auto RP = CachedRegisterPressure.
find(&
MBB);
989 if (RP != CachedRegisterPressure.
end())
1001 MII != MIE; --MII) {
1003 if (
MI.isDebugInstr() ||
MI.isPseudoProbe())
1007 RPTracker.recedeSkipDebugValues();
1008 assert(&*RPTracker.getPos() == &
MI &&
"RPTracker sync error!");
1009 RPTracker.recede(RegOpers);
1012 RPTracker.closeRegion();
1013 auto It = CachedRegisterPressure.
insert(
1014 std::make_pair(&
MBB, RPTracker.getPressure().MaxSetPressure));
1015 return It.first->second;
1018bool MachineSinking::registerPressureSetExceedsLimit(
1021 unsigned Weight = NRegs *
TRI->getRegClassWeight(RC).RegWeight;
1022 const int *PS =
TRI->getRegClassPressureSets(RC);
1023 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(
MBB);
1024 for (; *PS != -1; PS++)
1025 if (Weight + BBRegisterPressure[*PS] >=
1035 AllSuccsCache &AllSuccessors) {
1036 assert (SuccToSinkTo &&
"Invalid SinkTo Candidate BB");
1038 if (
MBB == SuccToSinkTo)
1051 bool NonPHIUse =
false;
1054 if (UseBlock == SuccToSinkTo && !UseInst.
isPHI())
1062 bool BreakPHIEdge =
false;
1065 FindSuccToSinkTo(
MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1066 return isProfitableToSinkTo(
Reg,
MI, SuccToSinkTo, MBB2, AllSuccessors);
1085 if (
Reg.isPhysical()) {
1087 if (MO.
isUse() && !
MRI->isConstantPhysReg(
Reg) && !
TII->isIgnorableUse(MO))
1095 bool LocalUse =
false;
1096 if (!AllUsesDominatedByBlock(
Reg, SuccToSinkTo,
MBB, BreakPHIEdge,
1114 if (registerPressureSetExceedsLimit(1,
MRI->getRegClass(
Reg),
1116 LLVM_DEBUG(
dbgs() <<
"register pressure exceed limit, not profitable.");
1132 AllSuccsCache &AllSuccessors)
const {
1134 auto Succs = AllSuccessors.find(
MBB);
1135 if (Succs != AllSuccessors.end())
1136 return Succs->second;
1149 if (DTChild->getIDom()->getBlock() ==
MI.getParent() &&
1152 AllSuccs.push_back(DTChild->getBlock());
1160 bool HasBlockFreq = LHSFreq != 0 || RHSFreq != 0;
1161 return HasBlockFreq ? LHSFreq < RHSFreq
1165 auto it = AllSuccessors.insert(std::make_pair(
MBB, AllSuccs));
1167 return it.first->second;
1174 AllSuccsCache &AllSuccessors) {
1175 assert (
MBB &&
"Invalid MachineBasicBlock!");
1184 if (!MO.
isReg())
continue;
1187 if (
Reg == 0)
continue;
1189 if (
Reg.isPhysical()) {
1194 if (!
MRI->isConstantPhysReg(
Reg) && !
TII->isIgnorableUse(MO))
1196 }
else if (!MO.
isDead()) {
1202 if (MO.
isUse())
continue;
1205 if (!
TII->isSafeToMoveRegClassDefs(
MRI->getRegClass(
Reg)))
1213 bool LocalUse =
false;
1214 if (!AllUsesDominatedByBlock(
Reg, SuccToSinkTo,
MBB,
1215 BreakPHIEdge, LocalUse))
1226 GetAllSortedSuccessors(
MI,
MBB, AllSuccessors)) {
1227 bool LocalUse =
false;
1228 if (AllUsesDominatedByBlock(
Reg, SuccBlock,
MBB,
1229 BreakPHIEdge, LocalUse)) {
1230 SuccToSinkTo = SuccBlock;
1241 if (!isProfitableToSinkTo(
Reg,
MI,
MBB, SuccToSinkTo, AllSuccessors))
1248 if (
MBB == SuccToSinkTo)
1253 if (SuccToSinkTo && SuccToSinkTo->
isEHPad())
1263 if (SuccToSinkTo && !
TII->isSafeToSink(
MI, SuccToSinkTo, CI))
1266 return SuccToSinkTo;
1281 auto *
MBB =
MI.getParent();
1286 auto *PredBB = PredMBB->getBasicBlock();
1292 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
1297 bool OffsetIsScalable;
1298 if (!
TII->getMemOperandWithOffset(
MI, BaseOp,
Offset, OffsetIsScalable,
TRI))
1301 if (!BaseOp->
isReg())
1304 if (!(
MI.mayLoad() && !
MI.isPredicable()))
1307 MachineBranchPredicate MBP;
1308 if (
TII->analyzeBranchPredicate(*PredMBB, MBP,
false))
1311 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1312 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1313 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1314 MBP.LHS.getReg() == BaseOp->
getReg();
1331 auto CopyOperands =
TII.isCopyInstr(SinkInst);
1334 SrcMO = CopyOperands->Source;
1335 DstMO = CopyOperands->Destination;
1338 bool PostRA =
MRI.getNumVirtRegs() == 0;
1346 bool arePhysRegs = !
Reg.isVirtual();
1347 if (arePhysRegs != PostRA)
1354 if (DbgMO.getSubReg() != SrcMO->
getSubReg() ||
1355 DbgMO.getSubReg() != DstMO->getSubReg())
1361 if (PostRA &&
Reg != DstMO->getReg())
1365 DbgMO.setReg(SrcMO->
getReg());
1371using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
1379 if (!SuccToSinkTo.
empty() && InsertPos != SuccToSinkTo.
end())
1381 InsertPos->getDebugLoc()));
1387 SuccToSinkTo.
splice(InsertPos, ParentBlock,
MI,
1394 for (
const auto &DbgValueToSink : DbgValuesToSink) {
1397 SuccToSinkTo.
insert(InsertPos, NewDbgMI);
1399 bool PropagatedAllSunkOps =
true;
1400 for (
unsigned Reg : DbgValueToSink.second) {
1403 PropagatedAllSunkOps =
false;
1408 if (!PropagatedAllSunkOps)
1422 auto BlockPair = std::make_pair(
From, To);
1426 if (
auto It = HasStoreCache.
find(BlockPair); It != HasStoreCache.
end())
1429 if (
auto It = StoreInstrCache.
find(BlockPair); It != StoreInstrCache.
end())
1431 return I->mayAlias(AA, MI, false);
1434 bool SawStore =
false;
1435 bool HasAliasedStore =
false;
1444 if (BB == To || BB ==
From)
1448 if (HandledBlocks.
count(BB))
1451 HandledBlocks.
insert(BB);
1454 if (!HandledDomBlocks.
count(BB))
1455 HandledDomBlocks.
insert(BB);
1461 for (
auto *DomBB : HandledDomBlocks) {
1462 if (DomBB != BB && DT->
dominates(DomBB, BB))
1463 HasStoreCache[std::make_pair(DomBB, To)] =
true;
1464 else if(DomBB != BB && DT->
dominates(BB, DomBB))
1465 HasStoreCache[std::make_pair(
From, DomBB)] =
true;
1467 HasStoreCache[BlockPair] =
true;
1474 if (
I.isCall() ||
I.hasOrderedMemoryRef()) {
1475 for (
auto *DomBB : HandledDomBlocks) {
1476 if (DomBB != BB && DT->
dominates(DomBB, BB))
1477 HasStoreCache[std::make_pair(DomBB, To)] =
true;
1478 else if(DomBB != BB && DT->
dominates(BB, DomBB))
1479 HasStoreCache[std::make_pair(
From, DomBB)] =
true;
1481 HasStoreCache[BlockPair] =
true;
1491 if (
I.mayAlias(AA,
MI,
false))
1492 HasAliasedStore =
true;
1493 StoreInstrCache[BlockPair].push_back(&
I);
1500 HasStoreCache[BlockPair] =
false;
1501 return HasAliasedStore;
1510 assert(Preheader &&
"Cycle sink needs a preheader block");
1512 bool CanSink =
true;
1518 LLVM_DEBUG(
dbgs() <<
"CycleSink: Use not in cycle, can't sink.\n");
1533 SinkBlock =
MI.getParent();
1540 LLVM_DEBUG(
dbgs() <<
"CycleSink: Can't find nearest dominator\n");
1544 LLVM_DEBUG(
dbgs() <<
"CycleSink: Setting nearest common dom block: " <<
1553 LLVM_DEBUG(
dbgs() <<
"CycleSink: Not sinking, can't find sink block.\n");
1556 if (SinkBlock == Preheader) {
1558 dbgs() <<
"CycleSink: Not sinking, sink block is the preheader\n");
1563 dbgs() <<
"CycleSink: Not Sinking, block too large to analyse.\n");
1574 RegsToClearKillFlags.insert(MO.
getReg());
1579 assert(!
I.isDebugInstr() &&
"Should not sink debug inst");
1586bool MachineSinking::SinkInstruction(
MachineInstr &
MI,
bool &SawStore,
1587 AllSuccsCache &AllSuccessors) {
1593 if (!
MI.isSafeToMove(AA, SawStore))
1598 if (
MI.isConvergent())
1614 bool BreakPHIEdge =
false;
1617 FindSuccToSinkTo(
MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1628 if (
Reg == 0 || !
Reg.isPhysical())
1634 LLVM_DEBUG(
dbgs() <<
"Sink instr " <<
MI <<
"\tinto block " << *SuccToSinkTo);
1641 bool TryBreak =
false;
1643 MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo,
MI) :
true;
1644 if (!
MI.isSafeToMove(AA, Store)) {
1645 LLVM_DEBUG(
dbgs() <<
" *** NOTE: Won't sink load along critical edge.\n");
1651 if (!TryBreak && !DT->
dominates(ParentBlock, SuccToSinkTo)) {
1657 if (!TryBreak && CI->
getCycle(SuccToSinkTo) &&
1672 PostponeSplitCriticalEdge(
MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1675 "break critical edge\n");
1685 bool Status = PostponeSplitCriticalEdge(
MI, ParentBlock,
1686 SuccToSinkTo, BreakPHIEdge);
1689 "break critical edge\n");
1698 LLVM_DEBUG(
dbgs() <<
" *** Not sinking: prologue interference\n");
1704 for (
auto &MO :
MI.all_defs()) {
1714 if (
User.getInt()) {
1729 if (
MI.getMF()->getFunction().getSubprogram() &&
MI.isCopy())
1730 SalvageUnsunkDebugUsersOfCopy(
MI, SuccToSinkTo);
1740 RegsToClearKillFlags.insert(MO.
getReg());
1745void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1756 for (
auto &MO :
MI.all_defs()) {
1765 if (
User.getParent() ==
MI.getParent())
1769 "DBG_VALUE user of vreg, but has no operand for it?");
1776 for (
auto *
User : DbgDefUsers) {
1777 for (
auto &
Reg : DbgUseRegs) {
1778 for (
auto &
DbgOp :
User->getDebugOperandsForReg(
Reg)) {
1779 DbgOp.setReg(
MI.getOperand(1).getReg());
1780 DbgOp.setSubReg(
MI.getOperand(1).getSubReg());
1837 MachineFunctionProperties::Property::NoVRegs);
1857char PostRAMachineSinking::ID = 0;
1861 "PostRA Machine Sink",
false,
false)
1876 for (
auto *SI : SinkableBBs) {
1877 if (aliasWithRegsInLiveIn(*SI,
Reg,
TRI)) {
1891 if (!SinkableBBs.
count(SI) && aliasWithRegsInLiveIn(*SI,
Reg,
TRI))
1903 for (
auto DefReg : DefedRegsInCopy) {
1906 if (!BB || (SingleBB && SingleBB != BB))
1917 for (
auto U : UsedOpsInCopy) {
1923 if (UI.killsRegister(SrcReg,
TRI)) {
1924 UI.clearRegisterKills(SrcReg,
TRI);
1938 for (
unsigned DefReg : DefedRegsInCopy)
1941 for (
auto U : UsedOpsInCopy) {
1942 Register SrcReg =
MI->getOperand(U).getReg();
1945 Mask |= (*S).second;
1956 bool HasRegDependency =
false;
1957 for (
unsigned i = 0, e =
MI->getNumOperands(); i != e; ++i) {
1966 HasRegDependency =
true;
1975 }
else if (MO.
isUse()) {
1977 HasRegDependency =
true;
1983 return HasRegDependency;
1995 if (!
SI->livein_empty() &&
SI->pred_size() == 1)
1998 if (SinkableBBs.
empty())
2001 bool Changed =
false;
2005 ModifiedRegUnits.clear();
2006 UsedRegUnits.clear();
2007 SeenDbgInstrs.clear();
2017 if (
MI.isDebugValue() && !
MI.isDebugRef()) {
2019 bool IsValid =
true;
2025 ModifiedRegUnits, UsedRegUnits)) {
2032 MIUnits[Unit].push_back(MO.
getReg());
2036 for (
auto &RegOps : MIUnits)
2037 SeenDbgInstrs[RegOps.first].emplace_back(&
MI,
2038 std::move(RegOps.second));
2043 if (
MI.isDebugOrPseudoInstr())
2050 if (!
MI.isCopy() || !
MI.getOperand(0).isRenamable()) {
2058 ModifiedRegUnits, UsedRegUnits)) {
2064 "Unexpect SrcReg or DefReg");
2075 "Unexpected predecessor");
2081 for (
auto &MO :
MI.all_defs()) {
2083 for (
const auto &
MIRegs : SeenDbgInstrs.lookup(Unit)) {
2084 auto &Regs = DbgValsToSinkMap[
MIRegs.first];
2086 Regs.push_back(
Reg);
2090 auto DbgValsToSink = DbgValsToSinkMap.
takeVector();
2098 dbgs() <<
" *** Not sinking: prologue interference\n");
2109 ++NumPostRACopySink;
2118 bool Changed =
false;
2122 ModifiedRegUnits.init(*
TRI);
2123 UsedRegUnits.init(*
TRI);
2125 Changed |= tryToSinkCopy(BB, MF,
TRI,
TII);
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder MachineInstrBuilder & DefMI
BlockVerifier::State From
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
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)
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< unsigned > SinkIntoCycleLimit("machine-sink-cycle-limit", cl::desc("The maximum number of instructions considered for cycle sinking."), cl::init(50), cl::Hidden)
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.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
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)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
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()
const_toplevel_iterator toplevel_end() const
void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)
unsigned getCycleDepth(const BlockT *Block) const
get the depth for the cycle which containing a given block.
const_toplevel_iterator toplevel_begin() const
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
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.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
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.
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in 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 '...
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
bool sizeWithoutDebugLargerThan(unsigned Limit) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
void onEdgeSplit(const MachineBasicBlock &NewPredecessor, const MachineBasicBlock &NewSuccessor, const MachineBranchProbabilityInfo &MBPI)
incrementally calculate block frequencies when we split edges, to avoid full CFG traversal.
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Legacy analysis pass which computes a MachineCycleInfo.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
bool isReachableFromEntry(const MachineBasicBlock *A)
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
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.
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
const MachineOperand & getOperand(unsigned i) const
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
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...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
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.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
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.
void clear()
Completely clear the SetVector.
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...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
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...
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)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
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.
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.