diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2019-01-19 10:01:25 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2019-01-19 10:01:25 +0000 |
commit | d8e91e46262bc44006913e6796843909f1ac7bcd (patch) | |
tree | 7d0c143d9b38190e0fa0180805389da22cd834c5 /lib/Transforms/Scalar/GVN.cpp | |
parent | b7eb8e35e481a74962664b63dfb09483b200209a (diff) | |
download | src-d8e91e46262bc44006913e6796843909f1ac7bcd.tar.gz src-d8e91e46262bc44006913e6796843909f1ac7bcd.zip |
Vendor import of llvm trunk r351319 (just before the release_80 branchvendor/llvm/llvm-trunk-r351319
Notes
Notes:
svn path=/vendor/llvm/dist/; revision=343171
svn path=/vendor/llvm/llvm-trunk-r351319/; revision=343172; tag=vendor/llvm/llvm-trunk-r351319
Diffstat (limited to 'lib/Transforms/Scalar/GVN.cpp')
-rw-r--r-- | lib/Transforms/Scalar/GVN.cpp | 201 |
1 files changed, 65 insertions, 136 deletions
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 1e0a22cb14b3..9861948c8297 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -38,7 +38,6 @@ #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/PHITransAddr.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/Attributes.h" @@ -48,6 +47,7 @@ #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugLoc.h" +#include "llvm/IR/DomTreeUpdater.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" @@ -71,6 +71,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/SSAUpdater.h" #include "llvm/Transforms/Utils/VNCoercion.h" #include <algorithm> @@ -97,11 +98,16 @@ STATISTIC(NumPRELoad, "Number of loads PRE'd"); static cl::opt<bool> EnablePRE("enable-pre", cl::init(true), cl::Hidden); static cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true)); +static cl::opt<bool> EnableMemDep("enable-gvn-memdep", cl::init(true)); // Maximum allowed recursion depth. static cl::opt<uint32_t> -MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, - cl::desc("Max recurse depth (default = 1000)")); +MaxRecurseDepth("gvn-max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, + cl::desc("Max recurse depth in GVN (default = 1000)")); + +static cl::opt<uint32_t> MaxNumDeps( + "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore, + cl::desc("Max number of dependences to attempt Load PRE (default = 100)")); struct llvm::GVN::Expression { uint32_t opcode; @@ -392,18 +398,13 @@ uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) { uint32_t e = assignExpNewValueNum(exp).first; valueNumbering[C] = e; return e; - } else if (AA->onlyReadsMemory(C)) { + } else if (MD && AA->onlyReadsMemory(C)) { Expression exp = createExpr(C); auto ValNum = assignExpNewValueNum(exp); if (ValNum.second) { valueNumbering[C] = ValNum.first; return ValNum.first; } - if (!MD) { - uint32_t e = assignExpNewValueNum(exp).first; - valueNumbering[C] = e; - return e; - } MemDepResult local_dep = MD->getDependency(C); @@ -436,7 +437,7 @@ uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) { // Non-local case. const MemoryDependenceResults::NonLocalDepInfo &deps = - MD->getNonLocalCallDependency(CallSite(C)); + MD->getNonLocalCallDependency(C); // FIXME: Move the checking logic to MemDep! CallInst* cdep = nullptr; @@ -677,7 +678,7 @@ static bool IsValueFullyAvailableInBlock(BasicBlock *BB, // Optimistically assume that the block is fully available and check to see // if we already know about this block in one lookup. - std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV = + std::pair<DenseMap<BasicBlock*, char>::iterator, bool> IV = FullyAvailableBlocks.insert(std::make_pair(BB, 2)); // If the entry already existed for this block, return the precomputed value. @@ -1074,15 +1075,8 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, // because if the index is out of bounds we should deoptimize rather than // access the array. // Check that there is no guard in this block above our instruction. - if (!IsSafeToSpeculativelyExecute) { - auto It = FirstImplicitControlFlowInsts.find(TmpBB); - if (It != FirstImplicitControlFlowInsts.end()) { - assert(It->second->getParent() == TmpBB && - "Implicit control flow map broken?"); - if (OI->dominates(It->second, LI)) - return false; - } - } + if (!IsSafeToSpeculativelyExecute && ICF->isDominatedByICFIFromSameBlock(LI)) + return false; while (TmpBB->getSinglePredecessor()) { TmpBB = TmpBB->getSinglePredecessor(); if (TmpBB == LoadBB) // Infinite (unreachable) loop. @@ -1099,8 +1093,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, return false; // Check that there is no implicit control flow in a block above. - if (!IsSafeToSpeculativelyExecute && - FirstImplicitControlFlowInsts.count(TmpBB)) + if (!IsSafeToSpeculativelyExecute && ICF->hasICF(TmpBB)) return false; } @@ -1322,7 +1315,7 @@ bool GVN::processNonLocalLoad(LoadInst *LI) { // dependencies, this load isn't worth worrying about. Optimizing // it will be too expensive. unsigned NumDeps = Deps.size(); - if (NumDeps > 100) + if (NumDeps > MaxNumDeps) return false; // If we had a phi translation failure, we'll have a single entry which is a @@ -1451,37 +1444,6 @@ bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) { return Changed; } -static void patchReplacementInstruction(Instruction *I, Value *Repl) { - auto *ReplInst = dyn_cast<Instruction>(Repl); - if (!ReplInst) - return; - - // Patch the replacement so that it is not more restrictive than the value - // being replaced. - // Note that if 'I' is a load being replaced by some operation, - // for example, by an arithmetic operation, then andIRFlags() - // would just erase all math flags from the original arithmetic - // operation, which is clearly not wanted and not needed. - if (!isa<LoadInst>(I)) - ReplInst->andIRFlags(I); - - // FIXME: If both the original and replacement value are part of the - // same control-flow region (meaning that the execution of one - // guarantees the execution of the other), then we can combine the - // noalias scopes here and do better than the general conservative - // answer used in combineMetadata(). - - // In general, GVN unifies expressions over different control-flow - // regions, and so we need a conservative combination of the noalias - // scopes. - static const unsigned KnownIDs[] = { - LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, - LLVMContext::MD_noalias, LLVMContext::MD_range, - LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, - LLVMContext::MD_invariant_group}; - combineMetadata(ReplInst, I, KnownIDs); -} - static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) { patchReplacementInstruction(I, Repl); I->replaceAllUsesWith(Repl); @@ -1683,10 +1645,12 @@ static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, } void GVN::assignBlockRPONumber(Function &F) { + BlockRPONumber.clear(); uint32_t NextBlockNumber = 1; ReversePostOrderTraversal<Function *> RPOT(&F); for (BasicBlock *BB : RPOT) BlockRPONumber[BB] = NextBlockNumber++; + InvalidBlockRPONumbers = false; } // Tries to replace instruction with const, using information from @@ -1778,6 +1742,9 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; + // Cached information for anything that uses LHS will be invalid. + if (MD) + MD->invalidateCachedPointerInfo(LHS); } // Now try to deduce additional equalities from this one. For example, if @@ -1853,6 +1820,9 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, Root.getStart()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; + // Cached information for anything that uses NotCmp will be invalid. + if (MD) + MD->invalidateCachedPointerInfo(NotCmp); } } // Ensure that any instruction in scope that gets the "A < B" value number @@ -1975,7 +1945,7 @@ bool GVN::processInstruction(Instruction *I) { // Allocations are always uniquely numbered, so we can save time and memory // by fast failing them. - if (isa<AllocaInst>(I) || isa<TerminatorInst>(I) || isa<PHINode>(I)) { + if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) { addToLeaderTable(Num, I, I->getParent()); return false; } @@ -2020,20 +1990,22 @@ bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, TLI = &RunTLI; VN.setAliasAnalysis(&RunAA); MD = RunMD; - OrderedInstructions OrderedInstrs(DT); - OI = &OrderedInstrs; + ImplicitControlFlowTracking ImplicitCFT(DT); + ICF = &ImplicitCFT; VN.setMemDep(MD); ORE = RunORE; + InvalidBlockRPONumbers = true; bool Changed = false; bool ShouldContinue = true; + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); // Merge unconditional branches, allowing PRE to catch more // optimization opportunities. for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { BasicBlock *BB = &*FI++; - bool removedBlock = MergeBlockIntoPredecessor(BB, DT, LI, MD); + bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, nullptr, MD); if (removedBlock) ++NumGVNBlocks; @@ -2052,7 +2024,6 @@ bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, // Fabricate val-num for dead-code in order to suppress assertion in // performPRE(). assignValNumForDeadCode(); - assignBlockRPONumber(F); bool PREChanged = true; while (PREChanged) { PREChanged = performPRE(F); @@ -2104,27 +2075,16 @@ bool GVN::processBlock(BasicBlock *BB) { if (!AtStart) --BI; - bool InvalidateImplicitCF = false; - const Instruction *MaybeFirstICF = FirstImplicitControlFlowInsts.lookup(BB); for (auto *I : InstrsToErase) { assert(I->getParent() == BB && "Removing instruction from wrong block?"); LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n'); salvageDebugInfo(*I); if (MD) MD->removeInstruction(I); LLVM_DEBUG(verifyRemoved(I)); - if (MaybeFirstICF == I) { - // We have erased the first ICF in block. The map needs to be updated. - InvalidateImplicitCF = true; - // Do not keep dangling pointer on the erased instruction. - MaybeFirstICF = nullptr; - } + ICF->removeInstruction(I); I->eraseFromParent(); } - - OI->invalidateBlock(BB); InstrsToErase.clear(); - if (InvalidateImplicitCF) - fillImplicitControlFlowInfo(BB); if (AtStart) BI = BB->begin(); @@ -2184,7 +2144,7 @@ bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, } bool GVN::performScalarPRE(Instruction *CurInst) { - if (isa<AllocaInst>(CurInst) || isa<TerminatorInst>(CurInst) || + if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() || isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() || CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() || isa<DbgInfoIntrinsic>(CurInst)) @@ -2197,6 +2157,16 @@ bool GVN::performScalarPRE(Instruction *CurInst) { if (isa<CmpInst>(CurInst)) return false; + // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from + // sinking the addressing mode computation back to its uses. Extending the + // GEP's live range increases the register pressure, and therefore it can + // introduce unnecessary spills. + // + // This doesn't prevent Load PRE. PHI translation will make the GEP available + // to the load by moving it to the predecessor block if necessary. + if (isa<GetElementPtrInst>(CurInst)) + return false; + // We don't currently value number ANY inline asm calls. if (CallInst *CallI = dyn_cast<CallInst>(CurInst)) if (CallI->isInlineAsm()) @@ -2215,6 +2185,10 @@ bool GVN::performScalarPRE(Instruction *CurInst) { BasicBlock *PREPred = nullptr; BasicBlock *CurrentBlock = CurInst->getParent(); + // Update the RPO numbers for this function. + if (InvalidBlockRPONumbers) + assignBlockRPONumber(*CurrentBlock->getParent()); + SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap; for (BasicBlock *P : predecessors(CurrentBlock)) { // We're not interested in PRE where blocks with predecessors that are @@ -2226,6 +2200,8 @@ bool GVN::performScalarPRE(Instruction *CurInst) { // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and // when CurInst has operand defined in CurrentBlock (so it may be defined // by phi in the loop header). + assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) && + "Invalid BlockRPONumber map."); if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] && llvm::any_of(CurInst->operands(), [&](const Use &U) { if (auto *Inst = dyn_cast<Instruction>(U.get())) @@ -2268,13 +2244,8 @@ bool GVN::performScalarPRE(Instruction *CurInst) { // is always executed. An instruction with implicit control flow could // prevent us from doing it. If we cannot speculate the execution, then // PRE should be prohibited. - auto It = FirstImplicitControlFlowInsts.find(CurrentBlock); - if (It != FirstImplicitControlFlowInsts.end()) { - assert(It->second->getParent() == CurrentBlock && - "Implicit control flow map broken?"); - if (OI->dominates(It->second, CurInst)) - return false; - } + if (ICF->isDominatedByICFIFromSameBlock(CurInst)) + return false; } // Don't do PRE across indirect branch. @@ -2335,14 +2306,10 @@ bool GVN::performScalarPRE(Instruction *CurInst) { if (MD) MD->removeInstruction(CurInst); LLVM_DEBUG(verifyRemoved(CurInst)); - bool InvalidateImplicitCF = - FirstImplicitControlFlowInsts.lookup(CurInst->getParent()) == CurInst; // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes // some assertion failures. - OI->invalidateBlock(CurrentBlock); + ICF->removeInstruction(CurInst); CurInst->eraseFromParent(); - if (InvalidateImplicitCF) - fillImplicitControlFlowInfo(CurrentBlock); ++NumGVNInstr; return true; @@ -2382,6 +2349,7 @@ BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) { SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT)); if (MD) MD->invalidateCachedPredecessors(); + InvalidBlockRPONumbers = true; return BB; } @@ -2391,11 +2359,12 @@ bool GVN::splitCriticalEdges() { if (toSplit.empty()) return false; do { - std::pair<TerminatorInst*, unsigned> Edge = toSplit.pop_back_val(); + std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val(); SplitCriticalEdge(Edge.first, Edge.second, CriticalEdgeSplittingOptions(DT)); } while (!toSplit.empty()); if (MD) MD->invalidateCachedPredecessors(); + InvalidBlockRPONumbers = true; return true; } @@ -2411,8 +2380,6 @@ bool GVN::iterateOnFunction(Function &F) { ReversePostOrderTraversal<Function *> RPOT(&F); for (BasicBlock *BB : RPOT) - fillImplicitControlFlowInfo(BB); - for (BasicBlock *BB : RPOT) Changed |= processBlock(BB); return Changed; @@ -2423,48 +2390,8 @@ void GVN::cleanupGlobalSets() { LeaderTable.clear(); BlockRPONumber.clear(); TableAllocator.Reset(); - FirstImplicitControlFlowInsts.clear(); -} - -void -GVN::fillImplicitControlFlowInfo(BasicBlock *BB) { - // Make sure that all marked instructions are actually deleted by this point, - // so that we don't need to care about omitting them. - assert(InstrsToErase.empty() && "Filling before removed all marked insns?"); - auto MayNotTransferExecutionToSuccessor = [&](const Instruction *I) { - // If a block's instruction doesn't always pass the control to its successor - // instruction, mark the block as having implicit control flow. We use them - // to avoid wrong assumptions of sort "if A is executed and B post-dominates - // A, then B is also executed". This is not true is there is an implicit - // control flow instruction (e.g. a guard) between them. - // - // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false - // for volatile stores and loads because they can trap. The discussion on - // whether or not it is correct is still ongoing. We might want to get rid - // of this logic in the future. Anyways, trapping instructions shouldn't - // introduce implicit control flow, so we explicitly allow them here. This - // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed. - if (isGuaranteedToTransferExecutionToSuccessor(I)) - return false; - if (isa<LoadInst>(I)) { - assert(cast<LoadInst>(I)->isVolatile() && - "Non-volatile load should transfer execution to successor!"); - return false; - } - if (isa<StoreInst>(I)) { - assert(cast<StoreInst>(I)->isVolatile() && - "Non-volatile store should transfer execution to successor!"); - return false; - } - return true; - }; - FirstImplicitControlFlowInsts.erase(BB); - - for (auto &I : *BB) - if (MayNotTransferExecutionToSuccessor(&I)) { - FirstImplicitControlFlowInsts[BB] = &I; - break; - } + ICF->clear(); + InvalidBlockRPONumbers = true; } /// Verify that the specified instruction does not occur in our @@ -2554,6 +2481,8 @@ void GVN::addDeadBlock(BasicBlock *BB) { PHINode &Phi = cast<PHINode>(*II); Phi.setIncomingValue(Phi.getBasicBlockIndex(P), UndefValue::get(Phi.getType())); + if (MD) + MD->invalidateCachedPointerInfo(&Phi); } } } @@ -2613,8 +2542,8 @@ class llvm::gvn::GVNLegacyPass : public FunctionPass { public: static char ID; // Pass identification, replacement for typeid - explicit GVNLegacyPass(bool NoLoads = false) - : FunctionPass(ID), NoLoads(NoLoads) { + explicit GVNLegacyPass(bool NoMemDepAnalysis = !EnableMemDep) + : FunctionPass(ID), NoMemDepAnalysis(NoMemDepAnalysis) { initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry()); } @@ -2629,7 +2558,7 @@ public: getAnalysis<DominatorTreeWrapperPass>().getDomTree(), getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), getAnalysis<AAResultsWrapperPass>().getAAResults(), - NoLoads ? nullptr + NoMemDepAnalysis ? nullptr : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep(), LIWP ? &LIWP->getLoopInfo() : nullptr, &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE()); @@ -2639,7 +2568,7 @@ public: AU.addRequired<AssumptionCacheTracker>(); AU.addRequired<DominatorTreeWrapperPass>(); AU.addRequired<TargetLibraryInfoWrapperPass>(); - if (!NoLoads) + if (!NoMemDepAnalysis) AU.addRequired<MemoryDependenceWrapperPass>(); AU.addRequired<AAResultsWrapperPass>(); @@ -2650,7 +2579,7 @@ public: } private: - bool NoLoads; + bool NoMemDepAnalysis; GVN Impl; }; @@ -2667,6 +2596,6 @@ INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) // The public interface to this file... -FunctionPass *llvm::createGVNPass(bool NoLoads) { - return new GVNLegacyPass(NoLoads); +FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) { + return new GVNLegacyPass(NoMemDepAnalysis); } |