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

Generated by: LCOV version 1.13