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