/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineLICM.cpp
Line | Count | Source (jump to first uncovered line) |
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/TargetSchedule.h" |
38 | | #include "llvm/IR/DebugLoc.h" |
39 | | #include "llvm/MC/MCInstrDesc.h" |
40 | | #include "llvm/MC/MCRegisterInfo.h" |
41 | | #include "llvm/Pass.h" |
42 | | #include "llvm/Support/Casting.h" |
43 | | #include "llvm/Support/CommandLine.h" |
44 | | #include "llvm/Support/Debug.h" |
45 | | #include "llvm/Support/raw_ostream.h" |
46 | | #include "llvm/Target/TargetInstrInfo.h" |
47 | | #include "llvm/Target/TargetLowering.h" |
48 | | #include "llvm/Target/TargetRegisterInfo.h" |
49 | | #include "llvm/Target/TargetSubtargetInfo.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 | | |
75 | | STATISTIC(NumHoisted, |
76 | | "Number of machine instructions hoisted out of loops"); |
77 | | STATISTIC(NumLowRP, |
78 | | "Number of instructions hoisted in low reg pressure situation"); |
79 | | STATISTIC(NumHighLatency, |
80 | | "Number of high latency instructions hoisted"); |
81 | | STATISTIC(NumCSEed, |
82 | | "Number of hoisted machine instructions CSEed"); |
83 | | STATISTIC(NumPostRAHoisted, |
84 | | "Number of machine instructions hoisted out of loops post regalloc"); |
85 | | |
86 | | namespace { |
87 | | |
88 | | class MachineLICM : public MachineFunctionPass { |
89 | | const TargetInstrInfo *TII; |
90 | | const TargetLoweringBase *TLI; |
91 | | const TargetRegisterInfo *TRI; |
92 | | const MachineFrameInfo *MFI; |
93 | | MachineRegisterInfo *MRI; |
94 | | TargetSchedModel SchedModel; |
95 | | bool PreRegAlloc = true; |
96 | | |
97 | | // Various analyses that we use... |
98 | | AliasAnalysis *AA; // Alias analysis info. |
99 | | MachineLoopInfo *MLI; // Current MachineLoopInfo |
100 | | MachineDominatorTree *DT; // Machine dominator tree for the cur loop |
101 | | |
102 | | // State that is updated as we process loops |
103 | | bool Changed; // True if a loop is changed. |
104 | | bool FirstInLoop; // True if it's the first LICM in the loop. |
105 | | MachineLoop *CurLoop; // The current loop we are working on. |
106 | | MachineBasicBlock *CurPreheader; // The preheader for CurLoop. |
107 | | |
108 | | // Exit blocks for CurLoop. |
109 | | SmallVector<MachineBasicBlock *, 8> ExitBlocks; |
110 | | |
111 | 21.5k | bool isExitBlock(const MachineBasicBlock *MBB) const { |
112 | 21.5k | return is_contained(ExitBlocks, MBB); |
113 | 21.5k | } |
114 | | |
115 | | // Track 'estimated' register pressure. |
116 | | SmallSet<unsigned, 32> RegSeen; |
117 | | SmallVector<unsigned, 8> RegPressure; |
118 | | |
119 | | // Register pressure "limit" per register pressure set. If the pressure |
120 | | // is higher than the limit, then it's considered high. |
121 | | SmallVector<unsigned, 8> RegLimit; |
122 | | |
123 | | // Register pressure on path leading from loop preheader to current BB. |
124 | | SmallVector<SmallVector<unsigned, 8>, 16> BackTrace; |
125 | | |
126 | | // For each opcode, keep a list of potential CSE instructions. |
127 | | DenseMap<unsigned, std::vector<const MachineInstr *>> CSEMap; |
128 | | |
129 | | enum { |
130 | | SpeculateFalse = 0, |
131 | | SpeculateTrue = 1, |
132 | | SpeculateUnknown = 2 |
133 | | }; |
134 | | |
135 | | // If a MBB does not dominate loop exiting blocks then it may not safe |
136 | | // to hoist loads from this block. |
137 | | // Tri-state: 0 - false, 1 - true, 2 - unknown |
138 | | unsigned SpeculationState; |
139 | | |
140 | | public: |
141 | | static char ID; // Pass identification, replacement for typeid |
142 | | |
143 | 65.3k | MachineLICM() : MachineFunctionPass(ID) { |
144 | 65.3k | initializeMachineLICMPass(*PassRegistry::getPassRegistry()); |
145 | 65.3k | } |
146 | | |
147 | | explicit MachineLICM(bool PreRA) |
148 | 0 | : MachineFunctionPass(ID), PreRegAlloc(PreRA) { |
149 | 0 | initializeMachineLICMPass(*PassRegistry::getPassRegistry()); |
150 | 0 | } |
151 | | |
152 | | bool runOnMachineFunction(MachineFunction &MF) override; |
153 | | |
154 | 65.2k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
155 | 65.2k | AU.addRequired<MachineLoopInfo>(); |
156 | 65.2k | AU.addRequired<MachineDominatorTree>(); |
157 | 65.2k | AU.addRequired<AAResultsWrapperPass>(); |
158 | 65.2k | AU.addPreserved<MachineLoopInfo>(); |
159 | 65.2k | AU.addPreserved<MachineDominatorTree>(); |
160 | 65.2k | MachineFunctionPass::getAnalysisUsage(AU); |
161 | 65.2k | } |
162 | | |
163 | 1.19M | void releaseMemory() override { |
164 | 1.19M | RegSeen.clear(); |
165 | 1.19M | RegPressure.clear(); |
166 | 1.19M | RegLimit.clear(); |
167 | 1.19M | BackTrace.clear(); |
168 | 1.19M | CSEMap.clear(); |
169 | 1.19M | } |
170 | | |
171 | | private: |
172 | | /// Keep track of information about hoisting candidates. |
173 | | struct CandidateInfo { |
174 | | MachineInstr *MI; |
175 | | unsigned Def; |
176 | | int FI; |
177 | | |
178 | | CandidateInfo(MachineInstr *mi, unsigned def, int fi) |
179 | 36.3k | : MI(mi), Def(def), FI(fi) {} |
180 | | }; |
181 | | |
182 | | void HoistRegionPostRA(); |
183 | | |
184 | | void HoistPostRA(MachineInstr *MI, unsigned Def); |
185 | | |
186 | | void ProcessMI(MachineInstr *MI, BitVector &PhysRegDefs, |
187 | | BitVector &PhysRegClobbers, SmallSet<int, 32> &StoredFIs, |
188 | | SmallVectorImpl<CandidateInfo> &Candidates); |
189 | | |
190 | | void AddToLiveIns(unsigned Reg); |
191 | | |
192 | | bool IsLICMCandidate(MachineInstr &I); |
193 | | |
194 | | bool IsLoopInvariantInst(MachineInstr &I); |
195 | | |
196 | | bool HasLoopPHIUse(const MachineInstr *MI) const; |
197 | | |
198 | | bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, |
199 | | unsigned Reg) const; |
200 | | |
201 | | bool IsCheapInstruction(MachineInstr &MI) const; |
202 | | |
203 | | bool CanCauseHighRegPressure(const DenseMap<unsigned, int> &Cost, |
204 | | bool Cheap); |
205 | | |
206 | | void UpdateBackTraceRegPressure(const MachineInstr *MI); |
207 | | |
208 | | bool IsProfitableToHoist(MachineInstr &MI); |
209 | | |
210 | | bool IsGuaranteedToExecute(MachineBasicBlock *BB); |
211 | | |
212 | | void EnterScope(MachineBasicBlock *MBB); |
213 | | |
214 | | void ExitScope(MachineBasicBlock *MBB); |
215 | | |
216 | | void ExitScopeIfDone( |
217 | | MachineDomTreeNode *Node, |
218 | | DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren, |
219 | | DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap); |
220 | | |
221 | | void HoistOutOfLoop(MachineDomTreeNode *LoopHeaderNode); |
222 | | |
223 | | void HoistRegion(MachineDomTreeNode *N, bool IsHeader); |
224 | | |
225 | | void SinkIntoLoop(); |
226 | | |
227 | | void InitRegPressure(MachineBasicBlock *BB); |
228 | | |
229 | | DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI, |
230 | | bool ConsiderSeen, |
231 | | bool ConsiderUnseenAsDef); |
232 | | |
233 | | void UpdateRegPressure(const MachineInstr *MI, |
234 | | bool ConsiderUnseenAsDef = false); |
235 | | |
236 | | MachineInstr *ExtractHoistableLoad(MachineInstr *MI); |
237 | | |
238 | | const MachineInstr * |
239 | | LookForDuplicate(const MachineInstr *MI, |
240 | | std::vector<const MachineInstr *> &PrevMIs); |
241 | | |
242 | | bool EliminateCSE( |
243 | | MachineInstr *MI, |
244 | | DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI); |
245 | | |
246 | | bool MayCSE(MachineInstr *MI); |
247 | | |
248 | | bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader); |
249 | | |
250 | | void InitCSEMap(MachineBasicBlock *BB); |
251 | | |
252 | | MachineBasicBlock *getCurPreheader(); |
253 | | }; |
254 | | |
255 | | } // end anonymous namespace |
256 | | |
257 | | char MachineLICM::ID = 0; |
258 | | |
259 | | char &llvm::MachineLICMID = MachineLICM::ID; |
260 | | |
261 | 36.7k | INITIALIZE_PASS_BEGIN36.7k (MachineLICM, DEBUG_TYPE,
|
262 | 36.7k | "Machine Loop Invariant Code Motion", false, false) |
263 | 36.7k | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
264 | 36.7k | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
265 | 36.7k | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) |
266 | 36.7k | INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE, |
267 | | "Machine Loop Invariant Code Motion", false, false) |
268 | | |
269 | | /// Test if the given loop is the outer-most loop that has a unique predecessor. |
270 | 258k | static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) { |
271 | 258k | // Check whether this loop even has a unique predecessor. |
272 | 258k | if (!CurLoop->getLoopPredecessor()) |
273 | 2.82k | return false; |
274 | 256k | // Ok, now check to see if any of its outer loops do. |
275 | 258k | for (MachineLoop *L = CurLoop->getParentLoop(); 256k L258k ; L = L->getParentLoop()2.78k ) |
276 | 2.78k | if (2.78k L->getLoopPredecessor()2.78k ) |
277 | 0 | return false; |
278 | 256k | // None of them did, so this is the outermost with a unique predecessor. |
279 | 256k | return true; |
280 | 258k | } |
281 | | |
282 | 1.19M | bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { |
283 | 1.19M | if (skipFunction(*MF.getFunction())) |
284 | 89 | return false; |
285 | 1.19M | |
286 | 1.19M | Changed = FirstInLoop = false; |
287 | 1.19M | const TargetSubtargetInfo &ST = MF.getSubtarget(); |
288 | 1.19M | TII = ST.getInstrInfo(); |
289 | 1.19M | TLI = ST.getTargetLowering(); |
290 | 1.19M | TRI = ST.getRegisterInfo(); |
291 | 1.19M | MFI = &MF.getFrameInfo(); |
292 | 1.19M | MRI = &MF.getRegInfo(); |
293 | 1.19M | SchedModel.init(ST.getSchedModel(), &ST, TII); |
294 | 1.19M | |
295 | 1.19M | PreRegAlloc = MRI->isSSA(); |
296 | 1.19M | |
297 | 1.19M | if (PreRegAlloc) |
298 | 1.19M | DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: "); |
299 | 1.19M | else |
300 | 1.19M | DEBUG(dbgs() << "******** Post-regalloc Machine LICM: "); |
301 | 1.19M | DEBUG(dbgs() << MF.getName() << " ********\n"); |
302 | 1.19M | |
303 | 1.19M | if (PreRegAlloc1.19M ) { |
304 | 602k | // Estimate register pressure during pre-regalloc pass. |
305 | 602k | unsigned NumRPS = TRI->getNumRegPressureSets(); |
306 | 602k | RegPressure.resize(NumRPS); |
307 | 602k | std::fill(RegPressure.begin(), RegPressure.end(), 0); |
308 | 602k | RegLimit.resize(NumRPS); |
309 | 6.69M | for (unsigned i = 0, e = NumRPS; i != e6.69M ; ++i6.09M ) |
310 | 6.09M | RegLimit[i] = TRI->getRegPressureSetLimit(MF, i); |
311 | 602k | } |
312 | 1.19M | |
313 | 1.19M | // Get our Loop information... |
314 | 1.19M | MLI = &getAnalysis<MachineLoopInfo>(); |
315 | 1.19M | DT = &getAnalysis<MachineDominatorTree>(); |
316 | 1.19M | AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
317 | 1.19M | |
318 | 1.19M | SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end()); |
319 | 1.70M | while (!Worklist.empty()1.70M ) { |
320 | 514k | CurLoop = Worklist.pop_back_val(); |
321 | 514k | CurPreheader = nullptr; |
322 | 514k | ExitBlocks.clear(); |
323 | 514k | |
324 | 514k | // If this is done before regalloc, only visit outer-most preheader-sporting |
325 | 514k | // loops. |
326 | 514k | if (PreRegAlloc && 514k !LoopIsOuterMostWithPredecessor(CurLoop)258k ) { |
327 | 2.82k | Worklist.append(CurLoop->begin(), CurLoop->end()); |
328 | 2.82k | continue; |
329 | 2.82k | } |
330 | 512k | |
331 | 512k | CurLoop->getExitBlocks(ExitBlocks); |
332 | 512k | |
333 | 512k | if (!PreRegAlloc) |
334 | 256k | HoistRegionPostRA(); |
335 | 256k | else { |
336 | 256k | // CSEMap is initialized for loop header when the first instruction is |
337 | 256k | // being hoisted. |
338 | 256k | MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); |
339 | 256k | FirstInLoop = true; |
340 | 256k | HoistOutOfLoop(N); |
341 | 256k | CSEMap.clear(); |
342 | 256k | |
343 | 256k | if (SinkInstsToAvoidSpills) |
344 | 1 | SinkIntoLoop(); |
345 | 256k | } |
346 | 514k | } |
347 | 1.19M | |
348 | 1.19M | return Changed; |
349 | 1.19M | } |
350 | | |
351 | | /// Return true if instruction stores to the specified frame. |
352 | 96.4k | static bool InstructionStoresToFI(const MachineInstr *MI, int FI) { |
353 | 96.4k | // If we lost memory operands, conservatively assume that the instruction |
354 | 96.4k | // writes to all slots. |
355 | 96.4k | if (MI->memoperands_empty()) |
356 | 2 | return true; |
357 | 96.4k | for (const MachineMemOperand *MemOp : MI->memoperands()) 96.4k { |
358 | 96.4k | if (!MemOp->isStore() || 96.4k !MemOp->getPseudoValue()25.2k ) |
359 | 71.2k | continue; |
360 | 25.2k | if (const FixedStackPseudoSourceValue *25.2k Value25.2k = |
361 | 25.2k | dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) { |
362 | 25.2k | if (Value->getFrameIndex() == FI) |
363 | 25.2k | return true; |
364 | 71.2k | } |
365 | 96.4k | } |
366 | 71.2k | return false; |
367 | 71.2k | } |
368 | | |
369 | | /// Examine the instruction for potentai LICM candidate. Also |
370 | | /// gather register def and frame object update information. |
371 | | void MachineLICM::ProcessMI(MachineInstr *MI, |
372 | | BitVector &PhysRegDefs, |
373 | | BitVector &PhysRegClobbers, |
374 | | SmallSet<int, 32> &StoredFIs, |
375 | 7.64M | SmallVectorImpl<CandidateInfo> &Candidates) { |
376 | 7.64M | bool RuledOut = false; |
377 | 7.64M | bool HasNonInvariantUse = false; |
378 | 7.64M | unsigned Def = 0; |
379 | 25.4M | for (const MachineOperand &MO : MI->operands()) { |
380 | 25.4M | if (MO.isFI()25.4M ) { |
381 | 249k | // Remember if the instruction stores to the frame index. |
382 | 249k | int FI = MO.getIndex(); |
383 | 249k | if (!StoredFIs.count(FI) && |
384 | 198k | MFI->isSpillSlotObjectIndex(FI) && |
385 | 96.4k | InstructionStoresToFI(MI, FI)) |
386 | 25.2k | StoredFIs.insert(FI); |
387 | 249k | HasNonInvariantUse = true; |
388 | 249k | continue; |
389 | 249k | } |
390 | 25.2M | |
391 | 25.2M | // We can't hoist an instruction defining a physreg that is clobbered in |
392 | 25.2M | // the loop. |
393 | 25.2M | if (25.2M MO.isRegMask()25.2M ) { |
394 | 451k | PhysRegClobbers.setBitsNotInMask(MO.getRegMask()); |
395 | 451k | continue; |
396 | 451k | } |
397 | 24.7M | |
398 | 24.7M | if (24.7M !MO.isReg()24.7M ) |
399 | 8.26M | continue; |
400 | 16.5M | unsigned Reg = MO.getReg(); |
401 | 16.5M | if (!Reg) |
402 | 94.5k | continue; |
403 | 16.5M | assert(TargetRegisterInfo::isPhysicalRegister(Reg) && |
404 | 16.4M | "Not expecting virtual register!"); |
405 | 16.4M | |
406 | 16.4M | if (!MO.isDef()16.4M ) { |
407 | 9.47M | if (Reg && 9.47M (PhysRegDefs.test(Reg) || 9.47M PhysRegClobbers.test(Reg)2.04M )) |
408 | 9.47M | // If it's using a non-loop-invariant register, then it's obviously not |
409 | 9.47M | // safe to hoist. |
410 | 9.40M | HasNonInvariantUse = true; |
411 | 9.47M | continue; |
412 | 9.47M | } |
413 | 6.96M | |
414 | 6.96M | if (6.96M MO.isImplicit()6.96M ) { |
415 | 12.3M | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid()12.3M ; ++AI9.52M ) |
416 | 9.52M | PhysRegClobbers.set(*AI); |
417 | 2.87M | if (!MO.isDead()) |
418 | 2.87M | // Non-dead implicit def? This cannot be hoisted. |
419 | 1.52M | RuledOut = true; |
420 | 2.87M | // No need to check if a dead implicit def is also defined by |
421 | 2.87M | // another instruction. |
422 | 2.87M | continue; |
423 | 2.87M | } |
424 | 4.09M | |
425 | 4.09M | // FIXME: For now, avoid instructions with multiple defs, unless |
426 | 4.09M | // it's a dead implicit def. |
427 | 4.09M | if (4.09M Def4.09M ) |
428 | 57.0k | RuledOut = true; |
429 | 4.09M | else |
430 | 4.03M | Def = Reg; |
431 | 4.09M | |
432 | 4.09M | // If we have already seen another instruction that defines the same |
433 | 4.09M | // register, then this is not safe. Two defs is indicated by setting a |
434 | 4.09M | // PhysRegClobbers bit. |
435 | 36.1M | for (MCRegAliasIterator AS(Reg, TRI, true); AS.isValid()36.1M ; ++AS32.0M ) { |
436 | 32.0M | if (PhysRegDefs.test(*AS)) |
437 | 26.7M | PhysRegClobbers.set(*AS); |
438 | 32.0M | PhysRegDefs.set(*AS); |
439 | 32.0M | } |
440 | 4.09M | if (PhysRegClobbers.test(Reg)) |
441 | 4.09M | // MI defined register is seen defined by another instruction in |
442 | 4.09M | // the loop, it cannot be a LICM candidate. |
443 | 3.25M | RuledOut = true; |
444 | 25.4M | } |
445 | 7.64M | |
446 | 7.64M | // Only consider reloads for now and remats which do not have register |
447 | 7.64M | // operands. FIXME: Consider unfold load folding instructions. |
448 | 7.64M | if (Def && 7.64M !RuledOut4.03M ) { |
449 | 654k | int FI = std::numeric_limits<int>::min(); |
450 | 654k | if ((!HasNonInvariantUse && 654k IsLICMCandidate(*MI)31.7k ) || |
451 | 622k | (TII->isLoadFromStackSlot(*MI, FI) && 622k MFI->isSpillSlotObjectIndex(FI)5.25k )) |
452 | 36.3k | Candidates.push_back(CandidateInfo(MI, Def, FI)); |
453 | 654k | } |
454 | 7.64M | } |
455 | | |
456 | | /// Walk the specified region of the CFG and hoist loop invariants out to the |
457 | | /// preheader. |
458 | 256k | void MachineLICM::HoistRegionPostRA() { |
459 | 256k | MachineBasicBlock *Preheader = getCurPreheader(); |
460 | 256k | if (!Preheader) |
461 | 2.83k | return; |
462 | 253k | |
463 | 253k | unsigned NumRegs = TRI->getNumRegs(); |
464 | 253k | BitVector PhysRegDefs(NumRegs); // Regs defined once in the loop. |
465 | 253k | BitVector PhysRegClobbers(NumRegs); // Regs defined more than once. |
466 | 253k | |
467 | 253k | SmallVector<CandidateInfo, 32> Candidates; |
468 | 253k | SmallSet<int, 32> StoredFIs; |
469 | 253k | |
470 | 253k | // Walk the entire region, count number of defs for each register, and |
471 | 253k | // collect potential LICM candidates. |
472 | 253k | const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks(); |
473 | 1.18M | for (MachineBasicBlock *BB : Blocks) { |
474 | 1.18M | // If the header of the loop containing this basic block is a landing pad, |
475 | 1.18M | // then don't try to hoist instructions out of this loop. |
476 | 1.18M | const MachineLoop *ML = MLI->getLoopFor(BB); |
477 | 1.18M | if (ML && 1.18M ML->getHeader()->isEHPad()1.18M ) continue0 ; |
478 | 1.18M | |
479 | 1.18M | // Conservatively treat live-in's as an external def. |
480 | 1.18M | // FIXME: That means a reload that're reused in successor block(s) will not |
481 | 1.18M | // be LICM'ed. |
482 | 1.18M | for (const auto &LI : BB->liveins()) 1.18M { |
483 | 80.0M | for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid()80.0M ; ++AI70.0M ) |
484 | 70.0M | PhysRegDefs.set(*AI); |
485 | 9.90M | } |
486 | 1.18M | |
487 | 1.18M | SpeculationState = SpeculateUnknown; |
488 | 1.18M | for (MachineInstr &MI : *BB) |
489 | 7.64M | ProcessMI(&MI, PhysRegDefs, PhysRegClobbers, StoredFIs, Candidates); |
490 | 1.18M | } |
491 | 253k | |
492 | 253k | // Gather the registers read / clobbered by the terminator. |
493 | 253k | BitVector TermRegs(NumRegs); |
494 | 253k | MachineBasicBlock::iterator TI = Preheader->getFirstTerminator(); |
495 | 253k | if (TI != Preheader->end()253k ) { |
496 | 77.1k | for (const MachineOperand &MO : TI->operands()) { |
497 | 77.1k | if (!MO.isReg()) |
498 | 76.7k | continue; |
499 | 402 | unsigned Reg = MO.getReg(); |
500 | 402 | if (!Reg) |
501 | 360 | continue; |
502 | 126 | for (MCRegAliasIterator AI(Reg, TRI, true); 42 AI.isValid()126 ; ++AI84 ) |
503 | 84 | TermRegs.set(*AI); |
504 | 77.1k | } |
505 | 76.3k | } |
506 | 253k | |
507 | 253k | // Now evaluate whether the potential candidates qualify. |
508 | 253k | // 1. Check if the candidate defined register is defined by another |
509 | 253k | // instruction in the loop. |
510 | 253k | // 2. If the candidate is a load from stack slot (always true for now), |
511 | 253k | // check if the slot is stored anywhere in the loop. |
512 | 253k | // 3. Make sure candidate def should not clobber |
513 | 253k | // registers read by the terminator. Similarly its def should not be |
514 | 253k | // clobbered by the terminator. |
515 | 36.3k | for (CandidateInfo &Candidate : Candidates) { |
516 | 36.3k | if (Candidate.FI != std::numeric_limits<int>::min() && |
517 | 4.77k | StoredFIs.count(Candidate.FI)) |
518 | 377 | continue; |
519 | 36.0k | |
520 | 36.0k | unsigned Def = Candidate.Def; |
521 | 36.0k | if (!PhysRegClobbers.test(Def) && 36.0k !TermRegs.test(Def)1.91k ) { |
522 | 1.91k | bool Safe = true; |
523 | 1.91k | MachineInstr *MI = Candidate.MI; |
524 | 5.58k | for (const MachineOperand &MO : MI->operands()) { |
525 | 5.58k | if (!MO.isReg() || 5.58k MO.isDef()2.01k || !MO.getReg()103 ) |
526 | 5.55k | continue; |
527 | 22 | unsigned Reg = MO.getReg(); |
528 | 22 | if (PhysRegDefs.test(Reg) || |
529 | 22 | PhysRegClobbers.test(Reg)10 ) { |
530 | 12 | // If it's using a non-loop-invariant register, then it's obviously |
531 | 12 | // not safe to hoist. |
532 | 12 | Safe = false; |
533 | 12 | break; |
534 | 12 | } |
535 | 1.91k | } |
536 | 1.91k | if (Safe) |
537 | 1.89k | HoistPostRA(MI, Candidate.Def); |
538 | 1.91k | } |
539 | 36.3k | } |
540 | 256k | } |
541 | | |
542 | | /// Add register 'Reg' to the livein sets of BBs in the current loop, and make |
543 | | /// sure it is not killed by any instructions in the loop. |
544 | 1.89k | void MachineLICM::AddToLiveIns(unsigned Reg) { |
545 | 1.89k | const std::vector<MachineBasicBlock *> &Blocks = CurLoop->getBlocks(); |
546 | 4.06k | for (MachineBasicBlock *BB : Blocks) { |
547 | 4.06k | if (!BB->isLiveIn(Reg)) |
548 | 3.85k | BB->addLiveIn(Reg); |
549 | 909k | for (MachineInstr &MI : *BB) { |
550 | 3.30M | for (MachineOperand &MO : MI.operands()) { |
551 | 3.30M | if (!MO.isReg() || 3.30M !MO.getReg()2.08M || MO.isDef()2.08M ) continue1.75M ; |
552 | 1.55M | if (1.55M MO.getReg() == Reg || 1.55M TRI->isSuperRegister(Reg, MO.getReg())1.55M ) |
553 | 5.02k | MO.setIsKill(false); |
554 | 3.30M | } |
555 | 909k | } |
556 | 4.06k | } |
557 | 1.89k | } |
558 | | |
559 | | /// When an instruction is found to only use loop invariant operands that is |
560 | | /// safe to hoist, this instruction is called to do the dirty work. |
561 | 1.89k | void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { |
562 | 1.89k | MachineBasicBlock *Preheader = getCurPreheader(); |
563 | 1.89k | |
564 | 1.89k | // Now move the instructions to the predecessor, inserting it before any |
565 | 1.89k | // terminator instructions. |
566 | 1.89k | DEBUG(dbgs() << "Hoisting to BB#" << Preheader->getNumber() << " from BB#" |
567 | 1.89k | << MI->getParent()->getNumber() << ": " << *MI); |
568 | 1.89k | |
569 | 1.89k | // Splice the instruction to the preheader. |
570 | 1.89k | MachineBasicBlock *MBB = MI->getParent(); |
571 | 1.89k | Preheader->splice(Preheader->getFirstTerminator(), MBB, MI); |
572 | 1.89k | |
573 | 1.89k | // Add register to livein list to all the BBs in the current loop since a |
574 | 1.89k | // loop invariant must be kept live throughout the whole loop. This is |
575 | 1.89k | // important to ensure later passes do not scavenge the def register. |
576 | 1.89k | AddToLiveIns(Def); |
577 | 1.89k | |
578 | 1.89k | ++NumPostRAHoisted; |
579 | 1.89k | Changed = true; |
580 | 1.89k | } |
581 | | |
582 | | /// Check if this mbb is guaranteed to execute. If not then a load from this mbb |
583 | | /// may not be safe to hoist. |
584 | 141k | bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { |
585 | 141k | if (SpeculationState != SpeculateUnknown) |
586 | 25.4k | return SpeculationState == SpeculateFalse; |
587 | 116k | |
588 | 116k | if (116k BB != CurLoop->getHeader()116k ) { |
589 | 85.9k | // Check loop exiting blocks. |
590 | 85.9k | SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks; |
591 | 85.9k | CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); |
592 | 85.9k | for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks) |
593 | 93.5k | if (93.5k !DT->dominates(BB, CurrentLoopExitingBlock)93.5k ) { |
594 | 76.7k | SpeculationState = SpeculateTrue; |
595 | 76.7k | return false; |
596 | 76.7k | } |
597 | 39.5k | } |
598 | 39.5k | |
599 | 39.5k | SpeculationState = SpeculateFalse; |
600 | 39.5k | return true; |
601 | 39.5k | } |
602 | | |
603 | 1.08M | void MachineLICM::EnterScope(MachineBasicBlock *MBB) { |
604 | 1.08M | DEBUG(dbgs() << "Entering BB#" << MBB->getNumber() << '\n'); |
605 | 1.08M | |
606 | 1.08M | // Remember livein register pressure. |
607 | 1.08M | BackTrace.push_back(RegPressure); |
608 | 1.08M | } |
609 | | |
610 | 845k | void MachineLICM::ExitScope(MachineBasicBlock *MBB) { |
611 | 845k | DEBUG(dbgs() << "Exiting BB#" << MBB->getNumber() << '\n'); |
612 | 845k | BackTrace.pop_back(); |
613 | 845k | } |
614 | | |
615 | | /// Destroy scope for the MBB that corresponds to the given dominator tree node |
616 | | /// if its a leaf or all of its children are done. Walk up the dominator tree to |
617 | | /// destroy ancestors which are now done. |
618 | | void MachineLICM::ExitScopeIfDone(MachineDomTreeNode *Node, |
619 | | DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren, |
620 | 1.08M | DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) { |
621 | 1.08M | if (OpenChildren[Node]) |
622 | 642k | return; |
623 | 444k | |
624 | 444k | // Pop scope. |
625 | 444k | ExitScope(Node->getBlock()); |
626 | 444k | |
627 | 444k | // Now traverse upwards to pop ancestors whose offsprings are all done. |
628 | 845k | while (MachineDomTreeNode *Parent845k = ParentMap[Node]) { |
629 | 711k | unsigned Left = --OpenChildren[Parent]; |
630 | 711k | if (Left != 0) |
631 | 310k | break; |
632 | 401k | ExitScope(Parent->getBlock()); |
633 | 401k | Node = Parent; |
634 | 401k | } |
635 | 1.08M | } |
636 | | |
637 | | /// Walk the specified loop in the CFG (defined by all blocks dominated by the |
638 | | /// specified header block, and that are in the current loop) in depth first |
639 | | /// order w.r.t the DominatorTree. This allows us to visit definitions before |
640 | | /// uses, allowing us to hoist a loop body in one pass without iteration. |
641 | 256k | void MachineLICM::HoistOutOfLoop(MachineDomTreeNode *HeaderN) { |
642 | 256k | MachineBasicBlock *Preheader = getCurPreheader(); |
643 | 256k | if (!Preheader) |
644 | 17 | return; |
645 | 256k | |
646 | 256k | SmallVector<MachineDomTreeNode*, 32> Scopes; |
647 | 256k | SmallVector<MachineDomTreeNode*, 8> WorkList; |
648 | 256k | DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap; |
649 | 256k | DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; |
650 | 256k | |
651 | 256k | // Perform a DFS walk to determine the order of visit. |
652 | 256k | WorkList.push_back(HeaderN); |
653 | 1.48M | while (!WorkList.empty()1.48M ) { |
654 | 1.23M | MachineDomTreeNode *Node = WorkList.pop_back_val(); |
655 | 1.23M | assert(Node && "Null dominator tree node?"); |
656 | 1.23M | MachineBasicBlock *BB = Node->getBlock(); |
657 | 1.23M | |
658 | 1.23M | // If the header of the loop containing this basic block is a landing pad, |
659 | 1.23M | // then don't try to hoist instructions out of this loop. |
660 | 1.23M | const MachineLoop *ML = MLI->getLoopFor(BB); |
661 | 1.23M | if (ML && 1.23M ML->getHeader()->isEHPad()1.08M ) |
662 | 1 | continue; |
663 | 1.23M | |
664 | 1.23M | // If this subregion is not in the top level loop at all, exit. |
665 | 1.23M | if (1.23M !CurLoop->contains(BB)1.23M ) |
666 | 143k | continue; |
667 | 1.08M | |
668 | 1.08M | Scopes.push_back(Node); |
669 | 1.08M | const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); |
670 | 1.08M | unsigned NumChildren = Children.size(); |
671 | 1.08M | |
672 | 1.08M | // Don't hoist things out of a large switch statement. This often causes |
673 | 1.08M | // code to be hoisted that wasn't going to be executed, and increases |
674 | 1.08M | // register pressure in a situation where it's likely to matter. |
675 | 1.08M | if (BB->succ_size() >= 25) |
676 | 37 | NumChildren = 0; |
677 | 1.08M | |
678 | 1.08M | OpenChildren[Node] = NumChildren; |
679 | 1.08M | // Add children in reverse order as then the next popped worklist node is |
680 | 1.08M | // the first child of this node. This means we ultimately traverse the |
681 | 1.08M | // DOM tree in exactly the same order as if we'd recursed. |
682 | 2.06M | for (int i = (int)NumChildren-1; i >= 02.06M ; --i974k ) { |
683 | 974k | MachineDomTreeNode *Child = Children[i]; |
684 | 974k | ParentMap[Child] = Node; |
685 | 974k | WorkList.push_back(Child); |
686 | 974k | } |
687 | 1.23M | } |
688 | 256k | |
689 | 256k | if (Scopes.size() == 0) |
690 | 0 | return; |
691 | 256k | |
692 | 256k | // Compute registers which are livein into the loop headers. |
693 | 256k | RegSeen.clear(); |
694 | 256k | BackTrace.clear(); |
695 | 256k | InitRegPressure(Preheader); |
696 | 256k | |
697 | 256k | // Now perform LICM. |
698 | 1.08M | for (MachineDomTreeNode *Node : Scopes) { |
699 | 1.08M | MachineBasicBlock *MBB = Node->getBlock(); |
700 | 1.08M | |
701 | 1.08M | EnterScope(MBB); |
702 | 1.08M | |
703 | 1.08M | // Process the block |
704 | 1.08M | SpeculationState = SpeculateUnknown; |
705 | 1.08M | for (MachineBasicBlock::iterator |
706 | 11.8M | MII = MBB->begin(), E = MBB->end(); MII != E11.8M ; ) { |
707 | 10.7M | MachineBasicBlock::iterator NextMII = MII; ++NextMII; |
708 | 10.7M | MachineInstr *MI = &*MII; |
709 | 10.7M | if (!Hoist(MI, Preheader)) |
710 | 9.98M | UpdateRegPressure(MI); |
711 | 10.7M | MII = NextMII; |
712 | 10.7M | } |
713 | 1.08M | |
714 | 1.08M | // If it's a leaf node, it's done. Traverse upwards to pop ancestors. |
715 | 1.08M | ExitScopeIfDone(Node, OpenChildren, ParentMap); |
716 | 1.08M | } |
717 | 256k | } |
718 | | |
719 | | /// Sink instructions into loops if profitable. This especially tries to prevent |
720 | | /// register spills caused by register pressure if there is little to no |
721 | | /// overhead moving instructions into loops. |
722 | 1 | void MachineLICM::SinkIntoLoop() { |
723 | 1 | MachineBasicBlock *Preheader = getCurPreheader(); |
724 | 1 | if (!Preheader) |
725 | 0 | return; |
726 | 1 | |
727 | 1 | SmallVector<MachineInstr *, 8> Candidates; |
728 | 1 | for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin(); |
729 | 9 | I != Preheader->instr_end()9 ; ++I8 ) { |
730 | 8 | // We need to ensure that we can safely move this instruction into the loop. |
731 | 8 | // As such, it must not have side-effects, e.g. such as a call has. |
732 | 8 | if (IsLoopInvariantInst(*I) && 8 !HasLoopPHIUse(&*I)6 ) |
733 | 5 | Candidates.push_back(&*I); |
734 | 8 | } |
735 | 1 | |
736 | 5 | for (MachineInstr *I : Candidates) { |
737 | 5 | const MachineOperand &MO = I->getOperand(0); |
738 | 5 | if (!MO.isDef() || 5 !MO.isReg()5 || !MO.getReg()5 ) |
739 | 0 | continue; |
740 | 5 | if (5 !MRI->hasOneDef(MO.getReg())5 ) |
741 | 0 | continue; |
742 | 5 | bool CanSink = true; |
743 | 5 | MachineBasicBlock *B = nullptr; |
744 | 5 | for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) { |
745 | 5 | // FIXME: Come up with a proper cost model that estimates whether sinking |
746 | 5 | // the instruction (and thus possibly executing it on every loop |
747 | 5 | // iteration) is more expensive than a register. |
748 | 5 | // For now assumes that copies are cheap and thus almost always worth it. |
749 | 5 | if (!MI.isCopy()5 ) { |
750 | 0 | CanSink = false; |
751 | 0 | break; |
752 | 0 | } |
753 | 5 | if (5 !B5 ) { |
754 | 5 | B = MI.getParent(); |
755 | 5 | continue; |
756 | 5 | } |
757 | 0 | B = DT->findNearestCommonDominator(B, MI.getParent()); |
758 | 0 | if (!B0 ) { |
759 | 0 | CanSink = false; |
760 | 0 | break; |
761 | 0 | } |
762 | 5 | } |
763 | 5 | if (!CanSink || 5 !B5 || B == Preheader5 ) |
764 | 0 | continue; |
765 | 5 | B->splice(B->getFirstNonPHI(), Preheader, I); |
766 | 5 | } |
767 | 1 | } |
768 | | |
769 | 10.3M | static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { |
770 | 8.52M | return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); |
771 | 10.3M | } |
772 | | |
773 | | /// Find all virtual register references that are liveout of the preheader to |
774 | | /// initialize the starting "register pressure". Note this does not count live |
775 | | /// through (livein but not used) registers. |
776 | 459k | void MachineLICM::InitRegPressure(MachineBasicBlock *BB) { |
777 | 459k | std::fill(RegPressure.begin(), RegPressure.end(), 0); |
778 | 459k | |
779 | 459k | // If the preheader has only a single predecessor and it ends with a |
780 | 459k | // fallthrough or an unconditional branch, then scan its predecessor for live |
781 | 459k | // defs as well. This happens whenever the preheader is created by splitting |
782 | 459k | // the critical edge from the loop predecessor to the loop header. |
783 | 459k | if (BB->pred_size() == 1459k ) { |
784 | 292k | MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
785 | 292k | SmallVector<MachineOperand, 4> Cond; |
786 | 292k | if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && 292k Cond.empty()290k ) |
787 | 203k | InitRegPressure(*BB->pred_begin()); |
788 | 292k | } |
789 | 459k | |
790 | 459k | for (const MachineInstr &MI : *BB) |
791 | 3.04M | UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true); |
792 | 459k | } |
793 | | |
794 | | /// Update estimate of register pressure after the specified instruction. |
795 | | void MachineLICM::UpdateRegPressure(const MachineInstr *MI, |
796 | 13.0M | bool ConsiderUnseenAsDef) { |
797 | 13.0M | auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef); |
798 | 8.54M | for (const auto &RPIdAndCost : Cost) { |
799 | 8.54M | unsigned Class = RPIdAndCost.first; |
800 | 8.54M | if (static_cast<int>(RegPressure[Class]) < -RPIdAndCost.second) |
801 | 0 | RegPressure[Class] = 0; |
802 | 8.54M | else |
803 | 8.54M | RegPressure[Class] += RPIdAndCost.second; |
804 | 8.54M | } |
805 | 13.0M | } |
806 | | |
807 | | /// Calculate the additional register pressure that the registers used in MI |
808 | | /// cause. |
809 | | /// |
810 | | /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to |
811 | | /// figure out which usages are live-ins. |
812 | | /// FIXME: Figure out a way to consider 'RegSeen' from all code paths. |
813 | | DenseMap<unsigned, int> |
814 | | MachineLICM::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen, |
815 | 13.8M | bool ConsiderUnseenAsDef) { |
816 | 13.8M | DenseMap<unsigned, int> Cost; |
817 | 13.8M | if (MI->isImplicitDef()) |
818 | 95.3k | return Cost; |
819 | 46.0M | for (unsigned i = 0, e = MI->getDesc().getNumOperands(); 13.7M i != e46.0M ; ++i32.3M ) { |
820 | 32.3M | const MachineOperand &MO = MI->getOperand(i); |
821 | 32.3M | if (!MO.isReg() || 32.3M MO.isImplicit()20.7M ) |
822 | 11.5M | continue; |
823 | 20.7M | unsigned Reg = MO.getReg(); |
824 | 20.7M | if (!TargetRegisterInfo::isVirtualRegister(Reg)) |
825 | 2.41M | continue; |
826 | 18.2M | |
827 | 18.2M | // FIXME: It seems bad to use RegSeen only for some of these calculations. |
828 | 18.2M | bool isNew = ConsiderSeen ? 18.2M RegSeen.insert(Reg).second17.2M : false1.01M ; |
829 | 18.2M | const TargetRegisterClass *RC = MRI->getRegClass(Reg); |
830 | 18.2M | |
831 | 18.2M | RegClassWeight W = TRI->getRegClassWeight(RC); |
832 | 18.2M | int RCCost = 0; |
833 | 18.2M | if (MO.isDef()) |
834 | 7.96M | RCCost = W.RegWeight; |
835 | 10.3M | else { |
836 | 10.3M | bool isKill = isOperandKill(MO, MRI); |
837 | 10.3M | if (isNew && 10.3M !isKill1.00M && ConsiderUnseenAsDef548k ) |
838 | 10.3M | // Haven't seen this, it must be a livein. |
839 | 320k | RCCost = W.RegWeight; |
840 | 10.0M | else if (10.0M !isNew && 10.0M isKill9.32M ) |
841 | 4.24M | RCCost = -W.RegWeight; |
842 | 10.3M | } |
843 | 18.2M | if (RCCost == 0) |
844 | 5.76M | continue; |
845 | 12.5M | const int *PS = TRI->getRegClassPressureSets(RC); |
846 | 25.2M | for (; *PS != -125.2M ; ++PS12.6M ) { |
847 | 12.6M | if (Cost.find(*PS) == Cost.end()) |
848 | 9.31M | Cost[*PS] = RCCost; |
849 | 12.6M | else |
850 | 3.37M | Cost[*PS] += RCCost; |
851 | 12.6M | } |
852 | 32.3M | } |
853 | 13.8M | return Cost; |
854 | 13.8M | } |
855 | | |
856 | | /// Return true if this machine instruction loads from global offset table or |
857 | | /// constant pool. |
858 | 28.3k | static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) { |
859 | 28.3k | assert(MI.mayLoad() && "Expected MI that loads!"); |
860 | 28.3k | |
861 | 28.3k | // If we lost memory operands, conservatively assume that the instruction |
862 | 28.3k | // reads from everything.. |
863 | 28.3k | if (MI.memoperands_empty()) |
864 | 0 | return true; |
865 | 28.3k | |
866 | 28.3k | for (MachineMemOperand *MemOp : MI.memoperands()) |
867 | 28.3k | if (const PseudoSourceValue *28.3k PSV28.3k = MemOp->getPseudoValue()) |
868 | 22.3k | if (22.3k PSV->isGOT() || 22.3k PSV->isConstantPool()21.7k ) |
869 | 18.8k | return true; |
870 | 9.54k | |
871 | 9.54k | return false; |
872 | 9.54k | } |
873 | | |
874 | | /// Returns true if the instruction may be a suitable candidate for LICM. |
875 | | /// e.g. If the instruction is a call, then it's obviously not safe to hoist it. |
876 | 10.7M | bool MachineLICM::IsLICMCandidate(MachineInstr &I) { |
877 | 10.7M | // Check if it's safe to move the instruction. |
878 | 10.7M | bool DontMoveAcrossStore = true; |
879 | 10.7M | if (!I.isSafeToMove(AA, DontMoveAcrossStore)) |
880 | 5.23M | return false; |
881 | 5.53M | |
882 | 5.53M | // If it is load then check if it is guaranteed to execute by making sure that |
883 | 5.53M | // it dominates all exiting blocks. If it doesn't, then there is a path out of |
884 | 5.53M | // the loop which does not execute this load, so we can't hoist it. Loads |
885 | 5.53M | // from constant memory are not safe to speculate all the time, for example |
886 | 5.53M | // indexed load from a jump table. |
887 | 5.53M | // Stores and side effects are already checked by isSafeToMove. |
888 | 5.53M | if (5.53M I.mayLoad() && 5.53M !mayLoadFromGOTOrConstantPool(I)28.3k && |
889 | 9.54k | !IsGuaranteedToExecute(I.getParent())) |
890 | 5.35k | return false; |
891 | 5.53M | |
892 | 5.53M | return true; |
893 | 5.53M | } |
894 | | |
895 | | /// Returns true if the instruction is loop invariant. |
896 | | /// I.e., all virtual register operands are defined outside of the loop, |
897 | | /// physical registers aren't accessed explicitly, and there are no side |
898 | | /// effects that aren't captured by the operands or other flags. |
899 | 10.7M | bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { |
900 | 10.7M | if (!IsLICMCandidate(I)) |
901 | 5.23M | return false; |
902 | 5.50M | |
903 | 5.50M | // The instruction is loop invariant if all of its operands are. |
904 | 5.50M | for (const MachineOperand &MO : I.operands()) 5.50M { |
905 | 10.8M | if (!MO.isReg()) |
906 | 1.34M | continue; |
907 | 9.45M | |
908 | 9.45M | unsigned Reg = MO.getReg(); |
909 | 9.45M | if (Reg == 09.45M ) continue10.3k ; |
910 | 9.44M | |
911 | 9.44M | // Don't hoist an instruction that uses or defines a physical register. |
912 | 9.44M | if (9.44M TargetRegisterInfo::isPhysicalRegister(Reg)9.44M ) { |
913 | 1.79M | if (MO.isUse()1.79M ) { |
914 | 589k | // If the physreg has no defs anywhere, it's just an ambient register |
915 | 589k | // and we can freely move its uses. Alternatively, if it's allocatable, |
916 | 589k | // it could get allocated to something with a def during allocation. |
917 | 589k | // However, if the physreg is known to always be caller saved/restored |
918 | 589k | // then this use is safe to hoist. |
919 | 589k | if (!MRI->isConstantPhysReg(Reg) && |
920 | 369k | !(TRI->isCallerPreservedPhysReg(Reg, *I.getParent()->getParent()))) |
921 | 369k | return false; |
922 | 219k | // Otherwise it's safe to move. |
923 | 219k | continue; |
924 | 1.20M | } else if (1.20M !MO.isDead()1.20M ) { |
925 | 1.18M | // A def that isn't dead. We can't move it. |
926 | 1.18M | return false; |
927 | 12.5k | } else if (12.5k CurLoop->getHeader()->isLiveIn(Reg)12.5k ) { |
928 | 0 | // If the reg is live into the loop, we can't hoist an instruction |
929 | 0 | // which would clobber it. |
930 | 0 | return false; |
931 | 0 | } |
932 | 7.66M | } |
933 | 7.66M | |
934 | 7.66M | if (7.66M !MO.isUse()7.66M ) |
935 | 4.31M | continue; |
936 | 3.34M | |
937 | 7.66M | assert(MRI->getVRegDef(Reg) && |
938 | 3.34M | "Machine instr not mapped for this vreg?!"); |
939 | 3.34M | |
940 | 3.34M | // If the loop contains the definition of an operand, then the instruction |
941 | 3.34M | // isn't loop invariant. |
942 | 3.34M | if (CurLoop->contains(MRI->getVRegDef(Reg))) |
943 | 2.94M | return false; |
944 | 1.00M | } |
945 | 1.00M | |
946 | 1.00M | // If we got this far, the instruction is loop invariant! |
947 | 1.00M | return true; |
948 | 1.00M | } |
949 | | |
950 | | /// Return true if the specified instruction is used by a phi node and hoisting |
951 | | /// it could cause a copy to be inserted. |
952 | 950k | bool MachineLICM::HasLoopPHIUse(const MachineInstr *MI) const { |
953 | 950k | SmallVector<const MachineInstr*, 8> Work(1, MI); |
954 | 1.37M | do { |
955 | 1.37M | MI = Work.pop_back_val(); |
956 | 3.18M | for (const MachineOperand &MO : MI->operands()) { |
957 | 3.18M | if (!MO.isReg() || 3.18M !MO.isDef()2.03M ) |
958 | 1.81M | continue; |
959 | 1.37M | unsigned Reg = MO.getReg(); |
960 | 1.37M | if (!TargetRegisterInfo::isVirtualRegister(Reg)) |
961 | 306k | continue; |
962 | 1.06M | for (MachineInstr &UseMI : MRI->use_instructions(Reg)) 1.06M { |
963 | 1.30M | // A PHI may cause a copy to be inserted. |
964 | 1.30M | if (UseMI.isPHI()1.30M ) { |
965 | 120k | // A PHI inside the loop causes a copy because the live range of Reg is |
966 | 120k | // extended across the PHI. |
967 | 120k | if (CurLoop->contains(&UseMI)) |
968 | 98.6k | return true; |
969 | 21.5k | // A PHI in an exit block can cause a copy to be inserted if the PHI |
970 | 21.5k | // has multiple predecessors in the loop with different values. |
971 | 21.5k | // For now, approximate by rejecting all exit blocks. |
972 | 21.5k | if (21.5k isExitBlock(UseMI.getParent())21.5k ) |
973 | 21.4k | return true; |
974 | 5 | continue; |
975 | 5 | } |
976 | 1.18M | // Look past copies as well. |
977 | 1.18M | if (1.18M UseMI.isCopy() && 1.18M CurLoop->contains(&UseMI)421k ) |
978 | 421k | Work.push_back(&UseMI); |
979 | 1.30M | } |
980 | 3.18M | } |
981 | 1.25M | } while (!Work.empty()); |
982 | 829k | return false; |
983 | 950k | } |
984 | | |
985 | | /// Compute operand latency between a def of 'Reg' and an use in the current |
986 | | /// loop, return true if the target considered it high. |
987 | | bool MachineLICM::HasHighOperandLatency(MachineInstr &MI, |
988 | 264k | unsigned DefIdx, unsigned Reg) const { |
989 | 264k | if (MRI->use_nodbg_empty(Reg)) |
990 | 0 | return false; |
991 | 264k | |
992 | 264k | for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) 264k { |
993 | 273k | if (UseMI.isCopyLike()) |
994 | 90.0k | continue; |
995 | 183k | if (183k !CurLoop->contains(UseMI.getParent())183k ) |
996 | 126 | continue; |
997 | 799k | for (unsigned i = 0, e = UseMI.getNumOperands(); 182k i != e799k ; ++i617k ) { |
998 | 617k | const MachineOperand &MO = UseMI.getOperand(i); |
999 | 617k | if (!MO.isReg() || 617k !MO.isUse()533k ) |
1000 | 219k | continue; |
1001 | 397k | unsigned MOReg = MO.getReg(); |
1002 | 397k | if (MOReg != Reg) |
1003 | 214k | continue; |
1004 | 183k | |
1005 | 183k | if (183k TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i)183k ) |
1006 | 19 | return true; |
1007 | 617k | } |
1008 | 182k | |
1009 | 182k | // Only look at the first in loop use. |
1010 | 182k | break; |
1011 | 264k | } |
1012 | 264k | |
1013 | 264k | return false; |
1014 | 264k | } |
1015 | | |
1016 | | /// Return true if the instruction is marked "cheap" or the operand latency |
1017 | | /// between its def and a use is one or less. |
1018 | 950k | bool MachineLICM::IsCheapInstruction(MachineInstr &MI) const { |
1019 | 950k | if (TII->isAsCheapAsAMove(MI) || 950k MI.isCopyLike()450k ) |
1020 | 606k | return true; |
1021 | 343k | |
1022 | 343k | bool isCheap = false; |
1023 | 343k | unsigned NumDefs = MI.getDesc().getNumDefs(); |
1024 | 343k | for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && 343k i != e343k ; ++i722 ) { |
1025 | 343k | MachineOperand &DefMO = MI.getOperand(i); |
1026 | 343k | if (!DefMO.isReg() || 343k !DefMO.isDef()343k ) |
1027 | 0 | continue; |
1028 | 343k | --NumDefs; |
1029 | 343k | unsigned Reg = DefMO.getReg(); |
1030 | 343k | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
1031 | 0 | continue; |
1032 | 343k | |
1033 | 343k | if (343k !TII->hasLowDefLatency(SchedModel, MI, i)343k ) |
1034 | 342k | return false; |
1035 | 722 | isCheap = true; |
1036 | 722 | } |
1037 | 343k | |
1038 | 722 | return isCheap; |
1039 | 950k | } |
1040 | | |
1041 | | /// Visit BBs from header to current BB, check if hoisting an instruction of the |
1042 | | /// given cost matrix can cause high register pressure. |
1043 | | bool MachineLICM::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost, |
1044 | 264k | bool CheapInstr) { |
1045 | 286k | for (const auto &RPIdAndCost : Cost) { |
1046 | 286k | if (RPIdAndCost.second <= 0) |
1047 | 105k | continue; |
1048 | 180k | |
1049 | 180k | unsigned Class = RPIdAndCost.first; |
1050 | 180k | int Limit = RegLimit[Class]; |
1051 | 180k | |
1052 | 180k | // Don't hoist cheap instructions if they would increase register pressure, |
1053 | 180k | // even if we're under the limit. |
1054 | 180k | if (CheapInstr && 180k !HoistCheapInsts125k ) |
1055 | 125k | return true; |
1056 | 55.4k | |
1057 | 55.4k | for (const auto &RP : BackTrace) |
1058 | 157k | if (157k static_cast<int>(RP[Class]) + RPIdAndCost.second >= Limit157k ) |
1059 | 7.11k | return true; |
1060 | 132k | } |
1061 | 132k | |
1062 | 132k | return false; |
1063 | 132k | } |
1064 | | |
1065 | | /// Traverse the back trace from header to the current block and update their |
1066 | | /// register pressures to reflect the effect of hoisting MI from the current |
1067 | | /// block to the preheader. |
1068 | 513k | void MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) { |
1069 | 513k | // First compute the 'cost' of the instruction, i.e. its contribution |
1070 | 513k | // to register pressure. |
1071 | 513k | auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false, |
1072 | 513k | /*ConsiderUnseenAsDef=*/false); |
1073 | 513k | |
1074 | 513k | // Update register pressure of blocks from loop header to current block. |
1075 | 513k | for (auto &RP : BackTrace) |
1076 | 1.90M | for (const auto &RPIdAndCost : Cost) |
1077 | 1.79M | RP[RPIdAndCost.first] += RPIdAndCost.second; |
1078 | 513k | } |
1079 | | |
1080 | | /// Return true if it is potentially profitable to hoist the given loop |
1081 | | /// invariant. |
1082 | 1.00M | bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { |
1083 | 1.00M | if (MI.isImplicitDef()) |
1084 | 51.6k | return true; |
1085 | 950k | |
1086 | 950k | // Besides removing computation from the loop, hoisting an instruction has |
1087 | 950k | // these effects: |
1088 | 950k | // |
1089 | 950k | // - The value defined by the instruction becomes live across the entire |
1090 | 950k | // loop. This increases register pressure in the loop. |
1091 | 950k | // |
1092 | 950k | // - If the value is used by a PHI in the loop, a copy will be required for |
1093 | 950k | // lowering the PHI after extending the live range. |
1094 | 950k | // |
1095 | 950k | // - When hoisting the last use of a value in the loop, that value no longer |
1096 | 950k | // needs to be live in the loop. This lowers register pressure in the loop. |
1097 | 950k | |
1098 | 950k | bool CheapInstr = IsCheapInstruction(MI); |
1099 | 950k | bool CreatesCopy = HasLoopPHIUse(&MI); |
1100 | 950k | |
1101 | 950k | // Don't hoist a cheap instruction if it would create a copy in the loop. |
1102 | 950k | if (CheapInstr && 950k CreatesCopy607k ) { |
1103 | 115k | DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI); |
1104 | 115k | return false; |
1105 | 115k | } |
1106 | 834k | |
1107 | 834k | // Rematerializable instructions should always be hoisted since the register |
1108 | 834k | // allocator can just pull them down again when needed. |
1109 | 834k | if (834k TII->isTriviallyReMaterializable(MI, AA)834k ) |
1110 | 570k | return true; |
1111 | 264k | |
1112 | 264k | // FIXME: If there are long latency loop-invariant instructions inside the |
1113 | 264k | // loop at this point, why didn't the optimizer's LICM hoist them? |
1114 | 1.05M | for (unsigned i = 0, e = MI.getDesc().getNumOperands(); 264k i != e1.05M ; ++i787k ) { |
1115 | 787k | const MachineOperand &MO = MI.getOperand(i); |
1116 | 787k | if (!MO.isReg() || 787k MO.isImplicit()522k ) |
1117 | 264k | continue; |
1118 | 522k | unsigned Reg = MO.getReg(); |
1119 | 522k | if (!TargetRegisterInfo::isVirtualRegister(Reg)) |
1120 | 76.5k | continue; |
1121 | 446k | if (446k MO.isDef() && 446k HasHighOperandLatency(MI, i, Reg)264k ) { |
1122 | 19 | DEBUG(dbgs() << "Hoist High Latency: " << MI); |
1123 | 19 | ++NumHighLatency; |
1124 | 19 | return true; |
1125 | 19 | } |
1126 | 787k | } |
1127 | 264k | |
1128 | 264k | // Estimate register pressure to determine whether to LICM the instruction. |
1129 | 264k | // In low register pressure situation, we can be more aggressive about |
1130 | 264k | // hoisting. Also, favors hoisting long latency instructions even in |
1131 | 264k | // moderately high pressure situation. |
1132 | 264k | // Cheap instructions will only be hoisted if they don't increase register |
1133 | 264k | // pressure at all. |
1134 | 264k | auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false, |
1135 | 264k | /*ConsiderUnseenAsDef=*/false); |
1136 | 264k | |
1137 | 264k | // Visit BBs from header to current BB, if hoisting this doesn't cause |
1138 | 264k | // high register pressure, then it's safe to proceed. |
1139 | 264k | if (!CanCauseHighRegPressure(Cost, CheapInstr)264k ) { |
1140 | 132k | DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI); |
1141 | 132k | ++NumLowRP; |
1142 | 132k | return true; |
1143 | 132k | } |
1144 | 132k | |
1145 | 132k | // Don't risk increasing register pressure if it would create copies. |
1146 | 132k | if (132k CreatesCopy132k ) { |
1147 | 43 | DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI); |
1148 | 43 | return false; |
1149 | 43 | } |
1150 | 132k | |
1151 | 132k | // Do not "speculate" in high register pressure situation. If an |
1152 | 132k | // instruction is not guaranteed to be executed in the loop, it's best to be |
1153 | 132k | // conservative. |
1154 | 132k | if (132k AvoidSpeculation && |
1155 | 132k | (!IsGuaranteedToExecute(MI.getParent()) && 132k !MayCSE(&MI)79.4k )) { |
1156 | 47.2k | DEBUG(dbgs() << "Won't speculate: " << MI); |
1157 | 47.2k | return false; |
1158 | 47.2k | } |
1159 | 84.9k | |
1160 | 84.9k | // High register pressure situation, only hoist if the instruction is going |
1161 | 84.9k | // to be remat'ed. |
1162 | 84.9k | if (84.9k !TII->isTriviallyReMaterializable(MI, AA) && |
1163 | 84.9k | !MI.isDereferenceableInvariantLoad(AA)84.9k ) { |
1164 | 84.6k | DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI); |
1165 | 84.6k | return false; |
1166 | 84.6k | } |
1167 | 298 | |
1168 | 298 | return true; |
1169 | 298 | } |
1170 | | |
1171 | | /// Unfold a load from the given machineinstr if the load itself could be |
1172 | | /// hoisted. Return the unfolded and hoistable load, or null if the load |
1173 | | /// couldn't be unfolded or if it wouldn't be hoistable. |
1174 | 9.98M | MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { |
1175 | 9.98M | // Don't unfold simple loads. |
1176 | 9.98M | if (MI->canFoldAsLoad()) |
1177 | 12.5k | return nullptr; |
1178 | 9.97M | |
1179 | 9.97M | // If not, we may be able to unfold a load and hoist that. |
1180 | 9.97M | // First test whether the instruction is loading from an amenable |
1181 | 9.97M | // memory location. |
1182 | 9.97M | if (9.97M !MI->isDereferenceableInvariantLoad(AA)9.97M ) |
1183 | 9.96M | return nullptr; |
1184 | 9.75k | |
1185 | 9.75k | // Next determine the register class for a temporary register. |
1186 | 9.75k | unsigned LoadRegIndex; |
1187 | 9.75k | unsigned NewOpc = |
1188 | 9.75k | TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), |
1189 | 9.75k | /*UnfoldLoad=*/true, |
1190 | 9.75k | /*UnfoldStore=*/false, |
1191 | 9.75k | &LoadRegIndex); |
1192 | 9.75k | if (NewOpc == 09.75k ) return nullptr9.52k ; |
1193 | 230 | const MCInstrDesc &MID = TII->get(NewOpc); |
1194 | 230 | MachineFunction &MF = *MI->getParent()->getParent(); |
1195 | 230 | const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex, TRI, MF); |
1196 | 230 | // Ok, we're unfolding. Create a temporary register and do the unfold. |
1197 | 230 | unsigned Reg = MRI->createVirtualRegister(RC); |
1198 | 230 | |
1199 | 230 | SmallVector<MachineInstr *, 2> NewMIs; |
1200 | 230 | bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg, |
1201 | 230 | /*UnfoldLoad=*/true, |
1202 | 230 | /*UnfoldStore=*/false, NewMIs); |
1203 | 230 | (void)Success; |
1204 | 230 | assert(Success && |
1205 | 230 | "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " |
1206 | 230 | "succeeded!"); |
1207 | 230 | assert(NewMIs.size() == 2 && |
1208 | 230 | "Unfolded a load into multiple instructions!"); |
1209 | 230 | MachineBasicBlock *MBB = MI->getParent(); |
1210 | 230 | MachineBasicBlock::iterator Pos = MI; |
1211 | 230 | MBB->insert(Pos, NewMIs[0]); |
1212 | 230 | MBB->insert(Pos, NewMIs[1]); |
1213 | 230 | // If unfolding produced a load that wasn't loop-invariant or profitable to |
1214 | 230 | // hoist, discard the new instructions and bail. |
1215 | 230 | if (!IsLoopInvariantInst(*NewMIs[0]) || 230 !IsProfitableToHoist(*NewMIs[0])170 ) { |
1216 | 60 | NewMIs[0]->eraseFromParent(); |
1217 | 60 | NewMIs[1]->eraseFromParent(); |
1218 | 60 | return nullptr; |
1219 | 60 | } |
1220 | 170 | |
1221 | 170 | // Update register pressure for the unfolded instruction. |
1222 | 170 | UpdateRegPressure(NewMIs[1]); |
1223 | 170 | |
1224 | 170 | // Otherwise we successfully unfolded a load that we can hoist. |
1225 | 170 | MI->eraseFromParent(); |
1226 | 170 | return NewMIs[0]; |
1227 | 170 | } |
1228 | | |
1229 | | /// Initialize the CSE map with instructions that are in the current loop |
1230 | | /// preheader that may become duplicates of instructions that are hoisted |
1231 | | /// out of the loop. |
1232 | 115k | void MachineLICM::InitCSEMap(MachineBasicBlock *BB) { |
1233 | 115k | for (MachineInstr &MI : *BB) |
1234 | 598k | CSEMap[MI.getOpcode()].push_back(&MI); |
1235 | 115k | } |
1236 | | |
1237 | | /// Find an instruction amount PrevMIs that is a duplicate of MI. |
1238 | | /// Return this instruction if it's found. |
1239 | | const MachineInstr* |
1240 | | MachineLICM::LookForDuplicate(const MachineInstr *MI, |
1241 | 516k | std::vector<const MachineInstr*> &PrevMIs) { |
1242 | 516k | for (const MachineInstr *PrevMI : PrevMIs) |
1243 | 1.95M | if (1.95M TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? 1.95M MRI1.95M : nullptr0 ))) |
1244 | 273k | return PrevMI; |
1245 | 243k | |
1246 | 243k | return nullptr; |
1247 | 243k | } |
1248 | | |
1249 | | /// Given a LICM'ed instruction, look for an instruction on the preheader that |
1250 | | /// computes the same value. If it's found, do a RAU on with the definition of |
1251 | | /// the existing instruction rather than hoisting the instruction to the |
1252 | | /// preheader. |
1253 | | bool MachineLICM::EliminateCSE(MachineInstr *MI, |
1254 | 754k | DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI) { |
1255 | 754k | // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate |
1256 | 754k | // the undef property onto uses. |
1257 | 754k | if (CI == CSEMap.end() || 754k MI->isImplicitDef()513k ) |
1258 | 280k | return false; |
1259 | 473k | |
1260 | 473k | if (const MachineInstr *473k Dup473k = LookForDuplicate(MI, CI->second)) { |
1261 | 240k | DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); |
1262 | 240k | |
1263 | 240k | // Replace virtual registers defined by MI by their counterparts defined |
1264 | 240k | // by Dup. |
1265 | 240k | SmallVector<unsigned, 2> Defs; |
1266 | 866k | for (unsigned i = 0, e = MI->getNumOperands(); i != e866k ; ++i625k ) { |
1267 | 625k | const MachineOperand &MO = MI->getOperand(i); |
1268 | 625k | |
1269 | 625k | // Physical registers may not differ here. |
1270 | 625k | assert((!MO.isReg() || MO.getReg() == 0 || |
1271 | 625k | !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || |
1272 | 625k | MO.getReg() == Dup->getOperand(i).getReg()) && |
1273 | 625k | "Instructions with different phys regs are not identical!"); |
1274 | 625k | |
1275 | 625k | if (MO.isReg() && 625k MO.isDef()252k && |
1276 | 241k | !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) |
1277 | 240k | Defs.push_back(i); |
1278 | 625k | } |
1279 | 240k | |
1280 | 240k | SmallVector<const TargetRegisterClass*, 2> OrigRCs; |
1281 | 481k | for (unsigned i = 0, e = Defs.size(); i != e481k ; ++i240k ) { |
1282 | 240k | unsigned Idx = Defs[i]; |
1283 | 240k | unsigned Reg = MI->getOperand(Idx).getReg(); |
1284 | 240k | unsigned DupReg = Dup->getOperand(Idx).getReg(); |
1285 | 240k | OrigRCs.push_back(MRI->getRegClass(DupReg)); |
1286 | 240k | |
1287 | 240k | if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))240k ) { |
1288 | 0 | // Restore old RCs if more than one defs. |
1289 | 0 | for (unsigned j = 0; j != i0 ; ++j0 ) |
1290 | 0 | MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]); |
1291 | 0 | return false; |
1292 | 0 | } |
1293 | 240k | } |
1294 | 240k | |
1295 | 240k | for (unsigned Idx : Defs) 240k { |
1296 | 240k | unsigned Reg = MI->getOperand(Idx).getReg(); |
1297 | 240k | unsigned DupReg = Dup->getOperand(Idx).getReg(); |
1298 | 240k | MRI->replaceRegWith(Reg, DupReg); |
1299 | 240k | MRI->clearKillFlags(DupReg); |
1300 | 240k | } |
1301 | 240k | |
1302 | 240k | MI->eraseFromParent(); |
1303 | 240k | ++NumCSEed; |
1304 | 240k | return true; |
1305 | 232k | } |
1306 | 232k | return false; |
1307 | 232k | } |
1308 | | |
1309 | | /// Return true if the given instruction will be CSE'd if it's hoisted out of |
1310 | | /// the loop. |
1311 | 79.4k | bool MachineLICM::MayCSE(MachineInstr *MI) { |
1312 | 79.4k | unsigned Opcode = MI->getOpcode(); |
1313 | 79.4k | DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator |
1314 | 79.4k | CI = CSEMap.find(Opcode); |
1315 | 79.4k | // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate |
1316 | 79.4k | // the undef property onto uses. |
1317 | 79.4k | if (CI == CSEMap.end() || 79.4k MI->isImplicitDef()43.1k ) |
1318 | 36.3k | return false; |
1319 | 43.1k | |
1320 | 43.1k | return LookForDuplicate(MI, CI->second) != nullptr; |
1321 | 43.1k | } |
1322 | | |
1323 | | /// When an instruction is found to use only loop invariant operands |
1324 | | /// that are safe to hoist, this instruction is called to do the dirty work. |
1325 | | /// It returns true if the instruction is hoisted. |
1326 | 10.7M | bool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) { |
1327 | 10.7M | // First check whether we should hoist this instruction. |
1328 | 10.7M | if (!IsLoopInvariantInst(*MI) || 10.7M !IsProfitableToHoist(*MI)1.00M ) { |
1329 | 9.98M | // If not, try unfolding a hoistable load. |
1330 | 9.98M | MI = ExtractHoistableLoad(MI); |
1331 | 9.98M | if (!MI9.98M ) return false9.98M ; |
1332 | 754k | } |
1333 | 754k | |
1334 | 754k | // Now move the instructions to the predecessor, inserting it before any |
1335 | 754k | // terminator instructions. |
1336 | 754k | DEBUG754k ({ |
1337 | 754k | dbgs() << "Hoisting " << *MI; |
1338 | 754k | if (MI->getParent()->getBasicBlock()) |
1339 | 754k | dbgs() << " from BB#" << MI->getParent()->getNumber(); |
1340 | 754k | if (Preheader->getBasicBlock()) |
1341 | 754k | dbgs() << " to BB#" << Preheader->getNumber(); |
1342 | 754k | dbgs() << "\n"; |
1343 | 754k | }); |
1344 | 754k | |
1345 | 754k | // If this is the first instruction being hoisted to the preheader, |
1346 | 754k | // initialize the CSE map with potential common expressions. |
1347 | 754k | if (FirstInLoop754k ) { |
1348 | 115k | InitCSEMap(Preheader); |
1349 | 115k | FirstInLoop = false; |
1350 | 115k | } |
1351 | 754k | |
1352 | 754k | // Look for opportunity to CSE the hoisted instruction. |
1353 | 754k | unsigned Opcode = MI->getOpcode(); |
1354 | 754k | DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator |
1355 | 754k | CI = CSEMap.find(Opcode); |
1356 | 754k | if (!EliminateCSE(MI, CI)754k ) { |
1357 | 513k | // Otherwise, splice the instruction to the preheader. |
1358 | 513k | Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI); |
1359 | 513k | |
1360 | 513k | // Since we are moving the instruction out of its basic block, we do not |
1361 | 513k | // retain its debug location. Doing so would degrade the debugging |
1362 | 513k | // experience and adversely affect the accuracy of profiling information. |
1363 | 513k | MI->setDebugLoc(DebugLoc()); |
1364 | 513k | |
1365 | 513k | // Update register pressure for BBs from header to this block. |
1366 | 513k | UpdateBackTraceRegPressure(MI); |
1367 | 513k | |
1368 | 513k | // Clear the kill flags of any register this instruction defines, |
1369 | 513k | // since they may need to be live throughout the entire loop |
1370 | 513k | // rather than just live for part of it. |
1371 | 513k | for (MachineOperand &MO : MI->operands()) |
1372 | 1.30M | if (1.30M MO.isReg() && 1.30M MO.isDef()632k && !MO.isDead()514k ) |
1373 | 513k | MRI->clearKillFlags(MO.getReg()); |
1374 | 513k | |
1375 | 513k | // Add to the CSE map. |
1376 | 513k | if (CI != CSEMap.end()) |
1377 | 272k | CI->second.push_back(MI); |
1378 | 513k | else |
1379 | 241k | CSEMap[Opcode].push_back(MI); |
1380 | 513k | } |
1381 | 10.7M | |
1382 | 10.7M | ++NumHoisted; |
1383 | 10.7M | Changed = true; |
1384 | 10.7M | |
1385 | 10.7M | return true; |
1386 | 10.7M | } |
1387 | | |
1388 | | /// Get the preheader for the current loop, splitting a critical edge if needed. |
1389 | 514k | MachineBasicBlock *MachineLICM::getCurPreheader() { |
1390 | 514k | // Determine the block to which to hoist instructions. If we can't find a |
1391 | 514k | // suitable loop predecessor, we can't do any hoisting. |
1392 | 514k | |
1393 | 514k | // If we've tried to get a preheader and failed, don't try again. |
1394 | 514k | if (CurPreheader == reinterpret_cast<MachineBasicBlock *>(-1)) |
1395 | 0 | return nullptr; |
1396 | 514k | |
1397 | 514k | if (514k !CurPreheader514k ) { |
1398 | 512k | CurPreheader = CurLoop->getLoopPreheader(); |
1399 | 512k | if (!CurPreheader512k ) { |
1400 | 26.4k | MachineBasicBlock *Pred = CurLoop->getLoopPredecessor(); |
1401 | 26.4k | if (!Pred26.4k ) { |
1402 | 2.82k | CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); |
1403 | 2.82k | return nullptr; |
1404 | 2.82k | } |
1405 | 23.6k | |
1406 | 23.6k | CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), *this); |
1407 | 23.6k | if (!CurPreheader23.6k ) { |
1408 | 34 | CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1); |
1409 | 34 | return nullptr; |
1410 | 34 | } |
1411 | 511k | } |
1412 | 512k | } |
1413 | 511k | return CurPreheader; |
1414 | 511k | } |