https://github.com/momchil-velikov updated https://github.com/llvm/llvm-project/pull/211024
>From 6096261b4f019ad2a533b471ba426369158b8322 Mon Sep 17 00:00:00 2001 From: Momchil Velikov <[email protected]> Date: Tue, 21 Jul 2026 16:27:12 +0100 Subject: [PATCH 1/2] [GVN] Restructure `GVN.h` to reduce its size (NFC) * Rename `GVNPass::ValueTable` to `GVNValueTable`, and move it out to the `llvm` 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. --- llvm/include/llvm/Transforms/Scalar/GVN.h | 169 +----------------- .../include/llvm/Transforms/Scalar/GVNHoist.h | 30 ++++ llvm/include/llvm/Transforms/Scalar/GVNSink.h | 30 ++++ .../llvm/Transforms/Scalar/GVNValueTable.h | 164 +++++++++++++++++ llvm/lib/Passes/PassBuilder.cpp | 2 + llvm/lib/Passes/PassBuilderPipelines.cpp | 2 + llvm/lib/Transforms/Scalar/GVN.cpp | 161 +++++++++++------ llvm/lib/Transforms/Scalar/GVNHoist.cpp | 14 +- llvm/lib/Transforms/Scalar/GVNSink.cpp | 2 +- 9 files changed, 354 insertions(+), 220 deletions(-) create mode 100644 llvm/include/llvm/Transforms/Scalar/GVNHoist.h create mode 100644 llvm/include/llvm/Transforms/Scalar/GVNSink.h create mode 100644 llvm/include/llvm/Transforms/Scalar/GVNValueTable.h 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) { +GVNValueTable::Expression +GVNValueTable::createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate, + Value *LHS, Value *RHS) { assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && "Not a comparison!"); Expression E; @@ -457,8 +458,8 @@ GVNPass::Expression GVNPass::ValueTable::createCmpExpr( return E; } -GVNPass::Expression -GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) { +GVNValueTable::Expression +GVNValueTable::createExtractvalueExpr(ExtractValueInst *EI) { assert(EI && "Not an ExtractValueInst?"); Expression E; E.Ty = EI->getType(); @@ -486,7 +487,7 @@ GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) { return E; } -GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) { +GVNValueTable::Expression GVNValueTable::createGEPExpr(GetElementPtrInst *GEP) { Expression E; Type *PtrTy = GEP->getType()->getScalarType(); const DataLayout &DL = GEP->getDataLayout(); @@ -518,7 +519,7 @@ GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) { return E; } -uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) { +uint32_t GVNValueTable::lookupOrAddCall(CallInst *C) { // FIXME: Currently the calls which may access the thread id may // be considered as not accessing the memory. But this is // problematic for coroutines, since coroutines may resume in a @@ -651,7 +652,7 @@ uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) { } /// Returns the value number for the specified load or store instruction. -uint32_t GVNPass::ValueTable::computeLoadStoreVN(Instruction *I) { +uint32_t GVNValueTable::computeLoadStoreVN(Instruction *I) { if (!MSSA || !IsMSSAEnabled) { ValueNumbering[I] = NextValueNumber; return NextValueNumber++; @@ -671,9 +672,9 @@ uint32_t GVNPass::ValueTable::computeLoadStoreVN(Instruction *I) { /// 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) { +uint32_t GVNValueTable::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]) { @@ -753,10 +754,9 @@ uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred, // 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) { +bool GVNValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum, + const BasicBlock *Pred, + const BasicBlock *PhiBlock, GVNPass &GVN) { CallInst *Call = nullptr; auto Leaders = GVN.LeaderTable.getLeaders(Num); for (const auto &Entry : Leaders) { @@ -788,8 +788,7 @@ bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum, /// 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) { +std::pair<uint32_t, bool> GVNValueTable::assignExpNewValueNum(Expression &Exp) { uint32_t &E = ExpressionNumbering[Exp]; bool CreateNewValNum = !E; if (CreateNewValNum) { @@ -804,11 +803,12 @@ 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) { - return all_of( - GVN.LeaderTable.getLeaders(Num), - [=](const LeaderMap::LeaderTableEntry &L) { return L.BB == BB; }); +bool GVNValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB, + GVNPass &GVN) { + return all_of(GVN.LeaderTable.getLeaders(Num), + [=](const GVNPass::LeaderMap::LeaderTableEntry &L) { + return L.BB == BB; + }); } /// Include the incoming memory state into the hash of the expression for the @@ -817,7 +817,7 @@ bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB, /// * 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) { +void GVNValueTable::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); @@ -828,21 +828,20 @@ void GVNPass::ValueTable::addMemoryStateToExp(Instruction *I, Expression &Exp) { // 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; +GVNValueTable::GVNValueTable() = default; +GVNValueTable::GVNValueTable(const GVNValueTable &) = default; +GVNValueTable::GVNValueTable(GVNValueTable &&) = default; +GVNValueTable::~GVNValueTable() = default; +GVNValueTable &GVNValueTable::operator=(const GVNValueTable &Arg) = default; /// add - Insert a value into the table with a specified value number. -void GVNPass::ValueTable::add(Value *V, uint32_t Num) { +void GVNValueTable::add(Value *V, uint32_t Num) { ValueNumbering.insert(std::make_pair(V, Num)); if (PHINode *PN = dyn_cast<PHINode>(V)) NumberingPhi[Num] = PN; } -uint32_t GVNPass::ValueTable::lookupOrAdd(MemoryAccess *MA) { +uint32_t GVNValueTable::lookupOrAdd(MemoryAccess *MA) { return MSSA->isLiveOnEntryDef(MA) || isa<MemoryPhi>(MA) ? lookupOrAdd(MA->getBlock()) : lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst()); @@ -850,7 +849,7 @@ uint32_t GVNPass::ValueTable::lookupOrAdd(MemoryAccess *MA) { /// lookupOrAdd - 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) { +uint32_t GVNValueTable::lookupOrAdd(Value *V) { auto VI = ValueNumbering.find(V); if (VI != ValueNumbering.end()) return VI->second; @@ -935,7 +934,7 @@ 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 { +uint32_t GVNValueTable::lookup(Value *V, bool Verify) const { auto VI = ValueNumbering.find(V); if (Verify) { assert(VI != ValueNumbering.end() && "Value not numbered?"); @@ -948,15 +947,15 @@ uint32_t GVNPass::ValueTable::lookup(Value *V, bool Verify) const { /// 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) { +uint32_t GVNValueTable::lookupOrAddCmp(unsigned Opcode, + CmpInst::Predicate Predicate, Value *LHS, + Value *RHS) { Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS); return assignExpNewValueNum(Exp).first; } /// Returns the value number of ptrtoint \p Ptr to \Ty. -uint32_t GVNPass::ValueTable::lookupPtrToInt(Value *Ptr, Type *Ty) { +uint32_t GVNValueTable::lookupPtrToInt(Value *Ptr, Type *Ty) { Expression Exp(Instruction::PtrToInt); Exp.Ty = Ty; Exp.VarArgs.push_back(lookupOrAdd(Ptr)); @@ -964,9 +963,9 @@ uint32_t GVNPass::ValueTable::lookupPtrToInt(Value *Ptr, Type *Ty) { } /// Wrap phiTranslateImpl to provide caching functionality. -uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred, - const BasicBlock *PhiBlock, - uint32_t Num, GVNPass &GVN) { +uint32_t GVNValueTable::phiTranslate(const BasicBlock *Pred, + const BasicBlock *PhiBlock, uint32_t Num, + GVNPass &GVN) { auto FindRes = PhiTranslateTable.find({Num, Pred}); if (FindRes != PhiTranslateTable.end()) return FindRes->second; @@ -977,19 +976,19 @@ uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred, /// Erase stale entry from phiTranslate cache so phiTranslate can be computed /// again. -void GVNPass::ValueTable::eraseTranslateCacheEntry( - uint32_t Num, const BasicBlock &CurrBlock) { +void GVNValueTable::eraseTranslateCacheEntry(uint32_t Num, + const BasicBlock &CurrBlock) { for (const BasicBlock *Pred : predecessors(&CurrBlock)) PhiTranslateTable.erase({Num, Pred}); } /// Returns true if a value number exists for the specified value. -bool GVNPass::ValueTable::exists(Value *V) const { +bool GVNValueTable::exists(Value *V) const { return ValueNumbering.contains(V); } /// Remove all entries from the ValueTable. -void GVNPass::ValueTable::clear() { +void GVNValueTable::clear() { ValueNumbering.clear(); ExpressionNumbering.clear(); NumberingPhi.clear(); @@ -1002,7 +1001,7 @@ void GVNPass::ValueTable::clear() { } /// Remove a value from the value numbering. -void GVNPass::ValueTable::erase(Value *V) { +void GVNValueTable::erase(Value *V) { uint32_t Num = ValueNumbering.lookup(V); ValueNumbering.erase(V); // If V is PHINode, V <--> value number is an one-to-one mapping. @@ -1014,7 +1013,7 @@ 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 { +void GVNValueTable::verifyRemoved(const Value *V) const { assert(!ValueNumbering.contains(V) && "Inst still occurs in value numbering map!"); } @@ -1075,6 +1074,66 @@ void GVNPass::LeaderMap::erase(uint32_t N, Instruction *I, } } +//===----------------------------------------------------------------------===// +// Helper Dependency Information Classes +//===----------------------------------------------------------------------===// + +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 GVNPass::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 GVNPass::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; +}; + //===----------------------------------------------------------------------===// // GVN Pass //===----------------------------------------------------------------------===// diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp index 3022f4a8481d0..da605664df87b 100644 --- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp +++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp @@ -66,8 +66,10 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Scalar/GVN.h" +#include "llvm/Transforms/Scalar/GVNValueTable.h" +#include "llvm/Transforms/Scalar/GVNHoist.h" #include "llvm/Transforms/Utils/Local.h" + #include <algorithm> #include <cassert> #include <memory> @@ -163,7 +165,7 @@ class InsnInfo { public: // Inserts I and its value number in VNtoScalars. - void insert(Instruction *I, GVNPass::ValueTable &VN) { + void insert(Instruction *I, GVNValueTable &VN) { // Scalar instruction. unsigned V = VN.lookupOrAdd(I); VNtoScalars[{V, InvalidVN}].push_back(I); @@ -178,7 +180,7 @@ class LoadInfo { public: // Insert Load and the value number of its memory address in VNtoLoads. - void insert(LoadInst *Load, GVNPass::ValueTable &VN) { + void insert(LoadInst *Load, GVNValueTable &VN) { if (Load->isSimple()) { unsigned V = VN.lookupOrAdd(Load->getPointerOperand()); // With opaque pointers we may have loads from the same pointer with @@ -197,7 +199,7 @@ class StoreInfo { public: // Insert the Store and a hash number of the store address and the stored // value in VNtoStores. - void insert(StoreInst *Store, GVNPass::ValueTable &VN) { + void insert(StoreInst *Store, GVNValueTable &VN) { if (!Store->isSimple()) return; // Hash the store address and the stored value. @@ -217,7 +219,7 @@ class CallInfo { public: // Insert Call and its value numbering in one of the VNtoCalls* containers. - void insert(CallInst *Call, GVNPass::ValueTable &VN) { + void insert(CallInst *Call, GVNValueTable &VN) { // A call that doesNotAccessMemory is handled as a Scalar, // onlyReadsMemory will be handled as a Load instruction, // all other calls will be handled as stores. @@ -260,7 +262,7 @@ class GVNHoist { unsigned int rank(const Value *V) const; private: - GVNPass::ValueTable VN; + GVNValueTable VN; DominatorTree *DT; PostDominatorTree *PDT; AliasAnalysis *AA; diff --git a/llvm/lib/Transforms/Scalar/GVNSink.cpp b/llvm/lib/Transforms/Scalar/GVNSink.cpp index 67196ef9715f1..48782be4bbcc0 100644 --- a/llvm/lib/Transforms/Scalar/GVNSink.cpp +++ b/llvm/lib/Transforms/Scalar/GVNSink.cpp @@ -61,8 +61,8 @@ #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Scalar/GVNExpression.h" +#include "llvm/Transforms/Scalar/GVNSink.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/LockstepReverseIterator.h" >From 3c4ea8c411ee80ade64b75a48b40beae90a68423 Mon Sep 17 00:00:00 2001 From: Momchil Velikov <[email protected]> Date: Wed, 22 Jul 2026 11:08:35 +0100 Subject: [PATCH 2/2] [fixup] Fix formatting --- llvm/lib/Transforms/Scalar/GVNHoist.cpp | 2 +- llvm/lib/Transforms/Scalar/GVNSink.cpp | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp index da605664df87b..756315ad3e761 100644 --- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp +++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp @@ -33,6 +33,7 @@ // 2. geps when corresponding load/store cannot be hoisted. //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/GVNHoist.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" @@ -67,7 +68,6 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar/GVNValueTable.h" -#include "llvm/Transforms/Scalar/GVNHoist.h" #include "llvm/Transforms/Utils/Local.h" #include <algorithm> diff --git a/llvm/lib/Transforms/Scalar/GVNSink.cpp b/llvm/lib/Transforms/Scalar/GVNSink.cpp index 48782be4bbcc0..a54538170a82a 100644 --- a/llvm/lib/Transforms/Scalar/GVNSink.cpp +++ b/llvm/lib/Transforms/Scalar/GVNSink.cpp @@ -33,6 +33,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/GVNSink.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Hashing.h" @@ -62,7 +63,6 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar/GVNExpression.h" -#include "llvm/Transforms/Scalar/GVNSink.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/LockstepReverseIterator.h" _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
