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"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/MC/MCRegisterInfo.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  Register SrcReg = MI.getOperand(1).getReg();
200  Register DstReg = MI.getOperand(0).getReg();
201  if (!Register::isVirtualRegister(SrcReg) ||
202  !Register::isVirtualRegister(DstReg) || !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 {
236  assert(Register::isVirtualRegister(Reg) && "Only makes sense for vregs");
237 
238  // Ignore debug uses because debug info doesn't affect the code.
239  if (MRI->use_nodbg_empty(Reg))
240  return true;
241 
242  // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
243  // into and they are all PHI nodes. In this case, machine-sink must break
244  // the critical edge first. e.g.
245  //
246  // %bb.1: derived from LLVM BB %bb4.preheader
247  // Predecessors according to CFG: %bb.0
248  // ...
249  // %reg16385 = DEC64_32r %reg16437, implicit-def dead %eflags
250  // ...
251  // JE_4 <%bb.37>, implicit %eflags
252  // Successors according to CFG: %bb.37 %bb.2
253  //
254  // %bb.2: derived from LLVM BB %bb.nph
255  // Predecessors according to CFG: %bb.0 %bb.1
256  // %reg16386 = PHI %reg16434, %bb.0, %reg16385, %bb.1
257  BreakPHIEdge = true;
258  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
259  MachineInstr *UseInst = MO.getParent();
260  unsigned OpNo = &MO - &UseInst->getOperand(0);
261  MachineBasicBlock *UseBlock = UseInst->getParent();
262  if (!(UseBlock == MBB && UseInst->isPHI() &&
263  UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
264  BreakPHIEdge = false;
265  break;
266  }
267  }
268  if (BreakPHIEdge)
269  return true;
270 
271  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
272  // Determine the block of the use.
273  MachineInstr *UseInst = MO.getParent();
274  unsigned OpNo = &MO - &UseInst->getOperand(0);
275  MachineBasicBlock *UseBlock = UseInst->getParent();
276  if (UseInst->isPHI()) {
277  // PHI nodes use the operand in the predecessor block, not the block with
278  // the PHI.
279  UseBlock = UseInst->getOperand(OpNo+1).getMBB();
280  } else if (UseBlock == DefMBB) {
281  LocalUse = true;
282  return false;
283  }
284 
285  // Check that it dominates.
286  if (!DT->dominates(MBB, UseBlock))
287  return false;
288  }
289 
290  return true;
291 }
292 
293 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
294  if (skipFunction(MF.getFunction()))
295  return false;
296 
297  LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
298 
299  TII = MF.getSubtarget().getInstrInfo();
300  TRI = MF.getSubtarget().getRegisterInfo();
301  MRI = &MF.getRegInfo();
302  DT = &getAnalysis<MachineDominatorTree>();
303  PDT = &getAnalysis<MachinePostDominatorTree>();
304  LI = &getAnalysis<MachineLoopInfo>();
305  MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
306  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
307  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
308 
309  bool EverMadeChange = false;
310 
311  while (true) {
312  bool MadeChange = false;
313 
314  // Process all basic blocks.
315  CEBCandidates.clear();
316  ToSplit.clear();
317  for (auto &MBB: MF)
318  MadeChange |= ProcessBlock(MBB);
319 
320  // If we have anything we marked as toSplit, split it now.
321  for (auto &Pair : ToSplit) {
322  auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
323  if (NewSucc != nullptr) {
324  LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
325  << printMBBReference(*Pair.first) << " -- "
326  << printMBBReference(*NewSucc) << " -- "
327  << printMBBReference(*Pair.second) << '\n');
328  MadeChange = true;
329  ++NumSplit;
330  } else
331  LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
332  }
333  // If this iteration over the code changed anything, keep iterating.
334  if (!MadeChange) break;
335  EverMadeChange = true;
336  }
337 
338  // Now clear any kill flags for recorded registers.
339  for (auto I : RegsToClearKillFlags)
340  MRI->clearKillFlags(I);
341  RegsToClearKillFlags.clear();
342 
343  return EverMadeChange;
344 }
345 
347  // Can't sink anything out of a block that has less than two successors.
348  if (MBB.succ_size() <= 1 || MBB.empty()) return false;
349 
350  // Don't bother sinking code out of unreachable blocks. In addition to being
351  // unprofitable, it can also lead to infinite looping, because in an
352  // unreachable loop there may be nowhere to stop.
353  if (!DT->isReachableFromEntry(&MBB)) return false;
354 
355  bool MadeChange = false;
356 
357  // Cache all successors, sorted by frequency info and loop depth.
358  AllSuccsCache AllSuccessors;
359 
360  // Walk the basic block bottom-up. Remember if we saw a store.
362  --I;
363  bool ProcessedBegin, SawStore = false;
364  do {
365  MachineInstr &MI = *I; // The instruction to sink.
366 
367  // Predecrement I (if it's not begin) so that it isn't invalidated by
368  // sinking.
369  ProcessedBegin = I == MBB.begin();
370  if (!ProcessedBegin)
371  --I;
372 
373  if (MI.isDebugInstr())
374  continue;
375 
376  bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
377  if (Joined) {
378  MadeChange = true;
379  continue;
380  }
381 
382  if (SinkInstruction(MI, SawStore, AllSuccessors)) {
383  ++NumSunk;
384  MadeChange = true;
385  }
386 
387  // If we just processed the first instruction in the block, we're done.
388  } while (!ProcessedBegin);
389 
390  return MadeChange;
391 }
392 
393 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
395  MachineBasicBlock *To) {
396  // FIXME: Need much better heuristics.
397 
398  // If the pass has already considered breaking this edge (during this pass
399  // through the function), then let's go ahead and break it. This means
400  // sinking multiple "cheap" instructions into the same block.
401  if (!CEBCandidates.insert(std::make_pair(From, To)).second)
402  return true;
403 
404  if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
405  return true;
406 
407  if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
409  return true;
410 
411  // MI is cheap, we probably don't want to break the critical edge for it.
412  // However, if this would allow some definitions of its source operands
413  // to be sunk then it's probably worth it.
414  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
415  const MachineOperand &MO = MI.getOperand(i);
416  if (!MO.isReg() || !MO.isUse())
417  continue;
418  Register Reg = MO.getReg();
419  if (Reg == 0)
420  continue;
421 
422  // We don't move live definitions of physical registers,
423  // so sinking their uses won't enable any opportunities.
425  continue;
426 
427  // If this instruction is the only user of a virtual register,
428  // check if breaking the edge will enable sinking
429  // both this instruction and the defining instruction.
430  if (MRI->hasOneNonDBGUse(Reg)) {
431  // If the definition resides in same MBB,
432  // claim it's likely we can sink these together.
433  // If definition resides elsewhere, we aren't
434  // blocking it from being sunk so don't break the edge.
435  MachineInstr *DefMI = MRI->getVRegDef(Reg);
436  if (DefMI->getParent() == MI.getParent())
437  return true;
438  }
439  }
440 
441  return false;
442 }
443 
444 bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
445  MachineBasicBlock *FromBB,
446  MachineBasicBlock *ToBB,
447  bool BreakPHIEdge) {
448  if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
449  return false;
450 
451  // Avoid breaking back edge. From == To means backedge for single BB loop.
452  if (!SplitEdges || FromBB == ToBB)
453  return false;
454 
455  // Check for backedges of more "complex" loops.
456  if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
457  LI->isLoopHeader(ToBB))
458  return false;
459 
460  // It's not always legal to break critical edges and sink the computation
461  // to the edge.
462  //
463  // %bb.1:
464  // v1024
465  // Beq %bb.3
466  // <fallthrough>
467  // %bb.2:
468  // ... no uses of v1024
469  // <fallthrough>
470  // %bb.3:
471  // ...
472  // = v1024
473  //
474  // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
475  //
476  // %bb.1:
477  // ...
478  // Bne %bb.2
479  // %bb.4:
480  // v1024 =
481  // B %bb.3
482  // %bb.2:
483  // ... no uses of v1024
484  // <fallthrough>
485  // %bb.3:
486  // ...
487  // = v1024
488  //
489  // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
490  // flow. We need to ensure the new basic block where the computation is
491  // sunk to dominates all the uses.
492  // It's only legal to break critical edge and sink the computation to the
493  // new block if all the predecessors of "To", except for "From", are
494  // not dominated by "From". Given SSA property, this means these
495  // predecessors are dominated by "To".
496  //
497  // There is no need to do this check if all the uses are PHI nodes. PHI
498  // sources are only defined on the specific predecessor edges.
499  if (!BreakPHIEdge) {
501  E = ToBB->pred_end(); PI != E; ++PI) {
502  if (*PI == FromBB)
503  continue;
504  if (!DT->dominates(ToBB, *PI))
505  return false;
506  }
507  }
508 
509  ToSplit.insert(std::make_pair(FromBB, ToBB));
510 
511  return true;
512 }
513 
514 /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
515 bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
516  MachineBasicBlock *MBB,
517  MachineBasicBlock *SuccToSinkTo,
518  AllSuccsCache &AllSuccessors) {
519  assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
520 
521  if (MBB == SuccToSinkTo)
522  return false;
523 
524  // It is profitable if SuccToSinkTo does not post dominate current block.
525  if (!PDT->dominates(SuccToSinkTo, MBB))
526  return true;
527 
528  // It is profitable to sink an instruction from a deeper loop to a shallower
529  // loop, even if the latter post-dominates the former (PR21115).
530  if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
531  return true;
532 
533  // Check if only use in post dominated block is PHI instruction.
534  bool NonPHIUse = false;
535  for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
536  MachineBasicBlock *UseBlock = UseInst.getParent();
537  if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
538  NonPHIUse = true;
539  }
540  if (!NonPHIUse)
541  return true;
542 
543  // If SuccToSinkTo post dominates then also it may be profitable if MI
544  // can further profitably sinked into another block in next round.
545  bool BreakPHIEdge = false;
546  // FIXME - If finding successor is compile time expensive then cache results.
547  if (MachineBasicBlock *MBB2 =
548  FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
549  return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
550 
551  // If SuccToSinkTo is final destination and it is a post dominator of current
552  // block then it is not profitable to sink MI into SuccToSinkTo block.
553  return false;
554 }
555 
556 /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
557 /// computing it if it was not already cached.
559 MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
560  AllSuccsCache &AllSuccessors) const {
561  // Do we have the sorted successors in cache ?
562  auto Succs = AllSuccessors.find(MBB);
563  if (Succs != AllSuccessors.end())
564  return Succs->second;
565 
567  MBB->succ_end());
568 
569  // Handle cases where sinking can happen but where the sink point isn't a
570  // successor. For example:
571  //
572  // x = computation
573  // if () {} else {}
574  // use x
575  //
576  const std::vector<MachineDomTreeNode *> &Children =
577  DT->getNode(MBB)->getChildren();
578  for (const auto &DTChild : Children)
579  // DomTree children of MBB that have MBB as immediate dominator are added.
580  if (DTChild->getIDom()->getBlock() == MI.getParent() &&
581  // Skip MBBs already added to the AllSuccs vector above.
582  !MBB->isSuccessor(DTChild->getBlock()))
583  AllSuccs.push_back(DTChild->getBlock());
584 
585  // Sort Successors according to their loop depth or block frequency info.
587  AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
588  uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
589  uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
590  bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
591  return HasBlockFreq ? LHSFreq < RHSFreq
592  : LI->getLoopDepth(L) < LI->getLoopDepth(R);
593  });
594 
595  auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
596 
597  return it.first->second;
598 }
599 
600 /// FindSuccToSinkTo - Find a successor to sink this instruction to.
602 MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
603  bool &BreakPHIEdge,
604  AllSuccsCache &AllSuccessors) {
605  assert (MBB && "Invalid MachineBasicBlock!");
606 
607  // Loop over all the operands of the specified instruction. If there is
608  // anything we can't handle, bail out.
609 
610  // SuccToSinkTo - This is the successor to sink this instruction to, once we
611  // decide.
612  MachineBasicBlock *SuccToSinkTo = nullptr;
613  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
614  const MachineOperand &MO = MI.getOperand(i);
615  if (!MO.isReg()) continue; // Ignore non-register operands.
616 
617  Register Reg = MO.getReg();
618  if (Reg == 0) continue;
619 
620  if (Register::isPhysicalRegister(Reg)) {
621  if (MO.isUse()) {
622  // If the physreg has no defs anywhere, it's just an ambient register
623  // and we can freely move its uses. Alternatively, if it's allocatable,
624  // it could get allocated to something with a def during allocation.
625  if (!MRI->isConstantPhysReg(Reg))
626  return nullptr;
627  } else if (!MO.isDead()) {
628  // A def that isn't dead. We can't move it.
629  return nullptr;
630  }
631  } else {
632  // Virtual register uses are always safe to sink.
633  if (MO.isUse()) continue;
634 
635  // If it's not safe to move defs of the register class, then abort.
636  if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
637  return nullptr;
638 
639  // Virtual register defs can only be sunk if all their uses are in blocks
640  // dominated by one of the successors.
641  if (SuccToSinkTo) {
642  // If a previous operand picked a block to sink to, then this operand
643  // must be sinkable to the same block.
644  bool LocalUse = false;
645  if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
646  BreakPHIEdge, LocalUse))
647  return nullptr;
648 
649  continue;
650  }
651 
652  // Otherwise, we should look at all the successors and decide which one
653  // we should sink to. If we have reliable block frequency information
654  // (frequency != 0) available, give successors with smaller frequencies
655  // higher priority, otherwise prioritize smaller loop depths.
656  for (MachineBasicBlock *SuccBlock :
657  GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
658  bool LocalUse = false;
659  if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
660  BreakPHIEdge, LocalUse)) {
661  SuccToSinkTo = SuccBlock;
662  break;
663  }
664  if (LocalUse)
665  // Def is used locally, it's never safe to move this def.
666  return nullptr;
667  }
668 
669  // If we couldn't find a block to sink to, ignore this instruction.
670  if (!SuccToSinkTo)
671  return nullptr;
672  if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
673  return nullptr;
674  }
675  }
676 
677  // It is not possible to sink an instruction into its own block. This can
678  // happen with loops.
679  if (MBB == SuccToSinkTo)
680  return nullptr;
681 
682  // It's not safe to sink instructions to EH landing pad. Control flow into
683  // landing pad is implicitly defined.
684  if (SuccToSinkTo && SuccToSinkTo->isEHPad())
685  return nullptr;
686 
687  return SuccToSinkTo;
688 }
689 
690 /// Return true if MI is likely to be usable as a memory operation by the
691 /// implicit null check optimization.
692 ///
693 /// This is a "best effort" heuristic, and should not be relied upon for
694 /// correctness. This returning true does not guarantee that the implicit null
695 /// check optimization is legal over MI, and this returning false does not
696 /// guarantee MI cannot possibly be used to do a null check.
698  const TargetInstrInfo *TII,
699  const TargetRegisterInfo *TRI) {
700  using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
701 
702  auto *MBB = MI.getParent();
703  if (MBB->pred_size() != 1)
704  return false;
705 
706  auto *PredMBB = *MBB->pred_begin();
707  auto *PredBB = PredMBB->getBasicBlock();
708 
709  // Frontends that don't use implicit null checks have no reason to emit
710  // branches with make.implicit metadata, and this function should always
711  // return false for them.
712  if (!PredBB ||
713  !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
714  return false;
715 
716  const MachineOperand *BaseOp;
717  int64_t Offset;
718  if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI))
719  return false;
720 
721  if (!BaseOp->isReg())
722  return false;
723 
724  if (!(MI.mayLoad() && !MI.isPredicable()))
725  return false;
726 
727  MachineBranchPredicate MBP;
728  if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
729  return false;
730 
731  return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
732  (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
733  MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
734  MBP.LHS.getReg() == BaseOp->getReg();
735 }
736 
737 /// Sink an instruction and its associated debug instructions. If the debug
738 /// instructions to be sunk are already known, they can be provided in DbgVals.
739 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
740  MachineBasicBlock::iterator InsertPos,
741  SmallVectorImpl<MachineInstr *> *DbgVals = nullptr) {
742  // If debug values are provided use those, otherwise call collectDebugValues.
743  SmallVector<MachineInstr *, 2> DbgValuesToSink;
744  if (DbgVals)
745  DbgValuesToSink.insert(DbgValuesToSink.begin(),
746  DbgVals->begin(), DbgVals->end());
747  else
748  MI.collectDebugValues(DbgValuesToSink);
749 
750  // If we cannot find a location to use (merge with), then we erase the debug
751  // location to prevent debug-info driven tools from potentially reporting
752  // wrong location information.
753  if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
755  InsertPos->getDebugLoc()));
756  else
757  MI.setDebugLoc(DebugLoc());
758 
759  // Move the instruction.
760  MachineBasicBlock *ParentBlock = MI.getParent();
761  SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
763 
764  // Move previously adjacent debug value instructions to the insert position.
765  for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
766  DBE = DbgValuesToSink.end();
767  DBI != DBE; ++DBI) {
768  MachineInstr *DbgMI = *DBI;
769  SuccToSinkTo.splice(InsertPos, ParentBlock, DbgMI,
770  ++MachineBasicBlock::iterator(DbgMI));
771  }
772 }
773 
774 /// SinkInstruction - Determine whether it is safe to sink the specified machine
775 /// instruction out of its current block into a successor.
776 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
777  AllSuccsCache &AllSuccessors) {
778  // Don't sink instructions that the target prefers not to sink.
779  if (!TII->shouldSink(MI))
780  return false;
781 
782  // Check if it's safe to move the instruction.
783  if (!MI.isSafeToMove(AA, SawStore))
784  return false;
785 
786  // Convergent operations may not be made control-dependent on additional
787  // values.
788  if (MI.isConvergent())
789  return false;
790 
791  // Don't break implicit null checks. This is a performance heuristic, and not
792  // required for correctness.
793  if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
794  return false;
795 
796  // FIXME: This should include support for sinking instructions within the
797  // block they are currently in to shorten the live ranges. We often get
798  // instructions sunk into the top of a large block, but it would be better to
799  // also sink them down before their first use in the block. This xform has to
800  // be careful not to *increase* register pressure though, e.g. sinking
801  // "x = y + z" down if it kills y and z would increase the live ranges of y
802  // and z and only shrink the live range of x.
803 
804  bool BreakPHIEdge = false;
805  MachineBasicBlock *ParentBlock = MI.getParent();
806  MachineBasicBlock *SuccToSinkTo =
807  FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
808 
809  // If there are no outputs, it must have side-effects.
810  if (!SuccToSinkTo)
811  return false;
812 
813  // If the instruction to move defines a dead physical register which is live
814  // when leaving the basic block, don't move it because it could turn into a
815  // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
816  for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
817  const MachineOperand &MO = MI.getOperand(I);
818  if (!MO.isReg()) continue;
819  Register Reg = MO.getReg();
820  if (Reg == 0 || !Register::isPhysicalRegister(Reg))
821  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. Each DBG_VALUE has an
962  /// entry in this map for each unit it touches.
964 
965  /// Sink Copy instructions unused in the same block close to their uses in
966  /// successors.
967  bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
968  const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
969 };
970 } // namespace
971 
972 char PostRAMachineSinking::ID = 0;
974 
975 INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
976  "PostRA Machine Sink", false, false)
977 
978 static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
980  LiveRegUnits LiveInRegUnits(*TRI);
981  LiveInRegUnits.addLiveIns(MBB);
982  return !LiveInRegUnits.available(Reg);
983 }
984 
985 static MachineBasicBlock *
987  const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
988  unsigned Reg, const TargetRegisterInfo *TRI) {
989  // Try to find a single sinkable successor in which Reg is live-in.
990  MachineBasicBlock *BB = nullptr;
991  for (auto *SI : SinkableBBs) {
992  if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
993  // If BB is set here, Reg is live-in to at least two sinkable successors,
994  // so quit.
995  if (BB)
996  return nullptr;
997  BB = SI;
998  }
999  }
1000  // Reg is not live-in to any sinkable successors.
1001  if (!BB)
1002  return nullptr;
1003 
1004  // Check if any register aliased with Reg is live-in in other successors.
1005  for (auto *SI : CurBB.successors()) {
1006  if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1007  return nullptr;
1008  }
1009  return BB;
1010 }
1011 
1012 static MachineBasicBlock *
1014  const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1015  ArrayRef<unsigned> DefedRegsInCopy,
1016  const TargetRegisterInfo *TRI) {
1017  MachineBasicBlock *SingleBB = nullptr;
1018  for (auto DefReg : DefedRegsInCopy) {
1019  MachineBasicBlock *BB =
1020  getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1021  if (!BB || (SingleBB && SingleBB != BB))
1022  return nullptr;
1023  SingleBB = BB;
1024  }
1025  return SingleBB;
1026 }
1027 
1029  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1030  LiveRegUnits &UsedRegUnits,
1031  const TargetRegisterInfo *TRI) {
1032  for (auto U : UsedOpsInCopy) {
1033  MachineOperand &MO = MI->getOperand(U);
1034  Register SrcReg = MO.getReg();
1035  if (!UsedRegUnits.available(SrcReg)) {
1036  MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1037  for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1038  if (UI.killsRegister(SrcReg, TRI)) {
1039  UI.clearRegisterKills(SrcReg, TRI);
1040  MO.setIsKill(true);
1041  break;
1042  }
1043  }
1044  }
1045  }
1046 }
1047 
1049  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1050  SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1051  MachineFunction &MF = *SuccBB->getParent();
1052  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1053  for (unsigned DefReg : DefedRegsInCopy)
1054  for (MCSubRegIterator S(DefReg, TRI, true); S.isValid(); ++S)
1055  SuccBB->removeLiveIn(*S);
1056  for (auto U : UsedOpsInCopy) {
1057  Register Reg = MI->getOperand(U).getReg();
1058  if (!SuccBB->isLiveIn(Reg))
1059  SuccBB->addLiveIn(Reg);
1060  }
1061 }
1062 
1064  SmallVectorImpl<unsigned> &UsedOpsInCopy,
1065  SmallVectorImpl<unsigned> &DefedRegsInCopy,
1066  LiveRegUnits &ModifiedRegUnits,
1067  LiveRegUnits &UsedRegUnits) {
1068  bool HasRegDependency = false;
1069  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1070  MachineOperand &MO = MI->getOperand(i);
1071  if (!MO.isReg())
1072  continue;
1073  Register Reg = MO.getReg();
1074  if (!Reg)
1075  continue;
1076  if (MO.isDef()) {
1077  if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1078  HasRegDependency = true;
1079  break;
1080  }
1081  DefedRegsInCopy.push_back(Reg);
1082 
1083  // FIXME: instead of isUse(), readsReg() would be a better fix here,
1084  // For example, we can ignore modifications in reg with undef. However,
1085  // it's not perfectly clear if skipping the internal read is safe in all
1086  // other targets.
1087  } else if (MO.isUse()) {
1088  if (!ModifiedRegUnits.available(Reg)) {
1089  HasRegDependency = true;
1090  break;
1091  }
1092  UsedOpsInCopy.push_back(i);
1093  }
1094  }
1095  return HasRegDependency;
1096 }
1097 
1099  const TargetRegisterInfo *TRI) {
1100  SmallSet<unsigned, 4> RegUnits;
1101  for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI)
1102  RegUnits.insert(*RI);
1103  return RegUnits;
1104 }
1105 
1106 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1107  MachineFunction &MF,
1108  const TargetRegisterInfo *TRI,
1109  const TargetInstrInfo *TII) {
1111  // FIXME: For now, we sink only to a successor which has a single predecessor
1112  // so that we can directly sink COPY instructions to the successor without
1113  // adding any new block or branch instruction.
1114  for (MachineBasicBlock *SI : CurBB.successors())
1115  if (!SI->livein_empty() && SI->pred_size() == 1)
1116  SinkableBBs.insert(SI);
1117 
1118  if (SinkableBBs.empty())
1119  return false;
1120 
1121  bool Changed = false;
1122 
1123  // Track which registers have been modified and used between the end of the
1124  // block and the current instruction.
1125  ModifiedRegUnits.clear();
1126  UsedRegUnits.clear();
1127  SeenDbgInstrs.clear();
1128 
1129  for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
1130  MachineInstr *MI = &*I;
1131  ++I;
1132 
1133  // Track the operand index for use in Copy.
1134  SmallVector<unsigned, 2> UsedOpsInCopy;
1135  // Track the register number defed in Copy.
1136  SmallVector<unsigned, 2> DefedRegsInCopy;
1137 
1138  // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
1139  // for DBG_VALUEs later, record them when they're encountered.
1140  if (MI->isDebugValue()) {
1141  auto &MO = MI->getOperand(0);
1142  if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) {
1143  // Bail if we can already tell the sink would be rejected, rather
1144  // than needlessly accumulating lots of DBG_VALUEs.
1145  if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1146  ModifiedRegUnits, UsedRegUnits))
1147  continue;
1148 
1149  // Record debug use of each reg unit.
1150  SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI);
1151  for (unsigned Reg : Units)
1152  SeenDbgInstrs[Reg].push_back(MI);
1153  }
1154  continue;
1155  }
1156 
1157  if (MI->isDebugInstr())
1158  continue;
1159 
1160  // Do not move any instruction across function call.
1161  if (MI->isCall())
1162  return false;
1163 
1164  if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
1165  LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1166  TRI);
1167  continue;
1168  }
1169 
1170  // Don't sink the COPY if it would violate a register dependency.
1171  if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
1172  ModifiedRegUnits, UsedRegUnits)) {
1173  LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1174  TRI);
1175  continue;
1176  }
1177  assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
1178  "Unexpect SrcReg or DefReg");
1179  MachineBasicBlock *SuccBB =
1180  getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
1181  // Don't sink if we cannot find a single sinkable successor in which Reg
1182  // is live-in.
1183  if (!SuccBB) {
1184  LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
1185  TRI);
1186  continue;
1187  }
1188  assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
1189  "Unexpected predecessor");
1190 
1191  // Collect DBG_VALUEs that must sink with this copy. We've previously
1192  // recorded which reg units that DBG_VALUEs read, if this instruction
1193  // writes any of those units then the corresponding DBG_VALUEs must sink.
1194  SetVector<MachineInstr *> DbgValsToSinkSet;
1195  SmallVector<MachineInstr *, 4> DbgValsToSink;
1196  for (auto &MO : MI->operands()) {
1197  if (!MO.isReg() || !MO.isDef())
1198  continue;
1199 
1200  SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI);
1201  for (unsigned Reg : Units)
1202  for (auto *MI : SeenDbgInstrs.lookup(Reg))
1203  DbgValsToSinkSet.insert(MI);
1204  }
1205  DbgValsToSink.insert(DbgValsToSink.begin(), DbgValsToSinkSet.begin(),
1206  DbgValsToSinkSet.end());
1207 
1208  // Clear the kill flag if SrcReg is killed between MI and the end of the
1209  // block.
1210  clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
1211  MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
1212  performSink(*MI, *SuccBB, InsertPos, &DbgValsToSink);
1213  updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
1214 
1215  Changed = true;
1216  ++NumPostRACopySink;
1217  }
1218  return Changed;
1219 }
1220 
1221 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
1222  if (skipFunction(MF.getFunction()))
1223  return false;
1224 
1225  bool Changed = false;
1226  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1227  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
1228 
1229  ModifiedRegUnits.init(*TRI);
1230  UsedRegUnits.init(*TRI);
1231  for (auto &BB : MF)
1232  Changed |= tryToSinkCopy(BB, MF, TRI, TII);
1233 
1234  return Changed;
1235 }
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:651
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...
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
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
unsigned Reg
bool isPredicable(QueryType Type=AllInBundle) const
Return true if this instruction has a predicate operand that controls execution.
Definition: MachineInstr.h:705
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:477
bool isCopyLike() const
Return true if the instruction behaves like a copy.
bool isPHI() const
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
Represents a predicate at the MachineFunction level.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
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
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
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.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:748
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: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: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
static SmallSet< unsigned, 4 > getRegUnits(unsigned Reg, const TargetRegisterInfo *TRI)
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)
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:825
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:1301
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.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
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.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19