llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-transforms Author: Momchil Velikov (momchil-velikov) <details> <summary>Changes</summary> Over the years GVN.h/GVN.cpp has grown in size and complexity, and the order of member functions and definitions has become somewhat arbitrary. This commit reorganises the code to improve readability and maintainability. * in `GVNPass` class, put private member variables first, followed by public member functions, and then private member functions * in `GVNPass` class: private type definitions are placed in front of the logically related member variables (except `ValueTable` which need to be public) * definitions of `GVNPass::ValueTable` methods are grouped and reordered to match the order of their declarations * The following `GVNPass` member functions were made `private` and `LLVM_API` removed: `getDominatorTree`, `getAliasAnalysis`, `getMemDep`, `isScalarPREEnabled`, `isLoadPREEnabled`, `isLoadInLoopPREEnabled`, `isLoadPRESplitBackedgeEnabled`, `isMemDepEnabled`, `isMemorySSAEnabled`, and `salvageAndRemoveInstruction` * `constructSSAForLoadSet` changed to take a `Dominator &`, in order to not require access to the (now) private `getDominatorTree` * member functions of `GVNPass` rearranged into a more logical order: - starting with the main pass entry pount (`runImpl`) put utility member functions in front of their callers, in order of calling (where it matters), for example `runImpl` -> `iterateOnFunction` -> `perfromPRE` - group functions of the same "theme" together, for example `iterateOnFunction` + `processBlock` + `processInstrution`, or another example, `performLoadPRE` + `performLoopLoadPRE` - put miscelaneous helper member functions at the end * rearrange definitions in `GVN.cpp` to match the order of declarations in `GVN.h` * place `static` helper functions close and in front of their callers --- Patch is 149.63 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/210334.diff 2 Files Affected: - (modified) llvm/include/llvm/Transforms/Scalar/GVN.h (+107-84) - (modified) llvm/lib/Transforms/Scalar/GVN.cpp (+1522-1523) ``````````diff diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h index 0b9c8dc88fe14..46c54363298a2 100644 --- a/llvm/include/llvm/Transforms/Scalar/GVN.h +++ b/llvm/include/llvm/Transforms/Scalar/GVN.h @@ -120,37 +120,10 @@ struct GVNOptions { /// FIXME: We should have a good summary of the GVN algorithm implemented by /// this particular pass here. class GVNPass : public OptionalPassInfoMixin<GVNPass> { - GVNOptions Options; - public: struct Expression; struct AvailableValue; struct AvailableValueInBlock; - - GVNPass(GVNOptions Options = {}) : Options(Options) {} - - /// Run the pass over the function. - LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); - - LLVM_ABI void - printPipeline(raw_ostream &OS, - function_ref<StringRef(StringRef)> MapClassName2PassName); - - /// This removes the specified instruction from - /// our various maps and marks it for deletion. - LLVM_ABI void salvageAndRemoveInstruction(Instruction *I); - - DominatorTree &getDominatorTree() const { return *DT; } - AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); } - MemoryDependenceResults &getMemDep() const { return *MD; } - - LLVM_ABI bool isScalarPREEnabled() const; - LLVM_ABI bool isLoadPREEnabled() const; - LLVM_ABI bool isLoadInLoopPREEnabled() const; - LLVM_ABI bool isLoadPRESplitBackedgeEnabled() const; - LLVM_ABI bool isMemDepEnabled() const; - LLVM_ABI bool isMemorySSAEnabled() const; - /// This class holds the mapping between values and value numbers. It is used /// as an efficient mechanism to determine the expression-wise equivalence of /// two values. @@ -210,6 +183,7 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { LLVM_ABI ~ValueTable(); LLVM_ABI ValueTable &operator=(const ValueTable &Arg); + LLVM_ABI void add(Value *V, uint32_t Num); LLVM_ABI uint32_t lookupOrAdd(MemoryAccess *MA); LLVM_ABI uint32_t lookupOrAdd(Value *V); LLVM_ABI uint32_t lookup(Value *V, bool Verify = true) const; @@ -222,7 +196,6 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { LLVM_ABI void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock); LLVM_ABI bool exists(Value *V) const; - LLVM_ABI void add(Value *V, uint32_t Num); LLVM_ABI void clear(); LLVM_ABI void erase(Value *V); void setAliasAnalysis(AAResults *A) { AA = A; } @@ -244,6 +217,7 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { friend class GVNLegacyPass; friend struct DenseMapInfo<Expression>; + GVNOptions Options; MemoryDependenceResults *MD = nullptr; DominatorTree *DT = nullptr; const TargetLibraryInfo *TLI = nullptr; @@ -254,7 +228,6 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { LoopInfo *LI = nullptr; AAResults *AA = nullptr; MemorySSAUpdater *MSSAU = nullptr; - ValueTable VN; /// A mapping from value numbers to lists of Value*'s that @@ -346,18 +319,35 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { // of BlockRPONumber prior to accessing the contents of BlockRPONumber. bool InvalidBlockRPONumbers = true; + // List of critical edges to be split between iterations. + SmallVector<std::pair<Instruction *, unsigned>, 4> ToSplit; + +public: + GVNPass(GVNOptions Options = {}) : Options(Options) {} + + /// Run the pass over the function. + LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + LLVM_ABI void + printPipeline(raw_ostream &OS, + function_ref<StringRef(StringRef)> MapClassName2PassName); + +private: + DominatorTree &getDominatorTree() const { return *DT; } + AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); } + MemoryDependenceResults &getMemDep() const { return *MD; } + + bool isScalarPREEnabled() const; + bool isLoadPREEnabled() const; + bool isLoadInLoopPREEnabled() const; + bool isLoadPRESplitBackedgeEnabled() const; + bool isMemDepEnabled() const; + bool isMemorySSAEnabled() const; + using LoadDepVect = SmallVector<NonLocalDepResult, 64>; using AvailValInBlkVect = SmallVector<AvailableValueInBlock, 64>; using UnavailBlkVect = SmallVector<BasicBlock *, 64>; - bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, - const TargetLibraryInfo &RunTLI, AAResults &RunAA, - MemoryDependenceResults *RunMD, LoopInfo &LI, - OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr); - - // List of critical edges to be split between iterations. - SmallVector<std::pair<Instruction *, unsigned>, 4> ToSplit; - enum class DepKind { Other = 0, // Unknown value. Def, // Exactly overlapping locations. @@ -416,6 +406,41 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { using DependencyBlockSet = DenseMap<BasicBlock *, DependencyBlockInfo>; + /// Given a select-dependency for the load (the load address is a select of + /// \p TrueAddr and \p FalseAddr guarded by \p Cond), determine whether a + /// value is available by finding dominating values for both addresses. If + /// so, the load can be rematerialized as a select of those two values. + std::optional<AvailableValue> + analyzeSelectAvailability(LoadInst *Load, Value *Cond, Value *TrueAddr, + Value *FalseAddr, Instruction *From); + + /// Given a local dependency (Def or Clobber) determine if a value is + /// available for the load. + std::optional<AvailableValue> + analyzeLoadAvailability(LoadInst *Load, const ReachingMemVal &Dep, + Value *Address); + + /// Given a list of non-local dependencies, determine if a value is + /// available for the load in each specified block. If it is, add it to + /// ValuesPerBlock. If not, add it to UnavailableBlocks. + void analyzeLoadAvailability(LoadInst *Load, + SmallVectorImpl<ReachingMemVal> &Deps, + AvailValInBlkVect &ValuesPerBlock, + UnavailBlkVect &UnavailableBlocks); + + /// Given a critical edge from Pred to LoadBB, find a load instruction + /// which is identical to Load from another successor of Pred. + LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB, + LoadInst *Load); + + /// Eliminates partially redundant \p Load, replacing it with \p + /// AvailableLoads (connected by Phis if needed). + void eliminatePartiallyRedundantLoad( + LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, + MapVector<BasicBlock *, Value *> &AvailableLoads, + MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad); + + // Helper functions for d etermining load dependencies. std::optional<GVNPass::ReachingMemVal> scanMemoryAccessesUsers( const MemoryLocation &Loc, bool IsInvariantLoad, BasicBlock *BB, const SmallVectorImpl<MemoryAccess *> &ClobbersList, MemorySSA &MSSA, @@ -438,40 +463,6 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { SmallVectorImpl<ReachingMemVal> &Values, MemorySSA &MSSA, AAResults &AA); - // Helper functions of redundant load elimination. - bool processLoad(LoadInst *L); - bool processMaskedLoad(IntrinsicInst *I); - bool processNonLocalLoad(LoadInst *L); - bool processNonLocalLoad(LoadInst *L, SmallVectorImpl<ReachingMemVal> &Deps); - bool processAssumeIntrinsic(AssumeInst *II); - - /// Given a local dependency (Def or Clobber) determine if a value is - /// available for the load. - std::optional<AvailableValue> - analyzeLoadAvailability(LoadInst *Load, const ReachingMemVal &Dep, - Value *Address); - - /// Given a select-dependency for the load (the load address is a select of - /// \p TrueAddr and \p FalseAddr guarded by \p Cond), determine whether a - /// value is available by finding dominating values for both addresses. If - /// so, the load can be rematerialized as a select of those two values. - std::optional<AvailableValue> - analyzeSelectAvailability(LoadInst *Load, Value *Cond, Value *TrueAddr, - Value *FalseAddr, Instruction *From); - - /// Given a list of non-local dependencies, determine if a value is - /// available for the load in each specified block. If it is, add it to - /// ValuesPerBlock. If not, add it to UnavailableBlocks. - void analyzeLoadAvailability(LoadInst *Load, - SmallVectorImpl<ReachingMemVal> &Deps, - AvailValInBlkVect &ValuesPerBlock, - UnavailBlkVect &UnavailableBlocks); - - /// Given a critical edge from Pred to LoadBB, find a load instruction - /// which is identical to Load from another successor of Pred. - LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB, - LoadInst *Load); - bool performLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks); @@ -481,31 +472,63 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, UnavailBlkVect &UnavailableBlocks); - /// Eliminates partially redundant \p Load, replacing it with \p - /// AvailableLoads (connected by Phis if needed). - void eliminatePartiallyRedundantLoad( - LoadInst *Load, AvailValInBlkVect &ValuesPerBlock, - MapVector<BasicBlock *, Value *> &AvailableLoads, - MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad); + // Try to eliminate redundent loades with non-local dependencies. + bool processNonLocalLoad(LoadInst *L); + bool processNonLocalLoad(LoadInst *L, SmallVectorImpl<ReachingMemVal> &Deps); - // Other helper routines. + /// Add any blocks determined to be unreachable by a conditional branch with a + /// constant condition to the dead blocks. + bool processFoldableCondBr(CondBrInst *BI); + + /// Propagate equalities derived from llvm.assume intrinsics. + bool processAssumeIntrinsic(AssumeInst *II); + + /// Try to eliminate redundant loads. + bool processLoad(LoadInst *L); + + /// Try to eliminate masked loads which have loaded from + /// masked stores with the same mask. + bool processMaskedLoad(IntrinsicInst *I); + + /// Propagate value of a condition to blocks dominated by "then" and "else" + /// edges, as well as certains derived equalities. + bool + propagateEquality(Value *LHS, Value *RHS, + const std::variant<BasicBlockEdge, Instruction *> &Root); + + // Pass iteration helper functions. bool processInstruction(Instruction *I); bool processBlock(BasicBlock *BB); bool iterateOnFunction(Function &F); - bool performPRE(Function &F); - bool performScalarPRE(Instruction *I); + + // Scalar PRE helper functions bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, BasicBlock *Curr, unsigned int ValNo); + bool performScalarPRE(Instruction *I); + bool performPRE(Function &F); + + /// Main entry point for the GVN pass. Also used by the GVNLegacyPass. + bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, + const TargetLibraryInfo &RunTLI, AAResults &RunAA, + MemoryDependenceResults *RunMD, LoopInfo &LI, + OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr); + + // Other helper routines. + Value *findLeader(const BasicBlock *BB, uint32_t Num); void cleanupGlobalSets(); + void removeInstruction(Instruction *I); + + /// This removes the specified instruction from + /// our various maps and marks it for deletion. + void salvageAndRemoveInstruction(Instruction *I); + void verifyRemoved(const Instruction *I) const; + bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); - bool - propagateEquality(Value *LHS, Value *RHS, - const std::variant<BasicBlockEdge, Instruction *> &Root); - bool processFoldableCondBr(CondBrInst *BI); + void addDeadBlock(BasicBlock *BB); void assignValNumForDeadCode(); void assignBlockRPONumber(Function &F); diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 155308f0e7f71..f16d1fe9ca893 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -289,6 +289,72 @@ struct llvm::GVNPass::AvailableValue { Value *MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt) const; }; +Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load, + Instruction *InsertPt) const { + Value *Res; + Type *LoadTy = Load->getType(); + const DataLayout &DL = Load->getDataLayout(); + if (isSimpleValue()) { + Res = getSimpleValue(); + if (Res->getType() != LoadTy) { + Res = getValueForLoad(Res, Offset, LoadTy, InsertPt, Load->getFunction()); + + LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset + << " " << *getSimpleValue() << '\n' + << *Res << '\n' + << "\n\n\n"); + } + } else if (isCoercedLoadValue()) { + LoadInst *CoercedLoad = getCoercedLoadValue(); + if (CoercedLoad->getType() == LoadTy && Offset == 0) { + Res = CoercedLoad; + combineMetadataForCSE(CoercedLoad, Load, false); + } else { + Res = getValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt, + Load->getFunction()); + // We are adding a new user for this load, for which the original + // metadata may not hold. Additionally, the new load may have a different + // size and type, so their metadata cannot be combined in any + // straightforward way. + // Drop all metadata that is not known to cause immediate UB on violation, + // unless the load has !noundef, in which case all metadata violations + // will be promoted to UB. + // !noalias and !alias.scope are kept: the load is not moved and still + // accesses the same memory, and these are independent of the load type + // and offset, so they remain valid for the coerced result. + if (!CoercedLoad->hasMetadata(LLVMContext::MD_noundef)) + CoercedLoad->dropUnknownNonDebugMetadata( + {LLVMContext::MD_dereferenceable, + LLVMContext::MD_dereferenceable_or_null, + LLVMContext::MD_invariant_load, LLVMContext::MD_invariant_group, + LLVMContext::MD_alias_scope, LLVMContext::MD_noalias}); + LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset + << " " << *getCoercedLoadValue() << '\n' + << *Res << '\n' + << "\n\n\n"); + } + } else if (isMemIntrinValue()) { + Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy, InsertPt, + DL); + LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset + << " " << *getMemIntrinValue() << '\n' + << *Res << '\n' + << "\n\n\n"); + } else if (isSelectValue()) { + // Introduce a new value select for a load from an eligible pointer select. + Value *Cond = getSelectCondition(); + assert(V1 && V2 && "both value operands of the select must be present"); + Res = SelectInst::Create(Cond, V1, V2, "", InsertPt->getIterator()); + // We use the DebugLoc from the original load here, as this instruction + // materializes the value that would previously have been loaded. + cast<SelectInst>(Res)->setDebugLoc(Load->getDebugLoc()); + } else { + llvm_unreachable("Should not materialize value from dead block"); + } + assert(Res && "failed to materialize?"); + return Res; +} + /// Represents an AvailableValue which can be rematerialized at the end of /// the associated BasicBlock. struct llvm::GVNPass::AvailableValueInBlock { @@ -452,37 +518,6 @@ GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) { return E; } -//===----------------------------------------------------------------------===// -// 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) { - ValueNumbering.insert(std::make_pair(V, Num)); - if (PHINode *PN = dyn_cast<PHINode>(V)) - NumberingPhi[Num] = PN; -} - -/// Include the incoming memory state into the hash of the expression for the -/// given instruction. If the incoming memory state is: -/// * LiveOnEntry, add the value number of the entry block, -/// * a MemoryPhi, add the value number of the basic block corresponding to that -/// MemoryPhi, -/// * a MemoryDef, add the value number of the memory setting instruction. -void GVNPass::ValueTable::addMemoryStateToExp(Instruction *I, Expression &Exp) { - assert(MSSA && "addMemoryStateToExp should not be called without MemorySSA"); - assert(MSSA->getMemoryAccess(I) && "Instruction does not access memory"); - MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I); - Exp.VarArgs.push_back(lookupOrAdd(MA)); -} - uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) { // FIXME: Currently the calls which may access the thread id may // be considered as not accessing the memory. But this is @@ -634,133 +669,326 @@ uint32_t GVNPass::ValueTable::computeLoadStoreVN(Instruction *I) { return V; } -/// Returns true if a value number exists for the specified value. -bool GVNPass::ValueTable::exists(Value *V) const { - return ValueNumbering.contains(V); -} +/// 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) { + // See if we can refine the value number by looking at the PN incoming value + // for the given predecessor. + if (PHINode *PN = NumberingPhi[Num]) { + if (PN->getParent() != PhiBlock) + return Num; + for (unsigned I = 0; I != PN->getNumIncomingValues(); ++I) { + if (PN->getIncomingBlock(I) != Pred) + continue; + if (uint32_t TransVal = lookup(PN->getIncomingValue(I), false)) + return TransVal; + } + return Num; + } -uint32_t GVNPass::ValueTable::lookupOrAdd(MemoryAccess *MA) { - return MSSA->isLiveOnEntryDef(MA) || isa<MemoryPhi>(MA) - ? lookupOrAdd(MA->getBlock()) - : lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst()); -} + if (BasicBlock *BB = NumberingBB[Num]) { + assert(MSSA && "NumberingBB is non-empty only when using MemorySSA"); + // Value numbers of basic blocks are used to represent memory state in + // load/store instructions and read-only function calls when said state is + // set by a MemoryPhi. + if (BB != PhiBlock) + return Num; + MemoryPhi *MPhi = MSSA->getMemoryAccess(BB); + for (unsigned i = 0, N = MPhi->getNumIncomingValues(); i != N; ++i) { + if (MPhi->getIncomingBlock(i) != Pred) + continue; + MemoryAccess *MA = MPhi->getIncomingValue(i); + if (auto *PredPhi = dyn_cast<MemoryPhi>(MA)) + return lookupOrAdd(PredPhi->getBlock()); + if (MSSA->isLiveOnEntryDef(MA)) + return lookupOrAdd(&BB->getParent()->getEntryBlock()); + return lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst()); + } + llvm_unreachable( + "CFG/MemorySSA mismatch: predecessor not found among incoming blocks"); + } -/// lookupOrAdd - Returns the value number for the specified value, assigning -/// it a new number if it did not hav... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/210334 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
