LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineCSE.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 238 241 98.8 %
Date: 2018-07-13 00:08:38 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       83556 :   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       42002 :     MachineCSE() : MachineFunctionPass(ID) {
      72       21001 :       initializeMachineCSEPass(*PassRegistry::getPassRegistry());
      73       21001 :     }
      74             : 
      75             :     bool runOnMachineFunction(MachineFunction &MF) override;
      76             : 
      77       20846 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      78       20846 :       AU.setPreservesCFG();
      79       20846 :       MachineFunctionPass::getAnalysisUsage(AU);
      80             :       AU.addRequired<AAResultsWrapperPass>();
      81       20846 :       AU.addPreservedID(MachineLoopInfoID);
      82             :       AU.addRequired<MachineDominatorTree>();
      83             :       AU.addPreserved<MachineDominatorTree>();
      84       20846 :     }
      85             : 
      86      201704 :     void releaseMemory() override {
      87      201704 :       ScopeMap.clear();
      88             :       Exps.clear();
      89      201704 :     }
      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       26316 : INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE,
     137             :                       "Machine Common Subexpression Elimination", false, false)
     138       26316 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     139       26316 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     140      188612 : 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     1313406 : bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI,
     148             :                                                MachineBasicBlock *MBB) {
     149             :   bool Changed = false;
     150    13798592 :   for (MachineOperand &MO : MI->operands()) {
     151    10325147 :     if (!MO.isReg() || !MO.isUse())
     152             :       continue;
     153     2500727 :     unsigned Reg = MO.getReg();
     154     2500727 :     if (!TargetRegisterInfo::isVirtualRegister(Reg))
     155             :       continue;
     156     1677596 :     bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg);
     157     1677596 :     MachineInstr *DefMI = MRI->getVRegDef(Reg);
     158     1677596 :     if (!DefMI->isCopy())
     159             :       continue;
     160      585110 :     unsigned SrcReg = DefMI->getOperand(1).getReg();
     161      585110 :     if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
     162             :       continue;
     163      311800 :     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      311788 :     if (DefMI->getOperand(1).getSubReg())
     178             :       continue;
     179      127267 :     if (!MRI->constrainRegAttrs(SrcReg, Reg))
     180             :       continue;
     181             :     LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
     182             :     LLVM_DEBUG(dbgs() << "***     to: " << *MI);
     183             :     // Propagate SrcReg of copies to MI.
     184       73989 :     MO.setReg(SrcReg);
     185       73989 :     MRI->clearKillFlags(SrcReg);
     186             :     // Coalesce single use copies.
     187       73989 :     if (OnlyOneUse) {
     188       62917 :       DefMI->eraseFromParent();
     189             :       ++NumCoalesces;
     190             :     }
     191             :     Changed = true;
     192             :   }
     193             : 
     194     1313406 :   return Changed;
     195             : }
     196             : 
     197             : bool
     198       31916 : MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
     199             :                                    MachineBasicBlock::const_iterator I,
     200             :                                    MachineBasicBlock::const_iterator E) const {
     201       31916 :   unsigned LookAheadLeft = LookAheadLimit;
     202       56315 :   while (LookAheadLeft) {
     203             :     // Skip over dbg_value's.
     204       56269 :     I = skipDebugInstructionsForward(I, E);
     205             : 
     206       56269 :     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      342147 :     for (const MachineOperand &MO : I->operands()) {
     212      174513 :       if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
     213             :         SeenDef = true;
     214      241932 :       if (!MO.isReg() || !MO.getReg())
     215             :         continue;
     216      180250 :       if (!TRI->regsOverlap(MO.getReg(), Reg))
     217             :         continue;
     218       32054 :       if (MO.isUse())
     219             :         // Found a use!
     220             :         return false;
     221             :       SeenDef = true;
     222             :     }
     223       25084 :     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       24399 :     --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      385617 : 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     5116661 :   for (const MachineOperand &MO : MI->operands()) {
     245     3949642 :     if (!MO.isReg() || MO.isDef())
     246     1636489 :       continue;
     247      729033 :     unsigned Reg = MO.getReg();
     248      729033 :     if (!Reg)
     249      161388 :       continue;
     250      567645 :     if (TargetRegisterInfo::isVirtualRegister(Reg))
     251       65259 :       continue;
     252             :     // Reading either caller preserved or constant physregs is ok.
     253      502386 :     if (!MRI->isCallerPreservedOrConstPhysReg(Reg))
     254     6451704 :       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
     255     2752053 :         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      385617 :   PhysUseDef = false;
     261             :   MachineBasicBlock::const_iterator I = MI; I = std::next(I);
     262     5116661 :   for (const MachineOperand &MO : MI->operands()) {
     263     5460077 :     if (!MO.isReg() || !MO.isDef())
     264     3155059 :       continue;
     265      855087 :     unsigned Reg = MO.getReg();
     266      855087 :     if (!Reg)
     267           0 :       continue;
     268      855087 :     if (TargetRegisterInfo::isVirtualRegister(Reg))
     269      134189 :       continue;
     270             :     // Check against PhysRefs even if the def is "dead".
     271      720898 :     if (PhysRefs.count(Reg))
     272      457304 :       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      752814 :     if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end()))
     277       31231 :       PhysDefs.push_back(Reg);
     278             :   }
     279             : 
     280             :   // Finally, add all defs to PhysRefs as well.
     281      416848 :   for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i)
     282      196745 :     for (MCRegAliasIterator AI(PhysDefs[i], TRI, true); AI.isValid(); ++AI)
     283       51526 :       PhysRefs.insert(*AI);
     284             : 
     285      385617 :   return !PhysRefs.empty();
     286             : }
     287             : 
     288       44497 : 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       44497 :   const MachineBasicBlock *MBB = MI->getParent();
     296       44497 :   const MachineBasicBlock *CSMBB = CSMI->getParent();
     297             : 
     298             :   bool CrossMBB = false;
     299       44497 :   if (CSMBB != MBB) {
     300       15245 :     if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
     301             :       return false;
     302             : 
     303        1728 :     for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
     304         950 :       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       30737 :   MachineBasicBlock::const_iterator I = CSMI; I = std::next(I);
     312             :   MachineBasicBlock::const_iterator E = MI;
     313             :   MachineBasicBlock::const_iterator EE = CSMBB->end();
     314       30737 :   unsigned LookAheadLeft = LookAheadLimit;
     315      844975 :   while (LookAheadLeft) {
     316             :     // Skip over dbg_value's.
     317      844623 :     while (I != E && I != EE && I->isDebugInstr())
     318             :       ++I;
     319             : 
     320      844809 :     if (I == EE) {
     321             :       assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
     322             :       (void)CrossMBB;
     323             :       CrossMBB = false;
     324         196 :       NonLocal = true;
     325         196 :       I = MBB->begin();
     326             :       EE = MBB->end();
     327             :       continue;
     328             :     }
     329             : 
     330      844417 :     if (I == E)
     331             :       return true;
     332             : 
     333     7217233 :     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     3212975 :       if (MO.isRegMask())
     337       22759 :         return false;
     338     8016212 :       if (!MO.isReg() || !MO.isDef())
     339     3183098 :         continue;
     340      791870 :       unsigned MOReg = MO.getReg();
     341     1553890 :       if (TargetRegisterInfo::isVirtualRegister(MOReg))
     342             :         continue;
     343       29850 :       if (PhysRefs.count(MOReg))
     344             :         return false;
     345             :     }
     346             : 
     347      814042 :     --LookAheadLeft;
     348             :     ++I;
     349             :   }
     350             : 
     351             :   return false;
     352             : }
     353             : 
     354     4620783 : bool MachineCSE::isCSECandidate(MachineInstr *MI) {
     355     4501467 :   if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() ||
     356             :       MI->isInlineAsm() || MI->isDebugInstr())
     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     9824823 :   if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
     365     1967502 :       MI->hasUnmodeledSideEffects())
     366             :     return false;
     367             : 
     368     1932817 :   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      348954 :     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     3397100 :   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      110756 : 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      221512 :   if (TargetRegisterInfo::isVirtualRegister(CSReg) &&
     397             :       TargetRegisterInfo::isVirtualRegister(Reg)) {
     398             :     MayIncreasePressure = false;
     399             :     SmallPtrSet<MachineInstr*, 8> CSUses;
     400     3143000 :     for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) {
     401     1405366 :       CSUses.insert(&MI);
     402             :     }
     403      332784 :     for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
     404      110664 :       if (!CSUses.count(&MI)) {
     405             :         MayIncreasePressure = true;
     406             :         break;
     407             :       }
     408             :     }
     409             :   }
     410      110756 :   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      110406 :   if (TII->isAsCheapAsAMove(*MI)) {
     416       28782 :     MachineBasicBlock *CSBB = CSMI->getParent();
     417       28782 :     MachineBasicBlock *BB = MI->getParent();
     418       28782 :     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      866380 :   for (const MachineOperand &MO : MI->operands()) {
     426      839427 :     if (MO.isReg() && MO.isUse() &&
     427      168005 :         TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
     428             :       HasVRegUse = true;
     429             :       break;
     430             :     }
     431             :   }
     432       91740 :   if (!HasVRegUse) {
     433             :     bool HasNonCopyUse = false;
     434      293062 :     for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
     435             :       // Ignore copies.
     436             :       if (!MI.isCopyLike()) {
     437             :         HasNonCopyUse = true;
     438             :         break;
     439             :       }
     440             :     }
     441       68602 :     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     2526940 :   for (MachineInstr &UseMI : MRI->use_nodbg_instructions(CSReg)) {
     449     1187444 :     HasPHI |= UseMI.isPHI();
     450     1187444 :     if (UseMI.getParent() == MI->getParent())
     451        1728 :       return true;
     452             :   }
     453             : 
     454       50108 :   return !HasPHI;
     455             : }
     456             : 
     457      359277 : void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
     458             :   LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
     459      359277 :   ScopeType *Scope = new ScopeType(VNT);
     460      718554 :   ScopeMap[MBB] = Scope;
     461      359277 : }
     462             : 
     463      359277 : void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
     464             :   LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
     465      359277 :   DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB);
     466             :   assert(SI != ScopeMap.end());
     467      359277 :   delete SI->second;
     468             :   ScopeMap.erase(SI);
     469      359277 : }
     470             : 
     471      359277 : bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) {
     472             :   bool Changed = false;
     473             : 
     474             :   SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
     475             :   SmallVector<unsigned, 2> ImplicitDefsToUpdate;
     476             :   SmallVector<unsigned, 2> ImplicitDefs;
     477     5339337 :   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
     478     4620783 :     MachineInstr *MI = &*I;
     479             :     ++I;
     480             : 
     481     4620783 :     if (!isCSECandidate(MI))
     482     7425081 :       continue;
     483             : 
     484     1698284 :     bool FoundCSE = VNT.count(MI);
     485             :     if (!FoundCSE) {
     486             :       // Using trivial copy propagation to find more CSE opportunities.
     487     1313406 :       if (PerformTrivialCopyPropagation(MI, MBB)) {
     488             :         Changed = true;
     489             : 
     490             :         // After coalescing MI itself may become a copy.
     491       50240 :         if (MI->isCopyLike())
     492           0 :           continue;
     493             : 
     494             :         // Try again to see if CSE is possible.
     495       50240 :         FoundCSE = VNT.count(MI);
     496             :       }
     497             :     }
     498             : 
     499             :     // Commute commutable instructions.
     500             :     bool Commuted = false;
     501     3010965 :     if (!FoundCSE && MI->isCommutable()) {
     502      239723 :       if (MachineInstr *NewMI = TII->commuteInstruction(*MI)) {
     503             :         Commuted = true;
     504      209260 :         FoundCSE = VNT.count(NewMI);
     505      209260 :         if (NewMI != MI) {
     506             :           // New instruction. It doesn't need to be kept.
     507           0 :           NewMI->eraseFromParent();
     508             :           Changed = true;
     509      209260 :         } else if (!FoundCSE)
     510             :           // MI was changed but it didn't help, commute it back!
     511      209246 :           (void)TII->commuteInstruction(*MI);
     512             :       }
     513             :     }
     514             : 
     515             :     // If the instruction defines physical registers and the values *may* be
     516             :     // used, then it's not safe to replace it with a common subexpression.
     517             :     // It's also not safe if the instruction uses physical registers.
     518     1698284 :     bool CrossMBBPhysDef = false;
     519      118201 :     SmallSet<unsigned, 8> PhysRefs;
     520             :     SmallVector<unsigned, 2> PhysDefs;
     521     1698284 :     bool PhysUseDef = false;
     522     1698284 :     if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs,
     523             :                                           PhysDefs, PhysUseDef)) {
     524             :       FoundCSE = false;
     525             : 
     526             :       // ... Unless the CS is local or is in the sole predecessor block
     527             :       // and it also defines the physical register which is not clobbered
     528             :       // in between and the physical register uses were not clobbered.
     529             :       // This can never be the case if the instruction both uses and
     530             :       // defines the same physical register, which was detected above.
     531      275032 :       if (!PhysUseDef) {
     532       44497 :         unsigned CSVN = VNT.lookup(MI);
     533       88994 :         MachineInstr *CSMI = Exps[CSVN];
     534       44497 :         if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
     535             :           FoundCSE = true;
     536             :       }
     537             :     }
     538             : 
     539     3003335 :     if (!FoundCSE) {
     540     3160166 :       VNT.insert(MI, CurrVN++);
     541     1580083 :       Exps.push_back(MI);
     542             :       continue;
     543             :     }
     544             : 
     545             :     // Found a common subexpression, eliminate it.
     546      118201 :     unsigned CSVN = VNT.lookup(MI);
     547      236402 :     MachineInstr *CSMI = Exps[CSVN];
     548             :     LLVM_DEBUG(dbgs() << "Examining: " << *MI);
     549             :     LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
     550             : 
     551             :     // Check if it's profitable to perform this CSE.
     552             :     bool DoCSE = true;
     553      118201 :     unsigned NumDefs = MI->getNumDefs();
     554             : 
     555      179873 :     for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
     556      120605 :       MachineOperand &MO = MI->getOperand(i);
     557      242260 :       if (!MO.isReg() || !MO.isDef())
     558       11494 :         continue;
     559      118960 :       unsigned OldReg = MO.getReg();
     560      237920 :       unsigned NewReg = CSMI->getOperand(i).getReg();
     561             : 
     562             :       // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
     563             :       // we should make sure it is not dead at CSMI.
     564      120146 :       if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead())
     565           2 :         ImplicitDefsToUpdate.push_back(i);
     566             : 
     567             :       // Keep track of implicit defs of CSMI and MI, to clear possibly
     568             :       // made-redundant kill flags.
     569      119861 :       if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg)
     570         285 :         ImplicitDefs.push_back(OldReg);
     571             : 
     572      127164 :       if (OldReg == NewReg) {
     573        8204 :         --NumDefs;
     574        8204 :         continue;
     575             :       }
     576             : 
     577             :       assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
     578             :              TargetRegisterInfo::isVirtualRegister(NewReg) &&
     579             :              "Do not CSE physical register defs!");
     580             : 
     581      110756 :       if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
     582             :         LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
     583             :         DoCSE = false;
     584       58933 :         break;
     585             :       }
     586             : 
     587             :       // Don't perform CSE if the result of the new instruction cannot exist
     588             :       // within the constraints (register class, bank, or low-level type) of
     589             :       // the old instruction.
     590       51827 :       if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
     591             :         LLVM_DEBUG(
     592             :             dbgs() << "*** Not the same register constraints, avoid CSE!\n");
     593             :         DoCSE = false;
     594             :         break;
     595             :       }
     596             : 
     597       51823 :       CSEPairs.push_back(std::make_pair(OldReg, NewReg));
     598       51823 :       --NumDefs;
     599             :     }
     600             : 
     601             :     // Actually perform the elimination.
     602             :     if (DoCSE) {
     603      162914 :       for (std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
     604       51823 :         unsigned OldReg = CSEPair.first;
     605       51823 :         unsigned NewReg = CSEPair.second;
     606             :         // OldReg may have been unused but is used now, clear the Dead flag
     607       51823 :         MachineInstr *Def = MRI->getUniqueVRegDef(NewReg);
     608             :         assert(Def != nullptr && "CSEd register has no unique definition?");
     609       51823 :         Def->clearRegisterDeads(NewReg);
     610             :         // Replace with NewReg and clear kill flags which may be wrong now.
     611       51823 :         MRI->replaceRegWith(OldReg, NewReg);
     612       51823 :         MRI->clearKillFlags(NewReg);
     613             :       }
     614             : 
     615             :       // Go through implicit defs of CSMI and MI, if a def is not dead at MI,
     616             :       // we should make sure it is not dead at CSMI.
     617       59272 :       for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
     618           2 :         CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false);
     619             : 
     620             :       // Go through implicit defs of CSMI and MI, and clear the kill flags on
     621             :       // their uses in all the instructions between CSMI and MI.
     622             :       // We might have made some of the kill flags redundant, consider:
     623             :       //   subs  ... implicit-def %nzcv    <- CSMI
     624             :       //   csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore
     625             :       //   subs  ... implicit-def %nzcv    <- MI, to be eliminated
     626             :       //   csinc ... implicit killed %nzcv
     627             :       // Since we eliminated MI, and reused a register imp-def'd by CSMI
     628             :       // (here %nzcv), that register, if it was killed before MI, should have
     629             :       // that kill flag removed, because it's lifetime was extended.
     630       59268 :       if (CSMI->getParent() == MI->getParent()) {
     631      837127 :         for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II)
     632      828939 :           for (auto ImplicitDef : ImplicitDefs)
     633         383 :             if (MachineOperand *MO = II->findRegisterUseOperand(
     634             :                     ImplicitDef, /*isKill=*/true, TRI))
     635             :               MO->setIsKill(false);
     636             :       } else {
     637             :         // If the instructions aren't in the same BB, bail out and clear the
     638             :         // kill flag on all uses of the imp-def'd register.
     639       50616 :         for (auto ImplicitDef : ImplicitDefs)
     640         151 :           MRI->clearKillFlags(ImplicitDef);
     641             :       }
     642             : 
     643       59268 :       if (CrossMBBPhysDef) {
     644             :         // Add physical register defs now coming in from a predecessor to MBB
     645             :         // livein list.
     646         301 :         while (!PhysDefs.empty()) {
     647             :           unsigned LiveIn = PhysDefs.pop_back_val();
     648         149 :           if (!MBB->isLiveIn(LiveIn))
     649             :             MBB->addLiveIn(LiveIn);
     650             :         }
     651             :         ++NumCrossBBCSEs;
     652             :       }
     653             : 
     654       59268 :       MI->eraseFromParent();
     655             :       ++NumCSEs;
     656             :       if (!PhysRefs.empty())
     657             :         ++NumPhysCSEs;
     658             :       if (Commuted)
     659             :         ++NumCommutes;
     660             :       Changed = true;
     661             :     } else {
     662      117866 :       VNT.insert(MI, CurrVN++);
     663       58933 :       Exps.push_back(MI);
     664             :     }
     665             :     CSEPairs.clear();
     666             :     ImplicitDefsToUpdate.clear();
     667             :     ImplicitDefs.clear();
     668             :   }
     669             : 
     670      359277 :   return Changed;
     671             : }
     672             : 
     673             : /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
     674             : /// dominator tree node if its a leaf or all of its children are done. Walk
     675             : /// up the dominator tree to destroy ancestors which are now done.
     676             : void
     677      359277 : MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
     678             :                         DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) {
     679      359277 :   if (OpenChildren[Node])
     680             :     return;
     681             : 
     682             :   // Pop scope.
     683      277964 :   ExitScope(Node->getBlock());
     684             : 
     685             :   // Now traverse upwards to pop ancestors whose offsprings are all done.
     686      359277 :   while (MachineDomTreeNode *Parent = Node->getIDom()) {
     687      157750 :     unsigned Left = --OpenChildren[Parent];
     688      157750 :     if (Left != 0)
     689             :       break;
     690       81313 :     ExitScope(Parent->getBlock());
     691       81313 :     Node = Parent;
     692       81313 :   }
     693             : }
     694             : 
     695      201527 : bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
     696             :   SmallVector<MachineDomTreeNode*, 32> Scopes;
     697             :   SmallVector<MachineDomTreeNode*, 8> WorkList;
     698             :   DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
     699             : 
     700      201527 :   CurrVN = 0;
     701             : 
     702             :   // Perform a DFS walk to determine the order of visit.
     703      201527 :   WorkList.push_back(Node);
     704             :   do {
     705      359277 :     Node = WorkList.pop_back_val();
     706      359277 :     Scopes.push_back(Node);
     707      359277 :     const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
     708      718554 :     OpenChildren[Node] = Children.size();
     709      359277 :     for (MachineDomTreeNode *Child : Children)
     710      157750 :       WorkList.push_back(Child);
     711      359277 :   } while (!WorkList.empty());
     712             : 
     713             :   // Now perform CSE.
     714             :   bool Changed = false;
     715      920081 :   for (MachineDomTreeNode *Node : Scopes) {
     716      359277 :     MachineBasicBlock *MBB = Node->getBlock();
     717      359277 :     EnterScope(MBB);
     718      359277 :     Changed |= ProcessBlock(MBB);
     719             :     // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
     720      359277 :     ExitScopeIfDone(Node, OpenChildren);
     721             :   }
     722             : 
     723      201527 :   return Changed;
     724             : }
     725             : 
     726      201685 : bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
     727      201685 :   if (skipFunction(MF.getFunction()))
     728             :     return false;
     729             : 
     730      201527 :   TII = MF.getSubtarget().getInstrInfo();
     731      201527 :   TRI = MF.getSubtarget().getRegisterInfo();
     732      201527 :   MRI = &MF.getRegInfo();
     733      403054 :   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
     734      201527 :   DT = &getAnalysis<MachineDominatorTree>();
     735      201527 :   LookAheadLimit = TII->getMachineCSELookAheadLimit();
     736      403054 :   return PerformCSE(DT->getRootNode());
     737             : }

Generated by: LCOV version 1.13