LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineCSE.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 240 243 98.8 %
Date: 2018-02-23 15:42:53 Functions: 19 19 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- MachineCSE.cpp - Machine Common Subexpression Elimination Pass -----===//
       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 performs global common subexpression elimination on machine
      11             : // instructions using a scoped hash table based value numbering scheme. It
      12             : // must be run while the machine function is still in SSA form.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #include "llvm/ADT/DenseMap.h"
      17             : #include "llvm/ADT/ScopedHashTable.h"
      18             : #include "llvm/ADT/SmallPtrSet.h"
      19             : #include "llvm/ADT/SmallSet.h"
      20             : #include "llvm/ADT/SmallVector.h"
      21             : #include "llvm/ADT/Statistic.h"
      22             : #include "llvm/Analysis/AliasAnalysis.h"
      23             : #include "llvm/CodeGen/MachineBasicBlock.h"
      24             : #include "llvm/CodeGen/MachineDominators.h"
      25             : #include "llvm/CodeGen/MachineFunction.h"
      26             : #include "llvm/CodeGen/MachineFunctionPass.h"
      27             : #include "llvm/CodeGen/MachineInstr.h"
      28             : #include "llvm/CodeGen/MachineOperand.h"
      29             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      30             : #include "llvm/CodeGen/Passes.h"
      31             : #include "llvm/CodeGen/TargetInstrInfo.h"
      32             : #include "llvm/CodeGen/TargetOpcodes.h"
      33             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      34             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      35             : #include "llvm/MC/MCInstrDesc.h"
      36             : #include "llvm/MC/MCRegisterInfo.h"
      37             : #include "llvm/Pass.h"
      38             : #include "llvm/Support/Allocator.h"
      39             : #include "llvm/Support/Debug.h"
      40             : #include "llvm/Support/RecyclingAllocator.h"
      41             : #include "llvm/Support/raw_ostream.h"
      42             : #include <cassert>
      43             : #include <iterator>
      44             : #include <utility>
      45             : #include <vector>
      46             : 
      47             : using namespace llvm;
      48             : 
      49             : #define DEBUG_TYPE "machine-cse"
      50             : 
      51             : STATISTIC(NumCoalesces, "Number of copies coalesced");
      52             : STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
      53             : STATISTIC(NumPhysCSEs,
      54             :           "Number of physreg referencing common subexpr eliminated");
      55             : STATISTIC(NumCrossBBCSEs,
      56             :           "Number of cross-MBB physreg referencing CS eliminated");
      57             : STATISTIC(NumCommutes,  "Number of copies coalesced after commuting");
      58             : 
      59             : namespace {
      60             : 
      61       75724 :   class MachineCSE : public MachineFunctionPass {
      62             :     const TargetInstrInfo *TII;
      63             :     const TargetRegisterInfo *TRI;
      64             :     AliasAnalysis *AA;
      65             :     MachineDominatorTree *DT;
      66             :     MachineRegisterInfo *MRI;
      67             : 
      68             :   public:
      69             :     static char ID; // Pass identification
      70             : 
      71       38080 :     MachineCSE() : MachineFunctionPass(ID) {
      72       19040 :       initializeMachineCSEPass(*PassRegistry::getPassRegistry());
      73       19040 :     }
      74             : 
      75             :     bool runOnMachineFunction(MachineFunction &MF) override;
      76             : 
      77       18930 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      78       18930 :       AU.setPreservesCFG();
      79       18930 :       MachineFunctionPass::getAnalysisUsage(AU);
      80             :       AU.addRequired<AAResultsWrapperPass>();
      81       18930 :       AU.addPreservedID(MachineLoopInfoID);
      82             :       AU.addRequired<MachineDominatorTree>();
      83             :       AU.addPreserved<MachineDominatorTree>();
      84       18930 :     }
      85             : 
      86      175900 :     void releaseMemory() override {
      87      175900 :       ScopeMap.clear();
      88             :       Exps.clear();
      89      175900 :     }
      90             : 
      91             :   private:
      92             :     using AllocatorTy = RecyclingAllocator<BumpPtrAllocator,
      93             :                             ScopedHashTableVal<MachineInstr *, unsigned>>;
      94             :     using ScopedHTType =
      95             :         ScopedHashTable<MachineInstr *, unsigned, MachineInstrExpressionTrait,
      96             :                         AllocatorTy>;
      97             :     using ScopeType = ScopedHTType::ScopeTy;
      98             : 
      99             :     unsigned LookAheadLimit = 0;
     100             :     DenseMap<MachineBasicBlock *, ScopeType *> ScopeMap;
     101             :     ScopedHTType VNT;
     102             :     SmallVector<MachineInstr *, 64> Exps;
     103             :     unsigned CurrVN = 0;
     104             : 
     105             :     bool PerformTrivialCopyPropagation(MachineInstr *MI,
     106             :                                        MachineBasicBlock *MBB);
     107             :     bool isPhysDefTriviallyDead(unsigned Reg,
     108             :                                 MachineBasicBlock::const_iterator I,
     109             :                                 MachineBasicBlock::const_iterator E) const;
     110             :     bool hasLivePhysRegDefUses(const MachineInstr *MI,
     111             :                                const MachineBasicBlock *MBB,
     112             :                                SmallSet<unsigned,8> &PhysRefs,
     113             :                                SmallVectorImpl<unsigned> &PhysDefs,
     114             :                                bool &PhysUseDef) const;
     115             :     bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
     116             :                           SmallSet<unsigned,8> &PhysRefs,
     117             :                           SmallVectorImpl<unsigned> &PhysDefs,
     118             :                           bool &NonLocal) const;
     119             :     bool isCSECandidate(MachineInstr *MI);
     120             :     bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
     121             :                            MachineInstr *CSMI, MachineInstr *MI);
     122             :     void EnterScope(MachineBasicBlock *MBB);
     123             :     void ExitScope(MachineBasicBlock *MBB);
     124             :     bool ProcessBlock(MachineBasicBlock *MBB);
     125             :     void ExitScopeIfDone(MachineDomTreeNode *Node,
     126             :                          DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren);
     127             :     bool PerformCSE(MachineDomTreeNode *Node);
     128             :   };
     129             : 
     130             : } // end anonymous namespace
     131             : 
     132             : char MachineCSE::ID = 0;
     133             : 
     134             : char &llvm::MachineCSEID = MachineCSE::ID;
     135             : 
     136       22315 : INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE,
     137             :                       "Machine Common Subexpression Elimination", false, false)
     138       22315 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     139       22315 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     140      164536 : INITIALIZE_PASS_END(MachineCSE, DEBUG_TYPE,
     141             :                     "Machine Common Subexpression Elimination", false, false)
     142             : 
     143             : /// The source register of a COPY machine instruction can be propagated to all
     144             : /// its users, and this propagation could increase the probability of finding
     145             : /// common subexpressions. If the COPY has only one user, the COPY itself can
     146             : /// be removed.
     147     1279832 : bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI,
     148             :                                                MachineBasicBlock *MBB) {
     149             :   bool Changed = false;
     150    13501926 :   for (MachineOperand &MO : MI->operands()) {
     151    10062950 :     if (!MO.isReg() || !MO.isUse())
     152             :       continue;
     153     2419667 :     unsigned Reg = MO.getReg();
     154     2419667 :     if (!TargetRegisterInfo::isVirtualRegister(Reg))
     155             :       continue;
     156     1531477 :     bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg);
     157     1531477 :     MachineInstr *DefMI = MRI->getVRegDef(Reg);
     158     1531477 :     if (!DefMI->isCopy())
     159             :       continue;
     160      495270 :     unsigned SrcReg = DefMI->getOperand(1).getReg();
     161      495270 :     if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
     162             :       continue;
     163      249946 :     if (DefMI->getOperand(0).getSubReg())
     164             :       continue;
     165             :     // FIXME: We should trivially coalesce subregister copies to expose CSE
     166             :     // opportunities on instructions with truncated operands (see
     167             :     // cse-add-with-overflow.ll). This can be done here as follows:
     168             :     // if (SrcSubReg)
     169             :     //  RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC,
     170             :     //                                     SrcSubReg);
     171             :     // MO.substVirtReg(SrcReg, SrcSubReg, *TRI);
     172             :     //
     173             :     // The 2-addr pass has been updated to handle coalesced subregs. However,
     174             :     // some machine-specific code still can't handle it.
     175             :     // To handle it properly we also need a way find a constrained subregister
     176             :     // class given a super-reg class and subreg index.
     177      249934 :     if (DefMI->getOperand(1).getSubReg())
     178             :       continue;
     179       97312 :     if (!MRI->constrainRegAttrs(SrcReg, Reg))
     180             :       continue;
     181             :     DEBUG(dbgs() << "Coalescing: " << *DefMI);
     182             :     DEBUG(dbgs() << "***     to: " << *MI);
     183             :     // Propagate SrcReg of copies to MI.
     184       57106 :     MO.setReg(SrcReg);
     185       57106 :     MRI->clearKillFlags(SrcReg);
     186             :     // Coalesce single use copies.
     187       57106 :     if (OnlyOneUse) {
     188       46775 :       DefMI->eraseFromParent();
     189             :       ++NumCoalesces;
     190             :     }
     191             :     Changed = true;
     192             :   }
     193             : 
     194     1279832 :   return Changed;
     195             : }
     196             : 
     197             : bool
     198       28986 : MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
     199             :                                    MachineBasicBlock::const_iterator I,
     200             :                                    MachineBasicBlock::const_iterator E) const {
     201       28986 :   unsigned LookAheadLeft = LookAheadLimit;
     202       46430 :   while (LookAheadLeft) {
     203             :     // Skip over dbg_value's.
     204       46388 :     I = skipDebugInstructionsForward(I, E);
     205             : 
     206       46388 :     if (I == E)
     207             :       // Reached end of block, we don't know if register is dead or not.
     208             :       return false;
     209             : 
     210             :     bool SeenDef = false;
     211      271635 :     for (const MachineOperand &MO : I->operands()) {
     212      141599 :       if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
     213             :         SeenDef = true;
     214      202448 :       if (!MO.isReg() || !MO.getReg())
     215             :         continue;
     216      131705 :       if (!TRI->regsOverlap(MO.getReg(), Reg))
     217             :         continue;
     218       29219 :       if (MO.isUse())
     219             :         // Found a use!
     220             :         return false;
     221             :       SeenDef = true;
     222             :     }
     223       17525 :     if (SeenDef)
     224             :       // See a def of Reg (or an alias) before encountering any use, it's
     225             :       // trivially dead.
     226             :       return true;
     227             : 
     228       17444 :     --LookAheadLeft;
     229             :     ++I;
     230             :   }
     231             :   return false;
     232             : }
     233             : 
     234             : /// hasLivePhysRegDefUses - Return true if the specified instruction read/write
     235             : /// physical registers (except for dead defs of physical registers). It also
     236             : /// returns the physical register def by reference if it's the only one and the
     237             : /// instruction does not uses a physical register.
     238      458759 : bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI,
     239             :                                        const MachineBasicBlock *MBB,
     240             :                                        SmallSet<unsigned,8> &PhysRefs,
     241             :                                        SmallVectorImpl<unsigned> &PhysDefs,
     242             :                                        bool &PhysUseDef) const{
     243             :   // First, add all uses to PhysRefs.
     244     6343449 :   for (const MachineOperand &MO : MI->operands()) {
     245     4909980 :     if (!MO.isReg() || MO.isDef())
     246     2062795 :       continue;
     247      879550 :     unsigned Reg = MO.getReg();
     248      879550 :     if (!Reg)
     249      156871 :       continue;
     250      722679 :     if (TargetRegisterInfo::isVirtualRegister(Reg))
     251       62277 :       continue;
     252             :     // Reading either caller preserved or constant physregs is ok.
     253      660402 :     if (!MRI->isCallerPreservedOrConstPhysReg(Reg))
     254     4395454 :       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     255     1564978 :         PhysRefs.insert(*AI);
     256             :   }
     257             : 
     258             :   // Next, collect all defs into PhysDefs.  If any is already in PhysRefs
     259             :   // (which currently contains only uses), set the PhysUseDef flag.
     260      458759 :   PhysUseDef = false;
     261             :   MachineBasicBlock::const_iterator I = MI; I = std::next(I);
     262     6343449 :   for (const MachineOperand &MO : MI->operands()) {
     263     6764240 :     if (!MO.isReg() || !MO.isDef())
     264     3837278 :       continue;
     265     1088085 :     unsigned Reg = MO.getReg();
     266     1088085 :     if (!Reg)
     267           0 :       continue;
     268     1088085 :     if (TargetRegisterInfo::isVirtualRegister(Reg))
     269      128758 :       continue;
     270             :     // Check against PhysRefs even if the def is "dead".
     271      959327 :     if (PhysRefs.count(Reg))
     272      617550 :       PhysUseDef = true;
     273             :     // If the def is dead, it's ok. But the def may not marked "dead". That's
     274             :     // common since this pass is run before livevariables. We can scan
     275             :     // forward a few instructions and check if it is obviously dead.
     276      988313 :     if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end()))
     277       28905 :       PhysDefs.push_back(Reg);
     278             :   }
     279             : 
     280             :   // Finally, add all defs to PhysRefs as well.
     281      487664 :   for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i)
     282      172093 :     for (MCRegAliasIterator AI(PhysDefs[i], TRI, true); AI.isValid(); ++AI)
     283       42689 :       PhysRefs.insert(*AI);
     284             : 
     285      458759 :   return !PhysRefs.empty();
     286             : }
     287             : 
     288       41651 : bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
     289             :                                   SmallSet<unsigned,8> &PhysRefs,
     290             :                                   SmallVectorImpl<unsigned> &PhysDefs,
     291             :                                   bool &NonLocal) const {
     292             :   // For now conservatively returns false if the common subexpression is
     293             :   // not in the same basic block as the given instruction. The only exception
     294             :   // is if the common subexpression is in the sole predecessor block.
     295       41651 :   const MachineBasicBlock *MBB = MI->getParent();
     296       41651 :   const MachineBasicBlock *CSMBB = CSMI->getParent();
     297             : 
     298             :   bool CrossMBB = false;
     299       41651 :   if (CSMBB != MBB) {
     300       14687 :     if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
     301             :       return false;
     302             : 
     303        1703 :     for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
     304        1070 :       if (MRI->isAllocatable(PhysDefs[i]) || MRI->isReserved(PhysDefs[i]))
     305             :         // Avoid extending live range of physical registers if they are
     306             :         //allocatable or reserved.
     307             :         return false;
     308             :     }
     309             :     CrossMBB = true;
     310             :   }
     311       28394 :   MachineBasicBlock::const_iterator I = CSMI; I = std::next(I);
     312             :   MachineBasicBlock::const_iterator E = MI;
     313             :   MachineBasicBlock::const_iterator EE = CSMBB->end();
     314       28394 :   unsigned LookAheadLeft = LookAheadLimit;
     315      728283 :   while (LookAheadLeft) {
     316             :     // Skip over dbg_value's.
     317     1449237 :     while (I != E && I != EE && I->isDebugValue())
     318             :       ++I;
     319             : 
     320      728128 :     if (I == EE) {
     321             :       assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
     322             :       (void)CrossMBB;
     323             :       CrossMBB = false;
     324         206 :       NonLocal = true;
     325         206 :       I = MBB->begin();
     326             :       EE = MBB->end();
     327             :       continue;
     328             :     }
     329             : 
     330      727716 :     if (I == E)
     331             :       return true;
     332             : 
     333     6181159 :     for (const MachineOperand &MO : I->operands()) {
     334             :       // RegMasks go on instructions like calls that clobber lots of physregs.
     335             :       // Don't attempt to CSE across such an instruction.
     336     2751490 :       if (MO.isRegMask())
     337       21504 :         return false;
     338     6876695 :       if (!MO.isReg() || !MO.isDef())
     339     2723066 :         continue;
     340      680878 :       unsigned MOReg = MO.getReg();
     341     1333360 :       if (TargetRegisterInfo::isVirtualRegister(MOReg))
     342             :         continue;
     343       28396 :       if (PhysRefs.count(MOReg))
     344             :         return false;
     345             :     }
     346             : 
     347      699683 :     --LookAheadLeft;
     348             :     ++I;
     349             :   }
     350             : 
     351             :   return false;
     352             : }
     353             : 
     354     4605056 : bool MachineCSE::isCSECandidate(MachineInstr *MI) {
     355     4491239 :   if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() ||
     356     4444378 :       MI->isInlineAsm() || MI->isDebugValue())
     357             :     return false;
     358             : 
     359             :   // Ignore copies.
     360             :   if (MI->isCopyLike())
     361             :     return false;
     362             : 
     363             :   // Ignore stuff that we obviously can't move.
     364     9936529 :   if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
     365     1989560 :       MI->hasUnmodeledSideEffects())
     366             :     return false;
     367             : 
     368     1958221 :   if (MI->mayLoad()) {
     369             :     // Okay, this instruction does a load. As a refinement, we allow the target
     370             :     // to decide whether the loaded value is actually a constant. If so, we can
     371             :     // actually use it as a load.
     372      342776 :     if (!MI->isDereferenceableInvariantLoad(AA))
     373             :       // FIXME: we should be able to hoist loads with no other side effects if
     374             :       // there are no other instructions which can change memory in this loop.
     375             :       // This is a trivial form of alias analysis.
     376             :       return false;
     377             :   }
     378             : 
     379             :   // Ignore stack guard loads, otherwise the register that holds CSEed value may
     380             :   // be spilled and get loaded back with corrupted data.
     381     3476350 :   if (MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
     382             :     return false;
     383             : 
     384             :   return true;
     385             : }
     386             : 
     387             : /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
     388             : /// common expression that defines Reg.
     389      107207 : bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
     390             :                                    MachineInstr *CSMI, MachineInstr *MI) {
     391             :   // FIXME: Heuristics that works around the lack the live range splitting.
     392             : 
     393             :   // If CSReg is used at all uses of Reg, CSE should not increase register
     394             :   // pressure of CSReg.
     395             :   bool MayIncreasePressure = true;
     396      214414 :   if (TargetRegisterInfo::isVirtualRegister(CSReg) &&
     397             :       TargetRegisterInfo::isVirtualRegister(Reg)) {
     398             :     MayIncreasePressure = false;
     399             :     SmallPtrSet<MachineInstr*, 8> CSUses;
     400     3059145 :     for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
     401     1368762 :       CSUses.insert(&MI);
     402             :     }
     403      322061 :     for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
     404      107107 :       if (!CSUses.count(&MI)) {
     405             :         MayIncreasePressure = true;
     406             :         break;
     407             :       }
     408             :     }
     409             :   }
     410      107207 :   if (!MayIncreasePressure) return true;
     411             : 
     412             :   // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
     413             :   // an immediate predecessor. We don't want to increase register pressure and
     414             :   // end up causing other computation to be spilled.
     415      106887 :   if (TII->isAsCheapAsAMove(*MI)) {
     416       27597 :     MachineBasicBlock *CSBB = CSMI->getParent();
     417       27597 :     MachineBasicBlock *BB = MI->getParent();
     418       27597 :     if (CSBB != BB && !CSBB->isSuccessor(BB))
     419             :       return false;
     420             :   }
     421             : 
     422             :   // Heuristics #2: If the expression doesn't not use a vr and the only use
     423             :   // of the redundant computation are copies, do not cse.
     424             :   bool HasVRegUse = false;
     425      840888 :   for (const MachineOperand &MO : MI->operands()) {
     426      814935 :     if (MO.isReg() && MO.isUse() &&
     427      163258 :         TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
     428             :       HasVRegUse = true;
     429             :       break;
     430             :     }
     431             :   }
     432       88838 :   if (!HasVRegUse) {
     433             :     bool HasNonCopyUse = false;
     434      284926 :     for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
     435             :       // Ignore copies.
     436             :       if (!MI.isCopyLike()) {
     437             :         HasNonCopyUse = true;
     438             :         break;
     439             :       }
     440             :     }
     441       66432 :     if (!HasNonCopyUse)
     442             :       return false;
     443             :   }
     444             : 
     445             :   // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
     446             :   // it unless the defined value is already used in the BB of the new use.
     447             :   bool HasPHI = false;
     448             :   SmallPtrSet<MachineBasicBlock*, 4> CSBBs;
     449     2475236 :   for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
     450     1162708 :     HasPHI |= MI.isPHI();
     451     1162708 :     CSBBs.insert(MI.getParent());
     452             :   }
     453             : 
     454       49940 :   if (!HasPHI)
     455             :     return true;
     456         404 :   return CSBBs.count(MI->getParent());
     457             : }
     458             : 
     459      326406 : void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
     460             :   DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
     461      326406 :   ScopeType *Scope = new ScopeType(VNT);
     462      652812 :   ScopeMap[MBB] = Scope;
     463      326406 : }
     464             : 
     465      326406 : void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
     466             :   DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
     467      326406 :   DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB);
     468             :   assert(SI != ScopeMap.end());
     469      326405 :   delete SI->second;
     470             :   ScopeMap.erase(SI);
     471      326406 : }
     472             : 
     473      326406 : bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) {
     474             :   bool Changed = false;
     475             : 
     476             :   SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
     477             :   SmallVector<unsigned, 2> ImplicitDefsToUpdate;
     478             :   SmallVector<unsigned, 2> ImplicitDefs;
     479     5257868 :   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
     480     4605056 :     MachineInstr *MI = &*I;
     481             :     ++I;
     482             : 
     483     4605056 :     if (!isCSECandidate(MI))
     484     7358639 :       continue;
     485             : 
     486     1737911 :     bool FoundCSE = VNT.count(MI);
     487             :     if (!FoundCSE) {
     488             :       // Using trivial copy propagation to find more CSE opportunities.
     489     1279832 :       if (PerformTrivialCopyPropagation(MI, MBB)) {
     490             :         Changed = true;
     491             : 
     492             :         // After coalescing MI itself may become a copy.
     493       39572 :         if (MI->isCopyLike())
     494           0 :           continue;
     495             : 
     496             :         // Try again to see if CSE is possible.
     497       39572 :         FoundCSE = VNT.count(MI);
     498             :       }
     499             :     }
     500             : 
     501             :     // Commute commutable instructions.
     502             :     bool Commuted = false;
     503     3017077 :     if (!FoundCSE && MI->isCommutable()) {
     504      215219 :       if (MachineInstr *NewMI = TII->commuteInstruction(*MI)) {
     505             :         Commuted = true;
     506      187815 :         FoundCSE = VNT.count(NewMI);
     507      187815 :         if (NewMI != MI) {
     508             :           // New instruction. It doesn't need to be kept.
     509           0 :           NewMI->eraseFromParent();
     510             :           Changed = true;
     511      187815 :         } else if (!FoundCSE)
     512             :           // MI was changed but it didn't help, commute it back!
     513      187801 :           (void)TII->commuteInstruction(*MI);
     514             :       }
     515             :     }
     516             : 
     517             :     // If the instruction defines physical registers and the values *may* be
     518             :     // used, then it's not safe to replace it with a common subexpression.
     519             :     // It's also not safe if the instruction uses physical registers.
     520     1737911 :     bool CrossMBBPhysDef = false;
     521      113562 :     SmallSet<unsigned, 8> PhysRefs;
     522             :     SmallVector<unsigned, 2> PhysDefs;
     523     1737911 :     bool PhysUseDef = false;
     524     1737911 :     if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs,
     525             :                                           PhysDefs, PhysUseDef)) {
     526             :       FoundCSE = false;
     527             : 
     528             :       // ... Unless the CS is local or is in the sole predecessor block
     529             :       // and it also defines the physical register which is not clobbered
     530             :       // in between and the physical register uses were not clobbered.
     531             :       // This can never be the case if the instruction both uses and
     532             :       // defines the same physical register, which was detected above.
     533      351726 :       if (!PhysUseDef) {
     534       41651 :         unsigned CSVN = VNT.lookup(MI);
     535       83302 :         MachineInstr *CSMI = Exps[CSVN];
     536       41651 :         if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
     537             :           FoundCSE = true;
     538             :       }
     539             :     }
     540             : 
     541     3010534 :     if (!FoundCSE) {
     542     3248698 :       VNT.insert(MI, CurrVN++);
     543     1624349 :       Exps.push_back(MI);
     544             :       continue;
     545             :     }
     546             : 
     547             :     // Found a common subexpression, eliminate it.
     548      113562 :     unsigned CSVN = VNT.lookup(MI);
     549      227124 :     MachineInstr *CSMI = Exps[CSVN];
     550             :     DEBUG(dbgs() << "Examining: " << *MI);
     551             :     DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
     552             : 
     553             :     // Check if it's profitable to perform this CSE.
     554             :     bool DoCSE = true;
     555      113562 :     unsigned NumDefs = MI->getDesc().getNumDefs() +
     556      227124 :                        MI->getDesc().getNumImplicitDefs();
     557             : 
     558      172125 :     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
     559      115850 :       MachineOperand &MO = MI->getOperand(i);
     560      232740 :       if (!MO.isReg() || !MO.isDef())
     561       10215 :         continue;
     562      114278 :       unsigned OldReg = MO.getReg();
     563      228556 :       unsigned NewReg = CSMI->getOperand(i).getReg();
     564             : 
     565             :       // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
     566             :       // we should make sure it is not dead at CSMI.
     567      115417 :       if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
     568          26 :         ImplicitDefsToUpdate.push_back(i);
     569             : 
     570             :       // Keep track of implicit defs of CSMI and MI, to clear possibly
     571             :       // made-redundant kill flags.
     572      115134 :       if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
     573         283 :         ImplicitDefs.push_back(OldReg);
     574             : 
     575      121349 :       if (OldReg == NewReg) {
     576        7071 :         --NumDefs;
     577        7071 :         continue;
     578             :       }
     579             : 
     580             :       assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
     581             :              TargetRegisterInfo::isVirtualRegister(NewReg) &&
     582             :              "Do not CSE physical register defs!");
     583             : 
     584      107207 :       if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
     585             :         DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
     586             :         DoCSE = false;
     587       57287 :         break;
     588             :       }
     589             : 
     590             :       // Don't perform CSE if the result of the new instruction cannot exist
     591             :       // within the constraints (register class, bank, or low-level type) of
     592             :       // the old instruction.
     593       49924 :       if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
     594             :         DEBUG(dbgs() << "*** Not the same register constraints, avoid CSE!\n");
     595             :         DoCSE = false;
     596             :         break;
     597             :       }
     598             : 
     599       49920 :       CSEPairs.push_back(std::make_pair(OldReg, NewReg));
     600       49920 :       --NumDefs;
     601             :     }
     602             : 
     603             :     // Actually perform the elimination.
     604             :     if (DoCSE) {
     605      156115 :       for (std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
     606       49920 :         unsigned OldReg = CSEPair.first;
     607       49920 :         unsigned NewReg = CSEPair.second;
     608             :         // OldReg may have been unused but is used now, clear the Dead flag
     609       49920 :         MachineInstr *Def = MRI->getUniqueVRegDef(NewReg);
     610             :         assert(Def != nullptr && "CSEd register has no unique definition?");
     611       49920 :         Def->clearRegisterDeads(NewReg);
     612             :         // Replace with NewReg and clear kill flags which may be wrong now.
     613       49920 :         MRI->replaceRegWith(OldReg, NewReg);
     614       49920 :         MRI->clearKillFlags(NewReg);
     615             :       }
     616             : 
     617             :       // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
     618             :       // we should make sure it is not dead at CSMI.
     619       56327 :       for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
     620          26 :         CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false);
     621             : 
     622             :       // Go through implicit defs of CSMI and MI, and clear the kill flags on
     623             :       // their uses in all the instructions between CSMI and MI.
     624             :       // We might have made some of the kill flags redundant, consider:
     625             :       //   subs  ... implicit-def %nzcv    <- CSMI
     626             :       //   csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
     627             :       //   subs  ... implicit-def %nzcv    <- MI, to be eliminated
     628             :       //   csinc ... implicit killed %nzcv
     629             :       // Since we eliminated MI, and reused a register imp-def'd by CSMI
     630             :       // (here %nzcv), that register, if it was killed before MI, should have
     631             :       // that kill flag removed, because it's lifetime was extended.
     632       56275 :       if (CSMI->getParent() == MI->getParent()) {
     633      689056 :         for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II)
     634      682066 :           for (auto ImplicitDef : ImplicitDefs)
     635         319 :             if (MachineOperand *MO = II->findRegisterUseOperand(
     636             :                     ImplicitDef, /*isKill=*/true, TRI))
     637             :               MO->setIsKill(false);
     638             :       } else {
     639             :         // If the instructions aren't in the same BB, bail out and clear the
     640             :         // kill flag on all uses of the imp-def'd register.
     641       48957 :         for (auto ImplicitDef : ImplicitDefs)
     642         155 :           MRI->clearKillFlags(ImplicitDef);
     643             :       }
     644             : 
     645       56275 :       if (CrossMBBPhysDef) {
     646             :         // Add physical register defs now coming in from a predecessor to MBB
     647             :         // livein list.
     648         317 :         while (!PhysDefs.empty()) {
     649             :           unsigned LiveIn = PhysDefs.pop_back_val();
     650         155 :           if (!MBB->isLiveIn(LiveIn))
     651             :             MBB->addLiveIn(LiveIn);
     652             :         }
     653             :         ++NumCrossBBCSEs;
     654             :       }
     655             : 
     656       56275 :       MI->eraseFromParent();
     657             :       ++NumCSEs;
     658             :       if (!PhysRefs.empty())
     659             :         ++NumPhysCSEs;
     660             :       if (Commuted)
     661             :         ++NumCommutes;
     662             :       Changed = true;
     663             :     } else {
     664      114574 :       VNT.insert(MI, CurrVN++);
     665       57287 :       Exps.push_back(MI);
     666             :     }
     667             :     CSEPairs.clear();
     668             :     ImplicitDefsToUpdate.clear();
     669             :     ImplicitDefs.clear();
     670             :   }
     671             : 
     672      326406 :   return Changed;
     673             : }
     674             : 
     675             : /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
     676             : /// dominator tree node if its a leaf or all of its children are done. Walk
     677             : /// up the dominator tree to destroy ancestors which are now done.
     678             : void
     679      326405 : MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
     680             :                         DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) {
     681      326406 :   if (OpenChildren[Node])
     682             :     return;
     683             : 
     684             :   // Pop scope.
     685      248918 :   ExitScope(Node->getBlock());
     686             : 
     687             :   // Now traverse upwards to pop ancestors whose offsprings are all done.
     688      326406 :   while (MachineDomTreeNode *Parent = Node->getIDom()) {
     689      150626 :     unsigned Left = --OpenChildren[Parent];
     690      150626 :     if (Left != 0)
     691             :       break;
     692       77488 :     ExitScope(Parent->getBlock());
     693       77488 :     Node = Parent;
     694       77488 :   }
     695             : }
     696             : 
     697      175780 : bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
     698             :   SmallVector<MachineDomTreeNode*, 32> Scopes;
     699             :   SmallVector<MachineDomTreeNode*, 8> WorkList;
     700             :   DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
     701             : 
     702      175780 :   CurrVN = 0;
     703             : 
     704             :   // Perform a DFS walk to determine the order of visit.
     705      175780 :   WorkList.push_back(Node);
     706             :   do {
     707      326406 :     Node = WorkList.pop_back_val();
     708      326406 :     Scopes.push_back(Node);
     709      326406 :     const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
     710      652811 :     OpenChildren[Node] = Children.size();
     711      326405 :     for (MachineDomTreeNode *Child : Children)
     712      150626 :       WorkList.push_back(Child);
     713      326405 :   } while (!WorkList.empty());
     714             : 
     715             :   // Now perform CSE.
     716             :   bool Changed = false;
     717      828589 :   for (MachineDomTreeNode *Node : Scopes) {
     718      326405 :     MachineBasicBlock *MBB = Node->getBlock();
     719      326405 :     EnterScope(MBB);
     720      326406 :     Changed |= ProcessBlock(MBB);
     721             :     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
     722      326406 :     ExitScopeIfDone(Node, OpenChildren);
     723             :   }
     724             : 
     725      175780 :   return Changed;
     726             : }
     727             : 
     728      175875 : bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
     729      175875 :   if (skipFunction(MF.getFunction()))
     730             :     return false;
     731             : 
     732      175780 :   TII = MF.getSubtarget().getInstrInfo();
     733      175780 :   TRI = MF.getSubtarget().getRegisterInfo();
     734      175780 :   MRI = &MF.getRegInfo();
     735      351560 :   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     736      175780 :   DT = &getAnalysis<MachineDominatorTree>();
     737      175780 :   LookAheadLimit = TII->getMachineCSELookAheadLimit();
     738      351560 :   return PerformCSE(DT->getRootNode());
     739             : }

Generated by: LCOV version 1.13