LLVM  15.0.0git
MachineSink.cpp
Go to the documentation of this file.
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"
20 #include "llvm/ADT/MapVector.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Analysis/CFG.h"
45 #include "llvm/IR/BasicBlock.h"
47 #include "llvm/IR/LLVMContext.h"
48 #include "llvm/InitializePasses.h"
49 #include "llvm/MC/MCRegisterInfo.h"
50 #include "llvm/Pass.h"
53 #include "llvm/Support/Debug.h"
55 #include <algorithm>
56 #include <cassert>
57 #include <cstdint>
58 #include <map>
59 #include <utility>
60 #include <vector>
61 
62 using namespace llvm;
63 
64 #define DEBUG_TYPE "machine-sink"
65 
66 static cl::opt<bool>
67 SplitEdges("machine-sink-split",
68  cl::desc("Split critical edges during machine sinking"),
69  cl::init(true), cl::Hidden);
70 
71 static cl::opt<bool>
72 UseBlockFreqInfo("machine-sink-bfi",
73  cl::desc("Use block frequency info to find successors to sink"),
74  cl::init(true), cl::Hidden);
75 
77  "machine-sink-split-probability-threshold",
78  cl::desc(
79  "Percentage threshold for splitting single-instruction critical edge. "
80  "If the branch threshold is higher than this threshold, we allow "
81  "speculative execution of up to 1 instruction to avoid branching to "
82  "splitted critical edge"),
83  cl::init(40), cl::Hidden);
84 
86  "machine-sink-load-instrs-threshold",
87  cl::desc("Do not try to find alias store for a load if there is a in-path "
88  "block whose instruction number is higher than this threshold."),
89  cl::init(2000), cl::Hidden);
90 
92  "machine-sink-load-blocks-threshold",
93  cl::desc("Do not try to find alias store for a load if the block number in "
94  "the straight line is higher than this threshold."),
95  cl::init(20), cl::Hidden);
96 
97 static cl::opt<bool>
98 SinkInstsIntoLoop("sink-insts-to-avoid-spills",
99  cl::desc("Sink instructions into loops to avoid "
100  "register spills"),
101  cl::init(false), cl::Hidden);
102 
104  "machine-sink-loop-limit",
105  cl::desc("The maximum number of instructions considered for loop sinking."),
106  cl::init(50), cl::Hidden);
107 
108 STATISTIC(NumSunk, "Number of machine instructions sunk");
109 STATISTIC(NumLoopSunk, "Number of machine instructions sunk into a loop");
110 STATISTIC(NumSplit, "Number of critical edges split");
111 STATISTIC(NumCoalesces, "Number of copies coalesced");
112 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
113 
114 namespace {
115 
116  class MachineSinking : public MachineFunctionPass {
117  const TargetInstrInfo *TII;
118  const TargetRegisterInfo *TRI;
119  MachineRegisterInfo *MRI; // Machine register information
120  MachineDominatorTree *DT; // Machine dominator tree
121  MachinePostDominatorTree *PDT; // Machine post dominator tree
122  MachineLoopInfo *LI;
124  const MachineBranchProbabilityInfo *MBPI;
125  AliasAnalysis *AA;
126  RegisterClassInfo RegClassInfo;
127 
128  // Remember which edges have been considered for breaking.
130  CEBCandidates;
131  // Remember which edges we are about to split.
132  // This is different from CEBCandidates since those edges
133  // will be split.
135 
136  DenseSet<Register> RegsToClearKillFlags;
137 
138  using AllSuccsCache =
139  std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
140 
141  /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
142  /// post-dominated by another DBG_VALUE of the same variable location.
143  /// This is necessary to detect sequences such as:
144  /// %0 = someinst
145  /// DBG_VALUE %0, !123, !DIExpression()
146  /// %1 = anotherinst
147  /// DBG_VALUE %1, !123, !DIExpression()
148  /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
149  /// would re-order assignments.
150  using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
151 
152  /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
153  /// debug instructions to sink.
155 
156  /// Record of debug variables that have had their locations set in the
157  /// current block.
158  DenseSet<DebugVariable> SeenDbgVars;
159 
160  std::map<std::pair<MachineBasicBlock *, MachineBasicBlock *>, bool>
161  HasStoreCache;
162  std::map<std::pair<MachineBasicBlock *, MachineBasicBlock *>,
163  std::vector<MachineInstr *>>
164  StoreInstrCache;
165 
166  /// Cached BB's register pressure.
167  std::map<MachineBasicBlock *, std::vector<unsigned>> CachedRegisterPressure;
168 
169  public:
170  static char ID; // Pass identification
171 
172  MachineSinking() : MachineFunctionPass(ID) {
174  }
175 
176  bool runOnMachineFunction(MachineFunction &MF) override;
177 
178  void getAnalysisUsage(AnalysisUsage &AU) const override {
186  if (UseBlockFreqInfo)
188  }
189 
190  void releaseMemory() override {
191  CEBCandidates.clear();
192  }
193 
194  private:
196  void ProcessDbgInst(MachineInstr &MI);
197  bool isWorthBreakingCriticalEdge(MachineInstr &MI,
199  MachineBasicBlock *To);
200 
201  bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
202  MachineInstr &MI);
203 
204  /// Postpone the splitting of the given critical
205  /// edge (\p From, \p To).
206  ///
207  /// We do not split the edges on the fly. Indeed, this invalidates
208  /// the dominance information and thus triggers a lot of updates
209  /// of that information underneath.
210  /// Instead, we postpone all the splits after each iteration of
211  /// the main loop. That way, the information is at least valid
212  /// for the lifetime of an iteration.
213  ///
214  /// \return True if the edge is marked as toSplit, false otherwise.
215  /// False can be returned if, for instance, this is not profitable.
216  bool PostponeSplitCriticalEdge(MachineInstr &MI,
218  MachineBasicBlock *To,
219  bool BreakPHIEdge);
220  bool SinkInstruction(MachineInstr &MI, bool &SawStore,
221  AllSuccsCache &AllSuccessors);
222 
223  /// If we sink a COPY inst, some debug users of it's destination may no
224  /// longer be dominated by the COPY, and will eventually be dropped.
225  /// This is easily rectified by forwarding the non-dominated debug uses
226  /// to the copy source.
227  void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
228  MachineBasicBlock *TargetBlock);
229  bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
230  MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
231  bool &LocalUse) const;
233  bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
234 
235  void FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
236  SmallVectorImpl<MachineInstr *> &Candidates);
237  bool SinkIntoLoop(MachineLoop *L, MachineInstr &I);
238 
239  bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
241  MachineBasicBlock *SuccToSinkTo,
242  AllSuccsCache &AllSuccessors);
243 
244  bool PerformTrivialForwardCoalescing(MachineInstr &MI,
246 
248  GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
249  AllSuccsCache &AllSuccessors) const;
250 
251  std::vector<unsigned> &getBBRegisterPressure(MachineBasicBlock &MBB);
252  };
253 
254 } // end anonymous namespace
255 
256 char MachineSinking::ID = 0;
257 
259 
260 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
261  "Machine code sinking", false, false)
268 
269 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
271  if (!MI.isCopy())
272  return false;
273 
274  Register SrcReg = MI.getOperand(1).getReg();
275  Register DstReg = MI.getOperand(0).getReg();
276  if (!Register::isVirtualRegister(SrcReg) ||
277  !Register::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg))
278  return false;
279 
280  const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
281  const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
282  if (SRC != DRC)
283  return false;
284 
285  MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
286  if (DefMI->isCopyLike())
287  return false;
288  LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
289  LLVM_DEBUG(dbgs() << "*** to: " << MI);
290  MRI->replaceRegWith(DstReg, SrcReg);
291  MI.eraseFromParent();
292 
293  // Conservatively, clear any kill flags, since it's possible that they are no
294  // longer correct.
295  MRI->clearKillFlags(SrcReg);
296 
297  ++NumCoalesces;
298  return true;
299 }
300 
301 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
302 /// occur in blocks dominated by the specified block. If any use is in the
303 /// definition block, then return false since it is never legal to move def
304 /// after uses.
305 bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
307  MachineBasicBlock *DefMBB,
308  bool &BreakPHIEdge,
309  bool &LocalUse) const {
310  assert(Register::isVirtualRegister(Reg) && "Only makes sense for vregs");
311 
312  // Ignore debug uses because debug info doesn't affect the code.
313  if (MRI->use_nodbg_empty(Reg))
314  return true;
315 
316  // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
317  // into and they are all PHI nodes. In this case, machine-sink must break
318  // the critical edge first. e.g.
319  //
320  // %bb.1:
321  // Predecessors according to CFG: %bb.0
322  // ...
323  // %def = DEC64_32r %x, implicit-def dead %eflags
324  // ...
325  // JE_4 <%bb.37>, implicit %eflags
326  // Successors according to CFG: %bb.37 %bb.2
327  //
328  // %bb.2:
329  // %p = PHI %y, %bb.0, %def, %bb.1
331  MachineInstr *UseInst = MO.getParent();
332  unsigned OpNo = UseInst->getOperandNo(&MO);
333  MachineBasicBlock *UseBlock = UseInst->getParent();
334  return UseBlock == MBB && UseInst->isPHI() &&
335  UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
336  })) {
337  BreakPHIEdge = true;
338  return true;
339  }
340 
341  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
342  // Determine the block of the use.
343  MachineInstr *UseInst = MO.getParent();
344  unsigned OpNo = &MO - &UseInst->getOperand(0);
345  MachineBasicBlock *UseBlock = UseInst->getParent();
346  if (UseInst->isPHI()) {
347  // PHI nodes use the operand in the predecessor block, not the block with
348  // the PHI.
349  UseBlock = UseInst->getOperand(OpNo+1).getMBB();
350  } else if (UseBlock == DefMBB) {
351  LocalUse = true;
352  return false;
353  }
354 
355  // Check that it dominates.
356  if (!DT->dominates(MBB, UseBlock))
357  return false;
358  }
359 
360  return true;
361 }
362 
363 /// Return true if this machine instruction loads from global offset table or
364 /// constant pool.
366  assert(MI.mayLoad() && "Expected MI that loads!");
367 
368  // If we lost memory operands, conservatively assume that the instruction
369  // reads from everything..
370  if (MI.memoperands_empty())
371  return true;
372 
373  for (MachineMemOperand *MemOp : MI.memoperands())
374  if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
375  if (PSV->isGOT() || PSV->isConstantPool())
376  return true;
377 
378  return false;
379 }
380 
381 void MachineSinking::FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
382  SmallVectorImpl<MachineInstr *> &Candidates) {
383  for (auto &MI : *BB) {
384  LLVM_DEBUG(dbgs() << "LoopSink: Analysing candidate: " << MI);
385  if (!TII->shouldSink(MI)) {
386  LLVM_DEBUG(dbgs() << "LoopSink: Instruction not a candidate for this "
387  "target\n");
388  continue;
389  }
390  if (!L->isLoopInvariant(MI)) {
391  LLVM_DEBUG(dbgs() << "LoopSink: Instruction is not loop invariant\n");
392  continue;
393  }
394  bool DontMoveAcrossStore = true;
395  if (!MI.isSafeToMove(AA, DontMoveAcrossStore)) {
396  LLVM_DEBUG(dbgs() << "LoopSink: Instruction not safe to move.\n");
397  continue;
398  }
399  if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
400  LLVM_DEBUG(dbgs() << "LoopSink: Dont sink GOT or constant pool loads\n");
401  continue;
402  }
403  if (MI.isConvergent())
404  continue;
405 
406  const MachineOperand &MO = MI.getOperand(0);
407  if (!MO.isReg() || !MO.getReg() || !MO.isDef())
408  continue;
409  if (!MRI->hasOneDef(MO.getReg()))
410  continue;
411 
412  LLVM_DEBUG(dbgs() << "LoopSink: Instruction added as candidate.\n");
413  Candidates.push_back(&MI);
414  }
415 }
416 
417 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
418  if (skipFunction(MF.getFunction()))
419  return false;
420 
421  LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
422 
423  TII = MF.getSubtarget().getInstrInfo();
425  MRI = &MF.getRegInfo();
426  DT = &getAnalysis<MachineDominatorTree>();
427  PDT = &getAnalysis<MachinePostDominatorTree>();
428  LI = &getAnalysis<MachineLoopInfo>();
429  MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
430  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
431  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
432  RegClassInfo.runOnMachineFunction(MF);
433 
434  // MachineSink currently uses MachineLoopInfo, which only recognizes natural
435  // loops. As such, we could sink instructions into irreducible cycles, which
436  // would be non-profitable.
437  // WARNING: The current implementation of hasStoreBetween() is incorrect for
438  // sinking into irreducible cycles (PR53990), this bailout is currently
439  // necessary for correctness, not just profitability.
441  if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *LI))
442  return false;
443 
444  bool EverMadeChange = false;
445 
446  while (true) {
447  bool MadeChange = false;
448 
449  // Process all basic blocks.
450  CEBCandidates.clear();
451  ToSplit.clear();
452  for (auto &MBB: MF)
453  MadeChange |= ProcessBlock(MBB);
454 
455  // If we have anything we marked as toSplit, split it now.
456  for (auto &Pair : ToSplit) {
457  auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
458  if (NewSucc != nullptr) {
459  LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
460  << printMBBReference(*Pair.first) << " -- "
461  << printMBBReference(*NewSucc) << " -- "
462  << printMBBReference(*Pair.second) << '\n');
463  if (MBFI)
464  MBFI->onEdgeSplit(*Pair.first, *NewSucc, *MBPI);
465 
466  MadeChange = true;
467  ++NumSplit;
468  } else
469  LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
470  }
471  // If this iteration over the code changed anything, keep iterating.
472  if (!MadeChange) break;
473  EverMadeChange = true;
474  }
475 
476  if (SinkInstsIntoLoop) {
478  for (auto *L : Loops) {
479  MachineBasicBlock *Preheader = LI->findLoopPreheader(L);
480  if (!Preheader) {
481  LLVM_DEBUG(dbgs() << "LoopSink: Can't find preheader\n");
482  continue;
483  }
485  FindLoopSinkCandidates(L, Preheader, Candidates);
486 
487  // Walk the candidates in reverse order so that we start with the use
488  // of a def-use chain, if there is any.
489  // TODO: Sort the candidates using a cost-model.
490  unsigned i = 0;
491  for (MachineInstr *I : llvm::reverse(Candidates)) {
492  if (i++ == SinkIntoLoopLimit) {
493  LLVM_DEBUG(dbgs() << "LoopSink: Limit reached of instructions to "
494  "be analysed.");
495  break;
496  }
497 
498  if (!SinkIntoLoop(L, *I))
499  break;
500  EverMadeChange = true;
501  ++NumLoopSunk;
502  }
503  }
504  }
505 
506  HasStoreCache.clear();
507  StoreInstrCache.clear();
508 
509  // Now clear any kill flags for recorded registers.
510  for (auto I : RegsToClearKillFlags)
511  MRI->clearKillFlags(I);
512  RegsToClearKillFlags.clear();
513 
514  return EverMadeChange;
515 }
516 
518  // Can't sink anything out of a block that has less than two successors.
519  if (MBB.succ_size() <= 1 || MBB.empty()) return false;
520 
521  // Don't bother sinking code out of unreachable blocks. In addition to being
522  // unprofitable, it can also lead to infinite looping, because in an
523  // unreachable loop there may be nowhere to stop.
524  if (!DT->isReachableFromEntry(&MBB)) return false;
525 
526  bool MadeChange = false;
527 
528  // Cache all successors, sorted by frequency info and loop depth.
529  AllSuccsCache AllSuccessors;
530 
531  // Walk the basic block bottom-up. Remember if we saw a store.
533  --I;
534  bool ProcessedBegin, SawStore = false;
535  do {
536  MachineInstr &MI = *I; // The instruction to sink.
537 
538  // Predecrement I (if it's not begin) so that it isn't invalidated by
539  // sinking.
540  ProcessedBegin = I == MBB.begin();
541  if (!ProcessedBegin)
542  --I;
543 
544  if (MI.isDebugOrPseudoInstr()) {
545  if (MI.isDebugValue())
546  ProcessDbgInst(MI);
547  continue;
548  }
549 
550  bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
551  if (Joined) {
552  MadeChange = true;
553  continue;
554  }
555 
556  if (SinkInstruction(MI, SawStore, AllSuccessors)) {
557  ++NumSunk;
558  MadeChange = true;
559  }
560 
561  // If we just processed the first instruction in the block, we're done.
562  } while (!ProcessedBegin);
563 
564  SeenDbgUsers.clear();
565  SeenDbgVars.clear();
566  // recalculate the bb register pressure after sinking one BB.
567  CachedRegisterPressure.clear();
568 
569  return MadeChange;
570 }
571 
572 void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
573  // When we see DBG_VALUEs for registers, record any vreg it reads, so that
574  // we know what to sink if the vreg def sinks.
575  assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
576 
577  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
578  MI.getDebugLoc()->getInlinedAt());
579  bool SeenBefore = SeenDbgVars.contains(Var);
580 
581  for (MachineOperand &MO : MI.debug_operands()) {
582  if (MO.isReg() && MO.getReg().isVirtual())
583  SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));
584  }
585 
586  // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
587  SeenDbgVars.insert(Var);
588 }
589 
590 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
592  MachineBasicBlock *To) {
593  // FIXME: Need much better heuristics.
594 
595  // If the pass has already considered breaking this edge (during this pass
596  // through the function), then let's go ahead and break it. This means
597  // sinking multiple "cheap" instructions into the same block.
598  if (!CEBCandidates.insert(std::make_pair(From, To)).second)
599  return true;
600 
601  if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
602  return true;
603 
604  if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
606  return true;
607 
608  // MI is cheap, we probably don't want to break the critical edge for it.
609  // However, if this would allow some definitions of its source operands
610  // to be sunk then it's probably worth it.
611  for (const MachineOperand &MO : MI.operands()) {
612  if (!MO.isReg() || !MO.isUse())
613  continue;
614  Register Reg = MO.getReg();
615  if (Reg == 0)
616  continue;
617 
618  // We don't move live definitions of physical registers,
619  // so sinking their uses won't enable any opportunities.
621  continue;
622 
623  // If this instruction is the only user of a virtual register,
624  // check if breaking the edge will enable sinking
625  // both this instruction and the defining instruction.
626  if (MRI->hasOneNonDBGUse(Reg)) {
627  // If the definition resides in same MBB,
628  // claim it's likely we can sink these together.
629  // If definition resides elsewhere, we aren't
630  // blocking it from being sunk so don't break the edge.
632  if (DefMI->getParent() == MI.getParent())
633  return true;
634  }
635  }
636 
637  return false;
638 }
639 
640 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
641  MachineBasicBlock *FromBB,
642  MachineBasicBlock *ToBB,
643  bool BreakPHIEdge) {
644  if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
645  return false;
646 
647  // Avoid breaking back edge. From == To means backedge for single BB loop.
648  if (!SplitEdges || FromBB == ToBB)
649  return false;
650 
651  // Check for backedges of more "complex" loops.
652  if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
653  LI->isLoopHeader(ToBB))
654  return false;
655 
656  // It's not always legal to break critical edges and sink the computation
657  // to the edge.
658  //
659  // %bb.1:
660  // v1024
661  // Beq %bb.3
662  // <fallthrough>
663  // %bb.2:
664  // ... no uses of v1024
665  // <fallthrough>
666  // %bb.3:
667  // ...
668  // = v1024
669  //
670  // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
671  //
672  // %bb.1:
673  // ...
674  // Bne %bb.2
675  // %bb.4:
676  // v1024 =
677  // B %bb.3
678  // %bb.2:
679  // ... no uses of v1024
680  // <fallthrough>
681  // %bb.3:
682  // ...
683  // = v1024
684  //
685  // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
686  // flow. We need to ensure the new basic block where the computation is
687  // sunk to dominates all the uses.
688  // It's only legal to break critical edge and sink the computation to the
689  // new block if all the predecessors of "To", except for "From", are
690  // not dominated by "From". Given SSA property, this means these
691  // predecessors are dominated by "To".
692  //
693  // There is no need to do this check if all the uses are PHI nodes. PHI
694  // sources are only defined on the specific predecessor edges.
695  if (!BreakPHIEdge) {
696  for (MachineBasicBlock *Pred : ToBB->predecessors())
697  if (Pred != FromBB && !DT->dominates(ToBB, Pred))
698  return false;
699  }
700 
701  ToSplit.insert(std::make_pair(FromBB, ToBB));
702 
703  return true;
704 }
705 
706 std::vector<unsigned> &
707 MachineSinking::getBBRegisterPressure(MachineBasicBlock &MBB) {
708  // Currently to save compiling time, MBB's register pressure will not change
709  // in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's
710  // register pressure is changed after sinking any instructions into it.
711  // FIXME: need a accurate and cheap register pressure estiminate model here.
712  auto RP = CachedRegisterPressure.find(&MBB);
713  if (RP != CachedRegisterPressure.end())
714  return RP->second;
715 
716  RegionPressure Pressure;
717  RegPressureTracker RPTracker(Pressure);
718 
719  // Initialize the register pressure tracker.
720  RPTracker.init(MBB.getParent(), &RegClassInfo, nullptr, &MBB, MBB.end(),
721  /*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);
722 
724  MIE = MBB.instr_begin();
725  MII != MIE; --MII) {
726  MachineInstr &MI = *std::prev(MII);
727  if (MI.isDebugInstr() || MI.isPseudoProbe())
728  continue;
729  RegisterOperands RegOpers;
730  RegOpers.collect(MI, *TRI, *MRI, false, false);
731  RPTracker.recedeSkipDebugValues();
732  assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");
733  RPTracker.recede(RegOpers);
734  }
735 
736  RPTracker.closeRegion();
737  auto It = CachedRegisterPressure.insert(
738  std::make_pair(&MBB, RPTracker.getPressure().MaxSetPressure));
739  return It.first->second;
740 }
741 
742 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
743 bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
745  MachineBasicBlock *SuccToSinkTo,
746  AllSuccsCache &AllSuccessors) {
747  assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
748 
749  if (MBB == SuccToSinkTo)
750  return false;
751 
752  // It is profitable if SuccToSinkTo does not post dominate current block.
753  if (!PDT->dominates(SuccToSinkTo, MBB))
754  return true;
755 
756  // It is profitable to sink an instruction from a deeper loop to a shallower
757  // loop, even if the latter post-dominates the former (PR21115).
758  if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
759  return true;
760 
761  // Check if only use in post dominated block is PHI instruction.
762  bool NonPHIUse = false;
763  for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
764  MachineBasicBlock *UseBlock = UseInst.getParent();
765  if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
766  NonPHIUse = true;
767  }
768  if (!NonPHIUse)
769  return true;
770 
771  // If SuccToSinkTo post dominates then also it may be profitable if MI
772  // can further profitably sinked into another block in next round.
773  bool BreakPHIEdge = false;
774  // FIXME - If finding successor is compile time expensive then cache results.
775  if (MachineBasicBlock *MBB2 =
776  FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
777  return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
778 
779  MachineLoop *ML = LI->getLoopFor(MBB);
780 
781  // If the instruction is not inside a loop, it is not profitable to sink MI to
782  // a post dominate block SuccToSinkTo.
783  if (!ML)
784  return false;
785 
786  auto isRegisterPressureSetExceedLimit = [&](const TargetRegisterClass *RC) {
787  unsigned Weight = TRI->getRegClassWeight(RC).RegWeight;
788  const int *PS = TRI->getRegClassPressureSets(RC);
789  // Get register pressure for block SuccToSinkTo.
790  std::vector<unsigned> BBRegisterPressure =
791  getBBRegisterPressure(*SuccToSinkTo);
792  for (; *PS != -1; PS++)
793  // check if any register pressure set exceeds limit in block SuccToSinkTo
794  // after sinking.
795  if (Weight + BBRegisterPressure[*PS] >=
797  return true;
798  return false;
799  };
800 
801  // If this instruction is inside a loop and sinking this instruction can make
802  // more registers live range shorten, it is still prifitable.
803  for (const MachineOperand &MO : MI.operands()) {
804  // Ignore non-register operands.
805  if (!MO.isReg())
806  continue;
807  Register Reg = MO.getReg();
808  if (Reg == 0)
809  continue;
810 
812  if (MO.isUse() &&
813  (MRI->isConstantPhysReg(Reg) || TII->isIgnorableUse(MO)))
814  continue;
815 
816  // Don't handle non-constant and non-ignorable physical register.
817  return false;
818  }
819 
820  // Users for the defs are all dominated by SuccToSinkTo.
821  if (MO.isDef()) {
822  // This def register's live range is shortened after sinking.
823  bool LocalUse = false;
824  if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
825  LocalUse))
826  return false;
827  } else {
829  // DefMI is defined outside of loop. There should be no live range
830  // impact for this operand. Defination outside of loop means:
831  // 1: defination is outside of loop.
832  // 2: defination is in this loop, but it is a PHI in the loop header.
833  if (LI->getLoopFor(DefMI->getParent()) != ML ||
834  (DefMI->isPHI() && LI->isLoopHeader(DefMI->getParent())))
835  continue;
836  // The DefMI is defined inside the loop.
837  // If sinking this operand makes some register pressure set exceed limit,
838  // it is not profitable.
839  if (isRegisterPressureSetExceedLimit(MRI->getRegClass(Reg))) {
840  LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
841  return false;
842  }
843  }
844  }
845 
846  // If MI is in loop and all its operands are alive across the whole loop or if
847  // no operand sinking make register pressure set exceed limit, it is
848  // profitable to sink MI.
849  return true;
850 }
851 
852 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
853 /// computing it if it was not already cached.
855 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
856  AllSuccsCache &AllSuccessors) const {
857  // Do we have the sorted successors in cache ?
858  auto Succs = AllSuccessors.find(MBB);
859  if (Succs != AllSuccessors.end())
860  return Succs->second;
861 
863 
864  // Handle cases where sinking can happen but where the sink point isn't a
865  // successor. For example:
866  //
867  // x = computation
868  // if () {} else {}
869  // use x
870  //
871  for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {
872  // DomTree children of MBB that have MBB as immediate dominator are added.
873  if (DTChild->getIDom()->getBlock() == MI.getParent() &&
874  // Skip MBBs already added to the AllSuccs vector above.
875  !MBB->isSuccessor(DTChild->getBlock()))
876  AllSuccs.push_back(DTChild->getBlock());
877  }
878 
879  // Sort Successors according to their loop depth or block frequency info.
881  AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
882  uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
883  uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
884  bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
885  return HasBlockFreq ? LHSFreq < RHSFreq
886  : LI->getLoopDepth(L) < LI->getLoopDepth(R);
887  });
888 
889  auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
890 
891  return it.first->second;
892 }
893 
894 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
896 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
897  bool &BreakPHIEdge,
898  AllSuccsCache &AllSuccessors) {
899  assert (MBB && "Invalid MachineBasicBlock!");
900 
901  // Loop over all the operands of the specified instruction. If there is
902  // anything we can't handle, bail out.
903 
904  // SuccToSinkTo - This is the successor to sink this instruction to, once we
905  // decide.
906  MachineBasicBlock *SuccToSinkTo = nullptr;
907  for (const MachineOperand &MO : MI.operands()) {
908  if (!MO.isReg()) continue; // Ignore non-register operands.
909 
910  Register Reg = MO.getReg();
911  if (Reg == 0) continue;
912 
914  if (MO.isUse()) {
915  // If the physreg has no defs anywhere, it's just an ambient register
916  // and we can freely move its uses. Alternatively, if it's allocatable,
917  // it could get allocated to something with a def during allocation.
918  if (!MRI->isConstantPhysReg(Reg) && !TII->isIgnorableUse(MO))
919  return nullptr;
920  } else if (!MO.isDead()) {
921  // A def that isn't dead. We can't move it.
922  return nullptr;
923  }
924  } else {
925  // Virtual register uses are always safe to sink.
926  if (MO.isUse()) continue;
927 
928  // If it's not safe to move defs of the register class, then abort.
929  if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
930  return nullptr;
931 
932  // Virtual register defs can only be sunk if all their uses are in blocks
933  // dominated by one of the successors.
934  if (SuccToSinkTo) {
935  // If a previous operand picked a block to sink to, then this operand
936  // must be sinkable to the same block.
937  bool LocalUse = false;
938  if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
939  BreakPHIEdge, LocalUse))
940  return nullptr;
941 
942  continue;
943  }
944 
945  // Otherwise, we should look at all the successors and decide which one
946  // we should sink to. If we have reliable block frequency information
947  // (frequency != 0) available, give successors with smaller frequencies
948  // higher priority, otherwise prioritize smaller loop depths.
949  for (MachineBasicBlock *SuccBlock :
950  GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
951  bool LocalUse = false;
952  if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
953  BreakPHIEdge, LocalUse)) {
954  SuccToSinkTo = SuccBlock;
955  break;
956  }
957  if (LocalUse)
958  // Def is used locally, it's never safe to move this def.
959  return nullptr;
960  }
961 
962  // If we couldn't find a block to sink to, ignore this instruction.
963  if (!SuccToSinkTo)
964  return nullptr;
965  if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
966  return nullptr;
967  }
968  }
969 
970  // It is not possible to sink an instruction into its own block. This can
971  // happen with loops.
972  if (MBB == SuccToSinkTo)
973  return nullptr;
974 
975  // It's not safe to sink instructions to EH landing pad. Control flow into
976  // landing pad is implicitly defined.
977  if (SuccToSinkTo && SuccToSinkTo->isEHPad())
978  return nullptr;
979 
980  // It ought to be okay to sink instructions into an INLINEASM_BR target, but
981  // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
982  // the source block (which this code does not yet do). So for now, forbid
983  // doing so.
984  if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
985  return nullptr;
986 
987  return SuccToSinkTo;
988 }
989 
990 /// Return true if MI is likely to be usable as a memory operation by the
991 /// implicit null check optimization.
992 ///
993 /// This is a "best effort" heuristic, and should not be relied upon for
994 /// correctness. This returning true does not guarantee that the implicit null
995 /// check optimization is legal over MI, and this returning false does not
996 /// guarantee MI cannot possibly be used to do a null check.
998  const TargetInstrInfo *TII,
999  const TargetRegisterInfo *TRI) {
1000  using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
1001 
1002  auto *MBB = MI.getParent();
1003  if (MBB->pred_size() != 1)
1004  return false;
1005 
1006  auto *PredMBB = *MBB->pred_begin();
1007  auto *PredBB = PredMBB->getBasicBlock();
1008 
1009  // Frontends that don't use implicit null checks have no reason to emit
1010  // branches with make.implicit metadata, and this function should always
1011  // return false for them.
1012  if (!PredBB ||
1013  !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
1014  return false;
1015 
1016  const MachineOperand *BaseOp;
1017  int64_t Offset;
1018  bool OffsetIsScalable;
1019  if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
1020  return false;
1021 
1022  if (!BaseOp->isReg())
1023  return false;
1024 
1025  if (!(MI.mayLoad() && !MI.isPredicable()))
1026  return false;
1027 
1028  MachineBranchPredicate MBP;
1029  if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
1030  return false;
1031 
1032  return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1033  (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1034  MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1035  MBP.LHS.getReg() == BaseOp->getReg();
1036 }
1037 
1038 /// If the sunk instruction is a copy, try to forward the copy instead of
1039 /// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
1040 /// there's any subregister weirdness involved. Returns true if copy
1041 /// propagation occurred.
1042 static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI,
1043  Register Reg) {
1044  const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
1045  const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
1046 
1047  // Copy DBG_VALUE operand and set the original to undef. We then check to
1048  // see whether this is something that can be copy-forwarded. If it isn't,
1049  // continue around the loop.
1050 
1051  const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
1052  auto CopyOperands = TII.isCopyInstr(SinkInst);
1053  if (!CopyOperands)
1054  return false;
1055  SrcMO = CopyOperands->Source;
1056  DstMO = CopyOperands->Destination;
1057 
1058  // Check validity of forwarding this copy.
1059  bool PostRA = MRI.getNumVirtRegs() == 0;
1060 
1061  // Trying to forward between physical and virtual registers is too hard.
1062  if (Reg.isVirtual() != SrcMO->getReg().isVirtual())
1063  return false;
1064 
1065  // Only try virtual register copy-forwarding before regalloc, and physical
1066  // register copy-forwarding after regalloc.
1067  bool arePhysRegs = !Reg.isVirtual();
1068  if (arePhysRegs != PostRA)
1069  return false;
1070 
1071  // Pre-regalloc, only forward if all subregisters agree (or there are no
1072  // subregs at all). More analysis might recover some forwardable copies.
1073  if (!PostRA)
1074  for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg))
1075  if (DbgMO.getSubReg() != SrcMO->getSubReg() ||
1076  DbgMO.getSubReg() != DstMO->getSubReg())
1077  return false;
1078 
1079  // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
1080  // of this copy. Only forward the copy if the DBG_VALUE operand exactly
1081  // matches the copy destination.
1082  if (PostRA && Reg != DstMO->getReg())
1083  return false;
1084 
1085  for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg)) {
1086  DbgMO.setReg(SrcMO->getReg());
1087  DbgMO.setSubReg(SrcMO->getSubReg());
1088  }
1089  return true;
1090 }
1091 
1092 using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
1093 /// Sink an instruction and its associated debug instructions.
1094 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
1095  MachineBasicBlock::iterator InsertPos,
1096  ArrayRef<MIRegs> DbgValuesToSink) {
1097  // If we cannot find a location to use (merge with), then we erase the debug
1098  // location to prevent debug-info driven tools from potentially reporting
1099  // wrong location information.
1100  if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
1101  MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
1102  InsertPos->getDebugLoc()));
1103  else
1104  MI.setDebugLoc(DebugLoc());
1105 
1106  // Move the instruction.
1107  MachineBasicBlock *ParentBlock = MI.getParent();
1108  SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
1110 
1111  // Sink a copy of debug users to the insert position. Mark the original
1112  // DBG_VALUE location as 'undef', indicating that any earlier variable
1113  // location should be terminated as we've optimised away the value at this
1114  // point.
1115  for (const auto &DbgValueToSink : DbgValuesToSink) {
1116  MachineInstr *DbgMI = DbgValueToSink.first;
1117  MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(DbgMI);
1118  SuccToSinkTo.insert(InsertPos, NewDbgMI);
1119 
1120  bool PropagatedAllSunkOps = true;
1121  for (unsigned Reg : DbgValueToSink.second) {
1122  if (DbgMI->hasDebugOperandForReg(Reg)) {
1123  if (!attemptDebugCopyProp(MI, *DbgMI, Reg)) {
1124  PropagatedAllSunkOps = false;
1125  break;
1126  }
1127  }
1128  }
1129  if (!PropagatedAllSunkOps)
1130  DbgMI->setDebugValueUndef();
1131  }
1132 }
1133 
1134 /// hasStoreBetween - check if there is store betweeen straight line blocks From
1135 /// and To.
1136 bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
1138  // Make sure From and To are in straight line which means From dominates To
1139  // and To post dominates From.
1140  if (!DT->dominates(From, To) || !PDT->dominates(To, From))
1141  return true;
1142 
1143  auto BlockPair = std::make_pair(From, To);
1144 
1145  // Does these two blocks pair be queried before and have a definite cached
1146  // result?
1147  if (HasStoreCache.find(BlockPair) != HasStoreCache.end())
1148  return HasStoreCache[BlockPair];
1149 
1150  if (StoreInstrCache.find(BlockPair) != StoreInstrCache.end())
1151  return llvm::any_of(StoreInstrCache[BlockPair], [&](MachineInstr *I) {
1152  return I->mayAlias(AA, MI, false);
1153  });
1154 
1155  bool SawStore = false;
1156  bool HasAliasedStore = false;
1157  DenseSet<MachineBasicBlock *> HandledBlocks;
1158  DenseSet<MachineBasicBlock *> HandledDomBlocks;
1159  // Go through all reachable blocks from From.
1160  for (MachineBasicBlock *BB : depth_first(From)) {
1161  // We insert the instruction at the start of block To, so no need to worry
1162  // about stores inside To.
1163  // Store in block From should be already considered when just enter function
1164  // SinkInstruction.
1165  if (BB == To || BB == From)
1166  continue;
1167 
1168  // We already handle this BB in previous iteration.
1169  if (HandledBlocks.count(BB))
1170  continue;
1171 
1172  HandledBlocks.insert(BB);
1173  // To post dominates BB, it must be a path from block From.
1174  if (PDT->dominates(To, BB)) {
1175  if (!HandledDomBlocks.count(BB))
1176  HandledDomBlocks.insert(BB);
1177 
1178  // If this BB is too big or the block number in straight line between From
1179  // and To is too big, stop searching to save compiling time.
1180  if (BB->size() > SinkLoadInstsPerBlockThreshold ||
1181  HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
1182  for (auto *DomBB : HandledDomBlocks) {
1183  if (DomBB != BB && DT->dominates(DomBB, BB))
1184  HasStoreCache[std::make_pair(DomBB, To)] = true;
1185  else if(DomBB != BB && DT->dominates(BB, DomBB))
1186  HasStoreCache[std::make_pair(From, DomBB)] = true;
1187  }
1188  HasStoreCache[BlockPair] = true;
1189  return true;
1190  }
1191 
1192  for (MachineInstr &I : *BB) {
1193  // Treat as alias conservatively for a call or an ordered memory
1194  // operation.
1195  if (I.isCall() || I.hasOrderedMemoryRef()) {
1196  for (auto *DomBB : HandledDomBlocks) {
1197  if (DomBB != BB && DT->dominates(DomBB, BB))
1198  HasStoreCache[std::make_pair(DomBB, To)] = true;
1199  else if(DomBB != BB && DT->dominates(BB, DomBB))
1200  HasStoreCache[std::make_pair(From, DomBB)] = true;
1201  }
1202  HasStoreCache[BlockPair] = true;
1203  return true;
1204  }
1205 
1206  if (I.mayStore()) {
1207  SawStore = true;
1208  // We still have chance to sink MI if all stores between are not
1209  // aliased to MI.
1210  // Cache all store instructions, so that we don't need to go through
1211  // all From reachable blocks for next load instruction.
1212  if (I.mayAlias(AA, MI, false))
1213  HasAliasedStore = true;
1214  StoreInstrCache[BlockPair].push_back(&I);
1215  }
1216  }
1217  }
1218  }
1219  // If there is no store at all, cache the result.
1220  if (!SawStore)
1221  HasStoreCache[BlockPair] = false;
1222  return HasAliasedStore;
1223 }
1224 
1225 /// Sink instructions into loops if profitable. This especially tries to prevent
1226 /// register spills caused by register pressure if there is little to no
1227 /// overhead moving instructions into loops.
1228 bool MachineSinking::SinkIntoLoop(MachineLoop *L, MachineInstr &I) {
1229  LLVM_DEBUG(dbgs() << "LoopSink: Finding sink block for: " << I);
1230  MachineBasicBlock *Preheader = L->getLoopPreheader();
1231  assert(Preheader && "Loop sink needs a preheader block");
1232  MachineBasicBlock *SinkBlock = nullptr;
1233  bool CanSink = true;
1234  const MachineOperand &MO = I.getOperand(0);
1235 
1236  for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
1237  LLVM_DEBUG(dbgs() << "LoopSink: Analysing use: " << MI);
1238  if (!L->contains(&MI)) {
1239  LLVM_DEBUG(dbgs() << "LoopSink: Use not in loop, can't sink.\n");
1240  CanSink = false;
1241  break;
1242  }
1243 
1244  // FIXME: Come up with a proper cost model that estimates whether sinking
1245  // the instruction (and thus possibly executing it on every loop
1246  // iteration) is more expensive than a register.
1247  // For now assumes that copies are cheap and thus almost always worth it.
1248  if (!MI.isCopy()) {
1249  LLVM_DEBUG(dbgs() << "LoopSink: Use is not a copy\n");
1250  CanSink = false;
1251  break;
1252  }
1253  if (!SinkBlock) {
1254  SinkBlock = MI.getParent();
1255  LLVM_DEBUG(dbgs() << "LoopSink: Setting sink block to: "
1256  << printMBBReference(*SinkBlock) << "\n");
1257  continue;
1258  }
1259  SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent());
1260  if (!SinkBlock) {
1261  LLVM_DEBUG(dbgs() << "LoopSink: Can't find nearest dominator\n");
1262  CanSink = false;
1263  break;
1264  }
1265  LLVM_DEBUG(dbgs() << "LoopSink: Setting nearest common dom block: " <<
1266  printMBBReference(*SinkBlock) << "\n");
1267  }
1268 
1269  if (!CanSink) {
1270  LLVM_DEBUG(dbgs() << "LoopSink: Can't sink instruction.\n");
1271  return false;
1272  }
1273  if (!SinkBlock) {
1274  LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, can't find sink block.\n");
1275  return false;
1276  }
1277  if (SinkBlock == Preheader) {
1278  LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, sink block is the preheader\n");
1279  return false;
1280  }
1281  if (SinkBlock->size() > SinkLoadInstsPerBlockThreshold) {
1282  LLVM_DEBUG(dbgs() << "LoopSink: Not Sinking, block too large to analyse.\n");
1283  return false;
1284  }
1285 
1286  LLVM_DEBUG(dbgs() << "LoopSink: Sinking instruction!\n");
1287  SinkBlock->splice(SinkBlock->SkipPHIsAndLabels(SinkBlock->begin()), Preheader,
1288  I);
1289 
1290  // The instruction is moved from its basic block, so do not retain the
1291  // debug information.
1292  assert(!I.isDebugInstr() && "Should not sink debug inst");
1293  I.setDebugLoc(DebugLoc());
1294  return true;
1295 }
1296 
1297 /// Return true if a target defined block prologue instruction interferes
1298 /// with a sink candidate.
1301  MachineInstr &MI,
1302  const TargetRegisterInfo *TRI,
1303  const TargetInstrInfo *TII,
1304  const MachineRegisterInfo *MRI) {
1305  if (BB->begin() == End)
1306  return false; // no prologue
1307  for (MachineBasicBlock::iterator PI = BB->getFirstNonPHI(); PI != End; ++PI) {
1308  // Only check target defined prologue instructions
1309  if (!TII->isBasicBlockPrologue(*PI))
1310  continue;
1311  for (auto &MO : MI.operands()) {
1312  if (!MO.isReg())
1313  continue;
1314  Register Reg = MO.getReg();
1315  if (!Reg)
1316  continue;
1317  if (MO.isUse()) {
1319  (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(Reg))))
1320  continue;
1321  if (PI->modifiesRegister(Reg, TRI))
1322  return true;
1323  } else {
1324  if (PI->readsRegister(Reg, TRI))
1325  return true;
1326  // Check for interference with non-dead defs
1327  auto *DefOp = PI->findRegisterDefOperand(Reg, false, true, TRI);
1328  if (DefOp && !DefOp->isDead())
1329  return true;
1330  }
1331  }
1332  }
1333  return false;
1334 }
1335 
1336 /// SinkInstruction - Determine whether it is safe to sink the specified machine
1337 /// instruction out of its current block into a successor.
1338 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
1339  AllSuccsCache &AllSuccessors) {
1340  // Don't sink instructions that the target prefers not to sink.
1341  if (!TII->shouldSink(MI))
1342  return false;
1343 
1344  // Check if it's safe to move the instruction.
1345  if (!MI.isSafeToMove(AA, SawStore))
1346  return false;
1347 
1348  // Convergent operations may not be made control-dependent on additional
1349  // values.
1350  if (MI.isConvergent())
1351  return false;
1352 
1353  // Don't break implicit null checks. This is a performance heuristic, and not
1354  // required for correctness.
1356  return false;
1357 
1358  // FIXME: This should include support for sinking instructions within the
1359  // block they are currently in to shorten the live ranges. We often get
1360  // instructions sunk into the top of a large block, but it would be better to
1361  // also sink them down before their first use in the block. This xform has to
1362  // be careful not to *increase* register pressure though, e.g. sinking
1363  // "x = y + z" down if it kills y and z would increase the live ranges of y
1364  // and z and only shrink the live range of x.
1365 
1366  bool BreakPHIEdge = false;
1367  MachineBasicBlock *ParentBlock = MI.getParent();
1368  MachineBasicBlock *SuccToSinkTo =
1369  FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1370 
1371  // If there are no outputs, it must have side-effects.
1372  if (!SuccToSinkTo)
1373  return false;
1374 
1375  // If the instruction to move defines a dead physical register which is live
1376  // when leaving the basic block, don't move it because it could turn into a
1377  // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
1378  for (const MachineOperand &MO : MI.operands()) {
1379  if (!MO.isReg() || MO.isUse())
1380  continue;
1381  Register Reg = MO.getReg();
1382  if (Reg == 0 || !Register::isPhysicalRegister(Reg))
1383  continue;
1384  if (SuccToSinkTo->isLiveIn(Reg))
1385  return false;
1386  }
1387 
1388  LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
1389 
1390  // If the block has multiple predecessors, this is a critical edge.
1391  // Decide if we can sink along it or need to break the edge.
1392  if (SuccToSinkTo->pred_size() > 1) {
1393  // We cannot sink a load across a critical edge - there may be stores in
1394  // other code paths.
1395  bool TryBreak = false;
1396  bool Store =
1397  MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo, MI) : true;
1398  if (!MI.isSafeToMove(AA, Store)) {
1399  LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
1400  TryBreak = true;
1401  }
1402 
1403  // We don't want to sink across a critical edge if we don't dominate the
1404  // successor. We could be introducing calculations to new code paths.
1405  if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
1406  LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
1407  TryBreak = true;
1408  }
1409 
1410  // Don't sink instructions into a loop.
1411  if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
1412  LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
1413  TryBreak = true;
1414  }
1415 
1416  // Otherwise we are OK with sinking along a critical edge.
1417  if (!TryBreak)
1418  LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
1419  else {
1420  // Mark this edge as to be split.
1421  // If the edge can actually be split, the next iteration of the main loop
1422  // will sink MI in the newly created block.
1423  bool Status =
1424  PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1425  if (!Status)
1426  LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1427  "break critical edge\n");
1428  // The instruction will not be sunk this time.
1429  return false;
1430  }
1431  }
1432 
1433  if (BreakPHIEdge) {
1434  // BreakPHIEdge is true if all the uses are in the successor MBB being
1435  // sunken into and they are all PHI nodes. In this case, machine-sink must
1436  // break the critical edge first.
1437  bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
1438  SuccToSinkTo, BreakPHIEdge);
1439  if (!Status)
1440  LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1441  "break critical edge\n");
1442  // The instruction will not be sunk this time.
1443  return false;
1444  }
1445 
1446  // Determine where to insert into. Skip phi nodes.
1447  MachineBasicBlock::iterator InsertPos =
1448  SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());
1449  if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI)) {
1450  LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
1451  return false;
1452  }
1453 
1454  // Collect debug users of any vreg that this inst defines.
1455  SmallVector<MIRegs, 4> DbgUsersToSink;
1456  for (auto &MO : MI.operands()) {
1457  if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1458  continue;
1459  if (!SeenDbgUsers.count(MO.getReg()))
1460  continue;
1461 
1462  // Sink any users that don't pass any other DBG_VALUEs for this variable.
1463  auto &Users = SeenDbgUsers[MO.getReg()];
1464  for (auto &User : Users) {
1465  MachineInstr *DbgMI = User.getPointer();
1466  if (User.getInt()) {
1467  // This DBG_VALUE would re-order assignments. If we can't copy-propagate
1468  // it, it can't be recovered. Set it undef.
1469  if (!attemptDebugCopyProp(MI, *DbgMI, MO.getReg()))
1470  DbgMI->setDebugValueUndef();
1471  } else {
1472  DbgUsersToSink.push_back(
1473  {DbgMI, SmallVector<unsigned, 2>(1, MO.getReg())});
1474  }
1475  }
1476  }
1477 
1478  // After sinking, some debug users may not be dominated any more. If possible,
1479  // copy-propagate their operands. As it's expensive, don't do this if there's
1480  // no debuginfo in the program.
1481  if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1482  SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
1483 
1484  performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);
1485 
1486  // Conservatively, clear any kill flags, since it's possible that they are no
1487  // longer correct.
1488  // Note that we have to clear the kill flags for any register this instruction
1489  // uses as we may sink over another instruction which currently kills the
1490  // used registers.
1491  for (MachineOperand &MO : MI.operands()) {
1492  if (MO.isReg() && MO.isUse())
1493  RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
1494  }
1495 
1496  return true;
1497 }
1498 
1499 void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1500  MachineInstr &MI, MachineBasicBlock *TargetBlock) {
1501  assert(MI.isCopy());
1502  assert(MI.getOperand(1).isReg());
1503 
1504  // Enumerate all users of vreg operands that are def'd. Skip those that will
1505  // be sunk. For the rest, if they are not dominated by the block we will sink
1506  // MI into, propagate the copy source to them.
1507  SmallVector<MachineInstr *, 4> DbgDefUsers;
1508  SmallVector<Register, 4> DbgUseRegs;
1509  const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
1510  for (auto &MO : MI.operands()) {
1511  if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
1512  continue;
1513  DbgUseRegs.push_back(MO.getReg());
1514  for (auto &User : MRI.use_instructions(MO.getReg())) {
1515  if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))
1516  continue;
1517 
1518  // If is in same block, will either sink or be use-before-def.
1519  if (User.getParent() == MI.getParent())
1520  continue;
1521 
1522  assert(User.hasDebugOperandForReg(MO.getReg()) &&
1523  "DBG_VALUE user of vreg, but has no operand for it?");
1524  DbgDefUsers.push_back(&User);
1525  }
1526  }
1527 
1528  // Point the users of this copy that are no longer dominated, at the source
1529  // of the copy.
1530  for (auto *User : DbgDefUsers) {
1531  for (auto &Reg : DbgUseRegs) {
1532  for (auto &DbgOp : User->getDebugOperandsForReg(Reg)) {
1533  DbgOp.setReg(MI.getOperand(1).getReg());
1534  DbgOp.setSubReg(MI.getOperand(1).getSubReg());
1535  }
1536  }
1537  }
1538 }
1539 
1540 //===----------------------------------------------------------------------===//
1541 // This pass is not intended to be a replacement or a complete alternative
1542 // for the pre-ra machine sink pass. It is only designed to sink COPY
1543 // instructions which should be handled after RA.
1544 //
1545 // This pass sinks COPY instructions into a successor block, if the COPY is not
1546 // used in the current block and the COPY is live-in to a single successor
1547 // (i.e., doesn't require the COPY to be duplicated). This avoids executing the
1548 // copy on paths where their results aren't needed. This also exposes
1549 // additional opportunites for dead copy elimination and shrink wrapping.
1550 //
1551 // These copies were either not handled by or are inserted after the MachineSink
1552 // pass. As an example of the former case, the MachineSink pass cannot sink
1553 // COPY instructions with allocatable source registers; for AArch64 these type
1554 // of copy instructions are frequently used to move function parameters (PhyReg)
1555 // into virtual registers in the entry block.
1556 //
1557 // For the machine IR below, this pass will sink %w19 in the entry into its
1558 // successor (%bb.1) because %w19 is only live-in in %bb.1.
1559 // %bb.0:
1560 // %wzr = SUBSWri %w1, 1
1561 // %w19 = COPY %w0
1562 // Bcc 11, %bb.2
1563 // %bb.1:
1564 // Live Ins: %w19
1565 // BL @fun
1566 // %w0 = ADDWrr %w0, %w19
1567 // RET %w0
1568 // %bb.2:
1569 // %w0 = COPY %wzr
1570 // RET %w0
1571 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
1572 // able to see %bb.0 as a candidate.
1573 //===----------------------------------------------------------------------===//
1574 namespace {
1575 
1576 class PostRAMachineSinking : public MachineFunctionPass {
1577 public:
1578  bool runOnMachineFunction(MachineFunction &MF) override;
1579 
1580  static char ID;
1581  PostRAMachineSinking() : MachineFunctionPass(ID) {}
1582  StringRef getPassName() const override { return "PostRA Machine Sink"; }
1583 
1584  void getAnalysisUsage(AnalysisUsage &AU) const override {
1585  AU.setPreservesCFG();
1587  }
1588 
1589  MachineFunctionProperties getRequiredProperties() const override {
1590  return MachineFunctionProperties().set(
1592  }
1593 
1594 private:
1595  /// Track which register units have been modified and used.
1596  LiveRegUnits ModifiedRegUnits, UsedRegUnits;
1597 
1598  /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
1599  /// entry in this map for each unit it touches. The DBG_VALUE's entry
1600  /// consists of a pointer to the instruction itself, and a vector of registers
1601  /// referred to by the instruction that overlap the key register unit.
1603 
1604  /// Sink Copy instructions unused in the same block close to their uses in
1605  /// successors.
1606  bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
1607  const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
1608 };
1609 } // namespace
1610 
1611 char PostRAMachineSinking::ID = 0;
1613 
1614 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
1615  "PostRA Machine Sink", false, false)
1616 
1617 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
1619  LiveRegUnits LiveInRegUnits(*TRI);
1620  LiveInRegUnits.addLiveIns(MBB);
1621  return !LiveInRegUnits.available(Reg);
1622 }
1623 
1624 static MachineBasicBlock *
1626  const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1627  unsigned Reg, const TargetRegisterInfo *TRI) {
1628  // Try to find a single sinkable successor in which Reg is live-in.
1629  MachineBasicBlock *BB = nullptr;
1630  for (auto *SI : SinkableBBs) {
1631  if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
1632  // If BB is set here, Reg is live-in to at least two sinkable successors,
1633  // so quit.
1634  if (BB)
1635  return nullptr;
1636  BB = SI;
1637  }
1638  }
1639  // Reg is not live-in to any sinkable successors.
1640  if (!BB)
1641  return nullptr;
1642 
1643  // Check if any register aliased with Reg is live-in in other successors.
1644  for (auto *SI : CurBB.successors()) {
1645  if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1646  return nullptr;
1647  }
1648  return BB;
1649 }
1650 
1651 static MachineBasicBlock *
1653  const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1654  ArrayRef<unsigned> DefedRegsInCopy,
1655  const TargetRegisterInfo *TRI) {
1656  MachineBasicBlock *SingleBB = nullptr;
1657  for (auto DefReg : DefedRegsInCopy) {
1659  getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1660  if (!BB || (SingleBB && SingleBB != BB))
1661  return nullptr;
1662  SingleBB = BB;
1663  }
1664  return SingleBB;
1665 }
1666 
1668  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1669  LiveRegUnits &UsedRegUnits,
1670  const TargetRegisterInfo *TRI) {
1671  for (auto U : UsedOpsInCopy) {
1672  MachineOperand &MO = MI->getOperand(U);
1673  Register SrcReg = MO.getReg();
1674  if (!UsedRegUnits.available(SrcReg)) {
1675  MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1676  for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1677  if (UI.killsRegister(SrcReg, TRI)) {
1678  UI.clearRegisterKills(SrcReg, TRI);
1679  MO.setIsKill(true);
1680  break;
1681  }
1682  }
1683  }
1684  }
1685 }
1686 
1688  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1689  SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1690  MachineFunction &MF = *SuccBB->getParent();
1692  for (unsigned DefReg : DefedRegsInCopy)
1693  for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S)
1694  SuccBB->removeLiveIn(*S);
1695  for (auto U : UsedOpsInCopy) {
1696  Register SrcReg = MI->getOperand(U).getReg();
1697  LaneBitmask Mask;
1698  for (MCRegUnitMaskIterator S(SrcReg, TRI); S.isValid(); ++S) {
1699  Mask |= (*S).second;
1700  }
1701  SuccBB->addLiveIn(SrcReg, Mask.any() ? Mask : LaneBitmask::getAll());
1702  }
1703  SuccBB->sortUniqueLiveIns();
1704 }
1705 
1707  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1708  SmallVectorImpl<unsigned> &DefedRegsInCopy,
1709  LiveRegUnits &ModifiedRegUnits,
1710  LiveRegUnits &UsedRegUnits) {
1711  bool HasRegDependency = false;
1712  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1713  MachineOperand &MO = MI->getOperand(i);
1714  if (!MO.isReg())
1715  continue;
1716  Register Reg = MO.getReg();
1717  if (!Reg)
1718  continue;
1719  if (MO.isDef()) {
1720  if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1721  HasRegDependency = true;
1722  break;
1723  }
1724  DefedRegsInCopy.push_back(Reg);
1725 
1726  // FIXME: instead of isUse(), readsReg() would be a better fix here,
1727  // For example, we can ignore modifications in reg with undef. However,
1728  // it's not perfectly clear if skipping the internal read is safe in all
1729  // other targets.
1730  } else if (MO.isUse()) {
1731  if (!ModifiedRegUnits.available(Reg)) {
1732  HasRegDependency = true;
1733  break;
1734  }
1735  UsedOpsInCopy.push_back(i);
1736  }
1737  }
1738  return HasRegDependency;
1739 }
1740 
1741 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1742  MachineFunction &MF,
1743  const TargetRegisterInfo *TRI,
1744  const TargetInstrInfo *TII) {
1746  // FIXME: For now, we sink only to a successor which has a single predecessor
1747  // so that we can directly sink COPY instructions to the successor without
1748  // adding any new block or branch instruction.
1749  for (MachineBasicBlock *SI : CurBB.successors())
1750  if (!SI->livein_empty() && SI->pred_size() == 1)
1751  SinkableBBs.insert(SI);
1752 
1753  if (SinkableBBs.empty())
1754  return false;
1755 
1756  bool Changed = false;
1757 
1758  // Track which registers have been modified and used between the end of the
1759  // block and the current instruction.
1760  ModifiedRegUnits.clear();
1761  UsedRegUnits.clear();
1762  SeenDbgInstrs.clear();
1763 
1765  // Track the operand index for use in Copy.
1766  SmallVector<unsigned, 2> UsedOpsInCopy;
1767  // Track the register number defed in Copy.
1768  SmallVector<unsigned, 2> DefedRegsInCopy;
1769 
1770  // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
1771  // for DBG_VALUEs later, record them when they're encountered.
1772  if (MI.isDebugValue()) {
1774  bool IsValid = true;
1775  for (MachineOperand &MO : MI.debug_operands()) {
1776  if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) {
1777  // Bail if we can already tell the sink would be rejected, rather
1778  // than needlessly accumulating lots of DBG_VALUEs.
1779  if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,
1780  ModifiedRegUnits, UsedRegUnits)) {
1781  IsValid = false;
1782  break;
1783  }
1784 
1785  // Record debug use of each reg unit.
1786  for (auto RI = MCRegUnitIterator(MO.getReg(), TRI); RI.isValid();
1787  ++RI)
1788  MIUnits[*RI].push_back(MO.getReg());
1789  }
1790  }
1791  if (IsValid) {
1792  for (auto &RegOps : MIUnits)
1793  SeenDbgInstrs[RegOps.first].emplace_back(&MI,
1794  std::move(RegOps.second));
1795  }
1796  continue;
1797  }
1798 
1799  if (MI.isDebugOrPseudoInstr())
1800  continue;
1801 
1802  // Do not move any instruction across function call.
1803  if (MI.isCall())
1804  return false;
1805 
1806  if (!MI.isCopy() || !MI.getOperand(0).isRenamable()) {
1807  LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1808  TRI);
1809  continue;
1810  }
1811 
1812  // Don't sink the COPY if it would violate a register dependency.
1813  if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,
1814  ModifiedRegUnits, UsedRegUnits)) {
1815  LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1816  TRI);
1817  continue;
1818  }
1819  assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1820  "Unexpect SrcReg or DefReg");
1821  MachineBasicBlock *SuccBB =
1822  getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
1823  // Don't sink if we cannot find a single sinkable successor in which Reg
1824  // is live-in.
1825  if (!SuccBB) {
1826  LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1827  TRI);
1828  continue;
1829  }
1830  assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1831  "Unexpected predecessor");
1832 
1833  // Collect DBG_VALUEs that must sink with this copy. We've previously
1834  // recorded which reg units that DBG_VALUEs read, if this instruction
1835  // writes any of those units then the corresponding DBG_VALUEs must sink.
1837  for (auto &MO : MI.operands()) {
1838  if (!MO.isReg() || !MO.isDef())
1839  continue;
1840 
1841  for (auto RI = MCRegUnitIterator(MO.getReg(), TRI); RI.isValid(); ++RI) {
1842  for (const auto &MIRegs : SeenDbgInstrs.lookup(*RI)) {
1843  auto &Regs = DbgValsToSinkMap[MIRegs.first];
1844  for (unsigned Reg : MIRegs.second)
1845  Regs.push_back(Reg);
1846  }
1847  }
1848  }
1849  auto DbgValsToSink = DbgValsToSinkMap.takeVector();
1850 
1851  LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);
1852 
1853  MachineBasicBlock::iterator InsertPos =
1854  SuccBB->SkipPHIsAndLabels(SuccBB->begin());
1855  if (blockPrologueInterferes(SuccBB, InsertPos, MI, TRI, TII, nullptr)) {
1856  LLVM_DEBUG(
1857  dbgs() << " *** Not sinking: prologue interference\n");
1858  continue;
1859  }
1860 
1861  // Clear the kill flag if SrcReg is killed between MI and the end of the
1862  // block.
1863  clearKillFlags(&MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
1864  performSink(MI, *SuccBB, InsertPos, DbgValsToSink);
1865  updateLiveIn(&MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
1866 
1867  Changed = true;
1868  ++NumPostRACopySink;
1869  }
1870  return Changed;
1871 }
1872 
1873 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1874  if (skipFunction(MF.getFunction()))
1875  return false;
1876 
1877  bool Changed = false;
1879  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
1880 
1881  ModifiedRegUnits.init(*TRI);
1882  UsedRegUnits.init(*TRI);
1883  for (auto &BB : MF)
1884  Changed |= tryToSinkCopy(BB, MF, TRI, TII);
1885 
1886  return Changed;
1887 }
llvm::MachineDominatorTree::findNearestCommonDominator
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
Definition: MachineDominators.h:160
llvm::LaneBitmask
Definition: LaneBitmask.h:40
i
i
Definition: README.txt:29
llvm::MachineBasicBlock::succ_size
unsigned succ_size() const
Definition: MachineBasicBlock.h:353
llvm::MachineInstr::setDebugValueUndef
void setDebugValueUndef()
Sets all register debug operands in this debug value instruction to be undef.
Definition: MachineInstr.h:1831
llvm::MachineBasicBlock::pred_begin
pred_iterator pred_begin()
Definition: MachineBasicBlock.h:325
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
Reg
unsigned Reg
Definition: MachineSink.cpp:1617
llvm::initializeMachineSinkingPass
void initializeMachineSinkingPass(PassRegistry &)
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::MachineBasicBlock::isLiveIn
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Definition: MachineBasicBlock.cpp:576
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:126
llvm::DILocation::getMergedLocation
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
Definition: DebugInfoMetadata.cpp:101
DebugInfoMetadata.h
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::LiveRegUnits::accumulateUsedDefed
static void accumulateUsedDefed(const MachineInstr &MI, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
For a machine instruction MI, adds all register units used in UsedRegUnits and defined or clobbered i...
Definition: LiveRegUnits.h:47
llvm::TargetInstrInfo::MachineBranchPredicate
Represents a predicate at the MachineFunction level.
Definition: TargetInstrInfo.h:651
Pass.h
llvm::RegisterOperands
List of registers defined and used by a machine instruction.
Definition: RegisterPressure.h:166
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
llvm::MachineLoopInfo::findLoopPreheader
MachineBasicBlock * findLoopPreheader(MachineLoop *L, bool SpeculativePreheader=false, bool FindMultiLoopPreheader=false) const
Find the block that either is the loop preheader, or could speculatively be used as the preheader.
Definition: MachineLoopInfo.cpp:118
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
attemptDebugCopyProp
static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI, Register Reg)
If the sunk instruction is a copy, try to forward the copy instead of leaving an 'undef' DBG_VALUE in...
Definition: MachineSink.cpp:1042
llvm::MachineOperand::setIsKill
void setIsKill(bool Val=true)
Definition: MachineOperand.h:509
SinkIntoLoopLimit
static cl::opt< unsigned > SinkIntoLoopLimit("machine-sink-loop-limit", cl::desc("The maximum number of instructions considered for loop sinking."), cl::init(50), cl::Hidden)
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:116
MapVector.h
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
RegisterClassInfo.h
MachineBasicBlock.h
llvm::LiveRegUnits::available
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:125
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::MemOp
Definition: TargetLowering.h:111
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:551
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
llvm::RegPressureTracker
Track the current register pressure at some position in the instruction stream, and remember the high...
Definition: RegisterPressure.h:357
llvm::MachineRegisterInfo::use_instructions
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:493
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
TargetInstrInfo.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:126
SinkInstruction
static bool SinkInstruction(Instruction *Inst, SmallPtrSetImpl< Instruction * > &Stores, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
SinkInstruction - Determine whether it is safe to sink the specified machine instruction out of its c...
Definition: Sink.cpp:102
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::MachineInstr::getMF
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
Definition: MachineInstr.cpp:636
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:765
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::LiveRegUnits::addLiveIns
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
Definition: LiveRegUnits.cpp:141
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:114
llvm::TargetRegisterInfo::getRegPressureSetLimit
virtual unsigned getRegPressureSetLimit(const MachineFunction &MF, unsigned Idx) const =0
Get the register unit pressure limit for this dimension.
llvm::MachineInstr::hasDebugOperandForReg
bool hasDebugOperandForReg(Register Reg) const
Returns whether this debug value has at least one debug operand with the register Reg.
Definition: MachineInstr.h:530
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1618
clearKillFlags
static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
Definition: MachineSink.cpp:1667
sinking
Machine code sinking
Definition: MachineSink.cpp:267
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:230
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
RegisterPressure.h
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
SinkLoadInstsPerBlockThreshold
static cl::opt< unsigned > SinkLoadInstsPerBlockThreshold("machine-sink-load-instrs-threshold", cl::desc("Do not try to find alias store for a load if there is a in-path " "block whose instruction number is higher than this threshold."), cl::init(2000), cl::Hidden)
AliasAnalysis.h
PointerIntPair.h
SinkingPreventsImplicitNullCheck
static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
Return true if MI is likely to be usable as a memory operation by the implicit null check optimizatio...
Definition: MachineSink.cpp:997
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::HexagonInstrInfo::isAsCheapAsAMove
bool isAsCheapAsAMove(const MachineInstr &MI) const override
Definition: HexagonInstrInfo.cpp:152
llvm::MachineInstr::getDebugOperandsForReg
static iterator_range< filter_iterator< Operand *, std::function< bool(Operand &Op)> > > getDebugOperandsForReg(Instruction *MI, Register Reg)
Returns a range of all of the operands that correspond to a debug use of Reg.
Definition: MachineInstr.h:541
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
CommandLine.h
llvm::MachineBasicBlock::pred_size
unsigned pred_size() const
Definition: MachineBasicBlock.h:337
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1607
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:650
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::MachineRegisterInfo::use_nodbg_operands
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:534
MachineLoopInfo.h
llvm::MachineLoopInfo::end
iterator end() const
Definition: MachineLoopInfo.h:121
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:22
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:480
llvm::User
Definition: User.h:44
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:369
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:501
llvm::MachineDominatorTree::isReachableFromEntry
bool isReachableFromEntry(const MachineBasicBlock *A)
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
Definition: MachineDominators.h:220
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:909
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::TargetRegisterInfo::getRegClassPressureSets
virtual const int * getRegClassPressureSets(const TargetRegisterClass *RC) const =0
Get the dimensions of register pressure impacted by this register class.
llvm::DomTreeNodeBase::children
iterator_range< iterator > children()
Definition: GenericDomTree.h:83
DenseSet.h
false
Definition: StackSlotColoring.cpp:141
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:180
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::size
size_type size() const
Definition: DenseSet.h:81
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::HexagonInstrInfo::shouldSink
bool shouldSink(const MachineInstr &MI) const override
Definition: HexagonInstrInfo.cpp:183
llvm::MachineFunction::begin
iterator begin()
Definition: MachineFunction.h:822
llvm::PseudoSourceValue
Special value supplied for machine level alias analysis.
Definition: PseudoSourceValue.h:35
llvm::LiveRegUnits
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
performSink
static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, MachineBasicBlock::iterator InsertPos, ArrayRef< MIRegs > DbgValuesToSink)
Sink an instruction and its associated debug instructions.
Definition: MachineSink.cpp:1094
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:396
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineLoopInfo::isLoopHeader
bool isLoopHeader(const MachineBasicBlock *BB) const
True if the block is a loop header node.
Definition: MachineLoopInfo.h:141
BranchProbability.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::RegisterOperands::collect
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
Definition: RegisterPressure.cpp:570
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:642
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
blockPrologueInterferes
static bool blockPrologueInterferes(MachineBasicBlock *BB, MachineBasicBlock::iterator End, MachineInstr &MI, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, const MachineRegisterInfo *MRI)
Return true if a target defined block prologue instruction interferes with a sink candidate.
Definition: MachineSink.cpp:1299
llvm::PPC::PRED_EQ
@ PRED_EQ
Definition: PPCPredicates.h:29
llvm::Register::isVirtual
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
llvm::MachineRegisterInfo::clearKillFlags
void clearKillFlags(Register Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
Definition: MachineRegisterInfo.cpp:427
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:640
BasicBlock.h
llvm::cl::opt< bool >
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE, "Machine code sinking", false, false) INITIALIZE_PASS_END(MachineSinking
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:42
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:112
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
uint64_t
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineSink.cpp:64
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::MachineSinkingID
char & MachineSinkingID
MachineSinking - This pass performs sinking on machine instructions.
Definition: MachineSink.cpp:258
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:385
mayLoadFromGOTOrConstantPool
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI)
Return true if this machine instruction loads from global offset table or constant pool.
Definition: MachineSink.cpp:365
llvm::MachineBlockFrequencyInfo::onEdgeSplit
void onEdgeSplit(const MachineBasicBlock &NewPredecessor, const MachineBasicBlock &NewSuccessor, const MachineBranchProbabilityInfo &MBPI)
incrementally calculate block frequencies when we split edges, to avoid full CFG traversal.
Definition: MachineBlockFrequencyInfo.cpp:258
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:174
llvm::MCRegUnitMaskIterator
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
Definition: MCRegisterInfo.h:714
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::MachineBasicBlock::SkipPHIsAndLabels
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
Definition: MachineBasicBlock.cpp:206
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:608
MCRegisterInfo.h
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3610
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
SplitEdges
static cl::opt< bool > SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden)
MachineFunctionPass.h
getSingleLiveInSuccBB
static MachineBasicBlock * getSingleLiveInSuccBB(MachineBasicBlock &CurBB, const SmallPtrSetImpl< MachineBasicBlock * > &SinkableBBs, unsigned Reg, const TargetRegisterInfo *TRI)
Definition: MachineSink.cpp:1625
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::PPC::PRED_NE
@ PRED_NE
Definition: PPCPredicates.h:32
SinkInstsIntoLoop
static cl::opt< bool > SinkInstsIntoLoop("sink-insts-to-avoid-spills", cl::desc("Sink instructions into loops to avoid " "register spills"), cl::init(false), cl::Hidden)
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::size
unsigned size() const
Definition: MachineBasicBlock.h:248
MachineBranchProbabilityInfo.h
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:29
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:234
llvm::MapVector::takeVector
VectorType takeVector()
Clear the MapVector and return the underlying vector.
Definition: MapVector.h:56
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1257
MachinePostDominators.h
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineRegisterInfo::hasOneDef
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
Definition: MachineRegisterInfo.h:452
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:358
llvm::MachineBranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Definition: MachineBranchProbabilityInfo.cpp:56
llvm::MachineBasicBlock::instr_begin
instr_iterator instr_begin()
Definition: MachineBasicBlock.h:261
Status
Definition: SIModeRegister.cpp:29
llvm::MachineBasicBlock::instr_end
instr_iterator instr_end()
Definition: MachineBasicBlock.h:263
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::MachineRegisterInfo::use_nodbg_empty
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
Definition: MachineRegisterInfo.h:574
CFG.h
llvm::RegClassWeight::RegWeight
unsigned RegWeight
Definition: TargetRegisterInfo.h:224
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
hasRegisterDependency
static bool hasRegisterDependency(MachineInstr *MI, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits)
Definition: MachineSink.cpp:1706
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:561
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1614
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:364
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:548
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::MachineBasicBlock::splice
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Definition: MachineBasicBlock.h:972
MIRegs
std::pair< MachineInstr *, SmallVector< unsigned, 2 > > MIRegs
Definition: MachineSink.cpp:1092
UseBlockFreqInfo
static cl::opt< bool > UseBlockFreqInfo("machine-sink-bfi", cl::desc("Use block frequency info to find successors to sink"), cl::init(true), cl::Hidden)
llvm::MachineRegisterInfo::hasOneNonDBGUse
bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
Definition: MachineRegisterInfo.cpp:415
llvm::MachineBasicBlock::removeLiveIn
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
Definition: MachineBasicBlock.cpp:558
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::detail::DenseSetImpl::contains
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
llvm::BranchProbability
Definition: BranchProbability.h:29
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:288
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::MachinePostDominatorTree
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
Definition: MachinePostDominators.h:27
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
llvm::MachineBasicBlock::addLiveIn
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
Definition: MachineBasicBlock.h:376
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:509
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:378
llvm::RegionPressure
RegisterPressure computed within a region of instructions delimited by TopPos and BottomPos.
Definition: RegisterPressure.h:82
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachinePostDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachinePostDominators.h:54
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1751
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:606
llvm::MachineInstr::isCopyLike
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Definition: MachineInstr.h:1307
llvm::MachineBasicBlock::sortUniqueLiveIns
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
Definition: MachineBasicBlock.cpp:582
code
*Add support for compiling functions in both ARM and Thumb then taking the smallest *Add support for compiling individual basic blocks in thumb when in a larger ARM function This can be used for presumed cold code
Definition: README-Thumb.txt:9
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1308
llvm::MachineLoopInfo::getLoopDepth
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
Definition: MachineLoopInfo.h:136
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
AA
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:680
INITIALIZE_PASS
INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink", "PostRA Machine Sink", false, false) static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB
PostOrderIterator.h
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:46
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:369
llvm::MachineLoopInfo::begin
iterator begin() const
Definition: MachineLoopInfo.h:120
SmallVector.h
SinkLoadBlocksThreshold
static cl::opt< unsigned > SinkLoadBlocksThreshold("machine-sink-load-blocks-threshold", cl::desc("Do not try to find alias store for a load if the block number in " "the straight line is higher than this threshold."), cl::init(20), cl::Hidden)
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:277
SplitEdgeProbabilityThreshold
static cl::opt< unsigned > SplitEdgeProbabilityThreshold("machine-sink-split-probability-threshold", cl::desc("Percentage threshold for splitting single-instruction critical edge. " "If the branch threshold is higher than this threshold, we allow " "speculative execution of up to 1 instruction to avoid branching to " "splitted critical edge"), cl::init(40), cl::Hidden)
llvm::MachineBasicBlock::isInlineAsmBrIndirectTarget
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
Definition: MachineBasicBlock.h:616
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
updateLiveIn
static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy)
Definition: MachineSink.cpp:1687
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:104
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1347
llvm::TargetRegisterInfo::getRegClassWeight
virtual const RegClassWeight & getRegClassWeight(const TargetRegisterClass *RC) const =0
Get the weight in units of pressure for this register class.
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:249
llvm::SmallSet::clear
void clear()
Definition: SmallSet.h:220
llvm::SmallVectorImpl< MachineInstr * >
MachineOperand.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::PostRAMachineSinkingID
char & PostRAMachineSinkingID
This pass perform post-ra machine sink for COPY instructions.
Definition: MachineSink.cpp:1612
llvm::cl::desc
Definition: CommandLine.h:405
ProcessBlock
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:174
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
MachineFunction.h
llvm::MachineLoop::isLoopInvariant
bool isLoopInvariant(MachineInstr &I) const
Returns true if the instruction is loop invariant.
Definition: MachineLoopInfo.cpp:154
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
MachineBlockFrequencyInfo.h
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:279
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
SetVector.h
MachineDominators.h
SmallSet.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37