contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp

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