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