63#define DEBUG_TYPE "machinelicm"
69 cl::desc(
"Disable hoisting instructions to"
73 "disable the feature"),
75 "enable the feature when using profile data"),
77 "enable the feature with/wo profile data")));
80 "Number of machine instructions hoisted out of loops");
82 "Number of instructions hoisted in low reg pressure situation");
84 "Number of high latency instructions hoisted");
86 "Number of hoisted machine instructions CSEed");
88 "Number of machine instructions hoisted out of loops post regalloc");
90 "Number of stores of const phys reg hoisted out of loops");
92 "Number of instructions not hoisted due to block frequency");
95 enum HoistResult { NotHoisted = 1, Hoisted = 2, ErasedMI = 4 };
97 class MachineLICMImpl {
98 const CodeGenOptions &Opts;
99 const TargetInstrInfo *TII =
nullptr;
100 const TargetLoweringBase *TLI =
nullptr;
101 const TargetRegisterInfo *TRI =
nullptr;
102 const MachineFrameInfo *MFI =
nullptr;
103 MachineRegisterInfo *MRI =
nullptr;
104 const RegisterClassInfo *RegClassInfo =
nullptr;
105 TargetSchedModel SchedModel;
106 bool PreRegAlloc =
false;
107 bool HasProfileData =
false;
113 MachineBlockFrequencyInfo *MBFI =
nullptr;
114 MachineLoopInfo *MLI =
nullptr;
115 MachineDomTreeUpdater *MDTU =
nullptr;
118 bool Changed =
false;
119 bool FirstInLoop =
false;
123 SmallDenseMap<MachineLoop *, bool> AllowedToHoistLoads;
126 DenseMap<MachineLoop *, SmallVector<MachineBasicBlock *, 8>> ExitBlockMap;
128 bool isExitBlock(MachineLoop *CurLoop,
const MachineBasicBlock *
MBB) {
129 auto [It,
Inserted] = ExitBlockMap.try_emplace(CurLoop);
133 It->second = std::move(ExitBlocks);
139 SmallDenseSet<Register> RegSeen;
140 SmallVector<unsigned, 8> RegPressure;
144 SmallVector<unsigned, 8> RegLimit;
150 DenseMap<MachineBasicBlock *,
151 DenseMap<unsigned, std::vector<MachineInstr *>>>
157 SmallDenseMap<MachineLoop *, bool> GuaranteedToExecute;
160 MachineLICMImpl(
const CodeGenOptions &Opts,
bool PreRegAlloc,
162 : Opts(Opts), PreRegAlloc(PreRegAlloc), LegacyPass(LegacyPass),
164 assert((LegacyPass || MFAM) &&
"LegacyPass or MFAM must be provided");
165 assert(!(LegacyPass && MFAM) &&
166 "LegacyPass and MFAM cannot be provided at the same time");
171 void releaseMemory() {
177 ExitBlockMap.clear();
182 struct CandidateInfo {
187 CandidateInfo(MachineInstr *mi,
Register def,
int fi)
188 : MI(mi), Def(def), FI(fi) {}
191 void HoistRegionPostRA(MachineLoop *CurLoop);
193 void HoistPostRA(MachineInstr *
MI,
Register Def, MachineLoop *CurLoop);
195 void ProcessMI(MachineInstr *
MI, BitVector &RUDefs, BitVector &RUClobbers,
196 SmallDenseSet<int> &StoredFIs,
197 SmallVectorImpl<CandidateInfo> &Candidates,
198 MachineLoop *CurLoop);
200 void AddToLiveIns(MCRegister
Reg, MachineLoop *CurLoop);
202 bool IsLICMCandidate(MachineInstr &
I, MachineLoop *CurLoop);
204 bool IsLoopInvariantInst(MachineInstr &
I, MachineLoop *CurLoop);
206 bool HasLoopPHIUse(
const MachineInstr *
MI, MachineLoop *CurLoop);
208 bool HasHighOperandLatency(MachineInstr &
MI,
unsigned DefIdx,
Register Reg,
209 MachineLoop *CurLoop)
const;
211 bool IsCheapInstruction(MachineInstr &
MI)
const;
213 bool CanCauseHighRegPressure(
const SmallDenseMap<unsigned, int> &
Cost,
216 void UpdateBackTraceRegPressure(
const MachineInstr *
MI);
218 bool IsProfitableToHoist(MachineInstr &
MI, MachineLoop *CurLoop);
220 bool IsGuaranteedToExecute(MachineBasicBlock *BB, MachineLoop *CurLoop);
222 void EnterScope(MachineBasicBlock *
MBB);
224 void ExitScope(MachineBasicBlock *
MBB);
226 void ExitScopeIfDone(
228 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
229 const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap);
233 void InitRegPressure(MachineBasicBlock *BB);
235 SmallDenseMap<unsigned, int> calcRegisterCost(
const MachineInstr *
MI,
237 bool ConsiderUnseenAsDef);
239 void UpdateRegPressure(
const MachineInstr *
MI,
240 bool ConsiderUnseenAsDef =
false);
242 MachineInstr *ExtractHoistableLoad(MachineInstr *
MI, MachineLoop *CurLoop);
244 MachineInstr *LookForDuplicate(
const MachineInstr *
MI,
245 std::vector<MachineInstr *> &PrevMIs);
248 EliminateCSE(MachineInstr *
MI,
249 DenseMap<
unsigned, std::vector<MachineInstr *>>::iterator &CI);
251 bool MayCSE(MachineInstr *
MI);
253 unsigned Hoist(MachineInstr *
MI, MachineBasicBlock *Preheader,
254 MachineLoop *CurLoop);
256 void InitCSEMap(MachineBasicBlock *BB);
258 void InitializeLoadsHoistableLoops();
260 bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
261 MachineBasicBlock *TgtBlock);
262 MachineBasicBlock *getOrCreatePreheader(MachineLoop *CurLoop);
269 MachineLICMBase(
char &ID,
bool PreRegAlloc)
270 : MachineFunctionPass(
ID), PreRegAlloc(PreRegAlloc) {}
274 void getAnalysisUsage(AnalysisUsage &AU)
const override {
277 AU.
addRequired<LazyMachineBlockFrequencyInfoPass>();
279 AU.
addRequired<MachineRegisterClassInfoWrapperPass>();
288 class MachineLICM :
public MachineLICMBase {
291 MachineLICM() : MachineLICMBase(ID,
false) {}
294 class EarlyMachineLICM :
public MachineLICMBase {
297 EarlyMachineLICM() : MachineLICMBase(ID,
true) {}
303char EarlyMachineLICM::ID;
309 "Machine Loop Invariant Code Motion",
false,
false)
319 "Early Machine Loop Invariant Code Motion",
false,
false)
326 "Early Machine Loop Invariant Code Motion",
false,
false)
329 if (skipFunction(MF.getFunction()))
336#define GET_RESULT(RESULT, GETTER, INFIX) \
338 ? &LegacyPass->getAnalysis<RESULT##INFIX##WrapperPass>().GETTER() \
339 : &MFAM->getResult<RESULT##Analysis>(MF))
355 MachineDomTreeUpdater::UpdateStrategy::Lazy);
361 TII = ST.getInstrInfo();
362 TLI = ST.getTargetLowering();
363 TRI = ST.getRegisterInfo();
366 SchedModel.
init(&ST);
385 unsigned NumRPS =
TRI->getNumRegPressureSets();
386 RegPressure.resize(NumRPS);
389 for (
unsigned i = 0, e = NumRPS; i != e; ++i)
393 if (Opts.machine_licm_hoist_const_loads)
394 InitializeLoadsHoistableLoops();
397 while (!Worklist.
empty()) {
401 HoistRegionPostRA(CurLoop);
407 HoistOutOfLoop(
N, CurLoop);
423 if (
MI->memoperands_empty())
426 if (!
MemOp->isStore() || !
MemOp->getPseudoValue())
430 if (
Value->getFrameIndex() == FI)
471 const unsigned NumRegs =
TRI.getNumRegs();
472 const unsigned MaskWords = (NumRegs + 31) / 32;
473 for (
unsigned K = 0;
K < MaskWords; ++
K) {
475 for (
unsigned Bit = 0; Bit < 32; ++Bit) {
476 const unsigned PhysReg = (
K * 32) + Bit;
477 if (PhysReg == NumRegs)
480 if (PhysReg && !((Word >> Bit) & 1)) {
481 for (MCRegUnit Unit :
TRI.regunits(PhysReg))
482 RUsFromRegsNotInMask.
set(
static_cast<unsigned>(Unit));
487 RUs |= RUsFromRegsNotInMask;
492void MachineLICMImpl::ProcessMI(MachineInstr *
MI, BitVector &RUDefs,
493 BitVector &RUClobbers,
494 SmallDenseSet<int> &StoredFIs,
495 SmallVectorImpl<CandidateInfo> &Candidates,
496 MachineLoop *CurLoop) {
497 bool RuledOut =
false;
498 bool HasNonInvariantUse =
false;
500 for (
const MachineOperand &MO :
MI->operands()) {
503 int FI = MO.getIndex();
504 if (!StoredFIs.
count(FI) &&
508 HasNonInvariantUse =
true;
514 if (MO.isRegMask()) {
527 if (!HasNonInvariantUse) {
528 for (MCRegUnit Unit :
TRI->regunits(
Reg)) {
531 if (RUDefs.
test(
static_cast<unsigned>(Unit)) ||
532 RUClobbers.
test(
static_cast<unsigned>(Unit))) {
533 HasNonInvariantUse =
true;
552 for (MCRegUnit Unit :
TRI->regunits(
Reg)) {
553 if (RUDefs.
test(
static_cast<unsigned>(Unit))) {
554 RUClobbers.
set(
static_cast<unsigned>(Unit));
556 }
else if (RUClobbers.
test(
static_cast<unsigned>(Unit))) {
562 RUDefs.
set(
static_cast<unsigned>(Unit));
568 if (Def && !RuledOut) {
569 int FI = std::numeric_limits<int>::min();
570 if ((!HasNonInvariantUse && IsLICMCandidate(*
MI, CurLoop)) ||
578void MachineLICMImpl::HoistRegionPostRA(MachineLoop *CurLoop) {
579 MachineBasicBlock *Preheader = getOrCreatePreheader(CurLoop);
583 unsigned NumRegUnits =
TRI->getNumRegUnits();
584 BitVector RUDefs(NumRegUnits);
585 BitVector RUClobbers(NumRegUnits);
588 SmallDenseSet<int> StoredFIs;
592 for (MachineBasicBlock *BB : CurLoop->
getBlocks()) {
596 if (
ML &&
ML->getHeader()->isEHPad())
continue;
601 for (
const auto &LI : BB->liveins()) {
602 for (MCRegUnit Unit :
TRI->regunits(LI.PhysReg))
603 RUDefs.
set(
static_cast<unsigned>(Unit));
607 if (
const uint32_t *Mask = BB->getBeginClobberMask(
TRI))
617 for (MCRegUnit Unit :
TRI->regunits(
Reg))
618 RUClobbers.
set(
static_cast<unsigned>(Unit));
620 for (MCRegUnit Unit :
TRI->regunits(
Reg))
621 RUClobbers.
set(
static_cast<unsigned>(Unit));
624 GuaranteedToExecute.
clear();
625 for (MachineInstr &
MI : *BB)
626 ProcessMI(&
MI, RUDefs, RUClobbers, StoredFIs, Candidates, CurLoop);
630 BitVector TermRUs(NumRegUnits);
632 if (TI != Preheader->
end()) {
633 for (
const MachineOperand &MO : TI->operands()) {
639 for (MCRegUnit Unit :
TRI->regunits(
Reg))
640 TermRUs.set(
static_cast<unsigned>(Unit));
652 for (CandidateInfo &Candidate : Candidates) {
653 if (Candidate.FI != std::numeric_limits<int>::min() &&
654 StoredFIs.
count(Candidate.FI))
659 for (MCRegUnit Unit :
TRI->regunits(Def)) {
660 if (RUClobbers.
test(
static_cast<unsigned>(Unit)) ||
661 TermRUs.test(
static_cast<unsigned>(Unit))) {
670 MachineInstr *
MI = Candidate.MI;
671 for (
const MachineOperand &MO :
MI->all_uses()) {
674 for (MCRegUnit Unit :
TRI->regunits(MO.getReg())) {
675 if (RUDefs.
test(
static_cast<unsigned>(Unit)) ||
676 RUClobbers.
test(
static_cast<unsigned>(Unit))) {
689 HoistPostRA(
MI, Candidate.Def, CurLoop);
695void MachineLICMImpl::AddToLiveIns(MCRegister
Reg, MachineLoop *CurLoop) {
696 for (MachineBasicBlock *BB : CurLoop->
getBlocks()) {
697 if (!BB->isLiveIn(
Reg))
699 for (MachineInstr &
MI : *BB) {
700 for (MachineOperand &MO :
MI.all_uses()) {
703 if (
TRI->regsOverlap(
Reg, MO.getReg()))
712void MachineLICMImpl::HoistPostRA(MachineInstr *
MI,
Register Def,
713 MachineLoop *CurLoop) {
729 assert(!
MI->isDebugInstr() &&
"Should not hoist debug inst");
735 AddToLiveIns(Def, CurLoop);
743bool MachineLICMImpl::IsGuaranteedToExecute(MachineBasicBlock *BB,
744 MachineLoop *CurLoop) {
753 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
763void MachineLICMImpl::EnterScope(MachineBasicBlock *
MBB) {
770void MachineLICMImpl::ExitScope(MachineBasicBlock *
MBB) {
778void MachineLICMImpl::ExitScopeIfDone(
780 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
781 const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap) {
782 if (OpenChildren[Node])
786 ExitScope(
Node->getBlock());
789 if (!Parent || --OpenChildren[Parent] != 0)
800 MachineLoop *CurLoop) {
801 MachineBasicBlock *Preheader = getOrCreatePreheader(CurLoop);
807 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
808 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
812 while (!WorkList.
empty()) {
814 assert(Node &&
"Null dominator tree node?");
815 MachineBasicBlock *BB =
Node->getBlock();
820 if (
ML &&
ML->getHeader()->isEHPad())
833 OpenChildren[
Node] = 0;
840 size_t WorkListStart = WorkList.
size();
842 ParentMap[Child] =
Node;
845 std::reverse(WorkList.
begin() + WorkListStart, WorkList.
end());
846 OpenChildren[
Node] = WorkList.
size() - WorkListStart;
855 InitRegPressure(Preheader);
859 MachineBasicBlock *
MBB =
Node->getBlock();
864 GuaranteedToExecute.
clear();
866 unsigned HoistRes = HoistResult::NotHoisted;
867 HoistRes = Hoist(&
MI, Preheader, CurLoop);
868 if (HoistRes & HoistResult::NotHoisted) {
871 SmallVector<MachineLoop *> InnerLoopWorkList;
872 for (MachineLoop *L = MLI->
getLoopFor(
MI.getParent()); L != CurLoop;
873 L =
L->getParentLoop())
876 while (!InnerLoopWorkList.
empty()) {
877 MachineLoop *InnerLoop = InnerLoopWorkList.
pop_back_val();
879 if (InnerLoopPreheader) {
880 HoistRes = Hoist(&
MI, InnerLoopPreheader, InnerLoop);
881 if (HoistRes & HoistResult::Hoisted)
887 if (HoistRes & HoistResult::ErasedMI)
890 UpdateRegPressure(&
MI);
894 ExitScopeIfDone(Node, OpenChildren, ParentMap);
901void MachineLICMImpl::InitRegPressure(MachineBasicBlock *BB) {
909 MachineBasicBlock *
TBB =
nullptr, *FBB =
nullptr;
910 SmallVector<MachineOperand, 4>
Cond;
915 for (
const MachineInstr &
MI : *BB)
916 UpdateRegPressure(&
MI,
true);
920void MachineLICMImpl::UpdateRegPressure(
const MachineInstr *
MI,
921 bool ConsiderUnseenAsDef) {
922 auto Cost = calcRegisterCost(
MI,
true, ConsiderUnseenAsDef);
923 for (
const auto &[Class, Weight] :
Cost) {
924 if (
static_cast<int>(RegPressure[Class]) < -Weight)
937SmallDenseMap<unsigned, int>
938MachineLICMImpl::calcRegisterCost(
const MachineInstr *
MI,
bool ConsiderSeen,
939 bool ConsiderUnseenAsDef) {
940 SmallDenseMap<unsigned, int>
Cost;
941 if (
MI->isImplicitDef())
943 for (
unsigned i = 0, e =
MI->getDesc().getNumOperands(); i != e; ++i) {
944 const MachineOperand &MO =
MI->getOperand(i);
952 bool isNew = ConsiderSeen ? RegSeen.
insert(
Reg).second :
false;
955 RegClassWeight
W =
TRI->getRegClassWeight(RC);
958 RCCost =
W.RegWeight;
961 if (isNew && !isKill && ConsiderUnseenAsDef)
963 RCCost =
W.RegWeight;
964 else if (!isNew && isKill)
965 RCCost = -
W.RegWeight;
969 const int *PS =
TRI->getRegClassPressureSets(RC);
970 for (; *PS != -1; ++PS)
979 assert(
MI.mayLoad() &&
"Expected MI that loads!");
983 if (
MI.memoperands_empty())
988 if (PSV->isGOT() || PSV->isConstantPool())
1005 bool FoundCallerPresReg =
false;
1006 if (!
MI.mayStore() ||
MI.hasUnmodeledSideEffects() ||
1007 (
MI.getNumOperands() == 0))
1016 if (
Reg.isVirtual())
1018 if (
Reg.isVirtual())
1020 if (!
TRI->isCallerPreservedPhysReg(
Reg.asMCReg(), *
MI.getMF()))
1023 FoundCallerPresReg =
true;
1024 }
else if (!MO.
isImm()) {
1028 return FoundCallerPresReg;
1046 Register CopySrcReg =
MI.getOperand(1).getReg();
1050 if (!
TRI->isCallerPreservedPhysReg(CopySrcReg.
asMCReg(), *MF))
1053 Register CopyDstReg =
MI.getOperand(0).getReg();
1066bool MachineLICMImpl::IsLICMCandidate(MachineInstr &
I, MachineLoop *CurLoop) {
1068 bool DontMoveAcrossStore =
1069 !Opts.machine_licm_hoist_const_loads || !AllowedToHoistLoads[CurLoop];
1070 if ((!
I.isSafeToMove(DontMoveAcrossStore)) &&
1071 !(Opts.machine_licm_hoist_const_stores &&
1084 !IsGuaranteedToExecute(
I.getParent(), CurLoop)) {
1093 if (
I.isConvergent())
1096 if (!
TII->shouldHoist(
I, CurLoop))
1103bool MachineLICMImpl::IsLoopInvariantInst(MachineInstr &
I,
1104 MachineLoop *CurLoop) {
1105 if (!IsLICMCandidate(
I, CurLoop)) {
1106 LLVM_DEBUG(
dbgs() <<
"LICM: Instruction not a LICM candidate\n");
1114bool MachineLICMImpl::HasLoopPHIUse(
const MachineInstr *
MI,
1115 MachineLoop *CurLoop) {
1118 MI = Work.pop_back_val();
1119 for (
const MachineOperand &MO :
MI->all_defs()) {
1125 if (
UseMI.isPHI()) {
1139 Work.push_back(&
UseMI);
1142 }
while (!Work.empty());
1148bool MachineLICMImpl::HasHighOperandLatency(MachineInstr &
MI,
unsigned DefIdx,
1150 MachineLoop *CurLoop)
const {
1155 if (
UseMI.isCopyLike())
1159 for (
unsigned i = 0, e =
UseMI.getNumOperands(); i != e; ++i) {
1160 const MachineOperand &MO =
UseMI.getOperand(i);
1167 if (
TII->hasHighOperandLatency(SchedModel,
MRI,
MI, DefIdx,
UseMI, i))
1180bool MachineLICMImpl::IsCheapInstruction(MachineInstr &
MI)
const {
1184 bool isCheap =
false;
1185 unsigned NumDefs =
MI.getDesc().getNumDefs();
1186 for (
unsigned i = 0, e =
MI.getNumOperands(); NumDefs && i != e; ++i) {
1187 MachineOperand &DefMO =
MI.getOperand(i);
1195 if (!
TII->hasLowDefLatency(SchedModel,
MI, i))
1205bool MachineLICMImpl::CanCauseHighRegPressure(
1206 const SmallDenseMap<unsigned, int> &
Cost,
bool CheapInstr) {
1207 for (
const auto &[Class, Weight] :
Cost) {
1211 int Limit = RegLimit[
Class];
1215 if (CheapInstr && !Opts.machine_licm_hoist_cheap_insts)
1218 for (
const auto &RP : BackTrace)
1219 if (
static_cast<int>(RP[Class]) + Weight >= Limit)
1229void MachineLICMImpl::UpdateBackTraceRegPressure(
const MachineInstr *
MI) {
1232 auto Cost = calcRegisterCost(
MI,
false,
1236 for (
auto &RP : BackTrace)
1237 for (
const auto &[Class, Weight] :
Cost)
1243bool MachineLICMImpl::IsProfitableToHoist(MachineInstr &
MI,
1244 MachineLoop *CurLoop) {
1245 if (
MI.isImplicitDef())
1260 if (Opts.machine_licm_hoist_const_stores &&
1264 bool CheapInstr = IsCheapInstruction(
MI);
1265 bool CreatesCopy = HasLoopPHIUse(&
MI, CurLoop);
1268 if (CheapInstr && CreatesCopy) {
1275 if (
TII->isTriviallyReMaterializable(
MI))
1280 for (
unsigned i = 0, e =
MI.getDesc().getNumOperands(); i != e; ++i) {
1281 const MachineOperand &MO =
MI.getOperand(i);
1287 if (MO.
isDef() && HasHighOperandLatency(
MI, i,
Reg, CurLoop)) {
1300 auto Cost = calcRegisterCost(&
MI,
false,
1305 if (!CanCauseHighRegPressure(
Cost, CheapInstr)) {
1320 if (Opts.machine_licm_avoid_speculation &&
1321 (!IsGuaranteedToExecute(
MI.getParent(), CurLoop) && !MayCSE(&
MI))) {
1329 if (
MI.isCopy() ||
MI.isRegSequence()) {
1333 [
this](
const MachineOperand &UseOp) {
1334 return !UseOp.isReg() || UseOp.getReg().isVirtual() ||
1335 MRI->isConstantPhysReg(UseOp.getReg());
1337 IsLoopInvariantInst(
MI, CurLoop) &&
1339 [&CurLoop,
this, DefReg,
1341 if (!CurLoop->contains(&UseMI))
1348 if (CanCauseHighRegPressure(Cost, false) &&
1349 !CurLoop->isLoopInvariant(UseMI, DefReg))
1359 if (!
TII->isTriviallyReMaterializable(
MI) &&
1360 !
MI.isDereferenceableInvariantLoad()) {
1371MachineInstr *MachineLICMImpl::ExtractHoistableLoad(MachineInstr *
MI,
1372 MachineLoop *CurLoop) {
1374 if (
MI->canFoldAsLoad())
1380 if (!
MI->isDereferenceableInvariantLoad())
1384 unsigned LoadRegIndex;
1386 TII->getOpcodeAfterMemoryUnfold(
MI->getOpcode(),
1390 if (NewOpc == 0)
return nullptr;
1391 const MCInstrDesc &MID =
TII->get(NewOpc);
1397 SmallVector<MachineInstr *, 2> NewMIs;
1403 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
1406 "Unfolded a load into multiple instructions!");
1413 if (!IsLoopInvariantInst(*NewMIs[0], CurLoop) ||
1414 !IsProfitableToHoist(*NewMIs[0], CurLoop)) {
1415 NewMIs[0]->eraseFromParent();
1416 NewMIs[1]->eraseFromParent();
1421 UpdateRegPressure(NewMIs[1]);
1426 if (
MI->shouldUpdateAdditionalCallInfo())
1429 MI->eraseFromParent();
1436void MachineLICMImpl::InitCSEMap(MachineBasicBlock *BB) {
1437 for (MachineInstr &
MI : *BB)
1443void MachineLICMImpl::InitializeLoadsHoistableLoops() {
1449 while (!Worklist.empty()) {
1450 auto *
L = Worklist.pop_back_val();
1451 AllowedToHoistLoads[
L] =
true;
1464 for (
auto *
MBB :
Loop->blocks()) {
1466 if (!AllowedToHoistLoads[
Loop])
1468 for (
auto &
MI : *
MBB) {
1469 if (!
MI.isLoadFoldBarrier() && !
MI.mayStore() && !
MI.isCall() &&
1470 !(
MI.mayLoad() &&
MI.hasOrderedMemoryRef()))
1472 for (MachineLoop *L =
Loop;
L !=
nullptr;
L =
L->getParentLoop())
1473 AllowedToHoistLoads[
L] =
false;
1483MachineLICMImpl::LookForDuplicate(
const MachineInstr *
MI,
1484 std::vector<MachineInstr *> &PrevMIs) {
1485 for (MachineInstr *PrevMI : PrevMIs)
1486 if (
TII->produceSameValue(*
MI, *PrevMI, (PreRegAlloc ?
MRI :
nullptr)))
1496bool MachineLICMImpl::EliminateCSE(
1498 DenseMap<
unsigned, std::vector<MachineInstr *>>::iterator &CI) {
1501 if (
MI->isImplicitDef())
1506 if (
MI->mayLoad() && !
MI->isDereferenceableInvariantLoad())
1509 if (MachineInstr *Dup = LookForDuplicate(
MI, CI->second)) {
1514 SmallVector<unsigned, 2> Defs;
1515 for (
unsigned i = 0, e =
MI->getNumOperands(); i != e; ++i) {
1516 const MachineOperand &MO =
MI->getOperand(i);
1520 MO.
getReg() == Dup->getOperand(i).getReg()) &&
1521 "Instructions with different phys regs are not identical!");
1528 for (
unsigned i = 0, e = Defs.
size(); i != e; ++i) {
1529 unsigned Idx = Defs[i];
1531 Register DupReg = Dup->getOperand(Idx).getReg();
1536 for (
unsigned j = 0;
j != i; ++
j)
1542 for (
unsigned Idx : Defs) {
1544 Register DupReg = Dup->getOperand(Idx).getReg();
1548 Dup->getOperand(Idx).setIsDead(
false);
1551 MI->eraseFromParent();
1560bool MachineLICMImpl::MayCSE(MachineInstr *
MI) {
1561 if (
MI->mayLoad() && !
MI->isDereferenceableInvariantLoad())
1564 unsigned Opcode =
MI->getOpcode();
1565 for (
auto &Map : CSEMap) {
1568 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
1569 Map.second.find(Opcode);
1572 if (CI ==
Map.second.end() ||
MI->isImplicitDef())
1574 if (LookForDuplicate(
MI, CI->second) !=
nullptr)
1585unsigned MachineLICMImpl::Hoist(MachineInstr *
MI, MachineBasicBlock *Preheader,
1586 MachineLoop *CurLoop) {
1587 MachineBasicBlock *SrcBlock =
MI->getParent();
1592 isTgtHotterThanSrc(SrcBlock, Preheader)) {
1593 ++NumNotHoistedDueToHotness;
1594 return HoistResult::NotHoisted;
1597 bool HasExtractHoistableLoad =
false;
1598 if (!IsLoopInvariantInst(*
MI, CurLoop) ||
1599 !IsProfitableToHoist(*
MI, CurLoop)) {
1601 MI = ExtractHoistableLoad(
MI, CurLoop);
1603 return HoistResult::NotHoisted;
1604 HasExtractHoistableLoad =
true;
1615 dbgs() <<
"Hoisting " << *
MI;
1616 if (
MI->getParent()->getBasicBlock())
1626 InitCSEMap(Preheader);
1627 FirstInLoop =
false;
1631 unsigned Opcode =
MI->getOpcode();
1632 bool HasCSEDone =
false;
1633 for (
auto &Map : CSEMap) {
1636 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
1637 Map.second.find(Opcode);
1638 if (CI !=
Map.second.end()) {
1639 if (EliminateCSE(
MI, CI)) {
1654 assert(!
MI->isDebugInstr() &&
"Should not hoist debug inst");
1658 UpdateBackTraceRegPressure(
MI);
1660 CSEMap[Preheader][Opcode].push_back(
MI);
1666 if (HasCSEDone || HasExtractHoistableLoad)
1667 return HoistResult::Hoisted | HoistResult::ErasedMI;
1668 return HoistResult::Hoisted;
1672MachineBasicBlock *MachineLICMImpl::getOrCreatePreheader(MachineLoop *CurLoop) {
1681 MachineBasicBlock *NewPreheader =
Pred->SplitCriticalEdge(
1682 CurLoop->
getHeader(), {nullptr, nullptr, MLI}, MDTU);
1685 return NewPreheader;
1693bool MachineLICMImpl::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
1694 MachineBasicBlock *TgtBlock) {
1703 double Ratio = (double)DstBF / SrcBF;
1706 return Ratio > Opts.machine_licm_block_freq_ratio_threshold;
1709template <
typename DerivedT,
bool PreRegAlloc>