LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineSink.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 277 279 99.3 %
Date: 2017-09-14 15:23:50 Functions: 22 22 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/IR/BasicBlock.h"
      37             : #include "llvm/IR/LLVMContext.h"
      38             : #include "llvm/Pass.h"
      39             : #include "llvm/Support/BranchProbability.h"
      40             : #include "llvm/Support/CommandLine.h"
      41             : #include "llvm/Support/Debug.h"
      42             : #include "llvm/Support/raw_ostream.h"
      43             : #include "llvm/Target/TargetInstrInfo.h"
      44             : #include "llvm/Target/TargetRegisterInfo.h"
      45             : #include "llvm/Target/TargetSubtargetInfo.h"
      46             : #include <algorithm>
      47             : #include <cassert>
      48             : #include <cstdint>
      49             : #include <map>
      50             : #include <utility>
      51             : #include <vector>
      52             : 
      53             : using namespace llvm;
      54             : 
      55             : #define DEBUG_TYPE "machine-sink"
      56             : 
      57             : static cl::opt<bool>
      58       72306 : SplitEdges("machine-sink-split",
      59      216918 :            cl::desc("Split critical edges during machine sinking"),
      60      289224 :            cl::init(true), cl::Hidden);
      61             : 
      62             : static cl::opt<bool>
      63       72306 : UseBlockFreqInfo("machine-sink-bfi",
      64      216918 :            cl::desc("Use block frequency info to find successors to sink"),
      65      289224 :            cl::init(true), cl::Hidden);
      66             : 
      67       72306 : static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
      68             :     "machine-sink-split-probability-threshold",
      69      216918 :     cl::desc(
      70             :         "Percentage threshold for splitting single-instruction critical edge. "
      71             :         "If the branch threshold is higher than this threshold, we allow "
      72             :         "speculative execution of up to 1 instruction to avoid branching to "
      73             :         "splitted critical edge"),
      74      289224 :     cl::init(40), cl::Hidden);
      75             : 
      76             : STATISTIC(NumSunk,      "Number of machine instructions sunk");
      77             : STATISTIC(NumSplit,     "Number of critical edges split");
      78             : STATISTIC(NumCoalesces, "Number of copies coalesced");
      79             : 
      80             : namespace {
      81             : 
      82       46550 :   class MachineSinking : public MachineFunctionPass {
      83             :     const TargetInstrInfo *TII;
      84             :     const TargetRegisterInfo *TRI;
      85             :     MachineRegisterInfo  *MRI;     // Machine register information
      86             :     MachineDominatorTree *DT;      // Machine dominator tree
      87             :     MachinePostDominatorTree *PDT; // Machine post dominator tree
      88             :     MachineLoopInfo *LI;
      89             :     const MachineBlockFrequencyInfo *MBFI;
      90             :     const MachineBranchProbabilityInfo *MBPI;
      91             :     AliasAnalysis *AA;
      92             : 
      93             :     // Remember which edges have been considered for breaking.
      94             :     SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
      95             :     CEBCandidates;
      96             :     // Remember which edges we are about to split.
      97             :     // This is different from CEBCandidates since those edges
      98             :     // will be split.
      99             :     SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
     100             : 
     101             :     SparseBitVector<> RegsToClearKillFlags;
     102             : 
     103             :     using AllSuccsCache =
     104             :         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
     105             : 
     106             :   public:
     107             :     static char ID; // Pass identification
     108             : 
     109       62460 :     MachineSinking() : MachineFunctionPass(ID) {
     110       15615 :       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     111       15615 :     }
     112             : 
     113             :     bool runOnMachineFunction(MachineFunction &MF) override;
     114             : 
     115       15569 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
     116       15569 :       AU.setPreservesCFG();
     117       15569 :       MachineFunctionPass::getAnalysisUsage(AU);
     118       15569 :       AU.addRequired<AAResultsWrapperPass>();
     119       15569 :       AU.addRequired<MachineDominatorTree>();
     120       15569 :       AU.addRequired<MachinePostDominatorTree>();
     121       15569 :       AU.addRequired<MachineLoopInfo>();
     122       15569 :       AU.addRequired<MachineBranchProbabilityInfo>();
     123       15569 :       AU.addPreserved<MachineDominatorTree>();
     124       15569 :       AU.addPreserved<MachinePostDominatorTree>();
     125       15569 :       AU.addPreserved<MachineLoopInfo>();
     126       15569 :       if (UseBlockFreqInfo)
     127             :         AU.addRequired<MachineBlockFrequencyInfo>();
     128       15569 :     }
     129             : 
     130      135776 :     void releaseMemory() override {
     131      271552 :       CEBCandidates.clear();
     132      135776 :     }
     133             : 
     134             :   private:
     135             :     bool ProcessBlock(MachineBasicBlock &MBB);
     136             :     bool isWorthBreakingCriticalEdge(MachineInstr &MI,
     137             :                                      MachineBasicBlock *From,
     138             :                                      MachineBasicBlock *To);
     139             : 
     140             :     /// \brief Postpone the splitting of the given critical
     141             :     /// edge (\p From, \p To).
     142             :     ///
     143             :     /// We do not split the edges on the fly. Indeed, this invalidates
     144             :     /// the dominance information and thus triggers a lot of updates
     145             :     /// of that information underneath.
     146             :     /// Instead, we postpone all the splits after each iteration of
     147             :     /// the main loop. That way, the information is at least valid
     148             :     /// for the lifetime of an iteration.
     149             :     ///
     150             :     /// \return True if the edge is marked as toSplit, false otherwise.
     151             :     /// False can be returned if, for instance, this is not profitable.
     152             :     bool PostponeSplitCriticalEdge(MachineInstr &MI,
     153             :                                    MachineBasicBlock *From,
     154             :                                    MachineBasicBlock *To,
     155             :                                    bool BreakPHIEdge);
     156             :     bool SinkInstruction(MachineInstr &MI, bool &SawStore,
     157             : 
     158             :                          AllSuccsCache &AllSuccessors);
     159             :     bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
     160             :                                  MachineBasicBlock *DefMBB,
     161             :                                  bool &BreakPHIEdge, bool &LocalUse) const;
     162             :     MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
     163             :                bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
     164             :     bool isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
     165             :                               MachineBasicBlock *MBB,
     166             :                               MachineBasicBlock *SuccToSinkTo,
     167             :                               AllSuccsCache &AllSuccessors);
     168             : 
     169             :     bool PerformTrivialForwardCoalescing(MachineInstr &MI,
     170             :                                          MachineBasicBlock *MBB);
     171             : 
     172             :     SmallVector<MachineBasicBlock *, 4> &
     173             :     GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
     174             :                            AllSuccsCache &AllSuccessors) const;
     175             :   };
     176             : 
     177             : } // end anonymous namespace
     178             : 
     179             : char MachineSinking::ID = 0;
     180             : 
     181             : char &llvm::MachineSinkingID = MachineSinking::ID;
     182             : 
     183       20212 : INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
     184             :                       "Machine code sinking", false, false)
     185       20212 : INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
     186       20212 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     187       20212 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     188       20212 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     189      198044 : INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
     190             :                     "Machine code sinking", false, false)
     191             : 
     192     2736313 : bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
     193             :                                                      MachineBasicBlock *MBB) {
     194     2736313 :   if (!MI.isCopy())
     195             :     return false;
     196             : 
     197      414305 :   unsigned SrcReg = MI.getOperand(1).getReg();
     198      414305 :   unsigned DstReg = MI.getOperand(0).getReg();
     199      736963 :   if (!TargetRegisterInfo::isVirtualRegister(SrcReg) ||
     200      769589 :       !TargetRegisterInfo::isVirtualRegister(DstReg) ||
     201       32626 :       !MRI->hasOneNonDBGUse(SrcReg))
     202             :     return false;
     203             : 
     204       41416 :   const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
     205       41416 :   const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
     206       20708 :   if (SRC != DRC)
     207             :     return false;
     208             : 
     209       12498 :   MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
     210         401 :   if (DefMI->isCopyLike())
     211             :     return false;
     212             :   DEBUG(dbgs() << "Coalescing: " << *DefMI);
     213             :   DEBUG(dbgs() << "*** to: " << MI);
     214         401 :   MRI->replaceRegWith(DstReg, SrcReg);
     215         401 :   MI.eraseFromParent();
     216             : 
     217             :   // Conservatively, clear any kill flags, since it's possible that they are no
     218             :   // longer correct.
     219         401 :   MRI->clearKillFlags(SrcReg);
     220             : 
     221         401 :   ++NumCoalesces;
     222             :   return true;
     223             : }
     224             : 
     225             : /// AllUsesDominatedByBlock - Return true if all uses of the specified register
     226             : /// occur in blocks dominated by the specified block. If any use is in the
     227             : /// definition block, then return false since it is never legal to move def
     228             : /// after uses.
     229             : bool
     230      821470 : MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
     231             :                                         MachineBasicBlock *MBB,
     232             :                                         MachineBasicBlock *DefMBB,
     233             :                                         bool &BreakPHIEdge,
     234             :                                         bool &LocalUse) const {
     235             :   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
     236             :          "Only makes sense for vregs");
     237             : 
     238             :   // Ignore debug uses because debug info doesn't affect the code.
     239     1642940 :   if (MRI->use_nodbg_empty(Reg))
     240             :     return true;
     241             : 
     242             :   // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
     243             :   // into and they are all PHI nodes. In this case, machine-sink must break
     244             :   // the critical edge first. e.g.
     245             :   //
     246             :   // BB#1: derived from LLVM BB %bb4.preheader
     247             :   //   Predecessors according to CFG: BB#0
     248             :   //     ...
     249             :   //     %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead>
     250             :   //     ...
     251             :   //     JE_4 <BB#37>, %EFLAGS<imp-use>
     252             :   //   Successors according to CFG: BB#37 BB#2
     253             :   //
     254             :   // BB#2: derived from LLVM BB %bb.nph
     255             :   //   Predecessors according to CFG: BB#0 BB#1
     256             :   //     %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1>
     257      782594 :   BreakPHIEdge = true;
     258     2362589 :   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
     259      785773 :     MachineInstr *UseInst = MO.getParent();
     260      785773 :     unsigned OpNo = &MO - &UseInst->getOperand(0);
     261      785773 :     MachineBasicBlock *UseBlock = UseInst->getParent();
     262      801629 :     if (!(UseBlock == MBB && UseInst->isPHI() &&
     263       31712 :           UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) {
     264      770966 :       BreakPHIEdge = false;
     265             :       break;
     266             :     }
     267             :   }
     268      782594 :   if (BreakPHIEdge)
     269             :     return true;
     270             : 
     271     2416088 :   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
     272             :     // Determine the block of the use.
     273      821258 :     MachineInstr *UseInst = MO.getParent();
     274      821258 :     unsigned OpNo = &MO - &UseInst->getOperand(0);
     275      821258 :     MachineBasicBlock *UseBlock = UseInst->getParent();
     276      789177 :     if (UseInst->isPHI()) {
     277             :       // PHI nodes use the operand in the predecessor block, not the block with
     278             :       // the PHI.
     279       64162 :       UseBlock = UseInst->getOperand(OpNo+1).getMBB();
     280      789177 :     } else if (UseBlock == DefMBB) {
     281      633632 :       LocalUse = true;
     282             :       return false;
     283             :     }
     284             : 
     285             :     // Check that it dominates.
     286      375252 :     if (!DT->dominates(MBB, UseBlock))
     287             :       return false;
     288             :   }
     289             : 
     290             :   return true;
     291             : }
     292             : 
     293      135752 : bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
     294      135752 :   if (skipFunction(*MF.getFunction()))
     295             :     return false;
     296             : 
     297             :   DEBUG(dbgs() << "******** Machine Sinking ********\n");
     298             : 
     299      135695 :   TII = MF.getSubtarget().getInstrInfo();
     300      135695 :   TRI = MF.getSubtarget().getRegisterInfo();
     301      135695 :   MRI = &MF.getRegInfo();
     302      135695 :   DT = &getAnalysis<MachineDominatorTree>();
     303      135695 :   PDT = &getAnalysis<MachinePostDominatorTree>();
     304      135695 :   LI = &getAnalysis<MachineLoopInfo>();
     305      135695 :   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
     306      135695 :   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
     307      271390 :   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     308             : 
     309      135695 :   bool EverMadeChange = false;
     310             : 
     311             :   while (true) {
     312      141392 :     bool MadeChange = false;
     313             : 
     314             :     // Process all basic blocks.
     315      282784 :     CEBCandidates.clear();
     316      282784 :     ToSplit.clear();
     317      905184 :     for (auto &MBB: MF)
     318      481008 :       MadeChange |= ProcessBlock(MBB);
     319             : 
     320             :     // If we have anything we marked as toSplit, split it now.
     321      568964 :     for (auto &Pair : ToSplit) {
     322        3396 :       auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
     323        3396 :       if (NewSucc != nullptr) {
     324             :         DEBUG(dbgs() << " *** Splitting critical edge:"
     325             :               " BB#" << Pair.first->getNumber()
     326             :               << " -- BB#" << NewSucc->getNumber()
     327             :               << " -- BB#" << Pair.second->getNumber() << '\n');
     328        3280 :         MadeChange = true;
     329             :         ++NumSplit;
     330             :       } else
     331             :         DEBUG(dbgs() << " *** Not legal to break critical edge\n");
     332             :     }
     333             :     // If this iteration over the code changed anything, keep iterating.
     334      141392 :     if (!MadeChange) break;
     335             :     EverMadeChange = true;
     336             :   }
     337             : 
     338             :   // Now clear any kill flags for recorded registers.
     339      284137 :   for (auto I : RegsToClearKillFlags)
     340       12747 :     MRI->clearKillFlags(I);
     341      271390 :   RegsToClearKillFlags.clear();
     342             : 
     343      135695 :   return EverMadeChange;
     344             : }
     345             : 
     346      481008 : bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
     347             :   // Can't sink anything out of a block that has less than two successors.
     348      642300 :   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
     349             : 
     350             :   // Don't bother sinking code out of unreachable blocks. In addition to being
     351             :   // unprofitable, it can also lead to infinite looping, because in an
     352             :   // unreachable loop there may be nowhere to stop.
     353      322584 :   if (!DT->isReachableFromEntry(&MBB)) return false;
     354             : 
     355      161291 :   bool MadeChange = false;
     356             : 
     357             :   // Cache all successors, sorted by frequency info and loop depth.
     358      161291 :   AllSuccsCache AllSuccessors;
     359             : 
     360             :   // Walk the basic block bottom-up.  Remember if we saw a store.
     361      161291 :   MachineBasicBlock::iterator I = MBB.end();
     362      161291 :   --I;
     363      161291 :   bool ProcessedBegin, SawStore = false;
     364             :   do {
     365     2776982 :     MachineInstr &MI = *I;  // The instruction to sink.
     366             : 
     367             :     // Predecrement I (if it's not begin) so that it isn't invalidated by
     368             :     // sinking.
     369     5553964 :     ProcessedBegin = I == MBB.begin();
     370     2776982 :     if (!ProcessedBegin)
     371             :       --I;
     372             : 
     373     2776982 :     if (MI.isDebugValue())
     374       40669 :       continue;
     375             : 
     376     2736313 :     bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);
     377     2736714 :     if (Joined) {
     378         401 :       MadeChange = true;
     379         401 :       continue;
     380             :     }
     381             : 
     382     2735912 :     if (SinkInstruction(MI, SawStore, AllSuccessors)) {
     383       21298 :       ++NumSunk;
     384       21298 :       MadeChange = true;
     385             :     }
     386             : 
     387             :     // If we just processed the first instruction in the block, we're done.
     388     2776982 :   } while (!ProcessedBegin);
     389             : 
     390      161291 :   return MadeChange;
     391             : }
     392             : 
     393        8739 : bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
     394             :                                                  MachineBasicBlock *From,
     395             :                                                  MachineBasicBlock *To) {
     396             :   // FIXME: Need much better heuristics.
     397             : 
     398             :   // If the pass has already considered breaking this edge (during this pass
     399             :   // through the function), then let's go ahead and break it. This means
     400             :   // sinking multiple "cheap" instructions into the same block.
     401       17478 :   if (!CEBCandidates.insert(std::make_pair(From, To)).second)
     402             :     return true;
     403             : 
     404        6723 :   if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
     405             :     return true;
     406             : 
     407        9200 :   if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
     408             :       BranchProbability(SplitEdgeProbabilityThreshold, 100))
     409             :     return true;
     410             : 
     411             :   // MI is cheap, we probably don't want to break the critical edge for it.
     412             :   // However, if this would allow some definitions of its source operands
     413             :   // to be sunk then it's probably worth it.
     414       12912 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     415        9208 :     const MachineOperand &MO = MI.getOperand(i);
     416       12134 :     if (!MO.isReg() || !MO.isUse())
     417        3543 :       continue;
     418        1061 :     unsigned Reg = MO.getReg();
     419        1089 :     if (Reg == 0)
     420          28 :       continue;
     421             : 
     422             :     // We don't move live definitions of physical registers,
     423             :     // so sinking their uses won't enable any opportunities.
     424        1033 :     if (TargetRegisterInfo::isPhysicalRegister(Reg))
     425          35 :       continue;
     426             : 
     427             :     // If this instruction is the only user of a virtual register,
     428             :     // check if breaking the edge will enable sinking
     429             :     // both this instruction and the defining instruction.
     430         998 :     if (MRI->hasOneNonDBGUse(Reg)) {
     431             :       // If the definition resides in same MBB,
     432             :       // claim it's likely we can sink these together.
     433             :       // If definition resides elsewhere, we aren't
     434             :       // blocking it from being sunk so don't break the edge.
     435         456 :       MachineInstr *DefMI = MRI->getVRegDef(Reg);
     436         456 :       if (DefMI->getParent() == MI.getParent())
     437             :         return true;
     438             :     }
     439             :   }
     440             : 
     441             :   return false;
     442             : }
     443             : 
     444        8739 : bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
     445             :                                                MachineBasicBlock *FromBB,
     446             :                                                MachineBasicBlock *ToBB,
     447             :                                                bool BreakPHIEdge) {
     448        8739 :   if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
     449             :     return false;
     450             : 
     451             :   // Avoid breaking back edge. From == To means backedge for single BB loop.
     452        6887 :   if (!SplitEdges || FromBB == ToBB)
     453             :     return false;
     454             : 
     455             :   // Check for backedges of more "complex" loops.
     456       27349 :   if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
     457       13376 :       LI->isLoopHeader(ToBB))
     458             :     return false;
     459             : 
     460             :   // It's not always legal to break critical edges and sink the computation
     461             :   // to the edge.
     462             :   //
     463             :   // BB#1:
     464             :   // v1024
     465             :   // Beq BB#3
     466             :   // <fallthrough>
     467             :   // BB#2:
     468             :   // ... no uses of v1024
     469             :   // <fallthrough>
     470             :   // BB#3:
     471             :   // ...
     472             :   //       = v1024
     473             :   //
     474             :   // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted:
     475             :   //
     476             :   // BB#1:
     477             :   // ...
     478             :   // Bne BB#2
     479             :   // BB#4:
     480             :   // v1024 =
     481             :   // B BB#3
     482             :   // BB#2:
     483             :   // ... no uses of v1024
     484             :   // <fallthrough>
     485             :   // BB#3:
     486             :   // ...
     487             :   //       = v1024
     488             :   //
     489             :   // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3
     490             :   // flow. We need to ensure the new basic block where the computation is
     491             :   // sunk to dominates all the uses.
     492             :   // It's only legal to break critical edge and sink the computation to the
     493             :   // new block if all the predecessors of "To", except for "From", are
     494             :   // not dominated by "From". Given SSA property, this means these
     495             :   // predecessors are dominated by "To".
     496             :   //
     497             :   // There is no need to do this check if all the uses are PHI nodes. PHI
     498             :   // sources are only defined on the specific predecessor edges.
     499        4837 :   if (!BreakPHIEdge) {
     500         344 :     for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
     501         631 :            E = ToBB->pred_end(); PI != E; ++PI) {
     502         284 :       if (*PI == FromBB)
     503          88 :         continue;
     504         392 :       if (!DT->dominates(ToBB, *PI))
     505             :         return false;
     506             :     }
     507             :   }
     508             : 
     509        9336 :   ToSplit.insert(std::make_pair(FromBB, ToBB));
     510             :   
     511        4668 :   return true;
     512             : }
     513             : 
     514             : /// collectDebgValues - Scan instructions following MI and collect any
     515             : /// matching DBG_VALUEs.
     516       21298 : static void collectDebugValues(MachineInstr &MI,
     517             :                                SmallVectorImpl<MachineInstr *> &DbgValues) {
     518       21298 :   DbgValues.clear();
     519       42596 :   if (!MI.getOperand(0).isReg())
     520       21278 :     return;
     521             : 
     522       42592 :   MachineBasicBlock::iterator DI = MI; ++DI;
     523       42592 :   for (MachineBasicBlock::iterator DE = MI.getParent()->end();
     524       23061 :        DI != DE; ++DI) {
     525       46082 :     if (!DI->isDebugValue())
     526             :       return;
     527        5204 :     if (DI->getOperand(0).isReg() &&
     528        1674 :         DI->getOperand(0).getReg() == MI.getOperand(0).getReg())
     529        2498 :       DbgValues.push_back(&*DI);
     530             :   }
     531             : }
     532             : 
     533             : /// isProfitableToSinkTo - Return true if it is profitable to sink MI.
     534      103402 : bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr &MI,
     535             :                                           MachineBasicBlock *MBB,
     536             :                                           MachineBasicBlock *SuccToSinkTo,
     537             :                                           AllSuccsCache &AllSuccessors) {
     538             :   assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
     539             : 
     540      103402 :   if (MBB == SuccToSinkTo)
     541             :     return false;
     542             : 
     543             :   // It is profitable if SuccToSinkTo does not post dominate current block.
     544      200100 :   if (!PDT->dominates(SuccToSinkTo, MBB))
     545             :     return true;
     546             : 
     547             :   // It is profitable to sink an instruction from a deeper loop to a shallower
     548             :   // loop, even if the latter post-dominates the former (PR21115).
     549       46314 :   if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
     550             :     return true;
     551             : 
     552             :   // Check if only use in post dominated block is PHI instruction.
     553       11238 :   bool NonPHIUse = false;
     554       81885 :   for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
     555       16057 :     MachineBasicBlock *UseBlock = UseInst.getParent();
     556       16057 :     if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
     557             :       NonPHIUse = true;
     558             :   }
     559       11238 :   if (!NonPHIUse)
     560             :     return true;
     561             : 
     562             :   // If SuccToSinkTo post dominates then also it may be profitable if MI
     563             :   // can further profitably sinked into another block in next round.
     564        4350 :   bool BreakPHIEdge = false;
     565             :   // FIXME - If finding successor is compile time expensive then cache results.
     566        4350 :   if (MachineBasicBlock *MBB2 =
     567        4350 :           FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
     568           0 :     return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
     569             : 
     570             :   // If SuccToSinkTo is final destination and it is a post dominator of current
     571             :   // block then it is not profitable to sink MI into SuccToSinkTo block.
     572             :   return false;
     573             : }
     574             : 
     575             : /// Get the sorted sequence of successors for this MachineBasicBlock, possibly
     576             : /// computing it if it was not already cached.
     577             : SmallVector<MachineBasicBlock *, 4> &
     578      745628 : MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
     579             :                                        AllSuccsCache &AllSuccessors) const {
     580             :   // Do we have the sorted successors in cache ?
     581      745628 :   auto Succs = AllSuccessors.find(MBB);
     582      745628 :   if (Succs != AllSuccessors.end())
     583      590890 :     return Succs->second;
     584             : 
     585             :   SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
     586      618952 :                                                MBB->succ_end());
     587             : 
     588             :   // Handle cases where sinking can happen but where the sink point isn't a
     589             :   // successor. For example:
     590             :   //
     591             :   //   x = computation
     592             :   //   if () {} else {}
     593             :   //   use x
     594             :   //
     595             :   const std::vector<MachineDomTreeNode *> &Children =
     596      309476 :     DT->getNode(MBB)->getChildren();
     597      933093 :   for (const auto &DTChild : Children)
     598             :     // DomTree children of MBB that have MBB as immediate dominator are added.
     599      625736 :     if (DTChild->getIDom()->getBlock() == MI.getParent() &&
     600             :         // Skip MBBs already added to the AllSuccs vector above.
     601      311595 :         !MBB->isSuccessor(DTChild->getBlock()))
     602       47048 :       AllSuccs.push_back(DTChild->getBlock());
     603             : 
     604             :   // Sort Successors according to their loop depth or block frequency info.
     605      618952 :   std::stable_sort(
     606             :       AllSuccs.begin(), AllSuccs.end(),
     607      548002 :       [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
     608      515523 :         uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
     609      515523 :         uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
     610      257763 :         bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
     611      274001 :         return HasBlockFreq ? LHSFreq < RHSFreq
     612      322715 :                             : LI->getLoopDepth(L) < LI->getLoopDepth(R);
     613             :       });
     614             : 
     615      618952 :   auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
     616             : 
     617      154738 :   return it.first->second;
     618             : }
     619             : 
     620             : /// FindSuccToSinkTo - Find a successor to sink this instruction to.
     621             : MachineBasicBlock *
     622     1411416 : MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
     623             :                                  bool &BreakPHIEdge,
     624             :                                  AllSuccsCache &AllSuccessors) {
     625             :   assert (MBB && "Invalid MachineBasicBlock!");
     626             : 
     627             :   // Loop over all the operands of the specified instruction.  If there is
     628             :   // anything we can't handle, bail out.
     629             : 
     630             :   // SuccToSinkTo - This is the successor to sink this instruction to, once we
     631             :   // decide.
     632     1411416 :   MachineBasicBlock *SuccToSinkTo = nullptr;
     633     3120553 :   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     634     6180390 :     const MachineOperand &MO = MI.getOperand(i);
     635     3090195 :     if (!MO.isReg()) continue;  // Ignore non-register operands.
     636             : 
     637     2299410 :     unsigned Reg = MO.getReg();
     638     2299410 :     if (Reg == 0) continue;
     639             : 
     640     2278620 :     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
     641     1296428 :       if (MO.isUse()) {
     642             :         // If the physreg has no defs anywhere, it's just an ambient register
     643             :         // and we can freely move its uses. Alternatively, if it's allocatable,
     644             :         // it could get allocated to something with a def during allocation.
     645      307364 :         if (!MRI->isConstantPhysReg(Reg))
     646             :           return nullptr;
     647      989064 :       } else if (!MO.isDead()) {
     648             :         // A def that isn't dead. We can't move it.
     649             :         return nullptr;
     650             :       }
     651             :     } else {
     652             :       // Virtual register uses are always safe to sink.
     653      982192 :       if (MO.isUse()) continue;
     654             : 
     655             :       // If it's not safe to move defs of the register class, then abort.
     656     1492726 :       if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
     657             :         return nullptr;
     658             : 
     659             :       // Virtual register defs can only be sunk if all their uses are in blocks
     660             :       // dominated by one of the successors.
     661      745634 :       if (SuccToSinkTo) {
     662             :         // If a previous operand picked a block to sink to, then this operand
     663             :         // must be sinkable to the same block.
     664           6 :         bool LocalUse = false;
     665           6 :         if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
     666             :                                      BreakPHIEdge, LocalUse))
     667           6 :           return nullptr;
     668             : 
     669           0 :         continue;
     670             :       }
     671             : 
     672             :       // Otherwise, we should look at all the successors and decide which one
     673             :       // we should sink to. If we have reliable block frequency information
     674             :       // (frequency != 0) available, give successors with smaller frequencies
     675             :       // higher priority, otherwise prioritize smaller loop depths.
     676      905898 :       for (MachineBasicBlock *SuccBlock :
     677     2236884 :            GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
     678      821464 :         bool LocalUse = false;
     679      821464 :         if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
     680             :                                     BreakPHIEdge, LocalUse)) {
     681      103402 :           SuccToSinkTo = SuccBlock;
     682      103402 :           break;
     683             :         }
     684      718062 :         if (LocalUse)
     685             :           // Def is used locally, it's never safe to move this def.
     686      633628 :           return nullptr;
     687             :       }
     688             : 
     689             :       // If we couldn't find a block to sink to, ignore this instruction.
     690      112000 :       if (!SuccToSinkTo)
     691             :         return nullptr;
     692      103402 :       if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
     693             :         return nullptr;
     694             :     }
     695             :   }
     696             : 
     697             :   // It is not possible to sink an instruction into its own block.  This can
     698             :   // happen with loops.
     699       30358 :   if (MBB == SuccToSinkTo)
     700             :     return nullptr;
     701             : 
     702             :   // It's not safe to sink instructions to EH landing pad. Control flow into
     703             :   // landing pad is implicitly defined.
     704       30358 :   if (SuccToSinkTo && SuccToSinkTo->isEHPad())
     705             :     return nullptr;
     706             : 
     707             :   return SuccToSinkTo;
     708             : }
     709             : 
     710             : /// \brief Return true if MI is likely to be usable as a memory operation by the
     711             : /// implicit null check optimization.
     712             : ///
     713             : /// This is a "best effort" heuristic, and should not be relied upon for
     714             : /// correctness.  This returning true does not guarantee that the implicit null
     715             : /// check optimization is legal over MI, and this returning false does not
     716             : /// guarantee MI cannot possibly be used to do a null check.
     717     1407070 : static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
     718             :                                              const TargetInstrInfo *TII,
     719             :                                              const TargetRegisterInfo *TRI) {
     720             :   using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
     721             : 
     722     1407070 :   auto *MBB = MI.getParent();
     723     1407070 :   if (MBB->pred_size() != 1)
     724             :     return false;
     725             : 
     726      855891 :   auto *PredMBB = *MBB->pred_begin();
     727      855891 :   auto *PredBB = PredMBB->getBasicBlock();
     728             : 
     729             :   // Frontends that don't use implicit null checks have no reason to emit
     730             :   // branches with make.implicit metadata, and this function should always
     731             :   // return false for them.
     732     1686578 :   if (!PredBB ||
     733     1686439 :       !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
     734             :     return false;
     735             : 
     736             :   unsigned BaseReg;
     737             :   int64_t Offset;
     738          11 :   if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
     739             :     return false;
     740             : 
     741           8 :   if (!(MI.mayLoad() && !MI.isPredicable()))
     742             :     return false;
     743             : 
     744           4 :   MachineBranchPredicate MBP;
     745           4 :   if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
     746             :     return false;
     747             : 
     748          12 :   return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
     749           4 :          (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
     750           8 :           MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
     751           4 :          MBP.LHS.getReg() == BaseReg;
     752             : }
     753             : 
     754             : /// SinkInstruction - Determine whether it is safe to sink the specified machine
     755             : /// instruction out of its current block into a successor.
     756     2735912 : bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
     757             :                                      AllSuccsCache &AllSuccessors) {
     758             :   // Don't sink instructions that the target prefers not to sink.
     759     2735912 :   if (!TII->shouldSink(MI))
     760             :     return false;
     761             : 
     762             :   // Check if it's safe to move the instruction.
     763     2735912 :   if (!MI.isSafeToMove(AA, SawStore))
     764             :     return false;
     765             : 
     766             :   // Convergent operations may not be made control-dependent on additional
     767             :   // values.
     768     1407105 :   if (MI.isConvergent())
     769             :     return false;
     770             : 
     771             :   // Don't break implicit null checks.  This is a performance heuristic, and not
     772             :   // required for correctness.
     773     1407070 :   if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
     774             :     return false;
     775             : 
     776             :   // FIXME: This should include support for sinking instructions within the
     777             :   // block they are currently in to shorten the live ranges.  We often get
     778             :   // instructions sunk into the top of a large block, but it would be better to
     779             :   // also sink them down before their first use in the block.  This xform has to
     780             :   // be careful not to *increase* register pressure though, e.g. sinking
     781             :   // "x = y + z" down if it kills y and z would increase the live ranges of y
     782             :   // and z and only shrink the live range of x.
     783             : 
     784     1407066 :   bool BreakPHIEdge = false;
     785     1407066 :   MachineBasicBlock *ParentBlock = MI.getParent();
     786             :   MachineBasicBlock *SuccToSinkTo =
     787     1407066 :       FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
     788             : 
     789             :   // If there are no outputs, it must have side-effects.
     790     1407066 :   if (!SuccToSinkTo)
     791             :     return false;
     792             : 
     793             :   // If the instruction to move defines a dead physical register which is live
     794             :   // when leaving the basic block, don't move it because it could turn into a
     795             :   // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
     796      135227 :   for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
     797      210380 :     const MachineOperand &MO = MI.getOperand(I);
     798      105190 :     if (!MO.isReg()) continue;
     799       75447 :     unsigned Reg = MO.getReg();
     800      136119 :     if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
     801        7414 :     if (SuccToSinkTo->isLiveIn(Reg))
     802             :       return false;
     803             :   }
     804             : 
     805             :   DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
     806             : 
     807             :   // If the block has multiple predecessors, this is a critical edge.
     808             :   // Decide if we can sink along it or need to break the edge.
     809       30037 :   if (SuccToSinkTo->pred_size() > 1) {
     810             :     // We cannot sink a load across a critical edge - there may be stores in
     811             :     // other code paths.
     812       10998 :     bool TryBreak = false;
     813       10998 :     bool store = true;
     814       10998 :     if (!MI.isSafeToMove(AA, store)) {
     815             :       DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
     816             :       TryBreak = true;
     817             :     }
     818             : 
     819             :     // We don't want to sink across a critical edge if we don't dominate the
     820             :     // successor. We could be introducing calculations to new code paths.
     821       21564 :     if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
     822             :       DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
     823             :       TryBreak = true;
     824             :     }
     825             : 
     826             :     // Don't sink instructions into a loop.
     827       13984 :     if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
     828             :       DEBUG(dbgs() << " *** NOTE: Loop header found\n");
     829             :       TryBreak = true;
     830             :     }
     831             : 
     832             :     // Otherwise we are OK with sinking along a critical edge.
     833       10993 :     if (!TryBreak)
     834             :       DEBUG(dbgs() << "Sinking along critical edge.\n");
     835             :     else {
     836             :       // Mark this edge as to be split.
     837             :       // If the edge can actually be split, the next iteration of the main loop
     838             :       // will sink MI in the newly created block.
     839             :       bool Status =
     840        4119 :         PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
     841             :       if (!Status)
     842             :         DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
     843             :               "break critical edge\n");
     844             :       // The instruction will not be sunk this time.
     845        4119 :       return false;
     846             :     }
     847             :   }
     848             : 
     849       25918 :   if (BreakPHIEdge) {
     850             :     // BreakPHIEdge is true if all the uses are in the successor MBB being
     851             :     // sunken into and they are all PHI nodes. In this case, machine-sink must
     852             :     // break the critical edge first.
     853             :     bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
     854        4620 :                                             SuccToSinkTo, BreakPHIEdge);
     855             :     if (!Status)
     856             :       DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
     857             :             "break critical edge\n");
     858             :     // The instruction will not be sunk this time.
     859        4620 :     return false;
     860             :   }
     861             : 
     862             :   // Determine where to insert into. Skip phi nodes.
     863       21298 :   MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
     864       68046 :   while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
     865             :     ++InsertPos;
     866             : 
     867             :   // collect matching debug values.
     868       21298 :   SmallVector<MachineInstr *, 2> DbgValuesToSink;
     869       21298 :   collectDebugValues(MI, DbgValuesToSink);
     870             : 
     871             :   // Move the instruction.
     872       42596 :   SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
     873       63894 :                        ++MachineBasicBlock::iterator(MI));
     874             : 
     875             :   // Move debug values.
     876       22547 :   for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
     877       21298 :          DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) {
     878        1249 :     MachineInstr *DbgMI = *DBI;
     879        2498 :     SuccToSinkTo->splice(InsertPos, ParentBlock,  DbgMI,
     880        3747 :                          ++MachineBasicBlock::iterator(DbgMI));
     881             :   }
     882             : 
     883             :   // Conservatively, clear any kill flags, since it's possible that they are no
     884             :   // longer correct.
     885             :   // Note that we have to clear the kill flags for any register this instruction
     886             :   // uses as we may sink over another instruction which currently kills the
     887             :   // used registers.
     888       95458 :   for (MachineOperand &MO : MI.operands()) {
     889      126931 :     if (MO.isReg() && MO.isUse())
     890       28725 :       RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
     891             :   }
     892             : 
     893       21298 :   return true;
     894      216918 : }

Generated by: LCOV version 1.13