//===- GVN.cpp - Eliminate redundant values and loads ---------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This pass performs global value numbering to eliminate fully redundant // instructions. It also performs simple dead load elimination. // // Note that this pass does the value numbering itself; it does not use the // ValueNumbering analysis passes. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/GVN.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumeBundleQueries.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionPrecedenceTracking.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/PHITransAddr.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/AssumeBundleBuilder.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> #include <cassert> #include <cstdint> #include <optional> #include <utility> usingnamespacellvm; usingnamespacellvm::gvn; usingnamespacellvm::VNCoercion; usingnamespacePatternMatch; #define DEBUG_TYPE … STATISTIC(NumGVNInstr, "Number of instructions deleted"); STATISTIC(NumGVNLoad, "Number of loads deleted"); STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); STATISTIC(NumGVNBlocks, "Number of blocks merged"); STATISTIC(NumGVNSimpl, "Number of instructions simplified"); STATISTIC(NumGVNEqProp, "Number of equalities propagated"); STATISTIC(NumPRELoad, "Number of loads PRE'd"); STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd"); STATISTIC(NumPRELoadMoved2CEPred, "Number of loads moved to predecessor of a critical edge in PRE"); STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax, "Number of blocks speculated as available in " "IsValueFullyAvailableInBlock(), max"); STATISTIC(MaxBBSpeculationCutoffReachedTimes, "Number of times we we reached gvn-max-block-speculations cut-off " "preventing further exploration"); static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden); static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true)); static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre", cl::init(true)); static cl::opt<bool> GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", cl::init(false)); static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true)); static cl::opt<uint32_t> MaxNumDeps( "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)")); // This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat. static cl::opt<uint32_t> MaxBBSpeculations( "gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)")); static cl::opt<uint32_t> MaxNumVisitedInsts( "gvn-max-num-visited-insts", cl::Hidden, cl::init(100), cl::desc("Max number of visited instructions when trying to find " "dominating value of select dependency (default = 100)")); static cl::opt<uint32_t> MaxNumInsnsPerBlock( "gvn-max-num-insns", cl::Hidden, cl::init(100), cl::desc("Max number of instructions to scan in each basic block in GVN " "(default = 100)")); struct llvm::GVNPass::Expression { … }; namespace llvm { template <> struct DenseMapInfo<GVNPass::Expression> { … }; } // end namespace llvm /// Represents a particular available value that we know how to materialize. /// Materialization of an AvailableValue never fails. An AvailableValue is /// implicitly associated with a rematerialization point which is the /// location of the instruction from which it was formed. struct llvm::gvn::AvailableValue { … }; /// Represents an AvailableValue which can be rematerialized at the end of /// the associated BasicBlock. struct llvm::gvn::AvailableValueInBlock { … }; //===----------------------------------------------------------------------===// // ValueTable Internal Functions //===----------------------------------------------------------------------===// GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) { … } GVNPass::Expression GVNPass::ValueTable::createCmpExpr( unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { … } GVNPass::Expression GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) { … } GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) { … } //===----------------------------------------------------------------------===// // ValueTable External Functions //===----------------------------------------------------------------------===// GVNPass::ValueTable::ValueTable() = default; GVNPass::ValueTable::ValueTable(const ValueTable &) = default; GVNPass::ValueTable::ValueTable(ValueTable &&) = default; GVNPass::ValueTable::~ValueTable() = default; GVNPass::ValueTable & GVNPass::ValueTable::operator=(const GVNPass::ValueTable &Arg) = default; /// add - Insert a value into the table with a specified value number. void GVNPass::ValueTable::add(Value *V, uint32_t num) { … } uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) { … } /// Returns true if a value number exists for the specified value. bool GVNPass::ValueTable::exists(Value *V) const { … } /// lookup_or_add - Returns the value number for the specified value, assigning /// it a new number if it did not have one before. uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) { … } /// Returns the value number of the specified value. Fails if /// the value has not yet been numbered. uint32_t GVNPass::ValueTable::lookup(Value *V, bool Verify) const { … } /// Returns the value number of the given comparison, /// assigning it a new number if it did not have one before. Useful when /// we deduced the result of a comparison, but don't immediately have an /// instruction realizing that comparison to hand. uint32_t GVNPass::ValueTable::lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { … } /// Remove all entries from the ValueTable. void GVNPass::ValueTable::clear() { … } /// Remove a value from the value numbering. void GVNPass::ValueTable::erase(Value *V) { … } /// verifyRemoved - Verify that the value is removed from all internal data /// structures. void GVNPass::ValueTable::verifyRemoved(const Value *V) const { … } //===----------------------------------------------------------------------===// // LeaderMap External Functions //===----------------------------------------------------------------------===// /// Push a new Value to the LeaderTable onto the list for its value number. void GVNPass::LeaderMap::insert(uint32_t N, Value *V, const BasicBlock *BB) { … } /// Scan the list of values corresponding to a given /// value number, and remove the given instruction if encountered. void GVNPass::LeaderMap::erase(uint32_t N, Instruction *I, const BasicBlock *BB) { … } void GVNPass::LeaderMap::verifyRemoved(const Value *V) const { … } //===----------------------------------------------------------------------===// // GVN Pass //===----------------------------------------------------------------------===// bool GVNPass::isPREEnabled() const { … } bool GVNPass::isLoadPREEnabled() const { … } bool GVNPass::isLoadInLoopPREEnabled() const { … } bool GVNPass::isLoadPRESplitBackedgeEnabled() const { … } bool GVNPass::isMemDepEnabled() const { … } PreservedAnalyses GVNPass::run(Function &F, FunctionAnalysisManager &AM) { … } void GVNPass::printPipeline( raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { … } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void GVNPass::dump(DenseMap<uint32_t, Value *> &d) const { errs() << "{\n"; for (auto &I : d) { errs() << I.first << "\n"; I.second->dump(); } errs() << "}\n"; } #endif enum class AvailabilityState : char { … }; /// Return true if we can prove that the value /// we're analyzing is fully available in the specified block. As we go, keep /// track of which blocks we know are fully alive in FullyAvailableBlocks. This /// map is actually a tri-state map with the following values: /// 0) we know the block *is not* fully available. /// 1) we know the block *is* fully available. /// 2) we do not know whether the block is fully available or not, but we are /// currently speculating that it will be. static bool IsValueFullyAvailableInBlock( BasicBlock *BB, DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) { … } /// If the specified OldValue exists in ValuesPerBlock, replace its value with /// NewValue. static void replaceValuesPerBlockEntry( SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, Value *OldValue, Value *NewValue) { … } /// Given a set of loads specified by ValuesPerBlock, /// construct SSA form, allowing us to eliminate Load. This returns the value /// that should be used at Load's definition site. static Value * ConstructSSAForLoadSet(LoadInst *Load, SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, GVNPass &gvn) { … } Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt, GVNPass &gvn) const { … } static bool isLifetimeStart(const Instruction *Inst) { … } /// Assuming To can be reached from both From and Between, does Between lie on /// every path from From to To? static bool liesBetween(const Instruction *From, Instruction *Between, const Instruction *To, DominatorTree *DT) { … } /// Try to locate the three instruction involved in a missed /// load-elimination case that is due to an intervening store. static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo, DominatorTree *DT, OptimizationRemarkEmitter *ORE) { … } // Find non-clobbered value for Loc memory location in extended basic block // (chain of basic blocks with single predecessors) starting From instruction. static Value *findDominatingValue(const MemoryLocation &Loc, Type *LoadTy, Instruction *From, AAResults *AA) { … } std::optional<AvailableValue> GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address) { … } void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks) { … } /// Given the following code, v1 is partially available on some edges, but not /// available on the edge from PredBB. This function tries to find if there is /// another identical load in the other successor of PredBB. /// /// v0 = load %addr /// br %LoadBB /// /// LoadBB: /// v1 = load %addr /// ... /// /// PredBB: /// ... /// br %cond, label %LoadBB, label %SuccBB /// /// SuccBB: /// v2 = load %addr /// ... /// LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB, LoadInst *Load) { … } void GVNPass::eliminatePartiallyRedundantLoad( LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, MapVector<BasicBlock *, Value *> &AvailableLoads, MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad) { … } bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks) { … } bool GVNPass::performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks) { … } static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE) { … } /// Attempt to eliminate a load whose dependencies are /// non-local by performing PHI construction. bool GVNPass::processNonLocalLoad(LoadInst *Load) { … } static bool impliesEquivalanceIfTrue(CmpInst* Cmp) { … } static bool impliesEquivalanceIfFalse(CmpInst* Cmp) { … } static bool hasUsersIn(Value *V, BasicBlock *BB) { … } bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) { … } static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) { … } /// Attempt to eliminate a load, first by eliminating it /// locally, and then attempting non-local elimination if that fails. bool GVNPass::processLoad(LoadInst *L) { … } /// Return a pair the first field showing the value number of \p Exp and the /// second field showing whether it is a value number newly created. std::pair<uint32_t, bool> GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) { … } /// Return whether all the values related with the same \p num are /// defined in \p BB. bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB, GVNPass &Gvn) { … } /// Wrap phiTranslateImpl to provide caching functionality. uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn) { … } // Return true if the value number \p Num and NewNum have equal value. // Return false if the result is unknown. bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred, const BasicBlock *PhiBlock, GVNPass &Gvn) { … } /// Translate value number \p Num using phis, so that it has the values of /// the phis in BB. uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn) { … } /// Erase stale entry from phiTranslate cache so phiTranslate can be computed /// again. void GVNPass::ValueTable::eraseTranslateCacheEntry( uint32_t Num, const BasicBlock &CurrBlock) { … } // In order to find a leader for a given value number at a // specific basic block, we first obtain the list of all Values for that number, // and then scan the list to find one whose block dominates the block in // question. This is fast because dominator tree queries consist of only // a few comparisons of DFS numbers. Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) { … } /// There is an edge from 'Src' to 'Dst'. Return /// true if every path from the entry block to 'Dst' passes via this edge. In /// particular 'Dst' must not be reachable via another edge from 'Src'. static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT) { … } void GVNPass::assignBlockRPONumber(Function &F) { … } bool GVNPass::replaceOperandsForInBlockEquality(Instruction *Instr) const { … } /// The given values are known to be equal in every block /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with /// 'RHS' everywhere in the scope. Returns whether a change was made. /// If DominatesByEdge is false, then it means that we will propagate the RHS /// value starting from the end of Root.Start. bool GVNPass::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, bool DominatesByEdge) { … } /// When calculating availability, handle an instruction /// by inserting it into the appropriate sets bool GVNPass::processInstruction(Instruction *I) { … } /// runOnFunction - This is the main transformation entry point for a function. bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, const TargetLibraryInfo &RunTLI, AAResults &RunAA, MemoryDependenceResults *RunMD, LoopInfo &LI, OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) { … } bool GVNPass::processBlock(BasicBlock *BB) { … } // Instantiate an expression in a predecessor that lacked it. bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, BasicBlock *Curr, unsigned int ValNo) { … } bool GVNPass::performScalarPRE(Instruction *CurInst) { … } /// Perform a purely local form of PRE that looks for diamond /// control flow patterns and attempts to perform simple PRE at the join point. bool GVNPass::performPRE(Function &F) { … } /// Split the critical edge connecting the given two blocks, and return /// the block inserted to the critical edge. BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) { … } /// Split critical edges found during the previous /// iteration that may enable further optimization. bool GVNPass::splitCriticalEdges() { … } /// Executes one iteration of GVN bool GVNPass::iterateOnFunction(Function &F) { … } void GVNPass::cleanupGlobalSets() { … } void GVNPass::removeInstruction(Instruction *I) { … } /// Verify that the specified instruction does not occur in our /// internal data structures. void GVNPass::verifyRemoved(const Instruction *Inst) const { … } /// BB is declared dead, which implied other blocks become dead as well. This /// function is to add all these blocks to "DeadBlocks". For the dead blocks' /// live successors, update their phi nodes by replacing the operands /// corresponding to dead blocks with UndefVal. void GVNPass::addDeadBlock(BasicBlock *BB) { … } // If the given branch is recognized as a foldable branch (i.e. conditional // branch with constant condition), it will perform following analyses and // transformation. // 1) If the dead out-coming edge is a critical-edge, split it. Let // R be the target of the dead out-coming edge. // 1) Identify the set of dead blocks implied by the branch's dead outcoming // edge. The result of this step will be {X| X is dominated by R} // 2) Identify those blocks which haves at least one dead predecessor. The // result of this step will be dominance-frontier(R). // 3) Update the PHIs in DF(R) by replacing the operands corresponding to // dead blocks with "UndefVal" in an hope these PHIs will optimized away. // // Return true iff *NEW* dead code are found. bool GVNPass::processFoldableCondBr(BranchInst *BI) { … } // performPRE() will trigger assert if it comes across an instruction without // associated val-num. As it normally has far more live instructions than dead // instructions, it makes more sense just to "fabricate" a val-number for the // dead code than checking if instruction involved is dead or not. void GVNPass::assignValNumForDeadCode() { … } class llvm::gvn::GVNLegacyPass : public FunctionPass { … }; char GVNLegacyPass::ID = …; INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) // The public interface to this file... FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) { … }
Codebase Browser
llvm