LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineSink.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 327 330 99.1 %
Date: 2018-07-13 00:08:38 Functions: 38 38 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- MachineSink.cpp - Sinking for machine instructions -----------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This pass moves instructions into successor blocks when possible, so that
      11             : // they aren't executed on paths where their results aren't needed.
      12             : //
      13             : // This pass is not intended to be a replacement or a complete alternative
      14             : // for an LLVM-IR-level sinking pass. It is only designed to sink simple
      15             : // constructs that are not exposed before lowering and instruction selection.
      16             : //
      17             : //===----------------------------------------------------------------------===//
      18             : 
      19             : #include "llvm/ADT/SetVector.h"
      20             : #include "llvm/ADT/SmallSet.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/ADT/SparseBitVector.h"
      23             : #include "llvm/ADT/Statistic.h"
      24             : #include "llvm/Analysis/AliasAnalysis.h"
      25             : #include "llvm/CodeGen/MachineBasicBlock.h"
      26             : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
      27             : #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
      28             : #include "llvm/CodeGen/MachineDominators.h"
      29             : #include "llvm/CodeGen/MachineFunction.h"
      30             : #include "llvm/CodeGen/MachineFunctionPass.h"
      31             : #include "llvm/CodeGen/MachineInstr.h"
      32             : #include "llvm/CodeGen/MachineLoopInfo.h"
      33             : #include "llvm/CodeGen/MachineOperand.h"
      34             : #include "llvm/CodeGen/MachinePostDominators.h"
      35             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      36             : #include "llvm/CodeGen/TargetInstrInfo.h"
      37             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      38             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      39             : #include "llvm/IR/BasicBlock.h"
      40             : #include "llvm/IR/LLVMContext.h"
      41             : #include "llvm/IR/DebugInfoMetadata.h"
      42             : #include "llvm/Pass.h"
      43             : #include "llvm/Support/BranchProbability.h"
      44             : #include "llvm/Support/CommandLine.h"
      45             : #include "llvm/Support/Debug.h"
      46             : #include "llvm/Support/raw_ostream.h"
      47             : #include <algorithm>
      48             : #include <cassert>
      49             : #include <cstdint>
      50             : #include <map>
      51             : #include <utility>
      52             : #include <vector>
      53             : 
      54             : using namespace llvm;
      55             : 
      56             : #define DEBUG_TYPE "machine-sink"
      57             : 
      58             : static cl::opt<bool>
      59       99743 : SplitEdges("machine-sink-split",
      60       99743 :            cl::desc("Split critical edges during machine sinking"),
      61      299229 :            cl::init(true), cl::Hidden);
      62             : 
      63             : static cl::opt<bool>
      64       99743 : UseBlockFreqInfo("machine-sink-bfi",
      65       99743 :            cl::desc("Use block frequency info to find successors to sink"),
      66      299229 :            cl::init(true), cl::Hidden);
      67             : 
      68       99743 : static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
      69             :     "machine-sink-split-probability-threshold",
      70       99743 :     cl::desc(
      71             :         "Percentage threshold for splitting single-instruction critical edge. "
      72             :         "If the branch threshold is higher than this threshold, we allow "
      73             :         "speculative execution of up to 1 instruction to avoid branching to "
      74             :         "splitted critical edge"),
      75      299229 :     cl::init(40), cl::Hidden);
      76             : 
      77             : STATISTIC(NumSunk,      "Number of machine instructions sunk");
      78             : STATISTIC(NumSplit,     "Number of critical edges split");
      79             : STATISTIC(NumCoalesces, "Number of copies coalesced");
      80             : STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
      81             : 
      82             : namespace {
      83             : 
      84       57453 :   class MachineSinking : public MachineFunctionPass {
      85             :     const TargetInstrInfo *TII;
      86             :     const TargetRegisterInfo *TRI;
      87             :     MachineRegisterInfo  *MRI;     // Machine register information
      88             :     MachineDominatorTree *DT;      // Machine dominator tree
      89             :     MachinePostDominatorTree *PDT; // Machine post dominator tree
      90             :     MachineLoopInfo *LI;
      91             :     const MachineBlockFrequencyInfo *MBFI;
      92             :     const MachineBranchProbabilityInfo *MBPI;
      93             :     AliasAnalysis *AA;
      94             : 
      95             :     // Remember which edges have been considered for breaking.
      96             :     SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
      97             :     CEBCandidates;
      98             :     // Remember which edges we are about to split.
      99             :     // This is different from CEBCandidates since those edges
     100             :     // will be split.
     101             :     SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
     102             : 
     103             :     SparseBitVector<> RegsToClearKillFlags;
     104             : 
     105             :     using AllSuccsCache =
     106             :         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
     107             : 
     108             :   public:
     109             :     static char ID; // Pass identification
     110             : 
     111       19255 :     MachineSinking() : MachineFunctionPass(ID) {
     112       19255 :       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     113       19255 :     }
     114             : 
     115             :     bool runOnMachineFunction(MachineFunction &MF) override;
     116             : 
     117       19110 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
     118       19110 :       AU.setPreservesCFG();
     119       19110 :       MachineFunctionPass::getAnalysisUsage(AU);
     120             :       AU.addRequired<AAResultsWrapperPass>();
     121             :       AU.addRequired<MachineDominatorTree>();
     122             :       AU.addRequired<MachinePostDominatorTree>();
     123             :       AU.addRequired<MachineLoopInfo>();
     124             :       AU.addRequired<MachineBranchProbabilityInfo>();
     125             :       AU.addPreserved<MachineDominatorTree>();
     126             :       AU.addPreserved<MachinePostDominatorTree>();
     127             :       AU.addPreserved<MachineLoopInfo>();
     128       19110 :       if (UseBlockFreqInfo)
     129             :         AU.addRequired<MachineBlockFrequencyInfo>();
     130       19110 :     }
     131             : 
     132      184104 :     void releaseMemory() override {
     133             :       CEBCandidates.clear();
     134      184104 :     }
     135             : 
     136             :   private:
     137             :     bool ProcessBlock(MachineBasicBlock &MBB);
     138             :     bool isWorthBreakingCriticalEdge(MachineInstr &MI,
     139             :                                      MachineBasicBlock *From,
     140             :                                      MachineBasicBlock *To);
     141             : 
     142             :     /// Postpone the splitting of the given critical
     143             :     /// edge (\p From, \p To).
     144             :     ///
     145             :     /// We do not split the edges on the fly. Indeed, this invalidates
     146             :     /// the dominance information and thus triggers a lot of updates
     147             :     /// of that information underneath.
     148             :     /// Instead, we postpone all the splits after each iteration of
     149             :     /// the main loop. That way, the information is at least valid
     150             :     /// for the lifetime of an iteration.
     151             :     ///
     152             :     /// \return True if the edge is marked as toSplit, false otherwise.
     153             :     /// False can be returned if, for instance, this is not profitable.
     154             :     bool PostponeSplitCriticalEdge(MachineInstr &MI,
     155             :                                    MachineBasicBlock *From,
     156             :                                    MachineBasicBlock *To,
     157             :                                    bool BreakPHIEdge);
     158             :     bool SinkInstruction(MachineInstr &MI, bool &SawStore,
     159             : 
     160             :                          AllSuccsCache &AllSuccessors);
     161             :     bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
     162             :                                  MachineBasicBlock *DefMBB,
     163             :                                  bool &BreakPHIEdge, bool &LocalUse) const;
     164             :     MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
     165             :                bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
     166             :     bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
     167             :                               MachineBasicBlock *MBB,
     168             :                               MachineBasicBlock *SuccToSinkTo,
     169             :                               AllSuccsCache &AllSuccessors);
     170             : 
     171             :     bool PerformTrivialForwardCoalescing(MachineInstr &MI,
     172             :                                          MachineBasicBlock *MBB);
     173             : 
     174             :     SmallVector<MachineBasicBlock *, 4> &
     175             :     GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
     176             :                            AllSuccsCache &AllSuccessors) const;
     177             :   };
     178             : 
     179             : } // end anonymous namespace
     180             : 
     181             : char MachineSinking::ID = 0;
     182             : 
     183             : char &llvm::MachineSinkingID = MachineSinking::ID;
     184             : 
     185       26316 : INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
     186             :                       "Machine code sinking", false, false)
     187       26316 : INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
     188       26316 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     189       26316 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     190       26316 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     191      185120 : INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
     192             :                     "Machine code sinking", false, false)
     193             : 
     194     2899844 : bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
     195             :                                                      MachineBasicBlock *MBB) {
     196     2899844 :   if (!MI.isCopy())
     197             :     return false;
     198             : 
     199      441220 :   unsigned SrcReg = MI.getOperand(1).getReg();
     200      441220 :   unsigned DstReg = MI.getOperand(0).getReg();
     201      342548 :   if (!TargetRegisterInfo::isVirtualRegister(SrcReg) ||
     202      477101 :       !TargetRegisterInfo::isVirtualRegister(DstReg) ||
     203       35881 :       !MRI->hasOneNonDBGUse(SrcReg))
     204             :     return false;
     205             : 
     206       21823 :   const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
     207             :   const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
     208       21823 :   if (SRC != DRC)
     209             :     return false;
     210             : 
     211       13433 :   MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
     212             :   if (DefMI->isCopyLike())
     213             :     return false;
     214             :   LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
     215             :   LLVM_DEBUG(dbgs() << "*** to: " << MI);
     216         562 :   MRI->replaceRegWith(DstReg, SrcReg);
     217         562 :   MI.eraseFromParent();
     218             : 
     219             :   // Conservatively, clear any kill flags, since it's possible that they are no
     220             :   // longer correct.
     221         562 :   MRI->clearKillFlags(SrcReg);
     222             : 
     223             :   ++NumCoalesces;
     224             :   return true;
     225             : }
     226             : 
     227             : /// AllUsesDominatedByBlock - Return true if all uses of the specified register
     228             : /// occur in blocks dominated by the specified block. If any use is in the
     229             : /// definition block, then return false since it is never legal to move def
     230             : /// after uses.
     231             : bool
     232      877780 : MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
     233             :                                         MachineBasicBlock *MBB,
     234             :                                         MachineBasicBlock *DefMBB,
     235             :                                         bool &BreakPHIEdge,
     236             :                                         bool &LocalUse) const {
     237             :   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
     238             :          "Only makes sense for vregs");
     239             : 
     240             :   // Ignore debug uses because debug info doesn't affect the code.
     241     1755560 :   if (MRI->use_nodbg_empty(Reg))
     242             :     return true;
     243             : 
     244             :   // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
     245             :   // into and they are all PHI nodes. In this case, machine-sink must break
     246             :   // the critical edge first. e.g.
     247             :   //
     248             :   // %bb.1: derived from LLVM BB %bb4.preheader
     249             :   //   Predecessors according to CFG: %bb.0
     250             :   //     ...
     251             :   //     %reg16385 = DEC64_32r %reg16437, implicit-def dead %eflags
     252             :   //     ...
     253             :   //     JE_4 <%bb.37>, implicit %eflags
     254             :   //   Successors according to CFG: %bb.37 %bb.2
     255             :   //
     256             :   // %bb.2: derived from LLVM BB %bb.nph
     257             :   //   Predecessors according to CFG: %bb.0 %bb.1
     258             :   //     %reg16386 = PHI %reg16434, %bb.0, %reg16385, %bb.1
     259      835365 :   BreakPHIEdge = true;
     260     1688007 :   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
     261      839492 :     MachineInstr *UseInst = MO.getParent();
     262      839492 :     unsigned OpNo = &MO - &UseInst->getOperand(0);
     263      839492 :     MachineBasicBlock *UseBlock = UseInst->getParent();
     264      858119 :     if (!(UseBlock == MBB && UseInst->isPHI() &&
     265       37254 :           UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
     266      822215 :       BreakPHIEdge = false;
     267             :       break;
     268             :     }
     269             :   }
     270      835365 :   if (BreakPHIEdge)
     271             :     return true;
     272             : 
     273     1758260 :   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
     274             :     // Determine the block of the use.
     275      877843 :     MachineInstr *UseInst = MO.getParent();
     276      877843 :     unsigned OpNo = &MO - &UseInst->getOperand(0);
     277      877843 :     MachineBasicBlock *UseBlock = UseInst->getParent();
     278             :     if (UseInst->isPHI()) {
     279             :       // PHI nodes use the operand in the predecessor block, not the block with
     280             :       // the PHI.
     281       75704 :       UseBlock = UseInst->getOperand(OpNo+1).getMBB();
     282      839991 :     } else if (UseBlock == DefMBB) {
     283      671441 :       LocalUse = true;
     284             :       return false;
     285             :     }
     286             : 
     287             :     // Check that it dominates.
     288      412804 :     if (!DT->dominates(MBB, UseBlock))
     289             :       return false;
     290             :   }
     291             : 
     292             :   return true;
     293             : }
     294             : 
     295      184085 : bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
     296      184085 :   if (skipFunction(MF.getFunction()))
     297             :     return false;
     298             : 
     299             :   LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
     300             : 
     301      183929 :   TII = MF.getSubtarget().getInstrInfo();
     302      183929 :   TRI = MF.getSubtarget().getRegisterInfo();
     303      183929 :   MRI = &MF.getRegInfo();
     304      183929 :   DT = &getAnalysis<MachineDominatorTree>();
     305      183929 :   PDT = &getAnalysis<MachinePostDominatorTree>();
     306      183929 :   LI = &getAnalysis<MachineLoopInfo>();
     307      183929 :   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
     308      183929 :   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
     309      367856 :   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     310             : 
     311             :   bool EverMadeChange = false;
     312             : 
     313             :   while (true) {
     314             :     bool MadeChange = false;
     315             : 
     316             :     // Process all basic blocks.
     317             :     CEBCandidates.clear();
     318             :     ToSplit.clear();
     319      742631 :     for (auto &MBB: MF)
     320      552333 :       MadeChange |= ProcessBlock(MBB);
     321             : 
     322             :     // If we have anything we marked as toSplit, split it now.
     323      193975 :     for (auto &Pair : ToSplit) {
     324        3677 :       auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
     325        3677 :       if (NewSucc != nullptr) {
     326             :         LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
     327             :                           << printMBBReference(*Pair.first) << " -- "
     328             :                           << printMBBReference(*NewSucc) << " -- "
     329             :                           << printMBBReference(*Pair.second) << '\n');
     330             :         MadeChange = true;
     331             :         ++NumSplit;
     332             :       } else
     333             :         LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
     334             :     }
     335             :     // If this iteration over the code changed anything, keep iterating.
     336      190298 :     if (!MadeChange) break;
     337             :     EverMadeChange = true;
     338             :   }
     339             : 
     340             :   // Now clear any kill flags for recorded registers.
     341      198108 :   for (auto I : RegsToClearKillFlags)
     342       14179 :     MRI->clearKillFlags(I);
     343             :   RegsToClearKillFlags.clear();
     344             : 
     345      183929 :   return EverMadeChange;
     346             : }
     347             : 
     348      552333 : bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
     349             :   // Can't sink anything out of a block that has less than two successors.
     350      725718 :   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
     351             : 
     352             :   // Don't bother sinking code out of unreachable blocks. In addition to being
     353             :   // unprofitable, it can also lead to infinite looping, because in an
     354             :   // unreachable loop there may be nowhere to stop.
     355      346770 :   if (!DT->isReachableFromEntry(&MBB)) return false;
     356             : 
     357             :   bool MadeChange = false;
     358             : 
     359             :   // Cache all successors, sorted by frequency info and loop depth.
     360             :   AllSuccsCache AllSuccessors;
     361             : 
     362             :   // Walk the basic block bottom-up.  Remember if we saw a store.
     363      173384 :   MachineBasicBlock::iterator I = MBB.end();
     364             :   --I;
     365      173384 :   bool ProcessedBegin, SawStore = false;
     366             :   do {
     367             :     MachineInstr &MI = *I;  // The instruction to sink.
     368             : 
     369             :     // Predecrement I (if it's not begin) so that it isn't invalidated by
     370             :     // sinking.
     371             :     ProcessedBegin = I == MBB.begin();
     372     2979600 :     if (!ProcessedBegin)
     373             :       --I;
     374             : 
     375       79756 :     if (MI.isDebugInstr())
     376       79756 :       continue;
     377             : 
     378     2899844 :     bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
     379     2900406 :     if (Joined) {
     380             :       MadeChange = true;
     381         562 :       continue;
     382             :     }
     383             : 
     384     2899282 :     if (SinkInstruction(MI, SawStore, AllSuccessors)) {
     385             :       ++NumSunk;
     386             :       MadeChange = true;
     387             :     }
     388             : 
     389             :     // If we just processed the first instruction in the block, we're done.
     390     2979600 :   } while (!ProcessedBegin);
     391             : 
     392             :   return MadeChange;
     393             : }
     394             : 
     395        9746 : bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
     396             :                                                  MachineBasicBlock *From,
     397             :                                                  MachineBasicBlock *To) {
     398             :   // FIXME: Need much better heuristics.
     399             : 
     400             :   // If the pass has already considered breaking this edge (during this pass
     401             :   // through the function), then let's go ahead and break it. This means
     402             :   // sinking multiple "cheap" instructions into the same block.
     403        9746 :   if (!CEBCandidates.insert(std::make_pair(From, To)).second)
     404             :     return true;
     405             : 
     406        7343 :   if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
     407             :     return true;
     408             : 
     409        7046 :   if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
     410             :       BranchProbability(SplitEdgeProbabilityThreshold, 100))
     411             :     return true;
     412             : 
     413             :   // MI is cheap, we probably don't want to break the critical edge for it.
     414             :   // However, if this would allow some definitions of its source operands
     415             :   // to be sunk then it's probably worth it.
     416       14968 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     417        5294 :     const MachineOperand &MO = MI.getOperand(i);
     418       13983 :     if (!MO.isReg() || !MO.isUse())
     419        4137 :       continue;
     420        1157 :     unsigned Reg = MO.getReg();
     421        1186 :     if (Reg == 0)
     422          29 :       continue;
     423             : 
     424             :     // We don't move live definitions of physical registers,
     425             :     // so sinking their uses won't enable any opportunities.
     426        1128 :     if (TargetRegisterInfo::isPhysicalRegister(Reg))
     427          21 :       continue;
     428             : 
     429             :     // If this instruction is the only user of a virtual register,
     430             :     // check if breaking the edge will enable sinking
     431             :     // both this instruction and the defining instruction.
     432        1107 :     if (MRI->hasOneNonDBGUse(Reg)) {
     433             :       // If the definition resides in same MBB,
     434             :       // claim it's likely we can sink these together.
     435             :       // If definition resides elsewhere, we aren't
     436             :       // blocking it from being sunk so don't break the edge.
     437         473 :       MachineInstr *DefMI = MRI->getVRegDef(Reg);
     438         473 :       if (DefMI->getParent() == MI.getParent())
     439             :         return true;
     440             :     }
     441             :   }
     442             : 
     443             :   return false;
     444             : }
     445             : 
     446        9746 : bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
     447             :                                                MachineBasicBlock *FromBB,
     448             :                                                MachineBasicBlock *ToBB,
     449             :                                                bool BreakPHIEdge) {
     450        9746 :   if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
     451             :     return false;
     452             : 
     453             :   // Avoid breaking back edge. From == To means backedge for single BB loop.
     454        7556 :   if (!SplitEdges || FromBB == ToBB)
     455             :     return false;
     456             : 
     457             :   // Check for backedges of more "complex" loops.
     458       30067 :   if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
     459        7399 :       LI->isLoopHeader(ToBB))
     460             :     return false;
     461             : 
     462             :   // It's not always legal to break critical edges and sink the computation
     463             :   // to the edge.
     464             :   //
     465             :   // %bb.1:
     466             :   // v1024
     467             :   // Beq %bb.3
     468             :   // <fallthrough>
     469             :   // %bb.2:
     470             :   // ... no uses of v1024
     471             :   // <fallthrough>
     472             :   // %bb.3:
     473             :   // ...
     474             :   //       = v1024
     475             :   //
     476             :   // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
     477             :   //
     478             :   // %bb.1:
     479             :   // ...
     480             :   // Bne %bb.2
     481             :   // %bb.4:
     482             :   // v1024 =
     483             :   // B %bb.3
     484             :   // %bb.2:
     485             :   // ... no uses of v1024
     486             :   // <fallthrough>
     487             :   // %bb.3:
     488             :   // ...
     489             :   //       = v1024
     490             :   //
     491             :   // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
     492             :   // flow. We need to ensure the new basic block where the computation is
     493             :   // sunk to dominates all the uses.
     494             :   // It's only legal to break critical edge and sink the computation to the
     495             :   // new block if all the predecessors of "To", except for "From", are
     496             :   // not dominated by "From". Given SSA property, this means these
     497             :   // predecessors are dominated by "To".
     498             :   //
     499             :   // There is no need to do this check if all the uses are PHI nodes. PHI
     500             :   // sources are only defined on the specific predecessor edges.
     501        5235 :   if (!BreakPHIEdge) {
     502             :     for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
     503         321 :            E = ToBB->pred_end(); PI != E; ++PI) {
     504         318 :       if (*PI == FromBB)
     505          98 :         continue;
     506         440 :       if (!DT->dominates(ToBB, *PI))
     507             :         return false;
     508             :     }
     509             :   }
     510             : 
     511        5042 :   ToSplit.insert(std::make_pair(FromBB, ToBB));
     512             :   
     513        5042 :   return true;
     514             : }
     515             : 
     516             : /// collectDebgValues - Scan instructions following MI and collect any
     517             : /// matching DBG_VALUEs.
     518       27977 : static void collectDebugValues(MachineInstr &MI,
     519             :                                SmallVectorImpl<MachineInstr *> &DbgValues) {
     520             :   DbgValues.clear();
     521       55954 :   if (!MI.getOperand(0).isReg())
     522       27924 :     return;
     523             : 
     524             :   MachineBasicBlock::iterator DI = MI; ++DI;
     525       27975 :   for (MachineBasicBlock::iterator DE = MI.getParent()->end();
     526       32249 :        DI != DE; ++DI) {
     527       32196 :     if (!DI->isDebugValue())
     528             :       return;
     529       12695 :     if (DI->getOperand(0).isReg() &&
     530        4147 :         DI->getOperand(0).getReg() == MI.getOperand(0).getReg())
     531        3248 :       DbgValues.push_back(&*DI);
     532             :   }
     533             : }
     534             : 
     535             : /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
     536      113763 : bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
     537             :                                           MachineBasicBlock *MBB,
     538             :                                           MachineBasicBlock *SuccToSinkTo,
     539             :                                           AllSuccsCache &AllSuccessors) {
     540             :   assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
     541             : 
     542      113763 :   if (MBB == SuccToSinkTo)
     543             :     return false;
     544             : 
     545             :   // It is profitable if SuccToSinkTo does not post dominate current block.
     546      218988 :   if (!PDT->dominates(SuccToSinkTo, MBB))
     547             :     return true;
     548             : 
     549             :   // It is profitable to sink an instruction from a deeper loop to a shallower
     550             :   // loop, even if the latter post-dominates the former (PR21115).
     551       52212 :   if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
     552             :     return true;
     553             : 
     554             :   // Check if only use in post dominated block is PHI instruction.
     555             :   bool NonPHIUse = false;
     556       73710 :   for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
     557       17730 :     MachineBasicBlock *UseBlock = UseInst.getParent();
     558       17730 :     if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
     559             :       NonPHIUse = true;
     560             :   }
     561       12750 :   if (!NonPHIUse)
     562             :     return true;
     563             : 
     564             :   // If SuccToSinkTo post dominates then also it may be profitable if MI
     565             :   // can further profitably sinked into another block in next round.
     566        4753 :   bool BreakPHIEdge = false;
     567             :   // FIXME - If finding successor is compile time expensive then cache results.
     568        4753 :   if (MachineBasicBlock *MBB2 =
     569        4753 :           FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
     570           0 :     return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
     571             : 
     572             :   // If SuccToSinkTo is final destination and it is a post dominator of current
     573             :   // block then it is not profitable to sink MI into SuccToSinkTo block.
     574             :   return false;
     575             : }
     576             : 
     577             : /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
     578             : /// computing it if it was not already cached.
     579             : SmallVector<MachineBasicBlock *, 4> &
     580      795262 : MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
     581             :                                        AllSuccsCache &AllSuccessors) const {
     582             :   // Do we have the sorted successors in cache ?
     583             :   auto Succs = AllSuccessors.find(MBB);
     584      795262 :   if (Succs != AllSuccessors.end())
     585      628975 :     return Succs->second;
     586             : 
     587             :   SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
     588             :                                                MBB->succ_end());
     589             : 
     590             :   // Handle cases where sinking can happen but where the sink point isn't a
     591             :   // successor. For example:
     592             :   //
     593             :   //   x = computation
     594             :   //   if () {} else {}
     595             :   //   use x
     596             :   //
     597             :   const std::vector<MachineDomTreeNode *> &Children =
     598      166287 :     DT->getNode(MBB)->getChildren();
     599      166287 :   for (const auto &DTChild : Children)
     600             :     // DomTree children of MBB that have MBB as immediate dominator are added.
     601      664943 :     if (DTChild->getIDom()->getBlock() == MI.getParent() &&
     602             :         // Skip MBBs already added to the AllSuccs vector above.
     603      331102 :         !MBB->isSuccessor(DTChild->getBlock()))
     604       48224 :       AllSuccs.push_back(DTChild->getBlock());
     605             : 
     606             :   // Sort Successors according to their loop depth or block frequency info.
     607             :   std::stable_sort(
     608             :       AllSuccs.begin(), AllSuccs.end(),
     609      578566 :       [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
     610      543140 :         uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
     611      543140 :         uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
     612      271570 :         bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
     613      289283 :         return HasBlockFreq ? LHSFreq < RHSFreq
     614      306996 :                             : LI->getLoopDepth(L) < LI->getLoopDepth(R);
     615             :       });
     616             : 
     617      166287 :   auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
     618             : 
     619      166287 :   return it.first->second;
     620             : }
     621             : 
     622             : /// FindSuccToSinkTo - Find a successor to sink this instruction to.
     623             : MachineBasicBlock *
     624     1497173 : MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
     625             :                                  bool &BreakPHIEdge,
     626             :                                  AllSuccsCache &AllSuccessors) {
     627             :   assert (MBB && "Invalid MachineBasicBlock!");
     628             : 
     629             :   // Loop over all the operands of the specified instruction.  If there is
     630             :   // anything we can't handle, bail out.
     631             : 
     632             :   // SuccToSinkTo - This is the successor to sink this instruction to, once we
     633             :   // decide.
     634             :   MachineBasicBlock *SuccToSinkTo = nullptr;
     635     3596481 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     636     3562967 :     const MachineOperand &MO = MI.getOperand(i);
     637     3562967 :     if (!MO.isReg()) continue;  // Ignore non-register operands.
     638             : 
     639     2764106 :     unsigned Reg = MO.getReg();
     640     2764106 :     if (Reg == 0) continue;
     641             : 
     642     2742012 :     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
     643     1658899 :       if (MO.isUse()) {
     644             :         // If the physreg has no defs anywhere, it's just an ambient register
     645             :         // and we can freely move its uses. Alternatively, if it's allocatable,
     646             :         // it could get allocated to something with a def during allocation.
     647      323373 :         if (!MRI->isConstantPhysReg(Reg))
     648             :           return nullptr;
     649     1335526 :       } else if (!MO.isDead()) {
     650             :         // A def that isn't dead. We can't move it.
     651             :         return nullptr;
     652             :       }
     653             :     } else {
     654             :       // Virtual register uses are always safe to sink.
     655     1083113 :       if (MO.isUse()) continue;
     656             : 
     657             :       // If it's not safe to move defs of the register class, then abort.
     658     1591852 :       if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
     659             :         return nullptr;
     660             : 
     661             :       // Virtual register defs can only be sunk if all their uses are in blocks
     662             :       // dominated by one of the successors.
     663      795278 :       if (SuccToSinkTo) {
     664             :         // If a previous operand picked a block to sink to, then this operand
     665             :         // must be sinkable to the same block.
     666          16 :         bool LocalUse = false;
     667          16 :         if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
     668             :                                      BreakPHIEdge, LocalUse))
     669          12 :           return nullptr;
     670             : 
     671           4 :         continue;
     672             :       }
     673             : 
     674             :       // Otherwise, we should look at all the successors and decide which one
     675             :       // we should sink to. If we have reliable block frequency information
     676             :       // (frequency != 0) available, give successors with smaller frequencies
     677             :       // higher priority, otherwise prioritize smaller loop depths.
     678      970334 :       for (MachineBasicBlock *SuccBlock :
     679     1683094 :            GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
     680      877764 :         bool LocalUse = false;
     681      877764 :         if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
     682             :                                     BreakPHIEdge, LocalUse)) {
     683             :           SuccToSinkTo = SuccBlock;
     684      113763 :           break;
     685             :         }
     686      764001 :         if (LocalUse)
     687             :           // Def is used locally, it's never safe to move this def.
     688      671431 :           return nullptr;
     689             :       }
     690             : 
     691             :       // If we couldn't find a block to sink to, ignore this instruction.
     692      123831 :       if (!SuccToSinkTo)
     693             :         return nullptr;
     694      113763 :       if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
     695             :         return nullptr;
     696             :     }
     697             :   }
     698             : 
     699             :   // It is not possible to sink an instruction into its own block.  This can
     700             :   // happen with loops.
     701       33514 :   if (MBB == SuccToSinkTo)
     702             :     return nullptr;
     703             : 
     704             :   // It's not safe to sink instructions to EH landing pad. Control flow into
     705             :   // landing pad is implicitly defined.
     706       33514 :   if (SuccToSinkTo && SuccToSinkTo->isEHPad())
     707             :     return nullptr;
     708             : 
     709             :   return SuccToSinkTo;
     710             : }
     711             : 
     712             : /// Return true if MI is likely to be usable as a memory operation by the
     713             : /// implicit null check optimization.
     714             : ///
     715             : /// This is a "best effort" heuristic, and should not be relied upon for
     716             : /// correctness.  This returning true does not guarantee that the implicit null
     717             : /// check optimization is legal over MI, and this returning false does not
     718             : /// guarantee MI cannot possibly be used to do a null check.
     719     1492424 : static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
     720             :                                              const TargetInstrInfo *TII,
     721             :                                              const TargetRegisterInfo *TRI) {
     722             :   using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
     723             : 
     724     1492424 :   auto *MBB = MI.getParent();
     725     1492424 :   if (MBB->pred_size() != 1)
     726             :     return false;
     727             : 
     728      896529 :   auto *PredMBB = *MBB->pred_begin();
     729      896529 :   auto *PredBB = PredMBB->getBasicBlock();
     730             : 
     731             :   // Frontends that don't use implicit null checks have no reason to emit
     732             :   // branches with make.implicit metadata, and this function should always
     733             :   // return false for them.
     734     1765651 :   if (!PredBB ||
     735      896388 :       !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
     736             :     return false;
     737             : 
     738             :   unsigned BaseReg;
     739             :   int64_t Offset;
     740          11 :   if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
     741             :     return false;
     742             : 
     743           8 :   if (!(MI.mayLoad() && !MI.isPredicable()))
     744             :     return false;
     745             : 
     746             :   MachineBranchPredicate MBP;
     747           4 :   if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
     748             :     return false;
     749             : 
     750           8 :   return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
     751           4 :          (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
     752           8 :           MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
     753           4 :          MBP.LHS.getReg() == BaseReg;
     754             : }
     755             : 
     756             : /// Sink an instruction and its associated debug instructions.
     757       27977 : static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
     758             :                         MachineBasicBlock::iterator InsertPos) {
     759             :   // Collect matching debug values.
     760             :   SmallVector<MachineInstr *, 2> DbgValuesToSink;
     761       27977 :   collectDebugValues(MI, DbgValuesToSink);
     762             : 
     763             :   // If we cannot find a location to use (merge with), then we erase the debug
     764             :   // location to prevent debug-info driven tools from potentially reporting
     765             :   // wrong location information.
     766       55131 :   if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
     767       54302 :     MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
     768             :                                                  InsertPos->getDebugLoc()));
     769             :   else
     770        1652 :     MI.setDebugLoc(DebugLoc());
     771             : 
     772             :   // Move the instruction.
     773       27977 :   MachineBasicBlock *ParentBlock = MI.getParent();
     774             :   SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
     775       27977 :                       ++MachineBasicBlock::iterator(MI));
     776             : 
     777             :   // Move previously adjacent debug value instructions to the insert position.
     778        3248 :   for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
     779             :                                                  DBE = DbgValuesToSink.end();
     780       31225 :        DBI != DBE; ++DBI) {
     781        3248 :     MachineInstr *DbgMI = *DBI;
     782             :     SuccToSinkTo.splice(InsertPos, ParentBlock, DbgMI,
     783        3248 :                         ++MachineBasicBlock::iterator(DbgMI));
     784             :   }
     785       27977 : }
     786             : 
     787             : /// SinkInstruction - Determine whether it is safe to sink the specified machine
     788             : /// instruction out of its current block into a successor.
     789     2899282 : bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
     790             :                                      AllSuccsCache &AllSuccessors) {
     791             :   // Don't sink instructions that the target prefers not to sink.
     792     2899282 :   if (!TII->shouldSink(MI))
     793             :     return false;
     794             : 
     795             :   // Check if it's safe to move the instruction.
     796     2899272 :   if (!MI.isSafeToMove(AA, SawStore))
     797             :     return false;
     798             : 
     799             :   // Convergent operations may not be made control-dependent on additional
     800             :   // values.
     801     1492458 :   if (MI.isConvergent())
     802             :     return false;
     803             : 
     804             :   // Don't break implicit null checks.  This is a performance heuristic, and not
     805             :   // required for correctness.
     806     1492424 :   if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
     807             :     return false;
     808             : 
     809             :   // FIXME: This should include support for sinking instructions within the
     810             :   // block they are currently in to shorten the live ranges.  We often get
     811             :   // instructions sunk into the top of a large block, but it would be better to
     812             :   // also sink them down before their first use in the block.  This xform has to
     813             :   // be careful not to *increase* register pressure though, e.g. sinking
     814             :   // "x = y + z" down if it kills y and z would increase the live ranges of y
     815             :   // and z and only shrink the live range of x.
     816             : 
     817     1492420 :   bool BreakPHIEdge = false;
     818     1492420 :   MachineBasicBlock *ParentBlock = MI.getParent();
     819             :   MachineBasicBlock *SuccToSinkTo =
     820     1492420 :       FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
     821             : 
     822             :   // If there are no outputs, it must have side-effects.
     823     1492420 :   if (!SuccToSinkTo)
     824             :     return false;
     825             : 
     826             :   // If the instruction to move defines a dead physical register which is live
     827             :   // when leaving the basic block, don't move it because it could turn into a
     828             :   // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
     829      147935 :   for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
     830      114740 :     const MachineOperand &MO = MI.getOperand(I);
     831      114740 :     if (!MO.isReg()) continue;
     832       83104 :     unsigned Reg = MO.getReg();
     833      150686 :     if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
     834        8151 :     if (SuccToSinkTo->isLiveIn(Reg))
     835             :       return false;
     836             :   }
     837             : 
     838             :   LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
     839             : 
     840             :   // If the block has multiple predecessors, this is a critical edge.
     841             :   // Decide if we can sink along it or need to break the edge.
     842       33195 :   if (SuccToSinkTo->pred_size() > 1) {
     843             :     // We cannot sink a load across a critical edge - there may be stores in
     844             :     // other code paths.
     845             :     bool TryBreak = false;
     846       12509 :     bool store = true;
     847       12509 :     if (!MI.isSafeToMove(AA, store)) {
     848             :       LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
     849             :       TryBreak = true;
     850             :     }
     851             : 
     852             :     // We don't want to sink across a critical edge if we don't dominate the
     853             :     // successor. We could be introducing calculations to new code paths.
     854       24474 :     if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
     855             :       LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
     856             :       TryBreak = true;
     857             :     }
     858             : 
     859             :     // Don't sink instructions into a loop.
     860       16202 :     if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
     861             :       LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
     862             :       TryBreak = true;
     863             :     }
     864             : 
     865             :     // Otherwise we are OK with sinking along a critical edge.
     866       12504 :     if (!TryBreak)
     867             :       LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
     868             :     else {
     869             :       // Mark this edge as to be split.
     870             :       // If the edge can actually be split, the next iteration of the main loop
     871             :       // will sink MI in the newly created block.
     872             :       bool Status =
     873        4549 :         PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
     874             :       if (!Status)
     875             :         LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
     876             :                              "break critical edge\n");
     877             :       // The instruction will not be sunk this time.
     878        4549 :       return false;
     879             :     }
     880             :   }
     881             : 
     882       28646 :   if (BreakPHIEdge) {
     883             :     // BreakPHIEdge is true if all the uses are in the successor MBB being
     884             :     // sunken into and they are all PHI nodes. In this case, machine-sink must
     885             :     // break the critical edge first.
     886             :     bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
     887        5197 :                                             SuccToSinkTo, BreakPHIEdge);
     888             :     if (!Status)
     889             :       LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
     890             :                            "break critical edge\n");
     891             :     // The instruction will not be sunk this time.
     892        5197 :     return false;
     893             :   }
     894             : 
     895             :   // Determine where to insert into. Skip phi nodes.
     896       23449 :   MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
     897       25306 :   while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
     898             :     ++InsertPos;
     899             : 
     900       23449 :   performSink(MI, *SuccToSinkTo, InsertPos);
     901             : 
     902             :   // Conservatively, clear any kill flags, since it's possible that they are no
     903             :   // longer correct.
     904             :   // Note that we have to clear the kill flags for any register this instruction
     905             :   // uses as we may sink over another instruction which currently kills the
     906             :   // used registers.
     907      184881 :   for (MachineOperand &MO : MI.operands()) {
     908      138977 :     if (MO.isReg() && MO.isUse())
     909       31457 :       RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
     910             :   }
     911             : 
     912             :   return true;
     913             : }
     914             : 
     915             : //===----------------------------------------------------------------------===//
     916             : // This pass is not intended to be a replacement or a complete alternative
     917             : // for the pre-ra machine sink pass. It is only designed to sink COPY
     918             : // instructions which should be handled after RA.
     919             : //
     920             : // This pass sinks COPY instructions into a successor block, if the COPY is not
     921             : // used in the current block and the COPY is live-in to a single successor
     922             : // (i.e., doesn't require the COPY to be duplicated).  This avoids executing the
     923             : // copy on paths where their results aren't needed.  This also exposes
     924             : // additional opportunites for dead copy elimination and shrink wrapping.
     925             : //
     926             : // These copies were either not handled by or are inserted after the MachineSink
     927             : // pass. As an example of the former case, the MachineSink pass cannot sink
     928             : // COPY instructions with allocatable source registers; for AArch64 these type
     929             : // of copy instructions are frequently used to move function parameters (PhyReg)
     930             : // into virtual registers in the entry block.
     931             : //
     932             : // For the machine IR below, this pass will sink %w19 in the entry into its
     933             : // successor (%bb.1) because %w19 is only live-in in %bb.1.
     934             : // %bb.0:
     935             : //   %wzr = SUBSWri %w1, 1
     936             : //   %w19 = COPY %w0
     937             : //   Bcc 11, %bb.2
     938             : // %bb.1:
     939             : //   Live Ins: %w19
     940             : //   BL @fun
     941             : //   %w0 = ADDWrr %w0, %w19
     942             : //   RET %w0
     943             : // %bb.2:
     944             : //   %w0 = COPY %wzr
     945             : //   RET %w0
     946             : // As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
     947             : // able to see %bb.0 as a candidate.
     948             : //===----------------------------------------------------------------------===//
     949             : namespace {
     950             : 
     951       56073 : class PostRAMachineSinking : public MachineFunctionPass {
     952             : public:
     953             :   bool runOnMachineFunction(MachineFunction &MF) override;
     954             : 
     955             :   static char ID;
     956       18785 :   PostRAMachineSinking() : MachineFunctionPass(ID) {}
     957       18653 :   StringRef getPassName() const override { return "PostRA Machine Sink"; }
     958             : 
     959       18637 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     960       18637 :     AU.setPreservesCFG();
     961       18637 :     MachineFunctionPass::getAnalysisUsage(AU);
     962       18637 :   }
     963             : 
     964       18641 :   MachineFunctionProperties getRequiredProperties() const override {
     965       37282 :     return MachineFunctionProperties().set(
     966       18641 :         MachineFunctionProperties::Property::NoVRegs);
     967             :   }
     968             : 
     969             : private:
     970             :   /// Track which register units have been modified and used.
     971             :   LiveRegUnits ModifiedRegUnits, UsedRegUnits;
     972             : 
     973             :   /// Sink Copy instructions unused in the same block close to their uses in
     974             :   /// successors.
     975             :   bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
     976             :                      const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
     977             : };
     978             : } // namespace
     979             : 
     980             : char PostRAMachineSinking::ID = 0;
     981             : char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID;
     982             : 
     983      146610 : INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
     984             :                 "PostRA Machine Sink", false, false)
     985             : 
     986       12116 : static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
     987             :                                   const TargetRegisterInfo *TRI) {
     988             :   LiveRegUnits LiveInRegUnits(*TRI);
     989       12116 :   LiveInRegUnits.addLiveIns(MBB);
     990       24232 :   return !LiveInRegUnits.available(Reg);
     991             : }
     992             : 
     993             : static MachineBasicBlock *
     994        6453 : getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
     995             :                       const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
     996             :                       unsigned Reg, const TargetRegisterInfo *TRI) {
     997             :   // Try to find a single sinkable successor in which Reg is live-in.
     998             :   MachineBasicBlock *BB = nullptr;
     999        6453 :   for (auto *SI : SinkableBBs) {
    1000        8018 :     if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
    1001             :       // If BB is set here, Reg is live-in to at least two sinkable successors,
    1002             :       // so quit.
    1003        6302 :       if (BB)
    1004         605 :         return nullptr;
    1005             :       BB = SI;
    1006             :     }
    1007             :   }
    1008             :   // Reg is not live-in to any sinkable successors.
    1009        5848 :   if (!BB)
    1010             :     return nullptr;
    1011             : 
    1012             :   // Check if any register aliased with Reg is live-in in other successors.
    1013       14393 :   for (auto *SI : CurBB.successors()) {
    1014        9858 :     if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
    1015             :       return nullptr;
    1016             :   }
    1017             :   return BB;
    1018             : }
    1019             : 
    1020             : static MachineBasicBlock *
    1021        6446 : getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
    1022             :                       const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
    1023             :                       ArrayRef<unsigned> DefedRegsInCopy,
    1024             :                       const TargetRegisterInfo *TRI) {
    1025             :   MachineBasicBlock *SingleBB = nullptr;
    1026       15516 :   for (auto DefReg : DefedRegsInCopy) {
    1027             :     MachineBasicBlock *BB =
    1028        6453 :         getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
    1029        6453 :     if (!BB || (SingleBB && SingleBB != BB))
    1030             :       return nullptr;
    1031             :     SingleBB = BB;
    1032             :   }
    1033             :   return SingleBB;
    1034             : }
    1035             : 
    1036        4528 : static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
    1037             :                            SmallVectorImpl<unsigned> &UsedOpsInCopy,
    1038             :                            LiveRegUnits &UsedRegUnits,
    1039             :                            const TargetRegisterInfo *TRI) {
    1040       13590 :   for (auto U : UsedOpsInCopy) {
    1041        4531 :     MachineOperand &MO = MI->getOperand(U);
    1042        4531 :     unsigned SrcReg = MO.getReg();
    1043        4531 :     if (!UsedRegUnits.available(SrcReg)) {
    1044         582 :       MachineBasicBlock::iterator NI = std::next(MI->getIterator());
    1045        7949 :       for (MachineInstr &UI : make_range(NI, CurBB.end())) {
    1046        6823 :         if (UI.killsRegister(SrcReg, TRI)) {
    1047          38 :           UI.clearRegisterKills(SrcReg, TRI);
    1048             :           MO.setIsKill(true);
    1049             :           break;
    1050             :         }
    1051             :       }
    1052             :     }
    1053             :   }
    1054        4528 : }
    1055             : 
    1056        4528 : static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
    1057             :                          SmallVectorImpl<unsigned> &UsedOpsInCopy,
    1058             :                          SmallVectorImpl<unsigned> &DefedRegsInCopy) {
    1059       13598 :   for (auto DefReg : DefedRegsInCopy)
    1060        4535 :     SuccBB->removeLiveIn(DefReg);
    1061       13590 :   for (auto U : UsedOpsInCopy) {
    1062        9062 :     unsigned Reg = MI->getOperand(U).getReg();
    1063        4531 :     if (!SuccBB->isLiveIn(Reg))
    1064             :       SuccBB->addLiveIn(Reg);
    1065             :   }
    1066        4528 : }
    1067             : 
    1068       16521 : static bool hasRegisterDependency(MachineInstr *MI,
    1069             :                                   SmallVectorImpl<unsigned> &UsedOpsInCopy,
    1070             :                                   SmallVectorImpl<unsigned> &DefedRegsInCopy,
    1071             :                                   LiveRegUnits &ModifiedRegUnits,
    1072             :                                   LiveRegUnits &UsedRegUnits) {
    1073             :   bool HasRegDependency = false;
    1074       31275 :   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    1075       24829 :     MachineOperand &MO = MI->getOperand(i);
    1076       24829 :     if (!MO.isReg())
    1077           0 :       continue;
    1078       24829 :     unsigned Reg = MO.getReg();
    1079       24829 :     if (!Reg)
    1080           0 :       continue;
    1081       24829 :     if (MO.isDef()) {
    1082       16549 :       if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
    1083             :         HasRegDependency = true;
    1084       10075 :         break;
    1085             :       }
    1086        8264 :       DefedRegsInCopy.push_back(Reg);
    1087             : 
    1088             :       // FIXME: instead of isUse(), readsReg() would be a better fix here,
    1089             :       // For example, we can ignore modifications in reg with undef. However,
    1090             :       // it's not perfectly clear if skipping the internal read is safe in all
    1091             :       // other targets.
    1092             :     } else if (MO.isUse()) {
    1093        8280 :       if (!ModifiedRegUnits.available(Reg)) {
    1094             :         HasRegDependency = true;
    1095             :         break;
    1096             :       }
    1097        6490 :       UsedOpsInCopy.push_back(i);
    1098             :     }
    1099             :   }
    1100       16521 :   return HasRegDependency;
    1101             : }
    1102             : 
    1103      343206 : bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
    1104             :                                          MachineFunction &MF,
    1105             :                                          const TargetRegisterInfo *TRI,
    1106             :                                          const TargetInstrInfo *TII) {
    1107             :   SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
    1108             :   // FIXME: For now, we sink only to a successor which has a single predecessor
    1109             :   // so that we can directly sink COPY instructions to the successor without
    1110             :   // adding any new block or branch instruction.
    1111      566815 :   for (MachineBasicBlock *SI : CurBB.successors())
    1112      424834 :     if (!SI->livein_empty() && SI->pred_size() == 1)
    1113       98243 :       SinkableBBs.insert(SI);
    1114             : 
    1115      343206 :   if (SinkableBBs.empty())
    1116             :     return false;
    1117             : 
    1118             :   bool Changed = false;
    1119             : 
    1120             :   // Track which registers have been modified and used between the end of the
    1121             :   // block and the current instruction.
    1122             :   ModifiedRegUnits.clear();
    1123             :   UsedRegUnits.clear();
    1124             : 
    1125      665160 :   for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
    1126             :     MachineInstr *MI = &*I;
    1127             :     ++I;
    1128             : 
    1129       20869 :     if (MI->isDebugInstr())
    1130      526912 :       continue;
    1131             : 
    1132             :     // Do not move any instruction across function call.
    1133      545466 :     if (MI->isCall())
    1134       34895 :       return false;
    1135             : 
    1136     1004621 :     if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
    1137      494050 :       LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
    1138             :                                         TRI);
    1139             :       continue;
    1140             :     }
    1141             : 
    1142             :     // Track the operand index for use in Copy.
    1143             :     SmallVector<unsigned, 2> UsedOpsInCopy;
    1144             :     // Track the register number defed in Copy.
    1145             :     SmallVector<unsigned, 2> DefedRegsInCopy;
    1146             : 
    1147             :     // Don't sink the COPY if it would violate a register dependency.
    1148       26596 :     if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
    1149             :                               ModifiedRegUnits, UsedRegUnits)) {
    1150       10075 :       LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
    1151             :                                         TRI);
    1152             :       continue;
    1153             :     }
    1154             :     assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
    1155             :            "Unexpect SrcReg or DefReg");
    1156             :     MachineBasicBlock *SuccBB =
    1157        6446 :         getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
    1158             :     // Don't sink if we cannot find a single sinkable successor in which Reg
    1159             :     // is live-in.
    1160        8364 :     if (!SuccBB) {
    1161        1918 :       LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
    1162             :                                         TRI);
    1163             :       continue;
    1164             :     }
    1165             :     assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
    1166             :            "Unexpected predecessor");
    1167             : 
    1168             :     // Clear the kill flag if SrcReg is killed between MI and the end of the
    1169             :     // block.
    1170        4528 :     clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
    1171        4528 :     MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
    1172        4528 :     performSink(*MI, *SuccBB, InsertPos);
    1173        4528 :     updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
    1174             : 
    1175             :     Changed = true;
    1176             :     ++NumPostRACopySink;
    1177             :   }
    1178             :   return Changed;
    1179             : }
    1180             : 
    1181      181782 : bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
    1182             :   bool Changed = false;
    1183      181782 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
    1184      181782 :   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
    1185             : 
    1186      181782 :   ModifiedRegUnits.init(*TRI);
    1187      181782 :   UsedRegUnits.init(*TRI);
    1188      524988 :   for (auto &BB : MF)
    1189      343206 :     Changed |= tryToSinkCopy(BB, MF, TRI, TII);
    1190             : 
    1191      181782 :   return Changed;
    1192      299229 : }

Generated by: LCOV version 1.13