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"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineDominators.h"
28 #include "llvm/CodeGen/MachineFrameInfo.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineFunctionPass.h"
31 #include "llvm/CodeGen/MachineInstr.h"
32 #include "llvm/CodeGen/MachineLoopInfo.h"
33 #include "llvm/CodeGen/MachineMemOperand.h"
34 #include "llvm/CodeGen/MachineOperand.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/PseudoSourceValue.h"
37 #include "llvm/CodeGen/TargetInstrInfo.h"
38 #include "llvm/CodeGen/TargetLowering.h"
39 #include "llvm/CodeGen/TargetRegisterInfo.h"
40 #include "llvm/CodeGen/TargetSchedule.h"
41 #include "llvm/CodeGen/TargetSubtargetInfo.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/MC/MCInstrDesc.h"
45 #include "llvm/MC/MCRegister.h"
46 #include "llvm/MC/MCRegisterInfo.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/Casting.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/raw_ostream.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <limits>
55 #include <vector>
56
57 using namespace llvm;
58
59 #define DEBUG_TYPE "machinelicm"
60
61 static cl::opt<bool>
62 AvoidSpeculation("avoid-speculation",
63 cl::desc("MachineLICM should avoid speculation"),
64 cl::init(true), cl::Hidden);
65
66 static cl::opt<bool>
67 HoistCheapInsts("hoist-cheap-insts",
68 cl::desc("MachineLICM should hoist even cheap instructions"),
69 cl::init(false), cl::Hidden);
70
71 static cl::opt<bool>
72 SinkInstsToAvoidSpills("sink-insts-to-avoid-spills",
73 cl::desc("MachineLICM should sink instructions into "
74 "loops to avoid register spills"),
75 cl::init(false), cl::Hidden);
76 static cl::opt<bool>
77 HoistConstStores("hoist-const-stores",
78 cl::desc("Hoist invariant stores"),
79 cl::init(true), cl::Hidden);
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.
82 static cl::opt<unsigned>
83 BlockFrequencyRatioThreshold("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
88 enum class UseBFI { None, PGO, All };
89
90 static cl::opt<UseBFI>
91 DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks",
92 cl::desc("Disable hoisting instructions to"
93 " hotter blocks"),
94 cl::init(UseBFI::PGO), cl::Hidden,
95 cl::values(clEnumValN(UseBFI::None, "none",
96 "disable the feature"),
97 clEnumValN(UseBFI::PGO, "pgo",
98 "enable the feature when using profile data"),
99 clEnumValN(UseBFI::All, "all",
100 "enable the feature with/wo profile data")));
101
102 STATISTIC(NumHoisted,
103 "Number of machine instructions hoisted out of loops");
104 STATISTIC(NumLowRP,
105 "Number of instructions hoisted in low reg pressure situation");
106 STATISTIC(NumHighLatency,
107 "Number of high latency instructions hoisted");
108 STATISTIC(NumCSEed,
109 "Number of hoisted machine instructions CSEed");
110 STATISTIC(NumPostRAHoisted,
111 "Number of machine instructions hoisted out of loops post regalloc");
112 STATISTIC(NumStoreConst,
113 "Number of stores of const phys reg hoisted out of loops");
114 STATISTIC(NumNotHoistedDueToHotness,
115 "Number of instructions not hoisted due to block frequency");
116
117 namespace {
118
119 class MachineLICMBase : public MachineFunctionPass {
120 const TargetInstrInfo *TII;
121 const TargetLoweringBase *TLI;
122 const TargetRegisterInfo *TRI;
123 const MachineFrameInfo *MFI;
124 MachineRegisterInfo *MRI;
125 TargetSchedModel SchedModel;
126 bool PreRegAlloc;
127 bool HasProfileData;
128
129 // Various analyses that we use...
130 AliasAnalysis *AA; // Alias analysis info.
131 MachineBlockFrequencyInfo *MBFI; // Machine block frequncy info
132 MachineLoopInfo *MLI; // Current MachineLoopInfo
133 MachineDominatorTree *DT; // Machine dominator tree for the cur loop
134
135 // State that is updated as we process loops
136 bool Changed; // True if a loop is changed.
137 bool FirstInLoop; // True if it's the first LICM in the loop.
138 MachineLoop *CurLoop; // The current loop we are working on.
139 MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
140
141 // Exit blocks for CurLoop.
142 SmallVector<MachineBasicBlock *, 8> ExitBlocks;
143
isExitBlock(const MachineBasicBlock * MBB) const144 bool isExitBlock(const MachineBasicBlock *MBB) const {
145 return is_contained(ExitBlocks, MBB);
146 }
147
148 // Track 'estimated' register pressure.
149 SmallSet<Register, 32> RegSeen;
150 SmallVector<unsigned, 8> RegPressure;
151
152 // Register pressure "limit" per register pressure set. If the pressure
153 // is higher than the limit, then it's considered high.
154 SmallVector<unsigned, 8> RegLimit;
155
156 // Register pressure on path leading from loop preheader to current BB.
157 SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;
158
159 // For each opcode, keep a list of potential CSE instructions.
160 DenseMap<unsigned, std::vector<const MachineInstr *>> CSEMap;
161
162 enum {
163 SpeculateFalse = 0,
164 SpeculateTrue = 1,
165 SpeculateUnknown = 2
166 };
167
168 // If a MBB does not dominate loop exiting blocks then it may not safe
169 // to hoist loads from this block.
170 // Tri-state: 0 - false, 1 - true, 2 - unknown
171 unsigned SpeculationState;
172
173 public:
MachineLICMBase(char & PassID,bool PreRegAlloc)174 MachineLICMBase(char &PassID, bool PreRegAlloc)
175 : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
176
177 bool runOnMachineFunction(MachineFunction &MF) override;
178
getAnalysisUsage(AnalysisUsage & AU) const179 void getAnalysisUsage(AnalysisUsage &AU) const override {
180 AU.addRequired<MachineLoopInfo>();
181 if (DisableHoistingToHotterBlocks != UseBFI::None)
182 AU.addRequired<MachineBlockFrequencyInfo>();
183 AU.addRequired<MachineDominatorTree>();
184 AU.addRequired<AAResultsWrapperPass>();
185 AU.addPreserved<MachineLoopInfo>();
186 MachineFunctionPass::getAnalysisUsage(AU);
187 }
188
releaseMemory()189 void releaseMemory() override {
190 RegSeen.clear();
191 RegPressure.clear();
192 RegLimit.clear();
193 BackTrace.clear();
194 CSEMap.clear();
195 }
196
197 private:
198 /// Keep track of information about hoisting candidates.
199 struct CandidateInfo {
200 MachineInstr *MI;
201 unsigned Def;
202 int FI;
203
CandidateInfo__anone76600a70111::MachineLICMBase::CandidateInfo204 CandidateInfo(MachineInstr *mi, unsigned def, int fi)
205 : MI(mi), Def(def), FI(fi) {}
206 };
207
208 void HoistRegionPostRA();
209
210 void HoistPostRA(MachineInstr *MI, unsigned Def);
211
212 void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs,
213 BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs,
214 SmallVectorImpl<CandidateInfo> &Candidates);
215
216 void AddToLiveIns(MCRegister Reg);
217
218 bool IsLICMCandidate(MachineInstr &I);
219
220 bool IsLoopInvariantInst(MachineInstr &I);
221
222 bool HasLoopPHIUse(const MachineInstr *MI) const;
223
224 bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
225 Register Reg) const;
226
227 bool IsCheapInstruction(MachineInstr &MI) const;
228
229 bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost,
230 bool Cheap);
231
232 void UpdateBackTraceRegPressure(const MachineInstr *MI);
233
234 bool IsProfitableToHoist(MachineInstr &MI);
235
236 bool IsGuaranteedToExecute(MachineBasicBlock *BB);
237
238 void EnterScope(MachineBasicBlock *MBB);
239
240 void ExitScope(MachineBasicBlock *MBB);
241
242 void ExitScopeIfDone(
243 MachineDomTreeNode *Node,
244 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,
245 DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap);
246
247 void HoistOutOfLoop(MachineDomTreeNode *HeaderN);
248
249 void HoistRegion(MachineDomTreeNode *N, bool IsHeader);
250
251 void SinkIntoLoop();
252
253 void InitRegPressure(MachineBasicBlock *BB);
254
255 DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
256 bool ConsiderSeen,
257 bool ConsiderUnseenAsDef);
258
259 void UpdateRegPressure(const MachineInstr *MI,
260 bool ConsiderUnseenAsDef = false);
261
262 MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
263
264 const MachineInstr *
265 LookForDuplicate(const MachineInstr *MI,
266 std::vector<const MachineInstr *> &PrevMIs);
267
268 bool EliminateCSE(
269 MachineInstr *MI,
270 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI);
271
272 bool MayCSE(MachineInstr *MI);
273
274 bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
275
276 void InitCSEMap(MachineBasicBlock *BB);
277
278 bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
279 MachineBasicBlock *TgtBlock);
280 MachineBasicBlock *getCurPreheader();
281 };
282
283 class MachineLICM : public MachineLICMBase {
284 public:
285 static char ID;
MachineLICM()286 MachineLICM() : MachineLICMBase(ID, false) {
287 initializeMachineLICMPass(*PassRegistry::getPassRegistry());
288 }
289 };
290
291 class EarlyMachineLICM : public MachineLICMBase {
292 public:
293 static char ID;
EarlyMachineLICM()294 EarlyMachineLICM() : MachineLICMBase(ID, true) {
295 initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry());
296 }
297 };
298
299 } // end anonymous namespace
300
301 char MachineLICM::ID;
302 char EarlyMachineLICM::ID;
303
304 char &llvm::MachineLICMID = MachineLICM::ID;
305 char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;
306
307 INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
308 "Machine Loop Invariant Code Motion", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)309 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
310 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
311 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
312 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
313 INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
314 "Machine Loop Invariant Code Motion", false, false)
315
316 INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
317 "Early Machine Loop Invariant Code Motion", false, false)
318 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
319 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
320 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
321 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
322 INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
323 "Early Machine Loop Invariant Code Motion", false, false)
324
325 /// Test if the given loop is the outer-most loop that has a unique predecessor.
326 static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
327 // Check whether this loop even has a unique predecessor.
328 if (!CurLoop->getLoopPredecessor())
329 return false;
330 // Ok, now check to see if any of its outer loops do.
331 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
332 if (L->getLoopPredecessor())
333 return false;
334 // None of them did, so this is the outermost with a unique predecessor.
335 return true;
336 }
337
runOnMachineFunction(MachineFunction & MF)338 bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
339 if (skipFunction(MF.getFunction()))
340 return false;
341
342 Changed = FirstInLoop = false;
343 const TargetSubtargetInfo &ST = MF.getSubtarget();
344 TII = ST.getInstrInfo();
345 TLI = ST.getTargetLowering();
346 TRI = ST.getRegisterInfo();
347 MFI = &MF.getFrameInfo();
348 MRI = &MF.getRegInfo();
349 SchedModel.init(&ST);
350
351 PreRegAlloc = MRI->isSSA();
352 HasProfileData = MF.getFunction().hasProfileData();
353
354 if (PreRegAlloc)
355 LLVM_DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: ");
356 else
357 LLVM_DEBUG(dbgs() << "******** Post-regalloc Machine LICM: ");
358 LLVM_DEBUG(dbgs() << MF.getName() << " ********\n");
359
360 if (PreRegAlloc) {
361 // Estimate register pressure during pre-regalloc pass.
362 unsigned NumRPS = TRI->getNumRegPressureSets();
363 RegPressure.resize(NumRPS);
364 std::fill(RegPressure.begin(), RegPressure.end(), 0);
365 RegLimit.resize(NumRPS);
366 for (unsigned i = 0, e = NumRPS; i != e; ++i)
367 RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);
368 }
369
370 // Get our Loop information...
371 if (DisableHoistingToHotterBlocks != UseBFI::None)
372 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
373 MLI = &getAnalysis<MachineLoopInfo>();
374 DT = &getAnalysis<MachineDominatorTree>();
375 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
376
377 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());
378 while (!Worklist.empty()) {
379 CurLoop = Worklist.pop_back_val();
380 CurPreheader = nullptr;
381 ExitBlocks.clear();
382
383 // If this is done before regalloc, only visit outer-most preheader-sporting
384 // loops.
385 if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) {
386 Worklist.append(CurLoop->begin(), CurLoop->end());
387 continue;
388 }
389
390 CurLoop->getExitBlocks(ExitBlocks);
391
392 if (!PreRegAlloc)
393 HoistRegionPostRA();
394 else {
395 // CSEMap is initialized for loop header when the first instruction is
396 // being hoisted.
397 MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader());
398 FirstInLoop = true;
399 HoistOutOfLoop(N);
400 CSEMap.clear();
401
402 if (SinkInstsToAvoidSpills)
403 SinkIntoLoop();
404 }
405 }
406
407 return Changed;
408 }
409
410 /// Return true if instruction stores to the specified frame.
InstructionStoresToFI(const MachineInstr * MI,int FI)411 static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
412 // Check mayStore before memory operands so that e.g. DBG_VALUEs will return
413 // true since they have no memory operands.
414 if (!MI->mayStore())
415 return false;
416 // If we lost memory operands, conservatively assume that the instruction
417 // writes to all slots.
418 if (MI->memoperands_empty())
419 return true;
420 for (const MachineMemOperand *MemOp : MI->memoperands()) {
421 if (!MemOp->isStore() || !MemOp->getPseudoValue())
422 continue;
423 if (const FixedStackPseudoSourceValue *Value =
424 dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {
425 if (Value->getFrameIndex() == FI)
426 return true;
427 }
428 }
429 return false;
430 }
431
432 /// Examine the instruction for potentai LICM candidate. Also
433 /// gather register def and frame object update information.
ProcessMI(MachineInstr * MI,BitVector & PhysRegDefs,BitVector & PhysRegClobbers,SmallSet<int,32> & StoredFIs,SmallVectorImpl<CandidateInfo> & Candidates)434 void MachineLICMBase::ProcessMI(MachineInstr *MI,
435 BitVector &PhysRegDefs,
436 BitVector &PhysRegClobbers,
437 SmallSet<int, 32> &StoredFIs,
438 SmallVectorImpl<CandidateInfo> &Candidates) {
439 bool RuledOut = false;
440 bool HasNonInvariantUse = false;
441 unsigned Def = 0;
442 for (const MachineOperand &MO : MI->operands()) {
443 if (MO.isFI()) {
444 // Remember if the instruction stores to the frame index.
445 int FI = MO.getIndex();
446 if (!StoredFIs.count(FI) &&
447 MFI->isSpillSlotObjectIndex(FI) &&
448 InstructionStoresToFI(MI, FI))
449 StoredFIs.insert(FI);
450 HasNonInvariantUse = true;
451 continue;
452 }
453
454 // We can't hoist an instruction defining a physreg that is clobbered in
455 // the loop.
456 if (MO.isRegMask()) {
457 PhysRegClobbers.setBitsNotInMask(MO.getRegMask());
458 continue;
459 }
460
461 if (!MO.isReg())
462 continue;
463 Register Reg = MO.getReg();
464 if (!Reg)
465 continue;
466 assert(Register::isPhysicalRegister(Reg) &&
467 "Not expecting virtual register!");
468
469 if (!MO.isDef()) {
470 if (Reg && (PhysRegDefs.test(Reg) || PhysRegClobbers.test(Reg)))
471 // If it's using a non-loop-invariant register, then it's obviously not
472 // safe to hoist.
473 HasNonInvariantUse = true;
474 continue;
475 }
476
477 if (MO.isImplicit()) {
478 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
479 PhysRegClobbers.set(*AI);
480 if (!MO.isDead())
481 // Non-dead implicit def? This cannot be hoisted.
482 RuledOut = true;
483 // No need to check if a dead implicit def is also defined by
484 // another instruction.
485 continue;
486 }
487
488 // FIXME: For now, avoid instructions with multiple defs, unless
489 // it's a dead implicit def.
490 if (Def)
491 RuledOut = true;
492 else
493 Def = Reg;
494
495 // If we have already seen another instruction that defines the same
496 // register, then this is not safe. Two defs is indicated by setting a
497 // PhysRegClobbers bit.
498 for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS) {
499 if (PhysRegDefs.test(*AS))
500 PhysRegClobbers.set(*AS);
501 }
502 // Need a second loop because MCRegAliasIterator can visit the same
503 // register twice.
504 for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid(); ++AS)
505 PhysRegDefs.set(*AS);
506
507 if (PhysRegClobbers.test(Reg))
508 // MI defined register is seen defined by another instruction in
509 // the loop, it cannot be a LICM candidate.
510 RuledOut = true;
511 }
512
513 // Only consider reloads for now and remats which do not have register
514 // operands. FIXME: Consider unfold load folding instructions.
515 if (Def && !RuledOut) {
516 int FI = std::numeric_limits<int>::min();
517 if ((!HasNonInvariantUse && IsLICMCandidate(*MI)) ||
518 (TII->isLoadFromStackSlot(*MI, FI) && MFI->isSpillSlotObjectIndex(FI)))
519 Candidates.push_back(CandidateInfo(MI, Def, FI));
520 }
521 }
522
523 /// Walk the specified region of the CFG and hoist loop invariants out to the
524 /// preheader.
HoistRegionPostRA()525 void MachineLICMBase::HoistRegionPostRA() {
526 MachineBasicBlock *Preheader = getCurPreheader();
527 if (!Preheader)
528 return;
529
530 unsigned NumRegs = TRI->getNumRegs();
531 BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop.
532 BitVector PhysRegClobbers(NumRegs); // Regs defined more than once.
533
534 SmallVector<CandidateInfo, 32> Candidates;
535 SmallSet<int, 32> StoredFIs;
536
537 // Walk the entire region, count number of defs for each register, and
538 // collect potential LICM candidates.
539 for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
540 // If the header of the loop containing this basic block is a landing pad,
541 // then don't try to hoist instructions out of this loop.
542 const MachineLoop *ML = MLI->getLoopFor(BB);
543 if (ML && ML->getHeader()->isEHPad()) continue;
544
545 // Conservatively treat live-in's as an external def.
546 // FIXME: That means a reload that're reused in successor block(s) will not
547 // be LICM'ed.
548 for (const auto &LI : BB->liveins()) {
549 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI)
550 PhysRegDefs.set(*AI);
551 }
552
553 SpeculationState = SpeculateUnknown;
554 for (MachineInstr &MI : *BB)
555 ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates);
556 }
557
558 // Gather the registers read / clobbered by the terminator.
559 BitVector TermRegs(NumRegs);
560 MachineBasicBlock::iterator TI = Preheader->getFirstTerminator();
561 if (TI != Preheader->end()) {
562 for (const MachineOperand &MO : TI->operands()) {
563 if (!MO.isReg())
564 continue;
565 Register Reg = MO.getReg();
566 if (!Reg)
567 continue;
568 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
569 TermRegs.set(*AI);
570 }
571 }
572
573 // Now evaluate whether the potential candidates qualify.
574 // 1. Check if the candidate defined register is defined by another
575 // instruction in the loop.
576 // 2. If the candidate is a load from stack slot (always true for now),
577 // check if the slot is stored anywhere in the loop.
578 // 3. Make sure candidate def should not clobber
579 // registers read by the terminator. Similarly its def should not be
580 // clobbered by the terminator.
581 for (CandidateInfo &Candidate : Candidates) {
582 if (Candidate.FI != std::numeric_limits<int>::min() &&
583 StoredFIs.count(Candidate.FI))
584 continue;
585
586 unsigned Def = Candidate.Def;
587 if (!PhysRegClobbers.test(Def) && !TermRegs.test(Def)) {
588 bool Safe = true;
589 MachineInstr *MI = Candidate.MI;
590 for (const MachineOperand &MO : MI->operands()) {
591 if (!MO.isReg() || MO.isDef() || !MO.getReg())
592 continue;
593 Register Reg = MO.getReg();
594 if (PhysRegDefs.test(Reg) ||
595 PhysRegClobbers.test(Reg)) {
596 // If it's using a non-loop-invariant register, then it's obviously
597 // not safe to hoist.
598 Safe = false;
599 break;
600 }
601 }
602 if (Safe)
603 HoistPostRA(MI, Candidate.Def);
604 }
605 }
606 }
607
608 /// Add register 'Reg' to the livein sets of BBs in the current loop, and make
609 /// sure it is not killed by any instructions in the loop.
AddToLiveIns(MCRegister Reg)610 void MachineLICMBase::AddToLiveIns(MCRegister Reg) {
611 for (MachineBasicBlock *BB : CurLoop->getBlocks()) {
612 if (!BB->isLiveIn(Reg))
613 BB->addLiveIn(Reg);
614 for (MachineInstr &MI : *BB) {
615 for (MachineOperand &MO : MI.operands()) {
616 if (!MO.isReg() || !MO.getReg() || MO.isDef()) continue;
617 if (MO.getReg() == Reg || TRI->isSuperRegister(Reg, MO.getReg()))
618 MO.setIsKill(false);
619 }
620 }
621 }
622 }
623
624 /// When an instruction is found to only use loop invariant operands that is
625 /// safe to hoist, this instruction is called to do the dirty work.
HoistPostRA(MachineInstr * MI,unsigned Def)626 void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def) {
627 MachineBasicBlock *Preheader = getCurPreheader();
628
629 // Now move the instructions to the predecessor, inserting it before any
630 // terminator instructions.
631 LLVM_DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader)
632 << " from " << printMBBReference(*MI->getParent()) << ": "
633 << *MI);
634
635 // Splice the instruction to the preheader.
636 MachineBasicBlock *MBB = MI->getParent();
637 Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);
638
639 // Since we are moving the instruction out of its basic block, we do not
640 // retain its debug location. Doing so would degrade the debugging
641 // experience and adversely affect the accuracy of profiling information.
642 assert(!MI->isDebugInstr() && "Should not hoist debug inst");
643 MI->setDebugLoc(DebugLoc());
644
645 // Add register to livein list to all the BBs in the current loop since a
646 // loop invariant must be kept live throughout the whole loop. This is
647 // important to ensure later passes do not scavenge the def register.
648 AddToLiveIns(Def);
649
650 ++NumPostRAHoisted;
651 Changed = true;
652 }
653
654 /// Check if this mbb is guaranteed to execute. If not then a load from this mbb
655 /// may not be safe to hoist.
IsGuaranteedToExecute(MachineBasicBlock * BB)656 bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) {
657 if (SpeculationState != SpeculateUnknown)
658 return SpeculationState == SpeculateFalse;
659
660 if (BB != CurLoop->getHeader()) {
661 // Check loop exiting blocks.
662 SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;
663 CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);
664 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)
665 if (!DT->dominates(BB, CurrentLoopExitingBlock)) {
666 SpeculationState = SpeculateTrue;
667 return false;
668 }
669 }
670
671 SpeculationState = SpeculateFalse;
672 return true;
673 }
674
EnterScope(MachineBasicBlock * MBB)675 void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) {
676 LLVM_DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');
677
678 // Remember livein register pressure.
679 BackTrace.push_back(RegPressure);
680 }
681
ExitScope(MachineBasicBlock * MBB)682 void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) {
683 LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
684 BackTrace.pop_back();
685 }
686
687 /// Destroy scope for the MBB that corresponds to the given dominator tree node
688 /// if its a leaf or all of its children are done. Walk up the dominator tree to
689 /// destroy ancestors which are now done.
ExitScopeIfDone(MachineDomTreeNode * Node,DenseMap<MachineDomTreeNode *,unsigned> & OpenChildren,DenseMap<MachineDomTreeNode *,MachineDomTreeNode * > & ParentMap)690 void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
691 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
692 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
693 if (OpenChildren[Node])
694 return;
695
696 // Pop scope.
697 ExitScope(Node->getBlock());
698
699 // Now traverse upwards to pop ancestors whose offsprings are all done.
700 while (MachineDomTreeNode *Parent = ParentMap[Node]) {
701 unsigned Left = --OpenChildren[Parent];
702 if (Left != 0)
703 break;
704 ExitScope(Parent->getBlock());
705 Node = Parent;
706 }
707 }
708
709 /// Walk the specified loop in the CFG (defined by all blocks dominated by the
710 /// specified header block, and that are in the current loop) in depth first
711 /// order w.r.t the DominatorTree. This allows us to visit definitions before
712 /// uses, allowing us to hoist a loop body in one pass without iteration.
HoistOutOfLoop(MachineDomTreeNode * HeaderN)713 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
714 MachineBasicBlock *Preheader = getCurPreheader();
715 if (!Preheader)
716 return;
717
718 SmallVector<MachineDomTreeNode*, 32> Scopes;
719 SmallVector<MachineDomTreeNode*, 8> WorkList;
720 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
721 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
722
723 // Perform a DFS walk to determine the order of visit.
724 WorkList.push_back(HeaderN);
725 while (!WorkList.empty()) {
726 MachineDomTreeNode *Node = WorkList.pop_back_val();
727 assert(Node && "Null dominator tree node?");
728 MachineBasicBlock *BB = Node->getBlock();
729
730 // If the header of the loop containing this basic block is a landing pad,
731 // then don't try to hoist instructions out of this loop.
732 const MachineLoop *ML = MLI->getLoopFor(BB);
733 if (ML && ML->getHeader()->isEHPad())
734 continue;
735
736 // If this subregion is not in the top level loop at all, exit.
737 if (!CurLoop->contains(BB))
738 continue;
739
740 Scopes.push_back(Node);
741 unsigned NumChildren = Node->getNumChildren();
742
743 // Don't hoist things out of a large switch statement. This often causes
744 // code to be hoisted that wasn't going to be executed, and increases
745 // register pressure in a situation where it's likely to matter.
746 if (BB->succ_size() >= 25)
747 NumChildren = 0;
748
749 OpenChildren[Node] = NumChildren;
750 if (NumChildren) {
751 // Add children in reverse order as then the next popped worklist node is
752 // the first child of this node. This means we ultimately traverse the
753 // DOM tree in exactly the same order as if we'd recursed.
754 for (MachineDomTreeNode *Child : reverse(Node->children())) {
755 ParentMap[Child] = Node;
756 WorkList.push_back(Child);
757 }
758 }
759 }
760
761 if (Scopes.size() == 0)
762 return;
763
764 // Compute registers which are livein into the loop headers.
765 RegSeen.clear();
766 BackTrace.clear();
767 InitRegPressure(Preheader);
768
769 // Now perform LICM.
770 for (MachineDomTreeNode *Node : Scopes) {
771 MachineBasicBlock *MBB = Node->getBlock();
772
773 EnterScope(MBB);
774
775 // Process the block
776 SpeculationState = SpeculateUnknown;
777 for (MachineBasicBlock::iterator
778 MII = MBB->begin(), E = MBB->end(); MII != E; ) {
779 MachineBasicBlock::iterator NextMII = MII; ++NextMII;
780 MachineInstr *MI = &*MII;
781 if (!Hoist(MI, Preheader))
782 UpdateRegPressure(MI);
783 // If we have hoisted an instruction that may store, it can only be a
784 // constant store.
785 MII = NextMII;
786 }
787
788 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
789 ExitScopeIfDone(Node, OpenChildren, ParentMap);
790 }
791 }
792
793 /// Sink instructions into loops if profitable. This especially tries to prevent
794 /// register spills caused by register pressure if there is little to no
795 /// overhead moving instructions into loops.
SinkIntoLoop()796 void MachineLICMBase::SinkIntoLoop() {
797 MachineBasicBlock *Preheader = getCurPreheader();
798 if (!Preheader)
799 return;
800
801 SmallVector<MachineInstr *, 8> Candidates;
802 for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin();
803 I != Preheader->instr_end(); ++I) {
804 // We need to ensure that we can safely move this instruction into the loop.
805 // As such, it must not have side-effects, e.g. such as a call has.
806 if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(&*I))
807 Candidates.push_back(&*I);
808 }
809
810 for (MachineInstr *I : Candidates) {
811 const MachineOperand &MO = I->getOperand(0);
812 if (!MO.isDef() || !MO.isReg() || !MO.getReg())
813 continue;
814 if (!MRI->hasOneDef(MO.getReg()))
815 continue;
816 bool CanSink = true;
817 MachineBasicBlock *B = nullptr;
818 for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
819 // FIXME: Come up with a proper cost model that estimates whether sinking
820 // the instruction (and thus possibly executing it on every loop
821 // iteration) is more expensive than a register.
822 // For now assumes that copies are cheap and thus almost always worth it.
823 if (!MI.isCopy()) {
824 CanSink = false;
825 break;
826 }
827 if (!B) {
828 B = MI.getParent();
829 continue;
830 }
831 B = DT->findNearestCommonDominator(B, MI.getParent());
832 if (!B) {
833 CanSink = false;
834 break;
835 }
836 }
837 if (!CanSink || !B || B == Preheader)
838 continue;
839
840 LLVM_DEBUG(dbgs() << "Sinking to " << printMBBReference(*B) << " from "
841 << printMBBReference(*I->getParent()) << ": " << *I);
842 B->splice(B->getFirstNonPHI(), Preheader, I);
843
844 // The instruction is is moved from its basic block, so do not retain the
845 // debug information.
846 assert(!I->isDebugInstr() && "Should not sink debug inst");
847 I->setDebugLoc(DebugLoc());
848 }
849 }
850
isOperandKill(const MachineOperand & MO,MachineRegisterInfo * MRI)851 static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
852 return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
853 }
854
855 /// Find all virtual register references that are liveout of the preheader to
856 /// initialize the starting "register pressure". Note this does not count live
857 /// through (livein but not used) registers.
InitRegPressure(MachineBasicBlock * BB)858 void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) {
859 std::fill(RegPressure.begin(), RegPressure.end(), 0);
860
861 // If the preheader has only a single predecessor and it ends with a
862 // fallthrough or an unconditional branch, then scan its predecessor for live
863 // defs as well. This happens whenever the preheader is created by splitting
864 // the critical edge from the loop predecessor to the loop header.
865 if (BB->pred_size() == 1) {
866 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
867 SmallVector<MachineOperand, 4> Cond;
868 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
869 InitRegPressure(*BB->pred_begin());
870 }
871
872 for (const MachineInstr &MI : *BB)
873 UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
874 }
875
876 /// Update estimate of register pressure after the specified instruction.
UpdateRegPressure(const MachineInstr * MI,bool ConsiderUnseenAsDef)877 void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
878 bool ConsiderUnseenAsDef) {
879 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
880 for (const auto &RPIdAndCost : Cost) {
881 unsigned Class = RPIdAndCost.first;
882 if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second)
883 RegPressure[Class] = 0;
884 else
885 RegPressure[Class] += RPIdAndCost.second;
886 }
887 }
888
889 /// Calculate the additional register pressure that the registers used in MI
890 /// cause.
891 ///
892 /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
893 /// figure out which usages are live-ins.
894 /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
895 DenseMap<unsigned, int>
calcRegisterCost(const MachineInstr * MI,bool ConsiderSeen,bool ConsiderUnseenAsDef)896 MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
897 bool ConsiderUnseenAsDef) {
898 DenseMap<unsigned, int> Cost;
899 if (MI->isImplicitDef())
900 return Cost;
901 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
902 const MachineOperand &MO = MI->getOperand(i);
903 if (!MO.isReg() || MO.isImplicit())
904 continue;
905 Register Reg = MO.getReg();
906 if (!Register::isVirtualRegister(Reg))
907 continue;
908
909 // FIXME: It seems bad to use RegSeen only for some of these calculations.
910 bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;
911 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
912
913 RegClassWeight W = TRI->getRegClassWeight(RC);
914 int RCCost = 0;
915 if (MO.isDef())
916 RCCost = W.RegWeight;
917 else {
918 bool isKill = isOperandKill(MO, MRI);
919 if (isNew && !isKill && ConsiderUnseenAsDef)
920 // Haven't seen this, it must be a livein.
921 RCCost = W.RegWeight;
922 else if (!isNew && isKill)
923 RCCost = -W.RegWeight;
924 }
925 if (RCCost == 0)
926 continue;
927 const int *PS = TRI->getRegClassPressureSets(RC);
928 for (; *PS != -1; ++PS) {
929 if (Cost.find(*PS) == Cost.end())
930 Cost[*PS] = RCCost;
931 else
932 Cost[*PS] += RCCost;
933 }
934 }
935 return Cost;
936 }
937
938 /// Return true if this machine instruction loads from global offset table or
939 /// constant pool.
mayLoadFromGOTOrConstantPool(MachineInstr & MI)940 static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
941 assert(MI.mayLoad() && "Expected MI that loads!");
942
943 // If we lost memory operands, conservatively assume that the instruction
944 // reads from everything..
945 if (MI.memoperands_empty())
946 return true;
947
948 for (MachineMemOperand *MemOp : MI.memoperands())
949 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
950 if (PSV->isGOT() || PSV->isConstantPool())
951 return true;
952
953 return false;
954 }
955
956 // This function iterates through all the operands of the input store MI and
957 // checks that each register operand statisfies isCallerPreservedPhysReg.
958 // This means, the value being stored and the address where it is being stored
959 // is constant throughout the body of the function (not including prologue and
960 // epilogue). When called with an MI that isn't a store, it returns false.
961 // A future improvement can be to check if the store registers are constant
962 // throughout the loop rather than throughout the funtion.
isInvariantStore(const MachineInstr & MI,const TargetRegisterInfo * TRI,const MachineRegisterInfo * MRI)963 static bool isInvariantStore(const MachineInstr &MI,
964 const TargetRegisterInfo *TRI,
965 const MachineRegisterInfo *MRI) {
966
967 bool FoundCallerPresReg = false;
968 if (!MI.mayStore() || MI.hasUnmodeledSideEffects() ||
969 (MI.getNumOperands() == 0))
970 return false;
971
972 // Check that all register operands are caller-preserved physical registers.
973 for (const MachineOperand &MO : MI.operands()) {
974 if (MO.isReg()) {
975 Register Reg = MO.getReg();
976 // If operand is a virtual register, check if it comes from a copy of a
977 // physical register.
978 if (Register::isVirtualRegister(Reg))
979 Reg = TRI->lookThruCopyLike(MO.getReg(), MRI);
980 if (Register::isVirtualRegister(Reg))
981 return false;
982 if (!TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *MI.getMF()))
983 return false;
984 else
985 FoundCallerPresReg = true;
986 } else if (!MO.isImm()) {
987 return false;
988 }
989 }
990 return FoundCallerPresReg;
991 }
992
993 // Return true if the input MI is a copy instruction that feeds an invariant
994 // store instruction. This means that the src of the copy has to satisfy
995 // isCallerPreservedPhysReg and atleast one of it's users should satisfy
996 // isInvariantStore.
isCopyFeedingInvariantStore(const MachineInstr & MI,const MachineRegisterInfo * MRI,const TargetRegisterInfo * TRI)997 static bool isCopyFeedingInvariantStore(const MachineInstr &MI,
998 const MachineRegisterInfo *MRI,
999 const TargetRegisterInfo *TRI) {
1000
1001 // FIXME: If targets would like to look through instructions that aren't
1002 // pure copies, this can be updated to a query.
1003 if (!MI.isCopy())
1004 return false;
1005
1006 const MachineFunction *MF = MI.getMF();
1007 // Check that we are copying a constant physical register.
1008 Register CopySrcReg = MI.getOperand(1).getReg();
1009 if (Register::isVirtualRegister(CopySrcReg))
1010 return false;
1011
1012 if (!TRI->isCallerPreservedPhysReg(CopySrcReg.asMCReg(), *MF))
1013 return false;
1014
1015 Register CopyDstReg = MI.getOperand(0).getReg();
1016 // Check if any of the uses of the copy are invariant stores.
1017 assert(Register::isVirtualRegister(CopyDstReg) &&
1018 "copy dst is not a virtual reg");
1019
1020 for (MachineInstr &UseMI : MRI->use_instructions(CopyDstReg)) {
1021 if (UseMI.mayStore() && isInvariantStore(UseMI, TRI, MRI))
1022 return true;
1023 }
1024 return false;
1025 }
1026
1027 /// Returns true if the instruction may be a suitable candidate for LICM.
1028 /// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
IsLICMCandidate(MachineInstr & I)1029 bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
1030 // Check if it's safe to move the instruction.
1031 bool DontMoveAcrossStore = true;
1032 if ((!I.isSafeToMove(AA, DontMoveAcrossStore)) &&
1033 !(HoistConstStores && isInvariantStore(I, TRI, MRI))) {
1034 return false;
1035 }
1036
1037 // If it is load then check if it is guaranteed to execute by making sure that
1038 // it dominates all exiting blocks. If it doesn't, then there is a path out of
1039 // the loop which does not execute this load, so we can't hoist it. Loads
1040 // from constant memory are not safe to speculate all the time, for example
1041 // indexed load from a jump table.
1042 // Stores and side effects are already checked by isSafeToMove.
1043 if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&
1044 !IsGuaranteedToExecute(I.getParent()))
1045 return false;
1046
1047 // Convergent attribute has been used on operations that involve inter-thread
1048 // communication which results are implicitly affected by the enclosing
1049 // control flows. It is not safe to hoist or sink such operations across
1050 // control flow.
1051 if (I.isConvergent())
1052 return false;
1053
1054 return true;
1055 }
1056
1057 /// Returns true if the instruction is loop invariant.
1058 /// I.e., all virtual register operands are defined outside of the loop,
1059 /// physical registers aren't accessed explicitly, and there are no side
1060 /// effects that aren't captured by the operands or other flags.
IsLoopInvariantInst(MachineInstr & I)1061 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {
1062 if (!IsLICMCandidate(I))
1063 return false;
1064
1065 // The instruction is loop invariant if all of its operands are.
1066 for (const MachineOperand &MO : I.operands()) {
1067 if (!MO.isReg())
1068 continue;
1069
1070 Register Reg = MO.getReg();
1071 if (Reg == 0) continue;
1072
1073 // Don't hoist an instruction that uses or defines a physical register.
1074 if (Register::isPhysicalRegister(Reg)) {
1075 if (MO.isUse()) {
1076 // If the physreg has no defs anywhere, it's just an ambient register
1077 // and we can freely move its uses. Alternatively, if it's allocatable,
1078 // it could get allocated to something with a def during allocation.
1079 // However, if the physreg is known to always be caller saved/restored
1080 // then this use is safe to hoist.
1081 if (!MRI->isConstantPhysReg(Reg) &&
1082 !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())))
1083 return false;
1084 // Otherwise it's safe to move.
1085 continue;
1086 } else if (!MO.isDead()) {
1087 // A def that isn't dead. We can't move it.
1088 return false;
1089 } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
1090 // If the reg is live into the loop, we can't hoist an instruction
1091 // which would clobber it.
1092 return false;
1093 }
1094 }
1095
1096 if (!MO.isUse())
1097 continue;
1098
1099 assert(MRI->getVRegDef(Reg) &&
1100 "Machine instr not mapped for this vreg?!");
1101
1102 // If the loop contains the definition of an operand, then the instruction
1103 // isn't loop invariant.
1104 if (CurLoop->contains(MRI->getVRegDef(Reg)))
1105 return false;
1106 }
1107
1108 // If we got this far, the instruction is loop invariant!
1109 return true;
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.
HasLoopPHIUse(const MachineInstr * MI) const1114 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
1115 SmallVector<const MachineInstr*, 8> Work(1, MI);
1116 do {
1117 MI = Work.pop_back_val();
1118 for (const MachineOperand &MO : MI->operands()) {
1119 if (!MO.isReg() || !MO.isDef())
1120 continue;
1121 Register Reg = MO.getReg();
1122 if (!Register::isVirtualRegister(Reg))
1123 continue;
1124 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {
1125 // A PHI may cause a copy to be inserted.
1126 if (UseMI.isPHI()) {
1127 // A PHI inside the loop causes a copy because the live range of Reg is
1128 // extended across the PHI.
1129 if (CurLoop->contains(&UseMI))
1130 return true;
1131 // A PHI in an exit block can cause a copy to be inserted if the PHI
1132 // has multiple predecessors in the loop with different values.
1133 // For now, approximate by rejecting all exit blocks.
1134 if (isExitBlock(UseMI.getParent()))
1135 return true;
1136 continue;
1137 }
1138 // Look past copies as well.
1139 if (UseMI.isCopy() && CurLoop->contains(&UseMI))
1140 Work.push_back(&UseMI);
1141 }
1142 }
1143 } while (!Work.empty());
1144 return false;
1145 }
1146
1147 /// Compute operand latency between a def of 'Reg' and an use in the current
1148 /// loop, return true if the target considered it high.
HasHighOperandLatency(MachineInstr & MI,unsigned DefIdx,Register Reg) const1149 bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,
1150 Register Reg) 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.
IsCheapInstruction(MachineInstr & MI) const1180 bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const {
1181 if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike())
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 (Register::isPhysicalRegister(Reg))
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.
1205 bool
CanCauseHighRegPressure(const DenseMap<unsigned,int> & Cost,bool CheapInstr)1206 MachineLICMBase::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
1207 bool CheapInstr) {
1208 for (const auto &RPIdAndCost : Cost) {
1209 if (RPIdAndCost.second <= 0)
1210 continue;
1211
1212 unsigned Class = RPIdAndCost.first;
1213 int Limit = RegLimit[Class];
1214
1215 // Don't hoist cheap instructions if they would increase register pressure,
1216 // even if we're under the limit.
1217 if (CheapInstr && !HoistCheapInsts)
1218 return true;
1219
1220 for (const auto &RP : BackTrace)
1221 if (static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit)
1222 return true;
1223 }
1224
1225 return false;
1226 }
1227
1228 /// Traverse the back trace from header to the current block and update their
1229 /// register pressures to reflect the effect of hoisting MI from the current
1230 /// block to the preheader.
UpdateBackTraceRegPressure(const MachineInstr * MI)1231 void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) {
1232 // First compute the 'cost' of the instruction, i.e. its contribution
1233 // to register pressure.
1234 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
1235 /*ConsiderUnseenAsDef=*/false);
1236
1237 // Update register pressure of blocks from loop header to current block.
1238 for (auto &RP : BackTrace)
1239 for (const auto &RPIdAndCost : Cost)
1240 RP[RPIdAndCost.first] += RPIdAndCost.second;
1241 }
1242
1243 /// Return true if it is potentially profitable to hoist the given loop
1244 /// invariant.
IsProfitableToHoist(MachineInstr & MI)1245 bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
1246 if (MI.isImplicitDef())
1247 return true;
1248
1249 // Besides removing computation from the loop, hoisting an instruction has
1250 // these effects:
1251 //
1252 // - The value defined by the instruction becomes live across the entire
1253 // loop. This increases register pressure in the loop.
1254 //
1255 // - If the value is used by a PHI in the loop, a copy will be required for
1256 // lowering the PHI after extending the live range.
1257 //
1258 // - When hoisting the last use of a value in the loop, that value no longer
1259 // needs to be live in the loop. This lowers register pressure in the loop.
1260
1261 if (HoistConstStores && isCopyFeedingInvariantStore(MI, MRI, TRI))
1262 return true;
1263
1264 bool CheapInstr = IsCheapInstruction(MI);
1265 bool CreatesCopy = HasLoopPHIUse(&MI);
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 // Rematerializable instructions should always be hoisted since the register
1274 // allocator can just pull them down again when needed.
1275 if (TII->isTriviallyReMaterializable(MI, AA))
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 (!Register::isVirtualRegister(Reg))
1286 continue;
1287 if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) {
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 (AvoidSpeculation &&
1321 (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) {
1322 LLVM_DEBUG(dbgs() << "Won't speculate: " << MI);
1323 return false;
1324 }
1325
1326 // High register pressure situation, only hoist if the instruction is going
1327 // to be remat'ed.
1328 if (!TII->isTriviallyReMaterializable(MI, AA) &&
1329 !MI.isDereferenceableInvariantLoad(AA)) {
1330 LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);
1331 return false;
1332 }
1333
1334 return true;
1335 }
1336
1337 /// Unfold a load from the given machineinstr if the load itself could be
1338 /// hoisted. Return the unfolded and hoistable load, or null if the load
1339 /// couldn't be unfolded or if it wouldn't be hoistable.
ExtractHoistableLoad(MachineInstr * MI)1340 MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
1341 // Don't unfold simple loads.
1342 if (MI->canFoldAsLoad())
1343 return nullptr;
1344
1345 // If not, we may be able to unfold a load and hoist that.
1346 // First test whether the instruction is loading from an amenable
1347 // memory location.
1348 if (!MI->isDereferenceableInvariantLoad(AA))
1349 return nullptr;
1350
1351 // Next determine the register class for a temporary register.
1352 unsigned LoadRegIndex;
1353 unsigned NewOpc =
1354 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),
1355 /*UnfoldLoad=*/true,
1356 /*UnfoldStore=*/false,
1357 &LoadRegIndex);
1358 if (NewOpc == 0) return nullptr;
1359 const MCInstrDesc &MID = TII->get(NewOpc);
1360 MachineFunction &MF = *MI->getMF();
1361 const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF);
1362 // Ok, we're unfolding. Create a temporary register and do the unfold.
1363 Register Reg = MRI->createVirtualRegister(RC);
1364
1365 SmallVector<MachineInstr *, 2> NewMIs;
1366 bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,
1367 /*UnfoldLoad=*/true,
1368 /*UnfoldStore=*/false, NewMIs);
1369 (void)Success;
1370 assert(Success &&
1371 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "
1372 "succeeded!");
1373 assert(NewMIs.size() == 2 &&
1374 "Unfolded a load into multiple instructions!");
1375 MachineBasicBlock *MBB = MI->getParent();
1376 MachineBasicBlock::iterator Pos = MI;
1377 MBB->insert(Pos, NewMIs[0]);
1378 MBB->insert(Pos, NewMIs[1]);
1379 // If unfolding produced a load that wasn't loop-invariant or profitable to
1380 // hoist, discard the new instructions and bail.
1381 if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) {
1382 NewMIs[0]->eraseFromParent();
1383 NewMIs[1]->eraseFromParent();
1384 return nullptr;
1385 }
1386
1387 // Update register pressure for the unfolded instruction.
1388 UpdateRegPressure(NewMIs[1]);
1389
1390 // Otherwise we successfully unfolded a load that we can hoist.
1391
1392 // Update the call site info.
1393 if (MI->shouldUpdateCallSiteInfo())
1394 MF.eraseCallSiteInfo(MI);
1395
1396 MI->eraseFromParent();
1397 return NewMIs[0];
1398 }
1399
1400 /// Initialize the CSE map with instructions that are in the current loop
1401 /// preheader that may become duplicates of instructions that are hoisted
1402 /// out of the loop.
InitCSEMap(MachineBasicBlock * BB)1403 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
1404 for (MachineInstr &MI : *BB)
1405 CSEMap[MI.getOpcode()].push_back(&MI);
1406 }
1407
1408 /// Find an instruction amount PrevMIs that is a duplicate of MI.
1409 /// Return this instruction if it's found.
1410 const MachineInstr*
LookForDuplicate(const MachineInstr * MI,std::vector<const MachineInstr * > & PrevMIs)1411 MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
1412 std::vector<const MachineInstr*> &PrevMIs) {
1413 for (const MachineInstr *PrevMI : PrevMIs)
1414 if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
1415 return PrevMI;
1416
1417 return nullptr;
1418 }
1419
1420 /// Given a LICM'ed instruction, look for an instruction on the preheader that
1421 /// computes the same value. If it's found, do a RAU on with the definition of
1422 /// the existing instruction rather than hoisting the instruction to the
1423 /// preheader.
EliminateCSE(MachineInstr * MI,DenseMap<unsigned,std::vector<const MachineInstr * >>::iterator & CI)1424 bool MachineLICMBase::EliminateCSE(MachineInstr *MI,
1425 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI) {
1426 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1427 // the undef property onto uses.
1428 if (CI == CSEMap.end() || MI->isImplicitDef())
1429 return false;
1430
1431 if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
1432 LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
1433
1434 // Replace virtual registers defined by MI by their counterparts defined
1435 // by Dup.
1436 SmallVector<unsigned, 2> Defs;
1437 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1438 const MachineOperand &MO = MI->getOperand(i);
1439
1440 // Physical registers may not differ here.
1441 assert((!MO.isReg() || MO.getReg() == 0 ||
1442 !Register::isPhysicalRegister(MO.getReg()) ||
1443 MO.getReg() == Dup->getOperand(i).getReg()) &&
1444 "Instructions with different phys regs are not identical!");
1445
1446 if (MO.isReg() && MO.isDef() &&
1447 !Register::isPhysicalRegister(MO.getReg()))
1448 Defs.push_back(i);
1449 }
1450
1451 SmallVector<const TargetRegisterClass*, 2> OrigRCs;
1452 for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
1453 unsigned Idx = Defs[i];
1454 Register Reg = MI->getOperand(Idx).getReg();
1455 Register DupReg = Dup->getOperand(Idx).getReg();
1456 OrigRCs.push_back(MRI->getRegClass(DupReg));
1457
1458 if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {
1459 // Restore old RCs if more than one defs.
1460 for (unsigned j = 0; j != i; ++j)
1461 MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);
1462 return false;
1463 }
1464 }
1465
1466 for (unsigned Idx : Defs) {
1467 Register Reg = MI->getOperand(Idx).getReg();
1468 Register DupReg = Dup->getOperand(Idx).getReg();
1469 MRI->replaceRegWith(Reg, DupReg);
1470 MRI->clearKillFlags(DupReg);
1471 }
1472
1473 MI->eraseFromParent();
1474 ++NumCSEed;
1475 return true;
1476 }
1477 return false;
1478 }
1479
1480 /// Return true if the given instruction will be CSE'd if it's hoisted out of
1481 /// the loop.
MayCSE(MachineInstr * MI)1482 bool MachineLICMBase::MayCSE(MachineInstr *MI) {
1483 unsigned Opcode = MI->getOpcode();
1484 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
1485 CI = CSEMap.find(Opcode);
1486 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
1487 // the undef property onto uses.
1488 if (CI == CSEMap.end() || MI->isImplicitDef())
1489 return false;
1490
1491 return LookForDuplicate(MI, CI->second) != nullptr;
1492 }
1493
1494 /// When an instruction is found to use only loop invariant operands
1495 /// that are safe to hoist, this instruction is called to do the dirty work.
1496 /// It returns true if the instruction is hoisted.
Hoist(MachineInstr * MI,MachineBasicBlock * Preheader)1497 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
1498 MachineBasicBlock *SrcBlock = MI->getParent();
1499
1500 // Disable the instruction hoisting due to block hotness
1501 if ((DisableHoistingToHotterBlocks == UseBFI::All ||
1502 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) &&
1503 isTgtHotterThanSrc(SrcBlock, Preheader)) {
1504 ++NumNotHoistedDueToHotness;
1505 return false;
1506 }
1507 // First check whether we should hoist this instruction.
1508 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
1509 // If not, try unfolding a hoistable load.
1510 MI = ExtractHoistableLoad(MI);
1511 if (!MI) return false;
1512 }
1513
1514 // If we have hoisted an instruction that may store, it can only be a constant
1515 // store.
1516 if (MI->mayStore())
1517 NumStoreConst++;
1518
1519 // Now move the instructions to the predecessor, inserting it before any
1520 // terminator instructions.
1521 LLVM_DEBUG({
1522 dbgs() << "Hoisting " << *MI;
1523 if (MI->getParent()->getBasicBlock())
1524 dbgs() << " from " << printMBBReference(*MI->getParent());
1525 if (Preheader->getBasicBlock())
1526 dbgs() << " to " << printMBBReference(*Preheader);
1527 dbgs() << "\n";
1528 });
1529
1530 // If this is the first instruction being hoisted to the preheader,
1531 // initialize the CSE map with potential common expressions.
1532 if (FirstInLoop) {
1533 InitCSEMap(Preheader);
1534 FirstInLoop = false;
1535 }
1536
1537 // Look for opportunity to CSE the hoisted instruction.
1538 unsigned Opcode = MI->getOpcode();
1539 DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
1540 CI = CSEMap.find(Opcode);
1541 if (!EliminateCSE(MI, CI)) {
1542 // Otherwise, splice the instruction to the preheader.
1543 Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
1544
1545 // Since we are moving the instruction out of its basic block, we do not
1546 // retain its debug location. Doing so would degrade the debugging
1547 // experience and adversely affect the accuracy of profiling information.
1548 assert(!MI->isDebugInstr() && "Should not hoist debug inst");
1549 MI->setDebugLoc(DebugLoc());
1550
1551 // Update register pressure for BBs from header to this block.
1552 UpdateBackTraceRegPressure(MI);
1553
1554 // Clear the kill flags of any register this instruction defines,
1555 // since they may need to be live throughout the entire loop
1556 // rather than just live for part of it.
1557 for (MachineOperand &MO : MI->operands())
1558 if (MO.isReg() && MO.isDef() && !MO.isDead())
1559 MRI->clearKillFlags(MO.getReg());
1560
1561 // Add to the CSE map.
1562 if (CI != CSEMap.end())
1563 CI->second.push_back(MI);
1564 else
1565 CSEMap[Opcode].push_back(MI);
1566 }
1567
1568 ++NumHoisted;
1569 Changed = true;
1570
1571 return true;
1572 }
1573
1574 /// Get the preheader for the current loop, splitting a critical edge if needed.
getCurPreheader()1575 MachineBasicBlock *MachineLICMBase::getCurPreheader() {
1576 // Determine the block to which to hoist instructions. If we can't find a
1577 // suitable loop predecessor, we can't do any hoisting.
1578
1579 // If we've tried to get a preheader and failed, don't try again.
1580 if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1))
1581 return nullptr;
1582
1583 if (!CurPreheader) {
1584 CurPreheader = CurLoop->getLoopPreheader();
1585 if (!CurPreheader) {
1586 MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
1587 if (!Pred) {
1588 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1589 return nullptr;
1590 }
1591
1592 CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this);
1593 if (!CurPreheader) {
1594 CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
1595 return nullptr;
1596 }
1597 }
1598 }
1599 return CurPreheader;
1600 }
1601
1602 /// Is the target basic block at least "BlockFrequencyRatioThreshold"
1603 /// times hotter than the source basic block.
isTgtHotterThanSrc(MachineBasicBlock * SrcBlock,MachineBasicBlock * TgtBlock)1604 bool MachineLICMBase::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,
1605 MachineBasicBlock *TgtBlock) {
1606 // Parse source and target basic block frequency from MBFI
1607 uint64_t SrcBF = MBFI->getBlockFreq(SrcBlock).getFrequency();
1608 uint64_t DstBF = MBFI->getBlockFreq(TgtBlock).getFrequency();
1609
1610 // Disable the hoisting if source block frequency is zero
1611 if (!SrcBF)
1612 return true;
1613
1614 double Ratio = (double)DstBF / SrcBF;
1615
1616 // Compare the block frequency ratio with the threshold
1617 return Ratio > BlockFrequencyRatioThreshold;
1618 }
1619