LLVM  10.0.0svn
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/SetVector.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
38 #include "llvm/IR/BasicBlock.h"
39 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/Pass.h"
44 #include "llvm/Support/Debug.h"
46 #include <algorithm>
47 #include <cassert>
48 #include <cstdint>
49 #include <map>
50 #include <utility>
51 #include <vector>
52 
53 using namespace llvm;
54 
55 #define DEBUG_TYPE "machine-sink"
56 
57 static cl::opt<bool>
58 SplitEdges("machine-sink-split",
59  cl::desc("Split critical edges during machine sinking"),
60  cl::init(true), cl::Hidden);
61 
62 static cl::opt<bool>
63 UseBlockFreqInfo("machine-sink-bfi",
64  cl::desc("Use block frequency info to find successors to sink"),
65  cl::init(true), cl::Hidden);
66 
68  "machine-sink-split-probability-threshold",
69  cl::desc(
70  "Percentage threshold for splitting single-instruction critical edge. "
71  "If the branch threshold is higher than this threshold, we allow "
72  "speculative execution of up to 1 instruction to avoid branching to "
73  "splitted critical edge"),
74  cl::init(40), cl::Hidden);
75 
76 STATISTIC(NumSunk, "Number of machine instructions sunk");
77 STATISTIC(NumSplit, "Number of critical edges split");
78 STATISTIC(NumCoalesces, "Number of copies coalesced");
79 STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
80 
81 namespace {
82 
83  class MachineSinking : public MachineFunctionPass {
84  const TargetInstrInfo *TII;
85  const TargetRegisterInfo *TRI;
86  MachineRegisterInfo *MRI; // Machine register information
87  MachineDominatorTree *DT; // Machine dominator tree
88  MachinePostDominatorTree *PDT; // Machine post dominator tree
89  MachineLoopInfo *LI;
90  const MachineBlockFrequencyInfo *MBFI;
91  const MachineBranchProbabilityInfo *MBPI;
92  AliasAnalysis *AA;
93 
94  // Remember which edges have been considered for breaking.
96  CEBCandidates;
97  // Remember which edges we are about to split.
98  // This is different from CEBCandidates since those edges
99  // will be split.
101 
102  SparseBitVector<> RegsToClearKillFlags;
103 
104  using AllSuccsCache =
105  std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
106 
107  public:
108  static char ID; // Pass identification
109 
110  MachineSinking() : MachineFunctionPass(ID) {
112  }
113 
114  bool runOnMachineFunction(MachineFunction &MF) override;
115 
116  void getAnalysisUsage(AnalysisUsage &AU) const override {
117  AU.setPreservesCFG();
127  if (UseBlockFreqInfo)
129  }
130 
131  void releaseMemory() override {
132  CEBCandidates.clear();
133  }
134 
135  private:
136  bool ProcessBlock(MachineBasicBlock &MBB);
137  bool isWorthBreakingCriticalEdge(MachineInstr &MI,
139  MachineBasicBlock *To);
140 
141  /// Postpone the splitting of the given critical
142  /// edge (\p From, \p To).
143  ///
144  /// We do not split the edges on the fly. Indeed, this invalidates
145  /// the dominance information and thus triggers a lot of updates
146  /// of that information underneath.
147  /// Instead, we postpone all the splits after each iteration of
148  /// the main loop. That way, the information is at least valid
149  /// for the lifetime of an iteration.
150  ///
151  /// \return True if the edge is marked as toSplit, false otherwise.
152  /// False can be returned if, for instance, this is not profitable.
153  bool PostponeSplitCriticalEdge(MachineInstr &MI,
155  MachineBasicBlock *To,
156  bool BreakPHIEdge);
157  bool SinkInstruction(MachineInstr &MI, bool &SawStore,
158 
159  AllSuccsCache &AllSuccessors);
160  bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
161  MachineBasicBlock *DefMBB,
162  bool &BreakPHIEdge, bool &LocalUse) const;
163  MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
164  bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
165  bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
166  MachineBasicBlock *MBB,
167  MachineBasicBlock *SuccToSinkTo,
168  AllSuccsCache &AllSuccessors);
169 
170  bool PerformTrivialForwardCoalescing(MachineInstr &MI,
171  MachineBasicBlock *MBB);
172 
174  GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
175  AllSuccsCache &AllSuccessors) const;
176  };
177 
178 } // end anonymous namespace
179 
180 char MachineSinking::ID = 0;
181 
183 
184 INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
185  "Machine code sinking", false, false)
191  "Machine code sinking", false, false)
192 
193 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
194  MachineBasicBlock *MBB) {
195  if (!MI.isCopy())
196  return false;
197 
198  unsigned SrcReg = MI.getOperand(1).getReg();
199  unsigned DstReg = MI.getOperand(0).getReg();
202  !MRI->hasOneNonDBGUse(SrcReg))
203  return false;
204 
205  const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
206  const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
207  if (SRC != DRC)
208  return false;
209 
210  MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
211  if (DefMI->isCopyLike())
212  return false;
213  LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
214  LLVM_DEBUG(dbgs() << "*** to: " << MI);
215  MRI->replaceRegWith(DstReg, SrcReg);
216  MI.eraseFromParent();
217 
218  // Conservatively, clear any kill flags, since it's possible that they are no
219  // longer correct.
220  MRI->clearKillFlags(SrcReg);
221 
222  ++NumCoalesces;
223  return true;
224 }
225 
226 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
227 /// occur in blocks dominated by the specified block. If any use is in the
228 /// definition block, then return false since it is never legal to move def
229 /// after uses.
230 bool
232  MachineBasicBlock *MBB,
233  MachineBasicBlock *DefMBB,
234  bool &BreakPHIEdge,
235  bool &LocalUse) const {
237  "Only makes sense for vregs");
238 
239  // Ignore debug uses because debug info doesn't affect the code.
240  if (MRI->use_nodbg_empty(Reg))
241  return true;
242 
243  // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
244  // into and they are all PHI nodes. In this case, machine-sink must break
245  // the critical edge first. e.g.
246  //
247  // %bb.1: derived from LLVM BB %bb4.preheader
248  // Predecessors according to CFG: %bb.0
249  // ...
250  // %reg16385 = DEC64_32r %reg16437, implicit-def dead %eflags
251  // ...
252  // JE_4 <%bb.37>, implicit %eflags
253  // Successors according to CFG: %bb.37 %bb.2
254  //
255  // %bb.2: derived from LLVM BB %bb.nph
256  // Predecessors according to CFG: %bb.0 %bb.1
257  // %reg16386 = PHI %reg16434, %bb.0, %reg16385, %bb.1
258  BreakPHIEdge = true;
259  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
260  MachineInstr *UseInst = MO.getParent();
261  unsigned OpNo = &MO - &UseInst->getOperand(0);
262  MachineBasicBlock *UseBlock = UseInst->getParent();
263  if (!(UseBlock == MBB && UseInst->isPHI() &&
264  UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
265  BreakPHIEdge = false;
266  break;
267  }
268  }
269  if (BreakPHIEdge)
270  return true;
271 
272  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
273  // Determine the block of the use.
274  MachineInstr *UseInst = MO.getParent();
275  unsigned OpNo = &MO - &UseInst->getOperand(0);
276  MachineBasicBlock *UseBlock = UseInst->getParent();
277  if (UseInst->isPHI()) {
278  // PHI nodes use the operand in the predecessor block, not the block with
279  // the PHI.
280  UseBlock = UseInst->getOperand(OpNo+1).getMBB();
281  } else if (UseBlock == DefMBB) {
282  LocalUse = true;
283  return false;
284  }
285 
286  // Check that it dominates.
287  if (!DT->dominates(MBB, UseBlock))
288  return false;
289  }
290 
291  return true;
292 }
293 
294 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
295  if (skipFunction(MF.getFunction()))
296  return false;
297 
298  LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
299 
300  TII = MF.getSubtarget().getInstrInfo();
301  TRI = MF.getSubtarget().getRegisterInfo();
302  MRI = &MF.getRegInfo();
303  DT = &getAnalysis<MachineDominatorTree>();
304  PDT = &getAnalysis<MachinePostDominatorTree>();
305  LI = &getAnalysis<MachineLoopInfo>();
306  MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
307  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
308  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
309 
310  bool EverMadeChange = false;
311 
312  while (true) {
313  bool MadeChange = false;
314 
315  // Process all basic blocks.
316  CEBCandidates.clear();
317  ToSplit.clear();
318  for (auto &MBB: MF)
319  MadeChange |= ProcessBlock(MBB);
320 
321  // If we have anything we marked as toSplit, split it now.
322  for (auto &Pair : ToSplit) {
323  auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
324  if (NewSucc != nullptr) {
325  LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
326  << printMBBReference(*Pair.first) << " -- "
327  << printMBBReference(*NewSucc) << " -- "
328  << printMBBReference(*Pair.second) << '\n');
329  MadeChange = true;
330  ++NumSplit;
331  } else
332  LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
333  }
334  // If this iteration over the code changed anything, keep iterating.
335  if (!MadeChange) break;
336  EverMadeChange = true;
337  }
338 
339  // Now clear any kill flags for recorded registers.
340  for (auto I : RegsToClearKillFlags)
341  MRI->clearKillFlags(I);
342  RegsToClearKillFlags.clear();
343 
344  return EverMadeChange;
345 }
346 
348  // Can't sink anything out of a block that has less than two successors.
349  if (MBB.succ_size() <= 1 || MBB.empty()) return false;
350 
351  // Don't bother sinking code out of unreachable blocks. In addition to being
352  // unprofitable, it can also lead to infinite looping, because in an
353  // unreachable loop there may be nowhere to stop.
354  if (!DT->isReachableFromEntry(&MBB)) return false;
355 
356  bool MadeChange = false;
357 
358  // Cache all successors, sorted by frequency info and loop depth.
359  AllSuccsCache AllSuccessors;
360 
361  // Walk the basic block bottom-up. Remember if we saw a store.
363  --I;
364  bool ProcessedBegin, SawStore = false;
365  do {
366  MachineInstr &MI = *I; // The instruction to sink.
367 
368  // Predecrement I (if it's not begin) so that it isn't invalidated by
369  // sinking.
370  ProcessedBegin = I == MBB.begin();
371  if (!ProcessedBegin)
372  --I;
373 
374  if (MI.isDebugInstr())
375  continue;
376 
377  bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
378  if (Joined) {
379  MadeChange = true;
380  continue;
381  }
382 
383  if (SinkInstruction(MI, SawStore, AllSuccessors)) {
384  ++NumSunk;
385  MadeChange = true;
386  }
387 
388  // If we just processed the first instruction in the block, we're done.
389  } while (!ProcessedBegin);
390 
391  return MadeChange;
392 }
393 
394 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
396  MachineBasicBlock *To) {
397  // FIXME: Need much better heuristics.
398 
399  // If the pass has already considered breaking this edge (during this pass
400  // through the function), then let's go ahead and break it. This means
401  // sinking multiple "cheap" instructions into the same block.
402  if (!CEBCandidates.insert(std::make_pair(From, To)).second)
403  return true;
404 
405  if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
406  return true;
407 
408  if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
410  return true;
411 
412  // MI is cheap, we probably don't want to break the critical edge for it.
413  // However, if this would allow some definitions of its source operands
414  // to be sunk then it's probably worth it.
415  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
416  const MachineOperand &MO = MI.getOperand(i);
417  if (!MO.isReg() || !MO.isUse())
418  continue;
419  unsigned Reg = MO.getReg();
420  if (Reg == 0)
421  continue;
422 
423  // We don't move live definitions of physical registers,
424  // so sinking their uses won't enable any opportunities.
426  continue;
427 
428  // If this instruction is the only user of a virtual register,
429  // check if breaking the edge will enable sinking
430  // both this instruction and the defining instruction.
431  if (MRI->hasOneNonDBGUse(Reg)) {
432  // If the definition resides in same MBB,
433  // claim it's likely we can sink these together.
434  // If definition resides elsewhere, we aren't
435  // blocking it from being sunk so don't break the edge.
436  MachineInstr *DefMI = MRI->getVRegDef(Reg);
437  if (DefMI->getParent() == MI.getParent())
438  return true;
439  }
440  }
441 
442  return false;
443 }
444 
445 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
446  MachineBasicBlock *FromBB,
447  MachineBasicBlock *ToBB,
448  bool BreakPHIEdge) {
449  if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
450  return false;
451 
452  // Avoid breaking back edge. From == To means backedge for single BB loop.
453  if (!SplitEdges || FromBB == ToBB)
454  return false;
455 
456  // Check for backedges of more "complex" loops.
457  if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
458  LI->isLoopHeader(ToBB))
459  return false;
460 
461  // It's not always legal to break critical edges and sink the computation
462  // to the edge.
463  //
464  // %bb.1:
465  // v1024
466  // Beq %bb.3
467  // <fallthrough>
468  // %bb.2:
469  // ... no uses of v1024
470  // <fallthrough>
471  // %bb.3:
472  // ...
473  // = v1024
474  //
475  // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
476  //
477  // %bb.1:
478  // ...
479  // Bne %bb.2
480  // %bb.4:
481  // v1024 =
482  // B %bb.3
483  // %bb.2:
484  // ... no uses of v1024
485  // <fallthrough>
486  // %bb.3:
487  // ...
488  // = v1024
489  //
490  // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
491  // flow. We need to ensure the new basic block where the computation is
492  // sunk to dominates all the uses.
493  // It's only legal to break critical edge and sink the computation to the
494  // new block if all the predecessors of "To", except for "From", are
495  // not dominated by "From". Given SSA property, this means these
496  // predecessors are dominated by "To".
497  //
498  // There is no need to do this check if all the uses are PHI nodes. PHI
499  // sources are only defined on the specific predecessor edges.
500  if (!BreakPHIEdge) {
502  E = ToBB->pred_end(); PI != E; ++PI) {
503  if (*PI == FromBB)
504  continue;
505  if (!DT->dominates(ToBB, *PI))
506  return false;
507  }
508  }
509 
510  ToSplit.insert(std::make_pair(FromBB, ToBB));
511 
512  return true;
513 }
514 
515 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
516 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
517  MachineBasicBlock *MBB,
518  MachineBasicBlock *SuccToSinkTo,
519  AllSuccsCache &AllSuccessors) {
520  assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
521 
522  if (MBB == SuccToSinkTo)
523  return false;
524 
525  // It is profitable if SuccToSinkTo does not post dominate current block.
526  if (!PDT->dominates(SuccToSinkTo, MBB))
527  return true;
528 
529  // It is profitable to sink an instruction from a deeper loop to a shallower
530  // loop, even if the latter post-dominates the former (PR21115).
531  if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
532  return true;
533 
534  // Check if only use in post dominated block is PHI instruction.
535  bool NonPHIUse = false;
536  for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
537  MachineBasicBlock *UseBlock = UseInst.getParent();
538  if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
539  NonPHIUse = true;
540  }
541  if (!NonPHIUse)
542  return true;
543 
544  // If SuccToSinkTo post dominates then also it may be profitable if MI
545  // can further profitably sinked into another block in next round.
546  bool BreakPHIEdge = false;
547  // FIXME - If finding successor is compile time expensive then cache results.
548  if (MachineBasicBlock *MBB2 =
549  FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
550  return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
551 
552  // If SuccToSinkTo is final destination and it is a post dominator of current
553  // block then it is not profitable to sink MI into SuccToSinkTo block.
554  return false;
555 }
556 
557 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
558 /// computing it if it was not already cached.
560 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
561  AllSuccsCache &AllSuccessors) const {
562  // Do we have the sorted successors in cache ?
563  auto Succs = AllSuccessors.find(MBB);
564  if (Succs != AllSuccessors.end())
565  return Succs->second;
566 
568  MBB->succ_end());
569 
570  // Handle cases where sinking can happen but where the sink point isn't a
571  // successor. For example:
572  //
573  // x = computation
574  // if () {} else {}
575  // use x
576  //
577  const std::vector<MachineDomTreeNode *> &Children =
578  DT->getNode(MBB)->getChildren();
579  for (const auto &DTChild : Children)
580  // DomTree children of MBB that have MBB as immediate dominator are added.
581  if (DTChild->getIDom()->getBlock() == MI.getParent() &&
582  // Skip MBBs already added to the AllSuccs vector above.
583  !MBB->isSuccessor(DTChild->getBlock()))
584  AllSuccs.push_back(DTChild->getBlock());
585 
586  // Sort Successors according to their loop depth or block frequency info.
588  AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
589  uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
590  uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
591  bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
592  return HasBlockFreq ? LHSFreq < RHSFreq
593  : LI->getLoopDepth(L) < LI->getLoopDepth(R);
594  });
595 
596  auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
597 
598  return it.first->second;
599 }
600 
601 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
603 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
604  bool &BreakPHIEdge,
605  AllSuccsCache &AllSuccessors) {
606  assert (MBB && "Invalid MachineBasicBlock!");
607 
608  // Loop over all the operands of the specified instruction. If there is
609  // anything we can't handle, bail out.
610 
611  // SuccToSinkTo - This is the successor to sink this instruction to, once we
612  // decide.
613  MachineBasicBlock *SuccToSinkTo = nullptr;
614  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
615  const MachineOperand &MO = MI.getOperand(i);
616  if (!MO.isReg()) continue; // Ignore non-register operands.
617 
618  unsigned Reg = MO.getReg();
619  if (Reg == 0) continue;
620 
622  if (MO.isUse()) {
623  // If the physreg has no defs anywhere, it's just an ambient register
624  // and we can freely move its uses. Alternatively, if it's allocatable,
625  // it could get allocated to something with a def during allocation.
626  if (!MRI->isConstantPhysReg(Reg))
627  return nullptr;
628  } else if (!MO.isDead()) {
629  // A def that isn't dead. We can't move it.
630  return nullptr;
631  }
632  } else {
633  // Virtual register uses are always safe to sink.
634  if (MO.isUse()) continue;
635 
636  // If it's not safe to move defs of the register class, then abort.
637  if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
638  return nullptr;
639 
640  // Virtual register defs can only be sunk if all their uses are in blocks
641  // dominated by one of the successors.
642  if (SuccToSinkTo) {
643  // If a previous operand picked a block to sink to, then this operand
644  // must be sinkable to the same block.
645  bool LocalUse = false;
646  if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
647  BreakPHIEdge, LocalUse))
648  return nullptr;
649 
650  continue;
651  }
652 
653  // Otherwise, we should look at all the successors and decide which one
654  // we should sink to. If we have reliable block frequency information
655  // (frequency != 0) available, give successors with smaller frequencies
656  // higher priority, otherwise prioritize smaller loop depths.
657  for (MachineBasicBlock *SuccBlock :
658  GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
659  bool LocalUse = false;
660  if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
661  BreakPHIEdge, LocalUse)) {
662  SuccToSinkTo = SuccBlock;
663  break;
664  }
665  if (LocalUse)
666  // Def is used locally, it's never safe to move this def.
667  return nullptr;
668  }
669 
670  // If we couldn't find a block to sink to, ignore this instruction.
671  if (!SuccToSinkTo)
672  return nullptr;
673  if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
674  return nullptr;
675  }
676  }
677 
678  // It is not possible to sink an instruction into its own block. This can
679  // happen with loops.
680  if (MBB == SuccToSinkTo)
681  return nullptr;
682 
683  // It's not safe to sink instructions to EH landing pad. Control flow into
684  // landing pad is implicitly defined.
685  if (SuccToSinkTo && SuccToSinkTo->isEHPad())
686  return nullptr;
687 
688  return SuccToSinkTo;
689 }
690 
691 /// Return true if MI is likely to be usable as a memory operation by the
692 /// implicit null check optimization.
693 ///
694 /// This is a "best effort" heuristic, and should not be relied upon for
695 /// correctness. This returning true does not guarantee that the implicit null
696 /// check optimization is legal over MI, and this returning false does not
697 /// guarantee MI cannot possibly be used to do a null check.
699  const TargetInstrInfo *TII,
700  const TargetRegisterInfo *TRI) {
701  using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
702 
703  auto *MBB = MI.getParent();
704  if (MBB->pred_size() != 1)
705  return false;
706 
707  auto *PredMBB = *MBB->pred_begin();
708  auto *PredBB = PredMBB->getBasicBlock();
709 
710  // Frontends that don't use implicit null checks have no reason to emit
711  // branches with make.implicit metadata, and this function should always
712  // return false for them.
713  if (!PredBB ||
714  !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
715  return false;
716 
717  const MachineOperand *BaseOp;
718  int64_t Offset;
719  if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI))
720  return false;
721 
722  if (!BaseOp->isReg())
723  return false;
724 
725  if (!(MI.mayLoad() && !MI.isPredicable()))
726  return false;
727 
728  MachineBranchPredicate MBP;
729  if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
730  return false;
731 
732  return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
733  (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
734  MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
735  MBP.LHS.getReg() == BaseOp->getReg();
736 }
737 
738 /// Sink an instruction and its associated debug instructions. If the debug
739 /// instructions to be sunk are already known, they can be provided in DbgVals.
740 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
741  MachineBasicBlock::iterator InsertPos,
742  SmallVectorImpl<MachineInstr *> *DbgVals = nullptr) {
743  // If debug values are provided use those, otherwise call collectDebugValues.
744  SmallVector<MachineInstr *, 2> DbgValuesToSink;
745  if (DbgVals)
746  DbgValuesToSink.insert(DbgValuesToSink.begin(),
747  DbgVals->begin(), DbgVals->end());
748  else
749  MI.collectDebugValues(DbgValuesToSink);
750 
751  // If we cannot find a location to use (merge with), then we erase the debug
752  // location to prevent debug-info driven tools from potentially reporting
753  // wrong location information.
754  if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
756  InsertPos->getDebugLoc()));
757  else
758  MI.setDebugLoc(DebugLoc());
759 
760  // Move the instruction.
761  MachineBasicBlock *ParentBlock = MI.getParent();
762  SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
764 
765  // Move previously adjacent debug value instructions to the insert position.
766  for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
767  DBE = DbgValuesToSink.end();
768  DBI != DBE; ++DBI) {
769  MachineInstr *DbgMI = *DBI;
770  SuccToSinkTo.splice(InsertPos, ParentBlock, DbgMI,
771  ++MachineBasicBlock::iterator(DbgMI));
772  }
773 }
774 
775 /// SinkInstruction - Determine whether it is safe to sink the specified machine
776 /// instruction out of its current block into a successor.
777 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
778  AllSuccsCache &AllSuccessors) {
779  // Don't sink instructions that the target prefers not to sink.
780  if (!TII->shouldSink(MI))
781  return false;
782 
783  // Check if it's safe to move the instruction.
784  if (!MI.isSafeToMove(AA, SawStore))
785  return false;
786 
787  // Convergent operations may not be made control-dependent on additional
788  // values.
789  if (MI.isConvergent())
790  return false;
791 
792  // Don't break implicit null checks. This is a performance heuristic, and not
793  // required for correctness.
794  if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
795  return false;
796 
797  // FIXME: This should include support for sinking instructions within the
798  // block they are currently in to shorten the live ranges. We often get
799  // instructions sunk into the top of a large block, but it would be better to
800  // also sink them down before their first use in the block. This xform has to
801  // be careful not to *increase* register pressure though, e.g. sinking
802  // "x = y + z" down if it kills y and z would increase the live ranges of y
803  // and z and only shrink the live range of x.
804 
805  bool BreakPHIEdge = false;
806  MachineBasicBlock *ParentBlock = MI.getParent();
807  MachineBasicBlock *SuccToSinkTo =
808  FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
809 
810  // If there are no outputs, it must have side-effects.
811  if (!SuccToSinkTo)
812  return false;
813 
814  // If the instruction to move defines a dead physical register which is live
815  // when leaving the basic block, don't move it because it could turn into a
816  // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
817  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
818  const MachineOperand &MO = MI.getOperand(I);
819  if (!MO.isReg()) continue;
820  unsigned Reg = MO.getReg();
821  if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
822  if (SuccToSinkTo->isLiveIn(Reg))
823  return false;
824  }
825 
826  LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
827 
828  // If the block has multiple predecessors, this is a critical edge.
829  // Decide if we can sink along it or need to break the edge.
830  if (SuccToSinkTo->pred_size() > 1) {
831  // We cannot sink a load across a critical edge - there may be stores in
832  // other code paths.
833  bool TryBreak = false;
834  bool store = true;
835  if (!MI.isSafeToMove(AA, store)) {
836  LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
837  TryBreak = true;
838  }
839 
840  // We don't want to sink across a critical edge if we don't dominate the
841  // successor. We could be introducing calculations to new code paths.
842  if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
843  LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
844  TryBreak = true;
845  }
846 
847  // Don't sink instructions into a loop.
848  if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
849  LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
850  TryBreak = true;
851  }
852 
853  // Otherwise we are OK with sinking along a critical edge.
854  if (!TryBreak)
855  LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
856  else {
857  // Mark this edge as to be split.
858  // If the edge can actually be split, the next iteration of the main loop
859  // will sink MI in the newly created block.
860  bool Status =
861  PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
862  if (!Status)
863  LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
864  "break critical edge\n");
865  // The instruction will not be sunk this time.
866  return false;
867  }
868  }
869 
870  if (BreakPHIEdge) {
871  // BreakPHIEdge is true if all the uses are in the successor MBB being
872  // sunken into and they are all PHI nodes. In this case, machine-sink must
873  // break the critical edge first.
874  bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
875  SuccToSinkTo, BreakPHIEdge);
876  if (!Status)
877  LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
878  "break critical edge\n");
879  // The instruction will not be sunk this time.
880  return false;
881  }
882 
883  // Determine where to insert into. Skip phi nodes.
884  MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
885  while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
886  ++InsertPos;
887 
888  performSink(MI, *SuccToSinkTo, InsertPos);
889 
890  // Conservatively, clear any kill flags, since it's possible that they are no
891  // longer correct.
892  // Note that we have to clear the kill flags for any register this instruction
893  // uses as we may sink over another instruction which currently kills the
894  // used registers.
895  for (MachineOperand &MO : MI.operands()) {
896  if (MO.isReg() && MO.isUse())
897  RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
898  }
899 
900  return true;
901 }
902 
903 //===----------------------------------------------------------------------===//
904 // This pass is not intended to be a replacement or a complete alternative
905 // for the pre-ra machine sink pass. It is only designed to sink COPY
906 // instructions which should be handled after RA.
907 //
908 // This pass sinks COPY instructions into a successor block, if the COPY is not
909 // used in the current block and the COPY is live-in to a single successor
910 // (i.e., doesn't require the COPY to be duplicated). This avoids executing the
911 // copy on paths where their results aren't needed. This also exposes
912 // additional opportunites for dead copy elimination and shrink wrapping.
913 //
914 // These copies were either not handled by or are inserted after the MachineSink
915 // pass. As an example of the former case, the MachineSink pass cannot sink
916 // COPY instructions with allocatable source registers; for AArch64 these type
917 // of copy instructions are frequently used to move function parameters (PhyReg)
918 // into virtual registers in the entry block.
919 //
920 // For the machine IR below, this pass will sink %w19 in the entry into its
921 // successor (%bb.1) because %w19 is only live-in in %bb.1.
922 // %bb.0:
923 // %wzr = SUBSWri %w1, 1
924 // %w19 = COPY %w0
925 // Bcc 11, %bb.2
926 // %bb.1:
927 // Live Ins: %w19
928 // BL @fun
929 // %w0 = ADDWrr %w0, %w19
930 // RET %w0
931 // %bb.2:
932 // %w0 = COPY %wzr
933 // RET %w0
934 // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
935 // able to see %bb.0 as a candidate.
936 //===----------------------------------------------------------------------===//
937 namespace {
938 
939 class PostRAMachineSinking : public MachineFunctionPass {
940 public:
941  bool runOnMachineFunction(MachineFunction &MF) override;
942 
943  static char ID;
944  PostRAMachineSinking() : MachineFunctionPass(ID) {}
945  StringRef getPassName() const override { return "PostRA Machine Sink"; }
946 
947  void getAnalysisUsage(AnalysisUsage &AU) const override {
948  AU.setPreservesCFG();
950  }
951 
952  MachineFunctionProperties getRequiredProperties() const override {
955  }
956 
957 private:
958  /// Track which register units have been modified and used.
959  LiveRegUnits ModifiedRegUnits, UsedRegUnits;
960 
961  /// Track DBG_VALUEs of (unmodified) register units.
963 
964  /// Sink Copy instructions unused in the same block close to their uses in
965  /// successors.
966  bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
967  const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
968 };
969 } // namespace
970 
971 char PostRAMachineSinking::ID = 0;
973 
974 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
975  "PostRA Machine Sink", false, false)
976 
977 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
979  LiveRegUnits LiveInRegUnits(*TRI);
980  LiveInRegUnits.addLiveIns(MBB);
981  return !LiveInRegUnits.available(Reg);
982 }
983 
984 static MachineBasicBlock *
986  const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
987  unsigned Reg, const TargetRegisterInfo *TRI) {
988  // Try to find a single sinkable successor in which Reg is live-in.
989  MachineBasicBlock *BB = nullptr;
990  for (auto *SI : SinkableBBs) {
991  if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
992  // If BB is set here, Reg is live-in to at least two sinkable successors,
993  // so quit.
994  if (BB)
995  return nullptr;
996  BB = SI;
997  }
998  }
999  // Reg is not live-in to any sinkable successors.
1000  if (!BB)
1001  return nullptr;
1002 
1003  // Check if any register aliased with Reg is live-in in other successors.
1004  for (auto *SI : CurBB.successors()) {
1005  if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1006  return nullptr;
1007  }
1008  return BB;
1009 }
1010 
1011 static MachineBasicBlock *
1013  const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1014  ArrayRef<unsigned> DefedRegsInCopy,
1015  const TargetRegisterInfo *TRI) {
1016  MachineBasicBlock *SingleBB = nullptr;
1017  for (auto DefReg : DefedRegsInCopy) {
1018  MachineBasicBlock *BB =
1019  getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1020  if (!BB || (SingleBB && SingleBB != BB))
1021  return nullptr;
1022  SingleBB = BB;
1023  }
1024  return SingleBB;
1025 }
1026 
1028  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1029  LiveRegUnits &UsedRegUnits,
1030  const TargetRegisterInfo *TRI) {
1031  for (auto U : UsedOpsInCopy) {
1032  MachineOperand &MO = MI->getOperand(U);
1033  unsigned SrcReg = MO.getReg();
1034  if (!UsedRegUnits.available(SrcReg)) {
1035  MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1036  for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1037  if (UI.killsRegister(SrcReg, TRI)) {
1038  UI.clearRegisterKills(SrcReg, TRI);
1039  MO.setIsKill(true);
1040  break;
1041  }
1042  }
1043  }
1044  }
1045 }
1046 
1048  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1049  SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1050  MachineFunction &MF = *SuccBB->getParent();
1051  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1052  for (unsigned DefReg : DefedRegsInCopy)
1053  for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S)
1054  SuccBB->removeLiveIn(*S);
1055  for (auto U : UsedOpsInCopy) {
1056  unsigned Reg = MI->getOperand(U).getReg();
1057  if (!SuccBB->isLiveIn(Reg))
1058  SuccBB->addLiveIn(Reg);
1059  }
1060 }
1061 
1063  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1064  SmallVectorImpl<unsigned> &DefedRegsInCopy,
1065  LiveRegUnits &ModifiedRegUnits,
1066  LiveRegUnits &UsedRegUnits) {
1067  bool HasRegDependency = false;
1068  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1069  MachineOperand &MO = MI->getOperand(i);
1070  if (!MO.isReg())
1071  continue;
1072  unsigned Reg = MO.getReg();
1073  if (!Reg)
1074  continue;
1075  if (MO.isDef()) {
1076  if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1077  HasRegDependency = true;
1078  break;
1079  }
1080  DefedRegsInCopy.push_back(Reg);
1081 
1082  // FIXME: instead of isUse(), readsReg() would be a better fix here,
1083  // For example, we can ignore modifications in reg with undef. However,
1084  // it's not perfectly clear if skipping the internal read is safe in all
1085  // other targets.
1086  } else if (MO.isUse()) {
1087  if (!ModifiedRegUnits.available(Reg)) {
1088  HasRegDependency = true;
1089  break;
1090  }
1091  UsedOpsInCopy.push_back(i);
1092  }
1093  }
1094  return HasRegDependency;
1095 }
1096 
1097 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1098  MachineFunction &MF,
1099  const TargetRegisterInfo *TRI,
1100  const TargetInstrInfo *TII) {
1102  // FIXME: For now, we sink only to a successor which has a single predecessor
1103  // so that we can directly sink COPY instructions to the successor without
1104  // adding any new block or branch instruction.
1105  for (MachineBasicBlock *SI : CurBB.successors())
1106  if (!SI->livein_empty() && SI->pred_size() == 1)
1107  SinkableBBs.insert(SI);
1108 
1109  if (SinkableBBs.empty())
1110  return false;
1111 
1112  bool Changed = false;
1113 
1114  // Track which registers have been modified and used between the end of the
1115  // block and the current instruction.
1116  ModifiedRegUnits.clear();
1117  UsedRegUnits.clear();
1118  SeenDbgInstrs.clear();
1119 
1120  for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
1121  MachineInstr *MI = &*I;
1122  ++I;
1123 
1124  // Track the operand index for use in Copy.
1125  SmallVector<unsigned, 2> UsedOpsInCopy;
1126  // Track the register number defed in Copy.
1127  SmallVector<unsigned, 2> DefedRegsInCopy;
1128 
1129  // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
1130  // for DBG_VALUEs later, record them when they're encountered.
1131  if (MI->isDebugValue()) {
1132  auto &MO = MI->getOperand(0);
1133  if (MO.isReg() && TRI->isPhysicalRegister(MO.getReg())) {
1134  // Bail if we can already tell the sink would be rejected, rather
1135  // than needlessly accumulating lots of DBG_VALUEs.
1136  if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1137  ModifiedRegUnits, UsedRegUnits))
1138  continue;
1139 
1140  // Record debug use of this register.
1141  SeenDbgInstrs[MO.getReg()].push_back(MI);
1142  }
1143  continue;
1144  }
1145 
1146  if (MI->isDebugInstr())
1147  continue;
1148 
1149  // Do not move any instruction across function call.
1150  if (MI->isCall())
1151  return false;
1152 
1153  if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
1154  LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1155  TRI);
1156  continue;
1157  }
1158 
1159  // Don't sink the COPY if it would violate a register dependency.
1160  if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1161  ModifiedRegUnits, UsedRegUnits)) {
1162  LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1163  TRI);
1164  continue;
1165  }
1166  assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1167  "Unexpect SrcReg or DefReg");
1168  MachineBasicBlock *SuccBB =
1169  getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
1170  // Don't sink if we cannot find a single sinkable successor in which Reg
1171  // is live-in.
1172  if (!SuccBB) {
1173  LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1174  TRI);
1175  continue;
1176  }
1177  assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1178  "Unexpected predecessor");
1179 
1180  // Collect DBG_VALUEs that must sink with this copy.
1181  SmallVector<MachineInstr *, 4> DbgValsToSink;
1182  for (auto &MO : MI->operands()) {
1183  if (!MO.isReg() || !MO.isDef())
1184  continue;
1185  unsigned reg = MO.getReg();
1186  for (auto *MI : SeenDbgInstrs.lookup(reg))
1187  DbgValsToSink.push_back(MI);
1188  }
1189 
1190  // Clear the kill flag if SrcReg is killed between MI and the end of the
1191  // block.
1192  clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
1193  MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
1194  performSink(*MI, *SuccBB, InsertPos, &DbgValsToSink);
1195  updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
1196 
1197  Changed = true;
1198  ++NumPostRACopySink;
1199  }
1200  return Changed;
1201 }
1202 
1203 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1204  if (skipFunction(MF.getFunction()))
1205  return false;
1206 
1207  bool Changed = false;
1208  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1209  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
1210 
1211  ModifiedRegUnits.init(*TRI);
1212  UsedRegUnits.init(*TRI);
1213  for (auto &BB : MF)
1214  Changed |= tryToSinkCopy(BB, MF, TRI, TII);
1215 
1216  return Changed;
1217 }
INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE, "Machine code sinking", false, false) INITIALIZE_PASS_END(MachineSinking
static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void collectDebugValues(SmallVectorImpl< MachineInstr *> &DbgValues)
Scan instructions following MI and collect any matching DBG_VALUEs.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool use_nodbg_empty(unsigned RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register...
static bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB, DominatorTree &DT)
AllUsesDominatedByBlock - Return true if all uses of the specified value occur in blocks dominated by...
Definition: Sink.cpp:36
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:635
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
MachineBasicBlock * getMBB() const
virtual bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const
Return true if it&#39;s safe to move a machine instruction that defines the specified register class...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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...
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
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void set(unsigned Idx)
void push_back(const T &Elt)
Definition: SmallVector.h:211
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:385
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
bool isPredicable(QueryType Type=AllInBundle) const
Return true if this instruction has a predicate operand that controls execution.
Definition: MachineInstr.h:689
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:33
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:461
bool isCopyLike() const
Return true if the instruction behaves like a copy.
bool isPHI() const
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
Represents a predicate at the MachineFunction level.
iterator_range< succ_iterator > successors()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
void clear()
Definition: SmallSet.h:218
void clearKillFlags(unsigned Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:117
const std::vector< DomTreeNodeBase * > & getChildren() const
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:365
virtual const TargetInstrInfo * getInstrInfo() const
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:198
reverse_iterator rend()
reverse_iterator rbegin()
TargetInstrInfo - Interface to description of machine instruction set.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
unsigned const MachineRegisterInfo * MRI
INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink", "PostRA Machine Sink", false, false) static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
char & PostRAMachineSinkingID
This pass perform post-ra machine sink for COPY instructions.
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:370
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Represent the analysis usage information of a pass.
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:138
self_iterator getIterator()
Definition: ilist_node.h:81
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
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)
virtual bool shouldSink(const MachineInstr &MI) const
Return true if the instruction should be sunk by MachineSink.
std::vector< MachineBasicBlock * >::iterator pred_iterator
bool isCopy() const
bool isConvergent(QueryType Type=AnyInBundle) const
Return true if this instruction is convergent.
Definition: MachineInstr.h:732
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...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
MCSubRegIterator enumerates all sub-registers of Reg.
bool isDebugInstr() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool isConstantPhysReg(unsigned PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
void setIsKill(bool Val=true)
virtual bool isAsCheapAsAMove(const MachineInstr &MI) const
Return true if the instruction is as cheap as a move instruction.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
virtual bool getMemOperandWithOffset(const MachineInstr &MI, const MachineOperand *&BaseOp, int64_t &Offset, const TargetRegisterInfo *TRI) const
Get the base operand and byte offset of an instruction that reads/writes memory.
Machine code sinking
#define DEBUG_TYPE
Definition: MachineSink.cpp:55
static cl::opt< bool > UseBlockFreqInfo("machine-sink-bfi", cl::desc("Use block frequency info to find successors to sink"), cl::init(true), cl::Hidden)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool isDebugValue() const
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
char & MachineSinkingID
MachineSinking - This pass performs sinking on machine instructions.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineInstrBuilder MachineInstrBuilder & DefMI
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
unsigned pred_size() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
void clear()
Completely clear the SetVector.
Definition: SetVector.h:215
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
bool isRenamable() const
isRenamable - Returns true if this register may be renamed, i.e.
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:467
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
unsigned succ_size() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
static MachineBasicBlock * getSingleLiveInSuccBB(MachineBasicBlock &CurBB, const SmallPtrSetImpl< MachineBasicBlock *> &SinkableBBs, unsigned Reg, const TargetRegisterInfo *TRI)
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Representation of each machine instruction.
Definition: MachineInstr.h:64
static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy)
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
virtual bool analyzeBranchPredicate(MachineBasicBlock &MBB, MachineBranchPredicate &MBP, bool AllowModify=false) const
Analyze the branching code at the end of MBB and parse it into the MachineBranchPredicate structure i...
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
void initializeMachineSinkingPass(PassRegistry &)
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register...
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isReachableFromEntry(const MachineBasicBlock *A)
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
static bool hasRegisterDependency(MachineInstr *MI, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits)
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:809
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static cl::opt< bool > SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden)
void stable_sort(R &&Range)
Definition: STLExtras.h:1316
aarch64 promote const
bool isLoopHeader(const MachineBasicBlock *BB) const
True if the block is a loop header node.
A vector that has set insertion semantics.
Definition: SetVector.h:40
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, MachineBasicBlock::iterator InsertPos, SmallVectorImpl< MachineInstr *> *DbgVals=nullptr)
Sink an instruction and its associated debug instructions.
Register getReg() const
getReg - Returns the register number.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool isSafeToMove(AliasAnalysis *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
Properties which a MachineFunction may have at a given point in time.