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