1 //===- MachineSink.cpp - Sinking for machine instructions -----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass moves instructions into successor blocks when possible, so that
10 // they aren't executed on paths where their results aren't needed.
11 //
12 // This pass is not intended to be a replacement or a complete alternative
13 // for an LLVM-IR-level sinking pass. It is only designed to sink simple
14 // constructs that are not exposed before lowering and instruction selection.
15 //
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/PointerIntPair.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/SparseBitVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/CodeGen/MachineBasicBlock.h"
27 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
28 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFunction.h"
31 #include "llvm/CodeGen/MachineFunctionPass.h"
32 #include "llvm/CodeGen/MachineInstr.h"
33 #include "llvm/CodeGen/MachineLoopInfo.h"
34 #include "llvm/CodeGen/MachineOperand.h"
35 #include "llvm/CodeGen/MachinePostDominators.h"
36 #include "llvm/CodeGen/MachineRegisterInfo.h"
37 #include "llvm/CodeGen/RegisterClassInfo.h"
38 #include "llvm/CodeGen/RegisterPressure.h"
39 #include "llvm/CodeGen/TargetInstrInfo.h"
40 #include "llvm/CodeGen/TargetRegisterInfo.h"
41 #include "llvm/CodeGen/TargetSubtargetInfo.h"
42 #include "llvm/IR/BasicBlock.h"
43 #include "llvm/IR/DebugInfoMetadata.h"
44 #include "llvm/IR/LLVMContext.h"
45 #include "llvm/InitializePasses.h"
46 #include "llvm/MC/MCRegisterInfo.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/BranchProbability.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/raw_ostream.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <cstdint>
55 #include <map>
56 #include <utility>
57 #include <vector>
58
59 using namespace llvm;
60
61 #define DEBUG_TYPE "machine-sink"
62
63 static cl::opt<bool>
64 SplitEdges("machine-sink-split",
65 cl::desc("Split critical edges during machine sinking"),
66 cl::init(true), cl::Hidden);
67
68 static cl::opt<bool>
69 UseBlockFreqInfo("machine-sink-bfi",
70 cl::desc("Use block frequency info to find successors to sink"),
71 cl::init(true), cl::Hidden);
72
73 static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
74 "machine-sink-split-probability-threshold",
75 cl::desc(
76 "Percentage threshold for splitting single-instruction critical edge. "
77 "If the branch threshold is higher than this threshold, we allow "
78 "speculative execution of up to 1 instruction to avoid branching to "
79 "splitted critical edge"),
80 cl::init(40), cl::Hidden);
81
82 static cl::opt<unsigned> SinkLoadInstsPerBlockThreshold(
83 "machine-sink-load-instrs-threshold",
84 cl::desc("Do not try to find alias store for a load if there is a in-path "
85 "block whose instruction number is higher than this threshold."),
86 cl::init(2000), cl::Hidden);
87
88 static cl::opt<unsigned> SinkLoadBlocksThreshold(
89 "machine-sink-load-blocks-threshold",
90 cl::desc("Do not try to find alias store for a load if the block number in "
91 "the straight line is higher than this threshold."),
92 cl::init(20), cl::Hidden);
93
94 STATISTIC(NumSunk, "Number of machine instructions sunk");
95 STATISTIC(NumSplit, "Number of critical edges split");
96 STATISTIC(NumCoalesces, "Number of copies coalesced");
97 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
98
99 namespace {
100
101 class MachineSinking : public MachineFunctionPass {
102 const TargetInstrInfo *TII;
103 const TargetRegisterInfo *TRI;
104 MachineRegisterInfo *MRI; // Machine register information
105 MachineDominatorTree *DT; // Machine dominator tree
106 MachinePostDominatorTree *PDT; // Machine post dominator tree
107 MachineLoopInfo *LI;
108 MachineBlockFrequencyInfo *MBFI;
109 const MachineBranchProbabilityInfo *MBPI;
110 AliasAnalysis *AA;
111 RegisterClassInfo RegClassInfo;
112
113 // Remember which edges have been considered for breaking.
114 SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
115 CEBCandidates;
116 // Remember which edges we are about to split.
117 // This is different from CEBCandidates since those edges
118 // will be split.
119 SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
120
121 SparseBitVector<> RegsToClearKillFlags;
122
123 using AllSuccsCache =
124 std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
125
126 /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
127 /// post-dominated by another DBG_VALUE of the same variable location.
128 /// This is necessary to detect sequences such as:
129 /// %0 = someinst
130 /// DBG_VALUE %0, !123, !DIExpression()
131 /// %1 = anotherinst
132 /// DBG_VALUE %1, !123, !DIExpression()
133 /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
134 /// would re-order assignments.
135 using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
136
137 /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
138 /// debug instructions to sink.
139 SmallDenseMap<unsigned, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;
140
141 /// Record of debug variables that have had their locations set in the
142 /// current block.
143 DenseSet<DebugVariable> SeenDbgVars;
144
145 std::map<std::pair<MachineBasicBlock *, MachineBasicBlock *>, bool>
146 HasStoreCache;
147 std::map<std::pair<MachineBasicBlock *, MachineBasicBlock *>,
148 std::vector<MachineInstr *>>
149 StoreInstrCache;
150
151 /// Cached BB's register pressure.
152 std::map<MachineBasicBlock *, std::vector<unsigned>> CachedRegisterPressure;
153
154 public:
155 static char ID; // Pass identification
156
MachineSinking()157 MachineSinking() : MachineFunctionPass(ID) {
158 initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
159 }
160
161 bool runOnMachineFunction(MachineFunction &MF) override;
162
getAnalysisUsage(AnalysisUsage & AU) const163 void getAnalysisUsage(AnalysisUsage &AU) const override {
164 MachineFunctionPass::getAnalysisUsage(AU);
165 AU.addRequired<AAResultsWrapperPass>();
166 AU.addRequired<MachineDominatorTree>();
167 AU.addRequired<MachinePostDominatorTree>();
168 AU.addRequired<MachineLoopInfo>();
169 AU.addRequired<MachineBranchProbabilityInfo>();
170 AU.addPreserved<MachineLoopInfo>();
171 if (UseBlockFreqInfo)
172 AU.addRequired<MachineBlockFrequencyInfo>();
173 }
174
releaseMemory()175 void releaseMemory() override {
176 CEBCandidates.clear();
177 }
178
179 private:
180 bool ProcessBlock(MachineBasicBlock &MBB);
181 void ProcessDbgInst(MachineInstr &MI);
182 bool isWorthBreakingCriticalEdge(MachineInstr &MI,
183 MachineBasicBlock *From,
184 MachineBasicBlock *To);
185
186 bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
187 MachineInstr &MI);
188
189 /// Postpone the splitting of the given critical
190 /// edge (\p From, \p To).
191 ///
192 /// We do not split the edges on the fly. Indeed, this invalidates
193 /// the dominance information and thus triggers a lot of updates
194 /// of that information underneath.
195 /// Instead, we postpone all the splits after each iteration of
196 /// the main loop. That way, the information is at least valid
197 /// for the lifetime of an iteration.
198 ///
199 /// \return True if the edge is marked as toSplit, false otherwise.
200 /// False can be returned if, for instance, this is not profitable.
201 bool PostponeSplitCriticalEdge(MachineInstr &MI,
202 MachineBasicBlock *From,
203 MachineBasicBlock *To,
204 bool BreakPHIEdge);
205 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
206 AllSuccsCache &AllSuccessors);
207
208 /// If we sink a COPY inst, some debug users of it's destination may no
209 /// longer be dominated by the COPY, and will eventually be dropped.
210 /// This is easily rectified by forwarding the non-dominated debug uses
211 /// to the copy source.
212 void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
213 MachineBasicBlock *TargetBlock);
214 bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
215 MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
216 bool &LocalUse) const;
217 MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
218 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
219 bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
220 MachineBasicBlock *MBB,
221 MachineBasicBlock *SuccToSinkTo,
222 AllSuccsCache &AllSuccessors);
223
224 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
225 MachineBasicBlock *MBB);
226
227 SmallVector<MachineBasicBlock *, 4> &
228 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
229 AllSuccsCache &AllSuccessors) const;
230
231 std::vector<unsigned> &getBBRegisterPressure(MachineBasicBlock &MBB);
232 };
233
234 } // end anonymous namespace
235
236 char MachineSinking::ID = 0;
237
238 char &llvm::MachineSinkingID = MachineSinking::ID;
239
240 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
241 "Machine code sinking", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)242 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
243 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
244 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
245 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
246 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
247 "Machine code sinking", false, false)
248
249 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
250 MachineBasicBlock *MBB) {
251 if (!MI.isCopy())
252 return false;
253
254 Register SrcReg = MI.getOperand(1).getReg();
255 Register DstReg = MI.getOperand(0).getReg();
256 if (!Register::isVirtualRegister(SrcReg) ||
257 !Register::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg))
258 return false;
259
260 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
261 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
262 if (SRC != DRC)
263 return false;
264
265 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
266 if (DefMI->isCopyLike())
267 return false;
268 LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
269 LLVM_DEBUG(dbgs() << "*** to: " << MI);
270 MRI->replaceRegWith(DstReg, SrcReg);
271 MI.eraseFromParent();
272
273 // Conservatively, clear any kill flags, since it's possible that they are no
274 // longer correct.
275 MRI->clearKillFlags(SrcReg);
276
277 ++NumCoalesces;
278 return true;
279 }
280
281 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
282 /// occur in blocks dominated by the specified block. If any use is in the
283 /// definition block, then return false since it is never legal to move def
284 /// after uses.
AllUsesDominatedByBlock(Register Reg,MachineBasicBlock * MBB,MachineBasicBlock * DefMBB,bool & BreakPHIEdge,bool & LocalUse) const285 bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
286 MachineBasicBlock *MBB,
287 MachineBasicBlock *DefMBB,
288 bool &BreakPHIEdge,
289 bool &LocalUse) const {
290 assert(Register::isVirtualRegister(Reg) && "Only makes sense for vregs");
291
292 // Ignore debug uses because debug info doesn't affect the code.
293 if (MRI->use_nodbg_empty(Reg))
294 return true;
295
296 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
297 // into and they are all PHI nodes. In this case, machine-sink must break
298 // the critical edge first. e.g.
299 //
300 // %bb.1:
301 // Predecessors according to CFG: %bb.0
302 // ...
303 // %def = DEC64_32r %x, implicit-def dead %eflags
304 // ...
305 // JE_4 <%bb.37>, implicit %eflags
306 // Successors according to CFG: %bb.37 %bb.2
307 //
308 // %bb.2:
309 // %p = PHI %y, %bb.0, %def, %bb.1
310 if (all_of(MRI->use_nodbg_operands(Reg), [&](MachineOperand &MO) {
311 MachineInstr *UseInst = MO.getParent();
312 unsigned OpNo = UseInst->getOperandNo(&MO);
313 MachineBasicBlock *UseBlock = UseInst->getParent();
314 return UseBlock == MBB && UseInst->isPHI() &&
315 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
316 })) {
317 BreakPHIEdge = true;
318 return true;
319 }
320
321 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
322 // Determine the block of the use.
323 MachineInstr *UseInst = MO.getParent();
324 unsigned OpNo = &MO - &UseInst->getOperand(0);
325 MachineBasicBlock *UseBlock = UseInst->getParent();
326 if (UseInst->isPHI()) {
327 // PHI nodes use the operand in the predecessor block, not the block with
328 // the PHI.
329 UseBlock = UseInst->getOperand(OpNo+1).getMBB();
330 } else if (UseBlock == DefMBB) {
331 LocalUse = true;
332 return false;
333 }
334
335 // Check that it dominates.
336 if (!DT->dominates(MBB, UseBlock))
337 return false;
338 }
339
340 return true;
341 }
342
runOnMachineFunction(MachineFunction & MF)343 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
344 if (skipFunction(MF.getFunction()))
345 return false;
346
347 LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
348
349 TII = MF.getSubtarget().getInstrInfo();
350 TRI = MF.getSubtarget().getRegisterInfo();
351 MRI = &MF.getRegInfo();
352 DT = &getAnalysis<MachineDominatorTree>();
353 PDT = &getAnalysis<MachinePostDominatorTree>();
354 LI = &getAnalysis<MachineLoopInfo>();
355 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
356 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
357 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
358 RegClassInfo.runOnMachineFunction(MF);
359
360 bool EverMadeChange = false;
361
362 while (true) {
363 bool MadeChange = false;
364
365 // Process all basic blocks.
366 CEBCandidates.clear();
367 ToSplit.clear();
368 for (auto &MBB: MF)
369 MadeChange |= ProcessBlock(MBB);
370
371 // If we have anything we marked as toSplit, split it now.
372 for (auto &Pair : ToSplit) {
373 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
374 if (NewSucc != nullptr) {
375 LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
376 << printMBBReference(*Pair.first) << " -- "
377 << printMBBReference(*NewSucc) << " -- "
378 << printMBBReference(*Pair.second) << '\n');
379 if (MBFI)
380 MBFI->onEdgeSplit(*Pair.first, *NewSucc, *MBPI);
381
382 MadeChange = true;
383 ++NumSplit;
384 } else
385 LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
386 }
387 // If this iteration over the code changed anything, keep iterating.
388 if (!MadeChange) break;
389 EverMadeChange = true;
390 }
391
392 HasStoreCache.clear();
393 StoreInstrCache.clear();
394
395 // Now clear any kill flags for recorded registers.
396 for (auto I : RegsToClearKillFlags)
397 MRI->clearKillFlags(I);
398 RegsToClearKillFlags.clear();
399
400 return EverMadeChange;
401 }
402
ProcessBlock(MachineBasicBlock & MBB)403 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
404 // Can't sink anything out of a block that has less than two successors.
405 if (MBB.succ_size() <= 1 || MBB.empty()) return false;
406
407 // Don't bother sinking code out of unreachable blocks. In addition to being
408 // unprofitable, it can also lead to infinite looping, because in an
409 // unreachable loop there may be nowhere to stop.
410 if (!DT->isReachableFromEntry(&MBB)) return false;
411
412 bool MadeChange = false;
413
414 // Cache all successors, sorted by frequency info and loop depth.
415 AllSuccsCache AllSuccessors;
416
417 // Walk the basic block bottom-up. Remember if we saw a store.
418 MachineBasicBlock::iterator I = MBB.end();
419 --I;
420 bool ProcessedBegin, SawStore = false;
421 do {
422 MachineInstr &MI = *I; // The instruction to sink.
423
424 // Predecrement I (if it's not begin) so that it isn't invalidated by
425 // sinking.
426 ProcessedBegin = I == MBB.begin();
427 if (!ProcessedBegin)
428 --I;
429
430 if (MI.isDebugInstr()) {
431 if (MI.isDebugValue())
432 ProcessDbgInst(MI);
433 continue;
434 }
435
436 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
437 if (Joined) {
438 MadeChange = true;
439 continue;
440 }
441
442 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
443 ++NumSunk;
444 MadeChange = true;
445 }
446
447 // If we just processed the first instruction in the block, we're done.
448 } while (!ProcessedBegin);
449
450 SeenDbgUsers.clear();
451 SeenDbgVars.clear();
452 // recalculate the bb register pressure after sinking one BB.
453 CachedRegisterPressure.clear();
454
455 return MadeChange;
456 }
457
ProcessDbgInst(MachineInstr & MI)458 void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
459 // When we see DBG_VALUEs for registers, record any vreg it reads, so that
460 // we know what to sink if the vreg def sinks.
461 assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
462
463 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
464 MI.getDebugLoc()->getInlinedAt());
465 bool SeenBefore = SeenDbgVars.contains(Var);
466
467 MachineOperand &MO = MI.getDebugOperand(0);
468 if (MO.isReg() && MO.getReg().isVirtual())
469 SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));
470
471 // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
472 SeenDbgVars.insert(Var);
473 }
474
isWorthBreakingCriticalEdge(MachineInstr & MI,MachineBasicBlock * From,MachineBasicBlock * To)475 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
476 MachineBasicBlock *From,
477 MachineBasicBlock *To) {
478 // FIXME: Need much better heuristics.
479
480 // If the pass has already considered breaking this edge (during this pass
481 // through the function), then let's go ahead and break it. This means
482 // sinking multiple "cheap" instructions into the same block.
483 if (!CEBCandidates.insert(std::make_pair(From, To)).second)
484 return true;
485
486 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
487 return true;
488
489 if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
490 BranchProbability(SplitEdgeProbabilityThreshold, 100))
491 return true;
492
493 // MI is cheap, we probably don't want to break the critical edge for it.
494 // However, if this would allow some definitions of its source operands
495 // to be sunk then it's probably worth it.
496 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
497 const MachineOperand &MO = MI.getOperand(i);
498 if (!MO.isReg() || !MO.isUse())
499 continue;
500 Register Reg = MO.getReg();
501 if (Reg == 0)
502 continue;
503
504 // We don't move live definitions of physical registers,
505 // so sinking their uses won't enable any opportunities.
506 if (Register::isPhysicalRegister(Reg))
507 continue;
508
509 // If this instruction is the only user of a virtual register,
510 // check if breaking the edge will enable sinking
511 // both this instruction and the defining instruction.
512 if (MRI->hasOneNonDBGUse(Reg)) {
513 // If the definition resides in same MBB,
514 // claim it's likely we can sink these together.
515 // If definition resides elsewhere, we aren't
516 // blocking it from being sunk so don't break the edge.
517 MachineInstr *DefMI = MRI->getVRegDef(Reg);
518 if (DefMI->getParent() == MI.getParent())
519 return true;
520 }
521 }
522
523 return false;
524 }
525
PostponeSplitCriticalEdge(MachineInstr & MI,MachineBasicBlock * FromBB,MachineBasicBlock * ToBB,bool BreakPHIEdge)526 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
527 MachineBasicBlock *FromBB,
528 MachineBasicBlock *ToBB,
529 bool BreakPHIEdge) {
530 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
531 return false;
532
533 // Avoid breaking back edge. From == To means backedge for single BB loop.
534 if (!SplitEdges || FromBB == ToBB)
535 return false;
536
537 // Check for backedges of more "complex" loops.
538 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
539 LI->isLoopHeader(ToBB))
540 return false;
541
542 // It's not always legal to break critical edges and sink the computation
543 // to the edge.
544 //
545 // %bb.1:
546 // v1024
547 // Beq %bb.3
548 // <fallthrough>
549 // %bb.2:
550 // ... no uses of v1024
551 // <fallthrough>
552 // %bb.3:
553 // ...
554 // = v1024
555 //
556 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
557 //
558 // %bb.1:
559 // ...
560 // Bne %bb.2
561 // %bb.4:
562 // v1024 =
563 // B %bb.3
564 // %bb.2:
565 // ... no uses of v1024
566 // <fallthrough>
567 // %bb.3:
568 // ...
569 // = v1024
570 //
571 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
572 // flow. We need to ensure the new basic block where the computation is
573 // sunk to dominates all the uses.
574 // It's only legal to break critical edge and sink the computation to the
575 // new block if all the predecessors of "To", except for "From", are
576 // not dominated by "From". Given SSA property, this means these
577 // predecessors are dominated by "To".
578 //
579 // There is no need to do this check if all the uses are PHI nodes. PHI
580 // sources are only defined on the specific predecessor edges.
581 if (!BreakPHIEdge) {
582 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
583 E = ToBB->pred_end(); PI != E; ++PI) {
584 if (*PI == FromBB)
585 continue;
586 if (!DT->dominates(ToBB, *PI))
587 return false;
588 }
589 }
590
591 ToSplit.insert(std::make_pair(FromBB, ToBB));
592
593 return true;
594 }
595
596 std::vector<unsigned> &
getBBRegisterPressure(MachineBasicBlock & MBB)597 MachineSinking::getBBRegisterPressure(MachineBasicBlock &MBB) {
598 // Currently to save compiling time, MBB's register pressure will not change
599 // in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's
600 // register pressure is changed after sinking any instructions into it.
601 // FIXME: need a accurate and cheap register pressure estiminate model here.
602 auto RP = CachedRegisterPressure.find(&MBB);
603 if (RP != CachedRegisterPressure.end())
604 return RP->second;
605
606 RegionPressure Pressure;
607 RegPressureTracker RPTracker(Pressure);
608
609 // Initialize the register pressure tracker.
610 RPTracker.init(MBB.getParent(), &RegClassInfo, nullptr, &MBB, MBB.end(),
611 /*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);
612
613 for (MachineBasicBlock::iterator MII = MBB.instr_end(),
614 MIE = MBB.instr_begin();
615 MII != MIE; --MII) {
616 MachineInstr &MI = *std::prev(MII);
617 if (MI.isDebugValue() || MI.isDebugLabel())
618 continue;
619 RegisterOperands RegOpers;
620 RegOpers.collect(MI, *TRI, *MRI, false, false);
621 RPTracker.recedeSkipDebugValues();
622 assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");
623 RPTracker.recede(RegOpers);
624 }
625
626 RPTracker.closeRegion();
627 auto It = CachedRegisterPressure.insert(
628 std::make_pair(&MBB, RPTracker.getPressure().MaxSetPressure));
629 return It.first->second;
630 }
631
632 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
isProfitableToSinkTo(Register Reg,MachineInstr & MI,MachineBasicBlock * MBB,MachineBasicBlock * SuccToSinkTo,AllSuccsCache & AllSuccessors)633 bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
634 MachineBasicBlock *MBB,
635 MachineBasicBlock *SuccToSinkTo,
636 AllSuccsCache &AllSuccessors) {
637 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
638
639 if (MBB == SuccToSinkTo)
640 return false;
641
642 // It is profitable if SuccToSinkTo does not post dominate current block.
643 if (!PDT->dominates(SuccToSinkTo, MBB))
644 return true;
645
646 // It is profitable to sink an instruction from a deeper loop to a shallower
647 // loop, even if the latter post-dominates the former (PR21115).
648 if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
649 return true;
650
651 // Check if only use in post dominated block is PHI instruction.
652 bool NonPHIUse = false;
653 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
654 MachineBasicBlock *UseBlock = UseInst.getParent();
655 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
656 NonPHIUse = true;
657 }
658 if (!NonPHIUse)
659 return true;
660
661 // If SuccToSinkTo post dominates then also it may be profitable if MI
662 // can further profitably sinked into another block in next round.
663 bool BreakPHIEdge = false;
664 // FIXME - If finding successor is compile time expensive then cache results.
665 if (MachineBasicBlock *MBB2 =
666 FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
667 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
668
669 MachineLoop *ML = LI->getLoopFor(MBB);
670
671 // If the instruction is not inside a loop, it is not profitable to sink MI to
672 // a post dominate block SuccToSinkTo.
673 if (!ML)
674 return false;
675
676 auto isRegisterPressureSetExceedLimit = [&](const TargetRegisterClass *RC) {
677 unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
678 const int *PS = TRI->getRegClassPressureSets(RC);
679 // Get register pressure for block SuccToSinkTo.
680 std::vector<unsigned> BBRegisterPressure =
681 getBBRegisterPressure(*SuccToSinkTo);
682 for (; *PS != -1; PS++)
683 // check if any register pressure set exceeds limit in block SuccToSinkTo
684 // after sinking.
685 if (Weight + BBRegisterPressure[*PS] >=
686 TRI->getRegPressureSetLimit(*MBB->getParent(), *PS))
687 return true;
688 return false;
689 };
690
691 // If this instruction is inside a loop and sinking this instruction can make
692 // more registers live range shorten, it is still prifitable.
693 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
694 const MachineOperand &MO = MI.getOperand(i);
695 // Ignore non-register operands.
696 if (!MO.isReg())
697 continue;
698 Register Reg = MO.getReg();
699 if (Reg == 0)
700 continue;
701
702 // Don't handle physical register.
703 if (Register::isPhysicalRegister(Reg))
704 return false;
705
706 // Users for the defs are all dominated by SuccToSinkTo.
707 if (MO.isDef()) {
708 // This def register's live range is shortened after sinking.
709 bool LocalUse = false;
710 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
711 LocalUse))
712 return false;
713 } else {
714 MachineInstr *DefMI = MRI->getVRegDef(Reg);
715 // DefMI is defined outside of loop. There should be no live range
716 // impact for this operand. Defination outside of loop means:
717 // 1: defination is outside of loop.
718 // 2: defination is in this loop, but it is a PHI in the loop header.
719 if (LI->getLoopFor(DefMI->getParent()) != ML ||
720 (DefMI->isPHI() && LI->isLoopHeader(DefMI->getParent())))
721 continue;
722 // The DefMI is defined inside the loop.
723 // If sinking this operand makes some register pressure set exceed limit,
724 // it is not profitable.
725 if (isRegisterPressureSetExceedLimit(MRI->getRegClass(Reg))) {
726 LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
727 return false;
728 }
729 }
730 }
731
732 // If MI is in loop and all its operands are alive across the whole loop or if
733 // no operand sinking make register pressure set exceed limit, it is
734 // profitable to sink MI.
735 return true;
736 }
737
738 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
739 /// computing it if it was not already cached.
740 SmallVector<MachineBasicBlock *, 4> &
GetAllSortedSuccessors(MachineInstr & MI,MachineBasicBlock * MBB,AllSuccsCache & AllSuccessors) const741 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
742 AllSuccsCache &AllSuccessors) const {
743 // Do we have the sorted successors in cache ?
744 auto Succs = AllSuccessors.find(MBB);
745 if (Succs != AllSuccessors.end())
746 return Succs->second;
747
748 SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->successors());
749
750 // Handle cases where sinking can happen but where the sink point isn't a
751 // successor. For example:
752 //
753 // x = computation
754 // if () {} else {}
755 // use x
756 //
757 for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {
758 // DomTree children of MBB that have MBB as immediate dominator are added.
759 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
760 // Skip MBBs already added to the AllSuccs vector above.
761 !MBB->isSuccessor(DTChild->getBlock()))
762 AllSuccs.push_back(DTChild->getBlock());
763 }
764
765 // Sort Successors according to their loop depth or block frequency info.
766 llvm::stable_sort(
767 AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
768 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
769 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
770 bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
771 return HasBlockFreq ? LHSFreq < RHSFreq
772 : LI->getLoopDepth(L) < LI->getLoopDepth(R);
773 });
774
775 auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
776
777 return it.first->second;
778 }
779
780 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
781 MachineBasicBlock *
FindSuccToSinkTo(MachineInstr & MI,MachineBasicBlock * MBB,bool & BreakPHIEdge,AllSuccsCache & AllSuccessors)782 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
783 bool &BreakPHIEdge,
784 AllSuccsCache &AllSuccessors) {
785 assert (MBB && "Invalid MachineBasicBlock!");
786
787 // Loop over all the operands of the specified instruction. If there is
788 // anything we can't handle, bail out.
789
790 // SuccToSinkTo - This is the successor to sink this instruction to, once we
791 // decide.
792 MachineBasicBlock *SuccToSinkTo = nullptr;
793 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
794 const MachineOperand &MO = MI.getOperand(i);
795 if (!MO.isReg()) continue; // Ignore non-register operands.
796
797 Register Reg = MO.getReg();
798 if (Reg == 0) continue;
799
800 if (Register::isPhysicalRegister(Reg)) {
801 if (MO.isUse()) {
802 // If the physreg has no defs anywhere, it's just an ambient register
803 // and we can freely move its uses. Alternatively, if it's allocatable,
804 // it could get allocated to something with a def during allocation.
805 if (!MRI->isConstantPhysReg(Reg))
806 return nullptr;
807 } else if (!MO.isDead()) {
808 // A def that isn't dead. We can't move it.
809 return nullptr;
810 }
811 } else {
812 // Virtual register uses are always safe to sink.
813 if (MO.isUse()) continue;
814
815 // If it's not safe to move defs of the register class, then abort.
816 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
817 return nullptr;
818
819 // Virtual register defs can only be sunk if all their uses are in blocks
820 // dominated by one of the successors.
821 if (SuccToSinkTo) {
822 // If a previous operand picked a block to sink to, then this operand
823 // must be sinkable to the same block.
824 bool LocalUse = false;
825 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
826 BreakPHIEdge, LocalUse))
827 return nullptr;
828
829 continue;
830 }
831
832 // Otherwise, we should look at all the successors and decide which one
833 // we should sink to. If we have reliable block frequency information
834 // (frequency != 0) available, give successors with smaller frequencies
835 // higher priority, otherwise prioritize smaller loop depths.
836 for (MachineBasicBlock *SuccBlock :
837 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
838 bool LocalUse = false;
839 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
840 BreakPHIEdge, LocalUse)) {
841 SuccToSinkTo = SuccBlock;
842 break;
843 }
844 if (LocalUse)
845 // Def is used locally, it's never safe to move this def.
846 return nullptr;
847 }
848
849 // If we couldn't find a block to sink to, ignore this instruction.
850 if (!SuccToSinkTo)
851 return nullptr;
852 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
853 return nullptr;
854 }
855 }
856
857 // It is not possible to sink an instruction into its own block. This can
858 // happen with loops.
859 if (MBB == SuccToSinkTo)
860 return nullptr;
861
862 // It's not safe to sink instructions to EH landing pad. Control flow into
863 // landing pad is implicitly defined.
864 if (SuccToSinkTo && SuccToSinkTo->isEHPad())
865 return nullptr;
866
867 // It ought to be okay to sink instructions into an INLINEASM_BR target, but
868 // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
869 // the source block (which this code does not yet do). So for now, forbid
870 // doing so.
871 if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
872 return nullptr;
873
874 return SuccToSinkTo;
875 }
876
877 /// Return true if MI is likely to be usable as a memory operation by the
878 /// implicit null check optimization.
879 ///
880 /// This is a "best effort" heuristic, and should not be relied upon for
881 /// correctness. This returning true does not guarantee that the implicit null
882 /// check optimization is legal over MI, and this returning false does not
883 /// guarantee MI cannot possibly be used to do a null check.
SinkingPreventsImplicitNullCheck(MachineInstr & MI,const TargetInstrInfo * TII,const TargetRegisterInfo * TRI)884 static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
885 const TargetInstrInfo *TII,
886 const TargetRegisterInfo *TRI) {
887 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
888
889 auto *MBB = MI.getParent();
890 if (MBB->pred_size() != 1)
891 return false;
892
893 auto *PredMBB = *MBB->pred_begin();
894 auto *PredBB = PredMBB->getBasicBlock();
895
896 // Frontends that don't use implicit null checks have no reason to emit
897 // branches with make.implicit metadata, and this function should always
898 // return false for them.
899 if (!PredBB ||
900 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
901 return false;
902
903 const MachineOperand *BaseOp;
904 int64_t Offset;
905 bool OffsetIsScalable;
906 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
907 return false;
908
909 if (!BaseOp->isReg())
910 return false;
911
912 if (!(MI.mayLoad() && !MI.isPredicable()))
913 return false;
914
915 MachineBranchPredicate MBP;
916 if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
917 return false;
918
919 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
920 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
921 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
922 MBP.LHS.getReg() == BaseOp->getReg();
923 }
924
925 /// If the sunk instruction is a copy, try to forward the copy instead of
926 /// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
927 /// there's any subregister weirdness involved. Returns true if copy
928 /// propagation occurred.
attemptDebugCopyProp(MachineInstr & SinkInst,MachineInstr & DbgMI)929 static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI) {
930 const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
931 const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
932
933 // Copy DBG_VALUE operand and set the original to undef. We then check to
934 // see whether this is something that can be copy-forwarded. If it isn't,
935 // continue around the loop.
936 MachineOperand &DbgMO = DbgMI.getDebugOperand(0);
937
938 const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
939 auto CopyOperands = TII.isCopyInstr(SinkInst);
940 if (!CopyOperands)
941 return false;
942 SrcMO = CopyOperands->Source;
943 DstMO = CopyOperands->Destination;
944
945 // Check validity of forwarding this copy.
946 bool PostRA = MRI.getNumVirtRegs() == 0;
947
948 // Trying to forward between physical and virtual registers is too hard.
949 if (DbgMO.getReg().isVirtual() != SrcMO->getReg().isVirtual())
950 return false;
951
952 // Only try virtual register copy-forwarding before regalloc, and physical
953 // register copy-forwarding after regalloc.
954 bool arePhysRegs = !DbgMO.getReg().isVirtual();
955 if (arePhysRegs != PostRA)
956 return false;
957
958 // Pre-regalloc, only forward if all subregisters agree (or there are no
959 // subregs at all). More analysis might recover some forwardable copies.
960 if (!PostRA && (DbgMO.getSubReg() != SrcMO->getSubReg() ||
961 DbgMO.getSubReg() != DstMO->getSubReg()))
962 return false;
963
964 // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
965 // of this copy. Only forward the copy if the DBG_VALUE operand exactly
966 // matches the copy destination.
967 if (PostRA && DbgMO.getReg() != DstMO->getReg())
968 return false;
969
970 DbgMO.setReg(SrcMO->getReg());
971 DbgMO.setSubReg(SrcMO->getSubReg());
972 return true;
973 }
974
975 /// Sink an instruction and its associated debug instructions.
performSink(MachineInstr & MI,MachineBasicBlock & SuccToSinkTo,MachineBasicBlock::iterator InsertPos,SmallVectorImpl<MachineInstr * > & DbgValuesToSink)976 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
977 MachineBasicBlock::iterator InsertPos,
978 SmallVectorImpl<MachineInstr *> &DbgValuesToSink) {
979
980 // If we cannot find a location to use (merge with), then we erase the debug
981 // location to prevent debug-info driven tools from potentially reporting
982 // wrong location information.
983 if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
984 MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
985 InsertPos->getDebugLoc()));
986 else
987 MI.setDebugLoc(DebugLoc());
988
989 // Move the instruction.
990 MachineBasicBlock *ParentBlock = MI.getParent();
991 SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
992 ++MachineBasicBlock::iterator(MI));
993
994 // Sink a copy of debug users to the insert position. Mark the original
995 // DBG_VALUE location as 'undef', indicating that any earlier variable
996 // location should be terminated as we've optimised away the value at this
997 // point.
998 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
999 DBE = DbgValuesToSink.end();
1000 DBI != DBE; ++DBI) {
1001 MachineInstr *DbgMI = *DBI;
1002 MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(*DBI);
1003 SuccToSinkTo.insert(InsertPos, NewDbgMI);
1004
1005 if (!attemptDebugCopyProp(MI, *DbgMI))
1006 DbgMI->setDebugValueUndef();
1007 }
1008 }
1009
1010 /// hasStoreBetween - check if there is store betweeen straight line blocks From
1011 /// and To.
hasStoreBetween(MachineBasicBlock * From,MachineBasicBlock * To,MachineInstr & MI)1012 bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
1013 MachineBasicBlock *To, MachineInstr &MI) {
1014 // Make sure From and To are in straight line which means From dominates To
1015 // and To post dominates From.
1016 if (!DT->dominates(From, To) || !PDT->dominates(To, From))
1017 return true;
1018
1019 auto BlockPair = std::make_pair(From, To);
1020
1021 // Does these two blocks pair be queried before and have a definite cached
1022 // result?
1023 if (HasStoreCache.find(BlockPair) != HasStoreCache.end())
1024 return HasStoreCache[BlockPair];
1025
1026 if (StoreInstrCache.find(BlockPair) != StoreInstrCache.end())
1027 return llvm::any_of(StoreInstrCache[BlockPair], [&](MachineInstr *I) {
1028 return I->mayAlias(AA, MI, false);
1029 });
1030
1031 bool SawStore = false;
1032 bool HasAliasedStore = false;
1033 DenseSet<MachineBasicBlock *> HandledBlocks;
1034 DenseSet<MachineBasicBlock *> HandledDomBlocks;
1035 // Go through all reachable blocks from From.
1036 for (MachineBasicBlock *BB : depth_first(From)) {
1037 // We insert the instruction at the start of block To, so no need to worry
1038 // about stores inside To.
1039 // Store in block From should be already considered when just enter function
1040 // SinkInstruction.
1041 if (BB == To || BB == From)
1042 continue;
1043
1044 // We already handle this BB in previous iteration.
1045 if (HandledBlocks.count(BB))
1046 continue;
1047
1048 HandledBlocks.insert(BB);
1049 // To post dominates BB, it must be a path from block From.
1050 if (PDT->dominates(To, BB)) {
1051 if (!HandledDomBlocks.count(BB))
1052 HandledDomBlocks.insert(BB);
1053
1054 // If this BB is too big or the block number in straight line between From
1055 // and To is too big, stop searching to save compiling time.
1056 if (BB->size() > SinkLoadInstsPerBlockThreshold ||
1057 HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
1058 for (auto *DomBB : HandledDomBlocks) {
1059 if (DomBB != BB && DT->dominates(DomBB, BB))
1060 HasStoreCache[std::make_pair(DomBB, To)] = true;
1061 else if(DomBB != BB && DT->dominates(BB, DomBB))
1062 HasStoreCache[std::make_pair(From, DomBB)] = true;
1063 }
1064 HasStoreCache[BlockPair] = true;
1065 return true;
1066 }
1067
1068 for (MachineInstr &I : *BB) {
1069 // Treat as alias conservatively for a call or an ordered memory
1070 // operation.
1071 if (I.isCall() || I.hasOrderedMemoryRef()) {
1072 for (auto *DomBB : HandledDomBlocks) {
1073 if (DomBB != BB && DT->dominates(DomBB, BB))
1074 HasStoreCache[std::make_pair(DomBB, To)] = true;
1075 else if(DomBB != BB && DT->dominates(BB, DomBB))
1076 HasStoreCache[std::make_pair(From, DomBB)] = true;
1077 }
1078 HasStoreCache[BlockPair] = true;
1079 return true;
1080 }
1081
1082 if (I.mayStore()) {
1083 SawStore = true;
1084 // We still have chance to sink MI if all stores between are not
1085 // aliased to MI.
1086 // Cache all store instructions, so that we don't need to go through
1087 // all From reachable blocks for next load instruction.
1088 if (I.mayAlias(AA, MI, false))
1089 HasAliasedStore = true;
1090 StoreInstrCache[BlockPair].push_back(&I);
1091 }
1092 }
1093 }
1094 }
1095 // If there is no store at all, cache the result.
1096 if (!SawStore)
1097 HasStoreCache[BlockPair] = false;
1098 return HasAliasedStore;
1099 }
1100
1101 /// SinkInstruction - Determine whether it is safe to sink the specified machine
1102 /// instruction out of its current block into a successor.
SinkInstruction(MachineInstr & MI,bool & SawStore,AllSuccsCache & AllSuccessors)1103 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
1104 AllSuccsCache &AllSuccessors) {
1105 // Don't sink instructions that the target prefers not to sink.
1106 if (!TII->shouldSink(MI))
1107 return false;
1108
1109 // Check if it's safe to move the instruction.
1110 if (!MI.isSafeToMove(AA, SawStore))
1111 return false;
1112
1113 // Convergent operations may not be made control-dependent on additional
1114 // values.
1115 if (MI.isConvergent())
1116 return false;
1117
1118 // Don't break implicit null checks. This is a performance heuristic, and not
1119 // required for correctness.
1120 if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
1121 return false;
1122
1123 // FIXME: This should include support for sinking instructions within the
1124 // block they are currently in to shorten the live ranges. We often get
1125 // instructions sunk into the top of a large block, but it would be better to
1126 // also sink them down before their first use in the block. This xform has to
1127 // be careful not to *increase* register pressure though, e.g. sinking
1128 // "x = y + z" down if it kills y and z would increase the live ranges of y
1129 // and z and only shrink the live range of x.
1130
1131 bool BreakPHIEdge = false;
1132 MachineBasicBlock *ParentBlock = MI.getParent();
1133 MachineBasicBlock *SuccToSinkTo =
1134 FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1135
1136 // If there are no outputs, it must have side-effects.
1137 if (!SuccToSinkTo)
1138 return false;
1139
1140 // If the instruction to move defines a dead physical register which is live
1141 // when leaving the basic block, don't move it because it could turn into a
1142 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
1143 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
1144 const MachineOperand &MO = MI.getOperand(I);
1145 if (!MO.isReg()) continue;
1146 Register Reg = MO.getReg();
1147 if (Reg == 0 || !Register::isPhysicalRegister(Reg))
1148 continue;
1149 if (SuccToSinkTo->isLiveIn(Reg))
1150 return false;
1151 }
1152
1153 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
1154
1155 // If the block has multiple predecessors, this is a critical edge.
1156 // Decide if we can sink along it or need to break the edge.
1157 if (SuccToSinkTo->pred_size() > 1) {
1158 // We cannot sink a load across a critical edge - there may be stores in
1159 // other code paths.
1160 bool TryBreak = false;
1161 bool Store =
1162 MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo, MI) : true;
1163 if (!MI.isSafeToMove(AA, Store)) {
1164 LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
1165 TryBreak = true;
1166 }
1167
1168 // We don't want to sink across a critical edge if we don't dominate the
1169 // successor. We could be introducing calculations to new code paths.
1170 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
1171 LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
1172 TryBreak = true;
1173 }
1174
1175 // Don't sink instructions into a loop.
1176 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
1177 LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
1178 TryBreak = true;
1179 }
1180
1181 // Otherwise we are OK with sinking along a critical edge.
1182 if (!TryBreak)
1183 LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
1184 else {
1185 // Mark this edge as to be split.
1186 // If the edge can actually be split, the next iteration of the main loop
1187 // will sink MI in the newly created block.
1188 bool Status =
1189 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1190 if (!Status)
1191 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1192 "break critical edge\n");
1193 // The instruction will not be sunk this time.
1194 return false;
1195 }
1196 }
1197
1198 if (BreakPHIEdge) {
1199 // BreakPHIEdge is true if all the uses are in the successor MBB being
1200 // sunken into and they are all PHI nodes. In this case, machine-sink must
1201 // break the critical edge first.
1202 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
1203 SuccToSinkTo, BreakPHIEdge);
1204 if (!Status)
1205 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1206 "break critical edge\n");
1207 // The instruction will not be sunk this time.
1208 return false;
1209 }
1210
1211 // Determine where to insert into. Skip phi nodes.
1212 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
1213 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
1214 ++InsertPos;
1215
1216 // Collect debug users of any vreg that this inst defines.
1217 SmallVector<MachineInstr *, 4> DbgUsersToSink;
1218 for (auto &MO : MI.operands()) {
1219 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1220 continue;
1221 if (!SeenDbgUsers.count(MO.getReg()))
1222 continue;
1223
1224 // Sink any users that don't pass any other DBG_VALUEs for this variable.
1225 auto &Users = SeenDbgUsers[MO.getReg()];
1226 for (auto &User : Users) {
1227 MachineInstr *DbgMI = User.getPointer();
1228 if (User.getInt()) {
1229 // This DBG_VALUE would re-order assignments. If we can't copy-propagate
1230 // it, it can't be recovered. Set it undef.
1231 if (!attemptDebugCopyProp(MI, *DbgMI))
1232 DbgMI->setDebugValueUndef();
1233 } else {
1234 DbgUsersToSink.push_back(DbgMI);
1235 }
1236 }
1237 }
1238
1239 // After sinking, some debug users may not be dominated any more. If possible,
1240 // copy-propagate their operands. As it's expensive, don't do this if there's
1241 // no debuginfo in the program.
1242 if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1243 SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
1244
1245 performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);
1246
1247 // Conservatively, clear any kill flags, since it's possible that they are no
1248 // longer correct.
1249 // Note that we have to clear the kill flags for any register this instruction
1250 // uses as we may sink over another instruction which currently kills the
1251 // used registers.
1252 for (MachineOperand &MO : MI.operands()) {
1253 if (MO.isReg() && MO.isUse())
1254 RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
1255 }
1256
1257 return true;
1258 }
1259
SalvageUnsunkDebugUsersOfCopy(MachineInstr & MI,MachineBasicBlock * TargetBlock)1260 void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1261 MachineInstr &MI, MachineBasicBlock *TargetBlock) {
1262 assert(MI.isCopy());
1263 assert(MI.getOperand(1).isReg());
1264
1265 // Enumerate all users of vreg operands that are def'd. Skip those that will
1266 // be sunk. For the rest, if they are not dominated by the block we will sink
1267 // MI into, propagate the copy source to them.
1268 SmallVector<MachineInstr *, 4> DbgDefUsers;
1269 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
1270 for (auto &MO : MI.operands()) {
1271 if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1272 continue;
1273 for (auto &User : MRI.use_instructions(MO.getReg())) {
1274 if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))
1275 continue;
1276
1277 // If is in same block, will either sink or be use-before-def.
1278 if (User.getParent() == MI.getParent())
1279 continue;
1280
1281 assert(User.getDebugOperand(0).isReg() &&
1282 "DBG_VALUE user of vreg, but non reg operand?");
1283 DbgDefUsers.push_back(&User);
1284 }
1285 }
1286
1287 // Point the users of this copy that are no longer dominated, at the source
1288 // of the copy.
1289 for (auto *User : DbgDefUsers) {
1290 User->getDebugOperand(0).setReg(MI.getOperand(1).getReg());
1291 User->getDebugOperand(0).setSubReg(MI.getOperand(1).getSubReg());
1292 }
1293 }
1294
1295 //===----------------------------------------------------------------------===//
1296 // This pass is not intended to be a replacement or a complete alternative
1297 // for the pre-ra machine sink pass. It is only designed to sink COPY
1298 // instructions which should be handled after RA.
1299 //
1300 // This pass sinks COPY instructions into a successor block, if the COPY is not
1301 // used in the current block and the COPY is live-in to a single successor
1302 // (i.e., doesn't require the COPY to be duplicated). This avoids executing the
1303 // copy on paths where their results aren't needed. This also exposes
1304 // additional opportunites for dead copy elimination and shrink wrapping.
1305 //
1306 // These copies were either not handled by or are inserted after the MachineSink
1307 // pass. As an example of the former case, the MachineSink pass cannot sink
1308 // COPY instructions with allocatable source registers; for AArch64 these type
1309 // of copy instructions are frequently used to move function parameters (PhyReg)
1310 // into virtual registers in the entry block.
1311 //
1312 // For the machine IR below, this pass will sink %w19 in the entry into its
1313 // successor (%bb.1) because %w19 is only live-in in %bb.1.
1314 // %bb.0:
1315 // %wzr = SUBSWri %w1, 1
1316 // %w19 = COPY %w0
1317 // Bcc 11, %bb.2
1318 // %bb.1:
1319 // Live Ins: %w19
1320 // BL @fun
1321 // %w0 = ADDWrr %w0, %w19
1322 // RET %w0
1323 // %bb.2:
1324 // %w0 = COPY %wzr
1325 // RET %w0
1326 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
1327 // able to see %bb.0 as a candidate.
1328 //===----------------------------------------------------------------------===//
1329 namespace {
1330
1331 class PostRAMachineSinking : public MachineFunctionPass {
1332 public:
1333 bool runOnMachineFunction(MachineFunction &MF) override;
1334
1335 static char ID;
PostRAMachineSinking()1336 PostRAMachineSinking() : MachineFunctionPass(ID) {}
getPassName() const1337 StringRef getPassName() const override { return "PostRA Machine Sink"; }
1338
getAnalysisUsage(AnalysisUsage & AU) const1339 void getAnalysisUsage(AnalysisUsage &AU) const override {
1340 AU.setPreservesCFG();
1341 MachineFunctionPass::getAnalysisUsage(AU);
1342 }
1343
getRequiredProperties() const1344 MachineFunctionProperties getRequiredProperties() const override {
1345 return MachineFunctionProperties().set(
1346 MachineFunctionProperties::Property::NoVRegs);
1347 }
1348
1349 private:
1350 /// Track which register units have been modified and used.
1351 LiveRegUnits ModifiedRegUnits, UsedRegUnits;
1352
1353 /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
1354 /// entry in this map for each unit it touches.
1355 DenseMap<unsigned, TinyPtrVector<MachineInstr *>> SeenDbgInstrs;
1356
1357 /// Sink Copy instructions unused in the same block close to their uses in
1358 /// successors.
1359 bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
1360 const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
1361 };
1362 } // namespace
1363
1364 char PostRAMachineSinking::ID = 0;
1365 char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID;
1366
1367 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
1368 "PostRA Machine Sink", false, false)
1369
aliasWithRegsInLiveIn(MachineBasicBlock & MBB,unsigned Reg,const TargetRegisterInfo * TRI)1370 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
1371 const TargetRegisterInfo *TRI) {
1372 LiveRegUnits LiveInRegUnits(*TRI);
1373 LiveInRegUnits.addLiveIns(MBB);
1374 return !LiveInRegUnits.available(Reg);
1375 }
1376
1377 static MachineBasicBlock *
getSingleLiveInSuccBB(MachineBasicBlock & CurBB,const SmallPtrSetImpl<MachineBasicBlock * > & SinkableBBs,unsigned Reg,const TargetRegisterInfo * TRI)1378 getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1379 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1380 unsigned Reg, const TargetRegisterInfo *TRI) {
1381 // Try to find a single sinkable successor in which Reg is live-in.
1382 MachineBasicBlock *BB = nullptr;
1383 for (auto *SI : SinkableBBs) {
1384 if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
1385 // If BB is set here, Reg is live-in to at least two sinkable successors,
1386 // so quit.
1387 if (BB)
1388 return nullptr;
1389 BB = SI;
1390 }
1391 }
1392 // Reg is not live-in to any sinkable successors.
1393 if (!BB)
1394 return nullptr;
1395
1396 // Check if any register aliased with Reg is live-in in other successors.
1397 for (auto *SI : CurBB.successors()) {
1398 if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1399 return nullptr;
1400 }
1401 return BB;
1402 }
1403
1404 static MachineBasicBlock *
getSingleLiveInSuccBB(MachineBasicBlock & CurBB,const SmallPtrSetImpl<MachineBasicBlock * > & SinkableBBs,ArrayRef<unsigned> DefedRegsInCopy,const TargetRegisterInfo * TRI)1405 getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
1406 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1407 ArrayRef<unsigned> DefedRegsInCopy,
1408 const TargetRegisterInfo *TRI) {
1409 MachineBasicBlock *SingleBB = nullptr;
1410 for (auto DefReg : DefedRegsInCopy) {
1411 MachineBasicBlock *BB =
1412 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1413 if (!BB || (SingleBB && SingleBB != BB))
1414 return nullptr;
1415 SingleBB = BB;
1416 }
1417 return SingleBB;
1418 }
1419
clearKillFlags(MachineInstr * MI,MachineBasicBlock & CurBB,SmallVectorImpl<unsigned> & UsedOpsInCopy,LiveRegUnits & UsedRegUnits,const TargetRegisterInfo * TRI)1420 static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
1421 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1422 LiveRegUnits &UsedRegUnits,
1423 const TargetRegisterInfo *TRI) {
1424 for (auto U : UsedOpsInCopy) {
1425 MachineOperand &MO = MI->getOperand(U);
1426 Register SrcReg = MO.getReg();
1427 if (!UsedRegUnits.available(SrcReg)) {
1428 MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1429 for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1430 if (UI.killsRegister(SrcReg, TRI)) {
1431 UI.clearRegisterKills(SrcReg, TRI);
1432 MO.setIsKill(true);
1433 break;
1434 }
1435 }
1436 }
1437 }
1438 }
1439
updateLiveIn(MachineInstr * MI,MachineBasicBlock * SuccBB,SmallVectorImpl<unsigned> & UsedOpsInCopy,SmallVectorImpl<unsigned> & DefedRegsInCopy)1440 static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
1441 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1442 SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1443 MachineFunction &MF = *SuccBB->getParent();
1444 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1445 for (unsigned DefReg : DefedRegsInCopy)
1446 for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S)
1447 SuccBB->removeLiveIn(*S);
1448 for (auto U : UsedOpsInCopy) {
1449 Register SrcReg = MI->getOperand(U).getReg();
1450 LaneBitmask Mask;
1451 for (MCRegUnitMaskIterator S(SrcReg, TRI); S.isValid(); ++S) {
1452 Mask |= (*S).second;
1453 }
1454 SuccBB->addLiveIn(SrcReg, Mask.any() ? Mask : LaneBitmask::getAll());
1455 }
1456 SuccBB->sortUniqueLiveIns();
1457 }
1458
hasRegisterDependency(MachineInstr * MI,SmallVectorImpl<unsigned> & UsedOpsInCopy,SmallVectorImpl<unsigned> & DefedRegsInCopy,LiveRegUnits & ModifiedRegUnits,LiveRegUnits & UsedRegUnits)1459 static bool hasRegisterDependency(MachineInstr *MI,
1460 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1461 SmallVectorImpl<unsigned> &DefedRegsInCopy,
1462 LiveRegUnits &ModifiedRegUnits,
1463 LiveRegUnits &UsedRegUnits) {
1464 bool HasRegDependency = false;
1465 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1466 MachineOperand &MO = MI->getOperand(i);
1467 if (!MO.isReg())
1468 continue;
1469 Register Reg = MO.getReg();
1470 if (!Reg)
1471 continue;
1472 if (MO.isDef()) {
1473 if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1474 HasRegDependency = true;
1475 break;
1476 }
1477 DefedRegsInCopy.push_back(Reg);
1478
1479 // FIXME: instead of isUse(), readsReg() would be a better fix here,
1480 // For example, we can ignore modifications in reg with undef. However,
1481 // it's not perfectly clear if skipping the internal read is safe in all
1482 // other targets.
1483 } else if (MO.isUse()) {
1484 if (!ModifiedRegUnits.available(Reg)) {
1485 HasRegDependency = true;
1486 break;
1487 }
1488 UsedOpsInCopy.push_back(i);
1489 }
1490 }
1491 return HasRegDependency;
1492 }
1493
getRegUnits(MCRegister Reg,const TargetRegisterInfo * TRI)1494 static SmallSet<MCRegister, 4> getRegUnits(MCRegister Reg,
1495 const TargetRegisterInfo *TRI) {
1496 SmallSet<MCRegister, 4> RegUnits;
1497 for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI)
1498 RegUnits.insert(*RI);
1499 return RegUnits;
1500 }
1501
tryToSinkCopy(MachineBasicBlock & CurBB,MachineFunction & MF,const TargetRegisterInfo * TRI,const TargetInstrInfo * TII)1502 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1503 MachineFunction &MF,
1504 const TargetRegisterInfo *TRI,
1505 const TargetInstrInfo *TII) {
1506 SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
1507 // FIXME: For now, we sink only to a successor which has a single predecessor
1508 // so that we can directly sink COPY instructions to the successor without
1509 // adding any new block or branch instruction.
1510 for (MachineBasicBlock *SI : CurBB.successors())
1511 if (!SI->livein_empty() && SI->pred_size() == 1)
1512 SinkableBBs.insert(SI);
1513
1514 if (SinkableBBs.empty())
1515 return false;
1516
1517 bool Changed = false;
1518
1519 // Track which registers have been modified and used between the end of the
1520 // block and the current instruction.
1521 ModifiedRegUnits.clear();
1522 UsedRegUnits.clear();
1523 SeenDbgInstrs.clear();
1524
1525 for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
1526 MachineInstr *MI = &*I;
1527 ++I;
1528
1529 // Track the operand index for use in Copy.
1530 SmallVector<unsigned, 2> UsedOpsInCopy;
1531 // Track the register number defed in Copy.
1532 SmallVector<unsigned, 2> DefedRegsInCopy;
1533
1534 // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
1535 // for DBG_VALUEs later, record them when they're encountered.
1536 if (MI->isDebugValue()) {
1537 auto &MO = MI->getDebugOperand(0);
1538 if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) {
1539 // Bail if we can already tell the sink would be rejected, rather
1540 // than needlessly accumulating lots of DBG_VALUEs.
1541 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1542 ModifiedRegUnits, UsedRegUnits))
1543 continue;
1544
1545 // Record debug use of each reg unit.
1546 SmallSet<MCRegister, 4> Units = getRegUnits(MO.getReg(), TRI);
1547 for (MCRegister Reg : Units)
1548 SeenDbgInstrs[Reg].push_back(MI);
1549 }
1550 continue;
1551 }
1552
1553 if (MI->isDebugInstr())
1554 continue;
1555
1556 // Do not move any instruction across function call.
1557 if (MI->isCall())
1558 return false;
1559
1560 if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
1561 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1562 TRI);
1563 continue;
1564 }
1565
1566 // Don't sink the COPY if it would violate a register dependency.
1567 if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1568 ModifiedRegUnits, UsedRegUnits)) {
1569 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1570 TRI);
1571 continue;
1572 }
1573 assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1574 "Unexpect SrcReg or DefReg");
1575 MachineBasicBlock *SuccBB =
1576 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
1577 // Don't sink if we cannot find a single sinkable successor in which Reg
1578 // is live-in.
1579 if (!SuccBB) {
1580 LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1581 TRI);
1582 continue;
1583 }
1584 assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1585 "Unexpected predecessor");
1586
1587 // Collect DBG_VALUEs that must sink with this copy. We've previously
1588 // recorded which reg units that DBG_VALUEs read, if this instruction
1589 // writes any of those units then the corresponding DBG_VALUEs must sink.
1590 SetVector<MachineInstr *> DbgValsToSinkSet;
1591 for (auto &MO : MI->operands()) {
1592 if (!MO.isReg() || !MO.isDef())
1593 continue;
1594
1595 SmallSet<MCRegister, 4> Units = getRegUnits(MO.getReg(), TRI);
1596 for (MCRegister Reg : Units)
1597 for (auto *MI : SeenDbgInstrs.lookup(Reg))
1598 DbgValsToSinkSet.insert(MI);
1599 }
1600 SmallVector<MachineInstr *, 4> DbgValsToSink(DbgValsToSinkSet.begin(),
1601 DbgValsToSinkSet.end());
1602
1603 // Clear the kill flag if SrcReg is killed between MI and the end of the
1604 // block.
1605 clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
1606 MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
1607 performSink(*MI, *SuccBB, InsertPos, DbgValsToSink);
1608 updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
1609
1610 Changed = true;
1611 ++NumPostRACopySink;
1612 }
1613 return Changed;
1614 }
1615
runOnMachineFunction(MachineFunction & MF)1616 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1617 if (skipFunction(MF.getFunction()))
1618 return false;
1619
1620 bool Changed = false;
1621 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1622 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
1623
1624 ModifiedRegUnits.init(*TRI);
1625 UsedRegUnits.init(*TRI);
1626 for (auto &BB : MF)
1627 Changed |= tryToSinkCopy(BB, MF, TRI, TII);
1628
1629 return Changed;
1630 }
1631