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