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