diff options
Diffstat (limited to 'llvm/lib/CodeGen')
-rw-r--r-- | llvm/lib/CodeGen/CodeGen.cpp | 2 | ||||
-rw-r--r-- | llvm/lib/CodeGen/MachineCSE.cpp | 284 | ||||
-rw-r--r-- | llvm/lib/CodeGen/TargetPassConfig.cpp | 6 |
3 files changed, 166 insertions, 126 deletions
diff --git a/llvm/lib/CodeGen/CodeGen.cpp b/llvm/lib/CodeGen/CodeGen.cpp index 1777020..16b8d45 100644 --- a/llvm/lib/CodeGen/CodeGen.cpp +++ b/llvm/lib/CodeGen/CodeGen.cpp @@ -75,7 +75,7 @@ void llvm::initializeCodeGen(PassRegistry &Registry) { initializeMachineBlockPlacementPass(Registry); initializeMachineBlockPlacementStatsPass(Registry); initializeMachineCFGPrinterPass(Registry); - initializeMachineCSEPass(Registry); + initializeMachineCSELegacyPass(Registry); initializeMachineCombinerPass(Registry); initializeMachineCopyPropagationPass(Registry); initializeMachineCycleInfoPrinterPassPass(Registry); diff --git a/llvm/lib/CodeGen/MachineCSE.cpp b/llvm/lib/CodeGen/MachineCSE.cpp index 2ac1fae..8e9fccc 100644 --- a/llvm/lib/CodeGen/MachineCSE.cpp +++ b/llvm/lib/CodeGen/MachineCSE.cpp @@ -12,6 +12,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/CodeGen/MachineCSE.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ScopedHashTable.h" #include "llvm/ADT/SmallPtrSet.h" @@ -25,6 +26,7 @@ #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" @@ -69,110 +71,110 @@ static cl::opt<bool> AggressiveMachineCSE( namespace { - class MachineCSE : public MachineFunctionPass { - const TargetInstrInfo *TII = nullptr; - const TargetRegisterInfo *TRI = nullptr; - MachineDominatorTree *DT = nullptr; - MachineRegisterInfo *MRI = nullptr; - MachineBlockFrequencyInfo *MBFI = nullptr; - - public: - static char ID; // Pass identification - - MachineCSE() : MachineFunctionPass(ID) { - initializeMachineCSEPass(*PassRegistry::getPassRegistry()); - } - - bool runOnMachineFunction(MachineFunction &MF) override; - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); - MachineFunctionPass::getAnalysisUsage(AU); - AU.addPreservedID(MachineLoopInfoID); - AU.addRequired<MachineDominatorTreeWrapperPass>(); - AU.addPreserved<MachineDominatorTreeWrapperPass>(); - AU.addRequired<MachineBlockFrequencyInfoWrapperPass>(); - AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>(); - } - - MachineFunctionProperties getRequiredProperties() const override { - return MachineFunctionProperties() - .set(MachineFunctionProperties::Property::IsSSA); - } +class MachineCSEImpl { + const TargetInstrInfo *TII = nullptr; + const TargetRegisterInfo *TRI = nullptr; + MachineDominatorTree *DT = nullptr; + MachineRegisterInfo *MRI = nullptr; + MachineBlockFrequencyInfo *MBFI = nullptr; + +public: + MachineCSEImpl(MachineDominatorTree *DT, MachineBlockFrequencyInfo *MBFI) + : DT(DT), MBFI(MBFI) {} + bool run(MachineFunction &MF); + +private: + using AllocatorTy = + RecyclingAllocator<BumpPtrAllocator, + ScopedHashTableVal<MachineInstr *, unsigned>>; + using ScopedHTType = + ScopedHashTable<MachineInstr *, unsigned, MachineInstrExpressionTrait, + AllocatorTy>; + using ScopeType = ScopedHTType::ScopeTy; + using PhysDefVector = SmallVector<std::pair<unsigned, unsigned>, 2>; + + unsigned LookAheadLimit = 0; + DenseMap<MachineBasicBlock *, ScopeType *> ScopeMap; + DenseMap<MachineInstr *, MachineBasicBlock *, MachineInstrExpressionTrait> + PREMap; + ScopedHTType VNT; + SmallVector<MachineInstr *, 64> Exps; + unsigned CurrVN = 0; + + bool PerformTrivialCopyPropagation(MachineInstr *MI, MachineBasicBlock *MBB); + bool isPhysDefTriviallyDead(MCRegister Reg, + MachineBasicBlock::const_iterator I, + MachineBasicBlock::const_iterator E) const; + bool hasLivePhysRegDefUses(const MachineInstr *MI, + const MachineBasicBlock *MBB, + SmallSet<MCRegister, 8> &PhysRefs, + PhysDefVector &PhysDefs, bool &PhysUseDef) const; + bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, + SmallSet<MCRegister, 8> &PhysRefs, + PhysDefVector &PhysDefs, bool &NonLocal) const; + bool isCSECandidate(MachineInstr *MI); + bool isProfitableToCSE(Register CSReg, Register Reg, MachineBasicBlock *CSBB, + MachineInstr *MI); + void EnterScope(MachineBasicBlock *MBB); + void ExitScope(MachineBasicBlock *MBB); + bool ProcessBlockCSE(MachineBasicBlock *MBB); + void ExitScopeIfDone(MachineDomTreeNode *Node, + DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren); + bool PerformCSE(MachineDomTreeNode *Node); + + bool isPRECandidate(MachineInstr *MI, SmallSet<MCRegister, 8> &PhysRefs); + bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB); + bool PerformSimplePRE(MachineDominatorTree *DT); + /// Heuristics to see if it's profitable to move common computations of MBB + /// and MBB1 to CandidateBB. + bool isProfitableToHoistInto(MachineBasicBlock *CandidateBB, + MachineBasicBlock *MBB, MachineBasicBlock *MBB1); + void releaseMemory(); +}; + +class MachineCSELegacy : public MachineFunctionPass { +public: + static char ID; // Pass identification + + MachineCSELegacy() : MachineFunctionPass(ID) { + initializeMachineCSELegacyPass(*PassRegistry::getPassRegistry()); + } - void releaseMemory() override { - ScopeMap.clear(); - PREMap.clear(); - Exps.clear(); - } + bool runOnMachineFunction(MachineFunction &MF) override; - private: - using AllocatorTy = RecyclingAllocator<BumpPtrAllocator, - ScopedHashTableVal<MachineInstr *, unsigned>>; - using ScopedHTType = - ScopedHashTable<MachineInstr *, unsigned, MachineInstrExpressionTrait, - AllocatorTy>; - using ScopeType = ScopedHTType::ScopeTy; - using PhysDefVector = SmallVector<std::pair<unsigned, unsigned>, 2>; - - unsigned LookAheadLimit = 0; - DenseMap<MachineBasicBlock *, ScopeType *> ScopeMap; - DenseMap<MachineInstr *, MachineBasicBlock *, MachineInstrExpressionTrait> - PREMap; - ScopedHTType VNT; - SmallVector<MachineInstr *, 64> Exps; - unsigned CurrVN = 0; - - bool PerformTrivialCopyPropagation(MachineInstr *MI, - MachineBasicBlock *MBB); - bool isPhysDefTriviallyDead(MCRegister Reg, - MachineBasicBlock::const_iterator I, - MachineBasicBlock::const_iterator E) const; - bool hasLivePhysRegDefUses(const MachineInstr *MI, - const MachineBasicBlock *MBB, - SmallSet<MCRegister, 8> &PhysRefs, - PhysDefVector &PhysDefs, bool &PhysUseDef) const; - bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, - SmallSet<MCRegister, 8> &PhysRefs, - PhysDefVector &PhysDefs, bool &NonLocal) const; - bool isCSECandidate(MachineInstr *MI); - bool isProfitableToCSE(Register CSReg, Register Reg, - MachineBasicBlock *CSBB, MachineInstr *MI); - void EnterScope(MachineBasicBlock *MBB); - void ExitScope(MachineBasicBlock *MBB); - bool ProcessBlockCSE(MachineBasicBlock *MBB); - void ExitScopeIfDone(MachineDomTreeNode *Node, - DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); - bool PerformCSE(MachineDomTreeNode *Node); - - bool isPRECandidate(MachineInstr *MI, SmallSet<MCRegister, 8> &PhysRefs); - bool ProcessBlockPRE(MachineDominatorTree *MDT, MachineBasicBlock *MBB); - bool PerformSimplePRE(MachineDominatorTree *DT); - /// Heuristics to see if it's profitable to move common computations of MBB - /// and MBB1 to CandidateBB. - bool isProfitableToHoistInto(MachineBasicBlock *CandidateBB, - MachineBasicBlock *MBB, - MachineBasicBlock *MBB1); - }; + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + MachineFunctionPass::getAnalysisUsage(AU); + AU.addPreservedID(MachineLoopInfoID); + AU.addRequired<MachineDominatorTreeWrapperPass>(); + AU.addPreserved<MachineDominatorTreeWrapperPass>(); + AU.addRequired<MachineBlockFrequencyInfoWrapperPass>(); + AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>(); + } + MachineFunctionProperties getRequiredProperties() const override { + return MachineFunctionProperties().set( + MachineFunctionProperties::Property::IsSSA); + } +}; } // end anonymous namespace -char MachineCSE::ID = 0; +char MachineCSELegacy::ID = 0; -char &llvm::MachineCSEID = MachineCSE::ID; +char &llvm::MachineCSELegacyID = MachineCSELegacy::ID; -INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE, +INITIALIZE_PASS_BEGIN(MachineCSELegacy, DEBUG_TYPE, "Machine Common Subexpression Elimination", false, false) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) -INITIALIZE_PASS_END(MachineCSE, DEBUG_TYPE, +INITIALIZE_PASS_END(MachineCSELegacy, DEBUG_TYPE, "Machine Common Subexpression Elimination", false, false) /// The source register of a COPY machine instruction can be propagated to all /// its users, and this propagation could increase the probability of finding /// common subexpressions. If the COPY has only one user, the COPY itself can /// be removed. -bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI, - MachineBasicBlock *MBB) { +bool MachineCSEImpl::PerformTrivialCopyPropagation(MachineInstr *MI, + MachineBasicBlock *MBB) { bool Changed = false; for (MachineOperand &MO : MI->all_uses()) { Register Reg = MO.getReg(); @@ -225,7 +227,7 @@ bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI, return Changed; } -bool MachineCSE::isPhysDefTriviallyDead( +bool MachineCSEImpl::isPhysDefTriviallyDead( MCRegister Reg, MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator E) const { unsigned LookAheadLeft = LookAheadLimit; @@ -282,11 +284,11 @@ static bool isCallerPreservedOrConstPhysReg(MCRegister Reg, /// physical registers (except for dead defs of physical registers). It also /// returns the physical register def by reference if it's the only one and the /// instruction does not uses a physical register. -bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, - const MachineBasicBlock *MBB, - SmallSet<MCRegister, 8> &PhysRefs, - PhysDefVector &PhysDefs, - bool &PhysUseDef) const { +bool MachineCSEImpl::hasLivePhysRegDefUses(const MachineInstr *MI, + const MachineBasicBlock *MBB, + SmallSet<MCRegister, 8> &PhysRefs, + PhysDefVector &PhysDefs, + bool &PhysUseDef) const { // First, add all uses to PhysRefs. for (const MachineOperand &MO : MI->all_uses()) { Register Reg = MO.getReg(); @@ -333,10 +335,10 @@ bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, return !PhysRefs.empty(); } -bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, - SmallSet<MCRegister, 8> &PhysRefs, - PhysDefVector &PhysDefs, - bool &NonLocal) const { +bool MachineCSEImpl::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, + SmallSet<MCRegister, 8> &PhysRefs, + PhysDefVector &PhysDefs, + bool &NonLocal) const { // For now conservatively returns false if the common subexpression is // not in the same basic block as the given instruction. The only exception // is if the common subexpression is in the sole predecessor block. @@ -400,7 +402,7 @@ bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, return false; } -bool MachineCSE::isCSECandidate(MachineInstr *MI) { +bool MachineCSEImpl::isCSECandidate(MachineInstr *MI) { if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() || MI->isInlineAsm() || MI->isDebugInstr() || MI->isJumpTableDebugInfo() || MI->isFakeUse()) @@ -437,8 +439,9 @@ bool MachineCSE::isCSECandidate(MachineInstr *MI) { /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a /// common expression that defines Reg. CSBB is basic block where CSReg is /// defined. -bool MachineCSE::isProfitableToCSE(Register CSReg, Register Reg, - MachineBasicBlock *CSBB, MachineInstr *MI) { +bool MachineCSEImpl::isProfitableToCSE(Register CSReg, Register Reg, + MachineBasicBlock *CSBB, + MachineInstr *MI) { if (AggressiveMachineCSE) return true; @@ -513,13 +516,13 @@ bool MachineCSE::isProfitableToCSE(Register CSReg, Register Reg, return !HasPHI; } -void MachineCSE::EnterScope(MachineBasicBlock *MBB) { +void MachineCSEImpl::EnterScope(MachineBasicBlock *MBB) { LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); ScopeType *Scope = new ScopeType(VNT); ScopeMap[MBB] = Scope; } -void MachineCSE::ExitScope(MachineBasicBlock *MBB) { +void MachineCSEImpl::ExitScope(MachineBasicBlock *MBB) { LLVM_DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); assert(SI != ScopeMap.end()); @@ -527,7 +530,7 @@ void MachineCSE::ExitScope(MachineBasicBlock *MBB) { ScopeMap.erase(SI); } -bool MachineCSE::ProcessBlockCSE(MachineBasicBlock *MBB) { +bool MachineCSEImpl::ProcessBlockCSE(MachineBasicBlock *MBB) { bool Changed = false; SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; @@ -748,9 +751,9 @@ bool MachineCSE::ProcessBlockCSE(MachineBasicBlock *MBB) { /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given /// dominator tree node if its a leaf or all of its children are done. Walk /// up the dominator tree to destroy ancestors which are now done. -void -MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, - DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { +void MachineCSEImpl::ExitScopeIfDone( + MachineDomTreeNode *Node, + DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren) { if (OpenChildren[Node]) return; @@ -767,7 +770,7 @@ MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, } } -bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { +bool MachineCSEImpl::PerformCSE(MachineDomTreeNode *Node) { SmallVector<MachineDomTreeNode*, 32> Scopes; SmallVector<MachineDomTreeNode*, 8> WorkList; DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; @@ -799,8 +802,8 @@ bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { // We use stronger checks for PRE candidate rather than for CSE ones to embrace // checks inside ProcessBlockCSE(), not only inside isCSECandidate(). This helps // to exclude instrs created by PRE that won't be CSEed later. -bool MachineCSE::isPRECandidate(MachineInstr *MI, - SmallSet<MCRegister, 8> &PhysRefs) { +bool MachineCSEImpl::isPRECandidate(MachineInstr *MI, + SmallSet<MCRegister, 8> &PhysRefs) { if (!isCSECandidate(MI) || MI->isNotDuplicable() || MI->mayLoad() || @@ -821,8 +824,8 @@ bool MachineCSE::isPRECandidate(MachineInstr *MI, return true; } -bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT, - MachineBasicBlock *MBB) { +bool MachineCSEImpl::ProcessBlockPRE(MachineDominatorTree *DT, + MachineBasicBlock *MBB) { bool Changed = false; for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) { SmallSet<MCRegister, 8> PhysRefs; @@ -902,7 +905,7 @@ bool MachineCSE::ProcessBlockPRE(MachineDominatorTree *DT, // anticipating that the next CSE step will eliminate this created redundancy. // If CSE doesn't eliminate this, than created instruction will remain dead // and eliminated later by Remove Dead Machine Instructions pass. -bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) { +bool MachineCSEImpl::PerformSimplePRE(MachineDominatorTree *DT) { SmallVector<MachineDomTreeNode *, 32> BBs; PREMap.clear(); @@ -920,9 +923,9 @@ bool MachineCSE::PerformSimplePRE(MachineDominatorTree *DT) { return Changed; } -bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB, - MachineBasicBlock *MBB, - MachineBasicBlock *MBB1) { +bool MachineCSEImpl::isProfitableToHoistInto(MachineBasicBlock *CandidateBB, + MachineBasicBlock *MBB, + MachineBasicBlock *MBB1) { if (CandidateBB->getParent()->getFunction().hasMinSize()) return true; assert(DT->dominates(CandidateBB, MBB) && "CandidateBB should dominate MBB"); @@ -932,18 +935,55 @@ bool MachineCSE::isProfitableToHoistInto(MachineBasicBlock *CandidateBB, MBFI->getBlockFreq(MBB) + MBFI->getBlockFreq(MBB1); } -bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { - if (skipFunction(MF.getFunction())) - return false; +void MachineCSEImpl::releaseMemory() { + ScopeMap.clear(); + PREMap.clear(); + Exps.clear(); +} +bool MachineCSEImpl::run(MachineFunction &MF) { TII = MF.getSubtarget().getInstrInfo(); TRI = MF.getSubtarget().getRegisterInfo(); MRI = &MF.getRegInfo(); - DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree(); - MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI(); LookAheadLimit = TII->getMachineCSELookAheadLimit(); bool ChangedPRE, ChangedCSE; ChangedPRE = PerformSimplePRE(DT); ChangedCSE = PerformCSE(DT->getRootNode()); + releaseMemory(); return ChangedPRE || ChangedCSE; } + +PreservedAnalyses MachineCSEPass::run(MachineFunction &MF, + MachineFunctionAnalysisManager &MFAM) { + MFPropsModifier _(*this, MF); + + if (MF.getFunction().hasOptNone()) + return PreservedAnalyses::all(); + + MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(MF); + MachineBlockFrequencyInfo &MBFI = + MFAM.getResult<MachineBlockFrequencyAnalysis>(MF); + MachineCSEImpl Impl(&MDT, &MBFI); + bool Changed = Impl.run(MF); + if (!Changed) + return PreservedAnalyses::all(); + + auto PA = getMachineFunctionPassPreservedAnalyses(); + PA.preserve<MachineLoopAnalysis>(); + PA.preserve<MachineDominatorTreeAnalysis>(); + PA.preserve<MachineBlockFrequencyAnalysis>(); + PA.preserveSet<CFGAnalyses>(); + return PA; +} + +bool MachineCSELegacy::runOnMachineFunction(MachineFunction &MF) { + if (skipFunction(MF.getFunction())) + return false; + + MachineDominatorTree &MDT = + getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree(); + MachineBlockFrequencyInfo &MBFI = + getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI(); + MachineCSEImpl Impl(&MDT, &MBFI); + return Impl.run(MF); +} diff --git a/llvm/lib/CodeGen/TargetPassConfig.cpp b/llvm/lib/CodeGen/TargetPassConfig.cpp index c0b8346..11a7752 100644 --- a/llvm/lib/CodeGen/TargetPassConfig.cpp +++ b/llvm/lib/CodeGen/TargetPassConfig.cpp @@ -311,7 +311,7 @@ static IdentifyingPassPtr overridePass(AnalysisID StandardID, if (StandardID == &EarlyMachineLICMID) return applyDisable(TargetID, DisableMachineLICM); - if (StandardID == &MachineCSEID) + if (StandardID == &MachineCSELegacyID) return applyDisable(TargetID, DisableMachineCSE); if (StandardID == &MachineLICMID) @@ -523,7 +523,7 @@ void llvm::registerCodeGenCallback(PassInstrumentationCallbacks &PIC, DISABLE_PASS(DisableCopyProp, MachineCopyPropagationPass) DISABLE_PASS(DisableEarlyIfConversion, EarlyIfConverterPass) DISABLE_PASS(DisableEarlyTailDup, EarlyTailDuplicatePass) - DISABLE_PASS(DisableMachineCSE, MachineCSEPass) + DISABLE_PASS(DisableMachineCSE, MachineCSELegacyPass) DISABLE_PASS(DisableMachineDCE, DeadMachineInstructionElimPass) DISABLE_PASS(DisableMachineLICM, EarlyMachineLICMPass) DISABLE_PASS(DisableMachineSink, MachineSinkingPass) @@ -1305,7 +1305,7 @@ void TargetPassConfig::addMachineSSAOptimization() { addILPOpts(); addPass(&EarlyMachineLICMID); - addPass(&MachineCSEID); + addPass(&MachineCSELegacyID); addPass(&MachineSinkingID); |