1//===- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs loop invariant code motion on machine instructions. We
10// attempt to remove as much code from the body of a loop as possible.
11//
12// This pass is not intended to be a replacement or a complete alternative
13// for the LLVM-IR-level LICM pass. It is only designed to hoist simple
14// constructs that are not exposed before lowering and instruction selection.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/MachineLICM.h"
19#include "CodeGenOptions.h"
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/Analysis/AliasAnalysis.h"
26#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
27#include "llvm/CodeGen/MachineBasicBlock.h"
28#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
29#include "llvm/CodeGen/MachineDomTreeUpdater.h"
30#include "llvm/CodeGen/MachineDominators.h"
31#include "llvm/CodeGen/MachineFrameInfo.h"
32#include "llvm/CodeGen/MachineFunction.h"
33#include "llvm/CodeGen/MachineFunctionPass.h"
34#include "llvm/CodeGen/MachineInstr.h"
35#include "llvm/CodeGen/MachineLoopInfo.h"
36#include "llvm/CodeGen/MachineMemOperand.h"
37#include "llvm/CodeGen/MachineOperand.h"
38#include "llvm/CodeGen/MachineRegisterInfo.h"
39#include "llvm/CodeGen/PseudoSourceValue.h"
40#include "llvm/CodeGen/RegisterClassInfo.h"
41#include "llvm/CodeGen/TargetInstrInfo.h"
42#include "llvm/CodeGen/TargetLowering.h"
43#include "llvm/CodeGen/TargetRegisterInfo.h"
44#include "llvm/CodeGen/TargetSchedule.h"
45#include "llvm/CodeGen/TargetSubtargetInfo.h"
46#include "llvm/IR/DebugLoc.h"
47#include "llvm/IR/Module.h"
48#include "llvm/InitializePasses.h"
49#include "llvm/MC/MCInstrDesc.h"
50#include "llvm/MC/MCRegister.h"
51#include "llvm/Pass.h"
52#include "llvm/Support/Casting.h"
53#include "llvm/Support/CommandLine.h"
54#include "llvm/Support/Debug.h"
55#include "llvm/Support/raw_ostream.h"
56#include "llvm/Target/TargetMachine.h"
57#include <cassert>
58#include <limits>
59#include <vector>
60
61using namespace llvm;
62
63#define DEBUG_TYPE "machinelicm"
64
65enum class UseBFI { None, PGO, All };
66
67static cl::opt<UseBFI>
68DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks",
69 cl::desc("Disable hoisting instructions to"
70 " hotter blocks"),
71 cl::init(Val: UseBFI::PGO), cl::Hidden,
72 cl::values(clEnumValN(UseBFI::None, "none",
73 "disable the feature"),
74 clEnumValN(UseBFI::PGO, "pgo",
75 "enable the feature when using profile data"),
76 clEnumValN(UseBFI::All, "all",
77 "enable the feature with/wo profile data")));
78
79STATISTIC(NumHoisted,
80 "Number of machine instructions hoisted out of loops");
81STATISTIC(NumLowRP,
82 "Number of instructions hoisted in low reg pressure situation");
83STATISTIC(NumHighLatency,
84 "Number of high latency instructions hoisted");
85STATISTIC(NumCSEed,
86 "Number of hoisted machine instructions CSEed");
87STATISTIC(NumPostRAHoisted,
88 "Number of machine instructions hoisted out of loops post regalloc");
89STATISTIC(NumStoreConst,
90 "Number of stores of const phys reg hoisted out of loops");
91STATISTIC(NumNotHoistedDueToHotness,
92 "Number of instructions not hoisted due to block frequency");
93
94namespace {
95 enum HoistResult { NotHoisted = 1, Hoisted = 2, ErasedMI = 4 };
96
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;
108 Pass *LegacyPass;
109 MachineFunctionAnalysisManager *MFAM;
110
111 // Various analyses that we use...
112 AliasAnalysis *AA = nullptr; // Alias analysis info.
113 MachineBlockFrequencyInfo *MBFI = nullptr; // Machine block frequncy info
114 MachineLoopInfo *MLI = nullptr; // Current MachineLoopInfo
115 MachineDomTreeUpdater *MDTU = nullptr; // Wraps current dominator tree
116
117 // State that is updated as we process loops
118 bool Changed = false; // True if a loop is changed.
119 bool FirstInLoop = false; // True if it's the first LICM in the loop.
120
121 // Holds information about whether it is allowed to move load instructions
122 // out of the loop
123 SmallDenseMap<MachineLoop *, bool> AllowedToHoistLoads;
124
125 // Exit blocks of each Loop.
126 DenseMap<MachineLoop *, SmallVector<MachineBasicBlock *, 8>> ExitBlockMap;
127
128 bool isExitBlock(MachineLoop *CurLoop, const MachineBasicBlock *MBB) {
129 auto [It, Inserted] = ExitBlockMap.try_emplace(Key: CurLoop);
130 if (Inserted) {
131 SmallVector<MachineBasicBlock *, 8> ExitBlocks;
132 CurLoop->getExitBlocks(ExitBlocks);
133 It->second = std::move(ExitBlocks);
134 }
135 return is_contained(Range&: It->second, Element: MBB);
136 }
137
138 // Track 'estimated' register pressure.
139 SmallDenseSet<Register> RegSeen;
140 SmallVector<unsigned, 8> RegPressure;
141
142 // Register pressure "limit" per register pressure set. If the pressure
143 // is higher than the limit, then it's considered high.
144 SmallVector<unsigned, 8> RegLimit;
145
146 // Register pressure on path leading from loop preheader to current BB.
147 SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;
148
149 // For each opcode per preheader, keep a list of potential CSE instructions.
150 DenseMap<MachineBasicBlock *,
151 DenseMap<unsigned, std::vector<MachineInstr *>>>
152 CSEMap;
153
154 // If a MBB does not dominate loop exiting blocks then it may not safe
155 // to hoist loads from this block. Cached per loop for the current block,
156 // which is checked against both the outermost loop and its subloops.
157 SmallDenseMap<MachineLoop *, bool> GuaranteedToExecute;
158
159 public:
160 MachineLICMImpl(const CodeGenOptions &Opts, bool PreRegAlloc,
161 Pass *LegacyPass, MachineFunctionAnalysisManager *MFAM)
162 : Opts(Opts), PreRegAlloc(PreRegAlloc), LegacyPass(LegacyPass),
163 MFAM(MFAM) {
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");
167 }
168
169 bool run(MachineFunction &MF);
170
171 void releaseMemory() {
172 RegSeen.clear();
173 RegPressure.clear();
174 RegLimit.clear();
175 BackTrace.clear();
176 CSEMap.clear();
177 ExitBlockMap.clear();
178 }
179
180 private:
181 /// Keep track of information about hoisting candidates.
182 struct CandidateInfo {
183 MachineInstr *MI;
184 Register Def;
185 int FI;
186
187 CandidateInfo(MachineInstr *mi, Register def, int fi)
188 : MI(mi), Def(def), FI(fi) {}
189 };
190
191 void HoistRegionPostRA(MachineLoop *CurLoop);
192
193 void HoistPostRA(MachineInstr *MI, Register Def, MachineLoop *CurLoop);
194
195 void ProcessMI(MachineInstr *MI, BitVector &RUDefs, BitVector &RUClobbers,
196 SmallDenseSet<int> &StoredFIs,
197 SmallVectorImpl<CandidateInfo> &Candidates,
198 MachineLoop *CurLoop);
199
200 void AddToLiveIns(MCRegister Reg, MachineLoop *CurLoop);
201
202 bool IsLICMCandidate(MachineInstr &I, MachineLoop *CurLoop);
203
204 bool IsLoopInvariantInst(MachineInstr &I, MachineLoop *CurLoop);
205
206 bool HasLoopPHIUse(const MachineInstr *MI, MachineLoop *CurLoop);
207
208 bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, Register Reg,
209 MachineLoop *CurLoop) const;
210
211 bool IsCheapInstruction(MachineInstr &MI) const;
212
213 bool CanCauseHighRegPressure(const SmallDenseMap<unsigned, int> &Cost,
214 bool Cheap);
215
216 void UpdateBackTraceRegPressure(const MachineInstr *MI);
217
218 bool IsProfitableToHoist(MachineInstr &MI, MachineLoop *CurLoop);
219
220 bool IsGuaranteedToExecute(MachineBasicBlock *BB, MachineLoop *CurLoop);
221
222 void EnterScope(MachineBasicBlock *MBB);
223
224 void ExitScope(MachineBasicBlock *MBB);
225
226 void ExitScopeIfDone(
227 MachineDomTreeNode *Node,
228 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
229 const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap);
230
231 void HoistOutOfLoop(MachineDomTreeNode *HeaderN, MachineLoop *CurLoop);
232
233 void InitRegPressure(MachineBasicBlock *BB);
234
235 SmallDenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
236 bool ConsiderSeen,
237 bool ConsiderUnseenAsDef);
238
239 void UpdateRegPressure(const MachineInstr *MI,
240 bool ConsiderUnseenAsDef = false);
241
242 MachineInstr *ExtractHoistableLoad(MachineInstr *MI, MachineLoop *CurLoop);
243
244 MachineInstr *LookForDuplicate(const MachineInstr *MI,
245 std::vector<MachineInstr *> &PrevMIs);
246
247 bool
248 EliminateCSE(MachineInstr *MI,
249 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI);
250
251 bool MayCSE(MachineInstr *MI);
252
253 unsigned Hoist(MachineInstr *MI, MachineBasicBlock *Preheader,
254 MachineLoop *CurLoop);
255
256 void InitCSEMap(MachineBasicBlock *BB);
257
258 void InitializeLoadsHoistableLoops();
259
260 bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
261 MachineBasicBlock *TgtBlock);
262 MachineBasicBlock *getOrCreatePreheader(MachineLoop *CurLoop);
263 };
264
265 class MachineLICMBase : public MachineFunctionPass {
266 bool PreRegAlloc;
267
268 public:
269 MachineLICMBase(char &ID, bool PreRegAlloc)
270 : MachineFunctionPass(ID), PreRegAlloc(PreRegAlloc) {}
271
272 bool runOnMachineFunction(MachineFunction &MF) override;
273
274 void getAnalysisUsage(AnalysisUsage &AU) const override {
275 AU.addRequired<MachineLoopInfoWrapperPass>();
276 if (DisableHoistingToHotterBlocks != UseBFI::None)
277 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
278 AU.addRequired<MachineDominatorTreeWrapperPass>();
279 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
280 AU.addRequired<AAResultsWrapperPass>();
281 AU.addPreserved<MachineLoopInfoWrapperPass>();
282 AU.addPreserved<MachineDominatorTreeWrapperPass>();
283 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
284 MachineFunctionPass::getAnalysisUsage(AU);
285 }
286 };
287
288 class MachineLICM : public MachineLICMBase {
289 public:
290 static char ID;
291 MachineLICM() : MachineLICMBase(ID, false) {}
292 };
293
294 class EarlyMachineLICM : public MachineLICMBase {
295 public:
296 static char ID;
297 EarlyMachineLICM() : MachineLICMBase(ID, true) {}
298 };
299
300} // end anonymous namespace
301
302char MachineLICM::ID;
303char EarlyMachineLICM::ID;
304
305char &llvm::MachineLICMID = MachineLICM::ID;
306char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;
307
308INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
309 "Machine Loop Invariant Code Motion", false, false)
310INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
311INITIALIZE_PASS_DEPENDENCY(LazyMachineBlockFrequencyInfoPass)
312INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
313INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
314INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
315INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
316 "Machine Loop Invariant Code Motion", false, false)
317
318INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
319 "Early Machine Loop Invariant Code Motion", false, false)
320INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
321INITIALIZE_PASS_DEPENDENCY(LazyMachineBlockFrequencyInfoPass)
322INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
323INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
324INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
325INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
326 "Early Machine Loop Invariant Code Motion", false, false)
327
328bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
329 if (skipFunction(F: MF.getFunction()))
330 return false;
331
332 MachineLICMImpl Impl(getCodeGenOptions(MF), PreRegAlloc, this, nullptr);
333 return Impl.run(MF);
334}
335
336#define GET_RESULT(RESULT, GETTER, INFIX) \
337 ((LegacyPass) \
338 ? &LegacyPass->getAnalysis<RESULT##INFIX##WrapperPass>().GETTER() \
339 : &MFAM->getResult<RESULT##Analysis>(MF))
340
341bool MachineLICMImpl::run(MachineFunction &MF) {
342 AA = MFAM != nullptr
343 ? &MFAM->getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
344 .getManager()
345 .getResult<AAManager>(IR&: MF.getFunction())
346 : &LegacyPass->getAnalysis<AAResultsWrapperPass>().getAAResults();
347
348 RegClassInfo =
349 MFAM != nullptr
350 ? &MFAM->getResult<MachineRegisterClassAnalysis>(IR&: MF)
351 : &LegacyPass->getAnalysis<MachineRegisterClassInfoWrapperPass>()
352 .getRCI();
353
354 MachineDomTreeUpdater DTU(GET_RESULT(MachineDominatorTree, getDomTree, ),
355 MachineDomTreeUpdater::UpdateStrategy::Lazy);
356 MDTU = &DTU;
357 MLI = GET_RESULT(MachineLoop, getLI, Info);
358
359 Changed = FirstInLoop = false;
360 const TargetSubtargetInfo &ST = MF.getSubtarget();
361 TII = ST.getInstrInfo();
362 TLI = ST.getTargetLowering();
363 TRI = ST.getRegisterInfo();
364 MFI = &MF.getFrameInfo();
365 MRI = &MF.getRegInfo();
366 SchedModel.init(TSInfo: &ST);
367
368 HasProfileData = MF.getFunction().hasProfileData();
369
370 if (DisableHoistingToHotterBlocks == UseBFI::All ||
371 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData))
372 MBFI = LegacyPass
373 ? &LegacyPass->getAnalysis<LazyMachineBlockFrequencyInfoPass>()
374 .getBFI()
375 : &MFAM->getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
376
377 if (PreRegAlloc)
378 LLVM_DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: ");
379 else
380 LLVM_DEBUG(dbgs() << "******** Post-regalloc Machine LICM: ");
381 LLVM_DEBUG(dbgs() << MF.getName() << " ********\n");
382
383 if (PreRegAlloc) {
384 // Estimate register pressure during pre-regalloc pass.
385 unsigned NumRPS = TRI->getNumRegPressureSets();
386 RegPressure.resize(N: NumRPS);
387 llvm::fill(Range&: RegPressure, Value: 0);
388 RegLimit.resize(N: NumRPS);
389 for (unsigned i = 0, e = NumRPS; i != e; ++i)
390 RegLimit[i] = RegClassInfo->getRegPressureSetLimit(Idx: i);
391 }
392
393 if (Opts.machine_licm_hoist_const_loads)
394 InitializeLoadsHoistableLoops();
395
396 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
397 while (!Worklist.empty()) {
398 MachineLoop *CurLoop = Worklist.pop_back_val();
399
400 if (!PreRegAlloc) {
401 HoistRegionPostRA(CurLoop);
402 } else {
403 // CSEMap is initialized for loop header when the first instruction is
404 // being hoisted.
405 MachineDomTreeNode *N = MDTU->getDomTree().getNode(BB: CurLoop->getHeader());
406 FirstInLoop = true;
407 HoistOutOfLoop(HeaderN: N, CurLoop);
408 CSEMap.clear();
409 }
410 }
411 releaseMemory();
412 return Changed;
413}
414
415/// Return true if instruction stores to the specified frame.
416static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
417 // Check mayStore before memory operands so that e.g. DBG_VALUEs will return
418 // true since they have no memory operands.
419 if (!MI->mayStore())
420 return false;
421 // If we lost memory operands, conservatively assume that the instruction
422 // writes to all slots.
423 if (MI->memoperands_empty())
424 return true;
425 for (const MachineMemOperand *MemOp : MI->memoperands()) {
426 if (!MemOp->isStore() || !MemOp->getPseudoValue())
427 continue;
428 if (const FixedStackPseudoSourceValue *Value =
429 dyn_cast<FixedStackPseudoSourceValue>(Val: MemOp->getPseudoValue())) {
430 if (Value->getFrameIndex() == FI)
431 return true;
432 }
433 }
434 return false;
435}
436
437static void applyBitsNotInRegMaskToRegUnitsMask(const TargetRegisterInfo &TRI,
438 BitVector &RUs,
439 const uint32_t *Mask) {
440 // FIXME: This intentionally works in reverse due to some issues with the
441 // Register Units infrastructure.
442 //
443 // This is used to apply callee-saved-register masks to the clobbered regunits
444 // mask.
445 //
446 // The right way to approach this is to start with a BitVector full of ones,
447 // then reset all the bits of the regunits of each register that is set in the
448 // mask (registers preserved), then OR the resulting bits with the Clobbers
449 // mask. This correctly prioritizes the saved registers, so if a RU is shared
450 // between a register that is preserved, and one that is NOT preserved, that
451 // RU will not be set in the output vector (the clobbers).
452 //
453 // What we have to do for now is the opposite: we have to assume that the
454 // regunits of all registers that are NOT preserved are clobbered, even if
455 // those regunits are preserved by another register. So if a RU is shared
456 // like described previously, that RU will be set.
457 //
458 // This is to work around an issue which appears in AArch64, but isn't
459 // exclusive to that target: AArch64's Qn registers (128 bits) have Dn
460 // register (lower 64 bits). A few Dn registers are preserved by some calling
461 // conventions, but Qn and Dn share exactly the same reg units.
462 //
463 // If we do this the right way, Qn will be marked as NOT clobbered even though
464 // its upper 64 bits are NOT preserved. The conservative approach handles this
465 // correctly at the cost of some missed optimizations on other targets.
466 //
467 // This is caused by how RegUnits are handled within TableGen. Ideally, Qn
468 // should have an extra RegUnit to model the "unknown" bits not covered by the
469 // subregs.
470 BitVector RUsFromRegsNotInMask(TRI.getNumRegUnits());
471 const unsigned NumRegs = TRI.getNumRegs();
472 const unsigned MaskWords = (NumRegs + 31) / 32;
473 for (unsigned K = 0; K < MaskWords; ++K) {
474 const uint32_t Word = Mask[K];
475 for (unsigned Bit = 0; Bit < 32; ++Bit) {
476 const unsigned PhysReg = (K * 32) + Bit;
477 if (PhysReg == NumRegs)
478 break;
479
480 if (PhysReg && !((Word >> Bit) & 1)) {
481 for (MCRegUnit Unit : TRI.regunits(Reg: PhysReg))
482 RUsFromRegsNotInMask.set(static_cast<unsigned>(Unit));
483 }
484 }
485 }
486
487 RUs |= RUsFromRegsNotInMask;
488}
489
490/// Examine the instruction for potential LICM candidate. Also
491/// gather register def and frame object update information.
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;
499 Register Def;
500 for (const MachineOperand &MO : MI->operands()) {
501 if (MO.isFI()) {
502 // Remember if the instruction stores to the frame index.
503 int FI = MO.getIndex();
504 if (!StoredFIs.count(V: FI) &&
505 MFI->isSpillSlotObjectIndex(ObjectIdx: FI) &&
506 InstructionStoresToFI(MI, FI))
507 StoredFIs.insert(V: FI);
508 HasNonInvariantUse = true;
509 continue;
510 }
511
512 // We can't hoist an instruction defining a physreg that is clobbered in
513 // the loop.
514 if (MO.isRegMask()) {
515 applyBitsNotInRegMaskToRegUnitsMask(TRI: *TRI, RUs&: RUClobbers, Mask: MO.getRegMask());
516 continue;
517 }
518
519 if (!MO.isReg())
520 continue;
521 Register Reg = MO.getReg();
522 if (!Reg)
523 continue;
524 assert(Reg.isPhysical() && "Not expecting virtual register!");
525
526 if (!MO.isDef()) {
527 if (!HasNonInvariantUse) {
528 for (MCRegUnit Unit : TRI->regunits(Reg)) {
529 // If it's using a non-loop-invariant register, then it's obviously
530 // not safe to hoist.
531 if (RUDefs.test(Idx: static_cast<unsigned>(Unit)) ||
532 RUClobbers.test(Idx: static_cast<unsigned>(Unit))) {
533 HasNonInvariantUse = true;
534 break;
535 }
536 }
537 }
538 continue;
539 }
540
541 // FIXME: For now, avoid instructions with multiple defs, unless it's dead.
542 if (!MO.isDead()) {
543 if (Def)
544 RuledOut = true;
545 else
546 Def = Reg;
547 }
548
549 // If we have already seen another instruction that defines the same
550 // register, then this is not safe. Two defs is indicated by setting a
551 // PhysRegClobbers bit.
552 for (MCRegUnit Unit : TRI->regunits(Reg)) {
553 if (RUDefs.test(Idx: static_cast<unsigned>(Unit))) {
554 RUClobbers.set(static_cast<unsigned>(Unit));
555 RuledOut = true;
556 } else if (RUClobbers.test(Idx: static_cast<unsigned>(Unit))) {
557 // MI defined register is seen defined by another instruction in
558 // the loop, it cannot be a LICM candidate.
559 RuledOut = true;
560 }
561
562 RUDefs.set(static_cast<unsigned>(Unit));
563 }
564 }
565
566 // Only consider reloads for now and remats which do not have register
567 // operands. FIXME: Consider unfold load folding instructions.
568 if (Def && !RuledOut) {
569 int FI = std::numeric_limits<int>::min();
570 if ((!HasNonInvariantUse && IsLICMCandidate(I&: *MI, CurLoop)) ||
571 (TII->isLoadFromStackSlot(MI: *MI, FrameIndex&: FI) && MFI->isSpillSlotObjectIndex(ObjectIdx: FI)))
572 Candidates.push_back(Elt: CandidateInfo(MI, Def, FI));
573 }
574}
575
576/// Walk the specified region of the CFG and hoist loop invariants out to the
577/// preheader.
578void MachineLICMImpl::HoistRegionPostRA(MachineLoop *CurLoop) {
579 MachineBasicBlock *Preheader = getOrCreatePreheader(CurLoop);
580 if (!Preheader)
581 return;
582
583 unsigned NumRegUnits = TRI->getNumRegUnits();
584 BitVector RUDefs(NumRegUnits); // RUs defined once in the loop.
585 BitVector RUClobbers(NumRegUnits); // RUs defined more than once.
586
587 SmallVector<CandidateInfo, 32> Candidates;
588 SmallDenseSet<int> StoredFIs;
589
590 // Walk the entire region, count number of defs for each register, and
591 // collect potential LICM candidates.
592 for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
593 // If the header of the loop containing this basic block is a landing pad,
594 // then don't try to hoist instructions out of this loop.
595 const MachineLoop *ML = MLI->getLoopFor(BB);
596 if (ML && ML->getHeader()->isEHPad()) continue;
597
598 // Conservatively treat live-in's as an external def.
599 // FIXME: That means a reload that're reused in successor block(s) will not
600 // be LICM'ed.
601 for (const auto &LI : BB->liveins()) {
602 for (MCRegUnit Unit : TRI->regunits(Reg: LI.PhysReg))
603 RUDefs.set(static_cast<unsigned>(Unit));
604 }
605
606 // Funclet entry blocks will clobber all registers
607 if (const uint32_t *Mask = BB->getBeginClobberMask(TRI))
608 applyBitsNotInRegMaskToRegUnitsMask(TRI: *TRI, RUs&: RUClobbers, Mask);
609
610 // EH landing pads clobber exception pointer/selector registers.
611 if (BB->isEHPad()) {
612 const MachineFunction &MF = *BB->getParent();
613 const Constant *PersonalityFn = MF.getFunction().getPersonalityFn();
614 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
615 ExceptionHandling EH = MF.getFunction().getParent()->getExceptionModel();
616 if (MCRegister Reg = TLI.getExceptionPointerRegister(EH, PersonalityFn))
617 for (MCRegUnit Unit : TRI->regunits(Reg))
618 RUClobbers.set(static_cast<unsigned>(Unit));
619 if (MCRegister Reg = TLI.getExceptionSelectorRegister(EH, PersonalityFn))
620 for (MCRegUnit Unit : TRI->regunits(Reg))
621 RUClobbers.set(static_cast<unsigned>(Unit));
622 }
623
624 GuaranteedToExecute.clear();
625 for (MachineInstr &MI : *BB)
626 ProcessMI(MI: &MI, RUDefs, RUClobbers, StoredFIs, Candidates, CurLoop);
627 }
628
629 // Gather the registers read / clobbered by the terminator.
630 BitVector TermRUs(NumRegUnits);
631 MachineBasicBlock::iterator TI = Preheader->getFirstTerminator();
632 if (TI != Preheader->end()) {
633 for (const MachineOperand &MO : TI->operands()) {
634 if (!MO.isReg())
635 continue;
636 Register Reg = MO.getReg();
637 if (!Reg)
638 continue;
639 for (MCRegUnit Unit : TRI->regunits(Reg))
640 TermRUs.set(static_cast<unsigned>(Unit));
641 }
642 }
643
644 // Now evaluate whether the potential candidates qualify.
645 // 1. Check if the candidate defined register is defined by another
646 // instruction in the loop.
647 // 2. If the candidate is a load from stack slot (always true for now),
648 // check if the slot is stored anywhere in the loop.
649 // 3. Make sure candidate def should not clobber
650 // registers read by the terminator. Similarly its def should not be
651 // clobbered by the terminator.
652 for (CandidateInfo &Candidate : Candidates) {
653 if (Candidate.FI != std::numeric_limits<int>::min() &&
654 StoredFIs.count(V: Candidate.FI))
655 continue;
656
657 Register Def = Candidate.Def;
658 bool Safe = true;
659 for (MCRegUnit Unit : TRI->regunits(Reg: Def)) {
660 if (RUClobbers.test(Idx: static_cast<unsigned>(Unit)) ||
661 TermRUs.test(Idx: static_cast<unsigned>(Unit))) {
662 Safe = false;
663 break;
664 }
665 }
666
667 if (!Safe)
668 continue;
669
670 MachineInstr *MI = Candidate.MI;
671 for (const MachineOperand &MO : MI->all_uses()) {
672 if (!MO.getReg())
673 continue;
674 for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg())) {
675 if (RUDefs.test(Idx: static_cast<unsigned>(Unit)) ||
676 RUClobbers.test(Idx: static_cast<unsigned>(Unit))) {
677 // If it's using a non-loop-invariant register, then it's obviously
678 // not safe to hoist.
679 Safe = false;
680 break;
681 }
682 }
683
684 if (!Safe)
685 break;
686 }
687
688 if (Safe)
689 HoistPostRA(MI, Def: Candidate.Def, CurLoop);
690 }
691}
692
693/// Add register 'Reg' to the livein sets of BBs in the current loop, and make
694/// sure it is not killed by any instructions in the loop.
695void MachineLICMImpl::AddToLiveIns(MCRegister Reg, MachineLoop *CurLoop) {
696 for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
697 if (!BB->isLiveIn(Reg))
698 BB->addLiveIn(PhysReg: Reg);
699 for (MachineInstr &MI : *BB) {
700 for (MachineOperand &MO : MI.all_uses()) {
701 if (!MO.getReg())
702 continue;
703 if (TRI->regsOverlap(RegA: Reg, RegB: MO.getReg()))
704 MO.setIsKill(false);
705 }
706 }
707 }
708}
709
710/// When an instruction is found to only use loop invariant operands that is
711/// safe to hoist, this instruction is called to do the dirty work.
712void MachineLICMImpl::HoistPostRA(MachineInstr *MI, Register Def,
713 MachineLoop *CurLoop) {
714 MachineBasicBlock *Preheader = CurLoop->getLoopPreheader();
715
716 // Now move the instructions to the predecessor, inserting it before any
717 // terminator instructions.
718 LLVM_DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader)
719 << " from " << printMBBReference(*MI->getParent()) << ": "
720 << *MI);
721
722 // Splice the instruction to the preheader.
723 MachineBasicBlock *MBB = MI->getParent();
724 Preheader->splice(Where: Preheader->getFirstTerminator(), Other: MBB, From: MI);
725
726 // Since we are moving the instruction out of its basic block, we do not
727 // retain its debug location. Doing so would degrade the debugging
728 // experience and adversely affect the accuracy of profiling information.
729 assert(!MI->isDebugInstr() && "Should not hoist debug inst");
730 MI->setDebugLoc(DebugLoc());
731
732 // Add register to livein list to all the BBs in the current loop since a
733 // loop invariant must be kept live throughout the whole loop. This is
734 // important to ensure later passes do not scavenge the def register.
735 AddToLiveIns(Reg: Def, CurLoop);
736
737 ++NumPostRAHoisted;
738 Changed = true;
739}
740
741/// Check if this mbb is guaranteed to execute. If not then a load from this mbb
742/// may not be safe to hoist.
743bool MachineLICMImpl::IsGuaranteedToExecute(MachineBasicBlock *BB,
744 MachineLoop *CurLoop) {
745 auto [It, Inserted] = GuaranteedToExecute.try_emplace(Key: CurLoop, Args: true);
746 if (!Inserted)
747 return It->second;
748
749 if (BB != CurLoop->getHeader()) {
750 // Check loop exiting blocks.
751 SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
752 CurLoop->getExitingBlocks(ExitingBlocks&: CurrentLoopExitingBlocks);
753 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
754 if (!MDTU->getDomTree().dominates(A: BB, B: CurrentLoopExitingBlock)) {
755 It->second = false;
756 return false;
757 }
758 }
759
760 return true;
761}
762
763void MachineLICMImpl::EnterScope(MachineBasicBlock *MBB) {
764 LLVM_DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');
765
766 // Remember livein register pressure.
767 BackTrace.push_back(Elt: RegPressure);
768}
769
770void MachineLICMImpl::ExitScope(MachineBasicBlock *MBB) {
771 LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
772 BackTrace.pop_back();
773}
774
775/// Destroy scope for the MBB that corresponds to the given dominator tree node
776/// if its a leaf or all of its children are done. Walk up the dominator tree to
777/// destroy ancestors which are now done.
778void MachineLICMImpl::ExitScopeIfDone(
779 MachineDomTreeNode *Node,
780 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
781 const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap) {
782 if (OpenChildren[Node])
783 return;
784
785 for(;;) {
786 ExitScope(MBB: Node->getBlock());
787 // Now traverse upwards to pop ancestors whose offsprings are all done.
788 MachineDomTreeNode *Parent = ParentMap.lookup(Val: Node);
789 if (!Parent || --OpenChildren[Parent] != 0)
790 break;
791 Node = Parent;
792 }
793}
794
795/// Walk the specified loop in the CFG (defined by all blocks dominated by the
796/// specified header block, and that are in the current loop) in depth first
797/// order w.r.t the DominatorTree. This allows us to visit definitions before
798/// uses, allowing us to hoist a loop body in one pass without iteration.
799void MachineLICMImpl::HoistOutOfLoop(MachineDomTreeNode *HeaderN,
800 MachineLoop *CurLoop) {
801 MachineBasicBlock *Preheader = getOrCreatePreheader(CurLoop);
802 if (!Preheader)
803 return;
804
805 SmallVector<MachineDomTreeNode*, 32> Scopes;
806 SmallVector<MachineDomTreeNode*, 8> WorkList;
807 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
808 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
809
810 // Perform a DFS walk to determine the order of visit.
811 WorkList.push_back(Elt: HeaderN);
812 while (!WorkList.empty()) {
813 MachineDomTreeNode *Node = WorkList.pop_back_val();
814 assert(Node && "Null dominator tree node?");
815 MachineBasicBlock *BB = Node->getBlock();
816
817 // If the header of the loop containing this basic block is a landing pad,
818 // then don't try to hoist instructions out of this loop.
819 const MachineLoop *ML = MLI->getLoopFor(BB);
820 if (ML && ML->getHeader()->isEHPad())
821 continue;
822
823 // If this subregion is not in the top level loop at all, exit.
824 if (!CurLoop->contains(BB))
825 continue;
826
827 Scopes.push_back(Elt: Node);
828
829 // Don't hoist things out of a large switch statement. This often causes
830 // code to be hoisted that wasn't going to be executed, and increases
831 // register pressure in a situation where it's likely to matter.
832 if (BB->succ_size() >= 25) {
833 OpenChildren[Node] = 0;
834 continue;
835 }
836
837 // Add children in reverse order as then the next popped worklist node is
838 // the first child of this node. This means we ultimately traverse the
839 // DOM tree in exactly the same order as if we'd recursed.
840 size_t WorkListStart = WorkList.size();
841 for (MachineDomTreeNode *Child : Node->children()) {
842 ParentMap[Child] = Node;
843 WorkList.push_back(Elt: Child);
844 }
845 std::reverse(first: WorkList.begin() + WorkListStart, last: WorkList.end());
846 OpenChildren[Node] = WorkList.size() - WorkListStart;
847 }
848
849 if (Scopes.size() == 0)
850 return;
851
852 // Compute registers which are livein into the loop headers.
853 RegSeen.clear();
854 BackTrace.clear();
855 InitRegPressure(BB: Preheader);
856
857 // Now perform LICM.
858 for (MachineDomTreeNode *Node : Scopes) {
859 MachineBasicBlock *MBB = Node->getBlock();
860
861 EnterScope(MBB);
862
863 // Process the block
864 GuaranteedToExecute.clear();
865 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *MBB)) {
866 unsigned HoistRes = HoistResult::NotHoisted;
867 HoistRes = Hoist(MI: &MI, Preheader, CurLoop);
868 if (HoistRes & HoistResult::NotHoisted) {
869 // We have failed to hoist MI to outermost loop's preheader. If MI is in
870 // a subloop, try to hoist it to subloop's preheader.
871 SmallVector<MachineLoop *> InnerLoopWorkList;
872 for (MachineLoop *L = MLI->getLoopFor(BB: MI.getParent()); L != CurLoop;
873 L = L->getParentLoop())
874 InnerLoopWorkList.push_back(Elt: L);
875
876 while (!InnerLoopWorkList.empty()) {
877 MachineLoop *InnerLoop = InnerLoopWorkList.pop_back_val();
878 MachineBasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
879 if (InnerLoopPreheader) {
880 HoistRes = Hoist(MI: &MI, Preheader: InnerLoopPreheader, CurLoop: InnerLoop);
881 if (HoistRes & HoistResult::Hoisted)
882 break;
883 }
884 }
885 }
886
887 if (HoistRes & HoistResult::ErasedMI)
888 continue;
889
890 UpdateRegPressure(MI: &MI);
891 }
892
893 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
894 ExitScopeIfDone(Node, OpenChildren, ParentMap);
895 }
896}
897
898/// Find all virtual register references that are liveout of the preheader to
899/// initialize the starting "register pressure". Note this does not count live
900/// through (livein but not used) registers.
901void MachineLICMImpl::InitRegPressure(MachineBasicBlock *BB) {
902 llvm::fill(Range&: RegPressure, Value: 0);
903
904 // If the preheader has only a single predecessor and it ends with a
905 // fallthrough or an unconditional branch, then scan its predecessor for live
906 // defs as well. This happens whenever the preheader is created by splitting
907 // the critical edge from the loop predecessor to the loop header.
908 if (BB->pred_size() == 1) {
909 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
910 SmallVector<MachineOperand, 4> Cond;
911 if (!TII->analyzeBranch(MBB&: *BB, TBB, FBB, Cond, AllowModify: false) && Cond.empty())
912 InitRegPressure(BB: *BB->pred_begin());
913 }
914
915 for (const MachineInstr &MI : *BB)
916 UpdateRegPressure(MI: &MI, /*ConsiderUnseenAsDef=*/true);
917}
918
919/// Update estimate of register pressure after the specified instruction.
920void MachineLICMImpl::UpdateRegPressure(const MachineInstr *MI,
921 bool ConsiderUnseenAsDef) {
922 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
923 for (const auto &[Class, Weight] : Cost) {
924 if (static_cast<int>(RegPressure[Class]) < -Weight)
925 RegPressure[Class] = 0;
926 else
927 RegPressure[Class] += Weight;
928 }
929}
930
931/// Calculate the additional register pressure that the registers used in MI
932/// cause.
933///
934/// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
935/// figure out which usages are live-ins.
936/// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
937SmallDenseMap<unsigned, int>
938MachineLICMImpl::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
939 bool ConsiderUnseenAsDef) {
940 SmallDenseMap<unsigned, int> Cost;
941 if (MI->isImplicitDef())
942 return Cost;
943 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
944 const MachineOperand &MO = MI->getOperand(i);
945 if (!MO.isReg() || MO.isImplicit())
946 continue;
947 Register Reg = MO.getReg();
948 if (!Reg.isVirtual())
949 continue;
950
951 // FIXME: It seems bad to use RegSeen only for some of these calculations.
952 bool isNew = ConsiderSeen ? RegSeen.insert(V: Reg).second : false;
953 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
954
955 RegClassWeight W = TRI->getRegClassWeight(RC);
956 int RCCost = 0;
957 if (MO.isDef())
958 RCCost = W.RegWeight;
959 else {
960 bool isKill = MRI->hasOneNonDBGUse(RegNo: Reg);
961 if (isNew && !isKill && ConsiderUnseenAsDef)
962 // Haven't seen this, it must be a livein.
963 RCCost = W.RegWeight;
964 else if (!isNew && isKill)
965 RCCost = -W.RegWeight;
966 }
967 if (RCCost == 0)
968 continue;
969 const int *PS = TRI->getRegClassPressureSets(RC);
970 for (; *PS != -1; ++PS)
971 Cost[*PS] += RCCost;
972 }
973 return Cost;
974}
975
976/// Return true if this machine instruction loads from global offset table or
977/// constant pool.
978static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
979 assert(MI.mayLoad() && "Expected MI that loads!");
980
981 // If we lost memory operands, conservatively assume that the instruction
982 // reads from everything..
983 if (MI.memoperands_empty())
984 return true;
985
986 for (MachineMemOperand *MemOp : MI.memoperands())
987 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
988 if (PSV->isGOT() || PSV->isConstantPool())
989 return true;
990
991 return false;
992}
993
994// This function iterates through all the operands of the input store MI and
995// checks that each register operand statisfies isCallerPreservedPhysReg.
996// This means, the value being stored and the address where it is being stored
997// is constant throughout the body of the function (not including prologue and
998// epilogue). When called with an MI that isn't a store, it returns false.
999// A future improvement can be to check if the store registers are constant
1000// throughout the loop rather than throughout the funtion.
1001static bool isInvariantStore(const MachineInstr &MI,
1002 const TargetRegisterInfo *TRI,
1003 const MachineRegisterInfo *MRI) {
1004
1005 bool FoundCallerPresReg = false;
1006 if (!MI.mayStore() || MI.hasUnmodeledSideEffects() ||
1007 (MI.getNumOperands() == 0))
1008 return false;
1009
1010 // Check that all register operands are caller-preserved physical registers.
1011 for (const MachineOperand &MO : MI.operands()) {
1012 if (MO.isReg()) {
1013 Register Reg = MO.getReg();
1014 // If operand is a virtual register, check if it comes from a copy of a
1015 // physical register.
1016 if (Reg.isVirtual())
1017 Reg = TRI->lookThruCopyLike(SrcReg: MO.getReg(), MRI);
1018 if (Reg.isVirtual())
1019 return false;
1020 if (!TRI->isCallerPreservedPhysReg(PhysReg: Reg.asMCReg(), MF: *MI.getMF()))
1021 return false;
1022 else
1023 FoundCallerPresReg = true;
1024 } else if (!MO.isImm()) {
1025 return false;
1026 }
1027 }
1028 return FoundCallerPresReg;
1029}
1030
1031// Return true if the input MI is a copy instruction that feeds an invariant
1032// store instruction. This means that the src of the copy has to satisfy
1033// isCallerPreservedPhysReg and atleast one of it's users should satisfy
1034// isInvariantStore.
1035static bool isCopyFeedingInvariantStore(const MachineInstr &MI,
1036 const MachineRegisterInfo *MRI,
1037 const TargetRegisterInfo *TRI) {
1038
1039 // FIXME: If targets would like to look through instructions that aren't
1040 // pure copies, this can be updated to a query.
1041 if (!MI.isCopy())
1042 return false;
1043
1044 const MachineFunction *MF = MI.getMF();
1045 // Check that we are copying a constant physical register.
1046 Register CopySrcReg = MI.getOperand(i: 1).getReg();
1047 if (CopySrcReg.isVirtual())
1048 return false;
1049
1050 if (!TRI->isCallerPreservedPhysReg(PhysReg: CopySrcReg.asMCReg(), MF: *MF))
1051 return false;
1052
1053 Register CopyDstReg = MI.getOperand(i: 0).getReg();
1054 // Check if any of the uses of the copy are invariant stores.
1055 assert(CopyDstReg.isVirtual() && "copy dst is not a virtual reg");
1056
1057 for (MachineInstr &UseMI : MRI->use_instructions(Reg: CopyDstReg)) {
1058 if (UseMI.mayStore() && isInvariantStore(MI: UseMI, TRI, MRI))
1059 return true;
1060 }
1061 return false;
1062}
1063
1064/// Returns true if the instruction may be a suitable candidate for LICM.
1065/// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
1066bool MachineLICMImpl::IsLICMCandidate(MachineInstr &I, MachineLoop *CurLoop) {
1067 // Check if it's safe to move the instruction.
1068 bool DontMoveAcrossStore =
1069 !Opts.machine_licm_hoist_const_loads || !AllowedToHoistLoads[CurLoop];
1070 if ((!I.isSafeToMove(SawStore&: DontMoveAcrossStore)) &&
1071 !(Opts.machine_licm_hoist_const_stores &&
1072 isInvariantStore(MI: I, TRI, MRI))) {
1073 LLVM_DEBUG(dbgs() << "LICM: Instruction not safe to move.\n");
1074 return false;
1075 }
1076
1077 // If it is a load then check if it is guaranteed to execute by making sure
1078 // that it dominates all exiting blocks. If it doesn't, then there is a path
1079 // out of the loop which does not execute this load, so we can't hoist it.
1080 // Loads from constant memory are safe to speculate, for example indexed load
1081 // from a jump table.
1082 // Stores and side effects are already checked by isSafeToMove.
1083 if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(MI&: I) &&
1084 !IsGuaranteedToExecute(BB: I.getParent(), CurLoop)) {
1085 LLVM_DEBUG(dbgs() << "LICM: Load not guaranteed to execute.\n");
1086 return false;
1087 }
1088
1089 // Convergent attribute has been used on operations that involve inter-thread
1090 // communication which results are implicitly affected by the enclosing
1091 // control flows. It is not safe to hoist or sink such operations across
1092 // control flow.
1093 if (I.isConvergent())
1094 return false;
1095
1096 if (!TII->shouldHoist(MI: I, FromLoop: CurLoop))
1097 return false;
1098
1099 return true;
1100}
1101
1102/// Returns true if the instruction is loop invariant.
1103bool MachineLICMImpl::IsLoopInvariantInst(MachineInstr &I,
1104 MachineLoop *CurLoop) {
1105 if (!IsLICMCandidate(I, CurLoop)) {
1106 LLVM_DEBUG(dbgs() << "LICM: Instruction not a LICM candidate\n");
1107 return false;
1108 }
1109 return CurLoop->isLoopInvariant(I);
1110}
1111
1112/// Return true if the specified instruction is used by a phi node and hoisting
1113/// it could cause a copy to be inserted.
1114bool MachineLICMImpl::HasLoopPHIUse(const MachineInstr *MI,
1115 MachineLoop *CurLoop) {
1116 SmallVector<const MachineInstr *, 8> Work(1, MI);
1117 do {
1118 MI = Work.pop_back_val();
1119 for (const MachineOperand &MO : MI->all_defs()) {
1120 Register Reg = MO.getReg();
1121 if (!Reg.isVirtual())
1122 continue;
1123 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
1124 // A PHI may cause a copy to be inserted.
1125 if (UseMI.isPHI()) {
1126 // A PHI inside the loop causes a copy because the live range of Reg is
1127 // extended across the PHI.
1128 if (CurLoop->contains(Inst: &UseMI))
1129 return true;
1130 // A PHI in an exit block can cause a copy to be inserted if the PHI
1131 // has multiple predecessors in the loop with different values.
1132 // For now, approximate by rejecting all exit blocks.
1133 if (isExitBlock(CurLoop, MBB: UseMI.getParent()))
1134 return true;
1135 continue;
1136 }
1137 // Look past copies as well.
1138 if (UseMI.isCopy() && CurLoop->contains(Inst: &UseMI))
1139 Work.push_back(Elt: &UseMI);
1140 }
1141 }
1142 } while (!Work.empty());
1143 return false;
1144}
1145
1146/// Compute operand latency between a def of 'Reg' and an use in the current
1147/// loop, return true if the target considered it high.
1148bool MachineLICMImpl::HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
1149 Register Reg,
1150 MachineLoop *CurLoop) const {
1151 if (MRI->use_nodbg_empty(RegNo: Reg))
1152 return false;
1153
1154 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
1155 if (UseMI.isCopyLike())
1156 continue;
1157 if (!CurLoop->contains(BB: UseMI.getParent()))
1158 continue;
1159 for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {
1160 const MachineOperand &MO = UseMI.getOperand(i);
1161 if (!MO.isReg() || !MO.isUse())
1162 continue;
1163 Register MOReg = MO.getReg();
1164 if (MOReg != Reg)
1165 continue;
1166
1167 if (TII->hasHighOperandLatency(SchedModel, MRI, DefMI: MI, DefIdx, UseMI, UseIdx: i))
1168 return true;
1169 }
1170
1171 // Only look at the first in loop use.
1172 break;
1173 }
1174
1175 return false;
1176}
1177
1178/// Return true if the instruction is marked "cheap" or the operand latency
1179/// between its def and a use is one or less.
1180bool MachineLICMImpl::IsCheapInstruction(MachineInstr &MI) const {
1181 if (TII->isAsCheapAsAMove(MI) || MI.isSubregToReg())
1182 return true;
1183
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);
1188 if (!DefMO.isReg() || !DefMO.isDef())
1189 continue;
1190 --NumDefs;
1191 Register Reg = DefMO.getReg();
1192 if (Reg.isPhysical())
1193 continue;
1194
1195 if (!TII->hasLowDefLatency(SchedModel, DefMI: MI, DefIdx: i))
1196 return false;
1197 isCheap = true;
1198 }
1199
1200 return isCheap;
1201}
1202
1203/// Visit BBs from header to current BB, check if hoisting an instruction of the
1204/// given cost matrix can cause high register pressure.
1205bool MachineLICMImpl::CanCauseHighRegPressure(
1206 const SmallDenseMap<unsigned, int> &Cost, bool CheapInstr) {
1207 for (const auto &[Class, Weight] : Cost) {
1208 if (Weight <= 0)
1209 continue;
1210
1211 int Limit = RegLimit[Class];
1212
1213 // Don't hoist cheap instructions if they would increase register pressure,
1214 // even if we're under the limit.
1215 if (CheapInstr && !Opts.machine_licm_hoist_cheap_insts)
1216 return true;
1217
1218 for (const auto &RP : BackTrace)
1219 if (static_cast<int>(RP[Class]) + Weight >= Limit)
1220 return true;
1221 }
1222
1223 return false;
1224}
1225
1226/// Traverse the back trace from header to the current block and update their
1227/// register pressures to reflect the effect of hoisting MI from the current
1228/// block to the preheader.
1229void MachineLICMImpl::UpdateBackTraceRegPressure(const MachineInstr *MI) {
1230 // First compute the 'cost' of the instruction, i.e. its contribution
1231 // to register pressure.
1232 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
1233 /*ConsiderUnseenAsDef=*/false);
1234
1235 // Update register pressure of blocks from loop header to current block.
1236 for (auto &RP : BackTrace)
1237 for (const auto &[Class, Weight] : Cost)
1238 RP[Class] += Weight;
1239}
1240
1241/// Return true if it is potentially profitable to hoist the given loop
1242/// invariant.
1243bool MachineLICMImpl::IsProfitableToHoist(MachineInstr &MI,
1244 MachineLoop *CurLoop) {
1245 if (MI.isImplicitDef())
1246 return true;
1247
1248 // Besides removing computation from the loop, hoisting an instruction has
1249 // these effects:
1250 //
1251 // - The value defined by the instruction becomes live across the entire
1252 // loop. This increases register pressure in the loop.
1253 //
1254 // - If the value is used by a PHI in the loop, a copy will be required for
1255 // lowering the PHI after extending the live range.
1256 //
1257 // - When hoisting the last use of a value in the loop, that value no longer
1258 // needs to be live in the loop. This lowers register pressure in the loop.
1259
1260 if (Opts.machine_licm_hoist_const_stores &&
1261 isCopyFeedingInvariantStore(MI, MRI, TRI))
1262 return true;
1263
1264 bool CheapInstr = IsCheapInstruction(MI);
1265 bool CreatesCopy = HasLoopPHIUse(MI: &MI, CurLoop);
1266
1267 // Don't hoist a cheap instruction if it would create a copy in the loop.
1268 if (CheapInstr && CreatesCopy) {
1269 LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
1270 return false;
1271 }
1272
1273 // Trivially rematerializable instructions should always be hoisted
1274 // providing the register allocator can just pull them down again when needed.
1275 if (TII->isTriviallyReMaterializable(MI))
1276 return true;
1277
1278 // FIXME: If there are long latency loop-invariant instructions inside the
1279 // loop at this point, why didn't the optimizer's LICM hoist them?
1280 for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
1281 const MachineOperand &MO = MI.getOperand(i);
1282 if (!MO.isReg() || MO.isImplicit())
1283 continue;
1284 Register Reg = MO.getReg();
1285 if (!Reg.isVirtual())
1286 continue;
1287 if (MO.isDef() && HasHighOperandLatency(MI, DefIdx: i, Reg, CurLoop)) {
1288 LLVM_DEBUG(dbgs() << "Hoist High Latency: " << MI);
1289 ++NumHighLatency;
1290 return true;
1291 }
1292 }
1293
1294 // Estimate register pressure to determine whether to LICM the instruction.
1295 // In low register pressure situation, we can be more aggressive about
1296 // hoisting. Also, favors hoisting long latency instructions even in
1297 // moderately high pressure situation.
1298 // Cheap instructions will only be hoisted if they don't increase register
1299 // pressure at all.
1300 auto Cost = calcRegisterCost(MI: &MI, /*ConsiderSeen=*/false,
1301 /*ConsiderUnseenAsDef=*/false);
1302
1303 // Visit BBs from header to current BB, if hoisting this doesn't cause
1304 // high register pressure, then it's safe to proceed.
1305 if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
1306 LLVM_DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
1307 ++NumLowRP;
1308 return true;
1309 }
1310
1311 // Don't risk increasing register pressure if it would create copies.
1312 if (CreatesCopy) {
1313 LLVM_DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);
1314 return false;
1315 }
1316
1317 // Do not "speculate" in high register pressure situation. If an
1318 // instruction is not guaranteed to be executed in the loop, it's best to be
1319 // conservative.
1320 if (Opts.machine_licm_avoid_speculation &&
1321 (!IsGuaranteedToExecute(BB: MI.getParent(), CurLoop) && !MayCSE(MI: &MI))) {
1322 LLVM_DEBUG(dbgs() << "Won't speculate: " << MI);
1323 return false;
1324 }
1325
1326 // If we have a COPY with other uses in the loop, hoist to allow the users to
1327 // also be hoisted.
1328 // TODO: Handle all isCopyLike?
1329 if (MI.isCopy() || MI.isRegSequence()) {
1330 Register DefReg = MI.getOperand(i: 0).getReg();
1331 if (DefReg.isVirtual() &&
1332 all_of(Range: MI.uses(),
1333 P: [this](const MachineOperand &UseOp) {
1334 return !UseOp.isReg() || UseOp.getReg().isVirtual() ||
1335 MRI->isConstantPhysReg(PhysReg: UseOp.getReg());
1336 }) &&
1337 IsLoopInvariantInst(I&: MI, CurLoop) &&
1338 any_of(Range: MRI->use_nodbg_instructions(Reg: DefReg),
1339 P: [&CurLoop, this, DefReg,
1340 Cost = std::move(Cost)](MachineInstr &UseMI) {
1341 if (!CurLoop->contains(Inst: &UseMI))
1342 return false;
1343
1344 // COPY is a cheap instruction, but if moving it won't cause
1345 // high RP we're fine to hoist it even if the user can't be
1346 // hoisted later Otherwise we want to check the user if it's
1347 // hoistable
1348 if (CanCauseHighRegPressure(Cost, CheapInstr: false) &&
1349 !CurLoop->isLoopInvariant(I&: UseMI, ExcludeReg: DefReg))
1350 return false;
1351
1352 return true;
1353 }))
1354 return true;
1355 }
1356
1357 // High register pressure situation, only hoist if the instruction is going
1358 // to be remat'ed.
1359 if (!TII->isTriviallyReMaterializable(MI) &&
1360 !MI.isDereferenceableInvariantLoad()) {
1361 LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
1362 return false;
1363 }
1364
1365 return true;
1366}
1367
1368/// Unfold a load from the given machineinstr if the load itself could be
1369/// hoisted. Return the unfolded and hoistable load, or null if the load
1370/// couldn't be unfolded or if it wouldn't be hoistable.
1371MachineInstr *MachineLICMImpl::ExtractHoistableLoad(MachineInstr *MI,
1372 MachineLoop *CurLoop) {
1373 // Don't unfold simple loads.
1374 if (MI->canFoldAsLoad())
1375 return nullptr;
1376
1377 // If not, we may be able to unfold a load and hoist that.
1378 // First test whether the instruction is loading from an amenable
1379 // memory location.
1380 if (!MI->isDereferenceableInvariantLoad())
1381 return nullptr;
1382
1383 // Next determine the register class for a temporary register.
1384 unsigned LoadRegIndex;
1385 unsigned NewOpc =
1386 TII->getOpcodeAfterMemoryUnfold(Opc: MI->getOpcode(),
1387 /*UnfoldLoad=*/true,
1388 /*UnfoldStore=*/false,
1389 LoadRegIndex: &LoadRegIndex);
1390 if (NewOpc == 0) return nullptr;
1391 const MCInstrDesc &MID = TII->get(Opcode: NewOpc);
1392 MachineFunction &MF = *MI->getMF();
1393 const TargetRegisterClass *RC = TII->getRegClass(MCID: MID, OpNum: LoadRegIndex);
1394 // Ok, we're unfolding. Create a temporary register and do the unfold.
1395 Register Reg = MRI->createVirtualRegister(RegClass: RC);
1396
1397 SmallVector<MachineInstr *, 2> NewMIs;
1398 bool Success = TII->unfoldMemoryOperand(MF, MI&: *MI, Reg,
1399 /*UnfoldLoad=*/true,
1400 /*UnfoldStore=*/false, NewMIs);
1401 (void)Success;
1402 assert(Success &&
1403 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
1404 "succeeded!");
1405 assert(NewMIs.size() == 2 &&
1406 "Unfolded a load into multiple instructions!");
1407 MachineBasicBlock *MBB = MI->getParent();
1408 MachineBasicBlock::iterator Pos = MI;
1409 MBB->insert(I: Pos, MI: NewMIs[0]);
1410 MBB->insert(I: Pos, MI: NewMIs[1]);
1411 // If unfolding produced a load that wasn't loop-invariant or profitable to
1412 // hoist, discard the new instructions and bail.
1413 if (!IsLoopInvariantInst(I&: *NewMIs[0], CurLoop) ||
1414 !IsProfitableToHoist(MI&: *NewMIs[0], CurLoop)) {
1415 NewMIs[0]->eraseFromParent();
1416 NewMIs[1]->eraseFromParent();
1417 return nullptr;
1418 }
1419
1420 // Update register pressure for the unfolded instruction.
1421 UpdateRegPressure(MI: NewMIs[1]);
1422
1423 // Otherwise we successfully unfolded a load that we can hoist.
1424
1425 // Update the call info.
1426 if (MI->shouldUpdateAdditionalCallInfo())
1427 MF.eraseAdditionalCallInfo(MI);
1428
1429 MI->eraseFromParent();
1430 return NewMIs[0];
1431}
1432
1433/// Initialize the CSE map with instructions that are in the current loop
1434/// preheader that may become duplicates of instructions that are hoisted
1435/// out of the loop.
1436void MachineLICMImpl::InitCSEMap(MachineBasicBlock *BB) {
1437 for (MachineInstr &MI : *BB)
1438 CSEMap[BB][MI.getOpcode()].push_back(x: &MI);
1439}
1440
1441/// Initialize AllowedToHoistLoads with information about whether invariant
1442/// loads can be moved outside a given loop
1443void MachineLICMImpl::InitializeLoadsHoistableLoops() {
1444 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
1445 SmallVector<MachineLoop *, 8> LoopsInPreOrder;
1446
1447 // Mark all loops as hoistable initially and prepare a list of loops in
1448 // pre-order DFS.
1449 while (!Worklist.empty()) {
1450 auto *L = Worklist.pop_back_val();
1451 AllowedToHoistLoads[L] = true;
1452 LoopsInPreOrder.push_back(Elt: L);
1453 llvm::append_range(C&: Worklist, R: L->getSubLoops());
1454 }
1455
1456 // Going from the innermost to outermost loops, check if a loop has
1457 // instructions preventing invariant load hoisting. If such instruction is
1458 // found, mark this loop and its parent as non-hoistable and continue
1459 // investigating the next loop.
1460 // Visiting in a reversed pre-ordered DFS manner
1461 // allows us to not process all the instructions of the outer loop if the
1462 // inner loop is proved to be non-load-hoistable.
1463 for (auto *Loop : reverse(C&: LoopsInPreOrder)) {
1464 for (auto *MBB : Loop->blocks()) {
1465 // If this loop has already been marked as non-hoistable, skip it.
1466 if (!AllowedToHoistLoads[Loop])
1467 continue;
1468 for (auto &MI : *MBB) {
1469 if (!MI.isLoadFoldBarrier() && !MI.mayStore() && !MI.isCall() &&
1470 !(MI.mayLoad() && MI.hasOrderedMemoryRef()))
1471 continue;
1472 for (MachineLoop *L = Loop; L != nullptr; L = L->getParentLoop())
1473 AllowedToHoistLoads[L] = false;
1474 break;
1475 }
1476 }
1477 }
1478}
1479
1480/// Find an instruction amount PrevMIs that is a duplicate of MI.
1481/// Return this instruction if it's found.
1482MachineInstr *
1483MachineLICMImpl::LookForDuplicate(const MachineInstr *MI,
1484 std::vector<MachineInstr *> &PrevMIs) {
1485 for (MachineInstr *PrevMI : PrevMIs)
1486 if (TII->produceSameValue(MI0: *MI, MI1: *PrevMI, MRI: (PreRegAlloc ? MRI : nullptr)))
1487 return PrevMI;
1488
1489 return nullptr;
1490}
1491
1492/// Given a LICM'ed instruction, look for an instruction on the preheader that
1493/// computes the same value. If it's found, do a RAU on with the definition of
1494/// the existing instruction rather than hoisting the instruction to the
1495/// preheader.
1496bool MachineLICMImpl::EliminateCSE(
1497 MachineInstr *MI,
1498 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI) {
1499 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1500 // the undef property onto uses.
1501 if (MI->isImplicitDef())
1502 return false;
1503
1504 // Do not CSE normal loads because between them could be store instructions
1505 // that change the loaded value
1506 if (MI->mayLoad() && !MI->isDereferenceableInvariantLoad())
1507 return false;
1508
1509 if (MachineInstr *Dup = LookForDuplicate(MI, PrevMIs&: CI->second)) {
1510 LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
1511
1512 // Replace virtual registers defined by MI by their counterparts defined
1513 // by Dup.
1514 SmallVector<unsigned, 2> Defs;
1515 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1516 const MachineOperand &MO = MI->getOperand(i);
1517
1518 // Physical registers may not differ here.
1519 assert((!MO.isReg() || MO.getReg() == 0 || !MO.getReg().isPhysical() ||
1520 MO.getReg() == Dup->getOperand(i).getReg()) &&
1521 "Instructions with different phys regs are not identical!");
1522
1523 if (MO.isReg() && MO.isDef() && !MO.getReg().isPhysical())
1524 Defs.push_back(Elt: i);
1525 }
1526
1527 SmallVector<const TargetRegisterClass*, 2> OrigRCs;
1528 for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1529 unsigned Idx = Defs[i];
1530 Register Reg = MI->getOperand(i: Idx).getReg();
1531 Register DupReg = Dup->getOperand(i: Idx).getReg();
1532 OrigRCs.push_back(Elt: MRI->getRegClass(Reg: DupReg));
1533
1534 if (!MRI->constrainRegClass(Reg: DupReg, RC: MRI->getRegClass(Reg))) {
1535 // Restore old RCs if more than one defs.
1536 for (unsigned j = 0; j != i; ++j)
1537 MRI->setRegClass(Reg: Dup->getOperand(i: Defs[j]).getReg(), RC: OrigRCs[j]);
1538 return false;
1539 }
1540 }
1541
1542 for (unsigned Idx : Defs) {
1543 Register Reg = MI->getOperand(i: Idx).getReg();
1544 Register DupReg = Dup->getOperand(i: Idx).getReg();
1545 MRI->replaceRegWith(FromReg: Reg, ToReg: DupReg);
1546 // Clear Dup dead flag if any, we reuse it for Reg.
1547 if (!MRI->use_nodbg_empty(RegNo: DupReg))
1548 Dup->getOperand(i: Idx).setIsDead(false);
1549 }
1550
1551 MI->eraseFromParent();
1552 ++NumCSEed;
1553 return true;
1554 }
1555 return false;
1556}
1557
1558/// Return true if the given instruction will be CSE'd if it's hoisted out of
1559/// the loop.
1560bool MachineLICMImpl::MayCSE(MachineInstr *MI) {
1561 if (MI->mayLoad() && !MI->isDereferenceableInvariantLoad())
1562 return false;
1563
1564 unsigned Opcode = MI->getOpcode();
1565 for (auto &Map : CSEMap) {
1566 // Check this CSEMap's preheader dominates MI's basic block.
1567 if (MDTU->getDomTree().dominates(A: Map.first, B: MI->getParent())) {
1568 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
1569 Map.second.find(Val: Opcode);
1570 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1571 // the undef property onto uses.
1572 if (CI == Map.second.end() || MI->isImplicitDef())
1573 continue;
1574 if (LookForDuplicate(MI, PrevMIs&: CI->second) != nullptr)
1575 return true;
1576 }
1577 }
1578
1579 return false;
1580}
1581
1582/// When an instruction is found to use only loop invariant operands
1583/// that are safe to hoist, this instruction is called to do the dirty work.
1584/// It returns true if the instruction is hoisted.
1585unsigned MachineLICMImpl::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader,
1586 MachineLoop *CurLoop) {
1587 MachineBasicBlock *SrcBlock = MI->getParent();
1588
1589 // Disable the instruction hoisting due to block hotness
1590 if ((DisableHoistingToHotterBlocks == UseBFI::All ||
1591 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) &&
1592 isTgtHotterThanSrc(SrcBlock, TgtBlock: Preheader)) {
1593 ++NumNotHoistedDueToHotness;
1594 return HoistResult::NotHoisted;
1595 }
1596 // First check whether we should hoist this instruction.
1597 bool HasExtractHoistableLoad = false;
1598 if (!IsLoopInvariantInst(I&: *MI, CurLoop) ||
1599 !IsProfitableToHoist(MI&: *MI, CurLoop)) {
1600 // If not, try unfolding a hoistable load.
1601 MI = ExtractHoistableLoad(MI, CurLoop);
1602 if (!MI)
1603 return HoistResult::NotHoisted;
1604 HasExtractHoistableLoad = true;
1605 }
1606
1607 // If we have hoisted an instruction that may store, it can only be a constant
1608 // store.
1609 if (MI->mayStore())
1610 NumStoreConst++;
1611
1612 // Now move the instructions to the predecessor, inserting it before any
1613 // terminator instructions.
1614 LLVM_DEBUG({
1615 dbgs() << "Hoisting " << *MI;
1616 if (MI->getParent()->getBasicBlock())
1617 dbgs() << " from " << printMBBReference(*MI->getParent());
1618 if (Preheader->getBasicBlock())
1619 dbgs() << " to " << printMBBReference(*Preheader);
1620 dbgs() << "\n";
1621 });
1622
1623 // If this is the first instruction being hoisted to the preheader,
1624 // initialize the CSE map with potential common expressions.
1625 if (FirstInLoop) {
1626 InitCSEMap(BB: Preheader);
1627 FirstInLoop = false;
1628 }
1629
1630 // Look for opportunity to CSE the hoisted instruction.
1631 unsigned Opcode = MI->getOpcode();
1632 bool HasCSEDone = false;
1633 for (auto &Map : CSEMap) {
1634 // Check this CSEMap's preheader dominates MI's basic block.
1635 if (MDTU->getDomTree().dominates(A: Map.first, B: MI->getParent())) {
1636 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
1637 Map.second.find(Val: Opcode);
1638 if (CI != Map.second.end()) {
1639 if (EliminateCSE(MI, CI)) {
1640 HasCSEDone = true;
1641 break;
1642 }
1643 }
1644 }
1645 }
1646
1647 if (!HasCSEDone) {
1648 // Otherwise, splice the instruction to the preheader.
1649 Preheader->splice(Where: Preheader->getFirstTerminator(),Other: MI->getParent(),From: MI);
1650
1651 // Since we are moving the instruction out of its basic block, we do not
1652 // retain its debug location. Doing so would degrade the debugging
1653 // experience and adversely affect the accuracy of profiling information.
1654 assert(!MI->isDebugInstr() && "Should not hoist debug inst");
1655 MI->setDebugLoc(DebugLoc());
1656
1657 // Update register pressure for BBs from header to this block.
1658 UpdateBackTraceRegPressure(MI);
1659
1660 CSEMap[Preheader][Opcode].push_back(x: MI);
1661 }
1662
1663 ++NumHoisted;
1664 Changed = true;
1665
1666 if (HasCSEDone || HasExtractHoistableLoad)
1667 return HoistResult::Hoisted | HoistResult::ErasedMI;
1668 return HoistResult::Hoisted;
1669}
1670
1671/// Get the preheader for the current loop, splitting a critical edge if needed.
1672MachineBasicBlock *MachineLICMImpl::getOrCreatePreheader(MachineLoop *CurLoop) {
1673 // Determine the block to which to hoist instructions. If we can't find a
1674 // suitable loop predecessor, we can't do any hoisting.
1675 if (MachineBasicBlock *Preheader = CurLoop->getLoopPreheader())
1676 return Preheader;
1677
1678 // Try forming a preheader by splitting the critical edge between the single
1679 // predecessor and the loop header.
1680 if (MachineBasicBlock *Pred = CurLoop->getLoopPredecessor()) {
1681 MachineBasicBlock *NewPreheader = Pred->SplitCriticalEdge(
1682 Succ: CurLoop->getHeader(), Analyses: {.LIS: nullptr, .SI: nullptr, .MLI: MLI}, MDTU);
1683 if (NewPreheader)
1684 Changed = true;
1685 return NewPreheader;
1686 }
1687
1688 return nullptr;
1689}
1690
1691/// Is the target basic block at least -machine-licm-block-freq-ratio-threshold
1692/// times hotter than the source basic block.
1693bool MachineLICMImpl::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
1694 MachineBasicBlock *TgtBlock) {
1695 // Parse source and target basic block frequency from MBFI
1696 uint64_t SrcBF = MBFI->getBlockFreq(MBB: SrcBlock).getFrequency();
1697 uint64_t DstBF = MBFI->getBlockFreq(MBB: TgtBlock).getFrequency();
1698
1699 // Disable the hoisting if source block frequency is zero
1700 if (!SrcBF)
1701 return true;
1702
1703 double Ratio = (double)DstBF / SrcBF;
1704
1705 // Compare the block frequency ratio with the threshold
1706 return Ratio > Opts.machine_licm_block_freq_ratio_threshold;
1707}
1708
1709template <typename DerivedT, bool PreRegAlloc>
1710PreservedAnalyses MachineLICMBasePass<DerivedT, PreRegAlloc>::run(
1711 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {
1712 bool Changed =
1713 MachineLICMImpl(getCodeGenOptions(MF), PreRegAlloc, nullptr, &MFAM)
1714 .run(MF);
1715 if (!Changed)
1716 return PreservedAnalyses::all();
1717 auto PA = getMachineFunctionPassPreservedAnalyses();
1718 PA.preserve<MachineLoopAnalysis>();
1719 PA.preserve<MachineDominatorTreeAnalysis>();
1720 return PA;
1721}
1722
1723template class llvm::MachineLICMBasePass<EarlyMachineLICMPass, true>;
1724template class llvm::MachineLICMBasePass<MachineLICMPass, false>;
1725