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