LLVM 24.0.0git
MachineLICM.cpp
Go to the documentation of this file.
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
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/Statistic.h"
46#include "llvm/IR/DebugLoc.h"
47#include "llvm/IR/Module.h"
49#include "llvm/MC/MCInstrDesc.h"
50#include "llvm/MC/MCRegister.h"
51#include "llvm/Pass.h"
54#include "llvm/Support/Debug.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"),
73 "disable the feature"),
75 "enable the feature when using profile data"),
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;
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(CurLoop);
130 if (Inserted) {
132 CurLoop->getExitBlocks(ExitBlocks);
133 It->second = std::move(ExitBlocks);
134 }
135 return is_contained(It->second, 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.
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>();
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>();
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
309 "Machine Loop Invariant Code Motion", false, false)
316 "Machine Loop Invariant Code Motion", false, false)
317
318INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
319 "Early Machine Loop Invariant Code Motion", false, false)
325INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
326 "Early Machine Loop Invariant Code Motion", false, false)
327
328bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
329 if (skipFunction(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
344 .getManager()
345 .getResult<AAManager>(MF.getFunction())
346 : &LegacyPass->getAnalysis<AAResultsWrapperPass>().getAAResults();
347
348 RegClassInfo =
349 MFAM != nullptr
352 .getRCI();
353
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(&ST);
367
368 HasProfileData = MF.getFunction().hasProfileData();
369
371 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData))
372 MBFI = LegacyPass
374 .getBFI()
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(NumRPS);
387 llvm::fill(RegPressure, 0);
388 RegLimit.resize(NumRPS);
389 for (unsigned i = 0, e = NumRPS; i != e; ++i)
390 RegLimit[i] = RegClassInfo->getRegPressureSetLimit(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(CurLoop->getHeader());
406 FirstInLoop = true;
407 HoistOutOfLoop(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;
429 dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {
430 if (Value->getFrameIndex() == FI)
431 return true;
432 }
433 }
434 return false;
435}
436
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(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;
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(FI) &&
505 MFI->isSpillSlotObjectIndex(FI) &&
507 StoredFIs.insert(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, RUClobbers, 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(static_cast<unsigned>(Unit)) ||
532 RUClobbers.test(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(static_cast<unsigned>(Unit))) {
554 RUClobbers.set(static_cast<unsigned>(Unit));
555 RuledOut = true;
556 } else if (RUClobbers.test(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(*MI, CurLoop)) ||
572 Candidates.push_back(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
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(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, 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();
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, RUDefs, RUClobbers, StoredFIs, Candidates, CurLoop);
627 }
628
629 // Gather the registers read / clobbered by the terminator.
630 BitVector TermRUs(NumRegUnits);
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(Candidate.FI))
655 continue;
656
657 Register Def = Candidate.Def;
658 bool Safe = true;
659 for (MCRegUnit Unit : TRI->regunits(Def)) {
660 if (RUClobbers.test(static_cast<unsigned>(Unit)) ||
661 TermRUs.test(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(MO.getReg())) {
675 if (RUDefs.test(static_cast<unsigned>(Unit)) ||
676 RUClobbers.test(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, 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(Reg);
699 for (MachineInstr &MI : *BB) {
700 for (MachineOperand &MO : MI.all_uses()) {
701 if (!MO.getReg())
702 continue;
703 if (TRI->regsOverlap(Reg, 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(Preheader->getFirstTerminator(), MBB, 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(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(CurLoop, 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(CurrentLoopExitingBlocks);
753 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
754 if (!MDTU->getDomTree().dominates(BB, 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(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(Node->getBlock());
787 // Now traverse upwards to pop ancestors whose offsprings are all done.
788 MachineDomTreeNode *Parent = ParentMap.lookup(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
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(HeaderN);
812 while (!WorkList.empty()) {
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(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(Child);
844 }
845 std::reverse(WorkList.begin() + WorkListStart, 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(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(*MBB)) {
866 unsigned HoistRes = HoistResult::NotHoisted;
867 HoistRes = Hoist(&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(MI.getParent()); L != CurLoop;
873 L = L->getParentLoop())
874 InnerLoopWorkList.push_back(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, InnerLoopPreheader, InnerLoop);
881 if (HoistRes & HoistResult::Hoisted)
882 break;
883 }
884 }
885 }
886
887 if (HoistRes & HoistResult::ErasedMI)
888 continue;
889
890 UpdateRegPressure(&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(RegPressure, 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(*BB, TBB, FBB, Cond, false) && Cond.empty())
912 InitRegPressure(*BB->pred_begin());
913 }
914
915 for (const MachineInstr &MI : *BB)
916 UpdateRegPressure(&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(Reg).second : false;
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(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.
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.
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(MO.getReg(), MRI);
1018 if (Reg.isVirtual())
1019 return false;
1020 if (!TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *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.
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(1).getReg();
1047 if (CopySrcReg.isVirtual())
1048 return false;
1049
1050 if (!TRI->isCallerPreservedPhysReg(CopySrcReg.asMCReg(), *MF))
1051 return false;
1052
1053 Register CopyDstReg = MI.getOperand(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(CopyDstReg)) {
1058 if (UseMI.mayStore() && isInvariantStore(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(DontMoveAcrossStore)) &&
1071 !(Opts.machine_licm_hoist_const_stores &&
1072 isInvariantStore(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(I) &&
1084 !IsGuaranteedToExecute(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(I, 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) {
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(&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, UseMI.getParent()))
1134 return true;
1135 continue;
1136 }
1137 // Look past copies as well.
1138 if (UseMI.isCopy() && CurLoop->contains(&UseMI))
1139 Work.push_back(&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(Reg))
1152 return false;
1153
1154 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
1155 if (UseMI.isCopyLike())
1156 continue;
1157 if (!CurLoop->contains(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, MI, DefIdx, UseMI, 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, MI, 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 &&
1262 return true;
1263
1264 bool CheapInstr = IsCheapInstruction(MI);
1265 bool CreatesCopy = HasLoopPHIUse(&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, 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, /*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(MI.getParent(), CurLoop) && !MayCSE(&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(0).getReg();
1331 if (DefReg.isVirtual() &&
1332 all_of(MI.uses(),
1333 [this](const MachineOperand &UseOp) {
1334 return !UseOp.isReg() || UseOp.getReg().isVirtual() ||
1335 MRI->isConstantPhysReg(UseOp.getReg());
1336 }) &&
1337 IsLoopInvariantInst(MI, CurLoop) &&
1339 [&CurLoop, this, DefReg,
1340 Cost = std::move(Cost)](MachineInstr &UseMI) {
1341 if (!CurLoop->contains(&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, false) &&
1349 !CurLoop->isLoopInvariant(UseMI, 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(MI->getOpcode(),
1387 /*UnfoldLoad=*/true,
1388 /*UnfoldStore=*/false,
1389 &LoadRegIndex);
1390 if (NewOpc == 0) return nullptr;
1391 const MCInstrDesc &MID = TII->get(NewOpc);
1392 MachineFunction &MF = *MI->getMF();
1393 const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex);
1394 // Ok, we're unfolding. Create a temporary register and do the unfold.
1396
1397 SmallVector<MachineInstr *, 2> NewMIs;
1398 bool Success = TII->unfoldMemoryOperand(MF, *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();
1409 MBB->insert(Pos, NewMIs[0]);
1410 MBB->insert(Pos, 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(*NewMIs[0], CurLoop) ||
1414 !IsProfitableToHoist(*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(NewMIs[1]);
1422
1423 // Otherwise we successfully unfolded a load that we can hoist.
1424
1425 // Update the call info.
1426 if (MI->shouldUpdateAdditionalCallInfo())
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(&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(L);
1453 llvm::append_range(Worklist, 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(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(*MI, *PrevMI, (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, 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(i);
1525 }
1526
1528 for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1529 unsigned Idx = Defs[i];
1530 Register Reg = MI->getOperand(Idx).getReg();
1531 Register DupReg = Dup->getOperand(Idx).getReg();
1532 OrigRCs.push_back(MRI->getRegClass(DupReg));
1533
1534 if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
1535 // Restore old RCs if more than one defs.
1536 for (unsigned j = 0; j != i; ++j)
1537 MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
1538 return false;
1539 }
1540 }
1541
1542 for (unsigned Idx : Defs) {
1543 Register Reg = MI->getOperand(Idx).getReg();
1544 Register DupReg = Dup->getOperand(Idx).getReg();
1545 MRI->replaceRegWith(Reg, DupReg);
1546 // Clear Dup dead flag if any, we reuse it for Reg.
1547 if (!MRI->use_nodbg_empty(DupReg))
1548 Dup->getOperand(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(Map.first, MI->getParent())) {
1568 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
1569 Map.second.find(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, 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
1591 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) &&
1592 isTgtHotterThanSrc(SrcBlock, Preheader)) {
1593 ++NumNotHoistedDueToHotness;
1594 return HoistResult::NotHoisted;
1595 }
1596 // First check whether we should hoist this instruction.
1597 bool HasExtractHoistableLoad = false;
1598 if (!IsLoopInvariantInst(*MI, CurLoop) ||
1599 !IsProfitableToHoist(*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(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(Map.first, MI->getParent())) {
1636 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
1637 Map.second.find(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(Preheader->getFirstTerminator(),MI->getParent(),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(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 CurLoop->getHeader(), {nullptr, nullptr, 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(SrcBlock).getFrequency();
1697 uint64_t DstBF = MBFI->getBlockFreq(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>
1712 bool Changed =
1713 MachineLICMImpl(getCodeGenOptions(MF), PreRegAlloc, nullptr, &MFAM)
1714 .run(MF);
1715 if (!Changed)
1716 return PreservedAnalyses::all();
1718 PA.preserve<MachineLoopAnalysis>();
1719 PA.preserve<MachineDominatorTreeAnalysis>();
1720 return PA;
1721}
1722
#define Success
MachineInstrBuilder & UseMI
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const AArch64InstrInfo & TII
uint64_t uint64_t
MachineBasicBlock & MBB
basic Basic Alias true
This file implements the BitVector class.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
This file defines the DenseMap class.
#define DEBUG_TYPE
IRTranslator LLVM IR MI
Module.h This file contains the declarations for the Module class.
static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &ExitBlocks)
Return true if the specified block is in the list.
Definition LCSSA.cpp:68
===- LazyMachineBlockFrequencyInfo.h - Lazy Block Frequency -*- C++ -*–===//
#define I(x, y, z)
Definition MD5.cpp:57
print mir2vec MIR2Vec Vocabulary Printer Pass
Definition MIR2Vec.cpp:656
#define GET_RESULT(RESULT, GETTER, INFIX)
static cl::opt< UseBFI > DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks", cl::desc("Disable hoisting instructions to" " hotter blocks"), cl::init(UseBFI::PGO), cl::Hidden, cl::values(clEnumValN(UseBFI::None, "none", "disable the feature"), clEnumValN(UseBFI::PGO, "pgo", "enable the feature when using profile data"), clEnumValN(UseBFI::All, "all", "enable the feature with/wo profile data")))
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI)
Return true if this machine instruction loads from global offset table or constant pool.
UseBFI
Machine Loop Invariant Code false
static bool InstructionStoresToFI(const MachineInstr *MI, int FI)
Return true if instruction stores to the specified frame.
static bool isCopyFeedingInvariantStore(const MachineInstr &MI, const MachineRegisterInfo *MRI, const TargetRegisterInfo *TRI)
static void applyBitsNotInRegMaskToRegUnitsMask(const TargetRegisterInfo &TRI, BitVector &RUs, const uint32_t *Mask)
static bool isInvariantStore(const MachineInstr &MI, const TargetRegisterInfo *TRI, const MachineRegisterInfo *MRI)
Register Reg
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
SmallVector< MachineOperand, 4 > Cond
MachineRegisterInfo & MRI
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
static DominatorTree getDomTree(Function &F)
This file contains some templates that are useful if you are working with the STL at all.
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)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
This file describes how to lower LLVM code to machine code.
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Register isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const override
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const override
bool isAsCheapAsAMove(const MachineInstr &MI) const override
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
Definition BitVector.h:483
BitVector & set()
Set all bits in the bitvector.
Definition BitVector.h:367
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Definition DenseMap.h:856
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
A specialized PseudoSourceValue for holding FixedStack values, which must include a frame index.
Constant * getPersonalityFn() const
Get the personality function associated with this function.
bool hasProfileData() const
Return true if the function is annotated with profile data.
Definition Function.h:313
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
Module * getParent()
Get the module that this global value is contained inside of...
This is an alternative analysis pass to MachineBlockFrequencyInfo.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
BlockT * getHeader() const
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
iterator end() const
iterator begin() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
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 '...
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineInstr *A, const MachineInstr *B) const
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
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.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
void eraseAdditionalCallInfo(const MachineInstr *MI)
Following functions update call site info.
Representation of each machine instruction.
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
Analysis pass that exposes the MachineLoopInfo for a machine function.
LLVM_ABI bool isLoopInvariant(MachineInstr &I, const Register ExcludeReg=0) const
Returns true if the instruction is loop invariant.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
LLVM_ABI bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
LLVM_ABI Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
LLVM_ABI void setRegClass(Register Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
LLVM_ABI const TargetRegisterClass * constrainRegClass(Register Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
LLVM_ABI void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
ExceptionHandling getExceptionModel() const
Returns the exception model recorded by the "exception-model" module flag, or the target's default ex...
Definition Module.cpp:744
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
Special value supplied for machine level alias analysis.
unsigned getRegPressureSetLimit(unsigned Idx) const
Get the register unit limit for the given pressure set index.
Wrapper class representing virtual and physical registers.
Definition Register.h:20
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition Register.h:107
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition Register.h:83
void resize(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
virtual Register getExceptionSelectorRegister(ExceptionHandling EH, const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception typeid on entry to a la...
virtual Register getExceptionPointerRegister(ExceptionHandling EH, const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception address on entry to an ...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)
Initialize the machine model for instruction scheduling.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetLowering * getTargetLowering() const
LLVM Value Representation.
Definition Value.h:75
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition DenseSet.h:188
Abstract Attribute helper functions.
Definition Attributor.h:166
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< DefNode * > Def
Definition RDFGraph.h:384
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI char & EarlyMachineLICMID
This pass performs loop invariant code motion on machine instructions.
void fill(R &&Range, T &&Value)
Provide wrappers to std::fill which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1775
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
InstructionCost Cost
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
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...
Definition STLExtras.h:649
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
ExceptionHandling
Definition CodeGen.h:54
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
LLVM_ABI char & MachineLICMID
This pass performs loop invariant code motion on machine instructions.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass
Definition FastISel.h:58
#define N