llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-transforms Author: Momchil Velikov (momchil-velikov) <details> <summary>Changes</summary> * Rename `GVNPass::ValueTable` to `GVNValueTable`, and move it out to the `llvm` namespace and to its own file `GVNValueTable.h` (the type is also used by `GVNHoistPass` and it makes sense to have it in a separate file instead of `GVNHoistPass` peeking into `GVN.h`). * Move `GVNPass::Expression` into `llvm::GVNValueTable`. * Move `DepKind`, `ReachingMemVal`, and `DependencyBlockInfo` to `GVN.cpp`. * Move `GVNHoistPass` and `GVNSinkPass` to their own headers. --- Patch is 36.37 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/211024.diff 9 Files Affected: - (modified) llvm/include/llvm/Transforms/Scalar/GVN.h (+7-162) - (added) llvm/include/llvm/Transforms/Scalar/GVNHoist.h (+30) - (added) llvm/include/llvm/Transforms/Scalar/GVNSink.h (+30) - (added) llvm/include/llvm/Transforms/Scalar/GVNValueTable.h (+164) - (modified) llvm/lib/Passes/PassBuilder.cpp (+2) - (modified) llvm/lib/Passes/PassBuilderPipelines.cpp (+2) - (modified) llvm/lib/Transforms/Scalar/GVN.cpp (+110-51) - (modified) llvm/lib/Transforms/Scalar/GVNHoist.cpp (+8-6) - (modified) llvm/lib/Transforms/Scalar/GVNSink.cpp (+1-1) ``````````diff diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h index 383b265586674..4d8a2d3eda820 100644 --- a/llvm/include/llvm/Transforms/Scalar/GVN.h +++ b/llvm/include/llvm/Transforms/Scalar/GVN.h @@ -26,6 +26,8 @@ #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Compiler.h" +#include "llvm/Transforms/Scalar/GVNValueTable.h" + #include <cstdint> #include <optional> #include <utility> @@ -122,102 +124,15 @@ struct GVNOptions { /// this particular pass here. class GVNPass : public OptionalPassInfoMixin<GVNPass> { public: - struct Expression; struct AvailableValue; struct AvailableValueInBlock; - /// 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. - class ValueTable { - DenseMap<Value *, uint32_t> ValueNumbering; - DenseMap<Expression, uint32_t> ExpressionNumbering; - - // Expressions is the vector of Expression. ExprIdx is the mapping from - // value number to the index of Expression in Expressions. We use it - // instead of a DenseMap because filling such mapping is faster than - // filling a DenseMap and the compile time is a little better. - uint32_t NextExprNumber = 0; - - std::vector<Expression> Expressions; - std::vector<uint32_t> ExprIdx; - - // Value number to PHINode mapping. Used for phi-translate in scalarpre. - DenseMap<uint32_t, PHINode *> NumberingPhi; - - // Value number to BasicBlock mapping. Used for phi-translate across - // MemoryPhis. - DenseMap<uint32_t, BasicBlock *> NumberingBB; - - // Cache for phi-translate in scalarpre. - using PhiTranslateMap = - DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>; - PhiTranslateMap PhiTranslateTable; - - AAResults *AA = nullptr; - MemoryDependenceResults *MD = nullptr; - bool IsMDEnabled = false; - MemorySSA *MSSA = nullptr; - bool IsMSSAEnabled = false; - DominatorTree *DT = nullptr; - - uint32_t NextValueNumber = 1; - - Expression createExpr(Instruction *I); - Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, - Value *LHS, Value *RHS); - Expression createExtractvalueExpr(ExtractValueInst *EI); - Expression createGEPExpr(GetElementPtrInst *GEP); - uint32_t lookupOrAddCall(CallInst *C); - uint32_t computeLoadStoreVN(Instruction *I); - uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, - uint32_t Num, GVNPass &GVN); - bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred, - const BasicBlock *PhiBlock, GVNPass &GVN); - std::pair<uint32_t, bool> assignExpNewValueNum(Expression &Exp); - bool areAllValsInBB(uint32_t Num, const BasicBlock *BB, GVNPass &GVN); - void addMemoryStateToExp(Instruction *I, Expression &Exp); - - public: - LLVM_ABI ValueTable(); - LLVM_ABI ValueTable(const ValueTable &Arg); - LLVM_ABI ValueTable(ValueTable &&Arg); - 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; - LLVM_ABI uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, - Value *LHS, Value *RHS); - LLVM_ABI uint32_t lookupPtrToInt(Value *Ptr, Type *Ty); - LLVM_ABI uint32_t phiTranslate(const BasicBlock *BB, - const BasicBlock *PhiBlock, uint32_t Num, - GVNPass &GVN); - LLVM_ABI void eraseTranslateCacheEntry(uint32_t Num, - const BasicBlock &CurrBlock); - LLVM_ABI bool exists(Value *V) const; - LLVM_ABI void clear(); - LLVM_ABI void erase(Value *V); - void setAliasAnalysis(AAResults *A) { AA = A; } - AAResults *getAliasAnalysis() const { return AA; } - void setMemDep(MemoryDependenceResults *M, bool MDEnabled = true) { - MD = M; - IsMDEnabled = MDEnabled; - } - void setMemorySSA(MemorySSA *M, bool MSSAEnabled = false) { - MSSA = M; - IsMSSAEnabled = MSSAEnabled; - } - void setDomTree(DominatorTree *D) { DT = D; } - uint32_t getNextUnusedValueNumber() { return NextValueNumber; } - LLVM_ABI void verifyRemoved(const Value *) const; - }; + struct ReachingMemVal; + struct DependencyBlockInfo; -private: + friend class GVNValueTable; friend class GVNLegacyPass; - friend struct DenseMapInfo<Expression>; +private: GVNOptions Options; MemoryDependenceResults *MD = nullptr; DominatorTree *DT = nullptr; @@ -229,7 +144,7 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { LoopInfo *LI = nullptr; AAResults *AA = nullptr; MemorySSAUpdater *MSSAU = nullptr; - ValueTable VN; + GVNValueTable VN; /// A mapping from value numbers to lists of Value*'s that /// have that value number. Use findLeader to query it. @@ -349,62 +264,6 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { using AvailValInBlkVect = SmallVector<AvailableValueInBlock, 64>; using UnavailBlkVect = SmallVector<BasicBlock *, 64>; - enum class DepKind { - Other = 0, // Unknown value. - Def, // Exactly overlapping locations. - Clobber, // Reaching value superset of needed bits. - Select, // Reaching value is a select of two reaching addresses. - }; - - // Describe a memory location value, such that there exists a path to a point - // in the program, along which that memory location is not modified. - struct ReachingMemVal { - DepKind Kind; - BasicBlock *Block; - const Value *Addr; - Instruction *Inst; - int32_t Offset; - // For DepKind::Select only: the condition and the two addresses referenced - // by the "true" and "false" side of the select-dependent load. - const Value *SelCond = nullptr; - const Value *SelTrueAddr = nullptr; - const Value *SelFalseAddr = nullptr; - - static ReachingMemVal getUnknown(BasicBlock *BB, const Value *Addr, - Instruction *Inst = nullptr) { - return {DepKind::Other, BB, Addr, Inst, -1}; - } - - static ReachingMemVal getDef(const Value *Addr, Instruction *Inst) { - return {DepKind::Def, Inst->getParent(), Addr, Inst, -1}; - } - - static ReachingMemVal getClobber(const Value *Addr, Instruction *Inst, - int32_t Offset = -1) { - return {DepKind::Clobber, Inst->getParent(), Addr, Inst, Offset}; - } - - static ReachingMemVal getSelect(BasicBlock *BB, const Value *Cond, - const Value *TrueAddr, - const Value *FalseAddr) { - return {DepKind::Select, BB, nullptr, nullptr, -1, Cond, - TrueAddr, FalseAddr}; - } - }; - - struct DependencyBlockInfo { - DependencyBlockInfo() = delete; - DependencyBlockInfo(const PHITransAddr &Addr, MemoryAccess *ClobberMA) - : Addr(Addr), InitialClobberMA(ClobberMA), ClobberMA(ClobberMA), - ForceUnknown(false), Visited(false) {} - PHITransAddr Addr; - MemoryAccess *InitialClobberMA; - MemoryAccess *ClobberMA; - std::optional<ReachingMemVal> MemVal; - bool ForceUnknown : 1; - bool Visited : 1; - }; - using DependencyBlockSet = DenseMap<BasicBlock *, DependencyBlockInfo>; /// Given a select-dependency for the load (the load address is a select of @@ -539,20 +398,6 @@ class GVNPass : public OptionalPassInfoMixin<GVNPass> { LLVM_ABI FunctionPass *createGVNPass(bool ScalarPRE); LLVM_ABI FunctionPass *createGVNPass(); -/// A simple and fast domtree-based GVN pass to hoist common expressions -/// from sibling branches. -struct GVNHoistPass : OptionalPassInfoMixin<GVNHoistPass> { - /// Run the pass over the function. - LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); -}; - -/// Uses an "inverted" value numbering to decide the similarity of -/// expressions and sinks similar expressions into successors. -struct GVNSinkPass : OptionalPassInfoMixin<GVNSinkPass> { - /// Run the pass over the function. - LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); -}; - } // end namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_GVN_H diff --git a/llvm/include/llvm/Transforms/Scalar/GVNHoist.h b/llvm/include/llvm/Transforms/Scalar/GVNHoist.h new file mode 100644 index 0000000000000..2ab562b13247a --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/GVNHoist.h @@ -0,0 +1,30 @@ +//===- GVNHoist.h - Hoist scalar and load expressions ---------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file provides the interface for the GVNHoist pass. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GVNHOIST_H +#define LLVM_TRANSFORMS_SCALAR_GVNHOIST_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A simple and fast domtree-based GVN pass to hoist common expressions +/// from sibling branches. +struct GVNHoistPass : OptionalPassInfoMixin<GVNHoistPass> { + /// Run the pass over the function. + LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_GVNHOIST_H diff --git a/llvm/include/llvm/Transforms/Scalar/GVNSink.h b/llvm/include/llvm/Transforms/Scalar/GVNSink.h new file mode 100644 index 0000000000000..f8dafc87d716c --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/GVNSink.h @@ -0,0 +1,30 @@ +//===- GVNSink.h - Sink expressions into successors -----------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file provides the interface for the GVNSink pass. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GVNSINK_H +#define LLVM_TRANSFORMS_SCALAR_GVNSINK_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Uses an "inverted" value numbering to decide the similarity of +/// expressions and sinks similar expressions into successors. +struct GVNSinkPass : OptionalPassInfoMixin<GVNSinkPass> { + /// Run the pass over the function. + LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_GVNSINK_H diff --git a/llvm/include/llvm/Transforms/Scalar/GVNValueTable.h b/llvm/include/llvm/Transforms/Scalar/GVNValueTable.h new file mode 100644 index 0000000000000..5d93461c1260c --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/GVNValueTable.h @@ -0,0 +1,164 @@ +//===- GVNValueTable.h - Value table for GVN ------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file provides a data structure for mapping values and expressions to +/// congruence class IDs. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GVNVALUETABLE_H +#define LLVM_TRANSFORMS_SCALAR_GVNVALUETABLE_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Transforms/Scalar/GVNValueTable.h" + +#include <cstdint> +#include <optional> +#include <utility> +#include <variant> +#include <vector> + +namespace llvm { + +class AAResults; +class AssumeInst; +class AssumptionCache; +class BasicBlock; +class BatchAAResults; +class CallInst; +class CondBrInst; +class EarliestEscapeAnalysis; +class ExtractValueInst; +class Function; +class FunctionPass; +class GVNLegacyPass; +class GVNPass; +class GetElementPtrInst; +class ImplicitControlFlowTracking; +class LoadInst; +class LoopInfo; +class MemDepResult; +class MemoryAccess; +class MemoryDependenceResults; +class MemoryLocation; +class MemorySSA; +class MemorySSAUpdater; +class NonLocalDepResult; +class OptimizationRemarkEmitter; +class PHINode; +class TargetLibraryInfo; +class Value; +class IntrinsicInst; + +/// 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. +class GVNValueTable { +public: + struct Expression; + +private: + DenseMap<Value *, uint32_t> ValueNumbering; + DenseMap<Expression, uint32_t> ExpressionNumbering; + + // Expressions is the vector of Expression. ExprIdx is the mapping from + // value number to the index of Expression in Expressions. We use it + // instead of a DenseMap because filling such mapping is faster than + // filling a DenseMap and the compile time is a little better. + uint32_t NextExprNumber = 0; + + std::vector<Expression> Expressions; + std::vector<uint32_t> ExprIdx; + + // Value number to PHINode mapping. Used for phi-translate in scalarpre. + DenseMap<uint32_t, PHINode *> NumberingPhi; + + // Value number to BasicBlock mapping. Used for phi-translate across + // MemoryPhis. + DenseMap<uint32_t, BasicBlock *> NumberingBB; + + // Cache for phi-translate in scalarpre. + using PhiTranslateMap = + DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>; + PhiTranslateMap PhiTranslateTable; + + AAResults *AA = nullptr; + MemoryDependenceResults *MD = nullptr; + bool IsMDEnabled = false; + MemorySSA *MSSA = nullptr; + bool IsMSSAEnabled = false; + DominatorTree *DT = nullptr; + + uint32_t NextValueNumber = 1; + + Expression createExpr(Instruction *I); + Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, + Value *LHS, Value *RHS); + Expression createExtractvalueExpr(ExtractValueInst *EI); + Expression createGEPExpr(GetElementPtrInst *GEP); + uint32_t lookupOrAddCall(CallInst *C); + uint32_t computeLoadStoreVN(Instruction *I); + uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock, + uint32_t Num, GVNPass &GVN); + bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred, + const BasicBlock *PhiBlock, GVNPass &GVN); + std::pair<uint32_t, bool> assignExpNewValueNum(Expression &Exp); + bool areAllValsInBB(uint32_t Num, const BasicBlock *BB, GVNPass &GVN); + void addMemoryStateToExp(Instruction *I, Expression &Exp); + +public: + LLVM_ABI GVNValueTable(); + LLVM_ABI GVNValueTable(const GVNValueTable &Arg); + LLVM_ABI GVNValueTable(GVNValueTable &&Arg); + LLVM_ABI ~GVNValueTable(); + LLVM_ABI GVNValueTable &operator=(const GVNValueTable &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; + LLVM_ABI uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, + Value *LHS, Value *RHS); + LLVM_ABI uint32_t lookupPtrToInt(Value *Ptr, Type *Ty); + LLVM_ABI uint32_t phiTranslate(const BasicBlock *BB, + const BasicBlock *PhiBlock, uint32_t Num, + GVNPass &GVN); + LLVM_ABI void eraseTranslateCacheEntry(uint32_t Num, + const BasicBlock &CurrBlock); + LLVM_ABI bool exists(Value *V) const; + LLVM_ABI void clear(); + LLVM_ABI void erase(Value *V); + void setAliasAnalysis(AAResults *A) { AA = A; } + AAResults *getAliasAnalysis() const { return AA; } + void setMemDep(MemoryDependenceResults *M, bool MDEnabled = true) { + MD = M; + IsMDEnabled = MDEnabled; + } + void setMemorySSA(MemorySSA *M, bool MSSAEnabled = false) { + MSSA = M; + IsMSSAEnabled = MSSAEnabled; + } + void setDomTree(DominatorTree *D) { DT = D; } + uint32_t getNextUnusedValueNumber() { return NextValueNumber; } + LLVM_ABI void verifyRemoved(const Value *) const; +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_GVNVALUETABLE_H diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index 17bc2a5a5afdd..2c9d32e758052 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -299,6 +299,8 @@ #include "llvm/Transforms/Scalar/FlattenCFG.h" #include "llvm/Transforms/Scalar/Float2Int.h" #include "llvm/Transforms/Scalar/GVN.h" +#include "llvm/Transforms/Scalar/GVNHoist.h" +#include "llvm/Transforms/Scalar/GVNSink.h" #include "llvm/Transforms/Scalar/GuardWidening.h" #include "llvm/Transforms/Scalar/IVUsersPrinter.h" #include "llvm/Transforms/Scalar/IndVarSimplify.h" diff --git a/llvm/lib/Passes/PassBuilderPipelines.cpp b/llvm/lib/Passes/PassBuilderPipelines.cpp index d62828c78bfe4..e46f98889e49d 100644 --- a/llvm/lib/Passes/PassBuilderPipelines.cpp +++ b/llvm/lib/Passes/PassBuilderPipelines.cpp @@ -102,6 +102,8 @@ #include "llvm/Transforms/Scalar/ExpandMemCmp.h" #include "llvm/Transforms/Scalar/Float2Int.h" #include "llvm/Transforms/Scalar/GVN.h" +#include "llvm/Transforms/Scalar/GVNHoist.h" +#include "llvm/Transforms/Scalar/GVNSink.h" #include "llvm/Transforms/Scalar/IndVarSimplify.h" #include "llvm/Transforms/Scalar/InferAlignment.h" #include "llvm/Transforms/Scalar/InstSimplifyPass.h" diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 996ed2a72cdaf..d763bab153822 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -145,7 +145,7 @@ static cl::opt<uint32_t> MaxNumInsnsPerBlock( cl::desc("Max number of instructions to scan in each basic block in GVN " "(default = 100)")); -struct llvm::GVNPass::Expression { +struct llvm::GVNValueTable::Expression { uint32_t Opcode; bool Commutative = false; // The type is not necessarily the result type of the expression, it may be @@ -178,15 +178,15 @@ struct llvm::GVNPass::Expression { } }; -template <> struct llvm::DenseMapInfo<GVNPass::Expression> { - static unsigned getHashValue(const GVNPass::Expression &E) { +template <> struct llvm::DenseMapInfo<GVNValueTable::Expression> { + static unsigned getHashValue(const GVNValueTable::Expression &E) { using llvm::hash_value; return static_cast<unsigned>(hash_value(E)); } - static bool isEqual(const GVNPass::Expression &LHS, - const GVNPass::Expression &RHS) { + static bool isEqual(const GVNValueTable::Expression &LHS, + const GVNValueTable::Expression &RHS) { return LHS == RHS; } }; @@ -391,7 +391,7 @@ struct llvm::GVNPass::AvailableValueInBlock { // ValueTable Internal Functions //===----------------------------------------------------------------------===// -GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) { +GVNValueTable::Expression GVNValueTable::createExpr(Instruction *I) { Expression E; E.Ty = I->getType(); E.Opcode = I->getOpcode(); @@ -438,8 +438,9 @@ GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) { return E; } -GVNPass::Expression GVNPass::ValueTable::createCmpExpr( - unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { +GVNValueTab... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/211024 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
