brintos / llvm-project-archived public Read only

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-exception6//7//===----------------------------------------------------------------------===//8//9// This pass moves instructions into successor blocks when possible, so that10// 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 alternative13// for an LLVM-IR-level sinking pass. It is only designed to sink simple14// constructs that are not exposed before lowering and instruction selection.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/CodeGen/MachineSink.h"19#include "llvm/ADT/DenseSet.h"20#include "llvm/ADT/DepthFirstIterator.h"21#include "llvm/ADT/MapVector.h"22#include "llvm/ADT/PointerIntPair.h"23#include "llvm/ADT/SetVector.h"24#include "llvm/ADT/SmallSet.h"25#include "llvm/ADT/SmallVector.h"26#include "llvm/ADT/Statistic.h"27#include "llvm/Analysis/AliasAnalysis.h"28#include "llvm/Analysis/CFG.h"29#include "llvm/Analysis/ProfileSummaryInfo.h"30#include "llvm/CodeGen/LiveIntervals.h"31#include "llvm/CodeGen/LiveVariables.h"32#include "llvm/CodeGen/MachineBasicBlock.h"33#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"34#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"35#include "llvm/CodeGen/MachineCycleAnalysis.h"36#include "llvm/CodeGen/MachineDomTreeUpdater.h"37#include "llvm/CodeGen/MachineDominators.h"38#include "llvm/CodeGen/MachineFunction.h"39#include "llvm/CodeGen/MachineFunctionPass.h"40#include "llvm/CodeGen/MachineInstr.h"41#include "llvm/CodeGen/MachineLoopInfo.h"42#include "llvm/CodeGen/MachineOperand.h"43#include "llvm/CodeGen/MachinePostDominators.h"44#include "llvm/CodeGen/MachineRegisterInfo.h"45#include "llvm/CodeGen/MachineSizeOpts.h"46#include "llvm/CodeGen/PostRAMachineSink.h"47#include "llvm/CodeGen/RegisterClassInfo.h"48#include "llvm/CodeGen/RegisterPressure.h"49#include "llvm/CodeGen/SlotIndexes.h"50#include "llvm/CodeGen/TargetInstrInfo.h"51#include "llvm/CodeGen/TargetPassConfig.h"52#include "llvm/CodeGen/TargetRegisterInfo.h"53#include "llvm/CodeGen/TargetSchedule.h"54#include "llvm/CodeGen/TargetSubtargetInfo.h"55#include "llvm/IR/BasicBlock.h"56#include "llvm/IR/DebugInfoMetadata.h"57#include "llvm/IR/LLVMContext.h"58#include "llvm/InitializePasses.h"59#include "llvm/Pass.h"60#include "llvm/Support/BranchProbability.h"61#include "llvm/Support/CommandLine.h"62#include "llvm/Support/Debug.h"63#include "llvm/Support/raw_ostream.h"64#include <cassert>65#include <cstdint>66#include <utility>67#include <vector>68 69using namespace llvm;70 71#define DEBUG_TYPE "machine-sink"72 73static cl::opt<bool>74    SplitEdges("machine-sink-split",75               cl::desc("Split critical edges during machine sinking"),76               cl::init(true), cl::Hidden);77 78static cl::opt<bool> UseBlockFreqInfo(79    "machine-sink-bfi",80    cl::desc("Use block frequency info to find successors to sink"),81    cl::init(true), cl::Hidden);82 83static cl::opt<unsigned> SplitEdgeProbabilityThreshold(84    "machine-sink-split-probability-threshold",85    cl::desc(86        "Percentage threshold for splitting single-instruction critical edge. "87        "If the branch threshold is higher than this threshold, we allow "88        "speculative execution of up to 1 instruction to avoid branching to "89        "splitted critical edge"),90    cl::init(40), cl::Hidden);91 92static cl::opt<unsigned> SinkLoadInstsPerBlockThreshold(93    "machine-sink-load-instrs-threshold",94    cl::desc("Do not try to find alias store for a load if there is a in-path "95             "block whose instruction number is higher than this threshold."),96    cl::init(2000), cl::Hidden);97 98static cl::opt<unsigned> SinkLoadBlocksThreshold(99    "machine-sink-load-blocks-threshold",100    cl::desc("Do not try to find alias store for a load if the block number in "101             "the straight line is higher than this threshold."),102    cl::init(20), cl::Hidden);103 104static cl::opt<bool>105    SinkInstsIntoCycle("sink-insts-to-avoid-spills",106                       cl::desc("Sink instructions into cycles to avoid "107                                "register spills"),108                       cl::init(false), cl::Hidden);109 110static cl::opt<unsigned> SinkIntoCycleLimit(111    "machine-sink-cycle-limit",112    cl::desc(113        "The maximum number of instructions considered for cycle sinking."),114    cl::init(50), cl::Hidden);115 116STATISTIC(NumSunk, "Number of machine instructions sunk");117STATISTIC(NumCycleSunk, "Number of machine instructions sunk into a cycle");118STATISTIC(NumSplit, "Number of critical edges split");119STATISTIC(NumCoalesces, "Number of copies coalesced");120STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");121 122using RegSubRegPair = TargetInstrInfo::RegSubRegPair;123 124namespace {125 126class MachineSinking {127  const TargetSubtargetInfo *STI = nullptr;128  const TargetInstrInfo *TII = nullptr;129  const TargetRegisterInfo *TRI = nullptr;130  MachineRegisterInfo *MRI = nullptr;      // Machine register information131  MachineDominatorTree *DT = nullptr;      // Machine dominator tree132  MachinePostDominatorTree *PDT = nullptr; // Machine post dominator tree133  MachineCycleInfo *CI = nullptr;134  ProfileSummaryInfo *PSI = nullptr;135  MachineBlockFrequencyInfo *MBFI = nullptr;136  const MachineBranchProbabilityInfo *MBPI = nullptr;137  AliasAnalysis *AA = nullptr;138  RegisterClassInfo RegClassInfo;139  TargetSchedModel SchedModel;140  // Required for split critical edge141  LiveIntervals *LIS;142  SlotIndexes *SI;143  LiveVariables *LV;144  MachineLoopInfo *MLI;145 146  // Remember which edges have been considered for breaking.147  SmallSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>, 8>148      CEBCandidates;149  // Memorize the register that also wanted to sink into the same block along150  // a different critical edge.151  // {register to sink, sink-to block} -> the first sink-from block.152  // We're recording the first sink-from block because that (critical) edge153  // was deferred until we see another register that's going to sink into the154  // same block.155  DenseMap<std::pair<Register, MachineBasicBlock *>, MachineBasicBlock *>156      CEMergeCandidates;157  // Remember which edges we are about to split.158  // This is different from CEBCandidates since those edges159  // will be split.160  SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;161 162  DenseSet<Register> RegsToClearKillFlags;163 164  using AllSuccsCache =165      SmallDenseMap<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;166 167  /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is168  /// post-dominated by another DBG_VALUE of the same variable location.169  /// This is necessary to detect sequences such as:170  ///     %0 = someinst171  ///     DBG_VALUE %0, !123, !DIExpression()172  ///     %1 = anotherinst173  ///     DBG_VALUE %1, !123, !DIExpression()174  /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that175  /// would re-order assignments.176  using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;177 178  using SinkItem = std::pair<MachineInstr *, MachineBasicBlock *>;179 180  /// Record of DBG_VALUE uses of vregs in a block, so that we can identify181  /// debug instructions to sink.182  SmallDenseMap<Register, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;183 184  /// Record of debug variables that have had their locations set in the185  /// current block.186  DenseSet<DebugVariable> SeenDbgVars;187 188  DenseMap<std::pair<MachineBasicBlock *, MachineBasicBlock *>, bool>189      HasStoreCache;190 191  DenseMap<std::pair<MachineBasicBlock *, MachineBasicBlock *>,192           SmallVector<MachineInstr *>>193      StoreInstrCache;194 195  /// Cached BB's register pressure.196  DenseMap<const MachineBasicBlock *, std::vector<unsigned>>197      CachedRegisterPressure;198 199  bool EnableSinkAndFold;200 201public:202  MachineSinking(bool EnableSinkAndFold, MachineDominatorTree *DT,203                 MachinePostDominatorTree *PDT, LiveVariables *LV,204                 MachineLoopInfo *MLI, SlotIndexes *SI, LiveIntervals *LIS,205                 MachineCycleInfo *CI, ProfileSummaryInfo *PSI,206                 MachineBlockFrequencyInfo *MBFI,207                 const MachineBranchProbabilityInfo *MBPI, AliasAnalysis *AA)208      : DT(DT), PDT(PDT), CI(CI), PSI(PSI), MBFI(MBFI), MBPI(MBPI), AA(AA),209        LIS(LIS), SI(SI), LV(LV), MLI(MLI),210        EnableSinkAndFold(EnableSinkAndFold) {}211 212  bool run(MachineFunction &MF);213 214  void releaseMemory() {215    CEBCandidates.clear();216    CEMergeCandidates.clear();217  }218 219private:220  bool ProcessBlock(MachineBasicBlock &MBB);221  void ProcessDbgInst(MachineInstr &MI);222  bool isLegalToBreakCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,223                                  MachineBasicBlock *To, bool BreakPHIEdge);224  bool isWorthBreakingCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,225                                   MachineBasicBlock *To,226                                   MachineBasicBlock *&DeferredFromBlock);227 228  bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,229                       MachineInstr &MI);230 231  /// Postpone the splitting of the given critical232  /// edge (\p From, \p To).233  ///234  /// We do not split the edges on the fly. Indeed, this invalidates235  /// the dominance information and thus triggers a lot of updates236  /// of that information underneath.237  /// Instead, we postpone all the splits after each iteration of238  /// the main loop. That way, the information is at least valid239  /// for the lifetime of an iteration.240  ///241  /// \return True if the edge is marked as toSplit, false otherwise.242  /// False can be returned if, for instance, this is not profitable.243  bool PostponeSplitCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,244                                 MachineBasicBlock *To, bool BreakPHIEdge);245  bool SinkInstruction(MachineInstr &MI, bool &SawStore,246                       AllSuccsCache &AllSuccessors);247 248  /// If we sink a COPY inst, some debug users of it's destination may no249  /// longer be dominated by the COPY, and will eventually be dropped.250  /// This is easily rectified by forwarding the non-dominated debug uses251  /// to the copy source.252  void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,253                                     MachineBasicBlock *TargetBlock);254  bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,255                               MachineBasicBlock *DefMBB, bool &BreakPHIEdge,256                               bool &LocalUse) const;257  MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,258                                      bool &BreakPHIEdge,259                                      AllSuccsCache &AllSuccessors);260 261  void FindCycleSinkCandidates(MachineCycle *Cycle, MachineBasicBlock *BB,262                               SmallVectorImpl<MachineInstr *> &Candidates);263 264  bool265  aggressivelySinkIntoCycle(MachineCycle *Cycle, MachineInstr &I,266                            DenseMap<SinkItem, MachineInstr *> &SunkInstrs);267 268  bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,269                            MachineBasicBlock *MBB,270                            MachineBasicBlock *SuccToSinkTo,271                            AllSuccsCache &AllSuccessors);272 273  bool PerformTrivialForwardCoalescing(MachineInstr &MI,274                                       MachineBasicBlock *MBB);275 276  bool PerformSinkAndFold(MachineInstr &MI, MachineBasicBlock *MBB);277 278  SmallVector<MachineBasicBlock *, 4> &279  GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,280                         AllSuccsCache &AllSuccessors) const;281 282  std::vector<unsigned> &getBBRegisterPressure(const MachineBasicBlock &MBB,283                                               bool UseCache = true);284 285  bool registerPressureSetExceedsLimit(unsigned NRegs,286                                       const TargetRegisterClass *RC,287                                       const MachineBasicBlock &MBB);288 289  bool registerPressureExceedsLimit(const MachineBasicBlock &MBB);290};291 292class MachineSinkingLegacy : public MachineFunctionPass {293public:294  static char ID;295 296  MachineSinkingLegacy() : MachineFunctionPass(ID) {297    initializeMachineSinkingLegacyPass(*PassRegistry::getPassRegistry());298  }299 300  bool runOnMachineFunction(MachineFunction &MF) override;301 302  void getAnalysisUsage(AnalysisUsage &AU) const override {303    MachineFunctionPass::getAnalysisUsage(AU);304    AU.addRequired<AAResultsWrapperPass>();305    AU.addRequired<MachineDominatorTreeWrapperPass>();306    AU.addRequired<MachinePostDominatorTreeWrapperPass>();307    AU.addRequired<MachineCycleInfoWrapperPass>();308    AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();309    AU.addPreserved<MachineCycleInfoWrapperPass>();310    AU.addPreserved<MachineLoopInfoWrapperPass>();311    AU.addRequired<ProfileSummaryInfoWrapperPass>();312    if (UseBlockFreqInfo)313      AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();314    AU.addRequired<TargetPassConfig>();315  }316};317 318} // end anonymous namespace319 320char MachineSinkingLegacy::ID = 0;321 322char &llvm::MachineSinkingLegacyID = MachineSinkingLegacy::ID;323 324INITIALIZE_PASS_BEGIN(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",325                      false, false)326INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)327INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)328INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)329INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)330INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)331INITIALIZE_PASS_END(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",332                    false, false)333 334/// Return true if a target defined block prologue instruction interferes335/// with a sink candidate.336static bool blockPrologueInterferes(const MachineBasicBlock *BB,337                                    MachineBasicBlock::const_iterator End,338                                    const MachineInstr &MI,339                                    const TargetRegisterInfo *TRI,340                                    const TargetInstrInfo *TII,341                                    const MachineRegisterInfo *MRI) {342  for (MachineBasicBlock::const_iterator PI = BB->getFirstNonPHI(); PI != End;343       ++PI) {344    // Only check target defined prologue instructions345    if (!TII->isBasicBlockPrologue(*PI))346      continue;347    for (auto &MO : MI.operands()) {348      if (!MO.isReg())349        continue;350      Register Reg = MO.getReg();351      if (!Reg)352        continue;353      if (MO.isUse()) {354        if (Reg.isPhysical() &&355            (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(Reg))))356          continue;357        if (PI->modifiesRegister(Reg, TRI))358          return true;359      } else {360        if (PI->readsRegister(Reg, TRI))361          return true;362        // Check for interference with non-dead defs363        auto *DefOp = PI->findRegisterDefOperand(Reg, TRI, false, true);364        if (DefOp && !DefOp->isDead())365          return true;366      }367    }368  }369 370  return false;371}372 373bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,374                                                     MachineBasicBlock *MBB) {375  if (!MI.isCopy())376    return false;377 378  Register SrcReg = MI.getOperand(1).getReg();379  Register DstReg = MI.getOperand(0).getReg();380  if (!SrcReg.isVirtual() || !DstReg.isVirtual() ||381      !MRI->hasOneNonDBGUse(SrcReg))382    return false;383 384  const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);385  const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);386  if (SRC != DRC)387    return false;388 389  MachineInstr *DefMI = MRI->getVRegDef(SrcReg);390  if (DefMI->isCopyLike())391    return false;392  LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);393  LLVM_DEBUG(dbgs() << "*** to: " << MI);394  MRI->replaceRegWith(DstReg, SrcReg);395  MI.eraseFromParent();396 397  // Conservatively, clear any kill flags, since it's possible that they are no398  // longer correct.399  MRI->clearKillFlags(SrcReg);400 401  ++NumCoalesces;402  return true;403}404 405bool MachineSinking::PerformSinkAndFold(MachineInstr &MI,406                                        MachineBasicBlock *MBB) {407  if (MI.isCopy() || MI.mayLoadOrStore() ||408      MI.getOpcode() == TargetOpcode::REG_SEQUENCE)409    return false;410 411  // Don't sink instructions that the target prefers not to sink.412  if (!TII->shouldSink(MI))413    return false;414 415  // Check if it's safe to move the instruction.416  bool SawStore = true;417  if (!MI.isSafeToMove(SawStore))418    return false;419 420  // Convergent operations may not be made control-dependent on additional421  // values.422  if (MI.isConvergent())423    return false;424 425  // Don't sink defs/uses of hard registers or if the instruction defines more426  // than one register.427  // Don't sink more than two register uses - it'll cover most of the cases and428  // greatly simplifies the register pressure checks.429  Register DefReg;430  Register UsedRegA, UsedRegB;431  for (const MachineOperand &MO : MI.operands()) {432    if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||433        MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||434        MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())435      continue;436    if (!MO.isReg())437      return false;438 439    Register Reg = MO.getReg();440    if (Reg == 0)441      continue;442 443    if (Reg.isVirtual()) {444      if (MO.isDef()) {445        if (DefReg)446          return false;447        DefReg = Reg;448        continue;449      }450 451      if (UsedRegA == 0)452        UsedRegA = Reg;453      else if (UsedRegB == 0)454        UsedRegB = Reg;455      else456        return false;457      continue;458    }459 460    if (Reg.isPhysical() && MO.isUse() &&461        (MRI->isConstantPhysReg(Reg) || TII->isIgnorableUse(MO)))462      continue;463 464    return false;465  }466 467  // Scan uses of the destination register. Every use, except the last, must be468  // a copy, with a chain of copies terminating with either a copy into a hard469  // register, or a load/store instruction where the use is part of the470  // address (*not* the stored value).471  using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;472  SmallVector<SinkInfo> SinkInto;473  SmallVector<Register> Worklist;474 475  const TargetRegisterClass *RC = MRI->getRegClass(DefReg);476  const TargetRegisterClass *RCA =477      UsedRegA == 0 ? nullptr : MRI->getRegClass(UsedRegA);478  const TargetRegisterClass *RCB =479      UsedRegB == 0 ? nullptr : MRI->getRegClass(UsedRegB);480 481  Worklist.push_back(DefReg);482  while (!Worklist.empty()) {483    Register Reg = Worklist.pop_back_val();484 485    for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {486      ExtAddrMode MaybeAM;487      MachineInstr &UseInst = *MO.getParent();488      if (UseInst.isCopy()) {489        Register DstReg;490        if (const MachineOperand &O = UseInst.getOperand(0); O.isReg())491          DstReg = O.getReg();492        if (DstReg == 0)493          return false;494        if (DstReg.isVirtual()) {495          Worklist.push_back(DstReg);496          continue;497        }498        // If we are going to replace a copy, the original instruction must be499        // as cheap as a copy.500        if (!TII->isAsCheapAsAMove(MI))501          return false;502        // The hard register must be in the register class of the original503        // instruction's destination register.504        if (!RC->contains(DstReg))505          return false;506      } else if (UseInst.mayLoadOrStore()) {507        ExtAddrMode AM;508        if (!TII->canFoldIntoAddrMode(UseInst, Reg, MI, AM))509          return false;510        MaybeAM = AM;511      } else {512        return false;513      }514 515      if (UseInst.getParent() != MI.getParent()) {516        // If the register class of the register we are replacing is a superset517        // of any of the register classes of the operands of the materialized518        // instruction don't consider that live range extended.519        const TargetRegisterClass *RCS = MRI->getRegClass(Reg);520        if (RCA && RCA->hasSuperClassEq(RCS))521          RCA = nullptr;522        else if (RCB && RCB->hasSuperClassEq(RCS))523          RCB = nullptr;524        if (RCA || RCB) {525          if (RCA == nullptr) {526            RCA = RCB;527            RCB = nullptr;528          }529 530          unsigned NRegs = !!RCA + !!RCB;531          if (RCA == RCB)532            RCB = nullptr;533 534          // Check we don't exceed register pressure at the destination.535          const MachineBasicBlock &MBB = *UseInst.getParent();536          if (RCB == nullptr) {537            if (registerPressureSetExceedsLimit(NRegs, RCA, MBB))538              return false;539          } else if (registerPressureSetExceedsLimit(1, RCA, MBB) ||540                     registerPressureSetExceedsLimit(1, RCB, MBB)) {541            return false;542          }543        }544      }545 546      SinkInto.emplace_back(&UseInst, MaybeAM);547    }548  }549 550  if (SinkInto.empty())551    return false;552 553  // Now we know we can fold the instruction in all its users.554  for (auto &[SinkDst, MaybeAM] : SinkInto) {555    MachineInstr *New = nullptr;556    LLVM_DEBUG(dbgs() << "Sinking copy of"; MI.dump(); dbgs() << "into";557               SinkDst->dump());558    if (SinkDst->isCopy()) {559      // TODO: After performing the sink-and-fold, the original instruction is560      // deleted. Its value is still available (in a hard register), so if there561      // are debug instructions which refer to the (now deleted) virtual562      // register they could be updated to refer to the hard register, in563      // principle. However, it's not clear how to do that, moreover in some564      // cases the debug instructions may need to be replicated proportionally565      // to the number of the COPY instructions replaced and in some extreme566      // cases we can end up with quadratic increase in the number of debug567      // instructions.568 569      // Sink a copy of the instruction, replacing a COPY instruction.570      MachineBasicBlock::iterator InsertPt = SinkDst->getIterator();571      Register DstReg = SinkDst->getOperand(0).getReg();572      TII->reMaterialize(*SinkDst->getParent(), InsertPt, DstReg, 0, MI);573      New = &*std::prev(InsertPt);574      if (!New->getDebugLoc())575        New->setDebugLoc(SinkDst->getDebugLoc());576 577      // The operand registers of the "sunk" instruction have their live range578      // extended and their kill flags may no longer be correct. Conservatively579      // clear the kill flags.580      if (UsedRegA)581        MRI->clearKillFlags(UsedRegA);582      if (UsedRegB)583        MRI->clearKillFlags(UsedRegB);584    } else {585      // Fold instruction into the addressing mode of a memory instruction.586      New = TII->emitLdStWithAddr(*SinkDst, MaybeAM);587 588      // The registers of the addressing mode may have their live range extended589      // and their kill flags may no longer be correct. Conservatively clear the590      // kill flags.591      if (Register R = MaybeAM.BaseReg; R.isValid() && R.isVirtual())592        MRI->clearKillFlags(R);593      if (Register R = MaybeAM.ScaledReg; R.isValid() && R.isVirtual())594        MRI->clearKillFlags(R);595    }596    LLVM_DEBUG(dbgs() << "yielding"; New->dump());597    // Clear the StoreInstrCache, since we may invalidate it by erasing.598    if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())599      StoreInstrCache.clear();600    SinkDst->eraseFromParent();601  }602 603  // Collect operands that need to be cleaned up because the registers no longer604  // exist (in COPYs and debug instructions). We cannot delete instructions or605  // clear operands while traversing register uses.606  SmallVector<MachineOperand *> Cleanup;607  Worklist.push_back(DefReg);608  while (!Worklist.empty()) {609    Register Reg = Worklist.pop_back_val();610    for (MachineOperand &MO : MRI->use_operands(Reg)) {611      MachineInstr *U = MO.getParent();612      assert((U->isCopy() || U->isDebugInstr()) &&613             "Only debug uses and copies must remain");614      if (U->isCopy())615        Worklist.push_back(U->getOperand(0).getReg());616      Cleanup.push_back(&MO);617    }618  }619 620  // Delete the dead COPYs and clear operands in debug instructions621  for (MachineOperand *MO : Cleanup) {622    MachineInstr *I = MO->getParent();623    if (I->isCopy()) {624      I->eraseFromParent();625    } else {626      MO->setReg(0);627      MO->setSubReg(0);628    }629  }630 631  MI.eraseFromParent();632  return true;633}634 635/// AllUsesDominatedByBlock - Return true if all uses of the specified register636/// occur in blocks dominated by the specified block. If any use is in the637/// definition block, then return false since it is never legal to move def638/// after uses.639bool MachineSinking::AllUsesDominatedByBlock(Register Reg,640                                             MachineBasicBlock *MBB,641                                             MachineBasicBlock *DefMBB,642                                             bool &BreakPHIEdge,643                                             bool &LocalUse) const {644  assert(Reg.isVirtual() && "Only makes sense for vregs");645 646  // Ignore debug uses because debug info doesn't affect the code.647  if (MRI->use_nodbg_empty(Reg))648    return true;649 650  // BreakPHIEdge is true if all the uses are in the successor MBB being sunken651  // into and they are all PHI nodes. In this case, machine-sink must break652  // the critical edge first. e.g.653  //654  // %bb.1:655  //   Predecessors according to CFG: %bb.0656  //     ...657  //     %def = DEC64_32r %x, implicit-def dead %eflags658  //     ...659  //     JE_4 <%bb.37>, implicit %eflags660  //   Successors according to CFG: %bb.37 %bb.2661  //662  // %bb.2:663  //     %p = PHI %y, %bb.0, %def, %bb.1664  if (all_of(MRI->use_nodbg_operands(Reg), [&](MachineOperand &MO) {665        MachineInstr *UseInst = MO.getParent();666        unsigned OpNo = MO.getOperandNo();667        MachineBasicBlock *UseBlock = UseInst->getParent();668        return UseBlock == MBB && UseInst->isPHI() &&669               UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;670      })) {671    BreakPHIEdge = true;672    return true;673  }674 675  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {676    // Determine the block of the use.677    MachineInstr *UseInst = MO.getParent();678    unsigned OpNo = &MO - &UseInst->getOperand(0);679    MachineBasicBlock *UseBlock = UseInst->getParent();680    if (UseInst->isPHI()) {681      // PHI nodes use the operand in the predecessor block, not the block with682      // the PHI.683      UseBlock = UseInst->getOperand(OpNo + 1).getMBB();684    } else if (UseBlock == DefMBB) {685      LocalUse = true;686      return false;687    }688 689    // Check that it dominates.690    if (!DT->dominates(MBB, UseBlock))691      return false;692  }693 694  return true;695}696 697/// Return true if this machine instruction loads from global offset table or698/// constant pool.699static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {700  assert(MI.mayLoad() && "Expected MI that loads!");701 702  // If we lost memory operands, conservatively assume that the instruction703  // reads from everything..704  if (MI.memoperands_empty())705    return true;706 707  for (MachineMemOperand *MemOp : MI.memoperands())708    if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())709      if (PSV->isGOT() || PSV->isConstantPool())710        return true;711 712  return false;713}714 715void MachineSinking::FindCycleSinkCandidates(716    MachineCycle *Cycle, MachineBasicBlock *BB,717    SmallVectorImpl<MachineInstr *> &Candidates) {718  for (auto &MI : *BB) {719    LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);720    if (MI.isMetaInstruction()) {721      LLVM_DEBUG(dbgs() << "CycleSink: not sinking meta instruction\n");722      continue;723    }724    if (!TII->shouldSink(MI)) {725      LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "726                           "target\n");727      continue;728    }729    if (!isCycleInvariant(Cycle, MI)) {730      LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");731      continue;732    }733    bool DontMoveAcrossStore = true;734    if (!MI.isSafeToMove(DontMoveAcrossStore)) {735      LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");736      continue;737    }738    if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {739      LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");740      continue;741    }742    if (MI.isConvergent())743      continue;744 745    const MachineOperand &MO = MI.getOperand(0);746    if (!MO.isReg() || !MO.getReg() || !MO.isDef())747      continue;748    if (!MRI->hasOneDef(MO.getReg()))749      continue;750 751    LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");752    Candidates.push_back(&MI);753  }754}755 756PreservedAnalyses757MachineSinkingPass::run(MachineFunction &MF,758                        MachineFunctionAnalysisManager &MFAM) {759  auto *DT = &MFAM.getResult<MachineDominatorTreeAnalysis>(MF);760  auto *PDT = &MFAM.getResult<MachinePostDominatorTreeAnalysis>(MF);761  auto *CI = &MFAM.getResult<MachineCycleAnalysis>(MF);762  auto *PSI = MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(MF)763                  .getCachedResult<ProfileSummaryAnalysis>(764                      *MF.getFunction().getParent());765  auto *MBFI = UseBlockFreqInfo766                   ? &MFAM.getResult<MachineBlockFrequencyAnalysis>(MF)767                   : nullptr;768  auto *MBPI = &MFAM.getResult<MachineBranchProbabilityAnalysis>(MF);769  auto *AA = &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(MF)770                  .getManager()771                  .getResult<AAManager>(MF.getFunction());772  auto *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(MF);773  auto *SI = MFAM.getCachedResult<SlotIndexesAnalysis>(MF);774  auto *LV = MFAM.getCachedResult<LiveVariablesAnalysis>(MF);775  auto *MLI = MFAM.getCachedResult<MachineLoopAnalysis>(MF);776  MachineSinking Impl(EnableSinkAndFold, DT, PDT, LV, MLI, SI, LIS, CI, PSI,777                      MBFI, MBPI, AA);778  bool Changed = Impl.run(MF);779  if (!Changed)780    return PreservedAnalyses::all();781  auto PA = getMachineFunctionPassPreservedAnalyses();782  PA.preserve<MachineCycleAnalysis>();783  PA.preserve<MachineLoopAnalysis>();784  return PA;785}786 787void MachineSinkingPass::printPipeline(788    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {789  OS << MapClassName2PassName(name()); // ideally machine-sink790  if (EnableSinkAndFold)791    OS << "<enable-sink-fold>";792}793 794bool MachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {795  if (skipFunction(MF.getFunction()))796    return false;797 798  TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();799  bool EnableSinkAndFold = PassConfig->getEnableSinkAndFold();800 801  auto *DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();802  auto *PDT =803      &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();804  auto *CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();805  auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();806  auto *MBFI =807      UseBlockFreqInfo808          ? &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI()809          : nullptr;810  auto *MBPI =811      &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();812  auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();813  // Get analyses for split critical edge.814  auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();815  auto *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;816  auto *SIWrapper = getAnalysisIfAvailable<SlotIndexesWrapperPass>();817  auto *SI = SIWrapper ? &SIWrapper->getSI() : nullptr;818  auto *LVWrapper = getAnalysisIfAvailable<LiveVariablesWrapperPass>();819  auto *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;820  auto *MLIWrapper = getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();821  auto *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;822 823  MachineSinking Impl(EnableSinkAndFold, DT, PDT, LV, MLI, SI, LIS, CI, PSI,824                      MBFI, MBPI, AA);825  return Impl.run(MF);826}827 828bool MachineSinking::run(MachineFunction &MF) {829  LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");830 831  STI = &MF.getSubtarget();832  TII = STI->getInstrInfo();833  TRI = STI->getRegisterInfo();834  MRI = &MF.getRegInfo();835 836  RegClassInfo.runOnMachineFunction(MF);837 838  bool EverMadeChange = false;839 840  while (true) {841    bool MadeChange = false;842 843    // Process all basic blocks.844    CEBCandidates.clear();845    CEMergeCandidates.clear();846    ToSplit.clear();847    for (auto &MBB : MF)848      MadeChange |= ProcessBlock(MBB);849 850    // If we have anything we marked as toSplit, split it now.851    MachineDomTreeUpdater MDTU(DT, PDT,852                               MachineDomTreeUpdater::UpdateStrategy::Lazy);853    for (const auto &Pair : ToSplit) {854      auto NewSucc = Pair.first->SplitCriticalEdge(855          Pair.second, {LIS, SI, LV, MLI}, nullptr, &MDTU);856      if (NewSucc != nullptr) {857        LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "858                          << printMBBReference(*Pair.first) << " -- "859                          << printMBBReference(*NewSucc) << " -- "860                          << printMBBReference(*Pair.second) << '\n');861        if (MBFI)862          MBFI->onEdgeSplit(*Pair.first, *NewSucc, *MBPI);863 864        MadeChange = true;865        ++NumSplit;866        CI->splitCriticalEdge(Pair.first, Pair.second, NewSucc);867      } else868        LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");869    }870    // If this iteration over the code changed anything, keep iterating.871    if (!MadeChange)872      break;873    EverMadeChange = true;874  }875 876  if (SinkInstsIntoCycle) {877    SmallVector<MachineCycle *, 8> Cycles(CI->toplevel_cycles());878    SchedModel.init(STI);879    bool HasHighPressure;880 881    DenseMap<SinkItem, MachineInstr *> SunkInstrs;882 883    enum CycleSinkStage { COPY, LOW_LATENCY, AGGRESSIVE, END };884    for (unsigned Stage = CycleSinkStage::COPY; Stage != CycleSinkStage::END;885         ++Stage, SunkInstrs.clear()) {886      HasHighPressure = false;887 888      for (auto *Cycle : Cycles) {889        MachineBasicBlock *Preheader = Cycle->getCyclePreheader();890        if (!Preheader) {891          LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");892          continue;893        }894        SmallVector<MachineInstr *, 8> Candidates;895        FindCycleSinkCandidates(Cycle, Preheader, Candidates);896 897        unsigned i = 0;898 899        // Walk the candidates in reverse order so that we start with the use900        // of a def-use chain, if there is any.901        // TODO: Sort the candidates using a cost-model.902        for (MachineInstr *I : llvm::reverse(Candidates)) {903          // CycleSinkStage::COPY: Sink a limited number of copies904          if (Stage == CycleSinkStage::COPY) {905            if (i++ == SinkIntoCycleLimit) {906              LLVM_DEBUG(dbgs()907                         << "CycleSink:   Limit reached of instructions to "908                            "be analyzed.");909              break;910            }911 912            if (!I->isCopy())913              continue;914          }915 916          // CycleSinkStage::LOW_LATENCY: sink unlimited number of instructions917          // which the target specifies as low-latency918          if (Stage == CycleSinkStage::LOW_LATENCY &&919              !TII->hasLowDefLatency(SchedModel, *I, 0))920            continue;921 922          if (!aggressivelySinkIntoCycle(Cycle, *I, SunkInstrs))923            continue;924          EverMadeChange = true;925          ++NumCycleSunk;926        }927 928        // Recalculate the pressure after sinking929        if (!HasHighPressure)930          HasHighPressure = registerPressureExceedsLimit(*Preheader);931      }932      if (!HasHighPressure)933        break;934    }935  }936 937  HasStoreCache.clear();938  StoreInstrCache.clear();939 940  // Now clear any kill flags for recorded registers.941  for (auto I : RegsToClearKillFlags)942    MRI->clearKillFlags(I);943  RegsToClearKillFlags.clear();944 945  releaseMemory();946  return EverMadeChange;947}948 949bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {950  if ((!EnableSinkAndFold && MBB.succ_size() <= 1) || MBB.empty())951    return false;952 953  // Don't bother sinking code out of unreachable blocks. In addition to being954  // unprofitable, it can also lead to infinite looping, because in an955  // unreachable cycle there may be nowhere to stop.956  if (!DT->isReachableFromEntry(&MBB))957    return false;958 959  bool MadeChange = false;960 961  // Cache all successors, sorted by frequency info and cycle depth.962  AllSuccsCache AllSuccessors;963 964  // Walk the basic block bottom-up.  Remember if we saw a store.965  MachineBasicBlock::iterator I = MBB.end();966  --I;967  bool ProcessedBegin, SawStore = false;968  do {969    MachineInstr &MI = *I; // The instruction to sink.970 971    // Predecrement I (if it's not begin) so that it isn't invalidated by972    // sinking.973    ProcessedBegin = I == MBB.begin();974    if (!ProcessedBegin)975      --I;976 977    if (MI.isDebugOrPseudoInstr() || MI.isFakeUse()) {978      if (MI.isDebugValue())979        ProcessDbgInst(MI);980      continue;981    }982 983    if (EnableSinkAndFold && PerformSinkAndFold(MI, &MBB)) {984      MadeChange = true;985      continue;986    }987 988    // Can't sink anything out of a block that has less than two successors.989    if (MBB.succ_size() <= 1)990      continue;991 992    if (PerformTrivialForwardCoalescing(MI, &MBB)) {993      MadeChange = true;994      continue;995    }996 997    if (SinkInstruction(MI, SawStore, AllSuccessors)) {998      ++NumSunk;999      MadeChange = true;1000    }1001 1002    // If we just processed the first instruction in the block, we're done.1003  } while (!ProcessedBegin);1004 1005  SeenDbgUsers.clear();1006  SeenDbgVars.clear();1007  // recalculate the bb register pressure after sinking one BB.1008  CachedRegisterPressure.clear();1009  return MadeChange;1010}1011 1012void MachineSinking::ProcessDbgInst(MachineInstr &MI) {1013  // When we see DBG_VALUEs for registers, record any vreg it reads, so that1014  // we know what to sink if the vreg def sinks.1015  assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");1016 1017  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),1018                    MI.getDebugLoc()->getInlinedAt());1019  bool SeenBefore = SeenDbgVars.contains(Var);1020 1021  for (MachineOperand &MO : MI.debug_operands()) {1022    if (MO.isReg() && MO.getReg().isVirtual())1023      SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));1024  }1025 1026  // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.1027  SeenDbgVars.insert(Var);1028}1029 1030bool MachineSinking::isWorthBreakingCriticalEdge(1031    MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To,1032    MachineBasicBlock *&DeferredFromBlock) {1033  // FIXME: Need much better heuristics.1034 1035  // If the pass has already considered breaking this edge (during this pass1036  // through the function), then let's go ahead and break it. This means1037  // sinking multiple "cheap" instructions into the same block.1038  if (!CEBCandidates.insert(std::make_pair(From, To)).second)1039    return true;1040 1041  if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))1042    return true;1043 1044  // Check and record the register and the destination block we want to sink1045  // into. Note that we want to do the following before the next check on branch1046  // probability. Because we want to record the initial candidate even if it's1047  // on hot edge, so that other candidates that might not on hot edges can be1048  // sinked as well.1049  for (const auto &MO : MI.all_defs()) {1050    Register Reg = MO.getReg();1051    if (!Reg)1052      continue;1053    Register SrcReg = Reg.isVirtual() ? TRI->lookThruCopyLike(Reg, MRI) : Reg;1054    auto Key = std::make_pair(SrcReg, To);1055    auto Res = CEMergeCandidates.try_emplace(Key, From);1056    // We wanted to sink the same register into the same block, consider it to1057    // be profitable.1058    if (!Res.second) {1059      // Return the source block that was previously held off.1060      DeferredFromBlock = Res.first->second;1061      return true;1062    }1063  }1064 1065  if (From->isSuccessor(To) &&1066      MBPI->getEdgeProbability(From, To) <=1067          BranchProbability(SplitEdgeProbabilityThreshold, 100))1068    return true;1069 1070  // MI is cheap, we probably don't want to break the critical edge for it.1071  // However, if this would allow some definitions of its source operands1072  // to be sunk then it's probably worth it.1073  for (const MachineOperand &MO : MI.all_uses()) {1074    Register Reg = MO.getReg();1075    if (Reg == 0)1076      continue;1077 1078    // We don't move live definitions of physical registers,1079    // so sinking their uses won't enable any opportunities.1080    if (Reg.isPhysical())1081      continue;1082 1083    // If this instruction is the only user of a virtual register,1084    // check if breaking the edge will enable sinking1085    // both this instruction and the defining instruction.1086    if (MRI->hasOneNonDBGUse(Reg)) {1087      // If the definition resides in same MBB,1088      // claim it's likely we can sink these together.1089      // If definition resides elsewhere, we aren't1090      // blocking it from being sunk so don't break the edge.1091      MachineInstr *DefMI = MRI->getVRegDef(Reg);1092      if (DefMI->getParent() == MI.getParent())1093        return true;1094    }1095  }1096 1097  // Let the target decide if it's worth breaking this1098  // critical edge for a "cheap" instruction.1099  return TII->shouldBreakCriticalEdgeToSink(MI);1100}1101 1102bool MachineSinking::isLegalToBreakCriticalEdge(MachineInstr &MI,1103                                                MachineBasicBlock *FromBB,1104                                                MachineBasicBlock *ToBB,1105                                                bool BreakPHIEdge) {1106  // Avoid breaking back edge. From == To means backedge for single BB cycle.1107  if (!SplitEdges || FromBB == ToBB || !FromBB->isSuccessor(ToBB))1108    return false;1109 1110  MachineCycle *FromCycle = CI->getCycle(FromBB);1111  MachineCycle *ToCycle = CI->getCycle(ToBB);1112 1113  // Check for backedges of more "complex" cycles.1114  if (FromCycle == ToCycle && FromCycle &&1115      (!FromCycle->isReducible() || FromCycle->getHeader() == ToBB))1116    return false;1117 1118  // It's not always legal to break critical edges and sink the computation1119  // to the edge.1120  //1121  // %bb.1:1122  // v10241123  // Beq %bb.31124  // <fallthrough>1125  // %bb.2:1126  // ... no uses of v10241127  // <fallthrough>1128  // %bb.3:1129  // ...1130  //       = v10241131  //1132  // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:1133  //1134  // %bb.1:1135  // ...1136  // Bne %bb.21137  // %bb.4:1138  // v1024 =1139  // B %bb.31140  // %bb.2:1141  // ... no uses of v10241142  // <fallthrough>1143  // %bb.3:1144  // ...1145  //       = v10241146  //1147  // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.31148  // flow. We need to ensure the new basic block where the computation is1149  // sunk to dominates all the uses.1150  // It's only legal to break critical edge and sink the computation to the1151  // new block if all the predecessors of "To", except for "From", are1152  // not dominated by "From". Given SSA property, this means these1153  // predecessors are dominated by "To".1154  //1155  // There is no need to do this check if all the uses are PHI nodes. PHI1156  // sources are only defined on the specific predecessor edges.1157  if (!BreakPHIEdge) {1158    for (MachineBasicBlock *Pred : ToBB->predecessors())1159      if (Pred != FromBB && !DT->dominates(ToBB, Pred))1160        return false;1161  }1162 1163  return true;1164}1165 1166bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,1167                                               MachineBasicBlock *FromBB,1168                                               MachineBasicBlock *ToBB,1169                                               bool BreakPHIEdge) {1170  bool Status = false;1171  MachineBasicBlock *DeferredFromBB = nullptr;1172  if (isWorthBreakingCriticalEdge(MI, FromBB, ToBB, DeferredFromBB)) {1173    // If there is a DeferredFromBB, we consider FromBB only if _both_1174    // of them are legal to split.1175    if ((!DeferredFromBB ||1176         ToSplit.count(std::make_pair(DeferredFromBB, ToBB)) ||1177         isLegalToBreakCriticalEdge(MI, DeferredFromBB, ToBB, BreakPHIEdge)) &&1178        isLegalToBreakCriticalEdge(MI, FromBB, ToBB, BreakPHIEdge)) {1179      ToSplit.insert(std::make_pair(FromBB, ToBB));1180      if (DeferredFromBB)1181        ToSplit.insert(std::make_pair(DeferredFromBB, ToBB));1182      Status = true;1183    }1184  }1185 1186  return Status;1187}1188 1189std::vector<unsigned> &1190MachineSinking::getBBRegisterPressure(const MachineBasicBlock &MBB,1191                                      bool UseCache) {1192  // Currently to save compiling time, MBB's register pressure will not change1193  // in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's1194  // register pressure is changed after sinking any instructions into it.1195  // FIXME: need a accurate and cheap register pressure estiminate model here.1196 1197  auto RP = CachedRegisterPressure.find(&MBB);1198  if (UseCache && RP != CachedRegisterPressure.end())1199    return RP->second;1200 1201  RegionPressure Pressure;1202  RegPressureTracker RPTracker(Pressure);1203 1204  // Initialize the register pressure tracker.1205  RPTracker.init(MBB.getParent(), &RegClassInfo, nullptr, &MBB, MBB.end(),1206                 /*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);1207 1208  for (MachineBasicBlock::const_iterator MII = MBB.instr_end(),1209                                         MIE = MBB.instr_begin();1210       MII != MIE; --MII) {1211    const MachineInstr &MI = *std::prev(MII);1212    if (MI.isDebugOrPseudoInstr())1213      continue;1214    RegisterOperands RegOpers;1215    RegOpers.collect(MI, *TRI, *MRI, false, false);1216    RPTracker.recedeSkipDebugValues();1217    assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");1218    RPTracker.recede(RegOpers);1219  }1220 1221  RPTracker.closeRegion();1222 1223  if (RP != CachedRegisterPressure.end()) {1224    CachedRegisterPressure[&MBB] = RPTracker.getPressure().MaxSetPressure;1225    return CachedRegisterPressure[&MBB];1226  }1227 1228  auto It = CachedRegisterPressure.insert(1229      std::make_pair(&MBB, RPTracker.getPressure().MaxSetPressure));1230  return It.first->second;1231}1232 1233bool MachineSinking::registerPressureSetExceedsLimit(1234    unsigned NRegs, const TargetRegisterClass *RC,1235    const MachineBasicBlock &MBB) {1236  unsigned Weight = NRegs * TRI->getRegClassWeight(RC).RegWeight;1237  const int *PS = TRI->getRegClassPressureSets(RC);1238  std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB);1239  for (; *PS != -1; PS++)1240    if (Weight + BBRegisterPressure[*PS] >=1241        RegClassInfo.getRegPressureSetLimit(*PS))1242      return true;1243  return false;1244}1245 1246// Recalculate RP and check if any pressure set exceeds the set limit.1247bool MachineSinking::registerPressureExceedsLimit(1248    const MachineBasicBlock &MBB) {1249  std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB, false);1250 1251  for (unsigned PS = 0; PS < BBRegisterPressure.size(); ++PS) {1252    if (BBRegisterPressure[PS] >=1253        TRI->getRegPressureSetLimit(*MBB.getParent(), PS)) {1254      return true;1255    }1256  }1257 1258  return false;1259}1260 1261/// isProfitableToSinkTo - Return true if it is profitable to sink MI.1262bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,1263                                          MachineBasicBlock *MBB,1264                                          MachineBasicBlock *SuccToSinkTo,1265                                          AllSuccsCache &AllSuccessors) {1266  assert(SuccToSinkTo && "Invalid SinkTo Candidate BB");1267 1268  if (MBB == SuccToSinkTo)1269    return false;1270 1271  // It is profitable if SuccToSinkTo does not post dominate current block.1272  if (!PDT->dominates(SuccToSinkTo, MBB))1273    return true;1274 1275  // It is profitable to sink an instruction from a deeper cycle to a shallower1276  // cycle, even if the latter post-dominates the former (PR21115).1277  if (CI->getCycleDepth(MBB) > CI->getCycleDepth(SuccToSinkTo))1278    return true;1279 1280  // Check if only use in post dominated block is PHI instruction.1281  bool NonPHIUse = false;1282  for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {1283    MachineBasicBlock *UseBlock = UseInst.getParent();1284    if (UseBlock == SuccToSinkTo && !UseInst.isPHI())1285      NonPHIUse = true;1286  }1287  if (!NonPHIUse)1288    return true;1289 1290  // If SuccToSinkTo post dominates then also it may be profitable if MI1291  // can further profitably sinked into another block in next round.1292  bool BreakPHIEdge = false;1293  // FIXME - If finding successor is compile time expensive then cache results.1294  if (MachineBasicBlock *MBB2 =1295          FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))1296    return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);1297 1298  MachineCycle *MCycle = CI->getCycle(MBB);1299 1300  // If the instruction is not inside a cycle, it is not profitable to sink MI1301  // to a post dominate block SuccToSinkTo.1302  if (!MCycle)1303    return false;1304 1305  // If this instruction is inside a Cycle and sinking this instruction can make1306  // more registers live range shorten, it is still prifitable.1307  for (const MachineOperand &MO : MI.operands()) {1308    // Ignore non-register operands.1309    if (!MO.isReg())1310      continue;1311    Register Reg = MO.getReg();1312    if (Reg == 0)1313      continue;1314 1315    if (Reg.isPhysical()) {1316      // Don't handle non-constant and non-ignorable physical register uses.1317      if (MO.isUse() && !MRI->isConstantPhysReg(Reg) &&1318          !TII->isIgnorableUse(MO))1319        return false;1320      continue;1321    }1322 1323    // Users for the defs are all dominated by SuccToSinkTo.1324    if (MO.isDef()) {1325      // This def register's live range is shortened after sinking.1326      bool LocalUse = false;1327      if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,1328                                   LocalUse))1329        return false;1330    } else {1331      MachineInstr *DefMI = MRI->getVRegDef(Reg);1332      if (!DefMI)1333        continue;1334      MachineCycle *Cycle = CI->getCycle(DefMI->getParent());1335      // DefMI is defined outside of cycle. There should be no live range1336      // impact for this operand. Defination outside of cycle means:1337      // 1: defination is outside of cycle.1338      // 2: defination is in this cycle, but it is a PHI in the cycle header.1339      if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() &&1340                              Cycle->getHeader() == DefMI->getParent()))1341        continue;1342      // The DefMI is defined inside the cycle.1343      // If sinking this operand makes some register pressure set exceed limit,1344      // it is not profitable.1345      if (registerPressureSetExceedsLimit(1, MRI->getRegClass(Reg),1346                                          *SuccToSinkTo)) {1347        LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");1348        return false;1349      }1350    }1351  }1352 1353  // If MI is in cycle and all its operands are alive across the whole cycle or1354  // if no operand sinking make register pressure set exceed limit, it is1355  // profitable to sink MI.1356  return true;1357}1358 1359/// Get the sorted sequence of successors for this MachineBasicBlock, possibly1360/// computing it if it was not already cached.1361SmallVector<MachineBasicBlock *, 4> &1362MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,1363                                       AllSuccsCache &AllSuccessors) const {1364  // Do we have the sorted successors in cache ?1365  auto Succs = AllSuccessors.find(MBB);1366  if (Succs != AllSuccessors.end())1367    return Succs->second;1368 1369  SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->successors());1370 1371  // Handle cases where sinking can happen but where the sink point isn't a1372  // successor. For example:1373  //1374  //   x = computation1375  //   if () {} else {}1376  //   use x1377  //1378  for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {1379    // DomTree children of MBB that have MBB as immediate dominator are added.1380    if (DTChild->getIDom()->getBlock() == MI.getParent() &&1381        // Skip MBBs already added to the AllSuccs vector above.1382        !MBB->isSuccessor(DTChild->getBlock()))1383      AllSuccs.push_back(DTChild->getBlock());1384  }1385 1386  // Sort Successors according to their cycle depth or block frequency info.1387  llvm::stable_sort(1388      AllSuccs, [&](const MachineBasicBlock *L, const MachineBasicBlock *R) {1389        uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;1390        uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;1391        if (llvm::shouldOptimizeForSize(MBB, PSI, MBFI) ||1392            (!LHSFreq && !RHSFreq))1393          return CI->getCycleDepth(L) < CI->getCycleDepth(R);1394        return LHSFreq < RHSFreq;1395      });1396 1397  auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));1398 1399  return it.first->second;1400}1401 1402/// FindSuccToSinkTo - Find a successor to sink this instruction to.1403MachineBasicBlock *1404MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,1405                                 bool &BreakPHIEdge,1406                                 AllSuccsCache &AllSuccessors) {1407  assert(MBB && "Invalid MachineBasicBlock!");1408 1409  // loop over all the operands of the specified instruction.  If there is1410  // anything we can't handle, bail out.1411 1412  // SuccToSinkTo - This is the successor to sink this instruction to, once we1413  // decide.1414  MachineBasicBlock *SuccToSinkTo = nullptr;1415  for (const MachineOperand &MO : MI.operands()) {1416    if (!MO.isReg())1417      continue; // Ignore non-register operands.1418 1419    Register Reg = MO.getReg();1420    if (Reg == 0)1421      continue;1422 1423    if (Reg.isPhysical()) {1424      if (MO.isUse()) {1425        // If the physreg has no defs anywhere, it's just an ambient register1426        // and we can freely move its uses. Alternatively, if it's allocatable,1427        // it could get allocated to something with a def during allocation.1428        if (!MRI->isConstantPhysReg(Reg) && !TII->isIgnorableUse(MO))1429          return nullptr;1430      } else if (!MO.isDead()) {1431        // A def that isn't dead. We can't move it.1432        return nullptr;1433      }1434    } else {1435      // Virtual register uses are always safe to sink.1436      if (MO.isUse())1437        continue;1438 1439      // If it's not safe to move defs of the register class, then abort.1440      if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))1441        return nullptr;1442 1443      // Virtual register defs can only be sunk if all their uses are in blocks1444      // dominated by one of the successors.1445      if (SuccToSinkTo) {1446        // If a previous operand picked a block to sink to, then this operand1447        // must be sinkable to the same block.1448        bool LocalUse = false;1449        if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,1450                                     LocalUse))1451          return nullptr;1452 1453        continue;1454      }1455 1456      // Otherwise, we should look at all the successors and decide which one1457      // we should sink to. If we have reliable block frequency information1458      // (frequency != 0) available, give successors with smaller frequencies1459      // higher priority, otherwise prioritize smaller cycle depths.1460      for (MachineBasicBlock *SuccBlock :1461           GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {1462        bool LocalUse = false;1463        if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, BreakPHIEdge,1464                                    LocalUse)) {1465          SuccToSinkTo = SuccBlock;1466          break;1467        }1468        if (LocalUse)1469          // Def is used locally, it's never safe to move this def.1470          return nullptr;1471      }1472 1473      // If we couldn't find a block to sink to, ignore this instruction.1474      if (!SuccToSinkTo)1475        return nullptr;1476      if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))1477        return nullptr;1478    }1479  }1480 1481  // It is not possible to sink an instruction into its own block.  This can1482  // happen with cycles.1483  if (MBB == SuccToSinkTo)1484    return nullptr;1485 1486  // It's not safe to sink instructions to EH landing pad. Control flow into1487  // landing pad is implicitly defined.1488  if (SuccToSinkTo && SuccToSinkTo->isEHPad())1489    return nullptr;1490 1491  // It ought to be okay to sink instructions into an INLINEASM_BR target, but1492  // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in1493  // the source block (which this code does not yet do). So for now, forbid1494  // doing so.1495  if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())1496    return nullptr;1497 1498  if (SuccToSinkTo && !TII->isSafeToSink(MI, SuccToSinkTo, CI))1499    return nullptr;1500 1501  return SuccToSinkTo;1502}1503 1504/// Return true if MI is likely to be usable as a memory operation by the1505/// implicit null check optimization.1506///1507/// This is a "best effort" heuristic, and should not be relied upon for1508/// correctness.  This returning true does not guarantee that the implicit null1509/// check optimization is legal over MI, and this returning false does not1510/// guarantee MI cannot possibly be used to do a null check.1511static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,1512                                             const TargetInstrInfo *TII,1513                                             const TargetRegisterInfo *TRI) {1514  using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;1515 1516  auto *MBB = MI.getParent();1517  if (MBB->pred_size() != 1)1518    return false;1519 1520  auto *PredMBB = *MBB->pred_begin();1521  auto *PredBB = PredMBB->getBasicBlock();1522 1523  // Frontends that don't use implicit null checks have no reason to emit1524  // branches with make.implicit metadata, and this function should always1525  // return false for them.1526  if (!PredBB ||1527      !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))1528    return false;1529 1530  const MachineOperand *BaseOp;1531  int64_t Offset;1532  bool OffsetIsScalable;1533  if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))1534    return false;1535 1536  if (!BaseOp->isReg())1537    return false;1538 1539  if (!(MI.mayLoad() && !MI.isPredicable()))1540    return false;1541 1542  MachineBranchPredicate MBP;1543  if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))1544    return false;1545 1546  return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&1547         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||1548          MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&1549         MBP.LHS.getReg() == BaseOp->getReg();1550}1551 1552/// If the sunk instruction is a copy, try to forward the copy instead of1553/// leaving an 'undef' DBG_VALUE in the original location. Don't do this if1554/// there's any subregister weirdness involved. Returns true if copy1555/// propagation occurred.1556static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI,1557                                 Register Reg) {1558  const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();1559  const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();1560 1561  // Copy DBG_VALUE operand and set the original to undef. We then check to1562  // see whether this is something that can be copy-forwarded. If it isn't,1563  // continue around the loop.1564 1565  const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;1566  auto CopyOperands = TII.isCopyInstr(SinkInst);1567  if (!CopyOperands)1568    return false;1569  SrcMO = CopyOperands->Source;1570  DstMO = CopyOperands->Destination;1571 1572  // Check validity of forwarding this copy.1573  bool PostRA = MRI.getNumVirtRegs() == 0;1574 1575  // Trying to forward between physical and virtual registers is too hard.1576  if (Reg.isVirtual() != SrcMO->getReg().isVirtual())1577    return false;1578 1579  // Only try virtual register copy-forwarding before regalloc, and physical1580  // register copy-forwarding after regalloc.1581  bool arePhysRegs = !Reg.isVirtual();1582  if (arePhysRegs != PostRA)1583    return false;1584 1585  // Pre-regalloc, only forward if all subregisters agree (or there are no1586  // subregs at all). More analysis might recover some forwardable copies.1587  if (!PostRA)1588    for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg))1589      if (DbgMO.getSubReg() != SrcMO->getSubReg() ||1590          DbgMO.getSubReg() != DstMO->getSubReg())1591        return false;1592 1593  // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register1594  // of this copy. Only forward the copy if the DBG_VALUE operand exactly1595  // matches the copy destination.1596  if (PostRA && Reg != DstMO->getReg())1597    return false;1598 1599  for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg)) {1600    DbgMO.setReg(SrcMO->getReg());1601    DbgMO.setSubReg(SrcMO->getSubReg());1602  }1603  return true;1604}1605 1606using MIRegs = std::pair<MachineInstr *, SmallVector<Register, 2>>;1607/// Sink an instruction and its associated debug instructions.1608static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,1609                        MachineBasicBlock::iterator InsertPos,1610                        ArrayRef<MIRegs> DbgValuesToSink) {1611  // If we cannot find a location to use (merge with), then we erase the debug1612  // location to prevent debug-info driven tools from potentially reporting1613  // wrong location information.1614  if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())1615    MI.setDebugLoc(DebugLoc::getMergedLocation(MI.getDebugLoc(),1616                                               InsertPos->getDebugLoc()));1617  else1618    MI.setDebugLoc(DebugLoc());1619 1620  // Move the instruction.1621  MachineBasicBlock *ParentBlock = MI.getParent();1622  SuccToSinkTo.splice(InsertPos, ParentBlock, MI,1623                      ++MachineBasicBlock::iterator(MI));1624 1625  // Sink a copy of debug users to the insert position. Mark the original1626  // DBG_VALUE location as 'undef', indicating that any earlier variable1627  // location should be terminated as we've optimised away the value at this1628  // point.1629  for (const auto &DbgValueToSink : DbgValuesToSink) {1630    MachineInstr *DbgMI = DbgValueToSink.first;1631    MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(DbgMI);1632    SuccToSinkTo.insert(InsertPos, NewDbgMI);1633 1634    bool PropagatedAllSunkOps = true;1635    for (Register Reg : DbgValueToSink.second) {1636      if (DbgMI->hasDebugOperandForReg(Reg)) {1637        if (!attemptDebugCopyProp(MI, *DbgMI, Reg)) {1638          PropagatedAllSunkOps = false;1639          break;1640        }1641      }1642    }1643    if (!PropagatedAllSunkOps)1644      DbgMI->setDebugValueUndef();1645  }1646}1647 1648/// hasStoreBetween - check if there is store betweeen straight line blocks From1649/// and To.1650bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,1651                                     MachineBasicBlock *To, MachineInstr &MI) {1652  // Make sure From and To are in straight line which means From dominates To1653  // and To post dominates From.1654  if (!DT->dominates(From, To) || !PDT->dominates(To, From))1655    return true;1656 1657  auto BlockPair = std::make_pair(From, To);1658 1659  // Does these two blocks pair be queried before and have a definite cached1660  // result?1661  if (auto It = HasStoreCache.find(BlockPair); It != HasStoreCache.end())1662    return It->second;1663 1664  if (auto It = StoreInstrCache.find(BlockPair); It != StoreInstrCache.end())1665    return llvm::any_of(It->second, [&](MachineInstr *I) {1666      return I->mayAlias(AA, MI, false);1667    });1668 1669  bool SawStore = false;1670  bool HasAliasedStore = false;1671  DenseSet<MachineBasicBlock *> HandledBlocks;1672  DenseSet<MachineBasicBlock *> HandledDomBlocks;1673  // Go through all reachable blocks from From.1674  for (MachineBasicBlock *BB : depth_first(From)) {1675    // We insert the instruction at the start of block To, so no need to worry1676    // about stores inside To.1677    // Store in block From should be already considered when just enter function1678    // SinkInstruction.1679    if (BB == To || BB == From)1680      continue;1681 1682    // We already handle this BB in previous iteration.1683    if (HandledBlocks.count(BB))1684      continue;1685 1686    HandledBlocks.insert(BB);1687    // To post dominates BB, it must be a path from block From.1688    if (PDT->dominates(To, BB)) {1689      if (!HandledDomBlocks.count(BB))1690        HandledDomBlocks.insert(BB);1691 1692      // If this BB is too big or the block number in straight line between From1693      // and To is too big, stop searching to save compiling time.1694      if (BB->sizeWithoutDebugLargerThan(SinkLoadInstsPerBlockThreshold) ||1695          HandledDomBlocks.size() > SinkLoadBlocksThreshold) {1696        for (auto *DomBB : HandledDomBlocks) {1697          if (DomBB != BB && DT->dominates(DomBB, BB))1698            HasStoreCache[std::make_pair(DomBB, To)] = true;1699          else if (DomBB != BB && DT->dominates(BB, DomBB))1700            HasStoreCache[std::make_pair(From, DomBB)] = true;1701        }1702        HasStoreCache[BlockPair] = true;1703        return true;1704      }1705 1706      for (MachineInstr &I : *BB) {1707        // Treat as alias conservatively for a call or an ordered memory1708        // operation.1709        if (I.isCall() || I.hasOrderedMemoryRef()) {1710          for (auto *DomBB : HandledDomBlocks) {1711            if (DomBB != BB && DT->dominates(DomBB, BB))1712              HasStoreCache[std::make_pair(DomBB, To)] = true;1713            else if (DomBB != BB && DT->dominates(BB, DomBB))1714              HasStoreCache[std::make_pair(From, DomBB)] = true;1715          }1716          HasStoreCache[BlockPair] = true;1717          return true;1718        }1719 1720        if (I.mayStore()) {1721          SawStore = true;1722          // We still have chance to sink MI if all stores between are not1723          // aliased to MI.1724          // Cache all store instructions, so that we don't need to go through1725          // all From reachable blocks for next load instruction.1726          if (I.mayAlias(AA, MI, false))1727            HasAliasedStore = true;1728          StoreInstrCache[BlockPair].push_back(&I);1729        }1730      }1731    }1732  }1733  // If there is no store at all, cache the result.1734  if (!SawStore)1735    HasStoreCache[BlockPair] = false;1736  return HasAliasedStore;1737}1738 1739/// Aggressively sink instructions into cycles. This will aggressively try to1740/// sink all instructions in the top-most preheaders in an attempt to reduce RP.1741/// In particular, it will sink into multiple successor blocks without limits1742/// based on the amount of sinking, or the type of ops being sunk (so long as1743/// they are safe to sink).1744bool MachineSinking::aggressivelySinkIntoCycle(1745    MachineCycle *Cycle, MachineInstr &I,1746    DenseMap<SinkItem, MachineInstr *> &SunkInstrs) {1747  // TODO: support instructions with multiple defs1748  if (I.getNumDefs() > 1)1749    return false;1750 1751  LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Finding sink block for: " << I);1752  assert(Cycle->getCyclePreheader() && "Cycle sink needs a preheader block");1753  SmallVector<std::pair<RegSubRegPair, MachineInstr *>> Uses;1754 1755  MachineOperand &DefMO = I.getOperand(0);1756  for (MachineInstr &MI : MRI->use_instructions(DefMO.getReg())) {1757    Uses.push_back({{DefMO.getReg(), DefMO.getSubReg()}, &MI});1758  }1759 1760  for (std::pair<RegSubRegPair, MachineInstr *> Entry : Uses) {1761    MachineInstr *MI = Entry.second;1762    LLVM_DEBUG(dbgs() << "AggressiveCycleSink:   Analysing use: " << MI);1763    if (MI->isPHI()) {1764      LLVM_DEBUG(1765          dbgs() << "AggressiveCycleSink:   Not attempting to sink for PHI.\n");1766      continue;1767    }1768    // We cannot sink before the prologue1769    if (MI->isPosition() || TII->isBasicBlockPrologue(*MI)) {1770      LLVM_DEBUG(dbgs() << "AggressiveCycleSink:   Use is BasicBlock prologue, "1771                           "can't sink.\n");1772      continue;1773    }1774    if (!Cycle->contains(MI->getParent())) {1775      LLVM_DEBUG(1776          dbgs() << "AggressiveCycleSink:   Use not in cycle, can't sink.\n");1777      continue;1778    }1779 1780    MachineBasicBlock *SinkBlock = MI->getParent();1781    MachineInstr *NewMI = nullptr;1782    SinkItem MapEntry(&I, SinkBlock);1783 1784    auto SI = SunkInstrs.find(MapEntry);1785 1786    // Check for the case in which we have already sunk a copy of this1787    // instruction into the user block.1788    if (SI != SunkInstrs.end()) {1789      LLVM_DEBUG(dbgs() << "AggressiveCycleSink:   Already sunk to block: "1790                        << printMBBReference(*SinkBlock) << "\n");1791      NewMI = SI->second;1792    }1793 1794    // Create a copy of the instruction in the use block.1795    if (!NewMI) {1796      LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Sinking instruction to block: "1797                        << printMBBReference(*SinkBlock) << "\n");1798 1799      NewMI = I.getMF()->CloneMachineInstr(&I);1800      if (DefMO.getReg().isVirtual()) {1801        const TargetRegisterClass *TRC = MRI->getRegClass(DefMO.getReg());1802        Register DestReg = MRI->createVirtualRegister(TRC);1803        NewMI->substituteRegister(DefMO.getReg(), DestReg, DefMO.getSubReg(),1804                                  *TRI);1805      }1806      SinkBlock->insert(SinkBlock->SkipPHIsAndLabels(SinkBlock->begin()),1807                        NewMI);1808      SunkInstrs.insert({MapEntry, NewMI});1809    }1810 1811    // Conservatively clear any kill flags on uses of sunk instruction1812    for (MachineOperand &MO : NewMI->all_uses()) {1813      assert(MO.isReg() && MO.isUse());1814      RegsToClearKillFlags.insert(MO.getReg());1815    }1816 1817    // The instruction is moved from its basic block, so do not retain the1818    // debug information.1819    assert(!NewMI->isDebugInstr() && "Should not sink debug inst");1820    NewMI->setDebugLoc(DebugLoc());1821 1822    // Replace the use with the newly created virtual register.1823    RegSubRegPair &UseReg = Entry.first;1824    MI->substituteRegister(UseReg.Reg, NewMI->getOperand(0).getReg(),1825                           UseReg.SubReg, *TRI);1826  }1827  // If we have replaced all uses, then delete the dead instruction1828  if (I.isDead(*MRI))1829    I.eraseFromParent();1830  return true;1831}1832 1833/// SinkInstruction - Determine whether it is safe to sink the specified machine1834/// instruction out of its current block into a successor.1835bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,1836                                     AllSuccsCache &AllSuccessors) {1837  // Don't sink instructions that the target prefers not to sink.1838  if (!TII->shouldSink(MI))1839    return false;1840 1841  // Check if it's safe to move the instruction.1842  if (!MI.isSafeToMove(SawStore))1843    return false;1844 1845  // Convergent operations may not be made control-dependent on additional1846  // values.1847  if (MI.isConvergent())1848    return false;1849 1850  // Don't break implicit null checks.  This is a performance heuristic, and not1851  // required for correctness.1852  if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))1853    return false;1854 1855  // FIXME: This should include support for sinking instructions within the1856  // block they are currently in to shorten the live ranges.  We often get1857  // instructions sunk into the top of a large block, but it would be better to1858  // also sink them down before their first use in the block.  This xform has to1859  // be careful not to *increase* register pressure though, e.g. sinking1860  // "x = y + z" down if it kills y and z would increase the live ranges of y1861  // and z and only shrink the live range of x.1862 1863  bool BreakPHIEdge = false;1864  MachineBasicBlock *ParentBlock = MI.getParent();1865  MachineBasicBlock *SuccToSinkTo =1866      FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);1867 1868  // If there are no outputs, it must have side-effects.1869  if (!SuccToSinkTo)1870    return false;1871 1872  // If the instruction to move defines a dead physical register which is live1873  // when leaving the basic block, don't move it because it could turn into a1874  // "zombie" define of that preg. E.g., EFLAGS.1875  for (const MachineOperand &MO : MI.all_defs()) {1876    Register Reg = MO.getReg();1877    if (Reg == 0 || !Reg.isPhysical())1878      continue;1879    if (SuccToSinkTo->isLiveIn(Reg))1880      return false;1881  }1882 1883  LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);1884 1885  // If the block has multiple predecessors, this is a critical edge.1886  // Decide if we can sink along it or need to break the edge.1887  if (SuccToSinkTo->pred_size() > 1) {1888    // We cannot sink a load across a critical edge - there may be stores in1889    // other code paths.1890    bool TryBreak = false;1891    bool Store =1892        MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo, MI) : true;1893    if (!MI.isSafeToMove(Store)) {1894      LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");1895      TryBreak = true;1896    }1897 1898    // We don't want to sink across a critical edge if we don't dominate the1899    // successor. We could be introducing calculations to new code paths.1900    if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {1901      LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");1902      TryBreak = true;1903    }1904 1905    // Don't sink instructions into a cycle.1906    if (!TryBreak && CI->getCycle(SuccToSinkTo) &&1907        (!CI->getCycle(SuccToSinkTo)->isReducible() ||1908         CI->getCycle(SuccToSinkTo)->getHeader() == SuccToSinkTo)) {1909      LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n");1910      TryBreak = true;1911    }1912 1913    // Otherwise we are OK with sinking along a critical edge.1914    if (!TryBreak)1915      LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");1916    else {1917      // Mark this edge as to be split.1918      // If the edge can actually be split, the next iteration of the main loop1919      // will sink MI in the newly created block.1920      bool Status = PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo,1921                                              BreakPHIEdge);1922      if (!Status)1923        LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "1924                             "break critical edge\n");1925      // The instruction will not be sunk this time.1926      return false;1927    }1928  }1929 1930  if (BreakPHIEdge) {1931    // BreakPHIEdge is true if all the uses are in the successor MBB being1932    // sunken into and they are all PHI nodes. In this case, machine-sink must1933    // break the critical edge first.1934    bool Status =1935        PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);1936    if (!Status)1937      LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "1938                           "break critical edge\n");1939    // The instruction will not be sunk this time.1940    return false;1941  }1942 1943  // Determine where to insert into. Skip phi nodes.1944  MachineBasicBlock::iterator InsertPos =1945      SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());1946  if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI)) {1947    LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");1948    return false;1949  }1950 1951  // Collect debug users of any vreg that this inst defines.1952  SmallVector<MIRegs, 4> DbgUsersToSink;1953  for (auto &MO : MI.all_defs()) {1954    if (!MO.getReg().isVirtual())1955      continue;1956    auto It = SeenDbgUsers.find(MO.getReg());1957    if (It == SeenDbgUsers.end())1958      continue;1959 1960    // Sink any users that don't pass any other DBG_VALUEs for this variable.1961    auto &Users = It->second;1962    for (auto &User : Users) {1963      MachineInstr *DbgMI = User.getPointer();1964      if (User.getInt()) {1965        // This DBG_VALUE would re-order assignments. If we can't copy-propagate1966        // it, it can't be recovered. Set it undef.1967        if (!attemptDebugCopyProp(MI, *DbgMI, MO.getReg()))1968          DbgMI->setDebugValueUndef();1969      } else {1970        DbgUsersToSink.push_back(1971            {DbgMI, SmallVector<Register, 2>(1, MO.getReg())});1972      }1973    }1974  }1975 1976  // After sinking, some debug users may not be dominated any more. If possible,1977  // copy-propagate their operands. As it's expensive, don't do this if there's1978  // no debuginfo in the program.1979  if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())1980    SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);1981 1982  performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);1983 1984  // Conservatively, clear any kill flags, since it's possible that they are no1985  // longer correct.1986  // Note that we have to clear the kill flags for any register this instruction1987  // uses as we may sink over another instruction which currently kills the1988  // used registers.1989  for (MachineOperand &MO : MI.all_uses())1990    RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.1991 1992  return true;1993}1994 1995void MachineSinking::SalvageUnsunkDebugUsersOfCopy(1996    MachineInstr &MI, MachineBasicBlock *TargetBlock) {1997  assert(MI.isCopy());1998  assert(MI.getOperand(1).isReg());1999 2000  // Enumerate all users of vreg operands that are def'd. Skip those that will2001  // be sunk. For the rest, if they are not dominated by the block we will sink2002  // MI into, propagate the copy source to them.2003  SmallVector<MachineInstr *, 4> DbgDefUsers;2004  SmallVector<Register, 4> DbgUseRegs;2005  const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();2006  for (auto &MO : MI.all_defs()) {2007    if (!MO.getReg().isVirtual())2008      continue;2009    DbgUseRegs.push_back(MO.getReg());2010    for (auto &User : MRI.use_instructions(MO.getReg())) {2011      if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))2012        continue;2013 2014      // If is in same block, will either sink or be use-before-def.2015      if (User.getParent() == MI.getParent())2016        continue;2017 2018      assert(User.hasDebugOperandForReg(MO.getReg()) &&2019             "DBG_VALUE user of vreg, but has no operand for it?");2020      DbgDefUsers.push_back(&User);2021    }2022  }2023 2024  // Point the users of this copy that are no longer dominated, at the source2025  // of the copy.2026  for (auto *User : DbgDefUsers) {2027    for (auto &Reg : DbgUseRegs) {2028      for (auto &DbgOp : User->getDebugOperandsForReg(Reg)) {2029        DbgOp.setReg(MI.getOperand(1).getReg());2030        DbgOp.setSubReg(MI.getOperand(1).getSubReg());2031      }2032    }2033  }2034}2035 2036//===----------------------------------------------------------------------===//2037// This pass is not intended to be a replacement or a complete alternative2038// for the pre-ra machine sink pass. It is only designed to sink COPY2039// instructions which should be handled after RA.2040//2041// This pass sinks COPY instructions into a successor block, if the COPY is not2042// used in the current block and the COPY is live-in to a single successor2043// (i.e., doesn't require the COPY to be duplicated).  This avoids executing the2044// copy on paths where their results aren't needed.  This also exposes2045// additional opportunites for dead copy elimination and shrink wrapping.2046//2047// These copies were either not handled by or are inserted after the MachineSink2048// pass. As an example of the former case, the MachineSink pass cannot sink2049// COPY instructions with allocatable source registers; for AArch64 these type2050// of copy instructions are frequently used to move function parameters (PhyReg)2051// into virtual registers in the entry block.2052//2053// For the machine IR below, this pass will sink %w19 in the entry into its2054// successor (%bb.1) because %w19 is only live-in in %bb.1.2055// %bb.0:2056//   %wzr = SUBSWri %w1, 12057//   %w19 = COPY %w02058//   Bcc 11, %bb.22059// %bb.1:2060//   Live Ins: %w192061//   BL @fun2062//   %w0 = ADDWrr %w0, %w192063//   RET %w02064// %bb.2:2065//   %w0 = COPY %wzr2066//   RET %w02067// As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be2068// able to see %bb.0 as a candidate.2069//===----------------------------------------------------------------------===//2070namespace {2071 2072class PostRAMachineSinkingImpl {2073  /// Track which register units have been modified and used.2074  LiveRegUnits ModifiedRegUnits, UsedRegUnits;2075 2076  /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an2077  /// entry in this map for each unit it touches. The DBG_VALUE's entry2078  /// consists of a pointer to the instruction itself, and a vector of registers2079  /// referred to by the instruction that overlap the key register unit.2080  DenseMap<MCRegUnit, SmallVector<MIRegs, 2>> SeenDbgInstrs;2081 2082  /// Sink Copy instructions unused in the same block close to their uses in2083  /// successors.2084  bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,2085                     const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);2086 2087public:2088  bool run(MachineFunction &MF);2089};2090 2091class PostRAMachineSinkingLegacy : public MachineFunctionPass {2092public:2093  bool runOnMachineFunction(MachineFunction &MF) override;2094 2095  static char ID;2096  PostRAMachineSinkingLegacy() : MachineFunctionPass(ID) {}2097  StringRef getPassName() const override { return "PostRA Machine Sink"; }2098 2099  void getAnalysisUsage(AnalysisUsage &AU) const override {2100    AU.setPreservesCFG();2101    MachineFunctionPass::getAnalysisUsage(AU);2102  }2103 2104  MachineFunctionProperties getRequiredProperties() const override {2105    return MachineFunctionProperties().setNoVRegs();2106  }2107};2108 2109} // namespace2110 2111char PostRAMachineSinkingLegacy::ID = 0;2112char &llvm::PostRAMachineSinkingID = PostRAMachineSinkingLegacy::ID;2113 2114INITIALIZE_PASS(PostRAMachineSinkingLegacy, "postra-machine-sink",2115                "PostRA Machine Sink", false, false)2116 2117static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, Register Reg,2118                                  const TargetRegisterInfo *TRI) {2119  LiveRegUnits LiveInRegUnits(*TRI);2120  LiveInRegUnits.addLiveIns(MBB);2121  return !LiveInRegUnits.available(Reg);2122}2123 2124static MachineBasicBlock *2125getSingleLiveInSuccBB(MachineBasicBlock &CurBB,2126                      const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,2127                      Register Reg, const TargetRegisterInfo *TRI) {2128  // Try to find a single sinkable successor in which Reg is live-in.2129  MachineBasicBlock *BB = nullptr;2130  for (auto *SI : SinkableBBs) {2131    if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {2132      // If BB is set here, Reg is live-in to at least two sinkable successors,2133      // so quit.2134      if (BB)2135        return nullptr;2136      BB = SI;2137    }2138  }2139  // Reg is not live-in to any sinkable successors.2140  if (!BB)2141    return nullptr;2142 2143  // Check if any register aliased with Reg is live-in in other successors.2144  for (auto *SI : CurBB.successors()) {2145    if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))2146      return nullptr;2147  }2148  return BB;2149}2150 2151static MachineBasicBlock *2152getSingleLiveInSuccBB(MachineBasicBlock &CurBB,2153                      const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,2154                      ArrayRef<Register> DefedRegsInCopy,2155                      const TargetRegisterInfo *TRI) {2156  MachineBasicBlock *SingleBB = nullptr;2157  for (auto DefReg : DefedRegsInCopy) {2158    MachineBasicBlock *BB =2159        getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);2160    if (!BB || (SingleBB && SingleBB != BB))2161      return nullptr;2162    SingleBB = BB;2163  }2164  return SingleBB;2165}2166 2167static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,2168                           const SmallVectorImpl<unsigned> &UsedOpsInCopy,2169                           const LiveRegUnits &UsedRegUnits,2170                           const TargetRegisterInfo *TRI) {2171  for (auto U : UsedOpsInCopy) {2172    MachineOperand &MO = MI->getOperand(U);2173    Register SrcReg = MO.getReg();2174    if (!UsedRegUnits.available(SrcReg)) {2175      MachineBasicBlock::iterator NI = std::next(MI->getIterator());2176      for (MachineInstr &UI : make_range(NI, CurBB.end())) {2177        if (UI.killsRegister(SrcReg, TRI)) {2178          UI.clearRegisterKills(SrcReg, TRI);2179          MO.setIsKill(true);2180          break;2181        }2182      }2183    }2184  }2185}2186 2187static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,2188                         const SmallVectorImpl<unsigned> &UsedOpsInCopy,2189                         const SmallVectorImpl<Register> &DefedRegsInCopy) {2190  for (Register DefReg : DefedRegsInCopy)2191    SuccBB->removeLiveInOverlappedWith(DefReg);2192 2193  for (auto U : UsedOpsInCopy)2194    SuccBB->addLiveIn(MI->getOperand(U).getReg());2195  SuccBB->sortUniqueLiveIns();2196}2197 2198static bool hasRegisterDependency(MachineInstr *MI,2199                                  SmallVectorImpl<unsigned> &UsedOpsInCopy,2200                                  SmallVectorImpl<Register> &DefedRegsInCopy,2201                                  LiveRegUnits &ModifiedRegUnits,2202                                  LiveRegUnits &UsedRegUnits) {2203  bool HasRegDependency = false;2204  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {2205    MachineOperand &MO = MI->getOperand(i);2206    if (!MO.isReg())2207      continue;2208    Register Reg = MO.getReg();2209    if (!Reg)2210      continue;2211    if (MO.isDef()) {2212      if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {2213        HasRegDependency = true;2214        break;2215      }2216      DefedRegsInCopy.push_back(Reg);2217 2218      // FIXME: instead of isUse(), readsReg() would be a better fix here,2219      // For example, we can ignore modifications in reg with undef. However,2220      // it's not perfectly clear if skipping the internal read is safe in all2221      // other targets.2222    } else if (MO.isUse()) {2223      if (!ModifiedRegUnits.available(Reg)) {2224        HasRegDependency = true;2225        break;2226      }2227      UsedOpsInCopy.push_back(i);2228    }2229  }2230  return HasRegDependency;2231}2232 2233bool PostRAMachineSinkingImpl::tryToSinkCopy(MachineBasicBlock &CurBB,2234                                             MachineFunction &MF,2235                                             const TargetRegisterInfo *TRI,2236                                             const TargetInstrInfo *TII) {2237  SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;2238  // FIXME: For now, we sink only to a successor which has a single predecessor2239  // so that we can directly sink COPY instructions to the successor without2240  // adding any new block or branch instruction.2241  for (MachineBasicBlock *SI : CurBB.successors())2242    if (!SI->livein_empty() && SI->pred_size() == 1)2243      SinkableBBs.insert(SI);2244 2245  if (SinkableBBs.empty())2246    return false;2247 2248  bool Changed = false;2249 2250  // Track which registers have been modified and used between the end of the2251  // block and the current instruction.2252  ModifiedRegUnits.clear();2253  UsedRegUnits.clear();2254  SeenDbgInstrs.clear();2255 2256  for (MachineInstr &MI : llvm::make_early_inc_range(llvm::reverse(CurBB))) {2257    // Track the operand index for use in Copy.2258    SmallVector<unsigned, 2> UsedOpsInCopy;2259    // Track the register number defed in Copy.2260    SmallVector<Register, 2> DefedRegsInCopy;2261 2262    // We must sink this DBG_VALUE if its operand is sunk. To avoid searching2263    // for DBG_VALUEs later, record them when they're encountered.2264    if (MI.isDebugValue() && !MI.isDebugRef()) {2265      SmallDenseMap<MCRegUnit, SmallVector<Register, 2>, 4> MIUnits;2266      bool IsValid = true;2267      for (MachineOperand &MO : MI.debug_operands()) {2268        if (MO.isReg() && MO.getReg().isPhysical()) {2269          // Bail if we can already tell the sink would be rejected, rather2270          // than needlessly accumulating lots of DBG_VALUEs.2271          if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,2272                                    ModifiedRegUnits, UsedRegUnits)) {2273            IsValid = false;2274            break;2275          }2276 2277          // Record debug use of each reg unit.2278          for (MCRegUnit Unit : TRI->regunits(MO.getReg()))2279            MIUnits[Unit].push_back(MO.getReg());2280        }2281      }2282      if (IsValid) {2283        for (auto &RegOps : MIUnits)2284          SeenDbgInstrs[RegOps.first].emplace_back(&MI,2285                                                   std::move(RegOps.second));2286      }2287      continue;2288    }2289 2290    // Don't postRASink instructions that the target prefers not to sink.2291    if (!TII->shouldPostRASink(MI))2292      continue;2293 2294    if (MI.isDebugOrPseudoInstr())2295      continue;2296 2297    // Do not move any instruction across function call.2298    if (MI.isCall())2299      return false;2300 2301    if (!MI.isCopy() || !MI.getOperand(0).isRenamable()) {2302      LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,2303                                        TRI);2304      continue;2305    }2306 2307    // Don't sink the COPY if it would violate a register dependency.2308    if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,2309                              ModifiedRegUnits, UsedRegUnits)) {2310      LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,2311                                        TRI);2312      continue;2313    }2314    assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&2315           "Unexpect SrcReg or DefReg");2316    MachineBasicBlock *SuccBB =2317        getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);2318    // Don't sink if we cannot find a single sinkable successor in which Reg2319    // is live-in.2320    if (!SuccBB) {2321      LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,2322                                        TRI);2323      continue;2324    }2325    assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&2326           "Unexpected predecessor");2327 2328    // Collect DBG_VALUEs that must sink with this copy. We've previously2329    // recorded which reg units that DBG_VALUEs read, if this instruction2330    // writes any of those units then the corresponding DBG_VALUEs must sink.2331    MapVector<MachineInstr *, MIRegs::second_type> DbgValsToSinkMap;2332    for (auto &MO : MI.all_defs()) {2333      for (MCRegUnit Unit : TRI->regunits(MO.getReg())) {2334        for (const auto &MIRegs : SeenDbgInstrs.lookup(Unit)) {2335          auto &Regs = DbgValsToSinkMap[MIRegs.first];2336          llvm::append_range(Regs, MIRegs.second);2337        }2338      }2339    }2340    auto DbgValsToSink = DbgValsToSinkMap.takeVector();2341 2342    LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);2343 2344    MachineBasicBlock::iterator InsertPos =2345        SuccBB->SkipPHIsAndLabels(SuccBB->begin());2346    if (blockPrologueInterferes(SuccBB, InsertPos, MI, TRI, TII, nullptr)) {2347      LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,2348                                        TRI);2349      LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");2350      continue;2351    }2352 2353    // Clear the kill flag if SrcReg is killed between MI and the end of the2354    // block.2355    clearKillFlags(&MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);2356    performSink(MI, *SuccBB, InsertPos, DbgValsToSink);2357    updateLiveIn(&MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);2358 2359    Changed = true;2360    ++NumPostRACopySink;2361  }2362  return Changed;2363}2364 2365bool PostRAMachineSinkingImpl::run(MachineFunction &MF) {2366  bool Changed = false;2367  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();2368  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();2369 2370  ModifiedRegUnits.init(*TRI);2371  UsedRegUnits.init(*TRI);2372  for (auto &BB : MF)2373    Changed |= tryToSinkCopy(BB, MF, TRI, TII);2374 2375  return Changed;2376}2377 2378bool PostRAMachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {2379  if (skipFunction(MF.getFunction()))2380    return false;2381 2382  return PostRAMachineSinkingImpl().run(MF);2383}2384 2385PreservedAnalyses2386PostRAMachineSinkingPass::run(MachineFunction &MF,2387                              MachineFunctionAnalysisManager &MFAM) {2388  MFPropsModifier _(*this, MF);2389 2390  if (!PostRAMachineSinkingImpl().run(MF))2391    return PreservedAnalyses::all();2392 2393  PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();2394  PA.preserveSet<CFGAnalyses>();2395  return PA;2396}2397