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())
503 for (
auto &[SinkDst, MaybeAM] : SinkInto) {
507 if (SinkDst->isCopy()) {
520 Register DstReg = SinkDst->getOperand(0).getReg();
521 TII->reMaterialize(*SinkDst->getParent(), InsertPt, DstReg, 0,
MI, *
TRI);
522 New = &*std::prev(InsertPt);
523 if (!
New->getDebugLoc())
524 New->setDebugLoc(SinkDst->getDebugLoc());
530 MRI->clearKillFlags(UsedRegA);
532 MRI->clearKillFlags(UsedRegB);
535 New =
TII->emitLdStWithAddr(*SinkDst, MaybeAM);
541 MRI->clearKillFlags(R);
543 MRI->clearKillFlags(R);
547 if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
548 StoreInstrCache.
clear();
549 SinkDst->eraseFromParent();
557 while (!Worklist.
empty()) {
561 assert((
U->isCopy() ||
U->isDebugInstr()) &&
562 "Only debug uses and copies must remain");
564 Worklist.
push_back(
U->getOperand(0).getReg());
573 I->eraseFromParent();
580 MI.eraseFromParent();
588bool MachineSinking::AllUsesDominatedByBlock(
Register Reg,
592 bool &LocalUse)
const {
593 assert(
Reg.isVirtual() &&
"Only makes sense for vregs");
596 if (
MRI->use_nodbg_empty(
Reg))
614 MachineInstr *UseInst = MO.getParent();
615 unsigned OpNo = MO.getOperandNo();
616 MachineBasicBlock *UseBlock = UseInst->getParent();
617 return UseBlock == MBB && UseInst->isPHI() &&
618 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
627 unsigned OpNo = &MO - &UseInst->
getOperand(0);
629 if (UseInst->
isPHI()) {
633 }
else if (UseBlock == DefMBB) {
649 assert(
MI.mayLoad() &&
"Expected MI that loads!");
653 if (
MI.memoperands_empty())
658 if (PSV->isGOT() || PSV->isConstantPool())
664void MachineSinking::FindCycleSinkCandidates(
667 for (
auto &
MI : *BB) {
670 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction not a candidate for this "
675 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction is not cycle invariant\n");
678 bool DontMoveAcrossStore =
true;
679 if (!
MI.isSafeToMove(AA, DontMoveAcrossStore)) {
680 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction not safe to move.\n");
684 LLVM_DEBUG(
dbgs() <<
"CycleSink: Dont sink GOT or constant pool loads\n");
687 if (
MI.isConvergent())
696 LLVM_DEBUG(
dbgs() <<
"CycleSink: Instruction added as candidate.\n");
711 DT = &getAnalysis<MachineDominatorTree>();
712 PDT = &getAnalysis<MachinePostDominatorTree>();
713 CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
714 MBFI =
UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
715 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
716 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
721 bool EverMadeChange =
false;
724 bool MadeChange =
false;
727 CEBCandidates.
clear();
733 for (
const auto &Pair : ToSplit) {
734 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *
this);
735 if (NewSucc !=
nullptr) {
750 if (!MadeChange)
break;
751 EverMadeChange =
true;
757 for (
auto *
Cycle : Cycles) {
764 FindCycleSinkCandidates(
Cycle, Preheader, Candidates);
772 LLVM_DEBUG(
dbgs() <<
"CycleSink: Limit reached of instructions to "
777 if (!SinkIntoCycle(
Cycle, *
I))
779 EverMadeChange =
true;
785 HasStoreCache.
clear();
786 StoreInstrCache.
clear();
789 for (
auto I : RegsToClearKillFlags)
790 MRI->clearKillFlags(
I);
791 RegsToClearKillFlags.clear();
793 return EverMadeChange;
805 bool MadeChange =
false;
808 AllSuccsCache AllSuccessors;
813 bool ProcessedBegin, SawStore =
false;
823 if (
MI.isDebugOrPseudoInstr()) {
824 if (
MI.isDebugValue())
829 if (EnableSinkAndFold && PerformSinkAndFold(
MI, &
MBB)) {
838 if (PerformTrivialForwardCoalescing(
MI, &
MBB)) {
849 }
while (!ProcessedBegin);
851 SeenDbgUsers.
clear();
854 CachedRegisterPressure.
clear();
861 assert(
MI.isDebugValue() &&
"Expected DBG_VALUE for processing");
864 MI.getDebugLoc()->getInlinedAt());
865 bool SeenBefore = SeenDbgVars.
contains(Var);
869 SeenDbgUsers[MO.
getReg()].push_back(SeenDbgUser(&
MI, SeenBefore));
884 if (!CEBCandidates.
insert(std::make_pair(
From, To)).second)
904 if (
Reg.isPhysical())
910 if (
MRI->hasOneNonDBGUse(
Reg)) {
928 if (!isWorthBreakingCriticalEdge(
MI, FromBB, ToBB))
939 if (FromCycle == ToCycle && FromCycle &&
984 if (Pred != FromBB && !DT->
dominates(ToBB, Pred))
988 ToSplit.insert(std::make_pair(FromBB, ToBB));
993std::vector<unsigned> &
999 auto RP = CachedRegisterPressure.
find(&
MBB);
1000 if (RP != CachedRegisterPressure.
end())
1012 MII != MIE; --MII) {
1014 if (
MI.isDebugInstr() ||
MI.isPseudoProbe())
1018 RPTracker.recedeSkipDebugValues();
1019 assert(&*RPTracker.getPos() == &
MI &&
"RPTracker sync error!");
1020 RPTracker.recede(RegOpers);
1023 RPTracker.closeRegion();
1024 auto It = CachedRegisterPressure.
insert(
1025 std::make_pair(&
MBB, RPTracker.getPressure().MaxSetPressure));
1026 return It.first->second;
1029bool MachineSinking::registerPressureSetExceedsLimit(
1032 unsigned Weight = NRegs *
TRI->getRegClassWeight(RC).RegWeight;
1033 const int *PS =
TRI->getRegClassPressureSets(RC);
1034 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(
MBB);
1035 for (; *PS != -1; PS++)
1036 if (Weight + BBRegisterPressure[*PS] >=
1046 AllSuccsCache &AllSuccessors) {
1047 assert (SuccToSinkTo &&
"Invalid SinkTo Candidate BB");
1049 if (
MBB == SuccToSinkTo)
1062 bool NonPHIUse =
false;
1065 if (UseBlock == SuccToSinkTo && !UseInst.
isPHI())
1073 bool BreakPHIEdge =
false;
1076 FindSuccToSinkTo(
MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1077 return isProfitableToSinkTo(
Reg,
MI, SuccToSinkTo, MBB2, AllSuccessors);
1096 if (
Reg.isPhysical()) {
1098 if (MO.
isUse() && !
MRI->isConstantPhysReg(
Reg) && !
TII->isIgnorableUse(MO))
1106 bool LocalUse =
false;
1107 if (!AllUsesDominatedByBlock(
Reg, SuccToSinkTo,
MBB, BreakPHIEdge,
1125 if (registerPressureSetExceedsLimit(1,
MRI->getRegClass(
Reg),
1127 LLVM_DEBUG(
dbgs() <<
"register pressure exceed limit, not profitable.");
1143 AllSuccsCache &AllSuccessors)
const {
1145 auto Succs = AllSuccessors.find(
MBB);
1146 if (Succs != AllSuccessors.end())
1147 return Succs->second;
1160 if (DTChild->getIDom()->getBlock() ==
MI.getParent() &&
1163 AllSuccs.push_back(DTChild->getBlock());
1171 bool HasBlockFreq = LHSFreq != 0 || RHSFreq != 0;
1172 return HasBlockFreq ? LHSFreq < RHSFreq
1176 auto it = AllSuccessors.insert(std::make_pair(
MBB, AllSuccs));
1178 return it.first->second;
1185 AllSuccsCache &AllSuccessors) {
1186 assert (
MBB &&
"Invalid MachineBasicBlock!");
1195 if (!MO.
isReg())
continue;
1198 if (
Reg == 0)
continue;
1200 if (
Reg.isPhysical()) {
1205 if (!
MRI->isConstantPhysReg(
Reg) && !
TII->isIgnorableUse(MO))
1207 }
else if (!MO.
isDead()) {
1213 if (MO.
isUse())
continue;
1216 if (!
TII->isSafeToMoveRegClassDefs(
MRI->getRegClass(
Reg)))
1224 bool LocalUse =
false;
1225 if (!AllUsesDominatedByBlock(
Reg, SuccToSinkTo,
MBB,
1226 BreakPHIEdge, LocalUse))
1237 GetAllSortedSuccessors(
MI,
MBB, AllSuccessors)) {
1238 bool LocalUse =
false;
1239 if (AllUsesDominatedByBlock(
Reg, SuccBlock,
MBB,
1240 BreakPHIEdge, LocalUse)) {
1241 SuccToSinkTo = SuccBlock;
1252 if (!isProfitableToSinkTo(
Reg,
MI,
MBB, SuccToSinkTo, AllSuccessors))
1259 if (
MBB == SuccToSinkTo)
1264 if (SuccToSinkTo && SuccToSinkTo->
isEHPad())
1274 if (SuccToSinkTo && !
TII->isSafeToSink(
MI, SuccToSinkTo, CI))
1277 return SuccToSinkTo;
1292 auto *
MBB =
MI.getParent();
1297 auto *PredBB = PredMBB->getBasicBlock();
1303 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
1308 bool OffsetIsScalable;
1309 if (!
TII->getMemOperandWithOffset(
MI, BaseOp,
Offset, OffsetIsScalable,
TRI))
1312 if (!BaseOp->
isReg())
1315 if (!(
MI.mayLoad() && !
MI.isPredicable()))
1318 MachineBranchPredicate MBP;
1319 if (
TII->analyzeBranchPredicate(*PredMBB, MBP,
false))
1322 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1323 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1324 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1325 MBP.LHS.getReg() == BaseOp->
getReg();
1342 auto CopyOperands =
TII.isCopyInstr(SinkInst);
1345 SrcMO = CopyOperands->Source;
1346 DstMO = CopyOperands->Destination;
1349 bool PostRA =
MRI.getNumVirtRegs() == 0;
1357 bool arePhysRegs = !
Reg.isVirtual();
1358 if (arePhysRegs != PostRA)
1365 if (DbgMO.getSubReg() != SrcMO->
getSubReg() ||
1366 DbgMO.getSubReg() != DstMO->getSubReg())
1372 if (PostRA &&
Reg != DstMO->getReg())
1376 DbgMO.setReg(SrcMO->
getReg());
1382using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
1390 if (!SuccToSinkTo.
empty() && InsertPos != SuccToSinkTo.
end())
1392 InsertPos->getDebugLoc()));
1398 SuccToSinkTo.
splice(InsertPos, ParentBlock,
MI,
1405 for (
const auto &DbgValueToSink : DbgValuesToSink) {
1408 SuccToSinkTo.
insert(InsertPos, NewDbgMI);
1410 bool PropagatedAllSunkOps =
true;
1411 for (
unsigned Reg : DbgValueToSink.second) {
1414 PropagatedAllSunkOps =
false;
1419 if (!PropagatedAllSunkOps)
1433 auto BlockPair = std::make_pair(
From, To);
1437 if (
auto It = HasStoreCache.
find(BlockPair); It != HasStoreCache.
end())
1440 if (
auto It = StoreInstrCache.
find(BlockPair); It != StoreInstrCache.
end())
1442 return I->mayAlias(AA, MI, false);
1445 bool SawStore =
false;
1446 bool HasAliasedStore =
false;
1455 if (BB == To || BB ==
From)
1459 if (HandledBlocks.
count(BB))
1462 HandledBlocks.
insert(BB);
1465 if (!HandledDomBlocks.
count(BB))
1466 HandledDomBlocks.
insert(BB);
1472 for (
auto *DomBB : HandledDomBlocks) {
1473 if (DomBB != BB && DT->
dominates(DomBB, BB))
1474 HasStoreCache[std::make_pair(DomBB, To)] =
true;
1475 else if(DomBB != BB && DT->
dominates(BB, DomBB))
1476 HasStoreCache[std::make_pair(
From, DomBB)] =
true;
1478 HasStoreCache[BlockPair] =
true;
1485 if (
I.isCall() ||
I.hasOrderedMemoryRef()) {
1486 for (
auto *DomBB : HandledDomBlocks) {
1487 if (DomBB != BB && DT->
dominates(DomBB, BB))
1488 HasStoreCache[std::make_pair(DomBB, To)] =
true;
1489 else if(DomBB != BB && DT->
dominates(BB, DomBB))
1490 HasStoreCache[std::make_pair(
From, DomBB)] =
true;
1492 HasStoreCache[BlockPair] =
true;
1502 if (
I.mayAlias(AA,
MI,
false))
1503 HasAliasedStore =
true;
1504 StoreInstrCache[BlockPair].push_back(&
I);
1511 HasStoreCache[BlockPair] =
false;
1512 return HasAliasedStore;
1521 assert(Preheader &&
"Cycle sink needs a preheader block");
1523 bool CanSink =
true;
1529 LLVM_DEBUG(
dbgs() <<
"CycleSink: Use not in cycle, can't sink.\n");
1544 SinkBlock =
MI.getParent();
1551 LLVM_DEBUG(
dbgs() <<
"CycleSink: Can't find nearest dominator\n");
1555 LLVM_DEBUG(
dbgs() <<
"CycleSink: Setting nearest common dom block: " <<
1564 LLVM_DEBUG(
dbgs() <<
"CycleSink: Not sinking, can't find sink block.\n");
1567 if (SinkBlock == Preheader) {
1569 dbgs() <<
"CycleSink: Not sinking, sink block is the preheader\n");
1574 dbgs() <<
"CycleSink: Not Sinking, block too large to analyse.\n");
1585 RegsToClearKillFlags.insert(MO.
getReg());
1590 assert(!
I.isDebugInstr() &&
"Should not sink debug inst");
1597bool MachineSinking::SinkInstruction(
MachineInstr &
MI,
bool &SawStore,
1598 AllSuccsCache &AllSuccessors) {
1604 if (!
MI.isSafeToMove(AA, SawStore))
1609 if (
MI.isConvergent())
1625 bool BreakPHIEdge =
false;
1628 FindSuccToSinkTo(
MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1639 if (
Reg == 0 || !
Reg.isPhysical())
1645 LLVM_DEBUG(
dbgs() <<
"Sink instr " <<
MI <<
"\tinto block " << *SuccToSinkTo);
1652 bool TryBreak =
false;
1654 MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo,
MI) :
true;
1655 if (!
MI.isSafeToMove(AA, Store)) {
1656 LLVM_DEBUG(
dbgs() <<
" *** NOTE: Won't sink load along critical edge.\n");
1662 if (!TryBreak && !DT->
dominates(ParentBlock, SuccToSinkTo)) {
1668 if (!TryBreak && CI->
getCycle(SuccToSinkTo) &&
1683 PostponeSplitCriticalEdge(
MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1686 "break critical edge\n");
1696 bool Status = PostponeSplitCriticalEdge(
MI, ParentBlock,
1697 SuccToSinkTo, BreakPHIEdge);
1700 "break critical edge\n");
1709 LLVM_DEBUG(
dbgs() <<
" *** Not sinking: prologue interference\n");
1715 for (
auto &MO :
MI.all_defs()) {
1725 if (
User.getInt()) {
1740 if (
MI.getMF()->getFunction().getSubprogram() &&
MI.isCopy())
1741 SalvageUnsunkDebugUsersOfCopy(
MI, SuccToSinkTo);
1751 RegsToClearKillFlags.insert(MO.
getReg());
1756void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1767 for (
auto &MO :
MI.all_defs()) {
1776 if (
User.getParent() ==
MI.getParent())
1780 "DBG_VALUE user of vreg, but has no operand for it?");
1787 for (
auto *
User : DbgDefUsers) {
1788 for (
auto &
Reg : DbgUseRegs) {
1789 for (
auto &
DbgOp :
User->getDebugOperandsForReg(
Reg)) {
1790 DbgOp.setReg(
MI.getOperand(1).getReg());
1791 DbgOp.setSubReg(
MI.getOperand(1).getSubReg());
1848 MachineFunctionProperties::Property::NoVRegs);
1868char PostRAMachineSinking::ID = 0;
1872 "PostRA Machine Sink",
false,
false)
1887 for (
auto *SI : SinkableBBs) {
1888 if (aliasWithRegsInLiveIn(*SI,
Reg,
TRI)) {
1902 if (!SinkableBBs.
count(SI) && aliasWithRegsInLiveIn(*SI,
Reg,
TRI))
1914 for (
auto DefReg : DefedRegsInCopy) {
1917 if (!BB || (SingleBB && SingleBB != BB))
1928 for (
auto U : UsedOpsInCopy) {
1934 if (UI.killsRegister(SrcReg,
TRI)) {
1935 UI.clearRegisterKills(SrcReg,
TRI);
1949 for (
unsigned DefReg : DefedRegsInCopy)
1952 for (
auto U : UsedOpsInCopy)
1962 bool HasRegDependency =
false;
1963 for (
unsigned i = 0, e =
MI->getNumOperands(); i != e; ++i) {
1972 HasRegDependency =
true;
1981 }
else if (MO.
isUse()) {
1983 HasRegDependency =
true;
1989 return HasRegDependency;
2001 if (!
SI->livein_empty() &&
SI->pred_size() == 1)
2004 if (SinkableBBs.
empty())
2007 bool Changed =
false;
2011 ModifiedRegUnits.clear();
2012 UsedRegUnits.clear();
2013 SeenDbgInstrs.clear();
2023 if (
MI.isDebugValue() && !
MI.isDebugRef()) {
2025 bool IsValid =
true;
2031 ModifiedRegUnits, UsedRegUnits)) {
2038 MIUnits[Unit].push_back(MO.
getReg());
2042 for (
auto &RegOps : MIUnits)
2043 SeenDbgInstrs[RegOps.first].emplace_back(&
MI,
2044 std::move(RegOps.second));
2049 if (
MI.isDebugOrPseudoInstr())
2056 if (!
MI.isCopy() || !
MI.getOperand(0).isRenamable()) {
2064 ModifiedRegUnits, UsedRegUnits)) {
2070 "Unexpect SrcReg or DefReg");
2081 "Unexpected predecessor");
2087 for (
auto &MO :
MI.all_defs()) {
2089 for (
const auto &
MIRegs : SeenDbgInstrs.lookup(Unit)) {
2090 auto &Regs = DbgValsToSinkMap[
MIRegs.first];
2092 Regs.push_back(
Reg);
2096 auto DbgValsToSink = DbgValsToSinkMap.
takeVector();
2104 dbgs() <<
" *** Not sinking: prologue interference\n");
2115 ++NumPostRACopySink;
2124 bool Changed =
false;
2128 ModifiedRegUnits.init(*
TRI);
2129 UsedRegUnits.init(*
TRI);
2131 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
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.
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.