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