1*0b57cec5SDimitry Andric //===- MachineCSE.cpp - Machine Common Subexpression Elimination Pass -----===// 2*0b57cec5SDimitry Andric // 3*0b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*0b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*0b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*0b57cec5SDimitry Andric // 7*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 8*0b57cec5SDimitry Andric // 9*0b57cec5SDimitry Andric // This pass performs global common subexpression elimination on machine 10*0b57cec5SDimitry Andric // instructions using a scoped hash table based value numbering scheme. It 11*0b57cec5SDimitry Andric // must be run while the machine function is still in SSA form. 12*0b57cec5SDimitry Andric // 13*0b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 14*0b57cec5SDimitry Andric 15*0b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h" 16*0b57cec5SDimitry Andric #include "llvm/ADT/ScopedHashTable.h" 17*0b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h" 18*0b57cec5SDimitry Andric #include "llvm/ADT/SmallSet.h" 19*0b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 20*0b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h" 21*0b57cec5SDimitry Andric #include "llvm/Analysis/AliasAnalysis.h" 22*0b57cec5SDimitry Andric #include "llvm/Analysis/CFG.h" 23*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBasicBlock.h" 24*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 25*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineDominators.h" 26*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunction.h" 27*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h" 28*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineInstr.h" 29*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineOperand.h" 30*0b57cec5SDimitry Andric #include "llvm/CodeGen/MachineRegisterInfo.h" 31*0b57cec5SDimitry Andric #include "llvm/CodeGen/Passes.h" 32*0b57cec5SDimitry Andric #include "llvm/CodeGen/TargetInstrInfo.h" 33*0b57cec5SDimitry Andric #include "llvm/CodeGen/TargetOpcodes.h" 34*0b57cec5SDimitry Andric #include "llvm/CodeGen/TargetRegisterInfo.h" 35*0b57cec5SDimitry Andric #include "llvm/CodeGen/TargetSubtargetInfo.h" 36*0b57cec5SDimitry Andric #include "llvm/MC/MCInstrDesc.h" 37*0b57cec5SDimitry Andric #include "llvm/MC/MCRegisterInfo.h" 38*0b57cec5SDimitry Andric #include "llvm/Pass.h" 39*0b57cec5SDimitry Andric #include "llvm/Support/Allocator.h" 40*0b57cec5SDimitry Andric #include "llvm/Support/Debug.h" 41*0b57cec5SDimitry Andric #include "llvm/Support/RecyclingAllocator.h" 42*0b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h" 43*0b57cec5SDimitry Andric #include <cassert> 44*0b57cec5SDimitry Andric #include <iterator> 45*0b57cec5SDimitry Andric #include <utility> 46*0b57cec5SDimitry Andric #include <vector> 47*0b57cec5SDimitry Andric 48*0b57cec5SDimitry Andric using namespace llvm; 49*0b57cec5SDimitry Andric 50*0b57cec5SDimitry Andric #define DEBUG_TYPE "machine-cse" 51*0b57cec5SDimitry Andric 52*0b57cec5SDimitry Andric STATISTIC(NumCoalesces, "Number of copies coalesced"); 53*0b57cec5SDimitry Andric STATISTIC(NumCSEs, "Number of common subexpression eliminated"); 54*0b57cec5SDimitry Andric STATISTIC(NumPREs, "Number of partial redundant expression" 55*0b57cec5SDimitry Andric " transformed to fully redundant"); 56*0b57cec5SDimitry Andric STATISTIC(NumPhysCSEs, 57*0b57cec5SDimitry Andric "Number of physreg referencing common subexpr eliminated"); 58*0b57cec5SDimitry Andric STATISTIC(NumCrossBBCSEs, 59*0b57cec5SDimitry Andric "Number of cross-MBB physreg referencing CS eliminated"); 60*0b57cec5SDimitry Andric STATISTIC(NumCommutes, "Number of copies coalesced after commuting"); 61*0b57cec5SDimitry Andric 62*0b57cec5SDimitry Andric namespace { 63*0b57cec5SDimitry Andric 64*0b57cec5SDimitry Andric class MachineCSE : public MachineFunctionPass { 65*0b57cec5SDimitry Andric const TargetInstrInfo *TII; 66*0b57cec5SDimitry Andric const TargetRegisterInfo *TRI; 67*0b57cec5SDimitry Andric AliasAnalysis *AA; 68*0b57cec5SDimitry Andric MachineDominatorTree *DT; 69*0b57cec5SDimitry Andric MachineRegisterInfo *MRI; 70*0b57cec5SDimitry Andric MachineBlockFrequencyInfo *MBFI; 71*0b57cec5SDimitry Andric 72*0b57cec5SDimitry Andric public: 73*0b57cec5SDimitry Andric static char ID; // Pass identification 74*0b57cec5SDimitry Andric 75*0b57cec5SDimitry Andric MachineCSE() : MachineFunctionPass(ID) { 76*0b57cec5SDimitry Andric initializeMachineCSEPass(*PassRegistry::getPassRegistry()); 77*0b57cec5SDimitry Andric } 78*0b57cec5SDimitry Andric 79*0b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 80*0b57cec5SDimitry Andric 81*0b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override { 82*0b57cec5SDimitry Andric AU.setPreservesCFG(); 83*0b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 84*0b57cec5SDimitry Andric AU.addRequired<AAResultsWrapperPass>(); 85*0b57cec5SDimitry Andric AU.addPreservedID(MachineLoopInfoID); 86*0b57cec5SDimitry Andric AU.addRequired<MachineDominatorTree>(); 87*0b57cec5SDimitry Andric AU.addPreserved<MachineDominatorTree>(); 88*0b57cec5SDimitry Andric AU.addRequired<MachineBlockFrequencyInfo>(); 89*0b57cec5SDimitry Andric AU.addPreserved<MachineBlockFrequencyInfo>(); 90*0b57cec5SDimitry Andric } 91*0b57cec5SDimitry Andric 92*0b57cec5SDimitry Andric void releaseMemory() override { 93*0b57cec5SDimitry Andric ScopeMap.clear(); 94*0b57cec5SDimitry Andric PREMap.clear(); 95*0b57cec5SDimitry Andric Exps.clear(); 96*0b57cec5SDimitry Andric } 97*0b57cec5SDimitry Andric 98*0b57cec5SDimitry Andric private: 99*0b57cec5SDimitry Andric using AllocatorTy = RecyclingAllocator<BumpPtrAllocator, 100*0b57cec5SDimitry Andric ScopedHashTableVal<MachineInstr *, unsigned>>; 101*0b57cec5SDimitry Andric using ScopedHTType = 102*0b57cec5SDimitry Andric ScopedHashTable<MachineInstr *, unsigned, MachineInstrExpressionTrait, 103*0b57cec5SDimitry Andric AllocatorTy>; 104*0b57cec5SDimitry Andric using ScopeType = ScopedHTType::ScopeTy; 105*0b57cec5SDimitry Andric using PhysDefVector = SmallVector<std::pair<unsigned, unsigned>, 2>; 106*0b57cec5SDimitry Andric 107*0b57cec5SDimitry Andric unsigned LookAheadLimit = 0; 108*0b57cec5SDimitry Andric DenseMap<MachineBasicBlock *, ScopeType *> ScopeMap; 109*0b57cec5SDimitry Andric DenseMap<MachineInstr *, MachineBasicBlock *, MachineInstrExpressionTrait> 110*0b57cec5SDimitry Andric PREMap; 111*0b57cec5SDimitry Andric ScopedHTType VNT; 112*0b57cec5SDimitry Andric SmallVector<MachineInstr *, 64> Exps; 113*0b57cec5SDimitry Andric unsigned CurrVN = 0; 114*0b57cec5SDimitry Andric 115*0b57cec5SDimitry Andric bool PerformTrivialCopyPropagation(MachineInstr *MI, 116*0b57cec5SDimitry Andric MachineBasicBlock *MBB); 117*0b57cec5SDimitry Andric bool isPhysDefTriviallyDead(unsigned Reg, 118*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator I, 119*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator E) const; 120*0b57cec5SDimitry Andric bool hasLivePhysRegDefUses(const MachineInstr *MI, 121*0b57cec5SDimitry Andric const MachineBasicBlock *MBB, 122*0b57cec5SDimitry Andric SmallSet<unsigned, 8> &PhysRefs, 123*0b57cec5SDimitry Andric PhysDefVector &PhysDefs, bool &PhysUseDef) const; 124*0b57cec5SDimitry Andric bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 125*0b57cec5SDimitry Andric SmallSet<unsigned, 8> &PhysRefs, 126*0b57cec5SDimitry Andric PhysDefVector &PhysDefs, bool &NonLocal) const; 127*0b57cec5SDimitry Andric bool isCSECandidate(MachineInstr *MI); 128*0b57cec5SDimitry Andric bool isProfitableToCSE(unsigned CSReg, unsigned Reg, 129*0b57cec5SDimitry Andric MachineBasicBlock *CSBB, MachineInstr *MI); 130*0b57cec5SDimitry Andric void EnterScope(MachineBasicBlock *MBB); 131*0b57cec5SDimitry Andric void ExitScope(MachineBasicBlock *MBB); 132*0b57cec5SDimitry Andric bool ProcessBlockCSE(MachineBasicBlock *MBB); 133*0b57cec5SDimitry Andric void ExitScopeIfDone(MachineDomTreeNode *Node, 134*0b57cec5SDimitry Andric DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); 135*0b57cec5SDimitry Andric bool PerformCSE(MachineDomTreeNode *Node); 136*0b57cec5SDimitry Andric 137*0b57cec5SDimitry Andric bool isPRECandidate(MachineInstr *MI); 138*0b57cec5SDimitry Andric bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB); 139*0b57cec5SDimitry Andric bool PerformSimplePRE(MachineDominatorTree *DT); 140*0b57cec5SDimitry Andric /// Heuristics to see if it's beneficial to move common computations of MBB 141*0b57cec5SDimitry Andric /// and MBB1 to CandidateBB. 142*0b57cec5SDimitry Andric bool isBeneficalToHoistInto(MachineBasicBlock *CandidateBB, 143*0b57cec5SDimitry Andric MachineBasicBlock *MBB, 144*0b57cec5SDimitry Andric MachineBasicBlock *MBB1); 145*0b57cec5SDimitry Andric }; 146*0b57cec5SDimitry Andric 147*0b57cec5SDimitry Andric } // end anonymous namespace 148*0b57cec5SDimitry Andric 149*0b57cec5SDimitry Andric char MachineCSE::ID = 0; 150*0b57cec5SDimitry Andric 151*0b57cec5SDimitry Andric char &llvm::MachineCSEID = MachineCSE::ID; 152*0b57cec5SDimitry Andric 153*0b57cec5SDimitry Andric INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE, 154*0b57cec5SDimitry Andric "Machine Common Subexpression Elimination", false, false) 155*0b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 156*0b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 157*0b57cec5SDimitry Andric INITIALIZE_PASS_END(MachineCSE, DEBUG_TYPE, 158*0b57cec5SDimitry Andric "Machine Common Subexpression Elimination", false, false) 159*0b57cec5SDimitry Andric 160*0b57cec5SDimitry Andric /// The source register of a COPY machine instruction can be propagated to all 161*0b57cec5SDimitry Andric /// its users, and this propagation could increase the probability of finding 162*0b57cec5SDimitry Andric /// common subexpressions. If the COPY has only one user, the COPY itself can 163*0b57cec5SDimitry Andric /// be removed. 164*0b57cec5SDimitry Andric bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI, 165*0b57cec5SDimitry Andric MachineBasicBlock *MBB) { 166*0b57cec5SDimitry Andric bool Changed = false; 167*0b57cec5SDimitry Andric for (MachineOperand &MO : MI->operands()) { 168*0b57cec5SDimitry Andric if (!MO.isReg() || !MO.isUse()) 169*0b57cec5SDimitry Andric continue; 170*0b57cec5SDimitry Andric unsigned Reg = MO.getReg(); 171*0b57cec5SDimitry Andric if (!TargetRegisterInfo::isVirtualRegister(Reg)) 172*0b57cec5SDimitry Andric continue; 173*0b57cec5SDimitry Andric bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg); 174*0b57cec5SDimitry Andric MachineInstr *DefMI = MRI->getVRegDef(Reg); 175*0b57cec5SDimitry Andric if (!DefMI->isCopy()) 176*0b57cec5SDimitry Andric continue; 177*0b57cec5SDimitry Andric unsigned SrcReg = DefMI->getOperand(1).getReg(); 178*0b57cec5SDimitry Andric if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 179*0b57cec5SDimitry Andric continue; 180*0b57cec5SDimitry Andric if (DefMI->getOperand(0).getSubReg()) 181*0b57cec5SDimitry Andric continue; 182*0b57cec5SDimitry Andric // FIXME: We should trivially coalesce subregister copies to expose CSE 183*0b57cec5SDimitry Andric // opportunities on instructions with truncated operands (see 184*0b57cec5SDimitry Andric // cse-add-with-overflow.ll). This can be done here as follows: 185*0b57cec5SDimitry Andric // if (SrcSubReg) 186*0b57cec5SDimitry Andric // RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC, 187*0b57cec5SDimitry Andric // SrcSubReg); 188*0b57cec5SDimitry Andric // MO.substVirtReg(SrcReg, SrcSubReg, *TRI); 189*0b57cec5SDimitry Andric // 190*0b57cec5SDimitry Andric // The 2-addr pass has been updated to handle coalesced subregs. However, 191*0b57cec5SDimitry Andric // some machine-specific code still can't handle it. 192*0b57cec5SDimitry Andric // To handle it properly we also need a way find a constrained subregister 193*0b57cec5SDimitry Andric // class given a super-reg class and subreg index. 194*0b57cec5SDimitry Andric if (DefMI->getOperand(1).getSubReg()) 195*0b57cec5SDimitry Andric continue; 196*0b57cec5SDimitry Andric if (!MRI->constrainRegAttrs(SrcReg, Reg)) 197*0b57cec5SDimitry Andric continue; 198*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI); 199*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "*** to: " << *MI); 200*0b57cec5SDimitry Andric 201*0b57cec5SDimitry Andric // Update matching debug values. 202*0b57cec5SDimitry Andric DefMI->changeDebugValuesDefReg(SrcReg); 203*0b57cec5SDimitry Andric 204*0b57cec5SDimitry Andric // Propagate SrcReg of copies to MI. 205*0b57cec5SDimitry Andric MO.setReg(SrcReg); 206*0b57cec5SDimitry Andric MRI->clearKillFlags(SrcReg); 207*0b57cec5SDimitry Andric // Coalesce single use copies. 208*0b57cec5SDimitry Andric if (OnlyOneUse) { 209*0b57cec5SDimitry Andric DefMI->eraseFromParent(); 210*0b57cec5SDimitry Andric ++NumCoalesces; 211*0b57cec5SDimitry Andric } 212*0b57cec5SDimitry Andric Changed = true; 213*0b57cec5SDimitry Andric } 214*0b57cec5SDimitry Andric 215*0b57cec5SDimitry Andric return Changed; 216*0b57cec5SDimitry Andric } 217*0b57cec5SDimitry Andric 218*0b57cec5SDimitry Andric bool 219*0b57cec5SDimitry Andric MachineCSE::isPhysDefTriviallyDead(unsigned Reg, 220*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator I, 221*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator E) const { 222*0b57cec5SDimitry Andric unsigned LookAheadLeft = LookAheadLimit; 223*0b57cec5SDimitry Andric while (LookAheadLeft) { 224*0b57cec5SDimitry Andric // Skip over dbg_value's. 225*0b57cec5SDimitry Andric I = skipDebugInstructionsForward(I, E); 226*0b57cec5SDimitry Andric 227*0b57cec5SDimitry Andric if (I == E) 228*0b57cec5SDimitry Andric // Reached end of block, we don't know if register is dead or not. 229*0b57cec5SDimitry Andric return false; 230*0b57cec5SDimitry Andric 231*0b57cec5SDimitry Andric bool SeenDef = false; 232*0b57cec5SDimitry Andric for (const MachineOperand &MO : I->operands()) { 233*0b57cec5SDimitry Andric if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) 234*0b57cec5SDimitry Andric SeenDef = true; 235*0b57cec5SDimitry Andric if (!MO.isReg() || !MO.getReg()) 236*0b57cec5SDimitry Andric continue; 237*0b57cec5SDimitry Andric if (!TRI->regsOverlap(MO.getReg(), Reg)) 238*0b57cec5SDimitry Andric continue; 239*0b57cec5SDimitry Andric if (MO.isUse()) 240*0b57cec5SDimitry Andric // Found a use! 241*0b57cec5SDimitry Andric return false; 242*0b57cec5SDimitry Andric SeenDef = true; 243*0b57cec5SDimitry Andric } 244*0b57cec5SDimitry Andric if (SeenDef) 245*0b57cec5SDimitry Andric // See a def of Reg (or an alias) before encountering any use, it's 246*0b57cec5SDimitry Andric // trivially dead. 247*0b57cec5SDimitry Andric return true; 248*0b57cec5SDimitry Andric 249*0b57cec5SDimitry Andric --LookAheadLeft; 250*0b57cec5SDimitry Andric ++I; 251*0b57cec5SDimitry Andric } 252*0b57cec5SDimitry Andric return false; 253*0b57cec5SDimitry Andric } 254*0b57cec5SDimitry Andric 255*0b57cec5SDimitry Andric static bool isCallerPreservedOrConstPhysReg(unsigned Reg, 256*0b57cec5SDimitry Andric const MachineFunction &MF, 257*0b57cec5SDimitry Andric const TargetRegisterInfo &TRI) { 258*0b57cec5SDimitry Andric // MachineRegisterInfo::isConstantPhysReg directly called by 259*0b57cec5SDimitry Andric // MachineRegisterInfo::isCallerPreservedOrConstPhysReg expects the 260*0b57cec5SDimitry Andric // reserved registers to be frozen. That doesn't cause a problem post-ISel as 261*0b57cec5SDimitry Andric // most (if not all) targets freeze reserved registers right after ISel. 262*0b57cec5SDimitry Andric // 263*0b57cec5SDimitry Andric // It does cause issues mid-GlobalISel, however, hence the additional 264*0b57cec5SDimitry Andric // reservedRegsFrozen check. 265*0b57cec5SDimitry Andric const MachineRegisterInfo &MRI = MF.getRegInfo(); 266*0b57cec5SDimitry Andric return TRI.isCallerPreservedPhysReg(Reg, MF) || 267*0b57cec5SDimitry Andric (MRI.reservedRegsFrozen() && MRI.isConstantPhysReg(Reg)); 268*0b57cec5SDimitry Andric } 269*0b57cec5SDimitry Andric 270*0b57cec5SDimitry Andric /// hasLivePhysRegDefUses - Return true if the specified instruction read/write 271*0b57cec5SDimitry Andric /// physical registers (except for dead defs of physical registers). It also 272*0b57cec5SDimitry Andric /// returns the physical register def by reference if it's the only one and the 273*0b57cec5SDimitry Andric /// instruction does not uses a physical register. 274*0b57cec5SDimitry Andric bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, 275*0b57cec5SDimitry Andric const MachineBasicBlock *MBB, 276*0b57cec5SDimitry Andric SmallSet<unsigned, 8> &PhysRefs, 277*0b57cec5SDimitry Andric PhysDefVector &PhysDefs, 278*0b57cec5SDimitry Andric bool &PhysUseDef) const { 279*0b57cec5SDimitry Andric // First, add all uses to PhysRefs. 280*0b57cec5SDimitry Andric for (const MachineOperand &MO : MI->operands()) { 281*0b57cec5SDimitry Andric if (!MO.isReg() || MO.isDef()) 282*0b57cec5SDimitry Andric continue; 283*0b57cec5SDimitry Andric unsigned Reg = MO.getReg(); 284*0b57cec5SDimitry Andric if (!Reg) 285*0b57cec5SDimitry Andric continue; 286*0b57cec5SDimitry Andric if (TargetRegisterInfo::isVirtualRegister(Reg)) 287*0b57cec5SDimitry Andric continue; 288*0b57cec5SDimitry Andric // Reading either caller preserved or constant physregs is ok. 289*0b57cec5SDimitry Andric if (!isCallerPreservedOrConstPhysReg(Reg, *MI->getMF(), *TRI)) 290*0b57cec5SDimitry Andric for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 291*0b57cec5SDimitry Andric PhysRefs.insert(*AI); 292*0b57cec5SDimitry Andric } 293*0b57cec5SDimitry Andric 294*0b57cec5SDimitry Andric // Next, collect all defs into PhysDefs. If any is already in PhysRefs 295*0b57cec5SDimitry Andric // (which currently contains only uses), set the PhysUseDef flag. 296*0b57cec5SDimitry Andric PhysUseDef = false; 297*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator I = MI; I = std::next(I); 298*0b57cec5SDimitry Andric for (const auto &MOP : llvm::enumerate(MI->operands())) { 299*0b57cec5SDimitry Andric const MachineOperand &MO = MOP.value(); 300*0b57cec5SDimitry Andric if (!MO.isReg() || !MO.isDef()) 301*0b57cec5SDimitry Andric continue; 302*0b57cec5SDimitry Andric unsigned Reg = MO.getReg(); 303*0b57cec5SDimitry Andric if (!Reg) 304*0b57cec5SDimitry Andric continue; 305*0b57cec5SDimitry Andric if (TargetRegisterInfo::isVirtualRegister(Reg)) 306*0b57cec5SDimitry Andric continue; 307*0b57cec5SDimitry Andric // Check against PhysRefs even if the def is "dead". 308*0b57cec5SDimitry Andric if (PhysRefs.count(Reg)) 309*0b57cec5SDimitry Andric PhysUseDef = true; 310*0b57cec5SDimitry Andric // If the def is dead, it's ok. But the def may not marked "dead". That's 311*0b57cec5SDimitry Andric // common since this pass is run before livevariables. We can scan 312*0b57cec5SDimitry Andric // forward a few instructions and check if it is obviously dead. 313*0b57cec5SDimitry Andric if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end())) 314*0b57cec5SDimitry Andric PhysDefs.push_back(std::make_pair(MOP.index(), Reg)); 315*0b57cec5SDimitry Andric } 316*0b57cec5SDimitry Andric 317*0b57cec5SDimitry Andric // Finally, add all defs to PhysRefs as well. 318*0b57cec5SDimitry Andric for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) 319*0b57cec5SDimitry Andric for (MCRegAliasIterator AI(PhysDefs[i].second, TRI, true); AI.isValid(); 320*0b57cec5SDimitry Andric ++AI) 321*0b57cec5SDimitry Andric PhysRefs.insert(*AI); 322*0b57cec5SDimitry Andric 323*0b57cec5SDimitry Andric return !PhysRefs.empty(); 324*0b57cec5SDimitry Andric } 325*0b57cec5SDimitry Andric 326*0b57cec5SDimitry Andric bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, 327*0b57cec5SDimitry Andric SmallSet<unsigned, 8> &PhysRefs, 328*0b57cec5SDimitry Andric PhysDefVector &PhysDefs, 329*0b57cec5SDimitry Andric bool &NonLocal) const { 330*0b57cec5SDimitry Andric // For now conservatively returns false if the common subexpression is 331*0b57cec5SDimitry Andric // not in the same basic block as the given instruction. The only exception 332*0b57cec5SDimitry Andric // is if the common subexpression is in the sole predecessor block. 333*0b57cec5SDimitry Andric const MachineBasicBlock *MBB = MI->getParent(); 334*0b57cec5SDimitry Andric const MachineBasicBlock *CSMBB = CSMI->getParent(); 335*0b57cec5SDimitry Andric 336*0b57cec5SDimitry Andric bool CrossMBB = false; 337*0b57cec5SDimitry Andric if (CSMBB != MBB) { 338*0b57cec5SDimitry Andric if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB) 339*0b57cec5SDimitry Andric return false; 340*0b57cec5SDimitry Andric 341*0b57cec5SDimitry Andric for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 342*0b57cec5SDimitry Andric if (MRI->isAllocatable(PhysDefs[i].second) || 343*0b57cec5SDimitry Andric MRI->isReserved(PhysDefs[i].second)) 344*0b57cec5SDimitry Andric // Avoid extending live range of physical registers if they are 345*0b57cec5SDimitry Andric //allocatable or reserved. 346*0b57cec5SDimitry Andric return false; 347*0b57cec5SDimitry Andric } 348*0b57cec5SDimitry Andric CrossMBB = true; 349*0b57cec5SDimitry Andric } 350*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator I = CSMI; I = std::next(I); 351*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator E = MI; 352*0b57cec5SDimitry Andric MachineBasicBlock::const_iterator EE = CSMBB->end(); 353*0b57cec5SDimitry Andric unsigned LookAheadLeft = LookAheadLimit; 354*0b57cec5SDimitry Andric while (LookAheadLeft) { 355*0b57cec5SDimitry Andric // Skip over dbg_value's. 356*0b57cec5SDimitry Andric while (I != E && I != EE && I->isDebugInstr()) 357*0b57cec5SDimitry Andric ++I; 358*0b57cec5SDimitry Andric 359*0b57cec5SDimitry Andric if (I == EE) { 360*0b57cec5SDimitry Andric assert(CrossMBB && "Reaching end-of-MBB without finding MI?"); 361*0b57cec5SDimitry Andric (void)CrossMBB; 362*0b57cec5SDimitry Andric CrossMBB = false; 363*0b57cec5SDimitry Andric NonLocal = true; 364*0b57cec5SDimitry Andric I = MBB->begin(); 365*0b57cec5SDimitry Andric EE = MBB->end(); 366*0b57cec5SDimitry Andric continue; 367*0b57cec5SDimitry Andric } 368*0b57cec5SDimitry Andric 369*0b57cec5SDimitry Andric if (I == E) 370*0b57cec5SDimitry Andric return true; 371*0b57cec5SDimitry Andric 372*0b57cec5SDimitry Andric for (const MachineOperand &MO : I->operands()) { 373*0b57cec5SDimitry Andric // RegMasks go on instructions like calls that clobber lots of physregs. 374*0b57cec5SDimitry Andric // Don't attempt to CSE across such an instruction. 375*0b57cec5SDimitry Andric if (MO.isRegMask()) 376*0b57cec5SDimitry Andric return false; 377*0b57cec5SDimitry Andric if (!MO.isReg() || !MO.isDef()) 378*0b57cec5SDimitry Andric continue; 379*0b57cec5SDimitry Andric unsigned MOReg = MO.getReg(); 380*0b57cec5SDimitry Andric if (TargetRegisterInfo::isVirtualRegister(MOReg)) 381*0b57cec5SDimitry Andric continue; 382*0b57cec5SDimitry Andric if (PhysRefs.count(MOReg)) 383*0b57cec5SDimitry Andric return false; 384*0b57cec5SDimitry Andric } 385*0b57cec5SDimitry Andric 386*0b57cec5SDimitry Andric --LookAheadLeft; 387*0b57cec5SDimitry Andric ++I; 388*0b57cec5SDimitry Andric } 389*0b57cec5SDimitry Andric 390*0b57cec5SDimitry Andric return false; 391*0b57cec5SDimitry Andric } 392*0b57cec5SDimitry Andric 393*0b57cec5SDimitry Andric bool MachineCSE::isCSECandidate(MachineInstr *MI) { 394*0b57cec5SDimitry Andric if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() || 395*0b57cec5SDimitry Andric MI->isInlineAsm() || MI->isDebugInstr()) 396*0b57cec5SDimitry Andric return false; 397*0b57cec5SDimitry Andric 398*0b57cec5SDimitry Andric // Ignore copies. 399*0b57cec5SDimitry Andric if (MI->isCopyLike()) 400*0b57cec5SDimitry Andric return false; 401*0b57cec5SDimitry Andric 402*0b57cec5SDimitry Andric // Ignore stuff that we obviously can't move. 403*0b57cec5SDimitry Andric if (MI->mayStore() || MI->isCall() || MI->isTerminator() || 404*0b57cec5SDimitry Andric MI->mayRaiseFPException() || MI->hasUnmodeledSideEffects()) 405*0b57cec5SDimitry Andric return false; 406*0b57cec5SDimitry Andric 407*0b57cec5SDimitry Andric if (MI->mayLoad()) { 408*0b57cec5SDimitry Andric // Okay, this instruction does a load. As a refinement, we allow the target 409*0b57cec5SDimitry Andric // to decide whether the loaded value is actually a constant. If so, we can 410*0b57cec5SDimitry Andric // actually use it as a load. 411*0b57cec5SDimitry Andric if (!MI->isDereferenceableInvariantLoad(AA)) 412*0b57cec5SDimitry Andric // FIXME: we should be able to hoist loads with no other side effects if 413*0b57cec5SDimitry Andric // there are no other instructions which can change memory in this loop. 414*0b57cec5SDimitry Andric // This is a trivial form of alias analysis. 415*0b57cec5SDimitry Andric return false; 416*0b57cec5SDimitry Andric } 417*0b57cec5SDimitry Andric 418*0b57cec5SDimitry Andric // Ignore stack guard loads, otherwise the register that holds CSEed value may 419*0b57cec5SDimitry Andric // be spilled and get loaded back with corrupted data. 420*0b57cec5SDimitry Andric if (MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD) 421*0b57cec5SDimitry Andric return false; 422*0b57cec5SDimitry Andric 423*0b57cec5SDimitry Andric return true; 424*0b57cec5SDimitry Andric } 425*0b57cec5SDimitry Andric 426*0b57cec5SDimitry Andric /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a 427*0b57cec5SDimitry Andric /// common expression that defines Reg. CSBB is basic block where CSReg is 428*0b57cec5SDimitry Andric /// defined. 429*0b57cec5SDimitry Andric bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, 430*0b57cec5SDimitry Andric MachineBasicBlock *CSBB, MachineInstr *MI) { 431*0b57cec5SDimitry Andric // FIXME: Heuristics that works around the lack the live range splitting. 432*0b57cec5SDimitry Andric 433*0b57cec5SDimitry Andric // If CSReg is used at all uses of Reg, CSE should not increase register 434*0b57cec5SDimitry Andric // pressure of CSReg. 435*0b57cec5SDimitry Andric bool MayIncreasePressure = true; 436*0b57cec5SDimitry Andric if (TargetRegisterInfo::isVirtualRegister(CSReg) && 437*0b57cec5SDimitry Andric TargetRegisterInfo::isVirtualRegister(Reg)) { 438*0b57cec5SDimitry Andric MayIncreasePressure = false; 439*0b57cec5SDimitry Andric SmallPtrSet<MachineInstr*, 8> CSUses; 440*0b57cec5SDimitry Andric for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { 441*0b57cec5SDimitry Andric CSUses.insert(&MI); 442*0b57cec5SDimitry Andric } 443*0b57cec5SDimitry Andric for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 444*0b57cec5SDimitry Andric if (!CSUses.count(&MI)) { 445*0b57cec5SDimitry Andric MayIncreasePressure = true; 446*0b57cec5SDimitry Andric break; 447*0b57cec5SDimitry Andric } 448*0b57cec5SDimitry Andric } 449*0b57cec5SDimitry Andric } 450*0b57cec5SDimitry Andric if (!MayIncreasePressure) return true; 451*0b57cec5SDimitry Andric 452*0b57cec5SDimitry Andric // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in 453*0b57cec5SDimitry Andric // an immediate predecessor. We don't want to increase register pressure and 454*0b57cec5SDimitry Andric // end up causing other computation to be spilled. 455*0b57cec5SDimitry Andric if (TII->isAsCheapAsAMove(*MI)) { 456*0b57cec5SDimitry Andric MachineBasicBlock *BB = MI->getParent(); 457*0b57cec5SDimitry Andric if (CSBB != BB && !CSBB->isSuccessor(BB)) 458*0b57cec5SDimitry Andric return false; 459*0b57cec5SDimitry Andric } 460*0b57cec5SDimitry Andric 461*0b57cec5SDimitry Andric // Heuristics #2: If the expression doesn't not use a vr and the only use 462*0b57cec5SDimitry Andric // of the redundant computation are copies, do not cse. 463*0b57cec5SDimitry Andric bool HasVRegUse = false; 464*0b57cec5SDimitry Andric for (const MachineOperand &MO : MI->operands()) { 465*0b57cec5SDimitry Andric if (MO.isReg() && MO.isUse() && 466*0b57cec5SDimitry Andric TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 467*0b57cec5SDimitry Andric HasVRegUse = true; 468*0b57cec5SDimitry Andric break; 469*0b57cec5SDimitry Andric } 470*0b57cec5SDimitry Andric } 471*0b57cec5SDimitry Andric if (!HasVRegUse) { 472*0b57cec5SDimitry Andric bool HasNonCopyUse = false; 473*0b57cec5SDimitry Andric for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { 474*0b57cec5SDimitry Andric // Ignore copies. 475*0b57cec5SDimitry Andric if (!MI.isCopyLike()) { 476*0b57cec5SDimitry Andric HasNonCopyUse = true; 477*0b57cec5SDimitry Andric break; 478*0b57cec5SDimitry Andric } 479*0b57cec5SDimitry Andric } 480*0b57cec5SDimitry Andric if (!HasNonCopyUse) 481*0b57cec5SDimitry Andric return false; 482*0b57cec5SDimitry Andric } 483*0b57cec5SDimitry Andric 484*0b57cec5SDimitry Andric // Heuristics #3: If the common subexpression is used by PHIs, do not reuse 485*0b57cec5SDimitry Andric // it unless the defined value is already used in the BB of the new use. 486*0b57cec5SDimitry Andric bool HasPHI = false; 487*0b57cec5SDimitry Andric for (MachineInstr &UseMI : MRI->use_nodbg_instructions(CSReg)) { 488*0b57cec5SDimitry Andric HasPHI |= UseMI.isPHI(); 489*0b57cec5SDimitry Andric if (UseMI.getParent() == MI->getParent()) 490*0b57cec5SDimitry Andric return true; 491*0b57cec5SDimitry Andric } 492*0b57cec5SDimitry Andric 493*0b57cec5SDimitry Andric return !HasPHI; 494*0b57cec5SDimitry Andric } 495*0b57cec5SDimitry Andric 496*0b57cec5SDimitry Andric void MachineCSE::EnterScope(MachineBasicBlock *MBB) { 497*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); 498*0b57cec5SDimitry Andric ScopeType *Scope = new ScopeType(VNT); 499*0b57cec5SDimitry Andric ScopeMap[MBB] = Scope; 500*0b57cec5SDimitry Andric } 501*0b57cec5SDimitry Andric 502*0b57cec5SDimitry Andric void MachineCSE::ExitScope(MachineBasicBlock *MBB) { 503*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); 504*0b57cec5SDimitry Andric DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); 505*0b57cec5SDimitry Andric assert(SI != ScopeMap.end()); 506*0b57cec5SDimitry Andric delete SI->second; 507*0b57cec5SDimitry Andric ScopeMap.erase(SI); 508*0b57cec5SDimitry Andric } 509*0b57cec5SDimitry Andric 510*0b57cec5SDimitry Andric bool MachineCSE::ProcessBlockCSE(MachineBasicBlock *MBB) { 511*0b57cec5SDimitry Andric bool Changed = false; 512*0b57cec5SDimitry Andric 513*0b57cec5SDimitry Andric SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; 514*0b57cec5SDimitry Andric SmallVector<unsigned, 2> ImplicitDefsToUpdate; 515*0b57cec5SDimitry Andric SmallVector<unsigned, 2> ImplicitDefs; 516*0b57cec5SDimitry Andric for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 517*0b57cec5SDimitry Andric MachineInstr *MI = &*I; 518*0b57cec5SDimitry Andric ++I; 519*0b57cec5SDimitry Andric 520*0b57cec5SDimitry Andric if (!isCSECandidate(MI)) 521*0b57cec5SDimitry Andric continue; 522*0b57cec5SDimitry Andric 523*0b57cec5SDimitry Andric bool FoundCSE = VNT.count(MI); 524*0b57cec5SDimitry Andric if (!FoundCSE) { 525*0b57cec5SDimitry Andric // Using trivial copy propagation to find more CSE opportunities. 526*0b57cec5SDimitry Andric if (PerformTrivialCopyPropagation(MI, MBB)) { 527*0b57cec5SDimitry Andric Changed = true; 528*0b57cec5SDimitry Andric 529*0b57cec5SDimitry Andric // After coalescing MI itself may become a copy. 530*0b57cec5SDimitry Andric if (MI->isCopyLike()) 531*0b57cec5SDimitry Andric continue; 532*0b57cec5SDimitry Andric 533*0b57cec5SDimitry Andric // Try again to see if CSE is possible. 534*0b57cec5SDimitry Andric FoundCSE = VNT.count(MI); 535*0b57cec5SDimitry Andric } 536*0b57cec5SDimitry Andric } 537*0b57cec5SDimitry Andric 538*0b57cec5SDimitry Andric // Commute commutable instructions. 539*0b57cec5SDimitry Andric bool Commuted = false; 540*0b57cec5SDimitry Andric if (!FoundCSE && MI->isCommutable()) { 541*0b57cec5SDimitry Andric if (MachineInstr *NewMI = TII->commuteInstruction(*MI)) { 542*0b57cec5SDimitry Andric Commuted = true; 543*0b57cec5SDimitry Andric FoundCSE = VNT.count(NewMI); 544*0b57cec5SDimitry Andric if (NewMI != MI) { 545*0b57cec5SDimitry Andric // New instruction. It doesn't need to be kept. 546*0b57cec5SDimitry Andric NewMI->eraseFromParent(); 547*0b57cec5SDimitry Andric Changed = true; 548*0b57cec5SDimitry Andric } else if (!FoundCSE) 549*0b57cec5SDimitry Andric // MI was changed but it didn't help, commute it back! 550*0b57cec5SDimitry Andric (void)TII->commuteInstruction(*MI); 551*0b57cec5SDimitry Andric } 552*0b57cec5SDimitry Andric } 553*0b57cec5SDimitry Andric 554*0b57cec5SDimitry Andric // If the instruction defines physical registers and the values *may* be 555*0b57cec5SDimitry Andric // used, then it's not safe to replace it with a common subexpression. 556*0b57cec5SDimitry Andric // It's also not safe if the instruction uses physical registers. 557*0b57cec5SDimitry Andric bool CrossMBBPhysDef = false; 558*0b57cec5SDimitry Andric SmallSet<unsigned, 8> PhysRefs; 559*0b57cec5SDimitry Andric PhysDefVector PhysDefs; 560*0b57cec5SDimitry Andric bool PhysUseDef = false; 561*0b57cec5SDimitry Andric if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, 562*0b57cec5SDimitry Andric PhysDefs, PhysUseDef)) { 563*0b57cec5SDimitry Andric FoundCSE = false; 564*0b57cec5SDimitry Andric 565*0b57cec5SDimitry Andric // ... Unless the CS is local or is in the sole predecessor block 566*0b57cec5SDimitry Andric // and it also defines the physical register which is not clobbered 567*0b57cec5SDimitry Andric // in between and the physical register uses were not clobbered. 568*0b57cec5SDimitry Andric // This can never be the case if the instruction both uses and 569*0b57cec5SDimitry Andric // defines the same physical register, which was detected above. 570*0b57cec5SDimitry Andric if (!PhysUseDef) { 571*0b57cec5SDimitry Andric unsigned CSVN = VNT.lookup(MI); 572*0b57cec5SDimitry Andric MachineInstr *CSMI = Exps[CSVN]; 573*0b57cec5SDimitry Andric if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef)) 574*0b57cec5SDimitry Andric FoundCSE = true; 575*0b57cec5SDimitry Andric } 576*0b57cec5SDimitry Andric } 577*0b57cec5SDimitry Andric 578*0b57cec5SDimitry Andric if (!FoundCSE) { 579*0b57cec5SDimitry Andric VNT.insert(MI, CurrVN++); 580*0b57cec5SDimitry Andric Exps.push_back(MI); 581*0b57cec5SDimitry Andric continue; 582*0b57cec5SDimitry Andric } 583*0b57cec5SDimitry Andric 584*0b57cec5SDimitry Andric // Found a common subexpression, eliminate it. 585*0b57cec5SDimitry Andric unsigned CSVN = VNT.lookup(MI); 586*0b57cec5SDimitry Andric MachineInstr *CSMI = Exps[CSVN]; 587*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Examining: " << *MI); 588*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 589*0b57cec5SDimitry Andric 590*0b57cec5SDimitry Andric // Check if it's profitable to perform this CSE. 591*0b57cec5SDimitry Andric bool DoCSE = true; 592*0b57cec5SDimitry Andric unsigned NumDefs = MI->getNumDefs(); 593*0b57cec5SDimitry Andric 594*0b57cec5SDimitry Andric for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 595*0b57cec5SDimitry Andric MachineOperand &MO = MI->getOperand(i); 596*0b57cec5SDimitry Andric if (!MO.isReg() || !MO.isDef()) 597*0b57cec5SDimitry Andric continue; 598*0b57cec5SDimitry Andric unsigned OldReg = MO.getReg(); 599*0b57cec5SDimitry Andric unsigned NewReg = CSMI->getOperand(i).getReg(); 600*0b57cec5SDimitry Andric 601*0b57cec5SDimitry Andric // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 602*0b57cec5SDimitry Andric // we should make sure it is not dead at CSMI. 603*0b57cec5SDimitry Andric if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) 604*0b57cec5SDimitry Andric ImplicitDefsToUpdate.push_back(i); 605*0b57cec5SDimitry Andric 606*0b57cec5SDimitry Andric // Keep track of implicit defs of CSMI and MI, to clear possibly 607*0b57cec5SDimitry Andric // made-redundant kill flags. 608*0b57cec5SDimitry Andric if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg) 609*0b57cec5SDimitry Andric ImplicitDefs.push_back(OldReg); 610*0b57cec5SDimitry Andric 611*0b57cec5SDimitry Andric if (OldReg == NewReg) { 612*0b57cec5SDimitry Andric --NumDefs; 613*0b57cec5SDimitry Andric continue; 614*0b57cec5SDimitry Andric } 615*0b57cec5SDimitry Andric 616*0b57cec5SDimitry Andric assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 617*0b57cec5SDimitry Andric TargetRegisterInfo::isVirtualRegister(NewReg) && 618*0b57cec5SDimitry Andric "Do not CSE physical register defs!"); 619*0b57cec5SDimitry Andric 620*0b57cec5SDimitry Andric if (!isProfitableToCSE(NewReg, OldReg, CSMI->getParent(), MI)) { 621*0b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); 622*0b57cec5SDimitry Andric DoCSE = false; 623*0b57cec5SDimitry Andric break; 624*0b57cec5SDimitry Andric } 625*0b57cec5SDimitry Andric 626*0b57cec5SDimitry Andric // Don't perform CSE if the result of the new instruction cannot exist 627*0b57cec5SDimitry Andric // within the constraints (register class, bank, or low-level type) of 628*0b57cec5SDimitry Andric // the old instruction. 629*0b57cec5SDimitry Andric if (!MRI->constrainRegAttrs(NewReg, OldReg)) { 630*0b57cec5SDimitry Andric LLVM_DEBUG( 631*0b57cec5SDimitry Andric dbgs() << "*** Not the same register constraints, avoid CSE!\n"); 632*0b57cec5SDimitry Andric DoCSE = false; 633*0b57cec5SDimitry Andric break; 634*0b57cec5SDimitry Andric } 635*0b57cec5SDimitry Andric 636*0b57cec5SDimitry Andric CSEPairs.push_back(std::make_pair(OldReg, NewReg)); 637*0b57cec5SDimitry Andric --NumDefs; 638*0b57cec5SDimitry Andric } 639*0b57cec5SDimitry Andric 640*0b57cec5SDimitry Andric // Actually perform the elimination. 641*0b57cec5SDimitry Andric if (DoCSE) { 642*0b57cec5SDimitry Andric for (std::pair<unsigned, unsigned> &CSEPair : CSEPairs) { 643*0b57cec5SDimitry Andric unsigned OldReg = CSEPair.first; 644*0b57cec5SDimitry Andric unsigned NewReg = CSEPair.second; 645*0b57cec5SDimitry Andric // OldReg may have been unused but is used now, clear the Dead flag 646*0b57cec5SDimitry Andric MachineInstr *Def = MRI->getUniqueVRegDef(NewReg); 647*0b57cec5SDimitry Andric assert(Def != nullptr && "CSEd register has no unique definition?"); 648*0b57cec5SDimitry Andric Def->clearRegisterDeads(NewReg); 649*0b57cec5SDimitry Andric // Replace with NewReg and clear kill flags which may be wrong now. 650*0b57cec5SDimitry Andric MRI->replaceRegWith(OldReg, NewReg); 651*0b57cec5SDimitry Andric MRI->clearKillFlags(NewReg); 652*0b57cec5SDimitry Andric } 653*0b57cec5SDimitry Andric 654*0b57cec5SDimitry Andric // Go through implicit defs of CSMI and MI, if a def is not dead at MI, 655*0b57cec5SDimitry Andric // we should make sure it is not dead at CSMI. 656*0b57cec5SDimitry Andric for (unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate) 657*0b57cec5SDimitry Andric CSMI->getOperand(ImplicitDefToUpdate).setIsDead(false); 658*0b57cec5SDimitry Andric for (auto PhysDef : PhysDefs) 659*0b57cec5SDimitry Andric if (!MI->getOperand(PhysDef.first).isDead()) 660*0b57cec5SDimitry Andric CSMI->getOperand(PhysDef.first).setIsDead(false); 661*0b57cec5SDimitry Andric 662*0b57cec5SDimitry Andric // Go through implicit defs of CSMI and MI, and clear the kill flags on 663*0b57cec5SDimitry Andric // their uses in all the instructions between CSMI and MI. 664*0b57cec5SDimitry Andric // We might have made some of the kill flags redundant, consider: 665*0b57cec5SDimitry Andric // subs ... implicit-def %nzcv <- CSMI 666*0b57cec5SDimitry Andric // csinc ... implicit killed %nzcv <- this kill flag isn't valid anymore 667*0b57cec5SDimitry Andric // subs ... implicit-def %nzcv <- MI, to be eliminated 668*0b57cec5SDimitry Andric // csinc ... implicit killed %nzcv 669*0b57cec5SDimitry Andric // Since we eliminated MI, and reused a register imp-def'd by CSMI 670*0b57cec5SDimitry Andric // (here %nzcv), that register, if it was killed before MI, should have 671*0b57cec5SDimitry Andric // that kill flag removed, because it's lifetime was extended. 672*0b57cec5SDimitry Andric if (CSMI->getParent() == MI->getParent()) { 673*0b57cec5SDimitry Andric for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II) 674*0b57cec5SDimitry Andric for (auto ImplicitDef : ImplicitDefs) 675*0b57cec5SDimitry Andric if (MachineOperand *MO = II->findRegisterUseOperand( 676*0b57cec5SDimitry Andric ImplicitDef, /*isKill=*/true, TRI)) 677*0b57cec5SDimitry Andric MO->setIsKill(false); 678*0b57cec5SDimitry Andric } else { 679*0b57cec5SDimitry Andric // If the instructions aren't in the same BB, bail out and clear the 680*0b57cec5SDimitry Andric // kill flag on all uses of the imp-def'd register. 681*0b57cec5SDimitry Andric for (auto ImplicitDef : ImplicitDefs) 682*0b57cec5SDimitry Andric MRI->clearKillFlags(ImplicitDef); 683*0b57cec5SDimitry Andric } 684*0b57cec5SDimitry Andric 685*0b57cec5SDimitry Andric if (CrossMBBPhysDef) { 686*0b57cec5SDimitry Andric // Add physical register defs now coming in from a predecessor to MBB 687*0b57cec5SDimitry Andric // livein list. 688*0b57cec5SDimitry Andric while (!PhysDefs.empty()) { 689*0b57cec5SDimitry Andric auto LiveIn = PhysDefs.pop_back_val(); 690*0b57cec5SDimitry Andric if (!MBB->isLiveIn(LiveIn.second)) 691*0b57cec5SDimitry Andric MBB->addLiveIn(LiveIn.second); 692*0b57cec5SDimitry Andric } 693*0b57cec5SDimitry Andric ++NumCrossBBCSEs; 694*0b57cec5SDimitry Andric } 695*0b57cec5SDimitry Andric 696*0b57cec5SDimitry Andric MI->eraseFromParent(); 697*0b57cec5SDimitry Andric ++NumCSEs; 698*0b57cec5SDimitry Andric if (!PhysRefs.empty()) 699*0b57cec5SDimitry Andric ++NumPhysCSEs; 700*0b57cec5SDimitry Andric if (Commuted) 701*0b57cec5SDimitry Andric ++NumCommutes; 702*0b57cec5SDimitry Andric Changed = true; 703*0b57cec5SDimitry Andric } else { 704*0b57cec5SDimitry Andric VNT.insert(MI, CurrVN++); 705*0b57cec5SDimitry Andric Exps.push_back(MI); 706*0b57cec5SDimitry Andric } 707*0b57cec5SDimitry Andric CSEPairs.clear(); 708*0b57cec5SDimitry Andric ImplicitDefsToUpdate.clear(); 709*0b57cec5SDimitry Andric ImplicitDefs.clear(); 710*0b57cec5SDimitry Andric } 711*0b57cec5SDimitry Andric 712*0b57cec5SDimitry Andric return Changed; 713*0b57cec5SDimitry Andric } 714*0b57cec5SDimitry Andric 715*0b57cec5SDimitry Andric /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given 716*0b57cec5SDimitry Andric /// dominator tree node if its a leaf or all of its children are done. Walk 717*0b57cec5SDimitry Andric /// up the dominator tree to destroy ancestors which are now done. 718*0b57cec5SDimitry Andric void 719*0b57cec5SDimitry Andric MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, 720*0b57cec5SDimitry Andric DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { 721*0b57cec5SDimitry Andric if (OpenChildren[Node]) 722*0b57cec5SDimitry Andric return; 723*0b57cec5SDimitry Andric 724*0b57cec5SDimitry Andric // Pop scope. 725*0b57cec5SDimitry Andric ExitScope(Node->getBlock()); 726*0b57cec5SDimitry Andric 727*0b57cec5SDimitry Andric // Now traverse upwards to pop ancestors whose offsprings are all done. 728*0b57cec5SDimitry Andric while (MachineDomTreeNode *Parent = Node->getIDom()) { 729*0b57cec5SDimitry Andric unsigned Left = --OpenChildren[Parent]; 730*0b57cec5SDimitry Andric if (Left != 0) 731*0b57cec5SDimitry Andric break; 732*0b57cec5SDimitry Andric ExitScope(Parent->getBlock()); 733*0b57cec5SDimitry Andric Node = Parent; 734*0b57cec5SDimitry Andric } 735*0b57cec5SDimitry Andric } 736*0b57cec5SDimitry Andric 737*0b57cec5SDimitry Andric bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { 738*0b57cec5SDimitry Andric SmallVector<MachineDomTreeNode*, 32> Scopes; 739*0b57cec5SDimitry Andric SmallVector<MachineDomTreeNode*, 8> WorkList; 740*0b57cec5SDimitry Andric DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; 741*0b57cec5SDimitry Andric 742*0b57cec5SDimitry Andric CurrVN = 0; 743*0b57cec5SDimitry Andric 744*0b57cec5SDimitry Andric // Perform a DFS walk to determine the order of visit. 745*0b57cec5SDimitry Andric WorkList.push_back(Node); 746*0b57cec5SDimitry Andric do { 747*0b57cec5SDimitry Andric Node = WorkList.pop_back_val(); 748*0b57cec5SDimitry Andric Scopes.push_back(Node); 749*0b57cec5SDimitry Andric const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 750*0b57cec5SDimitry Andric OpenChildren[Node] = Children.size(); 751*0b57cec5SDimitry Andric for (MachineDomTreeNode *Child : Children) 752*0b57cec5SDimitry Andric WorkList.push_back(Child); 753*0b57cec5SDimitry Andric } while (!WorkList.empty()); 754*0b57cec5SDimitry Andric 755*0b57cec5SDimitry Andric // Now perform CSE. 756*0b57cec5SDimitry Andric bool Changed = false; 757*0b57cec5SDimitry Andric for (MachineDomTreeNode *Node : Scopes) { 758*0b57cec5SDimitry Andric MachineBasicBlock *MBB = Node->getBlock(); 759*0b57cec5SDimitry Andric EnterScope(MBB); 760*0b57cec5SDimitry Andric Changed |= ProcessBlockCSE(MBB); 761*0b57cec5SDimitry Andric // If it's a leaf node, it's done. Traverse upwards to pop ancestors. 762*0b57cec5SDimitry Andric ExitScopeIfDone(Node, OpenChildren); 763*0b57cec5SDimitry Andric } 764*0b57cec5SDimitry Andric 765*0b57cec5SDimitry Andric return Changed; 766*0b57cec5SDimitry Andric } 767*0b57cec5SDimitry Andric 768*0b57cec5SDimitry Andric // We use stronger checks for PRE candidate rather than for CSE ones to embrace 769*0b57cec5SDimitry Andric // checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps 770*0b57cec5SDimitry Andric // to exclude instrs created by PRE that won't be CSEed later. 771*0b57cec5SDimitry Andric bool MachineCSE::isPRECandidate(MachineInstr *MI) { 772*0b57cec5SDimitry Andric if (!isCSECandidate(MI) || 773*0b57cec5SDimitry Andric MI->isNotDuplicable() || 774*0b57cec5SDimitry Andric MI->mayLoad() || 775*0b57cec5SDimitry Andric MI->isAsCheapAsAMove() || 776*0b57cec5SDimitry Andric MI->getNumDefs() != 1 || 777*0b57cec5SDimitry Andric MI->getNumExplicitDefs() != 1) 778*0b57cec5SDimitry Andric return false; 779*0b57cec5SDimitry Andric 780*0b57cec5SDimitry Andric for (auto def : MI->defs()) 781*0b57cec5SDimitry Andric if (!TRI->isVirtualRegister(def.getReg())) 782*0b57cec5SDimitry Andric return false; 783*0b57cec5SDimitry Andric 784*0b57cec5SDimitry Andric for (auto use : MI->uses()) 785*0b57cec5SDimitry Andric if (use.isReg() && !TRI->isVirtualRegister(use.getReg())) 786*0b57cec5SDimitry Andric return false; 787*0b57cec5SDimitry Andric 788*0b57cec5SDimitry Andric return true; 789*0b57cec5SDimitry Andric } 790*0b57cec5SDimitry Andric 791*0b57cec5SDimitry Andric bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT, 792*0b57cec5SDimitry Andric MachineBasicBlock *MBB) { 793*0b57cec5SDimitry Andric bool Changed = false; 794*0b57cec5SDimitry Andric for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;) { 795*0b57cec5SDimitry Andric MachineInstr *MI = &*I; 796*0b57cec5SDimitry Andric ++I; 797*0b57cec5SDimitry Andric 798*0b57cec5SDimitry Andric if (!isPRECandidate(MI)) 799*0b57cec5SDimitry Andric continue; 800*0b57cec5SDimitry Andric 801*0b57cec5SDimitry Andric if (!PREMap.count(MI)) { 802*0b57cec5SDimitry Andric PREMap[MI] = MBB; 803*0b57cec5SDimitry Andric continue; 804*0b57cec5SDimitry Andric } 805*0b57cec5SDimitry Andric 806*0b57cec5SDimitry Andric auto MBB1 = PREMap[MI]; 807*0b57cec5SDimitry Andric assert( 808*0b57cec5SDimitry Andric !DT->properlyDominates(MBB, MBB1) && 809*0b57cec5SDimitry Andric "MBB cannot properly dominate MBB1 while DFS through dominators tree!"); 810*0b57cec5SDimitry Andric auto CMBB = DT->findNearestCommonDominator(MBB, MBB1); 811*0b57cec5SDimitry Andric if (!CMBB->isLegalToHoistInto()) 812*0b57cec5SDimitry Andric continue; 813*0b57cec5SDimitry Andric 814*0b57cec5SDimitry Andric if (!isBeneficalToHoistInto(CMBB, MBB, MBB1)) 815*0b57cec5SDimitry Andric continue; 816*0b57cec5SDimitry Andric 817*0b57cec5SDimitry Andric // Two instrs are partial redundant if their basic blocks are reachable 818*0b57cec5SDimitry Andric // from one to another but one doesn't dominate another. 819*0b57cec5SDimitry Andric if (CMBB != MBB1) { 820*0b57cec5SDimitry Andric auto BB = MBB->getBasicBlock(), BB1 = MBB1->getBasicBlock(); 821*0b57cec5SDimitry Andric if (BB != nullptr && BB1 != nullptr && 822*0b57cec5SDimitry Andric (isPotentiallyReachable(BB1, BB) || 823*0b57cec5SDimitry Andric isPotentiallyReachable(BB, BB1))) { 824*0b57cec5SDimitry Andric 825*0b57cec5SDimitry Andric assert(MI->getOperand(0).isDef() && 826*0b57cec5SDimitry Andric "First operand of instr with one explicit def must be this def"); 827*0b57cec5SDimitry Andric unsigned VReg = MI->getOperand(0).getReg(); 828*0b57cec5SDimitry Andric unsigned NewReg = MRI->cloneVirtualRegister(VReg); 829*0b57cec5SDimitry Andric if (!isProfitableToCSE(NewReg, VReg, CMBB, MI)) 830*0b57cec5SDimitry Andric continue; 831*0b57cec5SDimitry Andric MachineInstr &NewMI = 832*0b57cec5SDimitry Andric TII->duplicate(*CMBB, CMBB->getFirstTerminator(), *MI); 833*0b57cec5SDimitry Andric NewMI.getOperand(0).setReg(NewReg); 834*0b57cec5SDimitry Andric 835*0b57cec5SDimitry Andric PREMap[MI] = CMBB; 836*0b57cec5SDimitry Andric ++NumPREs; 837*0b57cec5SDimitry Andric Changed = true; 838*0b57cec5SDimitry Andric } 839*0b57cec5SDimitry Andric } 840*0b57cec5SDimitry Andric } 841*0b57cec5SDimitry Andric return Changed; 842*0b57cec5SDimitry Andric } 843*0b57cec5SDimitry Andric 844*0b57cec5SDimitry Andric // This simple PRE (partial redundancy elimination) pass doesn't actually 845*0b57cec5SDimitry Andric // eliminate partial redundancy but transforms it to full redundancy, 846*0b57cec5SDimitry Andric // anticipating that the next CSE step will eliminate this created redundancy. 847*0b57cec5SDimitry Andric // If CSE doesn't eliminate this, than created instruction will remain dead 848*0b57cec5SDimitry Andric // and eliminated later by Remove Dead Machine Instructions pass. 849*0b57cec5SDimitry Andric bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) { 850*0b57cec5SDimitry Andric SmallVector<MachineDomTreeNode *, 32> BBs; 851*0b57cec5SDimitry Andric 852*0b57cec5SDimitry Andric PREMap.clear(); 853*0b57cec5SDimitry Andric bool Changed = false; 854*0b57cec5SDimitry Andric BBs.push_back(DT->getRootNode()); 855*0b57cec5SDimitry Andric do { 856*0b57cec5SDimitry Andric auto Node = BBs.pop_back_val(); 857*0b57cec5SDimitry Andric const std::vector<MachineDomTreeNode *> &Children = Node->getChildren(); 858*0b57cec5SDimitry Andric for (MachineDomTreeNode *Child : Children) 859*0b57cec5SDimitry Andric BBs.push_back(Child); 860*0b57cec5SDimitry Andric 861*0b57cec5SDimitry Andric MachineBasicBlock *MBB = Node->getBlock(); 862*0b57cec5SDimitry Andric Changed |= ProcessBlockPRE(DT, MBB); 863*0b57cec5SDimitry Andric 864*0b57cec5SDimitry Andric } while (!BBs.empty()); 865*0b57cec5SDimitry Andric 866*0b57cec5SDimitry Andric return Changed; 867*0b57cec5SDimitry Andric } 868*0b57cec5SDimitry Andric 869*0b57cec5SDimitry Andric bool MachineCSE::isBeneficalToHoistInto(MachineBasicBlock *CandidateBB, 870*0b57cec5SDimitry Andric MachineBasicBlock *MBB, 871*0b57cec5SDimitry Andric MachineBasicBlock *MBB1) { 872*0b57cec5SDimitry Andric if (CandidateBB->getParent()->getFunction().hasMinSize()) 873*0b57cec5SDimitry Andric return true; 874*0b57cec5SDimitry Andric assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB"); 875*0b57cec5SDimitry Andric assert(DT->dominates(CandidateBB, MBB1) && 876*0b57cec5SDimitry Andric "CandidateBB should dominate MBB1"); 877*0b57cec5SDimitry Andric return MBFI->getBlockFreq(CandidateBB) <= 878*0b57cec5SDimitry Andric MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1); 879*0b57cec5SDimitry Andric } 880*0b57cec5SDimitry Andric 881*0b57cec5SDimitry Andric bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 882*0b57cec5SDimitry Andric if (skipFunction(MF.getFunction())) 883*0b57cec5SDimitry Andric return false; 884*0b57cec5SDimitry Andric 885*0b57cec5SDimitry Andric TII = MF.getSubtarget().getInstrInfo(); 886*0b57cec5SDimitry Andric TRI = MF.getSubtarget().getRegisterInfo(); 887*0b57cec5SDimitry Andric MRI = &MF.getRegInfo(); 888*0b57cec5SDimitry Andric AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 889*0b57cec5SDimitry Andric DT = &getAnalysis<MachineDominatorTree>(); 890*0b57cec5SDimitry Andric MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 891*0b57cec5SDimitry Andric LookAheadLimit = TII->getMachineCSELookAheadLimit(); 892*0b57cec5SDimitry Andric bool ChangedPRE, ChangedCSE; 893*0b57cec5SDimitry Andric ChangedPRE = PerformSimplePRE(DT); 894*0b57cec5SDimitry Andric ChangedCSE = PerformCSE(DT->getRootNode()); 895*0b57cec5SDimitry Andric return ChangedPRE || ChangedCSE; 896*0b57cec5SDimitry Andric } 897